第三章线性方程组数值解法

第3章线性方程组的数值解法《计算方法与实习》第3章线性方程组的数值解法§1高斯消去法§2高斯―约当消去法§3解实三对角线性方程组的追赶法§4矩阵的三角分解§5行列式和逆矩阵的计算§6迭代法§7迭代法的收敛性第3章线性方程组的数值解法《计算方法与实习》实际中，存在大量的解线性方程组的问题。很多数值方法到最后也会涉及到线性方程组的求解问题：如样条插值的M和m关系式，曲线拟合的法方程，求解非线性方程组问题,方程组的Newton迭代等问题。第3章线性方程组的数值解法《计算方法与实习》nnnnnnnbxaxabxaxa11111110)det(A对线性方程组：或者：bAx我们有Gram法则：当且仅当时，有唯一的解，而且解为：nnninninniiiiiaabaaaabaaDADDDx11111111111det),det(,3—13.1简介第3章线性方程组的数值解法《计算方法与实习》但Gram法则不能用于计算方程组的解，如n＝100，1033次/秒的计算机要算10120年解线性方程组的方法可以分为2类：①直接法：准确，可靠，理论上得到的解是精确的,但由于计算中有舍入误差,故得到的也是近似解.②迭代法：速度快，但有误差（雅可比迭代法、高斯—赛得尔迭代法）第3章线性方程组的数值解法《计算方法与实习》3.2消元法我们知道，下面有3种方程的解我们可以直接求出：niabxaaadiagAiiiinn,,1,),,,(2211①n次运算nilxlbxllllllAiiijjijiinnnn,,1,1121222111②（n＋1）n/2次运算第3章线性方程组的数值解法《计算方法与实习》1,,,122211211niuxubxuuuuuuAiinijjijiinnnn③（n＋1）n/2次运算第3章线性方程组的数值解法《计算方法与实习》对方程组，作如下的变换，解不变①交换两个方程的次序②一个方程的两边同时乘以一个非0的数③一个方程的两边同时乘以一个非0数，加到另一个方程因此，对应的对增广矩阵(A，b)，作如下的变换，解不变①交换矩阵的两行②某一行乘以一个非0的数③某一行乘以一个非0数，加到另一行消元法就是对增广矩阵作上述行的变换，变为我们已知的3种类型之一，而后求根第3章线性方程组的数值解法《计算方法与实习》步骤如下：第一步：niiaai,,2,1111行第行第nnnnnnnbaaabaaabaaa21222221111211)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa运算量：(n-1)*(1+n)第3章线性方程组的数值解法《计算方法与实习》)3()3()3(3)3(3)3(3)3(33)2(2)2(2)2(23)2(221113121100000nnnnnnnbaabaabaaabaaaa运算量：(n-2)*(1+n-1)=(n-2)n第二步：niiaai,,3,2)2(22)2(2行第行第)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa第3章线性方程组的数值解法《计算方法与实习》第k步：nkiiaakkkkik,,1,k)()(行第行第类似的做下去，我们有：运算量：(n－k)*(1＋n－k＋1)=(n－k)(n－k＋2))()()3(3)3(3)3(33)2(2)2(2)2(23)2(2211131211000000nnnnnnnnbabaabaaabaaaan－1步以后，我们可以得到变换后的矩阵为：第3章线性方程组的数值解法《计算方法与实习》因此，总的运算量为：11)2)((nkknkn加上解上述上三角阵的运算量(n+1)n/2，总共为：)(33323nOnnn第3章线性方程组的数值解法《计算方法与实习》注意到，计算过程中)(kkka处在被除的位置，因此整个计算过程要保证它不为0所以，Gauss消元法的可行条件为：0)(kkka因此，有些有解的问题，不能用Gauss消元求解另外，如果某个)(kkka很小的话，会引入大的误差第3章线性方程组的数值解法《计算方法与实习》高斯主元素消元法是消去法的一种改进。它的基本思想是在逐次消元时总是选绝对值最大的元素(称之为主元)做除数,按消元法的步骤消元。这里主要介绍求解线性方程组最常用的列主元素消去法列主元素消去法所谓列主元素消去法就是在每一步消元过程中取系数子矩阵的第一列元素中绝对值最大者作主元。对线性方程组(3―1)进行n-1次消元后,可得到上三角形方程组第3章线性方程组的数值解法《计算方法与实习》2、列主元消元法在Gauss消元第k步之前，做如下的事情：||||max)()(kjkkiknikaa若交换k行和j行行的交换，不改变方程组的解，同时又有效地克服了Gauss消元的缺陷例：211111091,112xx11021111102119第3章线性方程组的数值解法《计算方法与实习》Gauss全主元消去法：优点------计算结果更可靠；缺点------挑主元花机时更多，次序有变动，程序复杂。说明：(1)也可采用无回代的列主元消去法(叫Gauss---Jordan消去法)，但比有回代的列主元消去法的乘除运算次数多.(2)有回代的列主元消去法所进行的乘除运算次数为，量很小。nnn313123nxx,,1第3章线性方程组的数值解法《计算方法与实习》总结1、高斯消去法的计算步骤为:1.消元过程对于k=1,2,…,n-1,若按顺序有某一ark≠0,r≥k,则交换k与r行,然后计算1,2,,/,1,2,,1ijikkjkkijikknaaaaajkkn2.回代过程对于k=n,n-1,…,2,1,计算11()/nkknkjjkkjkxaaxa第3章线性方程组的数值解法《计算方法与实习》123123123231425427xxxxxxxx①②③例1用列主元素消去法解方程组第3章线性方程组的数值解法《计算方法与实习》2、列主元消元法1）消元过程：对k=1,2,…,n-1（1）选主元：确定r，使得,ikikkkala,ijijikkjaala2)回代过程:(),1()()(),11()(),(1,2,...,1)nnnnnnnniiinijjjiiiiiaxaaaxxinnamaxrkikaika若，则停止计算；否则进行下一步0ika（2）交换A的r、k两行；（3）对i=k+1,…,n,对j=k+1,…,n+1计算第3章线性方程组的数值解法《计算方法与实习》3、矩阵直接分解法（高斯消元法的矩阵解释）Gauss消元法的第k步：（k=1,2,…n－1）nkiiaakkkkik,,1,k)()(行第行第从矩阵理论来看，相当于左乘矩阵（见P52~55）()()()()1()11,,1,,11kkikikkkkkkkknkaliknlalLk=第3章线性方程组的数值解法《计算方法与实习》因为：则矩阵Lk可逆，且10kL111111kkknkLll第3章线性方程组的数值解法《计算方法与实习》因此，整个Gauss消元法相当于左乘了一个单位下三角阵1111)(1)(1)(121nnnknknkkklllllL所以有()..(1)=nLstALAL为单位下三角阵，令U为上三角阵yUxbLybLUxbAx因此,我们可以通过2次反代过程求解方程组.把A分解为单位下三角L和上三角U的乘积叫做A的LU分解。其中高斯消元法是实现LU分解的一种方法。L1-1……Ln-1-1=(求出y)（求出x)第3章线性方程组的数值解法《计算方法与实习》比较第2行：22112222112,,jjjjjjaluujnualu比较第2列：22121222221212u,,3uuulalnillaiiiiiinnnnnnnnnnnnuuuuuulllaaaaaaaaa222112112121212222111211111第3章线性方程组的数值解法《计算方法与实习》比较第k行：1111,,krrjkrkjkjkjkrrjkrkjulaunkjuula比较第k列：kkkrrkirikikkkikkrrkirikuulalnkiulula1111,,1K-1次K-1＋1次第3章线性方程组的数值解法《计算方法与实习》分解过程完毕，加上两次反代过程1,,,,,1,111niuxuyxniylbyiinijjijiiijjijii总运算量为：332)1(2)1()()1)(1(2311nnnnnnnkknkknnk第3章线性方程组的数值解法《计算方法与实习》nnnnnnulluuluuu212222111211存储在矩阵的原来位置，且不影响计算紧凑格式：P62~63第3章线性方程组的数值解法《计算方法与实习》3、解实三对角线性方程组的追赶法实三对角线性方程组是一类特殊的方程组。我们将利用所谓“追赶法”解决。设所给的实三对角线性方程组为第3章线性方程组的数值解法《计算方法与实习》第3章线性方程组的数值解法《计算方法与实习》其中｜a1｜＞｜c1｜＞0｜ak｜≥｜bk｜+｜ck｜,bkck≠0,k=2,3,…,n-1｜an｜＞｜bn｜＞0则三对角矩阵A的各阶主子式都不等于0,也即A为非奇异。用数学归纳法证明:令A的k阶主子式为Δk,Δ2=a1a2-b2c1≠0其中111kkkkkcaaba第3章线性方程组的数值解法《计算方法与实习》因为11111111kkkkkkkkkkkkbcaabacaaacb第3章线性方程组的数值解法《计算方法与实习》所以方程式(3―26)右端的k-1阶行列式满足假设的条件,由此可得Δk≠0,即矩阵A的各阶主子式都不等于0。由于实三对角线性方程组的系数矩阵A为非奇异,则有唯一的一组解。下面来求解。从方程组(3―25)的第一个方程解得111211111111,rcxxaarcuvaa令(3―27)1112xuvx(3―28)第3章线性方程组的数值解法《计算方法与实习》将式(3―28)代入(3―25)式的第二个方程解出x22122232122122122222122122223,rubcxxavbavbrubcuvavbavbxuvx(3―29)令则第3章线性方程组的数值解法《计算方法与实习》再将(3―29)式代入(3―25)式的第三个方程解出x3,一般有xk=uk-vkxk+1,k=1,2,…,n-1(3―30)其中111kkkkkkkkkkkkrubuavbcvaubk=2,3,…,n-1(3―31)第3章线性方程组的数值解法《计算方法与实习》当k=n时,因为bnxn-1+anxn=rn又xn-1=un-1-vn-1xn于是11nn