数值分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第四章方程组的直接解法,4.2,直接三角分解法,4.2.3,平方根法,4.2.1,一般矩阵的直接三角分解法,4.2.2,三对角方程组的追赶法,1,4.2,直接三角分解法,4.2.1,一般矩阵的直接三角分解法,本节讨论矩阵,A,的三角分解法的直接计算以及直接利用,A,的三角分解式来求解方程组。,1.,不选主元的三角分解法,设,A=LU,，记 其中,L,为单位下三角阵，,U,为上三角阵。我们可直接给出,L,和,U,的元素的计算公式。,由,A,的第,1,行和第,1,列可计算出,U,的第,1,行和,L,的第,1,列，即,（,4.2.1,）,（,4.2.2,）,如果,U,的第,1,至,k-1,列和,L,的第,1,至,k-1,列已经算出，则由,2,可得,U,的第,k,行元素,同理，由,u,kj,=a,kj,-,j=k,k+1,n,。（,4.2.3,）,a,kj,=,i=k+1,k+2,n,可得,L,的第,k,列元素,交替使用（,4.2.3,）和（,4.2.4,），就能逐次计算出,U,（按行）和,L,（按列）的全部元素，而且可以把它们存放在矩阵,A,对应的位置上（,L,的对角线元素不必存放）。这就完成了,A,的,LU,分解。,l,ik,=(a,ik,-)/u,kk,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=y,，只要琢次,3,用向后回代的方法即可求得,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,方法,。,例,4.5,用,LU,分解法求解,解 由（,4.2.1,）,-,（,4.2.4,）计算可得,由（,4.2.5,）计算得,由（,4.2.6,）计算得,5,2.,列选主元的三角分解法,设从,A=A,（,1,）开始已完成,k-1,步分解计算，,U,的元素（按行）和,L,的元素（按列）存放在,A,的位置，得到,该矩阵与顺序,Gauss,消去法中得到的,A,（,k,）是不同的，这种存储方式的形式称为,紧凑形式。,6,当,i=k,时，,s,i,对应于（,4.2.3,）中的,u,kk,，它可能不宜在（,4.2.4,）作除法。当,i=k+1,k=2,.n,，,s,i,对应于（,4.2.4,）中的分子。记,现做第,k,行计算，令,交换的第,i,行与第行的位置，但每个位置上仍用原记号。然后仍按（,4.2.3,）计算，算出,U,的第,k,行。的计算可用,这就算出了,L,的第,k,行。,以上分解过程经过,n-1,步，可得,PA=LU,，因为,b,也参加换行计算，所以在其位置上得到,Pb,。最后再分两步求解方程组,LUx=Pb,，即求解,Ly=Pb,和,Ux=y,。,例,4.6,用列选主元的三角分解法解,由此知,由于,s,2,=5/30,i=1,，,2,，,n,。由此推出,d,vi,0,，,i=1,，,2,，,n,。记,15,令 ，则有由分解式 的唯一性可得（,4.2.3,）分解式的唯一性。定理得证。,称（,4.2.13,）式为矩阵,A,的,Cholesky,分解。利用,A,的,Cholesky,分解式来求解方程组,Ax=b,的方法称为,Cholesky,方法或平方根法，这是因为计算过程含开方运算。,设,A=,（,a,ij,），,由式（,4.2.13,）可得,16,这样，可以从,j=1,直到,j=n,逐列算出,L,的元素,再求解下三角方程组,Ly=b,和上三角方程组,L,T,x=y,。计算公式为,按逐列计算,L,的元素的计算步骤,设第,1,列至第,j-1,列已经计算得到,则有,（,4.2.15,）,（,4.2.14,）,17,解 不难验证系数矩阵是对称正定的，按（,4.2.14,）和（,4.2.15,）依次计算得,例,4.8,用平方根法求解,由（,4.2.14,）可得 由此推出 ，,所以平方根法的中间量 得以控制。不必选主元。,平方根法的原理基于矩阵的,LU,分解,所以它也是,Gauss,消去法的变形,.,但由于利用了矩阵正定的性质,减少了计算量。平方根法的乘除法运算次数为,(n,3,+9n,2,+2)/6,加减法次数为,(n,3,+6n,2,-7n)/6,。另外还有,n,次开方运算，其所含乘除法和加减法次数可分别看成,n,的常数倍。平方根需,n,3,/6,次乘除法，与,Gauss,消去法相比减少了一半,。,18,则可避免开方根运算，称为改进的平方根法。它即适合于求接对称正定方程组，也适合于,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,）用分解式，即,19,解,Ly=b,得,y=(6,1,-1),T,。解,L,T,x=D,-1,y,得,x=(2,1,-1),T,。,其中,j=1,时，求和部分为零。这样求解方程组,Ax=b,化为求解,Ly=b,和,L,T,x=D,-1,y.,对于例,4.8,给定的方程组，用改进的平方根法有,20,