第二讲线性方程组直接方法

Linear algebra — in particular, the solution of linear systems of equations — lies at the heart of most calculations in scientific computing.

— Dongarra & Eijkhout [32], 2000.

考虑线性方程组

A x = b, \quad A \in \mathbb {R} ^ {n \times n}, b \in \mathbb {R} ^ {n}. \tag {2.1}

线性方程组的求解有着非常广泛的应用背景, 科学计算中的很多问题最后都可能归结为求解一个或多个线性方程组. 从纯数学角度来看, 这个问题已经得到了完美的解决, 因为它的解可以通过行列式直接表示出来, 即 Cramer 法则. 但在实际计算中, 由于运算量增长速度太快, 当 $n$ 较大时, 用 Cramer 法则解线性方程组是不可行的. 另外, 由于实际计算中的舍入误差, 可能会导致一系列非常严重的问题.

一个从纯数学角度看似非常简单的问题, 实际计算时可能会非常困难, 有时甚至可能是一个无法解决的问题.

一般来说, 求解线性方程组的数值方法可以分为两类: 直接法与迭代法. 本讲介绍直接法, 即 Gauss 消去法. 直接法具有良好的稳定性和健壮性, 而且在有限步内终止, 因此在工程界很受欢迎. 但由于运算量是 $\mathcal{O}(n^{3})$ , 对于大规模问题, 所需时间会很长 (这里 $n$ 表示未知量的个数). 目前, Gauss 消去法是求解中小规模线性方程组或某些具有特殊结构的大规模稀疏线性方程组的首选方法.

Gauss消去法的思想可以追溯到公元一世纪左右的《九章算术》，Newton,Gauss,Lagrange等数学家都对该方法做出了贡献,相关历史可以参见[63].

关于线性方程组直接法的相关参考文献

G. H. Golub and C. F. Van Loan, Matrix Computations, 4th, 2013. [57]
J.W. Demmel, Applied Numerical Linear Algebra, 1997. [30]
L.N.Trefethen and D.Bau,III,Numerical Linear Algebra,1997.[125]
I. S. Duff, A. M. Erisman and J. K. Reid, Direct Methods for Sparse Matrices, 2nd, 2017. [38]
T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006. [29]

后面两个文献主要是介绍大规模稀疏线性方程组的直接解法.

在本讲中, 我们总是假定系数矩阵 $A$ 是非奇异的, 即线性方程组 (2.1) 的解存在且唯一. 另外, 为了讨论方便, 我们只考虑实数情形, 对于复系数线性方程组, 其求解方法是类似的.

README

第二讲 线性方程组直接方法

关于线性方程组直接法的相关参考文献

第二讲线性方程组直接方法