第六章 线性方程组数值解法a

第六章解线性方程组的直接法实际中，存在大量的解线性方程组的问题。很多数值方法如插值、数据拟合、常微分方程数值解等，到最后也会涉及到线性方程组的求解问题。nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111bAX记为：nnnnnnnbxaxabxaxa11111110)det(A对线性方程组：或者：bAx我们有Gram法则：时方程有唯一的解，而且解为：nnninninniiiiiaabaaaabaaDADDDx11111111111det),det(,当且仅当但Gram法则不能用于计算方程组的解，如n＝100，1033次/秒的计算机要算10120年解线性方程组的方法可以分为2类：①直接法：不考虑计算过程的舍入误差时，经有限次数的运算便可求得方程组准确解的方法准确，可靠，理论上得到的解是精确的适用于方程组系数矩阵阶数不太高的问题②迭代法：速度快，但有误差求解bxA§6.1高斯消元法/*GaussianElimination*/高斯消元法：思路=高斯消元法包括两个过程：消元过程：把方程组化为同解的上三角形方程回代过程：自下而上地代入计算各个解45247213232121321xxxxxxxx9164841005651520131221405651520131245247021131212352422323121x,x,x........r./rrrr/r求解方程组解：采用增广矩阵描述求解过程：定义:矩阵的初等行变换是指对矩阵进行三种变换.对换变换.即将矩阵中的某两行对换位置.倍乘变换.即将某一行遍乘一个非零常数k.倍加变换.即将矩阵的某一行遍乘一个常数k加至某一行注意下标的顺序回代求解消元记,)()1()1(nnijaAA)1()1(1)1(...nbbbbStep1：设，计算因子0)1(11a)...,,2(/)1(11)1(11niaamii将增广矩阵/*augmentedmatrix*/第i行mi1第1行，得到)1(1)1(1)1(12)1(11...baaan)2(A)2(b)...,,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij其中Stepk：设，计算因子且计算0)(kkka)...,,1(/)()(nkiaamkkkkikik)...,,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij共进行？步n1)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaa回代)()(/nnnnnnabx0)(nnnaWhatif?Nouniquesolutionexists.)1...,,1()(1)()(niaxabxiiinijjiijiii0)(iiiaWhatif?Thenwemustfindthesmallestintegerkiwith,andinterchangethek-throwwiththei-throw.0)(ikiaWhatifwecan’tfindsuchk?Nouniquesolutionexists.定理若A的所有顺序主子式/*determinantofleadingprincipalsubmatrices*/均不为0，则高斯消元无需换行即可进行到底，得到唯一解。iiiiiaaaaA...............)det(1111注：事实上，只要A非奇异，即A1存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。选主元消去法/*PivotingStrategies*/例：单精度解方程组211021219xxxx/*精确解为和*/...1000...00.1101191x8个...8999...99.0212xx8个用GaussianElimination计算：911212110/aam999212210101010...0.011ma8个92121012mb9991010011100,112xx小主元/*Smallpivotelement*/可能导致计算失败。全主元消去法/*CompletePivoting*/每一步选绝对值最大的元素为主元素，保证。1||ikmStepk:①选取;0||max||,ijnjikjiaakk②Ifikkthen交换第k行与第ik行;Ifjkkthen交换第k列与第jk列;③消元注：列交换改变了xi的顺序，须记录交换次序，解完后再换回来。列主元消去法/*PartialPivoting,ormaximalcolumnpivoting*/省去换列的步骤，每次仅选一列中最大的元。0||max||,iknikkiaak例：211111091,112xx11021111102119注：列主元法没有全主元法稳定。0,112xx例：211101019999991010010101注意：这两个方程组在数学上严格等价。标度化列主元消去法/*ScaledPartialPivoting*/对每一行计算。为省时间，si只在初始时计算一次。以后每一步考虑子列中最大的aik为主元。||max1ijnjiasnkkkaa...iiksa注：稳定性介于列主元法和全主元法之间。运算量/*AmountofComputation*/由于计算机中乘除/*multiplications/divisions*/运算的时间远远超过加减/*additions/subtractions*/运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。GaussianElimination:Stepk：设，计算因子且计算0)(kkka)...,,1(/)()(nkiaamkkkkikik)...,,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij共进行n1步)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx)1...,,1()(1)()(niaxabxiiinijjiijiii(nk)次(nk)2次(nk)次(nk)(nk+2)次nnnknknnk6523)2)((2311消元乘除次数：1次(ni+1)次22)1(1211nninni回代乘除次数：GaussianElimination的总乘除次数为，运算量为级。nnn3132333n三对角方程nnnnnnnnndddddxxxxxbacbacbacbacb132113211113332221111002,,10iiiiinnbcbacacinba　且（）　　§6.2解三对角方程组的追赶法设系数矩阵的元素满足追赶法的基础仍是高斯消元法。消元过程称为“追”的过程。1111122222233331111111111nnnnnnnnnnbcdyabcdyabcdyabcdyabd111111111/,//(),()/()2,3,...,1iiiiiiiiiiiicbydbcbaydyabain其中：回代过程称为“赶”的过程。111,...,ni,xyxyxiiiinn追赶法：运算量很小例：求解三对角方程100121001210012100124321xxxx解：iaibicidibi-uiaiuiyixi102-11－-0.50.512-12-101.5-.667.33313-12-101.3330.750.2514-12011.25-11bAx一.简单迭代法1.迭代法建立.考虑gBxxbAx(矩阵B不唯一)对应写出(1)()(0)(0,1,2,)kkxBxgkx取定初始向量§6.3解线性方程组的迭代法产生向量序列,,,,,)1()()2()1(kkxxxx若收敛,记xxkk)1(lim则有：,gxBx上式说明：是解向量,从而当k充分大时)1(kx注意:迭代阵B不唯一,影响收敛性。解向量(3.4)叫简单迭代法,B叫迭代矩阵。2.收敛性.定义3.3称|)(|max)(1BBini为矩阵B的谱半径。定理3.3简单迭代法（证略））（都收敛对任意初始向量1)0()()1(BxgBxxkkxxx都不收敛”。时不能说“对任意）（注意)0(1:xB收敛。则其对任意或若对迭代法)0(11111)()1(1||max||||1||max||||,),2,1,0(xbBbBkgBxxnjijniniijnjkk定理3.4),,2,1(|||||||,|max||||max||||||)()4.3(1||||)1()(1k1)(11)()1(1)()1(niBxxxxxxbxxbxxxxbxxgBxxBkikijkjnjnjjkjijninjjkjijikinjjkjijiki则记相减有与为例。将证：以收敛列解(i=1,2,…,n))(0011时当kBBkkkklim||max)1(1xxikinixki)1(xi即=0,例3.2设有方程组(其中)Ax=b,即aii0a11bxaxaxnn111212bxaxaxann22222121bxaxaxannnnnn2211(3.5)作等价变形xaxaxbaxnn12121111101xaxxabaxnn22121222201xaxabaxnnnnnnn02111(3.6)----------Jacobi迭代法]..........0[1)(1)(212)(1111)1(1knnkkkxaxaxbax]..........0[1)(2)(2)(1212)1(222knnkkkxaxxabax]0..........[1)()(22)(11)1(knknknnnnknxxaxabax于是有迭代公式(k=0,1,2,…)(3.7)