图像矩阵的Doolittle LU分解与MATLAB处理实例

矩阵Doolittle LU分解与MATLAB处理实例 1.矩阵Doolittle LU分解方法原理

LU分解在本质上是高斯消元法的一种表达形式。实质上是将A通过初等行变换变成一个上三角矩阵，其变换矩阵就是一个单位下三角矩阵。这正是所谓的杜尔里特算法（Doolittle algorithm）：从下至上地对矩阵A做初等行变换，将对角线左下方的元素变成零，然后再证明这些行变换的效果等同于左乘一系列单位下三角矩阵，这一系列单位下三角矩阵的乘积的逆就是L矩阵，它也是一个单位下三角矩阵。这类算法的复杂度一般在(三分之二的n三次方) 左右。 i）Doolittle分解

对于非奇异矩阵（任n阶顺序主子式不全为0）的方阵A，都可以进行Doolittle分解，得到A=LU，其中L为单位下三角矩阵，U为上三角矩阵；这里的Doolittle分解实际就是Gauss变换；

（ii）Crout分解

对于非奇异矩阵（任n阶顺序主子式不全为0）的方阵A，都可以进行Crout分解，得到A=LU，其中L为下三角矩阵，U为单位上三角矩阵； （iii）列主元三角分解

对于非奇异矩阵的方阵A，采用列主元三角分解，得到PA=LU，其中P为一个置换矩阵，L，U与Doolittle分解的规定相同； （iv）全主元三角分解

对于非奇异矩阵的方阵A，采用全主元三角分解，得到PAQ=LU，其中P，Q为置换矩阵，L，U与Doolittle分解的规定相同； （v）直接三角分解

对于非奇异矩阵的方阵A，利用直接三角分解推导得到的公式（Doolittle分解公式或者Crout分解公式），可以进行递归操作，以便于计算机编程实现； （vi）“追赶法”

追赶法是针对带状矩阵（尤其是三对角矩阵）这一大稀疏矩阵的特殊结构，得出的一种保带性分解的公式推导，实质结果也是LU分解；因为大稀疏矩阵在工程领域应用较多，所以这部分内容需要特别掌握。

（vii）Cholesky分解法（平方根法）和改进的平方根法

Cholesky分解法是是针对正定矩阵的分解，其结果是 A=LDLT=LD(1/2)D(1/2)LT=L1L1T。如何得到L1，实际也是给出了递归公式。

改进的平方根法是Cholesky分解的一种改进。为避免公式中开平方，得到的结果是A=LDLT=TLT， 同样给出了求T,L的公式。

2.Doolittle LU分解MATLAB处理实例

对于线性方程组AX = B，假设A的顺序主子式都不为零,则A可作LU 分解，即A = LU ，其中L 是单位下三角阵，U 是上三角阵

(1)

比较式(1)两侧，可以得到 (2)

先算出U 的第1行，在式(2)中令i=1，得到 u1j=a1j,i = 2,?,n (3) 接着在式(2)中令j=1,从而算出的L 第1列 li1= ai1/a11,i = 2,?,n (4) 若已算出U 的1至r ?1行元素，L 的1至r ?1列元素，可用式(5)先算出U 的第r 行元素

(5)

接着计算L 的第r 列

(6)

上述矩阵A的LU 分解计算步骤可按U1行L1列，U2行L2列，?，依次进行，如图2-1所示。

图2-1 ( Doolittle方法LU分解过程 )

其中Doolittle L U分解函数在MATLAB程序中代码如下： 创建Doolittle.m文件； % Doolittle.m

function [L,U]=Doolittle(A)

% 方阵A的Doolittle形式LU分解，即A=LU

% L为单位下三角阵，U为上三角阵，称为Doolittle分解 n=size(A,1); U=zeros(n); U(1,:)=A(1,:); L=eye(n);

L(2:n,1)=A(2:n,1)/U(1,1); for k=2:n

U(k,k:n)=A(k,k:n)-L(k,1:k-1)*U(1:k-1,k:n);

L(k+1:n,k)=(A(k+1:n,k)-L(k+1:n,1:k-1)*U(1:k-1,k))/U(k,k); end

figure(1);

imshow(L);title('L'); imwrite(L,'L.jpg','jpg'); figure(2);

imshow(U);title('U'); imwrite(U,'U.jpg','jpg');