文章目录
一、三对角方程组追赶法
A
x
=
f
Ax=f
Ax=f的系数矩阵呈对三角形
A
=
(
b
1
c
1
a
2
b
2
c
2
⋱
⋱
⋱
a
n
−
1
b
n
−
1
c
n
−
1
a
n
b
n
)
A= \begin{pmatrix} b_{1} & c_{1} \\ a_{2} & b_{2} & c_2\\ & \ddots & \ddots & \ddots\\ &&a_{n-1} & b_{n-1} &c_{n-1}\\ &&&a_{n}&b_{n}\\ \end{pmatrix}
A=⎝⎜⎜⎜⎜⎛b1a2c1b2⋱c2⋱an−1⋱bn−1ancn−1bn⎠⎟⎟⎟⎟⎞
A
=
L
U
A=LU
A=LU具有以下形式
L
=
(
1
l
2
1
l
3
⋱
⋱
1
l
n
1
)
L= \begin{pmatrix} 1 \\ l_{2} & 1 \\ &l_3& \ddots\\ && \ddots& 1\\ &&& l_n & 1\\ \end{pmatrix}
L=⎝⎜⎜⎜⎜⎛1l21l3⋱⋱1ln1⎠⎟⎟⎟⎟⎞
U = ( u 1 d 1 u 2 d 2 ⋱ ⋱ u n − 1 d n − 1 u n ) U= \begin{pmatrix} u_1&d_1 \\ & u_{2} & d_2 \\ &&\ddots& \ddots\\ &&&u_{n-1}& d_{n-1}\\ &&&& u_n\\ \end{pmatrix} U=⎝⎜⎜⎜⎜⎛u1d1u2d2⋱⋱un−1dn−1un⎠⎟⎟⎟⎟⎞
计算公式如下：
d
i
=
c
i
d_i=c_i
di=ci
u
1
=
b
1
u_1=b_1
u1=b1
l
i
=
a
i
/
u
i
−
1
l_i=a_i/u_{i-1}
li=ai/ui−1
u
i
=
b
i
−
l
i
c
i
−
1
u_i=b_i-l_ic_{i-1}
ui=bi−lici−1
计算次序是
u
1
,
l
2
,
u
2
,
l
3
,
u
3
,
⋯
,
l
n
,
u
n
u_1,l_2,u_2,l_3,u_3,\cdots,l_n,u_n
u1,l2,u2,l3,u3,⋯,ln,un
原方程组转化为
L
y
=
f
Ly=f
Ly=f
U
x
=
y
Ux=y
Ux=y
即可得解
求解三对角方程组前提条件是A是严格对角占优阵或对称正定
二、对称正定的Cholesky分解法
若A对称正定，则存在一个实的下三角阵L，使
A
=
L
L
T
A=LL^T
A=LLT
这种分解是唯一的
L
=
(
l
11
l
21
l
22
⋯
⋱
l
n
1
l
n
2
⋯
l
n
n
)
L= \begin{pmatrix} l_{11} \\ l_{21} & l_{22} \\ \cdots & & \ddots\\ l_{n1}&l_{n2}& \cdots&l_{nn}\\ \end{pmatrix}
L=⎝⎜⎜⎛l11l21⋯ln1l22ln2⋱⋯lnn⎠⎟⎟⎞
逐列计算L的元素，即
l
11
,
l
21
,
⋯
,
l
n
1
,
l
22
,
⋯
,
l
n
2
,
⋯
,
l
n
n
l_{11},l_{21},\cdots,l_{n1},l_{22},\cdots,l_{n2},\cdots,l_{nn}
l11,l21,⋯,ln1,l22,⋯,ln2,⋯,lnn
原方程组转化为
L
y
=
b
Ly=b
Ly=b
L
T
x
L^Tx
LTx=y
PS:Matlab有专用的函数来计算
L
L
L
L=chol(A)
为了避免相对耗时的平方根运算，将A分解为
A
=
L
D
L
T
A=LDL^T
A=LDLT
其中
L
=
(
1
l
21
1
⋯
⋱
l
n
1
l
n
2
⋯
1
)
L= \begin{pmatrix} 1 \\ l_{21} &1\\ \cdots & & \ddots\\ l_{n1}&l_{n2}& \cdots&1\\ \end{pmatrix}
L=⎝⎜⎜⎛1l21⋯ln11ln2⋱⋯1⎠⎟⎟⎞
D
=
(
d
1
d
2
⋱
d
n
)
D= \begin{pmatrix} d_1 \\ \ &d_2\\ & & \ddots\\ && &d_n\\ \end{pmatrix}
D=⎝⎜⎜⎛d1 d2⋱dn⎠⎟⎟⎞
称为改进的平方根法