线性方程组的求解精品文稿.ppt

《线性方程组的求解精品文稿.ppt》由会员分享，可在线阅读，更多相关《线性方程组的求解精品文稿.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性方程组的求解第1页，本讲稿共76页1 引言引言n一般的线性方程组一般的线性方程组本章：本章：即即有唯一有唯一第2页，本讲稿共76页 的求法的求法求求法法直接求法直接求法（解析法）（解析法）间接方法间接方法（数值方法、迭（数值方法、迭代方法）代方法）1.Grammer法则：法则：2.Gauss消元法及其改进消元法及其改进3.三角分解法（三角分解法（L-U方法）方法）适用：当适用：当A为低阶为低阶稠密阵（稠密阵（n150)第3页，本讲稿共76页二、预备知识1.几个概念：几个概念：1单位上单位上(下下)三角阵：主对角元素均为三角阵：主对角元素均为1的上（下）三角阵的上（下）三角阵 相关结论：其逆

2、仍为单位上（下）三角阵相关结论：其逆仍为单位上（下）三角阵 其积仍为单位上（下）三角阵其积仍为单位上（下）三角阵2置换阵（排列阵）：单位阵经过一次两行（两列）的互换形成矩阵为初等置置换阵（排列阵）：单位阵经过一次两行（两列）的互换形成矩阵为初等置换阵。换阵。初等置换阵的乘积即为置换阵初等置换阵的乘积即为置换阵 初等置换阵一定为对称阵初等置换阵一定为对称阵,3三对角阵三对角阵:对方阵对方阵当当称称A为三角阵为三角阵.4可约与不可约矩阵：对可约与不可约矩阵：对n阶矩阵阶矩阵A，若存在置换阵，若存在置换阵P使使其中，其中，为为r阶子块，阶子块，为为n-r阶子块，则称阶子块，则称A为可约矩阵，否则不可

3、约。为可约矩阵，否则不可约。第4页，本讲稿共76页5对角占优矩阵：对对角占优矩阵：对n阶矩阵阶矩阵A，若，若 或或 成立，则称成立，则称A为严格行或列对角占优矩阵。为严格行或列对角占优矩阵。若若 或或 且上述不等式且上述不等式 至少有一个严格成立，称至少有一个严格成立，称A为弱对角行（列）占优矩阵。为弱对角行（列）占优矩阵。相关结论：若相关结论：若A为严格行或列对角占优矩阵（或为严格行或列对角占优矩阵（或A为不可约行为不可约行 或列弱对角占优矩阵），则或列弱对角占优矩阵），则A可逆。可逆。论证：不妨设论证：不妨设A为严格行对角占优矩阵为严格行对角占优矩阵 反证：反证：A不可逆，即不可逆，即AX

4、=0有非零解有非零解 设设 ，对，对AX=0的第的第K个方程个方程 第5页，本讲稿共76页6 矩阵的谱半径：矩阵的谱半径：对对n阶矩阵阶矩阵A,设设 为为A的全部特征值的全部特征值,称称 为为A的谱半径。的谱半径。第6页，本讲稿共76页2.再论范数再论范数 1 2 3 主要讨论主要讨论 1 相关结论：相关结论：中的所有范数均等价中的所有范数均等价,即任意取即任意取 中的两个范数中的两个范数 ，则，则 一定存在两个正数一定存在两个正数C1以及以及C2使使 2 上的范数（乘积用的最多）上的范数（乘积用的最多）定义：定义：中的范数常用中的范数常用第7页，本讲稿共76页例：例：但在但在 中常用的是所谓

5、的中常用的是所谓的“算子范数算子范数”,称称 为为A的算子范数。的算子范数。易知：易知：称为矩阵范数和向量范数相容。称为矩阵范数和向量范数相容。注意：向量范数与矩阵算子范数相容。注意：向量范数与矩阵算子范数相容。常用的算子范数为：常用的算子范数为：行范数：行范数：列范数：列范数：第8页，本讲稿共76页相关结论：相关结论：1)对任意对任意n阶矩阵阶矩阵A，（，（可以是算子范数，也可以是一般可以是算子范数，也可以是一般范数）范数）论证：设论证：设 为为A的特征值，的特征值，为对应的特征向量为对应的特征向量 两边取算子范数：两边取算子范数：第9页，本讲稿共76页若为一般矩阵范数，设若为一般矩阵范数，

6、设 ,对应的特征向量为对应的特征向量为，0A=,令矩阵令矩阵,使使B 0,其中其中 它一定存在。它一定存在。2)对任意对任意n阶矩阵阶矩阵A，总存在一个算子范数总存在一个算子范数3)对对n阶矩阵阶矩阵A，若，若A的算子范数的算子范数A0,C20.使使第10页，本讲稿共76页3.向量列及矩阵列的收敛向量列及矩阵列的收敛定义定义1：给定的向量列：给定的向量列 及向量及向量 若若 结论：结论：论证：提示论证：提示 取取 范数为范数为定义定义2：结论：结论：为任意范数为任意范数 特别特别 当当n=1，A=a，第11页，本讲稿共76页2 Gauss消元法一、基本思想一、基本思想回忆：方程组的初等变换：回

7、忆：方程组的初等变换：1)互换两个方程互换两个方程 2)某个方程的非零倍数某个方程的非零倍数 3)某个方程的非零倍数加到另一个方程上某个方程的非零倍数加到另一个方程上 对应线性方程组对应线性方程组 Ax=b，用矩阵的语言描述：即为增广矩阵（，用矩阵的语言描述：即为增广矩阵（A,b）的初等行变）的初等行变换换 对列初等变换，除列交换之外，其余两种变换虽可作，但得到的新方程组与对列初等变换，除列交换之外，其余两种变换虽可作，但得到的新方程组与原来的方程组不等价原来的方程组不等价 特别注意的是：列交换时须记录！特别注意的是：列交换时须记录！显然：方程组经过初等变换变成等价的方程组。显然：方程组经过初

8、等变换变成等价的方程组。第12页，本讲稿共76页下面讨论下面讨论Gauss消元法：对给定的方程组：消元法：对给定的方程组：Ax=b。经过一系列的方程组的初等。经过一系列的方程组的初等变换，将变换，将 Ax=b 转化为转化为 Ux=g（U为上三角矩阵，称为上三角矩阵，称 Ux=g 为上三角方程组）或为上三角方程组）或 Lx=f（L为下三角矩阵，称为下三角矩阵，称Lx=f 为下三角方程组）为下三角方程组）然后回代即可求解，此即为然后回代即可求解，此即为Gauss消元法的基本思想。消元法的基本思想。解释解释“回代回代”对对 Ux=g，即，即 从倒数第一个方程求解，依次求得：从倒数第一个方程求解，依次

9、求得：类似地类似地 Lx=f：第13页，本讲稿共76页二、计算过程二、计算过程 消元过程消元过程 一般化为上三角方程组一般化为上三角方程组计算过程计算过程 回代过程回代过程以上三角方程组为例，说明如下：以上三角方程组为例，说明如下：对已知对已知 ，即为：，即为：设设doing第14页，本讲稿共76页设：设：doing：继续以上过程，注意设继续以上过程，注意设得到上三角方程得到上三角方程，可以推出，无需假设，可以推出，无需假设然后回代即可求解。然后回代即可求解。第15页，本讲稿共76页注注Notes：称称 为消元的主元素。如何保证为消元的主元素。如何保证 有两种途径：有两种途径：1）若）若A可逆

10、，总可以通过行交换使得（可逆，总可以通过行交换使得（k，k）位置上的元素非零）位置上的元素非零 2）Th.1:为为 A的第的第k阶顺序主子式阶顺序主子式.A可逆只能保证第可逆只能保证第n阶顺序主子式不为阶顺序主子式不为0，不能保证其他阶为，不能保证其他阶为0.消元过程的矩阵分析：消元过程的矩阵分析：第16页，本讲稿共76页以此类推：以此类推：均为单位下三角矩阵均为单位下三角矩阵归纳有归纳有：(单位下三角矩阵的逆为单位下三角矩阵，乘积也为单位下三角矩阵单位下三角矩阵的逆为单位下三角矩阵，乘积也为单位下三角矩阵)由此引进如下更一般的三角分解的概念：由此引进如下更一般的三角分解的概念：定义：对定义：

11、对n阶矩阵阶矩阵A，若存在下三角阵，若存在下三角阵L及上三角阵及上三角阵U，使，使A=LU，则称，则称 LU为为A的三角分解。的三角分解。当当L为单位下三角矩阵时，称为单位下三角矩阵时，称L-U为为Doolittel分解（分解（D分解）分解）当当U为单位上三角矩阵时，称为单位上三角矩阵时，称L-U为为Grout分解（分解（G分解）分解）第17页，本讲稿共76页Th.2：对：对n阶矩阵阶矩阵A，当，当A的顺序主子式的顺序主子式 0（k=1,2，n-1），则），则A一定一定 存存在在D分解且分解且D分解唯一。分解唯一。于是有于是有:Gauss消元顺利进行消元顺利进行另，为使主元另，为使主元 ，只要

12、，只要A可逆，交换可逆，交换AX=b的两两个方程组，可使的两两个方程组，可使 位位置上的元素非零，此时置上的元素非零，此时Gauss消元法可描述为，存在置换阵消元法可描述为，存在置换阵P使使PA=LU。第18页，本讲稿共76页Gauss消元法的改进消元法的改进 Gauss消元法的缺陷：消元法的缺陷：Gauss消元法的改进：切入点：主元素消元法的改进：切入点：主元素 方法：选主元方法：选主元+消元消元+回代回代第19页，本讲稿共76页具体步骤：具体步骤：第20页，本讲稿共76页（b）列主元素消元法）列主元素消元法 常用常用 第21页，本讲稿共76页 消元消元计算量计算量 回代回代消元：消元：步数

13、步数 1 2 n-1 除法除法 n-1 n-2 1 乘法乘法 n(n-1)(n-1)(n-2)21 第22页，本讲稿共76页 3 三角求解求法三角求解求法一、基本思想一、基本思想第23页，本讲稿共76页第24页，本讲稿共76页LU解法计算量与解法计算量与Gauss消元法计算量消元法计算量相同相同第25页，本讲稿共76页二、特殊的二、特殊的LU 解法解法对已知对已知Ax=b，若，若A为某些特殊矩阵，为某些特殊矩阵，LU解法亦有一些特殊变形，讨论以解法亦有一些特殊变形，讨论以下两种情况。下两种情况。第26页，本讲稿共76页第27页，本讲稿共76页第28页，本讲稿共76页 4、误差分析、误差分析第2

14、9页，本讲稿共76页一、解对系数的敏感性n关于Ax=b的求解，以上所述均为精确解，故误差分析只针对舍入误差，而舍入误差实质上是一种绝对误差。对Ax=b，可能产生舍入误差的来源是：A或b的微小变化（A及b会产生舍入误差）。n问题：A或b的扰动对Ax=b的解是否有影响？第30页，本讲稿共76页例题 解得x1=2，x2=0。扰动b 解得x1=1，x2=1。第31页，本讲稿共76页n值得指出：值得指出：A A、b b的扰动是一种客观存在；的扰动是一种客观存在；A A、b b的扰动对的扰动对Ax=bAx=b的解有时会产生破坏作用。的解有时会产生破坏作用。此即为解对系数的敏感性，显然，解对此即为解对系数的

15、敏感性，显然，解对A A、b b的敏感性越大，对解的破坏性的敏感性越大，对解的破坏性越大。反之亦然。越大。反之亦然。定义：对给定的线性方程组定义：对给定的线性方程组Ax=bAx=b，若，若A A、b b的微小扰动对的微小扰动对Ax=bAx=b的解产生的解产生 很大的变化，称为病态方很大的变化，称为病态方 程组，程组，A A为病态矩阵；反之，称为病态矩阵；反之，称Ax=bAx=b为良性方程组，为良性方程组，A A称称为良态矩阵。为良态矩阵。第32页，本讲稿共76页二、病态性分析二、病态性分析给定给定Ax=bAx=b（|A|0|A|0），则），则Ax*=b，x*唯一存在。唯一存在。分三种情形：分三

16、种情形：1.b 1.b扰动，扰动，A A不扰动不扰动 2.A 2.A扰动，扰动，b b不扰动不扰动 3.A 3.A以及以及b b同时扰动同时扰动第33页，本讲稿共76页 1.b 1.b扰动，扰动，A A不扰动不扰动 bb+bb+b b，则此时，则此时 x x*x x*+x x A A（x x*+x x）=b+=b+b b A Ax=x=b b x=Ax=A-1-1b b x x AA-1-1bb 又又b=Axb=Ax*AxAx*1/1/xx*A/b A/b AA-1-1AAb1/b b1/b 易知易知AA-1-1AA越大越大,对解得变化影响越大。反之亦然。对解得变化影响越大。反之亦然。第34页

17、，本讲稿共76页 2.A 2.A扰动，扰动，b b不扰动不扰动 AA+AA+A A，则此时，则此时 x x*xx*+x x （A+A+A A）（）（x x*+x x）=b=b 展开得展开得 （A+A+A A）x=-x=-AxAx*又又 A+A+A=AA=A（E+AE+A-1-1A A）另设另设|A|A-1-1A|A|A|A-1-1|A|A|1 1 有有E+AE+A-1-1A A可逆，可逆，则则(E+A(E+A-1-1A)A)-1-11/(1-A1/(1-A-1-1A)A)1/(1-A 1/(1-A-1-1A)A)第35页，本讲稿共76页进一步有：进一步有：x=-(A+x=-(A+A)A)-1-

18、1AxAx*=-(E+A=-(E+A-1-1A)A)-1-1A A-1-1AxAx*x (E+Ax (E+A-1-1A)A)-1-1 AA-1-1 A xA x*1/(1-A 1/(1-A-1-1A)AA)A-1-1 A xA x*x/xx/x*AA-1-1A/(1-AA/(1-A-1-1A)A)AA-1-1A A A/AA/A /1-A/1-A-1-1AAA/A)A/A)易知易知 AA-1-1AA越大，对系数的扰动起的扩张作用越大，从而解的变化越大。反之亦然。越大，对系数的扰动起的扩张作用越大，从而解的变化越大。反之亦然。第36页，本讲稿共76页 3.A 3.A以及以及b b同时扰动同时扰动

19、bb+bb+b b，AA+AA+A A，x x*xx*+x x 则（则（A+A+A A）（）（x x*+x x）=b+=b+b b 同同2.2.知得：知得：同样可看出同样可看出AA-1-1AA对解的影响一样的。对解的影响一样的。由此引出下面的条件数的概念由此引出下面的条件数的概念第37页，本讲稿共76页条件数定义：对任意的n阶可逆矩阵A，称 Cond(A)=A-1A 为A的条件数。易知，Cond(A)越大，Ax=b病态程度越大。常用的条件数 Cond(A)=A-1 A Cond(A)2=A-12A2第38页，本讲稿共76页条件数性质 1.Cond(A)1 Cond(A)=A-1 A A-1A=

20、1 2.对常数c 0 ，Cond(cA)=Cond(A)3.若R为正交矩阵，则Cond(R)2=1 4.对任意的n阶可逆阵A及正交阵R，有 Cond(A)2=Cond(RA)2=Cond(AR)2 5.对任意的n阶矩阵A、B有 Cond(AB)Cond(A)Cond(B)第39页，本讲稿共76页三、病态性诊断及处理已知对任意的n阶矩阵A,Cond(A)=A-1 A但实际上的计算很困难例：书中P170，希尔伯特矩阵Hn Cond(H3)=748第40页，本讲稿共76页诊断及处理方法诊断1.出现小主元2.系数阵的行列式很小或某些行近似相关3.系数阵元素的大小分布差异性大处理方法1.高精度算法（双倍

21、字节）2.预处理3.迭代处理第41页，本讲稿共76页四、事后估计设给定Ax=b，并设x为精确解x*的近似值，则有 x*-x/x*Cond(A)r/b 其中r为剩余向量 r=Ax*-Ax=b-Ax A(x*-x)=r x*-x=A-1r 第42页，本讲稿共76页5.5 迭代求解法第43页，本讲稿共76页一、基本思想给定Ax=b，|A|0，Ax*=b等价变形 x=Bx+f变形的可行性是显然的！a11x1+a12x2+a1nxn=b1 x1=(1-a11)x1-a12x2-a1nxn+b1第44页，本讲稿共76页任取x*的一个近似值 X(0)=(x1(0),x2(0),xn(0)T 视Bx+f为校正

22、器！迭代 x(1)=Bx(0)+f x(2)=Bx(1)+f x(k+1)=Bx(k)+f生成向量列x(k),若x(k)收敛，则其极限x*。第45页，本讲稿共76页证明：x(k+1)=Bx(k)+f lim x(k+1)=B limx(k)+f,k =B+f 故 x=Bx+f的解 又因为解唯一 =x*第46页，本讲稿共76页 在x(k)收敛时，取充分大的自然数N，视 x(N)x*,这种求解方法叫迭代法。命名：称x=Bx+f为迭代方程组 称B为迭代矩阵 称x(k+1)=Bx(k)+f(校正过程)为迭代格式 称x(k)为迭代列第47页，本讲稿共76页NOTES：1.对给定的Ax=b，其等价迭代方程

23、组不唯一!2.不同的初值x(0)或迭代矩阵B不同，得到不同的迭代列(有无穷多个迭代列)，但若收敛，其极限均 为x*。3.如何使得x(k)收敛？第48页，本讲稿共76页 分析：因x(k)x*=Bx(k-1)+f-(Bx*+f)=B(x(k-1)x*)=B2(x(k-2)x*)=Bk(x(0)x*)故有x(k)收敛 x(k)x*0（向量），k Bk(x(0)x*)0（向量），k Bk 0（矩阵），k (B)1(谱半径小于1)第49页，本讲稿共76页二、几种常用的迭代格式（自始至终）1。Jacobi格式（J-格式,三种形式,分量式,分量浓缩式,矩阵式）格式设计。已知Ax=b（|A|0）即 a11x1

24、+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 an1x1+an2x2+annxn=bn 第50页，本讲稿共76页假设aii 0,标准等价方程组 x1=(-a12x2-a13x3-a1nxn+b1)/a11 x2=(-a21x1-a23x3-a2nxn+b2)/a22 xn=(-an1x1-an2x2-an,n-1xn-1+bn)/ann矩阵形式：X=BJ X+fJ 其中BJ=0 -a12/a11 -a13/a11 -a1n/a11 -a21/a22 0 -a23/a22 -a2n/a22 -a31/a33 -a32/a33 0 -a3n/a33 -an1/ann -

25、an2/ann -an3/ann 0第51页，本讲稿共76页fJ=(b1/a11,b2/a22,bn/ann)TJ格式：X(k+1)=BJ x(k)+fJ x1(k+1)=(-a12x2(k)-a13x3(K)-a1nxn(k)+b1)/a11 x2(k+1)=(-a21x1(k)-a23x3(K)-a2nxn(k)+b2)/a22 xn(k+1)=(-an1x1(k)-an2x2(K)-an,n-1xn-1(k)+bn)/ann类似可写浓缩式：第52页，本讲稿共76页J格式的矩阵分析：格式的矩阵分析：对对Ax=b第53页，本讲稿共76页2。Seidel格式（格式（S-格式）格式）定位：是对定

26、位：是对J格式的改进（保留格式的改进（保留Jacobi假设）假设）目的：节约空间目的：节约空间 方法：在迭代计算中尽可能地利用最新的数据方法：在迭代计算中尽可能地利用最新的数据第54页，本讲稿共76页具体格式设计具体格式设计：第55页，本讲稿共76页 S-格式的矩阵分析：格式的矩阵分析：起点：起点：此为计算模式下的此为计算模式下的S-格式：格式：标准模式为：标准模式为：第56页，本讲稿共76页改进目的分析改进目的分析 是否比是否比J-格式省了内存空间？格式省了内存空间？在迭代计算时：对初值：在迭代计算时：对初值：第57页，本讲稿共76页3。SOR格式（超松弛格式）格式（超松弛格式）定位：是对定

27、位：是对S-格式的改进格式的改进 目的：提速目的：提速 方法：外推（线性拟合）方法：外推（线性拟合）过程：过程：第58页，本讲稿共76页 SOR格式的矩阵分析：格式的矩阵分析：（标准形式）（标准形式）第59页，本讲稿共76页三、迭代法收敛性判定三、迭代法收敛性判定第60页，本讲稿共76页下面给出判定条件：第61页，本讲稿共76页论证：论证：第62页，本讲稿共76页对对S-格式格式：第63页，本讲稿共76页4.充要条件.设系数矩阵A为对称矩阵，且第64页，本讲稿共76页第65页，本讲稿共76页第66页，本讲稿共76页第67页，本讲稿共76页5.充分条件：第68页，本讲稿共76页第69页，本讲稿共76页NOTES:第70页，本讲稿共76页改变方程组中方程次序不会改变方程组的解，但有时会改变格式改变方程组中方程次序不会改变方程组的解，但有时会改变格式 的收敛性。的收敛性。第71页，本讲稿共76页SOR格式收敛的必要条件格式收敛的必要条件:02第72页，本讲稿共76页四、误差估计四、误差估计第73页，本讲稿共76页五、迭代法的收敛速度：五、迭代法的收敛速度：第74页，本讲稿共76页第75页，本讲稿共76页第76页，本讲稿共76页