文档介绍：LU分解法的与特殊方程组的解法
假定我们能把矩阵A写成下列两个矩阵相乘的形式:A=LU
其中L为下三角矩阵,U为上三角矩阵。这样我们可以把
线性方程组 Ax=b写成
Ax=(LU)x=L( U x ) = b
Ly=b
令 U x=y,则原线性方程组 Ax=b
Ux=y
于是可首先求解向量y使 Ly=b
然后求解 Ux=y,从而求解线性方程组 Ax=b的目的.
LU分解法的基本思想
内容:LU分解.
关键词: :将系数矩阵A转变成等价两个矩阵L和U的乘积,其中L和U分别是下三角和上三角矩阵,而且要求U的对角元素都是1. :由于可以把L和U两个矩阵压缩到一个数组中,.
由LU=(Doolittle分解):
1
l21 1
l31 l32 1
…
…
…
ln1 ln2 … lnn-1 1
u11 u12 u13 … u1n
u22 u23 … u2n
…
un-1n u(n-1)n
unn
=
…
…
…
…
a
ann
L U
n1
an3 …
a11 a12 a13 … a1n
a21 a22 a23 … a2n
a31 a32 a33 … a3n
an2
A
…
…
…
第j个分量
第i个分量
根据矩阵乘法及相等的定义,有
得公式 u1j=a1j j=1,2,…,n
li1=ai1 / u11 i=2,3,…,n
在计算机程序中常常用这种方法解线性代数方程组。
它的优点是存储量很省。L和U中的三角零元素都不
必存储,就是U的对角元素也因为都是1没有必要再
记录在程序中,这样只用一个n阶方阵就可以把L和
U贮存起来。即:下三角(包括对角元)存储L各元
素而上三角存储U的元素。
再考察公式S会发现A中任一元素aij只在计算lij(j<=i)
和uij(j>i)中用到一次以后就不再出现了,因而完全
可以利用原始数组A的单元,一个个逐次贮存L或U中
的相应元素,即:
a11 a12 a13 … a1n u11 u12 u13 … u1n
a21 a22 a23 … a2n l21 u22 u23 … u2n
a31 a32 a33 … a3n l31 l32 u33 … u3n
an1 an2 an3 … ann ln1 ln2 ln3 … unn
…
…
…
...
…
…
…
…
...
...
(1)
(3)
(5)
(2n-1)
(2) (4) (6) (2n)
采用LU分解有如下特点:
(1)LU分解与右端向量无关。先分解,后
回代。一般说来,分解的运算次数正比于n
回代求解正比与n。求遇到多次回代时,分
解的工作不必重新做。这样节省计算时间。
(2)分解按步进行,前边分解得到的信息
为后边所用。
(3)[A]阵的存储空间可利用,节省存储。
3
2
特殊方程组的解法