《方程组直接三角分解法》由会员分享,可在线阅读,更多相关《方程组直接三角分解法(20页珍藏版)》请在金锄头文库上搜索。
1、第四章方程组的直接解法4.2 直接三角分解法直接三角分解法 4.2.3 平方根法平方根法4.2.1 一般矩阵的直接三角分解法一般矩阵的直接三角分解法4.2.2 三对角方程组的追赶法三对角方程组的追赶法第四章方程组的直接解法4.2 直接三角分解法直接三角分解法4.2.1 一般矩阵的直接三角分解法一般矩阵的直接三角分解法本节讨论矩阵本节讨论矩阵A的三角分解法的直接计算以及直接利用的三角分解法的直接计算以及直接利用A的三角分的三角分解式来求解方程组。解式来求解方程组。1.不选主元的三角分解法不选主元的三角分解法设设A=LU,记,记 其中其中L为单位下三角阵,为单位下三角阵,U为上三角阵。我们可直接给
2、出为上三角阵。我们可直接给出L和和U的元素的计算公式。的元素的计算公式。由由A的第的第1行和第行和第1列可计算出列可计算出U的第的第1行和行和L的第的第1列,即列,即(4.2.1)(4.2.2)如果如果U的第的第1至至k-1列和列和L的第的第1至至k-1列已经算出,则由列已经算出,则由第四章方程组的直接解法可得可得U的第的第k行元素行元素同理,由同理,由 ukj =akj - ,j =k,k+1, ,n。 (4.2.3) akj = ,i=k+1,k+2,n, 可得可得L的第的第k列元素列元素交替使用(交替使用(4.2.3)和)和 (4.2.4),就能逐次计算出),就能逐次计算出U(按行)和(
3、按行)和L(按列)的全部元素,而且可以把它们存放在矩阵(按列)的全部元素,而且可以把它们存放在矩阵A对应的位置上对应的位置上(L的对角线元素不必存放)。这就完成了的对角线元素不必存放)。这就完成了A的的LU分解。分解。 lik=(aik - )/ ukk ,i =k+1,k+2, ,n。 由(由(4.2.1)- (4.2.4)求得)求得L和和U后,解方程组后,解方程组Ax=b接化接为求接化接为求解解LUx=b,若记,若记Ux=y,则有,则有Ly=b。于是可分两部解方程组。于是可分两部解方程组LUx=b,只要琢次向前代入的方法即可求得只要琢次向前代入的方法即可求得y。第二步求解。第二步求解Ux=
4、y,只要琢次,只要琢次第四章方程组的直接解法用向后回代的方法即可求得用向后回代的方法即可求得x。设。设x=(x1 ,x2, xn) T, y=(y1, y2, yn) T,b= (b1 ,b2, bn) T, 则有计算公式则有计算公式(4.2.5)(4.2.6) 以上解方程组的计算与顺序以上解方程组的计算与顺序Gauss消去法相当。如果有一系列方消去法相当。如果有一系列方程组,其系数距阵都是相同的,右端向量程组,其系数距阵都是相同的,右端向量b不同,则只须进行一次不同,则只须进行一次LU分解计算。上述解方程的方法称为分解计算。上述解方程的方法称为LU分解法分解法,也称,也称Doolittle方
5、法方法。 例例4.5 用用LU分解法求解分解法求解第四章方程组的直接解法 解解 由(由(4.2.1)-( 4.2.4 )计算可得)计算可得由(由(4.2.5)计算得)计算得由(由(4.2.6)计算得)计算得 第四章方程组的直接解法2.列选主元的三角分解法列选主元的三角分解法 设从设从A=A (1)开始已完成)开始已完成k-1步分解计算,步分解计算,U的元素(按行)的元素(按行)和和L的元素(按列)存放在的元素(按列)存放在A的位置,得到的位置,得到该矩阵与顺序该矩阵与顺序Gauss消去法中得到的消去法中得到的A(k)是不同的,这种存储)是不同的,这种存储方式的形式称为方式的形式称为紧凑形式。紧
6、凑形式。第四章方程组的直接解法当当i=k时,时, si对应于(对应于(4.2.3)中的)中的ukk,它可能不宜在(,它可能不宜在(4.2.4)作除法。)作除法。当当i=k+1,k=2,.n, si对应于(对应于(4.2.4)中的分子。记)中的分子。记 现做第现做第k行计算,令行计算,令交换的第交换的第i行与第行的位置,但每个位置上仍用原记号。行与第行的位置,但每个位置上仍用原记号。然后仍按(然后仍按(4.2.3)计算,算出)计算,算出U的第的第k行。行。的计算可用的计算可用 这就算出了这就算出了L的第的第k行。行。以上分解过程经过以上分解过程经过n-1步,可得步,可得PA=LU,因为,因为b也
7、参加换行计算,也参加换行计算,所以在其位置上得到所以在其位置上得到Pb。最后再分两步求解方程组。最后再分两步求解方程组LUx=Pb,即求解,即求解Ly=Pb和和Ux=y。第四章方程组的直接解法例例4.6 用列选主元的三角分解法解用列选主元的三角分解法解由此知由此知由于由于s2=5/30 ,i=1,2,n 。 由此推出由此推出dvi 0, i=1,2,n 。记。记第四章方程组的直接解法 令令 ,则有,则有由分解式由分解式 的唯一性可得(的唯一性可得(4.2.3)分解式的唯一性。定理得证。)分解式的唯一性。定理得证。 称(称(4.2.13)式为矩阵)式为矩阵A的的Cholesky分解。利用分解。利
8、用A的的Cholesky分解式来求分解式来求解方程组解方程组Ax=b的方法称为的方法称为Cholesky方法或平方根法,这是因为计算过程含方法或平方根法,这是因为计算过程含开方运算。开方运算。 设设A=(aij),),由式(由式(4.2.13)可得)可得第四章方程组的直接解法 这样,可以从这样,可以从j=1直到直到j=n逐列算出逐列算出L的元素的元素,再求解下三角方程组再求解下三角方程组Ly=b和和上三角方程组上三角方程组 L T x=y 。计算公式为。计算公式为按逐列计算按逐列计算L的元素的计算步骤的元素的计算步骤,设第设第1列至第列至第j-1列已经计算得到列已经计算得到,则有则有(4.2.
9、15)(4.2.14)第四章方程组的直接解法 解解 不难验证系数矩阵是对称正定的,按(不难验证系数矩阵是对称正定的,按(4.2.14)和()和(4.2.15)依)依次计算得次计算得 例例4.8 用平方根法求解用平方根法求解 由(由(4.2.14)可得)可得 由此推出由此推出 ,所以平方根法的中间量所以平方根法的中间量 得以控制。不必选主元。得以控制。不必选主元。 平方根法的原理基于矩阵的平方根法的原理基于矩阵的LU分解分解,所以它也是所以它也是Gauss消去法的变形消去法的变形.但由于利用了矩阵正定的性质但由于利用了矩阵正定的性质,减少了计算量。平方根法的乘除法运算次减少了计算量。平方根法的乘
10、除法运算次数为数为(n3+9n2+2)/6,加减法次数为加减法次数为(n3+6n2-7n)/6 。另外还有。另外还有n次开方运算,次开方运算,其所含乘除法和加减法次数可分别看成其所含乘除法和加减法次数可分别看成n的常数倍。平方根需的常数倍。平方根需n3 /6次乘除次乘除法,与法,与Gauss消去法相比减少了一半消去法相比减少了一半。第四章方程组的直接解法则可避免开方根运算,称为改进的平方根法。则可避免开方根运算,称为改进的平方根法。 它即适合于求接对称正定方程它即适合于求接对称正定方程组,也适合于组,也适合于A求解对称且其顺序主子式全不为零的方程组。分解式的计算求解对称且其顺序主子式全不为零的方程组。分解式的计算公式为公式为(j=1,2,n)解解Ly=(6,-0.5,1.25)T ,得,得y=(3,0.5,-1) T ,再解,再解L T x=y可可以得到以得到x=(2,1,-1) T 。 如果对矩阵采(如果对矩阵采(4.2.12)用分解式,)用分解式, 即即第四章方程组的直接解法解解Ly=b得得y=(6,1,-1)T。解。解LTx=D-1y得得x=(2,1,-1)T。 其中其中j=1时,求和部分为零。这样求解方程组时,求和部分为零。这样求解方程组Ax=b化为求解化为求解Ly=b和和LTx=D-1y.对于例对于例4.8给定的方程组,用改进的平方根法有给定的方程组,用改进的平方根法有