数值计算方法第3章解线性方程组的数值解法1ppt课件

1、1 第第3章章 解线性方程组的数值解法解线性方程组的数值解法2引言 在自然科学和工程技术中很多问题的处理经常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法务虚验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况经常归结为求解大型线性方程组。 线性代数方面的计算方法就是研讨求解线性方程组的一些数值解法与研讨计算矩阵的特征值及特征向量的数值方法。3引言n关于线性方程组的数值解法普通有两类。n直接法：经过有限步算术运算，可求得方程组的准确解的方法假设在计算过程中没有舍入误

2、差n迭代法：用某种极限过程去逐渐逼近线性方程组准确解的方法n 迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题。43.1 高斯消元法n设线性方程组n简记 AX=bnnnnnnnnnnbxaxaxabxaxaxabxaxaxa.221122222121112121115高斯消元法n其中nnijnnnaaaaaaaaaa)(An2n1n2222112111TnTnbbbxxxbx2121,6高斯消元法n克莱姆法那么在实际上有着艰苦意义，但在实践运用中存在很大的困难，在线性代数中，为处理这一困难给出了高斯消元法。代替所得。列用的第是，其中，法则：

3、biAAADniDDxGrameriiiii)det(0A)det(D,.,2 , 17高斯消元法n例1.用消元法解方程组) 3(122)2(54) 1 (632132321xxxxxxxx8例题n第一步：-2xr1+r3得)4(114)2( 54) 1 (63232321xxxxxxx9例题n第二步：1 x r2+r4n回代得：x=1,2,3T)5(62)2(5) 1 (6332321xxxxxx103.1.1 高斯顺序消元法n下三角形方程求解下三角形方程求解n 设设n 1nilbxlxlxlbxlxlbxliinnnnnn,.,2 , 1, 0.221122221211111其中，11高斯

4、顺序消元法n由1得1122121221111/)(./)(ninnininnlxlbxlxlbxlbx该法称为向前代入法。即nilxlbxlbxiiijjijii,.,3 , 2/ )(/:11111112高斯顺序消元法n算法：;/ )(;11; 0nto2i3/2; ), 2 , 1, 2 , 1(,11111iiiijijiijlsbxxlssdoitojForsdoForlbxijnibl、赋初值13高斯顺序消元法 nnnnllllllLLbx21222111(1)其中式可简写成，14n上三角方程组的解法上三角方程组的解法n设设n ,.,n,iubxu.bxu.xubxu.xuxuiin

5、nnnnnnn210)2(2222211212111其中，15n由2式回代得n 12,.11,ni)/uxu(bx/ubxiinijjijiinnnn16上三角方程组的解法nnnnuuuuuuUUbx22211211(2)其中式可简写成，17高斯顺序消去法高斯顺序消去法n设 Ax=b. 记A(1)=A b(1)=b。设n1、第一次消元。0iiaTnnnnnniiibbbbbaaaaaaaniaalnaa.AA,.,3 , 2,.,32ii)()2()2(2)1(1)2()1()2()2(2)2(2)2(22)1(1)1(11)1(11)2(1)1(11)1(11)1(11)1(1）（令），行（

6、第第一行18高斯顺序消去法 ),.,2;,.,2()1(11)1(1)1(1)1()1(11)1()2(njniaaaaalaajiijjiijij),.,2(.)1(1)1(11)1(1)1(1)1(1)1()2(nibaablbbbiiiii19高斯顺序消去法n设第k-1次消元得A(k)x=b(k) 其中)()()2(2)1(1)()()()()2(2)2(22)1(1)1(12)1(11)()(.|knkkknnknkkknkkknnkkbbbbaaaaaaaaabA20高斯顺序消去法 那么第k次消元:nkjnkialaakkjikkijkij,.,1;,.,1)()()1(，则有，令1

7、,.,2 , 1,.,1)()(nknkiaalkkkikiknkiblbbkkikkiki,.,1)()()1(，21高斯顺序消去法n最后)()()2(2)1(1)()()()2(2)2(22)1(1)1(12)1(11)()(.nnkknnnkknkkknnnnbbbbaaaaaaaabA22高斯顺序消去法n也就是对于方程组AX=b系数矩阵做：) 1,.,2 , 1(,.,1,.,1/)()()1()()()1()()(nknkjnkilbbbalaaaalikkkkikikkjikkijkijkkkkikik23高斯顺序消去法 )()()2(2)1(1)()()()2(2)2(22)1(

8、1)1(12)1(11)()()n(.)(|AnnkknnnkknkkknnnnbbbbaaaaaaaanAbbx其中得到24高斯顺序消去法 ) 1,.,1(/ ).(/A)(1)()()()()()(niaxabxabxiiinijjiijiiinnnnnnnbx回代法再解25高斯顺序消去法；做对；做对机；输出算法失败信息，停做对输入：kjikijijkikiikkikikikkkiijalaankjblbbaalankianknibnjia,.,32/1,.,)2thenif),.,)(),.,(),.,() 1 (00011011212212126高斯顺序消去法)det(),.,()(.

9、)(det)3/ )(,.,)2/) 1else,thenif)(AAnixaaaAaxabxbniabxbainniinijjijiiinnnnnnn的行列式的值系数矩阵输出：方程组的解；做对；做并停机输出算法失败信息214121032211127高斯顺序消去法算法框图28高斯消去法的计算量 次除法。即做kn),.,1i (/:)()(nkaalkkkkkikik步第:) 1)()1()(故总的消元计算量为次乘法需由knknAAkk11)52)(1(61)1)()(nknnnknknkn) 1(21)()(nnbXAnn回代时乘除运算量为解) 13(312nnnN即总计算量为29高斯顺序消去

10、法条件nkakkk,.,2 , 1, 0)(高斯顺序消去法要求0.)det()()2(22)1(11nnnaaaA有：.也就是此算法的缺点., 00:)()()(即数值不稳定做除数易产生解的失真用此时很小，但若即使kkkkkkkkkaaa303.1.2 高斯主元素消去法nGauss列主元消元法n从第一列中选出绝对值最大的元素1111maxiniaannnnniiniinbaaabaaabaaabaaa.21212112221111211交换31高斯列主元消去法顺序消元计算机中实现) 3;:;1)2;|;|maxmax|2 1;i ; |max 1)11111TaaaaTdontojforkia

11、thenaifdontokforaijijjjkki32高斯列主元消去法n第 k 步n 从 的第 k 列 ， ， 中选取绝对值最大项，记录所在行，即n 假设 交换第k行与l行的一切对应元素，再进展顺序消元。n (k)kka1)(Ak(k)nk.a.(k)kkakkikkkiilaak记|max|)(nik)(kl 33框图34高斯列主元消去法输出奇异标志，停机；做对；即记选列主元：做对输入：then0if)2,then|if,.,| ,|,|max|),.,)(),.,(),.,() 1 (maxmaxmaxmaxailaaaankkiaaklilaanknibnjiaikikkkkiknik

12、kiiijk2111212212135高斯列主元消去法；做对；做对；做对行所有对应元素，即行与第交换第kjikijijkikiikkikikikiikkljljkjkjalaankjblbbaalankiTbbbbTTaaaaTnkkjlkkl,.,32/1,.,)4;2;,.,1then if)30000011136高斯列主元消去法。输出：方程组的解；做对；并停机输出奇异标志回代求解),.,()(/ )(,.,)2/) 1else,thenif)(nixaxabxbniabxbaiiinijjijiiinnnnnnn214121031372. 全主元消去法n例如.求解方程组n Txxxx)3

13、675. 0 ,05104. 0,4904. 0(:4,4000. 3000. 2000. 1643. 5072. 1000. 2623. 4712. 3000. 1000. 3000. 2001. 0*321位有效数字为精确解舍入到位浮点数进行计算用38全主元消去法.)4000. 0 ,09980. 0,4000. 0(00. 2002. 1000. 100. 500005. 32.0040000. 3000. 2001. 0003. 2002. 1000. 1006. 6001. 40005. 32.0040000. 3000. 2001. 0000. 3000. 2000. 1643.

14、5072. 1000. 2623. 4712. 3000. 1000. 3000. 2001. 0)|A(.是一个很坏的解解得用高斯顺序消去法求解Txb39全主元消去法Txb)3676.0,51080.0,88544.0(6866.0500.0000.38676.1008015.13.17605.6431.00722.000-0015.1500.0000.30023.30005.208015.13.17605.6431.00722.000-000.1000.2000.3000.3000.2001.0623.43.7121.000-643.5072.1000.2000.3000.2000.164

15、3.5072.1000.2623.4712.3000.1000.3000.2001.0)|A(.3i 得用选列主元消去法求解40全主元消去法；，对；中选绝对值最大者从选主元、第一步消元jtilathenaifdonjnitlanjiaijijij|max|max,.,1,.,1; 11|max.),.,2 , 1,(,) 111141全主元消去法顺序消元；做，初值踪数组序发生改变，因此设跟解的次而交换列时解的次序不变交换行时；列交换第一列与第；行交换第一行与第) 3)() 1 (,)Z(.2)Z(21)Z(1),(,),.,2 , 1(:),.,2 , 1(:)211tZZnniZniaatn

16、jaalitiljj42全主元消去法顺序消元列列交换行行交换如果；步选主元时得）假设第步消元：、第)2)()(;,;,;|max12)(;)(tzkztkktlkkljtilaakkkkkijnjikkjikk43全主元消去法),.,2 , 1()(: )()(),2(),1 (321nibizxnxnzxbzxbzxbin则增加数组理顺解：、求方程组的解44求最终的解。程序结束后，例如332211,1) 3(, 2)2(, 3) 1 (:bxbxbxzzz) 3() 1 (31ZZjj分析：做。；其解，这时321) 1 ()3()2()2() 3()1 (:2)2(, 1) 3(, 3) 1

17、 (bxzxbxzxbxzxzzz45Gauss全主元消元算法；做对做对；即记选全主元：做对输入：jtilaaaankkjnkkiaaktkljtilaankniiiznibnjiaijijkkkkijnjikjiiijkk,|,|then|if,.,.,|; ,|,|max|),.,)();,.,()()(),.,(),.,() 1 (maxmaxmax,212111213212212146Gauss全主元消元算法；做对；做对；输出奇异标志，并停机kjikijijkikiikkikikikitiklkljkjalaankjblbbaalankitzkzniaaktbbnkkjaakla,.,

18、32/1,.,)4);()();,.,(then if;);,.,(then if)3then0if)2000max1121147Gauss全主元消元算法。输出解；做对；并停机输出奇异标志),.,()(),.,()()3/ )(,.,)2/) 1else,thenif)(nixnibizxababbniabbaiiiinijjijiinnnnnn21521121041483.高斯-约当消去法n与普通消去法相比，高斯约当消去法是一种无回代过程的算法n设方程组AX=b经过k-1次消元得)()(1)(1)()()(1)(1)(1)(1)()(11Aknkkkknnknkkkkkkkknkkkkbbbaaaaaab49高斯-约当消去法Tnnnnkkkikkikikkjkikkikkijkikkkkkkkkkkkkkjkkjkkkkiknikkikikbbbxnkinibabbnkjkiniaaaakinikankkjabbaaaalkklilaankkiak),.,(,),.,2, 1(),.,1,.,2, 1(),.,2, 1i (),.1,(/0,|,|max|),.,1,(k)1