Crout方法解线性方程组的结构化程序设计

2022-04-09 来源：客趣旅游网

第20卷第2期三明高等专科学校学报2003年6月

Vol120No12JOURNALOFSANMINGCOLLEGEJun12003

刘墨德(三明高等专科学校计算机科学系,福建三明　365004)

摘　要:Crout方法通过对系数矩阵作三角分解能解出线性方程组的准确解,是解线性方程组的重要方法,文章给出了完整的算法设计,并编写了通用的结构化程序。

关键词:下三角阵;单位上三角阵;LV分解;回代;结构化

中图分类号:TP301.6　　文献标识码:A　　文章编号:1671-1343(2003)02-0062-05

1　引理

[1]

a11　　a12…a1nl11　　0　…　0

,必存在n阶下三角阵L=

l21　　l22　…　0

对任意n阶方阵A=

a21　　a22…a2n

……

an1　　an2…ann1　　v12　…　v1n

……

ln1　　ln2　…lnn

及n阶单位上三角阵V=

0　　　1　…　v2n

……0　　　0　…　　1[1][2]

,使得A=LV。

2　Crout方法解线性方程组的算法

(b1,b2,…bn)

给定线性方程组AX=b,其中系数矩阵A=(aij)

,用Crout方法解AX=b的算法如下:

(1)对A作LV分解

n×n

非奇异,X=(x1,x2,…,xn)

,b=

由A=LV及矩阵的乘法原理可得:

lij=aij-6likvkj,j=1,2,…,i

j-1

k=1

vij=(aij-6likvkj)/lii,j=i+1,i+2,…,nk=1

i-1

　i=1,2,…,n

(2)解两个三角型方程组

由A=LV及AX=b可得L(VX)=b,令Y=(y1,y2,…,yn)

=VX,则LY=b,于是求解

复杂的AX=b就被化为求解简单的下三角型方程组LY=b及单位上三角型方程组VX=Y。

a)先解下三角型方程组LY=b

收稿日期:2003204201

作者简介:刘墨德(1963-),男,福建南安人,三明高等专科学校计算机科学系讲师。

l11y1=b1

由LY=b得l21y1+l22y2=b2

b1/l11,i=1

,　∴yi=

(bi-6likyk)/lii,i=2,3,…,n

k=1i-1

…………………

ln1y1+ln2y2+…+lnnyn=bn

b)再解单位上三角型方程组VX=Y

x1+v12x2+…+v1nxn=y1

　　x2+…+v2nxn=y2

由VX=Y得　　　……………,利用回代解法可得方程组AX=b的

　　　　xn-1+vn21nxn=yn-1

　　　　　　xn=yn

yn,i=n解为xi=

yi-

k=i+1

6vikxk,i=n-1,…,2,1

3　算法流程[3]

　(1)LV分解过程P1　　　　　　　　　　　　(2)解三角型方程组过程P2

　　　(3)主程序

4　结构化程序设计

programcrout(input,output);

const　n=4;

type　id=1..n;ar1=array[id]　of　real;ar2=array[id,id]ofreal;var　b,x:ar1;a:ar2;i,j:id;

procedure　p1(a:ar2;var　l,v:ar2);

　var　i,j,k:id;　begin　　l[1,1]:=a[1,1];　　for　j:=2　to　n　do　begin　l[j,1]:=a[j,1];v[1,j]:=a[1,j]/l[1,1]　end;　　for　i:=2　to　n-1　do　　　begin　　　　for　j:=2　to　i　do　　　　　begin　　　　　　l[i,j]:=a[i,j];fork:=1toj-1dol[i,j]:=l[i,j]-l[i,k]3v[k,j]　　　　　end;　　　　for　j:=i+1　to　n　do　　　　　begin　　　　　　v[i,j]:=a[i,j];fork:=1toi-1dov[i,j]:=v[i,j]-l[i,k]3v[k,j];　　　　　　v[i,j]:=v[i,j]/l[i,i]　　　　　end;　　　end　　for　j:=2　to　n　do　　　begin　l[n,j]:=a[n,j];fork:=1toj-1dol[n,j]:=l[n,j]-l[n,k]3v[k,j]end　end;

procedure　p2(a:ar2;b:ar1;var　x:ar1);　var　i,j:id;y:ar1;l,v:ar2;　begin　　p1(a,l,v);y[1]:=b[1]/l[1,1];　　for　i:=　2　to　n　do　　　begin

　　　y[i]:=b[i];fork:=1toi-1doy[i]:=y[i]-l[i,k]3y[k];y[i]:=y[i]/l[i,i]　　　end;　　x[n]:=y[n];　　for　i:=　n-1　downto　1　do　　　begin　x[i]:=y[i];for　k:=i+1　to　n　do　x[i]:=x[i]-v[i,k]3x[k]　end;　end;

begin(3主程序3)

(输入系数矩阵A‘　writeln‘:);

　for　i:=1　to　n　do　　begin　for　j:=1　to　n　do　read(a[i,j]);readln　end;

(输入列矩阵b‘　write‘:);64

　for　i:=1　to　n　do　read(b[i]);writeln;

(输出结果‘(方程组的解为‘　p2(a,b,x);writeln‘:);writeln‘:);

(x　for　i:=1　to　n　do　write‘‘,i:1‘,=‘,x[i]:10:6‘,‘)end.

5　符号说明表

标识符数学符号

nnaAbbxXyYlLvViijjkk

类型

整实实实实实实整整整

个数1n2nnnn2n2111

入输入输入输出出

输出

作用

方程组的阶数系数矩阵列矩阵存放方程组的解

存放下三角型方程组的解n阶下三角阵n阶单位上三角阵行下标列下标

循环控制变量

6　计算复杂性分析[4]

(1)算法中使用了3个2维数组A,L,V及3个1维数组X,Y,b,数组共用3n2+3n个单

元,因为3n2+3n<3n2+3n2=6n2,故算法所需空间为O(n2)。

(2)LV分解过程中使用了3重循环,故算法所需计算时间至多为O(n3)。

(3)由于当今计算机的内存可以达到超大规模存贮,因此当n按常规意义取值时,算法所需空间为O(n2)及算法所需计算时间为O(n3)对计算机执行效率的影响极小。

7　计算实例

　5x1　　-x2　　　-x3　　　-x4=-4

用Crout方法求方程组　-x1　+10x2　　　-x3　　　-x4=12　-x1　　-x2　　+5x3　　　-x4=8

　　的解。

　-x1　　-x2　　　-x3　　+10x4=34

(准确解为x1=1,x2=2,x3=3,x4=4)

理论分析[5]:由于系数矩阵A非奇异(A=2112≠0),所以方程组有唯一解。计算机执行结果:输入系数矩阵A:　5-1-1-1-1-1

-1-1-110

　10-1-1

-1

输入列矩阵b:-4　12　8　34输出结果:

方程组的解为:x1=　1.000000x2=　2.000000x3=　3.000000x4=　4.000001

8　讨论

(1)从理论求解角度讲,Crout方法求出的解是准确解,但在计算机执行过程中由于数值

运算存在一定的舍入误差,所以计算机上求出的解是高精度近似解,在单精度机上准确解与近似解的误差不会超过10-6[1]。

(2)∵A=LV,∴|A|=|L||V|=l11l22…lnn,这表明Crout方法还具有求n阶行列式|A|的功能[5],计算|A|的编程如下:deta:=1;for　i:=1　to　n　do　deta:=deta3l[i,i];通过计算机运行上述计算实例得系数行列式|A|=deta=2112。(3)2维数组L,V及1维数组X,Y均可压缩,但这需要很高的编程技巧,所编出的程序清晰性及可读性很差,这不符合现代程序设计标准。此外,从现代计算机大容量的存贮规模及高速度的运算功能来看,节省下来的2n2+2n个存贮单元对计算机执行效率所构成的影响可以忽略不计,因此为了程序清晰性及可读性不应该去压缩数组[2][6]。参考文献:

[1]施吉林,刘淑珍,陈桂芝,等.计算机数值方法[M].北京:高等教育出版社,2000.[2]华中理工大学数学教研室.算法语言・计算方法[M].北京:高等教育出版社,1999.[3]谭浩强.田淑清.PASCAL程序设计[M].北京:高等教育出版社,1995.[4]王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2000.[5]北京大学数学力学系.高等代数[M].北京:高等教育出版社,1998.[6]麦中凡.程序设计技术[M].北京:高等教育出版社,1996.

[责任编辑:叶　普]

TheStructuredProgrammingofCrout’s

MethodSolvingLinearEquation

LIUMo2de

(DepartmentofComputerScience,SanmingCollege,Sanming365004,China)

Abstract:Crout’smethodbymeansofcoefficientmatrixdotriangleresolutionsolubleaccuracyansweroflinearequation.Itisanimportantsolutionofsolvinglinearequation.ThisarticlesuppliesacompletealgorithmdesignofCrout’smethodandwritinggeneralpurposestructuredprogramming.

Keywords:lowertriangularmartrix;unitupperriangularmartrix;LVresolution;loopcallbyvalue;structural

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

Crout方法解线性方程组的结构化程序设计