线性方程组的直接方法精选课件.ppt

《线性方程组的直接方法精选课件.ppt》由会员分享，可在线阅读，更多相关《线性方程组的直接方法精选课件.ppt（107页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于线性方程组的直接方法第一页，本课件共有107页解线性方程组的直接法解线性方程组的直接法简记为简记为Ax=b，其中，其中(6.1)常见的线性方程组是方程个数和未知量个数相常见的线性方程组是方程个数和未知量个数相同的同的n阶线性方程组，一般形式为阶线性方程组，一般形式为第二页，本课件共有107页线性方程组的数值解法一般有两类：线性方程组的数值解法一般有两类：1.直接法：就是经过有限步算术运算，可求得直接法：就是经过有限步算术运算，可求得方程组精确解的方法（方程组精确解的方法（若计算过程中没有舍若计算过程中没有舍入误差入误差），如克莱姆法则就是一种直接法，直），如克莱姆法则就是一种直接法，直接法

2、中具有代表性的算法是高斯接法中具有代表性的算法是高斯(Gauss)消去消去法。法。2.迭代法迭代法:就是用某种极限过程去逐步逼近线就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是性方程组的精确解的方法。也就是从解的某从解的某个近似值出发，通过构造一个无穷序列去逼近精个近似值出发，通过构造一个无穷序列去逼近精确解的方法。确解的方法。(一般有限步内得不到精确解一般有限步内得不到精确解)第三页，本课件共有107页三、特殊矩阵三、特殊矩阵1)对角矩阵2)三对角矩阵3)上三角矩阵4)上海森伯(Hessenberg)阵5)对称矩阵6)埃尔米特矩阵7)对称正定矩阵8)正交矩阵9)酉矩阵10)初等

3、置换阵11)置换阵第四页，本课件共有107页定理定理1设ARnn,A非奇异?定理定理2若ARnn对称正定矩阵，则?定理定理3若ARnn对称矩阵，则对称正定矩阵0,i=1,2,n 0,i=1,2,n 因此存在惟一的分解因此存在惟一的分解 A=LU A=LU 第五十八页，本课件共有107页L是单位下三角阵是单位下三角阵,U是上三角阵是上三角阵,将将U再分解再分解 其中其中D为对角阵为对角阵,U0为单位上三角阵，于是为单位上三角阵，于是A=LU=LDU0又又A=AT=U0TDLT由分解惟一性由分解惟一性,即得即得U0T=LA=LDLT第五十九页，本课件共有107页记记又因为又因为det(Ak)0,(

4、k=1,2,n),故故于是对角阵于是对角阵D还可分解还可分解其中其中 为下三角阵为下三角阵,令令L=LL=L1 1，定理得证。，定理得证。第六十页，本课件共有107页将将A=LLT展开，写成展开，写成按矩阵乘法展开，可逐行求出分解矩阵按矩阵乘法展开，可逐行求出分解矩阵L L的元素，计的元素，计算公式是对于算公式是对于i=1,2,ni=1,2,n j=i+1,i+2,n 这一方法称为这一方法称为平方根法平方根法,又称又称乔累斯基乔累斯基(Cholesky)分解分解,它所需要的乘除次数约它所需要的乘除次数约 为数量级为数量级,比比LU分解节省分解节省近一般的工作量。近一般的工作量。第六十一页，本课

5、件共有107页例例6.9 6.9 平方根法求解方程组平方根法求解方程组 解解:因方程组系数矩阵对称正定因方程组系数矩阵对称正定,设设A=,A=,即：即：由由Ly=bLy=b解得解得 由由 解得解得 由此例可以看出，平方根法解正定方程组的缺由此例可以看出，平方根法解正定方程组的缺点是需要进行开方运算。为避免开方运算，我们改点是需要进行开方运算。为避免开方运算，我们改用单位三角阵作为分解阵，即把对称正定矩阵用单位三角阵作为分解阵，即把对称正定矩阵A分分解成解成的形式，其中的形式，其中 第六十二页，本课件共有107页为对角阵，而为对角阵，而 是单位下三角阵是单位下三角阵,这里分解这里分解公式为公式为

6、 第六十三页，本课件共有107页据此可逐行计算据此可逐行计算 运用这种矩阵分解方法运用这种矩阵分解方法,方程组方程组Ax=bAx=b即即可归结为求解两个上三角方程组可归结为求解两个上三角方程组 和和其计算公式分别为其计算公式分别为 和和 求解方程组的上述算法称为改进的平方根法。这种方法求解方程组的上述算法称为改进的平方根法。这种方法总的计算量约为总的计算量约为 ，即仅为高斯消去法计算量的一，即仅为高斯消去法计算量的一半。半。第六十四页，本课件共有107页记笔记记笔记5.7 5.7 向量和矩阵的范数向量和矩阵的范数 为了研究线性方程组近似解的误差估计为了研究线性方程组近似解的误差估计和迭代法的收

7、敛性和迭代法的收敛性,有必要对向量及矩阵的有必要对向量及矩阵的“大小大小”引进某种度量引进某种度量-范数的概念。向量范数的概念。向量范范数是用来度量向量长度的数是用来度量向量长度的,它可以看成是二、它可以看成是二、三维解析几何中向量长度概念的推广。用三维解析几何中向量长度概念的推广。用Rn表示表示n维实向量空间。维实向量空间。第六十五页，本课件共有107页记笔记记笔记5.7 5.7 向量和矩阵的范数向量和矩阵的范数定义定义5.2对任一向量对任一向量X Rn,按照一定规则确定一个实按照一定规则确定一个实数与它对应数与它对应,该实数记为该实数记为|X|,若若|X|满足下面三个满足下面三个性质性质:

8、(1)|X|0；|X|=0当且仅当当且仅当X=0；(2)对任意实数对任意实数，|X|=|X|；(3)对任意向量对任意向量Y Rn，|X+Y|X|+|Y|则称该实数则称该实数|X|为向量为向量X的的范数范数第六十六页，本课件共有107页在在R Rn n中，常用的几种范数有：中，常用的几种范数有：记笔记记笔记其中其中x x1 1 1 1,x,x,x,x2 2,x,xn n n n分别是分别是X X的的的的n n n n个分量。以上定义的个分量。以上定义的范数分别称为范数分别称为范数分别称为范数分别称为1-1-范数，范数，范数，范数，2-2-范数和范数和范数和范数和 -范数范数可以验证它们都是满足范

9、数性质的，其中可以验证它们都是满足范数性质的，其中可以验证它们都是满足范数性质的，其中可以验证它们都是满足范数性质的，其中 是由内积导出的向量范数。是由内积导出的向量范数。5.7 5.7 向量和矩阵的范数向量和矩阵的范数第六十七页，本课件共有107页当不需要指明使用哪一种向量范数时，就用记号当不需要指明使用哪一种向量范数时，就用记号|.|泛指任泛指任何一种向量范数。何一种向量范数。有了向量的范数就可以用它来衡量向量的大小和表示有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。向量的误差。设设x*为为Ax=b的精确解，的精确解，x为其近似解，则其绝对误差可表为其近似解，则其绝对误差可表示

10、成示成|x-x*|，其相对误差可表示成，其相对误差可表示成记笔记记笔记5.7 5.7 向量和矩阵的范数向量和矩阵的范数或或第六十八页，本课件共有107页第六十九页，本课件共有107页例例5.10证明对任意同维向量证明对任意同维向量x,y有有 证：证：即即 第七十页，本课件共有107页例例5.11设设x=(1,0,-1,2)T,计算计算 解解:=1+0+|-1|+2=4第七十一页，本课件共有107页定理定理7.1 7.1 对于任意向量对于任意向量x,有有证证:即即 当当 p，第七十二页，本课件共有107页定义定义5.4(向量序列的极限向量序列的极限)设设为为中的中的一向量序列，一向量序列，,记记

11、。如果。如果(i=1,2,n)，则称则称收敛于向量收敛于向量，记为，记为定理定理7.2（向量范数的等价性）设（向量范数的等价性）设为为上任意两种向量范数上任意两种向量范数,则存在常数则存在常数C1,C20,使得对任意使得对任意恒有恒有（证（证:略）略）第七十三页，本课件共有107页定理定理7 其中其中为向量中的任一种范数。为向量中的任一种范数。证证由于由于 而对于而对于上的任一种上的任一种范数范数,由定理由定理3.7知存在常数知存在常数C1，C2，使，使于是可得于是可得从而定理得证。从而定理得证。第七十四页，本课件共有107页定义定义5.5（矩阵的范数矩阵的范数）如果矩阵）如果矩阵 的某个的某

12、个非负的实值函数非负的实值函数 ，满足，满足则称则称 是是 上的一个矩阵范数上的一个矩阵范数(或模或模)第七十五页，本课件共有107页矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证。(1)设设A0,x0,使使Ax0,根据向量范数的性根据向量范数的性质质 Ax 0,所以所以0 x0,使使 Ax=0,则则=0当当A=0时时,第七十六页，本课件共有107页矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证(2)根据向量范数的性质根据向量范数的性质第七十七页，本课件共有107页矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直

13、接验证(3)第七十八页，本课件共有107页矩阵范数定义的另一种方法是矩阵范数定义的另一种方法是这是由于这是由于同样，矩阵范数和向量范数密切相关，向量范数同样，矩阵范数和向量范数密切相关，向量范数有相应的矩阵范数，即有相应的矩阵范数，即第七十九页，本课件共有107页第八十页，本课件共有107页定义定义5.7（矩阵的谱半径）设（矩阵的谱半径）设的特征的特征值为值为,称称为为A的的谱半径。谱半径。例例 5.12 5.12 计算方阵计算方阵 的三种常用范数的三种常用范数 第八十一页，本课件共有107页例例5.12 5.12 计算方阵计算方阵 的三种范数的三种范数 解解 先计算先计算所以所以 ,从而从而

14、第八十二页，本课件共有107页定理定理5.8.1设设A为为n阶方阵阶方阵,则对任意则对任意矩阵范数矩阵范数都有都有证证:设设为为A的特征值，的特征值，x是是对应于的特征向对应于的特征向量量,则则x=Ax。两端取范数并依据其性质。两端取范数并依据其性质得得由于由于x0，故，故 ，所以，所以第八十三页，本课件共有107页第八十四页，本课件共有107页5.8误差分析误差分析5.8.1方程组的性态方程组的性态在建立方程组时，其系数往往含有误差在建立方程组时，其系数往往含有误差（如观测误差或计算误差），就是说，所要求（如观测误差或计算误差），就是说，所要求解的运算是有扰动的方程组，因此需要研究扰解的运算

15、是有扰动的方程组，因此需要研究扰动对解的影响。动对解的影响。第八十五页，本课件共有107页例例5.13考察方程组考察方程组 和和上上述述两两个个方方程程组组尽尽管管只只是是右右端端项项有有微微小小扰扰动动,但但解大不相同解大不相同,第第1个方程组的解是个方程组的解是第第2个方程组的解是个方程组的解是。这类方程组称。这类方程组称为病态的。为病态的。第八十六页，本课件共有107页定义定义5.8A或或b的微小变化的微小变化(又称扰动或摄动又称扰动或摄动)引引起方程组起方程组Ax=b解的巨大变化，则称方程组为病解的巨大变化，则称方程组为病态方程组，矩阵态方程组，矩阵A称为病态矩阵。否则方程组是称为病态

16、矩阵。否则方程组是良态方程组，矩阵良态方程组，矩阵A也是良态矩阵也是良态矩阵 为了定量地刻画方程组为了定量地刻画方程组“病态病态”的程度，的程度，要对方程组要对方程组Ax=b进行讨论，考察进行讨论，考察A（或（或b）微小）微小误差对解的影响。为此先引入矩阵条件数的概误差对解的影响。为此先引入矩阵条件数的概念。念。定义定义5.9（矩阵条件数）设（矩阵条件数）设A为非奇异矩阵，为非奇异矩阵，称称为矩阵为矩阵A条件数。条件数。第八十七页，本课件共有107页第八十八页，本课件共有107页第八十九页，本课件共有107页我们先来考察常数项我们先来考察常数项b的微小误差对解的影响。的微小误差对解的影响。设设

17、A是精确的是精确的,b有误差有误差(或扰动或扰动)b,显然显然,方程组方程组的解与的解与x有差别有差别,记为记为即有即有即即（由设（由设Ax=b0）于是于是（6.18）又又Ax=b0，则有，则有由（由（6.18）式及（）式及（6.19）式即得如下定理）式即得如下定理（6.19）或或第九十页，本课件共有107页定理定理5.12(b的扰动对解的影响的扰动对解的影响)设设A非奇异，非奇异，Ax=b0，且，且 则有则有证证:设设A A精确且非奇异精确且非奇异,b,b有扰动有扰动b,b,使解使解x有扰动有扰动x,则则 消去消去Ax=bAx=b，有，有又又相比较相比较可得可得 第九十一页，本课件共有107

18、页定理定理 5.13 (A5.13 (A的扰动对解的影响的扰动对解的影响)设设A A非奇异，非奇异，Ax=b0Ax=b0，且，且若若 ,则则证证：略：略第九十二页，本课件共有107页我们还可证明更为一般的结论：我们还可证明更为一般的结论：当方程组的系数矩阵当方程组的系数矩阵A非奇异和常数项非奇异和常数项b为非为非零向量时，且同时有扰动零向量时，且同时有扰动A，b，满足，满足，若，若x和和x+x分别是方程组分别是方程组Ax=b及及的解的解则则第九十三页，本课件共有107页例例6.13 6.13 线性方程组线性方程组 的系数矩阵带误差，成为如下方程组的系数矩阵带误差，成为如下方程组 求方程组系数矩

19、阵的条件数求方程组系数矩阵的条件数,并说明方程组的性态并说明方程组的性态 解解 因为因为 所以所以 因此方程组是良态的因此方程组是良态的 第九十四页，本课件共有107页5.7.2精度分析精度分析求得方程组求得方程组Ax=b的一个近似解以后的一个近似解以后,希望判断其希望判断其精度，检验精度的一个简单办法是将近似解再精度，检验精度的一个简单办法是将近似解再回代到原方程组去求出回代到原方程组去求出余量余量r.r=b-A如果如果r r很小，就认为解是相当精确的。很小，就认为解是相当精确的。定理定理6.14 6.14 设设 是方程组是方程组A Ax=b=b的一个近似解的一个近似解,其其精确解记为精确解

20、记为 ,r,r为为 的余量。则有的余量。则有 证明见证明见P P172172第九十五页，本课件共有107页例例5.14设设A为正交矩阵，证明：为正交矩阵，证明：cond2(A)=1分析：由正交矩阵和条件数的定义便可推得分析：由正交矩阵和条件数的定义便可推得解：因为解：因为A是正交矩阵，是正交矩阵，故故ATA=AAT=I，A-1=AT，从而，从而第九十六页，本课件共有107页例例5.15设设A，B为为n阶矩阵，证明：阶矩阵，证明：cond(AB)cond(A)cond(B)分析分析:由矩阵范数性质和条件数定义由矩阵范数性质和条件数定义便可证明便可证明证：证：cond(AB)=|AB|(AB)-1

21、|A|B|A-1|B-1|=|A|A-1|B|B-1|=cond(A)cond(B)第九十七页，本课件共有107页例例5.16设设A，B为为n阶非奇异矩阵，阶非奇异矩阵，|表示表示矩阵的任一种范数，证明：矩阵的任一种范数，证明：|A-1-B-1|A-1|B-1|A-B|cond(AB)cond(A)cond(B)分析分析:由矩阵范数的基本性质即可推证由矩阵范数的基本性质即可推证证：证：A-1-B-1=A-1(B-A)B-1,从而从而|A-1-B-1|A-1(B-A)B-1|A-1|B-A|B-1|A-1-B-1|A-1|B-A|B-1|第九十八页，本课件共有107页例例9 9 求Hilbert

22、矩阵H3的条件数.第九十九页，本课件共有107页如何发现判断矩阵是病态的?如何解决和处理?预处理方法预处理方法.第一百页，本课件共有107页例例10 10 设则化为则第一百零一页，本课件共有107页二、迭代改善法二、迭代改善法(略去略去)第一百零二页，本课件共有107页本章小结本章小结 本章介绍了解线性方程组的直接法。直接法是一种本章介绍了解线性方程组的直接法。直接法是一种计算量小而精度高的方法。直接法中具有代表性的算法计算量小而精度高的方法。直接法中具有代表性的算法是高斯（是高斯（Gauss）消去法（在第一章提到的克莱姆算法）消去法（在第一章提到的克莱姆算法也是一种直接法，但该算法用于高阶方

23、程组时计算量太也是一种直接法，但该算法用于高阶方程组时计算量太大而不实用），其它算法大都是它的变型，这类方法是大而不实用），其它算法大都是它的变型，这类方法是解具有稠密矩阵或非结构矩阵（零元分布无规律）方程解具有稠密矩阵或非结构矩阵（零元分布无规律）方程组的有效方法。组的有效方法。第一百零三页，本课件共有107页 选选主主元元的的算算法法有有很很好好的的数数值值稳稳定定性性。从从计计算算简简单单出出发发实际中多选用列主元法。实际中多选用列主元法。解解三三对对角角矩矩阵阵方方程程组组（A A的的对对角角元元占占优优）的的追追赶赶法法，解解对对称称正正定定矩矩阵阵方方程程组组的的平平方方根根法法都

24、都是是三三角角分分解解法法，且且都都是是数数值值稳稳定定的的方方法法，这这些些方方法法不不选选主主元元素素，也也具具有有较较高高的的精精度。度。向量、矩阵的范数、矩阵的条件数和病态方程组的向量、矩阵的范数、矩阵的条件数和病态方程组的概念，是数值计算中一些基本概念。线性方程组的病态概念，是数值计算中一些基本概念。线性方程组的病态程度是其本身的固有特性，因此即使用数值稳定的方法程度是其本身的固有特性，因此即使用数值稳定的方法求解，也难以克服严重病态导致的解的失真。在病态不求解，也难以克服严重病态导致的解的失真。在病态不十分严重时，用双精度求解可减轻病态的影响十分严重时，用双精度求解可减轻病态的影响

25、 第一百零四页，本课件共有107页 在在实实际际应应用用中中如如何何选选择择算算法法是是一一个个重重要要问问题题，往往往往从三个方面考虑：从三个方面考虑：解的精度高；解的精度高；计算量小；计算量小；所需计算机内存小。所需计算机内存小。但这些条件相互间是矛盾而不能兼顾的，因此实但这些条件相互间是矛盾而不能兼顾的，因此实际计算时应根据问题的特点和要求及所用计算机的性际计算时应根据问题的特点和要求及所用计算机的性能来选择算法。一般说，系数矩阵为中、小型满矩阵，能来选择算法。一般说，系数矩阵为中、小型满矩阵，用直接法较好；当系数矩阵为大型、稀疏矩阵时，有用直接法较好；当系数矩阵为大型、稀疏矩阵时，有效的解法是迭代法。效的解法是迭代法。第一百零五页，本课件共有107页Thank you very much!Thank you very much!第一百零六页，本课件共有107页感感谢谢大大家家观观看看第一百零七页，本课件共有107页