7
5.2.2 LU decomposition
AφQ
LUφQ
where
LUA（可求L,U 出 的所有元
let
UφY
then
LYQ
Require O(2n2) arithmetic operation
Bas20i2s0/7o/3f0 other iterative methods
8
5.2.3 Tridiagonal system (TDMA)
A W WA SSA PPANNA EE
Q P
2020/7/30
5
5.2 直接法
5.2.1 Gauss elimination 5.2.2 LU decomposition 5.2.3 Tridiagonal system 5.2.4 Cyclic reduction
2020/7/30
6
5.2.1 Gauss Elimination
from forward elimination
By backward substitution, we have
Require O(n3/3) arithmetic operation
Backward substitution O(n2/2)
Pivoting
2020R/7/3a0rely used in CFD
elimination:
*
*
*
Gives upper bi-diagonal matrix. By backward substitution, we get
2020/7/30
*
9
5.2.3 Tridiagonal system:块三对角方程 组
A
i W
i1
A
i P
i
A
i E
i
1
Qi
eliminatio n :
• 计算模板(计算分子;解元SE)
2020/7/30
2
5.1 代数方程系统: 计算模板
2D 2阶 模板
2D 3阶 模板
3D 2阶 模板
2020/7/30
3
5.1 代数方程系统: 整体方程系统
• 流场中每一点都有一个方程(小组), 整个计算域就有一 个大型稀疏方程系统
AQ
(2)
A:稀疏方 ,其阵 结构依 的赖 排于 序。
迭代次数：
15
5.3.2 收敛性：收敛速度
AQ
AMN 要想收敛快，M要 A求 ,N： 0
2020/7/30
16
5.3.3 一些基本迭代方法 • Jacobi method:
k1 i
ik
Rik Aii
i 1
n
R ikQ i A ix jk j A ix jk j,i1,2,.n ..C,onverge slow
GMRES • 5.3.8 Multigrid methods
2020/7/30
12
5.3.1 基本概念
Matrix A is sparse
设n次迭代的近似解为 n, 不满足上述方程，带入上述方程后
有残量 n ：
迭代误差
迭代解的收敛： 0,or 0
实际计算中:
PA PQ
2020/7/30
P预处理矩阵，加速收 速敛 度
j 1
ji1
• Gauss-Seidel Method:
k1 i
ik
Rik Aii
i1
n
RikQi Aijxkj1 Aijxkj
j1
ji1
2 times as fast as Jacobi
• Successive Over-relaxation (SOR if w>1):
Useful for solving linear systems occurring in certain PDE’s
(五) 代数方程的求解
• 5.1 代数方程系统 • 5.2 直接法 • 5.3 主要迭代法 • 5.4 其他迭代方法
2020/7/30
1
5.1 代数方程系统
• 有限差分(体积)离散格式提供一个网格点(单元 ）的代数方程, 以线性代数方程为例：
A PP A l l Q P
l
(1)
• P点和周围邻居点构成计算模板(比差分基架还 大）
k1 i
Hale Waihona Puke ikRik Aii
i1
n
RikQi Aijxkj1 Aijxkj
j1
ji
For positive definite matrix, the SOR converges for 02.
2020/7/30
17
GS 和SOR的一般形式
AX b ,
A LU
GS :
LX p 1 b UX p
A
i* P
A
i P
A
i W
A A i * 1 i 1
P
E
and
Q
* i
Q
i
A
i W
A Q i * 1 *
P
i1
back substituti on :
i
A
i* P
1
Q
* i
A
i E
i
1
2020/7/30
10
5.2.3 Tridiagonal system (cont)
13
5.3.2 收敛性
• Consider an iterative scheme for a linear system M称为迭代矩阵
上两式相减 或
这里 n
2020/7/30
14
5.3.2 收敛性（续）
设特征向量完备，则
2020/7/30
趋于零的充要条件：k 1 1 is the largest eigenvalue
在结构网格上 从的 西排 南序 角： 开始 向， 东向 ，北 向
2020/7/30
4
5.1 代数方程系统: 系数矩阵的存储
• 只存储非零的对角元 素
• 2维5点格式： 5 Ni *Nj
• 3维7点格式： 7 Ni *Nj*Nk
• Al,l-Nj=W • Al,l-1 =S • Al,l =P • Al,l+1 =N • Al,l+Nj=E
X p 1 L 1 b UX p
SOR :
X p 1 L 1 b UX
收敛条件：
p ( 1 ) X p
a i a ij , i j i
• 计算量 O (n) • 周期三对角方程组 • 三对角方程组的并行化解法
– cyclic reduction, recursive doubling, SPP…
• 五对角方程组（类似三对角）
2020/7/30
11
5.3 迭代法
• 5.3.1 基本概念 • 5.3.2 收敛速度 • 5.3.3 一些基本方法 • 5.3.4 不完全LU 分解方法 • 5.3.5 ADI 和其他分裂方法 • 5.3.6 Conjugate gradient methods • 5.3.7 Bi-conjugate gradients,CGSTAB,