研究生数值分析 直接三角分解法

§4 直接三角分解法 一、教学设计1．教学内容：Doolittle 分解法、Crout 分解法，紧凑格式的Doolittle 分解法、部分选主元的Doolittle 分解法。

2．重点难点：紧凑格式的Doolittle 分解法、部分选主元的Doolittle 分解法。

3．教学目标：了解直接三角分解法的基本思想，掌握基本三角分解法及其各种变形。

4．教学方法：讲授与讨论。

二、教学过程在上节中我们用矩阵初等变换来分析Gauss 消去法，得到了重要的矩阵LU 分解定理（定理 3.1，3.2）。

由此我们将得到Gauss 消去法的变形：直接三角分解法。

直接三角分解法的基本想法是，一旦实现了矩阵A 的LU 分解，那么求解方程组b x =A 的问题就等价于求解两个三角形方程组 （1）b y =L ，求y ； （2）y x =U ，求x 。

而这两个三角形方程组的求解是容易的。

下面我们先给出这两个三角形方程组的求解公式；然后研究在LU A =或LU PA =时，U L ,的元素与A 的元素之间的直接关系。

4－0 三角形线性方程组的解法 设⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=nn n n l l l l l l L21222111， 11121222n n nn u u u u u U u ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦则b y =L 为下三角形方程组，它的第i 个方程为),2,1(11,22111n i b y l y l y l y l y l ii ii i i i i i ij j ij ==++++=--=∑假定0≠ii l ，按n y y y ,,,21 的顺序解得：⎪⎪⎩⎪⎪⎨⎧=+-==∑-=),,3,2(/111111n i l b y l y l b y ii i i j j ij i上三角形方程组y x =U 的第i 个方程为),2,1(11,n i y x u x u x u x u in in i i i i ii nij j ij ==+++=++=∑假定0≠ii u ，按121,,,,x x x x n n -的顺序求解得：⎪⎪⎩⎪⎪⎨⎧--=+-==∑+=)1,2,,2,1(/1n n i u y x u x u y x ii i n i j j ij i nnn n4－1 基本的三角分解法设矩阵n n ij a A ⨯=)(的各阶顺序主子式均不为零，由定理3.1，A 有LU 分解如下⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡nn nrn n rn rrr r n rn ra a a a a a a a a a a a a a a a 2121222221111211 LU u u u u u u u u u u l l l l l l nn rn rrn r n r nrn n r r =⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡= 22221112112121211111比较等式两边的第1行上的相应元素，得U 的第1行元素：),,2,1(11n i a u i i == （4.4）比较等式两边的第1列上的相应元素（从第2开始），得L 的第1列元素：),,3,2(1111n i u a l i i ==（4.5） 比较等式两边的第2行上的相应元素（从第2开始），得i i i u u l a 21212+=故得U 的第2行元素：),,3,2(12122n i u l a u i i i =-=比较等式两边的第2列上的相应元素（从第3开始），得2222121i i i a u l u l =+，得L 的第2列元素：),,4,3(2212122n i u u l a l i i i =-=假设已求得U 的第1至1-r 行，L 的第1至1-r 列，比较等式两边的第r 行上的相应元素（从第r 开始），得rnrn n r r r n r n r r r r r r r r r r r r r rrrr r r r r r r r r a u u l u l u l a u u l u l u l a u u l u l u l =++++=++++=++++--+++--++--,11,22111,1,1,11,1,221,11,11,2211即),,1,(11n r r i a u u l riri r k ki rk +==+∑-=故得U 的第r 行元素：),,3,2;,,1,(11n r n r r i u l a u r k ki rk ri ri =+=-=∑-= （4.6）比较等式两边的第r 列上的相应元素（从第1+r 开始），得nrrr nr r r r n r n r n r r rr r r r r r r r r r r r r rr r r r r r r r r r r a u l u l u l u l a u l u l u l u l a u l u l u l u l =++++=++++=++++--++--+++++--+++,11,2211,2,2,11,222,211,2,1,1,11,122,111,1即),,2,1(,11n r r i a u l u l ir rr ir r k kr ik ++==+∑-=故得L 的第r 列元素：)1,,3,2;,,2,1(,11-=++=-=∑-=n r n r r i u u l a l rrr k krik ir ir （4.7）称由（4.4）－（4.7）式所表示的矩阵分解为Doolittle 分解。

实验六高斯列主元消去法和直接三角分解法（LU分解）一、实验名称：分别用高斯列主元消去法和直接三角分解法（LU分解）求方程组的解系数矩阵：10 7 8 7 常向量：107 5 6 5 88 6 10 9 67 5 9 10 7精确解为：（-60，102，-27，16）二、试验目的：分别用高斯列主元消去法和直接三角分解法（LU分解）求方程组的解，比较二者不同的特点。

三、算法描述：2、直接三角分解法（LU分解）四、源程序：1、高斯列主元消去法#include <stdio.h>void main(){float a[4][4]={{10,7,8,7},{7,5,6,5},{8,6,10,9},{7,5,9,10}}, y[4],c[4][4],x[4],d[4],m,b; int i,n,j,f;printf("请输入右端项:\n");for(i=0;i<=3;i++)scanf("%f",&y[i]);for(n=0;n<=2;n++){ m=a[n][n]; f=n;for(i=(n+1);i<=3;i++){if(m<a[i][n]){m=a[i][n]; f=i;}}if(f!=n){for(j=0;j<=3;j++){c[n][j]=a[n][j]; a[n][j]=a[f][j];a[f][j]=c[n][j];}d[n]=y[n]; y[n]=y[f]; y[f]=d[n];}for(i=(n+1);i<=3;i++){b=-a[i][n]/a[n][n];for(j=0;j<=3;j++)a[i][j]=a[n][j]*b+a[i][j];y[i]=y[n]*b+y[i];}}x[3]=y[3]/a[3][3];x[2]=(y[2]-a[2][3]*x[3])/a[2][2];x[1]=(y[1]-a[1][3]*x[3]-a[1][2]*x[2])/a[1][1];x[0]=(y[0]-a[0][3]*x[3]-a[0][2]*x[2]-a[0][1]*x[1])/a[0][0];printf("x1的值为%f\nx2的值为%f\nx3的值为%f\nx4的值为%f\n",x[0],x[1],x[2],x[3]);}2、直接三角分解法（LU分解）#include <stdio.h>void main (){float a[4][4]={{10,7,8,7},{7,5,6,5},{8,6,10,9},{7,5,9,10}},y[4], l[4][4],x[4],u[4][4],b[4]; int i,n,j;printf("请输入右端项:");for(i=0;i<=2;i++)scanf ("%f",&b[i]);for (i=0;i<=3;i++){ u[0][i]=a[0][i]；l[i][0]=a[i][0]/u[0][0];}for (n=1;n<=2;n++){for(j=0;j<=(3-n);j++){u[n][n+j]=a[n][n+j];for (i=0;i<n;i++)u[n][n+j]=u[n][n+j]-l[n+j][i]*u[i][n]; }if (n=1){l[2][1]=(a[2][1]-l[2][0]*u[0][1])/u[1][1]; l[3][1]=(a[3][1]-l[3][0]*u[0][1])/u[1][1]; } else if (n=2){l[3][2]=(float)(a[3][2]-l[3][0]*u[0][2]-l[3][1]*u[1][2])/u[2][2]; } }for (n=0;n<=3;n++){y[n]=b[n];for (i=0;i<n;i++)y[n]=y[n]-l[n][i]*y[i]; }for (n=3;n>=0;n--){x[n]=y[n];for (i=3;i>n;i--)x[n]=(x[n]-u[n][i]*x[i]);x[n]=x[n]/u[n][n]; }for(i=0;i<=3;i++)printf("x%d的的值为:%f\n",i+1,x[i]); }五、输出结果1、高斯列主元消去法（1）请输入右端项：10 8 6 7X1的值为-59.999584X1的值为101.999306X1的值为-26.999817X1的值为15.999890(2)请输入右端项：5 6 7 8X1的值为-98.999306X1的值为163.998840X1的值为-40.999695X1的值为24.999817六、对算法的理解和改进改变右端项会对结果产生明显的影响,高斯列主元消去法仅考虑依次按列选取主元素,然后按行使之变到主元位置,再进行消去运算,消元结果冲掉A,计算解X冲掉常数项b，则在计算过程中由于右端项的不同解必然不同。