3线性方程组解法

1、第3章 线性方程组的解法本章讨论线性方程组的求解问题.线性方程组的矩阵表示式中A称为系数矩阵，b称为右端项。数值分析中，线性方程组的数值解法主要分为直接法和迭代法两大类。直接法是用有限次计算就能求出线性方程组“准确解”的方法（不考虑舍入误差）；迭代法是由线性方程组构造出迭代计算公式，然后以一个猜测的向量作为迭代计算的初始向量逐步迭代计算，来获得满足精度要求的近似解。迭代法是一种逐次逼近的方法。1 线性方程组的迭代解法线性方程组迭代解法有Jocobi迭代法、Gauss-Seidel迭代法及SOR法等基本思想（与简单迭代法类比）将线性方程组等价变形为以构造向量迭代格式用算出的迭代向量序列去逼近解。

2、1. 构造原理（1） Jacobi迭代法将线性方程组的第i个变元用其他n-1个变元表出，可得 Jacobi迭代格式: （3）取定初始向量，代入，可逐次算出向量序列，这里。（2）Gauss-Seidel迭代法Seidel迭代格式:例1对线性方程组写出Jacobi迭代格式和Gauss-Seidel迭代格式.3）SOR法SOR法的迭代格式式中参数w称为松弛因子，当w =1时，SOR法就是Seidel迭代法.2.迭代分析及向量收敛 1） 三种迭代法的向量迭代格式对 Ax=b，将系数矩阵A作如下分解则Ax=b可以写成Jacobi迭代的向量迭代格式，. 为Jacobi迭代法的迭代矩阵.Seidel向量迭代

3、格式，.为Seidel迭代法的迭代矩阵.SOR法的向量迭代格式，.为超松弛迭代法的迭代矩阵。三种迭代格式可写成迭代格式2）向量收敛定义定义1 设向量序列及向量都是中的向量，如果有 成立,则称收敛于.简记为。3）范数定义与科学计算中的常用范数定义2 设L是数域K上的一个线性空间，如果定义在L上的实值函数满足1) ，有, 且；2) ，有；3) ，有,则称是L上的一个范数，称为x的一个范数。范数的定义很象绝对值函数，故常用或表示范数，而范数常记为或。这样，上面范数定义中的3个条件常写为1），有, 且；2），有；3），有将其与绝对值比较，是否很象？实际上，很多有关绝对值的运算和结论可以平行引进到有关范

4、数的运算和证明问题中。数值分析中常用的线性空间有l n维向量空间l 矩阵空间连续函数空间函数空间是由闭区间上所有连续函数组成的集合，其线性运算定义为加法数乘 ，为数在这些空间上，数值分析中常用的范数有(1)的向量范数1) 2) 3) 式中向量.例2 计算向量的各种范数.(2) 的矩阵范数矩阵范数要满足如下四条1），有,且；2），有；3），有；4），有.由于线性方程组求解问题中，系数矩阵总是与向量联系在一起的，为描述这种联系，引入如下的算子范数概念.定义3 设矩阵，称为矩阵A的算子范数。容易证明，矩阵A的算子范数也是矩阵范数，且满足不等式关系.例3设为矩阵的算子范数，证明若，则为非奇异矩阵，且证

5、：用反证法。若为奇异矩阵，则其对应的方程组有非零解，即有，使，得出两边取范数并作范数运算，矛盾，得非奇异。常用的矩阵范数有如下4种1）列范数：2）行范数：3）F范数：4）2范数：，是最大特征值。以上4个矩阵范数中，是算子范数，不是算子范数。例4 计算矩阵的各种范数.3）范数等价与向量极限定义4 设是线性空间L上的两个范数，若存在正常数m和M，成立则称范数是等价范数。定理1 上的所有范数都是等价的。定理2 。式中是上任何一种范数。4）谱半径及其与范数的关系定义5 设，是A的n个特征值，称为矩阵A的谱半径。注意如果是复数，表示复数模。定理3 设表示的某种算子范数，则有 引理4 设，则 3. 迭代法

6、的收敛条件与误差估计1）收敛条件定理5：对任意初始向量，由迭代格式产生的向量序列都收敛的充要条件是.证明 必要性设，在中令，得,于是有由及的任意性，有.再由引理，可得.充分性因为，则有I-B非奇异（这里I为单位矩阵），从而线性方程组有唯一解，即有展开有.类似必要性处理，有由引理，由有，上式取极限，得.l 判别条件若，则迭代法收敛.是矩阵B的某种算子范数.定义6设，1）如果A的主对角元素满足 则称矩阵A是严格行对角占优阵；2）如果A的主对角元素满足 则称矩阵A是严格列对角占优.严格行对角占优阵和严格列对角占优阵统称为严格对角占优阵.定理 严格对角占优阵是非奇异矩阵。证明 不妨设矩阵是严格行对角占

7、优阵. 用反证法证明.若A是奇异的，则由矩阵理论可知，齐次线性方程组有非零解，即存在，满足.记，有将的第m个等式写为等式两边取绝对值有因为，上式同除，有此与A是严格行对角占优阵矛盾. 故若A是非奇异的.l 判别条件设矩阵A是严格对角占优阵，则解线性方程组的Jacobi迭代法和Seidel迭代法均收敛.证明 只对A是行对角占优情况证之. 设矩阵A是严格行对角占优阵，则有， Jacobi迭代矩阵，故有由判别条件，可得Jacobi迭代的收敛性.对Seidel迭代，其迭代矩阵，设是矩阵的任一特征值，则有特征方程因，故矩阵的特征方程变为这个行列式方程对应的矩阵如果，利用矩阵A的行对角占优定义，可以得出如

8、下不等式这说明矩阵也是行严格对角占优阵，由定理，有, 矛盾，故应有成立. 由的任意性有谱半径，于是可得Seidel迭代的收敛性.定理7 SOR法收敛的必要条件是松弛因子w满足0<w<2.证明 因为SOR法的迭代矩阵为有 设是的n个特征值，则有，若SOR收敛，必有，注意到，得. 解之得.l 判别条件III设，如果（1）对称正定，（2），则解的SOR迭代法收敛.设A是对称正定矩阵，则解的Seidel迭代法收敛.l 判别条件IV设，如果（1）为严格对角占优阵，（2），则解的SOR迭代法收敛.2）误差估计定理8 设矩阵B的某种算子范数，则由式算出的序列与线性方程组的准确解有如下的误差估计1

9、） 2） 证明可以参照非线性方程求根定理的证明，注意将那里的绝对值换成这里的范数，那里的函数换成这里的矩阵，并注意范数关系的使用即可。练习1 设方程组为写出Jacobi迭代格式和Gauss-Seidel迭代格式，判别这两种迭代法的收敛性.练习2 设方程组为判别Jacobi迭代法和Gauss-Seidel迭代法的收敛性.练习3 设方程组为判别Jacobi迭代法和Gauss-Seidel迭代法的收敛性.练习4 方程组，其中确定使Jacobi迭代法和Gauss-Seidel迭代法均收敛的的取值范围.练习5 证明矩阵正定的充要条件是而Jacobi迭代只对是收敛的.3.4 线性方程组的直接解法 解线性方

10、程组的直接法有Gauss消元法，LU分解法及一些特殊线性方程组的解法等，其中Gauss消元法是直接法的基础.本章的重点是在一般公式推导上，要注意学习和体会.1. Gauss消元法基本思想先将线性方程组通过消元方法化为同解的上三角方程组，然后从该三角方程组中按第n个方程、第n-1个方程、第1个方程的顺序，逐步回代求出线性方程组的解.1) 构造原理Gauss消元法的求解过程分为两个:“消元”：把原方程组化为上三角方程组；“回代”：求上三角方程组的解.为推导公式的方便，记要求解的原方程组为Gauss消元法的算法构造如下一、消元过程1）设,令乘数 , 做(消去第i个方程组的x1)操作第1个方程+第i个

11、方程（i =2,3,n）则第i个方程变为这样消去第2，3，n个方程的变元x1后，原线性方程组变为 式中的计算公式为这样就完成了第1步消元.2) 对所得线性方程组中由第2，3，n个方程组成的n-1元线性方程组做同样的处理，可得到第2步消元后的线性方程组式中的计算公式为3)第k步消元过程的计算公式当做到第n-1步消元后，就完成了Guass消元过程，得到上三角方程组 二、回代过程1）在上三角方程组的最后一个方程中解出，得2）将的值代入倒数第2个方程，再解出，得3）依次回代，得计算的公式为当时，就完成了回代过程，从而完成了Gauss消元法的全过程，得到所求解.要注意的是，计算公式中分母不能为零，于是可

12、以得到如下Gauss消元法计算公式。三、Gauss消元法计算公式1. 对，计算2.对，计算2）分析（1）Gauss消元法的计算量Gauss消元法由消元过程和回代过程两部分组成，消元过程的计算量来自计算，所用的乘法和计算所用的除法。容易得出Gauss消元法的消元过程计算量为因此消元过程计算量为类似地可算出Gauss消元法的回代过程的计算量，于是得Gauss消元法的计算量为当n很大时，. 由于科学计算中，变元个数n都很大，因此也常说Gauss消元法的计算量为.（2）Gauss消元法的矩阵解释借助矩阵的理论，能更清楚地看到Gauss消元法的本质，也可得出易于推广的内容。Gauss消元法过程实际是对的

13、增广矩阵（A，b）做第三种行初等变换，它对应着用第三种初等矩阵左乘要变换的增广矩阵.Gauss消元过程的第一步消元的矩阵描述为式中与是消元后的线性方程组的系数矩阵和常数项。记利用矩阵运算与相等定义，有和类似地，经过第n-1步消元后，可以得出式中是变换后的上三角方程组的系数矩阵，若记，有和，可以证明是单位下三角矩阵，且注意到是上三角矩阵. 若令，则有（矩阵的一种分解形式）这种矩阵分解为寻找新的线性方程组解法创造了条件.（3）Gauss消元法可使用的条件Gauss消元法要求，什么样的线性方程组满足这个要求显得很重要，下面不加证明地给出两个结果.定理 9 的充要条件是矩阵A的所有顺序主子式不为零.定

14、理10 若线性方程组的系数矩阵A的顺序主子式都不为零，则可用Gauss消元法求解此方程组.（4）Gauss消元法的改进缺点1：必须在都成立时才能使用，这不能令人满意；缺点2：在使用Gauss消元法进行计算机求解时，人们发现有时求出的解是错误的.例5 设线性方程组试用Gauss消元法求解之.例6 研究下面线性方程组的Gauss消元法求解结果，假设计算在4位浮点十进制数的计算机上求解.通常称消元法中用作分母的数为主元. 列主元消元法全主元消元法2. LU分解法基本思想将方程组的系数矩阵A分解为下三角矩阵L与上三角矩阵U的乘积，即，使求解的问题变为求解两个系数矩阵为三角矩阵的和的问题. 1) 构造原

15、理Gauss消元法的矩阵解释说明矩阵A可以分解为下三角矩阵与上三角矩阵相乘的形式. 知道矩阵有这种三角分解的结构后，我们可以利用矩阵运算及相等的概念直接由A求出其分解矩阵L和U.具体做法为先设出L 和U的形式，再由求出L和U的元素.矩阵的三角分解有如下几种常用形式(1) Doolittle分解分解后，L和U的结构为，(2) Grout分解分解后，L和U的结构为(3) LDU分解分解后，L、D和U的结构为Doolittle分解算法构造过程由及矩阵乘积和相等概念，有得计算公式当 时，有从而得到矩阵U的计算公式同理有当时，可得到矩阵L的计算公式若规定式中求和项在时表示不求和，则计算Doolittle分解的L和U元素的公式用后两个表示：用算出的，回代求出的解；用算出的及，回代求出的解.用上述过程求解的方法称为Doolittle分解方法.2) 分析(1)A可以进行Doolittle分解的条件定理11 若非奇异矩阵A有Doolittle分解，分解具有唯一性.定理12 设，且A的各阶顺序主子式，则A有唯一的Doolittle分解.能进行Gauss消元法就能做Doolittle分解.（2）Doolittle分解的紧凑格式按下图方式存贮和计算的格式称为Doolittle分解的紧凑格式.例7 用LU分解