当前位置：文档之家 › 选主元的Doolittle分解法程序

选主元的Doolittle分解法程序

  • 格式：docx
  • 大小：12.86 KB
  • 文档页数：4

选主元的Doolittle分解法程序
北航人
说明：本人编程时使用DEV C++运行。
可以根据系数矩阵维数修改程序第三行的n值。
# include
# include
# define n 4
main ()
{ int i,j,k,row,v;
int M[n];
float m,r,max0,max1;
float a[n][n],b[n],s[n],l[n][n],u[n][n],x[n],y[n];
a[0][0]=1,a[0][1]=8,a[0][2]=2,a[0][3]=3;
a[1][0]=-6,a[1][1]=-3,a[1][2]=8,a[1][3]=1;
a[2][0]=2,a[2][1]=4,a[2][2]=4,a[2][3]=2;
a[3][0]=10,a[3][1]=5,a[3][2]=-5,a[3][3]=6;
b[0]=12,b[1]=40,b[2]=-50,b[3]=80;
for(k=0;k{ for(i=k;i{ m=0;
if(k-1>=0)
{ for(t=0;tm=m+l[i][t]*u[t][k];
}
s[i]=a[i][k]-m;
}
max0=fabs(s[k]);
for(i=k;i{ if(fabs(s[i])>max0)
{ max0=fabs(s[i]);
row=i;}
}
max1=s[k];
M[k]=row;
if(row!=k)
{ if(k-1>=0)
{ for(t=0;t<=k-1;t++)
{ r=l[k][t];
l[k][t]=l[row][t];
l[row][t]=r;
}
}
for(t=k;t{ r=a[k][t];
a[k][t]=a[row][t];
a[row][t]=r;
}
r=s[k];
s[k]=s[row];
s[row]=r;
}
u[k][k]=s[k];
if(k{ for(j=k+1;j{ m=0;
if(k-1>=0)
{ for(t=0;tm=m+l[k][t]*u[t][j];
}
u[k][j]=a[k][j]-m;
}
for(i=k+1;il[i][k]=s[i]/u[k][k];
}
}
for(k=0;k{ v=M[0];
m=b[k];
b[k]=b[t];
b[t]=m;
}
y[0]=b[0];
for(i=1;i{ m=0;
for(t=0;t<=i-1;t++)
m=m+l[i][t]*y[t];
y[i]=b[i]-m;
}
x[n-1]=y[n-1]/u[n-1][n-1];
for(i=n-2;i>=0;i--)
{ m=0;
for(t=i+1;tm=m+u[i][t]*x[t];
x[i]=(y[i]-m)/u[i][i];
}
for(i=0;iprintf("%.4f\n",x[i]);

}

合集下载

Gauss列主元素消去法实验

Gauss列主元素消去法实验

Lab06．Gauss 列主元素消去法实验【实验目的和要求】1．使学生深入理解并掌握Gauss 消去法和Gauss 列主元素消去法步骤； 2．通过对Gauss 消去法和Gauss 列主元素消去法的程序设计，以提高学生程序设计的能力；3．对具体问题，分别用Gauss 消去法和Gauss 列主元素消去法求解。

通过对结果的分析比较，使学生感受Gauss 列主元素消去法优点。

【实验内容】1．根据Matlab 语言特点，描述Gauss 消去法和Gauss 列主元素消去法步骤。

2．编写用不选主元的直接三角分解法解线性方程组Ax=b 的M 文件。

要求输出Ax=b 中矩阵A 及向量b ，A=LU 分解的L 与U ，det A 及解向量x 。

3．编写用Gauss 列主元素消去法解线性方程组Ax=b 的M 文件。

要求输出Ax=b 中矩阵A 及向量b 、PA=LU 分解的L 与U 、det A 及解向量x ，交换顺序。

4．给定方程组(1) ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--11134.981.4987.023.116.427.199.103.601.3321x x x(2) ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡----15900001.582012151********.23107104321x x x x 先用编写的程序计算，再将(1)中的系数3.01改为3.00，0.987改为0.990；将(2)中的系数2.099999改为2.1，5.900001改为9.5,再用Gauss 列主元素消去法解，并将两次计算的结果进行比较。

【实验仪器与软件】1．CPU 主频在1GHz 以上，内存在128Mb 以上的PC ；2．Matlab 6.0及以上版本。

实验讲评：实验成绩：评阅教师：200 年 月 日Lab06．Gauss 列主元素消去法实验第一题：1、算法描述：Ⅰ、Gauss 消去法由书上定理5可知 设Ax=b ，其中A ∈R^(n(1)如果()0(1,2,....,1)k kka k n ≠=-，则可通过高斯消去法将Ax=b 约化为等价的 角形线性方程组，且计算公式为：① 消元计算（k=1,2，….，n-1）()()(1)()()(1)()()/,1,...,,,,1,...,,,1,...,.k k ik ik kk k k k ij ij ik kj k k k iiik k m a a i k n a a m a i j k n b b m b i k n ++==+=-=+=-=+② 回带公式()()()()()1/,()/,1,...,2,1.n n n n nn ni i i i iii j ii j i x b a x ba x a i n =+==-=-∑（2）如果A 为非奇异矩阵，则可通过高斯消去法将方程组Ax=b 约化方程组为上三角矩阵以上消元和回代过程总的乘除法次数为332333nn nn +-≈，加减法次数为32353263nnn n+-≈以上过程就叫高斯消去法。

用直接三角分解法解线性方程组

用直接三角分解法解线性方程组


三角阵。等式左边是单位下三角阵，右边是上三角阵，要使等式
成则立L ， L只1 ,能U等于U单1，位即矩此阵三I。角于分是解L唯1一L1。
UU
1 1
I,
1 2 1
1 2 1
例7 解：
设 A 3 7
1
，试将A进行三角分解。
1 1 3
由高斯消去法得到
m21
3 1
3，m31
1 1
1
m 32
L1
1 1
0 0 1 2
例：
求
0 1 2
0 1 0
3 0 1
103的PLU分 解 。
解：用1，2， ，n的排列表示n阶置换阵P，其中排列的第i个元素
j，表示P的i行非零元素位于j列。则分解过程如下：
1 0 0 1 2
3 1 1 0 1
3 1 1 0
2 0
43
1 2
0 1 0
3 0 1
0 1 3
Ux j y j
Ly
j
bj
n1
k
n(n 1)
n2
n 次乘法
k 1
2
22
Ux j y j n k n(n 1) n2 n 次乘除法
k 1
2
22
即共需n 2 次乘除法运算。
n 2 次 乘 除 法
三角分解法的存放元素的方法：
以A (a ij )33 为例，
a11 A a21
1 mk1,k 1
k，
Lk1
1 mk1,k 1
k
mnk
1
mn,k
1
A ( L11 L21
L1 n1
)U
LU，1
a (1) 11
线性方程组的求解

线性方程组的求解

目录摘要 (1)一．用列主元消去法解方程组 (2)1．问题的提出 (2)2．问题的分析 (2)3．问题的解决 (3)二．编写一个列主元消去法求逆矩阵的程序 (4)1．问题的提出 (4)2．问题的分析 (4)3．问题的解决 (5)Ax (5)三．用LU分解法解方程组b1．问题的提出 (5)2．问题的分析 (5)3．问题的解决 (6)四．用改进平方根法解方程组 (7)1．问题的提出 (7)2．问题的分析 (7)3．问题的解决 (8)五．用追赶法解方程组 (9)1．问题的提出 (9)2．问题的分析 (9)3．问题的解决 (10)六．分别用雅可比迭代法与高斯-赛德尔迭代法解方程组 (11)1．问题的提出 (11)2．问题的分析 (11)3．问题的解决 (12)参考文献 (14)个人体会 (15)附录：程序代码 (16)摘要在科技研究和工程技术所提出的计算问题中，经常会遇到线性方程组的求解问题，这里主要是有关线性方程组的直接解法。

解线性方程组的直接法是用有限次运算求出线性方程组Ax=b 的解的方法。

线性方程组的直接法主要有Gauss消元法及其变形、LU(如Doolittle、Crout方法等)分解法和一些求解特殊线性方程组的方法（如追赶法、LDLT法等）。

这里主要有列主元消元法,LU分解法,改进的平方根法，追赶法和雅可比迭代，高斯—塞德尔迭代的构造过程及相应的程序。

线性方程的解法在数值计算中占有极重要的地位，因此，线性方程组的求解是数值分析课程中最基本的内容之一。

关键词：列主元消元法；LU分解；改进平方根法；追赶法；雅可比迭代；高斯—塞德尔迭代一．用列主元消去法解方程组：1．问题的提出：（1）⎪⎪⎩⎪⎪⎨⎧=-++--=+--=+-+=++4323231243432143214321421x x x x x x x x x x x x x x x （2）⎪⎪⎩⎪⎪⎨⎧=++--=++-=-+--=-+-434220332282432132143214321x x x x x x x x x x x x x x x2．问题的分析：列主元消去算法主要分为两个过程：消去过程和回代过程1． 消去过程对1,,2,1-=n k(1)选主元 找k i ∈}{,,n k ，⋯使)()(max k ik ni k ki k a ak ≤≤= (2)若0)(=k a k ik 则停止计算（detA=0）(3)若k i k ≠ 则换行()()k i k E E ↔ （4）消元对i =1,,1++n k)()(k kkk ik a a ik l =对1,,1++=n k j )()()1(k kjik k ij k ija l a a -=+ 2.回代过程（1）若0)(=n nn a 则停止计算（detA=0） (2) )()(1,n nnn n n a a n x +=（3）对1,,1 -=n i)(1)()(1,n iini j jn ij n n i a x a a i x ∑=+=+-3．问题的解决：（1）解：对于()b A |)1(=()b A |=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛------43141321************ 第1步选列主元为,3)1(31=a 31=i ，作变换()()31E E ↔，然后计算667.03221==l ， 333.03131==l ，333.03141-==-l再作变换()()(),414143131321212,,E E l E E E l E E E l E →-→-→-得到())2()2(|b A=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛------3533333.0667.2667.10333.2333.0333.10333.0333.0667.102113 第2步，对)2(A 选列主元为667.135)2(22==a ，22=i ，计算8.05432==l ， 142=l ， 再做变换32323)(E E l E →-，42424)(E E l E →-，得到()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-----=05/1333030015/3915/9003/13/13/502113)3()3(b A消去过程结束，回代计算得到解10214321===-=x x x x所以原方程组的解为TX )1,0,2,1(-=。

三角分解法

三角分解法

. . . . l21 1 . . = . . . . ... . . . . . an1 ... ann ln1 ... 1 ... . . . . . . unn
ai j =
min( i , j ) k =1
∑l
ik
uk j
ai j =
min( i , j )
一般采用列主元 对换, 将 i ,j 对换,对 j = i, i+1, …, n 有 一般采用列主元 ii a ji = ∑ l jk uki + l ji u k= k =1 法增强稳定性. 法增强稳定性.但注意 v i 1 b 也必须做相应的 l ji = ( a ji ∑ l jk uki ) / uii b 行交换. 行交换. k =1
=I
Upper-triangular
Lower-triangular With diagonal entries 1
注: L 为一般下三角阵而 U 为单位上三角阵的分解称为 单位上三角阵的分解称为 Crout 分解. 分解. ~~ 分解, 实际上只要考虑 A* 的 LU 分解,即A* = L U ,则 ~ ~ A= U * L* 即是 A 的 Crout 分解. 分解. =
(
)
n1 Step 6 Set l = 运算量为2 O(n3/6), 比普通 ann ∑ k =1 lnk ; , 比普通LU nn Step 7 Output ( lij for j = 1, …, i and i = 1, …, n );A = LDLT 分解少一半, 次开方. 分解少一半,但有 n 次开方.用
mn1
v A b
( 2) (2)
(1 (1 ( a11) a12) ... a11) n Step n 1: (2 ( v a22) ... a22) n Ln1Ln2 ... L1 A b = ... . . . (n ann)