第五章线性方程组的直接方法

1、5.1 引言引言 在工程技术、自然科学和社会科学中，经常遇在工程技术、自然科学和社会科学中，经常遇到的许多问题最终都可归结为解线性方程组，如电到的许多问题最终都可归结为解线性方程组，如电学中网络问题、用学中网络问题、用最小二乘法求实验数据的曲线拟最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的合问题，工程中的三次样条函数的插值问题，经济插值问题，经济运行中的运行中的投入产出问题投入产出问题以及大地测量、以及大地测量、机械与建筑机械与建筑结构的设计计算结构的设计计算问题等等，都归结为求解线性方程问题等等，都归结为求解线性方程组或非线性方程组的数学问题。因此线性方程组的组或非线性方程组的

2、数学问题。因此线性方程组的求解对于实际问题是极其重要的。求解对于实际问题是极其重要的。 第五章第五章 方程组的数值解法方程组的数值解法 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 nnnnnnnnbbbBxxxXaaaaaaaaaA.,.,.2121212222111211解线性方程组的直接法解线性方程组的直接法简记为简记为 Ax=b，其中，其中 ( 6.1 ) 常见的线性方程组是方程个数和未知量个常见的线性方程组是方程个数和未知量个数相同的数相同的n阶线性方程组，一般形式为阶线性方程组，一般形式为 线性方程组的数值解法一般有两类：

3、线性方程组的数值解法一般有两类： 直接法：就是经过有限步算术运算，可求得直接法：就是经过有限步算术运算，可求得方程组精确解的方法（方程组精确解的方法（若计算过程中没有舍若计算过程中没有舍入误差入误差），如克莱姆法则就是一种直接法，），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯直接法中具有代表性的算法是高斯(Gauss)消去法。消去法。1. 迭代法迭代法: 就是用某种极限过程去逐步逼近线就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是性方程组的精确解的方法。也就是从解的某从解的某个近似值出发，通过构造一个无穷序列去逼个近似值出发，通过构造一个无穷序列去逼近精确解的方法

4、。近精确解的方法。( (一般有限步内得不到精一般有限步内得不到精确解确解) )三、特殊矩阵三、特殊矩阵对角矩阵三对角矩阵上三角矩阵上海森伯格(Hessenberg)阵对称矩阵埃尔米特矩阵对称正定矩阵正交矩阵酉矩阵初等置换阵置换阵定理定理1 设ARnn, A非奇异?定理定理2 若ARnn对称正定矩阵，则?定理定理3 若ARnn对称矩阵，则对称正定矩阵0, i=1,2,n 因此存在惟一的分解因此存在惟一的分解 A=LU L是单位下三角阵是单位下三角阵, U是上三角阵是上三角阵, 将将U再分解再分解 01,1,111111122211111DUuuuuuuuuunnnnnnn其中其中D为对角阵为对角

5、阵, U0为单位上三角阵，于是为单位上三角阵，于是 A = L U = L D U0 又又 A = AT = U0TD LT由分解惟一性由分解惟一性, 即得即得 U0T=L A=L D LT nnuuuD2211记记 又因为又因为det(Ak)0,(k=1,2,n), 故故于是对角阵于是对角阵D还可分解还可分解 ), 2 , 1( , 0niuii2121221122112211DDuuuuuuuuuDnnnnnnTTTTLLLDLDLDLDLDLA1121212121)(其中其中 为下三角阵为下三角阵, ,令令L=LL=L1 1，定理得证。，定理得证。 211LDL 将将A=LLT展开，写成

6、展开，写成 nnnnnnnnnnnnnllllllllllllaaaaaaaaa22212111212221112122221111111按矩阵乘法展开，可逐行求出分解矩阵按矩阵乘法展开，可逐行求出分解矩阵L L的元素，计的元素，计算公式是对于算公式是对于i=1,2,ni=1,2,n 21112)(ikikiiiilaliiikikjkjijilllal11j=i+1, i+2,n 这一方法称为这一方法称为平方根法平方根法,又称又称乔累斯基乔累斯基(Cholesky)分分解解,它所需要的乘除次数约它所需要的乘除次数约 为数量级为数量级, ,比比LU分解分解节省近一般的工作量。节省近一般的工作量

7、。 361n例例6.9 6.9 平方根法求解方程组平方根法求解方程组 7851102021211321xxx解解: : 因方程组系数矩阵对称正定因方程组系数矩阵对称正定, ,设设A= ,A= ,即：即： TLL3332223121113332312221111102021211llllllllllll212, 111, 11131311121211111lallalal1122212222lal212102221313232lllal344112322313333llal322111L由由Ly=bLy=b解得解得 3, 3, 5321yyy由由 解得解得 yxLT1, 5, 2321xxx 由

8、此例可以看出，平方根法解正定方程组的缺由此例可以看出，平方根法解正定方程组的缺点是需要进行开方运算。为避免开方运算，我们改点是需要进行开方运算。为避免开方运算，我们改用单位三角阵作为分解阵，即把对称正定矩阵用单位三角阵作为分解阵，即把对称正定矩阵A分分解成解成 TLDLA 的形式，其中的形式，其中 ndddD21为对角阵，而为对角阵，而 1111321323121nnnllllllL是单位下三角阵是单位下三角阵, ,这里分这里分解公式为解公式为 11211, 2 , 11, 2 , 1/)(ikikkiiijkjjkikkijijnildadijdlldal据此可逐行计算据此可逐行计算 运用这

9、种矩阵分解方法运用这种矩阵分解方法, ,方程组方程组Ax=bAx=b即即可归结为求解两个上三角方程组可归结为求解两个上三角方程组 332312211dlldldbxDLLT)(bLy bDxLT1和和其计算公式分别为其计算公式分别为 11,2, 1ikkikiiniylby和和 nikkkiiiinnixldyx11 , 1,/求解方程组的上述算法称为改进的平方根法。这种求解方程组的上述算法称为改进的平方根法。这种方法总的计算量约为方法总的计算量约为 ，即仅为高斯消去法计，即仅为高斯消去法计算量的一半。算量的一半。 6/3n记笔记记笔记 为了研究线性方程组近似解的误差估计为了研究线性方程组近似

10、解的误差估计和迭代法的收敛性和迭代法的收敛性, 有必要对向量及矩阵的有必要对向量及矩阵的“大小大小”引进某种度量引进某种度量-范数的概念。向量范数的概念。向量范范数是用来度量向量长度的数是用来度量向量长度的,它可以看成是二、它可以看成是二、三维解析几何中向量长度概念的推广。用三维解析几何中向量长度概念的推广。用Rn表示表示n维实向量空间。维实向量空间。定义定义5.2 对任一向量对任一向量X Rn, 按照一定规则确定一个实按照一定规则确定一个实数与它对应数与它对应, 该实数记为该实数记为|X|, 若若|X|满足下面三个满足下面三个性质性质:(1) |X| 0；|X|=0当且仅当当且仅当X=0；(

11、2) 对任意实数对任意实数 ， | X|=| | |X|； 对任意向量对任意向量Y Rn，|X+Y| |X|+|Y| 则称该实数则称该实数|X|为向量为向量X的的范数范数记笔记记笔记11211222222121121|X|.|.()|max|,|,.,|max|nniinniiniinxxxxXxxxxXxxxx 2x 当不需要指明使用哪一种向量范数时，就用记号当不需要指明使用哪一种向量范数时，就用记号|.|泛指任何一种向量范数。泛指任何一种向量范数。 有了向量的范数就可以用它来衡量向量的大小和表示有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。向量的误差。 设设x*为为Ax=b的精

12、确解，的精确解，x为其近似解，则其绝对误差为其近似解，则其绝对误差可表示成可表示成|x- x* |，其相对误差可表示成，其相对误差可表示成的特例范数上述范数都是pnipipxXp11)|(|记笔记记笔记*xxx *xxx 或或yxyxyyxyyxxyxyxxxxxxx)()3()2(101:证时，当）（具有以下性质向量范数例例5.10 证明对任意同维向量证明对任意同维向量x , y 有有 yxyx证：证： xyxy()yyxxxyx yxxy即即 xyxy xyxy 例例5.11 设设x=(1, 0, -1, 2)T, 计算计算 21,xxx解解:110|1|24x 2222210( 1)26

13、x max(1,0,1 ,2)2x 定理定理7.1 7.1 对于任意向量对于任意向量x , ,有有证证: : limppxx 1maxii nxx 111111maxmaxnppppppiiii ni nixxxnx 即即 1ppxxnx 当当 p， 11pn limppxx 定义定义5.4 ( 向量序列的极限向量序列的极限 ) 设设 为为 中的中的一向量序列，一向量序列， , 记记 。如果。如果 (i =1,2, n)，则称则称 收敛于向量收敛于向量 ，记为，记为 ( )kxnR*nxR ()()()()12,Tkkkknxxxx *12,Tnxxxx ( )*limkiikxx ( )kx

14、*x()*limkkxx 定理定理7 .2（向量范数的等价性）设（向量范数的等价性）设 为为 上任意两种向量范数上任意两种向量范数, 则存在常数则存在常数C1, C20,使得对任意使得对任意 恒有恒有,pqxxnRnxR 12pqpCxxCx（证（证: :略）略） 定理定理7 其中其中 为向量中的任一种范数。为向量中的任一种范数。 ( )*limkkxx ()*lim0kkxx 证证 由于由于 ( )*limkkxx ()*lim0kkxx 而对于而对于 上的任一种上的任一种 范数范数, 由定理由定理3.7知存在常数知存在常数C1，C2，使，使 nR( )*( )*( )*12kkkCxxxx

15、Cxx 于是可得于是可得 ( )*( )*lim0lim0kkkkxxxx 从而定理得证。从而定理得证。 定义定义5.5（矩阵的范数矩阵的范数）如果矩阵）如果矩阵 的某个的某个非负的实值函数非负的实值函数 ，满足，满足 BAABRBABABAAAAAAnn4320001，对任意矩阵三角不等式（齐次性）对任意实数（正定性）时，且仅当n nAR ( )N AA 则称则称 是是 上的一个矩阵范数上的一个矩阵范数( (或模或模) ) ()N An nR (5.5) ., |,| nnnRxRAxAAx性，即满足和向量范数的相容我们希望一种矩阵范数.)|(5.6) .| | max| ,| ., 0称为

16、矩阵的算子范数是矩阵的一种范数下面验证相应地定义向量范数对于给定一种设矩阵的算子范数vvvxvvnnnAxAxAxRARx) )定义5(定义5(5.7) ., |,| ,| ,|nnnnnvnvRxRAxAAxRARx且满足相容条件一种矩阵范数上是则上一种向量范数是设 定定理理1 17 7矩阵范数定义的另一种方法是矩阵范数定义的另一种方法是这是由于这是由于同样，矩阵范数和向量范数密切相关，对向量同样，矩阵范数和向量范数密切相关，对向量p-范数有相应的矩阵范数，即范数有相应的矩阵范数，即1maxxAAx 001maxmax,1maxxxxAxxxAAxxxAAx 而而 1max(1 2pppxA

17、Axp 如如，）所以有所以有11111max2max8)max(max()(2()0ijnnijinjnijjniTTTTnAaAaAAaAAA AAA AA AfEA A 矩 阵 范 数 计 算 公 式定 理对 阶 方 阵（称 为 的 行 范 数 ）称 为 的 列 范 数 ）称 为 的范 数 ）其 中表 示的 最 大 特 征 值即定义定义5.7（矩阵的谱半径）设（矩阵的谱半径）设 的特征的特征 值为值为 , 称称 为为A的的谱半径。谱半径。例例 5.12 5.12 计算方阵计算方阵 n nAR (1,2, )iin 1( )maxii nA 100024024A 的三种常用范数的三种常用范数

18、 (1,2,)pAp 例例5.12 5.12 计算方阵计算方阵 100024024A 的三种范数的三种范数 解解 31131maxmax 1,4,88ijjiAa 3131maxmax 1,6,66ijijAa )(max2AAA先计算先计算 1001001000220240800440240032A A 所以所以 , ,从而从而 max()32A A 2324 2A 定理定理5.8.1 设设A为为n阶方阵阶方阵, 则对任意则对任意矩阵范数矩阵范数都有都有证证: 设设 为为A的特征值，的特征值，x是是 对应于的特征向对应于的特征向 量量,则则 x=Ax。两端取范数并依据其性质。两端取范数并依据

19、其性质 得得( )AA xxAxA x 由于由于x0，故，故 ，所以，所以A ()AA .|)( ,2AARAnn则为对称矩阵若 定定理理2 20 0.|11| , , 1|1BBIBIBB且为非奇异阵则满足若方阵 定定理理2 21 15.8 误差分析误差分析5.8.1 方程组的性态方程组的性态 在建立方程组时，其系数往往含有误差在建立方程组时，其系数往往含有误差（如观测误差或计算误差），就是说，所要（如观测误差或计算误差），就是说，所要求解的是有扰动的方程组，因此需要研究扰求解的是有扰动的方程组，因此需要研究扰动对解的影响。动对解的影响。 例例5.13 考察方程组考察方程组 121221.0

20、0012.0001xxxx 121221.00012xxxx 和和 上述两个方程组尽管只是右端项有微小上述两个方程组尽管只是右端项有微小扰动扰动, 但解大不相同但解大不相同, 第第1个方程组的解是个方程组的解是 第第2个方程组的解是个方程组的解是 。这类方程组称为病态的。这类方程组称为病态的。121xx 122,0 xx 定义定义5.8 A或或b的微小变化的微小变化(又称扰动或摄动又称扰动或摄动)引起方程组引起方程组Ax=b解的巨大变化，则称方程组解的巨大变化，则称方程组为病态方程组，矩阵为病态方程组，矩阵A称为病态矩阵。否则方称为病态矩阵。否则方程组是良态方程组，矩阵程组是良态方程组，矩阵A

21、也是良态矩阵也是良态矩阵 为了定量地刻画方程组为了定量地刻画方程组“病态病态”的程度，的程度，要对方程组要对方程组Ax=b进行讨论，考察进行讨论，考察A（或（或b）微）微小误差对解的影响。为此先引入矩阵条件数的小误差对解的影响。为此先引入矩阵条件数的概念。概念。 定义定义5.9 （矩阵条件数）设（矩阵条件数）设A为非奇异矩阵，为非奇异矩阵，称称 为矩阵为矩阵A条件数。条件数。 1cond()AAA cond( ) cond( ) cond( )111111max222min|()|()TTAAAAAAA AAAAA A .,|)cond( n112特征值的绝对值最大和最小的为其中为对称矩阵时当

22、AAAn常用的条件数有常用的条件数有: 条件数的性质：; 1)cond( . 1vAA，都有对任何非奇异矩阵;)cond()cond(0 . 2vvAcAcA ，则非奇异且常数设矩阵;)cond()cond()cond( ; 1)(cond . 32222AARRARAAA为正交矩阵，则为非奇异矩阵，如果为正交矩阵，则如果 我们先来考察常数项我们先来考察常数项b的微小误差对解的影的微小误差对解的影响。设响。设A是精确的是精确的, b有误差有误差 (或扰动或扰动)b, 显然显然,方方程组程组 的解与的解与x有差别有差别, 记为记为 即有即有即即 （由设（由设Ax=b0）于是于是 （6.18）又又

23、 Ax=b0，则有，则有 Axbbxxx ()A xxbb ()Axb 1xAb bAx 1Axb 由（由（6.18）式及（）式及（6.19）式即得如下定理）式即得如下定理 （6.19）或或定理定理 5.12 (b的扰动对解的影响的扰动对解的影响) 设设A非奇异，非奇异， Ax=b0，且，且 则有则有 ()A xxbb 1xbAAxb 证证:设设A精确且非奇异精确且非奇异,b有扰动有扰动b,使解使解x有扰动有扰动x, 则则 ()A xxbb 消去消去Ax=b，有，有1xAb bAx 又又1xbAAxb 相比较可得相比较可得 定理定理 5.13 (5.13 (A的扰动对解的影响的扰动对解的影响)

24、 ) 设设A非奇异，非奇异，Ax=b0，且，且若若 ，则则 ()()AAxxb 11AA 111AAAxAAxAAA 证证 ：略：略我们还可证明更为一般的结论：我们还可证明更为一般的结论： 当方程组的系数矩阵当方程组的系数矩阵A非奇异和常数项非奇异和常数项b为为非零向量时，且同时有扰动非零向量时，且同时有扰动A，b，满，满足足 ，若，若x和和x+x分别是方程组分别是方程组Ax=b 及及 的解的解则则11AA ()()AAxxbb 111AAxAbAxAbAAA 例例6.13 6.13 线性方程组线性方程组 12110112xx 的系数矩阵带误差，成为如下方程组的系数矩阵带误差，成为如下方程组

25、1211011 00052.xx 求方程组系数矩阵的条件数求方程组系数矩阵的条件数, , 并说明方程组的性态并说明方程组的性态 解解 因为因为 1111A 111121 1A 12 12cond( )AAA 所以所以 因此方程组是良态的因此方程组是良态的 000 0.0005A 5.7.2 精度分析精度分析求得方程组求得方程组Ax=b的一个近似解以后的一个近似解以后, ,希望判断希望判断其精度，检验精度的一个简单办法是将近似其精度，检验精度的一个简单办法是将近似解再回代到原方程组去求出解再回代到原方程组去求出余量余量r. r = b-A x 如果如果r很小，就认为解是相当精确的。很小，就认为解

26、是相当精确的。定理定理6.14(6.14(事后误差估计事后误差估计) ) 设设 是方程组是方程组Ax=b的一个近似解的一个近似解, ,其精确解记为其精确解记为 , ,r为为 的余的余量。则有量。则有 *xx x *cond( )xxrAbx 证明见证明见P172例例5.14 设设A为正交矩阵，证明：为正交矩阵，证明：cond2(A)=1分析：由正交矩阵和条件数的定义便可推得分析：由正交矩阵和条件数的定义便可推得解：因为解：因为A是正交矩阵，是正交矩阵， 故故ATA= AAT=I， A-1= AT，从而，从而21221222111max()()( )()( )condAA AA AIAAA AI

27、AA 故故例例5.15 设设A，B为为n阶矩阵，证明：阶矩阵，证明： cond(AB) cond(A) cond(B)分析分析: 由矩阵范数性质和条件数定义由矩阵范数性质和条件数定义 便可证明便可证明证：证： cond (AB) = | AB | | (AB)-1 | |A| |B| |A-1| |B-1| = |A| |A-1| |B| |B-1| = cond (A) cond (B) 例例9 求求Hilbert矩阵矩阵H3的条件数的条件数.1123111133234111345193630H, H36192180 , 30180180 1113336cond(H)HH408748. 13

28、1147361260,1, 1, 1 .TTH xx 以以三三位位十十进进制制求求解解准准确确解解1122331.000.5000.3331.83 0.5000.3330.2501.08,0.3330.2500.2000.783xxxxxx 1111222233331.089510.0895 0.4880 , 1 , 0.5120 .1.491010.4910 xxxxxxxxxxxx 如何发现判断矩阵是病态的如何发现判断矩阵是病态的? ?如何解决和处理如何解决和处理? ?预处理方法预处理方法. .,.PAQyPbAxbxQy cond()cond( ).PAQA 例例10 10 设设441211010.112xx 则则4110,11A 4244(110 )cond( )10 .101A 4141101,1 1011A 化为化为4121101.211xx 则则1444111011,10111011 422cond4.110 在三位十进制下得到很坏的近似解在三位十进制下得到很坏的近似解x=0，1T.在三位十进制下得到较好的在三位十进制下得到较好的近似解近似解x=1，1T.本章小结本章小结 本章介绍了解线性方程组的直接法。直接法本章介绍了解线性方程组的直接法。直接法是一种计算量小而精度高的方法。直接法中具有是一种计算量小而精度高的方法。直接法中具有代表性的算法是高斯（