3.2.2_矩阵的doolittle分解

矩阵的Doolittle递归分解算法及符号程序设计
智东杰;智慧来
【期刊名称】《智能系统学报》
【年(卷),期】2007(2)1
【摘要】将矩阵An×n的Doolittle分解推广到Am×n上,并在常规的迭代算法上加以创新,给出了递归的分解算法.在实现算法的过程中,对数据进行了巧妙处理,使中间数据及最终计算结果都具有分数形式,提高了结果的精确度,而且更符合人们阅读的习惯.经过运行测试,算法设计合理,程序运行高效准确.程序是对MathSoft公司的交互式的数学文字软件Mathcad的矩阵分解的数值计算扩充到符号运算.
【总页数】4页(P90-93)
【作者】智东杰;智慧来
【作者单位】河南理工大学,计算机学院,河南,焦作,454150;西华大学,能源与环境学院,四川,成都,610039
【正文语种】中文
【中图分类】TP311.1
【相关文献】
1.方程组系数矩阵的递归分块分解算法的设计实现 [J], 汪先明;孙希平
2.矩阵Doolittle分解的快速算法 [J], 吴光文;黄乡生;胡文龙
3.矩阵的Crout递归分解算法及程序设计 [J], 智慧来;张礼达
4.矩阵的LU并行递归分解算法的设计研究 [J], 黄丽嫦
5.一种采用Householder变换递归实现的复矩阵QR分解算法 [J], 胡冰新;李宁;吕俊
因版权原因，仅展示原文概要，查看原文内容请购买。

Doolittle分解方法是一种用于解决线性方程组的数值方法，它可以将一个矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积，从而可以方便地求解线性方程组。

在本文中，我们将介绍Doolittle分解方法的原理和实现过程，并用编程语言实现该方法来解方程组。

一、Doolittle分解方法原理1.1 Doolittle分解方法是一种LU分解的特例，它将一个矩阵A分解为一个下三角矩阵L和一个上三角矩阵U的乘积，即A=LU。

其中，L 的主对角线元素全为1，U的主对角线以上的元素全为0。

这样的分解可以方便地求解线性方程组Ax=b，其中b是一个已知的列向量。

1.2 Doolittle分解方法的具体实现过程是通过高斯消元法来实现的。

将矩阵A分解为一个下三角矩阵L和一个上三角矩阵U，然后通过回代法求解线性方程组Ax=b。

具体来说，我们首先将矩阵A分解为L 和U，然后用L和U的乘积代替原来的矩阵A，将原来的线性方程组Ax=b变为LUx=b，然后通过两次回代法求解线性方程组Ly=b和Ux=y，最终得到线性方程组的解x。

1.3 Doolittle分解方法的优点是可以方便地求解多个方程组，因为一旦矩阵A被分解为L和U，就可以通过多次回代法来求解不同的线性方程组，而不需要重新分解矩阵A。

1.4 Doolittle分解方法的缺点是需要对原始的矩阵A进行分解，这需要一定的计算量，特别是对于比较大的矩阵来说。

Doolittle分解方法在实际应用中往往需要结合其他数值方法来提高求解线性方程组的效率。

二、Doolittle分解方法的实现过程2.1 我们需要定义一个函数来实现Doolittle分解。

该函数的输入是一个矩阵A，输出是矩阵A的下三角矩阵L和上三角矩阵U。

2.2 接下来，我们需要通过高斯消元法来实现Doolittle分解。

具体来说，我们首先对矩阵A进行行变换和列变换，使得矩阵A的主对角线元素非零，然后逐步消去矩阵A的非主对角线元素，得到下三角矩阵L和上三角矩阵U。

矩阵分解的Matlab指令大全矩阵分解的Matlab指令大全(2011-09-03 10:37:08)[转]矩阵分解是指根据一定的原理用某种算法将一个矩阵分解成若干个矩阵的乘积。

常见的矩阵分解有可逆方阵的三角（LU）分解、任意满秩矩阵的正交三角（QR）分解、对称正定矩阵的Cholesky分解，以及任意方阵的Schur分解、Hessenberg分解、EVD分解、SVD分解、GMD分解等。

(1) 可逆方阵的LU分解矩阵的LU分解就是将一个矩阵表示为一个交换下三角矩阵和一个上三角矩阵的乘积形式。

线性代数中已经证明，只要方阵A是非奇异的（即可逆的），LU分解总是可以进行的。

当L为单位下三角矩阵而U为上三角矩阵时，此三角分解称为杜利特(Doolittle)分解。

当L为下三角矩阵而U为单位上三角矩阵时，此三角分解称为克劳特(Crout)分解。

显然，如果存在，矩阵的三角分解不是唯一的。

（PS：方阵A可唯一地分解为A=LDU(其中L，U分别为单位下，上三角矩阵，D为对角矩阵)的充分必要条件为A的前n-1个顺序主子式都不为0。

特别：对n阶对称正定矩阵，存在一个非奇异下三角矩阵L，使得A=LL'成立。

）MATLAB提供的lu函数用于对矩阵进行LU分解，其调用格式为：[L,U]=lu(X)：产生一个上三角阵U和一个变换形式的下三角阵L(行交换)，使之满足X=LU。

注意，这里的矩阵X必须是方阵。

[L,U,P]=lu(X)：产生一个上三角阵U和一个下三角阵L以及一个置换矩阵P，使之满足PX=LU。

当然矩阵X同样必须是方阵。

(2) 满秩矩阵的QR分解对矩阵X进行QR分解，就是把X分解为一个正交矩阵Q和一个上三角矩阵R的乘积形式。

QR分解只能对方阵进行。

MATLAB的函数qr可用于对矩阵进行QR分解，其调用格式为：[Q,R]=qr(X)：产生一个一个正交矩阵Q和一个上三角矩阵R，使之满足X=QR。

[Q,R,E]=qr(X)：产生一个一个正交矩阵Q、一个上三角矩阵R以及一个置换矩阵E，使之满足XE=QR。

选主元的doolittle分解法
选主元的doolittle分解法是一种矩阵分解算法，用于将一个矩阵分解成一个下三角矩阵L和一个上三角矩阵U的乘积，其中L的对角线元素为1。

此算法的主要步骤如下：
1.选择矩阵A的最大元素作为主元素并交换它所在的行和列，使主元素落在第一个位置。

2.用高斯消元法将主元素所在的列下方的元素置零，得到一个新的矩阵A'。

3.对矩阵A'进行LU分解，得到下三角矩阵L'和上三角矩阵U'。

4.重新排列L'和U'的行和列，以使主元素回到原来的位置。

5.重复上述步骤，直到所有的元素都已经被选为主元素并完成LU分解。

选主元的doolittle分解法可以避免在LU分解过程中因为某些元素过小而导致算法出现退化、不稳定的问题，从而提高求解线性方程组的精度和稳定性。

doolittle三角分解法的相关原理及概念Doolittle三角分解法是一种常用的数值分析方法，用于解决线性方程组的求解问题。

三角分解法以源自Lanczos二次投影算法的Doolittle分解法为代表，是一种迭代计算最小二乘解的有效方法，其原理在于利用变换，将具有给定系数矩阵的线性方程组转化为一组更简单的三角形方程组。

Doolittle三角分解法包括四个步骤：首先，通过算法将给定的矩阵进行分解，获得两个三角矩阵；其次，通过求解上半三角矩阵来求解未知系数的近似解；然后，使用上半三角矩阵求解出的近似解和下半三角矩阵求解未知系数矩阵；最后，使用求解出的未知系数来求解待定系数矩阵。

Doolittle三角分解法的优势在于其复杂度较低，且有较快的计算速度，能够很好的解决大规模的线性方程组的求解问题。

通常情况下，Doolittle三角分解法的计算复杂度为O(n3)，而传统Gauss消元法的复杂度为O(n2)，可以看出，Doolittle三角分解法的计算速度的较高。

另外，其精度较高，能够得到更准确的结果。

Doolittle三角分解法可以更好地解决大规模的线性方程组，而在解决小型线性方程组时，通常会使用精度更高的Gauss消元法。

对于规模较大的线性方程组，可以使用改良的Doolittle三角分解法来提高运算的准确度，改进的Doolittle三角分解法能够更好地解决线性方程组的求解问题，可以通过给定不同的改进步骤来提高算法的准确度。

总之，Doolittle三角分解法是一种简单、有效且精确的方法，能够有效地解决大规模的线性方程组的求解问题，其应用非常广泛，被应用在数值分析、优化和机器学习等方面。

同时，Doolittle三角分解法也可以作为其他线性方程组求解算法的基础，为实际应用中的求解提供了可靠的解决方案。

doolittle分解公式
Doolittle分解是一种矩阵分解方法，可以将一个矩阵分解为
一个下三角矩阵L和一个上三角矩阵U的乘积。

这个分解可以用来求解线性方程组、计算矩阵的行列式和逆矩阵等。

下面是Doolittle分解的公式：
设A是一个n×n的矩阵，它的Doolittle分解为A=LU，其中L 是一个下三角矩阵，U是一个上三角矩阵。

则有：
U(i,j) = A(i,j) - ∑(k=1)^(i-1) L(i,k)U(k,j) (1≤j≤n, i≤j)
L(i,j) = (A(i,j) - ∑(k=1)^(j-1) L(i,k)U(k,j))/U(j,j) (1≤i≤n, i<j)
其中，U(i,j)和L(i,j)分别表示U矩阵和L矩阵的第i行第j 列元素。

Doolittle分解的求解过程如下：
1. 首先，将矩阵A中第1行第1列元素赋值给U(1,1)，将
L(1,1)赋值为1。

2. 对于第1行，计算U(1,j) (2≤j≤n) 的值，然后根据公式(1)计算出L(i,1) (2≤i≤n) 的值。

3. 对于第1列，计算L(i,1) (2≤i≤n) 的值，然后根据公式(2)计算出U(1,j) (2≤j≤n) 的值。

4. 按照此方式，依次计算出U和L矩阵中的所有元素。

5. 最终得到的L和U矩阵即为A的Doolittle分解。

Doolittle分解的优点是计算简单，但它只适用于矩阵A的所有主元都非零的情况。

如果矩阵A存在主元为零的情况，则需要使用其他方法进行矩阵分解。

矩阵数值分析实验报告专业信息与计算科学班级学号姓名指导教师Doolittle 分解法一、实验目的在Gauss 消元法中,对于n 阶方程组,应用消去发经过n-1步消元之后,得到一个与Ax=b 等价的代数线性方程组)1()1(--=n n b x A ,而且)1(-n A 为一个上三角矩阵.所以我们想是否能把矩阵A 分解成一个下三角阵与一个上三角阵的乘积 A=LR,其中L 为下三角阵,R 为上三角阵.就变成了两个三角形方程组⎩⎨⎧==yRx b Ly , 的求解问题。

二、算法思想Setp1：利用for 循环求出r[k][j]=a[k][j]-∑-=1k 1p ]kp [r ]kp [l ，l[ik]=（a[ik]-∑-=1k 1p ]ip [r ]ip [l ）/r[k][k]。

Step2：y[i]=b[i]-∑-=1i 1k ]k [y ]ik [l ,得出x[i]=(y[i]-∑+=n1i k ]k [x ]ik [r )/r[i][i].三、程序代码#include <stdio.h>#include <stdlib.h>#define N 10 //矩阵大小范围float getmx(float a[N][N], float x[N], int i, int n) {float mx = 0;int r;for(r=i+1; r<n; r++){mx += a[i][r] * x[r];}return mx;}float getmy(float a[N][N], float y[N], int i, int n) {float my = 0;int r;for(r=0; r<n; r++){if(i != r) my += a[i][r] * y[r];}return my;}float getx(float a[N][N], float b[N], float x[N], int i, int n) {float result;if(i==n-1) //计算最后一个x的值result = (float)(b[i]/a[n-1][n-1]);else //计算其他x值（对于公式中的求和部分，需要调用getmx()函数） result = (float)((b[i]-getmx(a,x,i,n))/a[i][i]);return result;}float gety(float a[N][N], float b[N], float y[N], int i, int n) {float result;if(i==0) //计算第一个y的值result = float(b[i]/a[i][i]);else //计算其他y值（对于公式中的求和部分，需要调用getmy()函数） result = float((b[i]-getmy(a,y,i,n))/a[i][i]);return result;}void main(){float l[N][N]={0}; //定义L矩阵float u[N][N]={0}; //定义U矩阵float y[N]={0}; //定义数组Yfloat x[N]={0}; //定义数组Xfloat a[N][N]={{0},{0},{0}}; //定义系数矩阵float b[N]={0}; //定义右端项float sum=0;int i,j,k;int n=0;int flag=1;//用户手工输入矩阵while(flag){printf("请输入系数矩阵的大小：");scanf("%d", &n);if(n>N){printf("矩阵过大！\n");continue;}flag=0;}printf("请输入系数矩阵值：\n");for(i=0; i<n; i++){for(j=0; j<n; j++){printf("a[%d][%d]: ", i, j);scanf("%f", &a[i][j]);}}printf("请输入右端项数组：\n");for(i=0; i<n; i++){printf("b[%d]: ", i);scanf("%f", &b[i]);}/*显示原始矩阵*/printf("原始矩阵：\n");for(i=0; i<n; i++){for(j=0; j<n; j++)printf("%0.3f ",a[i][j]);printf("\n");}printf("\n\n");/*初始化矩阵l*/for(i=0; i<n; i++){for(j=0; j<n; j++){if(i==j) l[i][j] = 1;}}/*开始LU分解*//*第一步：对矩阵U的首行进行计算*/for(i=0; i<n; i++){u[0][i] = (float)(a[0][i]/l[0][0]); }/*第二步：逐步进行LU分解*/for(i=0; i<n; i++){/*对“L列”进行计算*/for(j=i+1; j<n; j++){for(k=0,sum=0; k<n; k++){if(k != i) sum += l[j][k]*u[k][i];}l[j][i] = (float)((a[j][i]-sum)/u[i][i]); }/*对“U行”进行计算*/for(j=i+1; j<n; j++){for(k=0,sum=0; k<n; k++){if(k != i+1) sum += l[i+1][k]*u[k][j]; }u[i+1][j] = (float)((a[i+1][j]-sum));}}/*输出矩阵l*/printf("矩阵L：\n");for(i=0; i<n; i++){for(j=0; j<n; j++){printf("%0.3f ", l[i][j]);}printf("\n");}/*输出矩阵u*/printf("\n矩阵U：\n");for(i=0; i<n; i++){for(j=0; j<n; j++){printf("%0.3f ", u[i][j]);}printf("\n");}/*回代方式计算数组Y*/for(i=0; i<n; i++){y[i] = gety(l,b,y,i,n);}/*显示数组Y*/printf("\n\n数组Y：\n");for(i=0; i<n; i++){printf("y%d = %0.3f\n", i+1,y[i]); }/*回代方式计算数组X*/for(i=n-1; i>=0; i--){x[i] = getx(u,y,x,i,n);}/*显示数组X*/printf("\n\n数组X：\n");for(i=0; i<n; i++){printf("x%d = %0.3f\n", i+1,x[i]); }}四、运行结果五、参考文献[1]刑志栋，矩阵数值分析，陕西：陕西科学技术出版社， 2005。

Doolittle 分解法的构造过程把矩阵A 写成下列两个矩阵相乘的形式：A=LU ，其中L 为下三角矩阵，U 为上三角矩阵。

这样我们可以把线性方程组 Ax=b 写成Ax=（LU)x=L( U x ) = b令 U x=y,则原线性方程组 Ax=b 化为两个简单的三角方程组：Ux=y 和Ly=b 。

于是可首先 求解Ly=b 得到向量y ，然后求解 Ux=y,从而求解线性方程组 Ax=b 的目的。

设矩阵A 的Doolittle 分解为： 为求出矩阵L 和U ，根据矩阵乘法规则，有用公式写法有：()ijjj j ii i i i j i a u u u l l l l U L j =⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=⋅-000,,0,1,,,,213211 LU u u u u u u l l l a a a a a a a a a A nn n n n n nn n n n n =⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛= 222112112121212222111211111{}∑∑==⋅=⋅=nk j i k kjik kj ik ij u l u l a 1,min 1ni u l u l u l a nj u u l u l u l a i nk k k ik k ik i jj nk k kj k kj k j ,,2,,2,11111111111111111111 =⋅=⋅=⋅===⋅=⋅=⋅=∑∑∑∑====iii k ki jkn k i k ki jkki jkji iji k kj ik nk ik kj ikkj kij u l u lu lu la u u l u lu la j i ji ⋅+⋅=⋅=⋅=+⋅=⋅=⋅=≤∑∑∑∑∑∑-===-===111111111,有时当于是可得Doolittle 分解公式：u 1j =a 1j j=1,2,…,n l i1=a i1 / u 11 i=2,3,…,n2）Doolittle 分解法算法1.输入变量个数n 、系数矩阵A 、常数项b2 如果a 11=0,则输出“LU 分解失败”提示并终止，否则a j1 ⇐ a j1/a 11 （j=2,…,n ）ij u u l a l ij u l a u iii k ki jk ji i k kjik ij ij ji >⋅-=≥⋅-=∑∑-=-= /)(1111注：因为 L 和U 中的三角零元素都不必存储，L 的对角元素也因为都是1没有必要再记录在程序中。