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

兰州交通大学数理与软件工程学院第3章解线性方程组的数值解法兰州交通大学数理与软件工程学院引言求解线性方程组的数值解，在科学研究和工程计算中具有广泛的应用，如电学中的网络、大地测量、机械和建筑结构计算、工程力学中运用差分法及有限元方法解连续介质力学问题常化为线性方程组的求解。就计算数学本身，在以后章节将要介绍的样条插值、微分方程边值问题数值解等都需要解线性方程兰州交通大学数理与软件工程学院•线性方程组的一般形式为简写成矩阵形式为Ax=b。nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111兰州交通大学数理与软件工程学院•其中A＝b＝A为非奇异矩阵，这时方程(3.1)有唯一解。nnnnnnaaaaaaaaa212222111211nxxxx21nbbb21兰州交通大学数理与软件工程学院•从数值计算的特点考虑，可将线性方程组按其系数矩阵阶数的高低和含零元素多少分成两类：第一类称为低阶稠密方程组，即系数矩阵的阶数不高，含零元素很少，大家在线性代数等课程学习中通常见到的，都属这类方程组；第二类称为高阶稀疏方程组，系数矩阵的阶数很高，如几百阶、甚至成千上万阶，其中零元素成片分布，兰州交通大学数理与软件工程学院•关于线性方程组的数值解法一般有两类。–直接法：在不考虑舍入误差影响的前提下，经有限次的四则运算能得到精确解的方法。而实际上，由于受计算机字长的限制，舍入误差客观存在，只能得近似解。目前，较实用的直接法主要有古老的Gauss法及其变形——选主元消去法及矩阵的–迭代法：用某一极限过程去逼近精确解的方法，实际上是给定一个初始近似解，然后按一定法则逐步求出满足一定精度要求的近似解。兰州交通大学数理与软件工程学院3.1高斯消元法•设线性方程组•简记AX=bnnnnnnnnnnbxaxaxabxaxaxabxaxaxa........................22112222212111212111兰州交通大学数理与软件工程学院3.1高斯消元法•其中TnTnnnijnnnbbbxxxaaaaaaaaaabx2121n2n1n2222112111,)(A兰州交通大学数理与软件工程学院3.1高斯消元法•克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法。代替所得。列用的第是，，，其中法则：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(6332321xxxxxx兰州交通大学数理与软件工程学院高斯顺序消元法•下三角形方程求解设（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、第一次消元。设Tnnnnnniiibbbbbaaaaaaaniaalnaa]......[........................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.2高斯主元素消去法•Gauss列主元消元法•从第一列中选出绝对值最大的元素nnnnniiniinbaaabaaabaaabaaa....................................................................................21212112221111211兰州交通大学数理与软件工程学院高斯主元素消去法顺序消元计算机中实现)3;:;;1)2;|;|maxmax||21;i;||max1)11111TaaaaTdontojforkiathenaifdontokforaijijjjkki兰州交通大学数理与软件工程学院高斯主元素消去法•第k步从的第k列，，中选取绝对值最大项，记录所在行，即若交换第k行与l行的所有对应元素，再进行顺序消元。)(Ak(k)kka(k)kka1(k)nk.a..kkikkkiilaak记||max||)(nik)(kl兰州交通大学数理与软件工程学院高斯列主元消去法输出奇异标志，停机；；做对；；即记选列主元：做对输入：then0if)2,then||if,...,,||,|,|max||),,...,,)(),...,,(),,...,,,()1(maxmaxmaxmaxailaaaankkiaaklilaanknibnjiaikikkkkiknikkiiijk21112122121兰州交通大学数理与软件工程学院高斯列主元消去法；做对；；做对；；做对行所有对应元素，即行与第