第3章 解线性方程组的数值解法1

第3章解线性方程组的数值解法引言在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组。线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。引言关于线性方程组的数值解法一般有两类。直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题3.1高斯消元法设线性方程组简记AX=bnnnnnnnnnnbxaxaxabxaxaxabxaxaxa........................22112222212111212111高斯消元法其中TnTnnnijnnnbbbxxxaaaaaaaaaabx2121n2n1n2222112111,)(A高斯消元法克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法。代替所得。列用的第是，，，其中法则：biAAADniDDxGrameriiiii)det(0A)det(D,...,2,1例题例1.用消元法解方程组)3(122)2(54)1(632132321xxxxxxxx例题第一步：-2x（1）+(3)得)4(114)2(54)1(63232321xxxxxxx例题第二步：1x（2）+（4）回代得：x=[1,2,3]T)5(62)2(54)1(6332321xxxxxx3.1.1高斯顺序消元法下三角形方程求解设（1）nilbxlxlxlbxlxlbxliinnnnnn,...,2,1,0.........221122221211111其中，高斯顺序消元法由（1）得该法称为向前代入法。即nilxlbxlbxlxlbxlxlbxlbxiiijjijiininnininn,...,3,2/)(//)(....../)(1111111122121221111高斯顺序消元法算法：;/)(;11;0nto2i3/2;),,2,1,,2,1(,11111iiiijijiijlsbxxlssdoitojForsdoForlbxijnibl、、、赋初值高斯顺序消元法nnnnllllllLbx21222111A(1)其中式可简写成，上三角方程组的解法设,...,n,,iubxu......bxu......xubxu......xuxuiinnnnnnnn210)2(2222211212111其中，由（2）式回代得12,...11,ni)/uxu(bx/ubxiinijjijiinnnn上三角方程组的解法nnnnuuuuuuUUbx22211211(2)其中式可简写成，高斯顺序消去法设Ax=b.记A(1)=Ab(1)=b1、第一次消元。设0iiaTnnnnnniiibbbbbaaaaaaaniaalnaa]......[........................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）（令），，行（第第一行高斯顺序消去法),...,2(.),...,2;,...,2()1(1)1(11)1(1)1(1)1(1)1()2()1(11)1(1)1(1)1()1(11)1()2(nibaablbbbnjniaaaaalaaiiiiijiijjiijij高斯顺序消去法设第k-1次消元得A(k)x=b(k)其中)()()2(2)1(1)()()()()2(2)2(22)1(1)1(12)1(11)()(...................................................][knkkknnknkkknkkknnkkbbbbaaaaaaaaabA高斯顺序消去法则第k次消元:1,...,2,1,...,1,,...,1;,...,1,,...,1,)()()1()()()1()()(nknkiblbbnkjnkialaankiaalkkikkikikkjikkijkijkkkikik则有令高斯顺序消去法最后)()()2(2)1(1)()()()2(2)2(22)1(1)1(12)1(11)()(......................................................][nnkknnnkknkkknnnnbbbbaaaaaaaabA高斯顺序消去法也就是对于方程组AX=b系数矩阵做：)1,...,2,1(,...,1,...,1/)()()1()()()1()()(nknkjnkilbbbalaaaalikkkkikikkjikkijkijkkkkikik高斯顺序消去法)()()2(2)1(1)()()()2(2)2(22)1(1)1(12)1(11)()()n(......................................................])([AnnkknnnkknkkknnnnbbbbaaaaaaaanAbbx其中得到高斯顺序消去法)1,...,1(/).(/A)(1)()()()()()(niaxabxabxiiinijjiijiiinnnnnnnbx回代法再解高斯顺序消去法；做对；；做对机；输出算法失败信息，停做对输入：kjikijijkikiikkikikikkkiijalaankjblbbaalankianknibnjia,...,32/1,...,)2thenif),,...,,)(),...,,(),,...,,,()1(000110112122121高斯顺序消去法)det(),,...,,()(...)(det)3/)(,,...,)2/)1else,thenif)(AAnixaaaAaxabxbniabxbainniinijjijiiinnnnnnn的行列式的值系数矩阵输出：方程组的解；；做对；做并停机输出算法失败信息2141210322111高斯顺序消去法算法框图高斯消去法的计算量)13(31)1(21)52)(1(61)]1)(()[(:)1)((n),...,1i(/:2)()(11)1()()()(nnnNnnbXAnnnknknknknknAAknkaalknnnkkkkkkkikik即总计算量为回代时乘除运算量为解故总的消元计算量为次乘法需由次除法除法即步第高斯顺序消去法条件.,,,0.,...,2,1,0,...,2,1*)det(:)det(1:)det(0...)det()()()()()()2(22)1(11即数值不稳定做除数易产生解的失真用此时很小若也就是次算法的缺点求因此高斯顺序消去法要即kkkkkkkkkkkknnnaankankaAAAaaaA3.1.2高斯主元素消去法Gauss列主元消元法从第一列中选出绝对值最大的元素1111maxiniaannnnniiniinbaaabaaabaaabaaa....................................................................................21212112221111211交换高斯列主元消去法顺序消元计算机中实现)3;:;;1)2;|;|maxmax||21;i;||max1)11111TaaaaTdontojforkiathenaifdontokforaijijjjkki高斯列主元消去法第k步从的第k列，，中选取绝对值最大项，记录所在行，即若交换第k行与l行的所有对应元素，再进行顺序消元。(k)kka1)(Ak(k)nk.a..(k)kkakkikkkiilaak记||max||)(nik)(kl框图高斯列主元消去法输出奇异标志，停机；；做对；；即记选列主元：做对输入：then0if)2,then||if,...,,||,|,|max||),,...,,)(),...,,(),,...,,,()1(maxmaxmaxmaxailaaaankkiaaklilaanknibnjiaikikkkkiknikkiiijk21112122121高斯列主元消去法；做对；；做对；；做对行所有对应元素，即行与第交换第kjikijijkikiikkikikikiikkljljkjkjalaankjblbbaalankiTbbbbTTaaaaTnkkjlkkl,...,32/1,...,)4;;2;;,...,,1thenif)300000111高斯列主元消去法。输出：方程组的解；做对；并停机输出奇异标志回代求解),...,,()(/)(,,...,)2/)1else,thenif)(nixaxabxbniabxbaiiinijjijiiinnnnnnn2141210312.全主元消去法例如.求解方程组Txxxx)3675.0,05104.0,4904.0(:4,4000.3000.2000.1643.5072.1000.2623.4712.3000.1000.3000.2001.0*321位有效数字为精确解舍入到位浮点数进行计算用全主元消去法.)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.5072.1000.2623.4712.3000.1000.3000.2001.0)|A(.是一个很坏的解解得用高斯顺序消去法求解Txb全主元消去法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.1