线性方程组解法综述.doc

线性方程组解法的研究综述摘要： 这篇论文在说明了线性方程组的应用目的的基础上，提出了线性方程组求解的研究现状，并列举了常用的求解方法，同时说明了它们的应用条件，剖析了各种方法的不足之处。 关键词 高斯消元 迭代 病态方程组一、问题提出 在自然科学和工程实际应用中，有许多问题的求解最终都转化为线性方程组的求解问题。例如,电学中的网络问题，曲线拟合中常用的最小二乘法、样条函数插值、解非线性方程组、求解偏微分方程的差分法、有限元法和边界元法以及目前工程实践中普遍存在的反演问题等。特别是在图像恢复、模型参数估计、解卷积、带限信号外推、地震勘探等众多领域，都需要求解线性方程组。 由于线性方程组问题在理论上的重要性和在工程实际应用中的大量存在，多年来人们在这方面做了广泛深入的研究和探讨，并取得了许多有价值的成果.由于模型误差、测量误差、计算误差等各种误差的存在，常常使得线性方程组中的系数矩阵和非齐次项信息具有某种程度的近似性(即扰动性)，这种近似性显然会使得线性方程组的求解不容易得到真实的理论解。此时，不同的求解方法由于运算机理不一样，求解过程中误差积累程度就不一样，因此必然会使得不同的求解方法得到的解具有不同的逼近真解的误差程度，尤其对具有病态性的方程组而言，由于病态线性方程组的条件数很大，数据误差以及计算过程中引入的舍入误差往往会使线性方程组的解不稳定，即不管原始数据的误差多么小，都可能造成解的很大变化，使线性方程组的解严重失真。因此，许多现有的方法都是无效的，病态线性方程组的求解变得相当困难。求解线性方程组的最常用的方法主要有直接法和迭代法两大类，其中直接法中最常用的方法是高斯消元法。但是，该方法求解病态线性方程组时不能得到合理的解，误差很大。 二、研究现状 目前关于线性方程组的数值解法一般有两大类。一类是直接方法，另一类是迭代方法。直接方法最基本的是高斯消元法及其变形，这类方法是解低阶稠密矩阵方程组的有效方法，近十几年来直接法在求解具有较大型稀疏矩阵方程组方面取得了较大进展。迭代法就是用某种迭代过程去逐步逼近线性方程组的精确解，迭代法具有需要计算机的存储单元较少，程序设计简单，原始系数矩阵在计算过程中始终不变等优点，但存在收敛性及收敛速度问题。迭代法是解大型稀疏矩阵方程组的重要方法。当前对迭代算法的研究已经较为成熟，但如何使之适合新体系模型，以获得更好的性能加速一直是应用和体系设计者关心的问题。 三、常用方法比较 1.直接方法 直接方法是指假设计算过程中不产生舍入误差，经过有限次运算可求得方程组的精确解的方法。事实上，由于舍入误差的存在，用直接法一般也只能求得方程组的近似解。直接方法中主要有三种方法：克拉默法则、高斯消元法、LU 分解法。 （1）克拉默法则 设有线性方程组（ n 个未知数 n 个方程） 其矩阵形式为 Ax = b其中如果线性方程组的系数行列式不为零，即 det( A) 0 ,则该方程组有唯一解。由克拉默法则知，其解为 其中Ai为上述方程组的右端向量b代替A中第i列向量所得的矩阵。（2） 高斯消元法 设 （1）如果，将第一个方程中x1的系数化为 1，得 其中 从其它n 1 个方程中消x1，使它变成如下形式 由方程（1）到（2）的过程中，元素 a11 起着重要的作用，特别地，把 a11称为主元素。如果（2）中a220，则以a22（1）为主元素，可以把方程组（3）化为： （3）针对（3）继续消元，重复同样的手段，第 k 步所要加工的方程组是： 设 a 0 ，第k步先使上述方程组中第k个方程中x 的系数化为 1， 然后再从其它（n - k）个方程中消，消元公式为: 按照上述步骤进行 n 次后,将原方程组加工成下列形式: 回代公式为: 综上所述,高斯消去法分为消元过程与回代过程，消元过程将所给方程组加工成上三角形方程组，再经回代过程求解。 由于计算时不涉及xi, i = 1, 2, , n，所以在存贮时可将方程组AX = b，写成增广矩阵（A, b）存贮。 下面，我们统计一下高斯消去法的工作量；在（4）第一个式子中，每执行一次需要 n (n k) 次除法，在（4）第二个式子中，每执行一次需要n (k 1) (n k)次除法。因此在消元过程中，共需要 次乘作法。此外，回代过程共有次乘法。汇总在一起，高斯消元法的计算量为：。( 3）选主元的高斯消元法 主元素法一般包括两种：列主元素法和全主元素法。这两种主元素法的精度差不多，且全主元素法程序设计复杂且占用机器时间较多。在实际应用中一般采用列主元素法，它既简单又能保证计算精度。方法如下： 给定线性方程组 Ax = b ，设 （1）列主元的高斯消元法的具体过程如下：第一步：首先在增广矩阵（1）中的第一列选取绝对值最大的元，如，则有，将（1）中的第一列屿第列互换。为方便起见，记行互换后的增广矩阵为 ，然后进行第一次消元，得矩阵： 第二步：在矩阵A（2），b（2）的第二列中选主元，比如，将矩阵A（2），b（2）的第二行与第i2 进行互换，再进行第二次消元，得矩阵A（3），b（3）.第 k 步：在矩阵 A(k)，b（k）的第k 列中选主元，进行第 k 次消元。 如此，经过 n 1步，增广矩阵（1）被化成上三角形，最后由回代过程求解。并且可证明，只要det（A）0，列主元素法就可以顺利完成，即不会出现akk（k）=0的情景。（4）矩阵的三角分解法 把一个 n 阶方阵 A 分解成结构简单的三角形矩阵称为矩阵的三角分解。事实上，只要 A 非奇异，经过一定的行交换后，它一定可以分解成两个三角形矩阵的乘积。 设 A = LU ,其中 L 为单位下三角矩阵，U 为上三角矩阵。 对矩阵 A 进行 LU 分解是有条件的，它要求在对 A 进行高斯消元的时候，所有的主元素均不为零。那么，A 满足什么条件才能保证这一要求呢？见下面的定理。 定理：若 A 为n 阶矩阵，且所有顺序主子式都不等于零，则存在唯一的单位下三角矩阵 L 和上三角矩阵U 使 A = LU 。 如果线性方程组 Ax = b 的系数矩阵已经进行三角分解，A = LU ，则解方程组Ax = b 等价于求解两个三角形方程组 Ly = b, Ux = y，即由 可求出 再由 解得 用三角分解法求解线性方程组的乘法运算量是数量级。由于在求出，yi 后， a ij 和 bi 就无须保留了，故上机计算时，可把 L,U 和 y 存在 A, b 所占的单元，回代时 x 取代 y ，整个计算过程中不需要增加新的存储单元。而且系数矩阵的三角分解与右端常数项无关，故在计算系数矩阵相同而右端项不同的一系列方程组时，用三角分解法更为简便。2.迭代方法 迭代法是从某一取定的初始向量x（0）出发，构造一个适当的迭代公式，逐次计算出向量x（1），x（2），.，使得向量 x（k）收敛于方程组的精确解。这样，取适当大的k，可取x（k）方程组的近似解。与直接法不同的是，即使在计算过程中无L舍入误差，迭代法也难以获得精确解。而迭代法具有计算简单，易于编制程序等优点，特别适合于求解大型稀疏线性方程组。 （1）雅可比（Jacobi）迭代法 的系数矩阵A非奇异，不妨设aii0，将方程组（2）变形为 建立迭代公式 取初始量x（0）后，由式三反复迭代得到向量序列 x（k），满足x（k+1）=Bx（k）+g，（k=0,1,2.n）其中B为迭代矩阵，迭代公式为 为了方便的表示出迭代矩阵B，常把系数矩阵分解为A=D-L-U,其中D=diag（a11，a22.ann），于是有x（k+1）=D-1（L+U）x（k）+D-1b，即B=D-1(L+U)=D-1(D-A)=I-D-1A,g=D-1b.（2） 高斯赛德尔（Gauss-Seidel）迭代法 的基础上，改写：如下； 取初始量想x（0）后，得迭代公式 4、 结论通过上述分析，发现各解线性方程组的方法都存在不足之处：1.直接法 实际计算中，由于舍入误差的存在和影响，这种方法只能求得线性方程组的近似解。对于高阶方程组，直接法求解的计算量往往过大。（1）克拉默法则求解线性方程组：必须计算 n + 1 个 n 阶行列式并做 n 次除法，而 每个 n 阶行列式的计算又需要作 (n 1) n! 次乘法，计算量十分惊人。例如当 n = 20 时，需要作 5.109 109次乘法，因而此法是不实用的。(k) (k +1)(k +1) ( k+1) (k +1) (k +1)（2）高斯消元法：在消元的过程中，可能出现主元为零的情况，这时消元法无法进行，即使主元不为零但很小，若用其作除数，会导致其它元素的数量级严重增长和舍入误差的扩散，最后也使得计算解不可靠。为使高斯消去法具有较好的数值稳定性，我们试图使用完全主元素消去法，但完全主元素消去法在选主元时要花费较多机器时间，为此又考虑使用列主元消去法。但由于仍须选主元，计算量也较大。 对于良态问题，高斯消去法也可能给出很坏的结果，这说明高斯消去法的算法很不稳定。事实上，一般的矩阵都是病态矩阵，采用高斯消去法一般也不能得到满意的结果。 （3） 矩阵的三角分解法：矩阵 A 可以进行三角分解是有条件的，它要求 A 为方阵且A 的所有顺序主子式均不等于零。2.迭代法 迭代法存在收敛性及收敛速度问题，在判断收敛性时，一般寻找迭代矩阵，这时会涉及到矩阵的求逆和乘法运算，而矩阵的谱半径一般也不易求出。另外，迭代法的计算访存比较低，尤其是系数矩阵为稀疏型时，有效计算的比例