线性方程组的数值解法素材PPT学习教案

1、会计学1线性方程组的数值解法素材线性方程组的数值解法素材 当阶数较高时用这种方法求解是不现实的。 阶行列式有 项，每项又是 个数的乘积。对较大的 ，其计算量之大，是一般计算机难以完成的。而且，这时的舍入误差对计算结果的影响也较大。n!nnn例如，求解一个20阶线性方程组，用加减消元法需3000次乘法运算，而用克莱姆法则要进行 次运算，如用每秒1亿次乘法运算的计算机要30万年。209.7 10第2页/共93页线性代数方程组的计算机解法常用方法：直接法 迭代法消去法消去法矩阵三角分解法矩阵三角分解法第3页/共93页第4页/共93页3.1 消去法消去法的基本思想：是通过将一个方程乘或除以某个常数，以

2、及将两个方程相加减，逐步减少方程中的变元数，最终使每个方程只含一个变元，从而得出所求的解。消去法常用方法：高斯消去法选主元消去法高斯约旦消去法第5页/共93页消去法3.1 高斯消去法 按自然顺序进行的消元法第6页/共93页例例 1 用高斯消元法求解方程组用高斯消元法求解方程组 12312312328214613225xxxxxxxxx解解 用第一个方程削去后两个方程中的用第一个方程削去后两个方程中的 得得 ,1x 9962214282232321xxxxxx再用第再用第2个方程消去第个方程消去第3个方程中的个方程中的 得得,2x 18962214282332321xxxxxx第7页/共93页最

3、后，经过回代求得原方程组的解为最后，经过回代求得原方程组的解为 52281412262918321323 xxxxxx例例 2 解方程组解方程组 02115472321321321xxxxxxxxx第8页/共93页解：消元 0121111547112 3235 . 2rr 620033307112 5 . 35 . 05 . 203330711231212124rrrr 回代得, 3263 x, 233332 xx127321 xxx第9页/共93页消去法 1ijabAx 11bxA 1A 1b 1ibnji, 2 , 1, 1 0111 a niaamii, 3 , 2,111111 第10

4、页/共93页i1im n1x 22bxA 22211212222222211112111nnnnnnnbbbxxxaaaaaaa njibmbbamaaiiijiijij, 3 , 2,1111211112第11页/共93页 k 12 nk1 k kkbxA knnknkkknkkknnkaaaaaaaaaaA2222322211112111 knkkkbbbbb2211 0 kkka nkiaamkkkkikik, 1, 第12页/共93页 0 kkka1 n nnbxA nnnnnnnnbbbxxxaaaaaa2211212222211112111 第13页/共93页 0 nnna11,x

5、xxnn 1 , 2 , 1 ,1 niaxabxabxiiinijjiijiiinnnnnn nkakkk, 2 , 1, 第14页/共93页 0 kkka1, 2 , 1 nk nkkjibmbbamaaaamkkikkikikkjikkijkijkkkkikik, 2, 1, 11)()( 1 , 2 , 1 ,1 niaxabxabxiiinijjiijiiinnnnnn第15页/共93页nkkiaaaikkkik, 2, 1,第16页/共93页nkkjibbabaaaaijikiijkjikij, 2, 1, 1 , 2 , 1 1 nibaxabbabiiinijjijinnnnn

6、bbb,21nxxx,21第17页/共93页定理2 Ax=b 可用高 斯消元法求解的充分必要条件是：系数矩阵 A 的各阶顺序主子式均不为零。高斯消元法的条件定理1 如果在消元过程中A的主元素 (k=1,2,n) ,则可通过高斯消元法求出Ax=b 的解。0)( kkka1110Da11110,2,3,kkkkkaaDknaa引理 A的主元素 (k=1,2,n) 的充要条件是矩阵A的各阶顺序主子式不为零，即0)( kkka第18页/共93页33n高斯消去法的计算量无法进行；或| akk(k) |1时，带来舍入误差的扩散。如何处理？ 0)( kkka第19页/共93页例例 1 解方程组解方程组 00

7、00. 10000. 10000. 10001. 20000. 30003. 02121xxxx 0 .66660 .99990001. 20000. 30003. 0221xxx解法一解法一 用高斯消元法求解（取用高斯消元法求解（取5位有效数字），用位有效数字），用第第 一个方程消去第二个方程中的一个方程消去第二个方程中的,1x3.1.2 高斯主元素消元法第20页/共93页因而再回代，得因而再回代，得 216666.00.66679999.02.00013.00000.666700.0003xx而精确值为而精确值为 显然该解与精确值相差显然该解与精确值相差太远，为了控制误差，采用另一种消元过

8、程。太远，为了控制误差，采用另一种消元过程。32,3121 xx解法二解法二 为了避免绝对值很小的元素作为主元，先交为了避免绝对值很小的元素作为主元，先交换两个方程，得到换两个方程，得到 0001. 20000. 30003. 00000. 10000. 10000. 12121xxxx第21页/共93页消去第二个方程中的消去第二个方程中的 得得 ,1x 9998. 19997. 20000. 10000. 10000. 1221xxx再回代，解得再回代，解得 3333. 06667. 00000. 10000. 16667. 09997. 29998. 112 xx结果与准确解非常接近。这个

9、例子告诉我们，在采用高斯消元法解方程组时，用做除法的小主元素可能使舍入误差增加，主元素的绝对值越小，则舍入误差影响越大。固应避免采用绝对值小的主元素，同时选主元素尽量的大，可使该法具有较好的数值稳定性。第22页/共93页列主元素消元法kkakka第23页/共93页例：例：求解线性方程组求解线性方程组 000. 3000. 2000. 1643. 5072. 1000. 2623. 4712. 3000. 1000. 3000. 2001. 0321xxx解法一：用列主元素消元法，方程组增广矩阵为：解法一：用列主元素消元法，方程组增广矩阵为： 000. 3643. 5072. 1000. 200

10、0. 2623. 4712. 3000. 1000. 1000. 3000. 2001. 0A第24页/共93页 002. 1003. 3001. 20500. 0801. 1176. 30000. 3643. 5072. 1000. 2000. 1000. 3000. 2001. 0000. 2623. 4712. 3000. 1000. 3643. 5072. 1000. 2 687. 0868. 100500. 0801. 1176. 30000. 3643. 5072. 1000. 2回代计算解为回代计算解为 Tx3678. 0 ,05113. 0,4990. 0* 第25页/共93页

11、全选主元素消元法 第26页/共93页第27页/共93页回代计算得回代计算得0.367, 0.0511, 0.491Ty从而原方程的解为从而原方程的解为 Tx367. 0 ,051. 0,491. 0 第28页/共93页3.1.3 高斯-约当(Jordan)消去法 消元时将主元上方元素也消为0，最后系数矩阵化为对角矩阵。这种算法只有消元，没有回代，这种方法称做高斯-约当(Jordan)消去法。 第29页/共93页例 用高斯-约当消去法解下列线性方程组 123123123223347712457xxxxxxxxx 解解 对线性方程组第 1 次消元，0211a，确定乘数 212111422ama，3

12、13111212ama 第30页/共93页) 1 ()3() 1 ()2(3121mm12312312322330350684xxxxxxxxx 第2次 消 元 ，2230a， 确 定 乘 数12122221.53ama，323222623ama，有 第31页/共93页1232(1)(2)(3)(2)mm12323371020330350066xxxxxx 第 3 次消元，3360a，确定乘数1313337/36ama，23233316ama有第32页/共93页1323(1)(3)(2)(3)mm12323200403060066xxxxx 解出 1232,2,1xxx 第33页/共93页消去

13、法小结第34页/共93页3.2 矩阵三角分解法nbAx n1 nnbxA LULUA ALU第35页/共93页ALUUALALU 1112121nnlll 1112112nnuuu 第36页/共93页1131313111311121212111211111232322131211323121333231232221131211)3 , 2 , 1(11113,ualluaualluajauuakuuuuuulllaaaaaaaaanULjjjj得由；得由时：为例的各元素，以此分解在于如何算出第37页/共93页)(32233213313333332332133133221231323223321

14、2313213212323231321231221222222122122ululauuululakuulalululaulauuulaulauuulak得时：由得由；得由；得时：杜里特尔分解第38页/共93页niulaniuaiiii, 3 , 2, 2 , 1,111111 由矩阵乘法规则LUA nnnnnnnnnnirrinnuuuuuulllaaaaaaaaaaa222112112121212222111211111由此可得 的第一行元素和 的第一列元素niualniauiiii, 3 , 2, 2 , 1,111111 UL第39页/共93页 当已得出 的前 行元素和 的前 列元素，

15、则对于 ，由rruirlrkkruiklnkkruiklirariurkkiurklnkkiurklria 111111nrri, 1, U1 rL1 r又可得计算 的第 行元素和 的第 列元素的公式:nrrirrurkkruiklirairlnrrirkkiurklriariu, 2, 1 ,11, 1, ,11 UrLr第40页/共93页例例 求矩阵求矩阵2144416512A 的LU分解。 u11=2 u12=1 u13=4 1213532 l22421 l32631 l212422u231247u 7)7(1431233u第41页/共93页所以所以2141002144412100276

16、512311007 700720412113012001UL第42页/共93页a11 a12 a1k a1n u11 u12 u1k u1n 第1框 a21 a22 a2k a2n l21 u22 u2k u2n 第2框 ak1 ak2 akk akn lk1 lk2 ukk ukn 第k框 an1 an2 ank ann ln1 ln2 lnk unn 第n框 按下图所示顺序逐框进行,先求 u 后求 l。矩阵三角分解算法总结：第43页/共93页 有了矩阵 A 的LU分解计算公式，当求解线性方程组 时，等价于求解 。这时可归结为利用递推计算相继求解两个三角形方程组（系数矩阵为三角矩阵）。用顺代

17、，由 求出 ，再利用回代，由 求出 。bAx bLUx bLy yUx xy3.2.2 解线性方程组的三角分解法 用杜里特尔三角分解法解线性方程组 的计算方法：bAx 第44页/共93页 对于 ，计算 和 。 求解 ，即计算 求解 ，即计算。nr, 3 , 2 nrriuri, 1, nrrilir, 2, 1, bLy niylbybyikkikii, 3 , 2,1111 yUx 1 , 2 , 1,1 niuxuyxuyxiinikkikiinnnn 计算 和 。niui, 2 , 1,1 nili, 3 , 2,1 第45页/共93页 30191063619134652. 1321xx

18、x方程组方程组试用杜里特尔分解求解试用杜里特尔分解求解例例第46页/共93页。，；，令、分解解：326246521101001636191346521311121131211332322131211323121luluuukuuuuuulllALU第47页/共93页LUAululaukuulalulauulauk473652143121434/ )(7)6(21935213223321331333322123132321321232312212222所以时：，时：第48页/共93页TyyyyyyybLy)4 , 1,10(43034, 12019,1030191014312112321321即

19、得）解（、解方程组第49页/共93页。所以方程组的解为所以方程组的解为解得：解得：解解TxxxxxxxyUx)1 , 2 , 3(3, 2,2(123321 第50页/共93页第51页/共93页用LU 直接分解的方法求解线性方程组的计算量为 ，和高斯消去法的计算量的数量级基本相同。33n当方程组系数矩阵不变，只有右侧向量b变化时，用LU分解法比消去法速度快。因为右侧向量b的改变不影响LU的变化。高斯消去法和LU分解法是等价的，其关键是把一般方程组变为三角方程组，只是实现途径不同。第52页/共93页3.4 向量与矩阵的范数向量与矩阵的范数 问题的提出 向量范数概念是三维

20、欧氏空间中向量长度概念的推广,在数值分析中起着重要作用. 为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对 （n维向量空间）中向量及 （ 维矩阵空间）中矩阵的“大小”及“距离”引进某种度量向量与矩阵范数的概念.nRnn nnR 第53页/共93页平面向量 x 大小：用 距离 反映。2221xxx 3.4 向量与矩阵的范数向量与矩阵的范数 引入范数的目的：实数大小：用绝对值反映复数大小：用模反映高维空间向量 x “大小” 用 反映？ 将度量长度数值的计算方法引入高维空间，用来反映空间向量的大小，就是范数的概念。第54页/共93页 非负性 |x|0 ，等号仅当 x=0 时成立； 齐次

21、性 对任何实数 , | x|=| | |x|； 三角不等式 |x+y| |x| +|y| ； 则称 |x| 为向量 x 的范数。定义 对任意 n 维向量 x Rn，若对应非负实数 |x| ， 满足 3.4.1 向量的范数第55页/共93页 由定义可知，向量 的范数 是按一定规律与 对应的实数，该实数的值没有确定，但只要满足这三个条件，这个实数就是向量 的一种范数。因此定义中的三个条件称为范数公理。xxxx当 时，0 x1 xx向量范数 有如下性质x证：利用条件，有11 xxxxxx yxyx yyxyyxx yxyx 证：第56页/共93页它们分别叫做向量的-范数、1-范数、2-范数、p -范

22、数（0p+）。 p -范数是以上范数的统一表达形式。常用的向量范数: 满足定义的范数不是唯一的.inixx 1maxnxxxx 211222212nxxxx ppnpppxxxx121)( 设设 x = ( x1 , x2 , , xn)T ，常用的向量范数有，常用的向量范数有 第57页/共93页 对于范数，有当 时，有 ， 只有当 时，才有 对任意实数 ，因为 ，所以 。对任意向量 ，有 0 x0max1 inixx0 x0 x Tnxxxx ,21 xxxxiiini maxmax1nRy 111maxmaxmaxmaxiiiiiii nii ni nxyxyxyxyxy iixxmax

23、例：范数的证明第58页/共93页可以证明这几种范数满足下述关系可以证明这几种范数满足下述关系 xnxxxnxx21事实上，对 Rn 上任意两种向量范数 |x| , |x| ，都存在与 x 无关的正常数 c1 , c2 使 这种性质称为向量范数的等价性。 xcxxc21 第59页/共93页12abac xxcx|x|a , |x|bRn第60页/共93页设给定 中的向量序列 ，其中 若对任何 ，都有，则向量 称为向量序列 的极限，或者说向量序列收敛于向量 ，记为：nR kx Tknkkkxxxx,21 nii, 2 , 1 *limikixx Tnxxxx*2*1*, kx*x *limxxkk

24、 向量收敛的定义：第61页/共93页向量序列收敛性定理： 向量序列收敛 (即 )的充要条件是 ，其中 为向量的任一种范数。 *limxxkk 0lim* xxkk 按不同方式规定的范数,其值一般不同。但在各种范数下考虑向量序列收敛性的结论是一致的。即向量序列如对某一种范数收敛则对其它范数也收敛，且有相同的极限。这样，在研究某一具体问题时，可以选择一较易简单的范数。第62页/共93页3.4.2 矩阵的范数第63页/共93页 定义：设 ， ，定义矩阵 的范数 对于每一种向量范数 ，相应的矩阵范数 为其中 是指 的最大可能值。即遍取所有不为0的 ，比值 中最大的，定义为 的矩阵范数。 nnRA nR

25、x AxAxA0 x maxpxppxpxAxA0max pAmaxxAxxxAxA第64页/共93页矩阵范数的性质： ,且仅当 时， ； 对任意实数 ， ； 对同维方阵 ，有: 0 A0 A0 A AA B ,BABA BAAB 相容性条件： 由矩阵范数的定义可直接得到 ，即有 ，称为相容性条件。即所给的矩阵范数与向量范数是相容的。xAxA xAAx 证明 p92第65页/共93页矩阵范数与向量范数的关系： 矩阵范数与向量范数密切相关，向量范数有相应的矩阵范数，即： （如 ）pxpAxAp1max , 2 , 1pxxAxAxAxx00maxmax AxxAxxA 第66页/共93页矩阵范数

26、与向量范数的关系： 矩阵范数与向量范数密切相关，向量范数有相应的矩阵范数，即： （如 ）pxpAxAp1max , 2 , 1p常用的矩阵范数有（矩阵范数的求取）常用的矩阵范数有（矩阵范数的求取）)(maxmaxmax211111AAAaAaATniijnjnjijni （矩阵的行范数）（矩阵的行范数）（矩阵的列范数）（矩阵的列范数）)(maxmaxmax211111AAAaAaATniijnjnjijni （矩阵的行范数）（矩阵的行范数）（矩阵的列范数）（矩阵的列范数）它们分别叫做矩阵的-范数、1-范数、谱范数。 max()TA ATA Amax2()TAA A（谱范数） 表示的最大特征值。

27、第67页/共93页例例4 设设 4321,5, 3AxT则则 TAx11, 7 求相应各范数。求相应各范数。解11751868111 AxAxAxAx35114818111 xAAxxAAx第68页/共93页3.5 方程组的性态 前几节讨论了求解线性代数方程组的直接法.给出系数矩阵A和自由项b,求未知向量x.实践中,A和b往往是实验观测数据或是计算所得结果.因此我们处理的线性方程组 实际上变成了bAx bbxxAA )(的关系怎样,是人们十分关心的问题.xbA 和和3.5.1 方程组的性态和矩阵的条件数第69页/共93页例例 1 解方程组解方程组 其中其中,bAx 61514151413141

28、3121A 现用绝对精确的计算（即不带任何舍入误差的计算）现用绝对精确的计算（即不带任何舍入误差的计算） 求解，可以看出求解，可以看出11232123312372240180240900720180720600 xbbbxbbbxbbb 此时，我们发现对于两组不同的自由项此时，我们发现对于两组不同的自由项 TTbbbbbbbb 321321, 600720180720900240180240721A第70页/共93页它的差只有它的差只有 ,Tbbb 而所得解而所得解 与与 之差却是之差却是xx Txxx 1500,1860,492 两组不同的右端其分量之差不过是两组不同的右端其分量之差不过是

29、可是解的差高可是解的差高 达达 之之1860倍像这样的方程组或矩阵倍像这样的方程组或矩阵A 就叫做病态的就叫做病态的 , 定义1 若方程组 Ax=b 的系数矩阵 A 或右端向量 b 的微小变化（小扰动）引起解产生巨大变化,则称此方程组为病态方程组; A称为病态矩阵, 否则称为良态方程组, A 称为良态矩阵。 第71页/共93页定理：设 非奇异， ，且 则 0 bAxA bbxxA bbAAxx 1 为了定量地刻划方程组的“病态”程度，下面就一般方程组 进行讨论。首先考察右端项b 的扰动对解的影响。bAx 第72页/共93页证： 设x为Ax=b的准确解，当方程组右端有小扰动b而A准确时,受扰解为

30、 x +x , 即 A(x +x)=b+ b 因为 Ax=b 所以 x=A-1 b 又由xAAxb 得得bAx 1因此bAbAx 11 bbAAxx 1bAx 1 即：即：第73页/共93页此不等式表明,解的相对误差不超过b的相对误差的 |A| |A-1| 倍.bbAAxx 1 bbAAAAAAAAxx111若系数矩阵A也有小扰动A ,则还可进一步导出更一般的误差估计式第74页/共93页定义定义2 设设A 为非奇异矩阵，称数为非奇异矩阵，称数cond(A)= |A| |A-1| 为为A 矩阵的条件数矩阵的条件数矩阵的条件数与范数有关，通常使用的条件数有 AAAAAAAcondAAAcondTT

31、minmax21221 所以，Cond(A)越大,A的病态程度越严重。 对任何非奇异矩阵对任何非奇异矩阵A，都有，都有 。 1 Acond不难证明，条件数具有如下不难证明，条件数具有如下性质性质第75页/共93页例例 求矩阵求矩阵A 的条件数，其中的条件数，其中 615141514131413121A解：解：1213max3131 jijiaA 600720180720900240180240721A于是于是 从而从而,18601 A 20151 AAAcond所以A是病态的第76页/共93页矩阵的某些行或列近似相关，这样的矩阵则有可能是病态矩阵。第77页/共93页3.5.2 直接法的精度分析

32、定理：设 是方程组 的一个近似解，其精确解记为 ， 为 的余量，则有xbAx *xrxbrAAxxx1* 求得方程组 的一个近似解 后，希望能判断其精度。检验精度的一个简单办法是将近似解再回代到原方程组去求其余量 。如果 很小，就认为解 是相当准确的。bAx xxAbr rxx第78页/共93页该定理给出了方程组近似解的相对误差界。即相对误差的事后估计证：由于 ，而 ，故有 bAx *rxxA *bAxxAAxb *1rArAxx11* 所以brAAxxx1* 第79页/共93页生成向量序列 x(k) ，若 xxkk)(lim称为迭代格式（1）的迭代矩阵。则有x* =Bx*+f ， 即x*为原

33、方程组Ax=b 的解，B迭代法基本思想：将方程组 Ax=b ( |A|0 ) 转化为与其等价的方程组x = Bx+fx(k+1) = Bx(k) + f （k=0,1,2,) (1)取初始向量 x(0)按下列迭代格式第80页/共93页雅可比迭代法 对线性方程组可以建立不同的迭代格式。下面介绍构造迭代格式的几种常用方法，雅克比迭代法和高斯塞德尔迭代法。设方程组 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111第81页/共93页其中 aii0 ( i=1 , 2 , , n)11221111221122221122111nnnnnnnnnnxa xa xbaxa xa xbaxa xa xba 分别从上式n个方程中分离出n个变量，如下：第82页/共93页建立迭代格式 )(1)(1)(1)(11)(11) 1(2)(2)(323)(12122) 1(21)(1)(313)(21