迭代法一般格式 一般来说，迭代格式可表示为 +1)=p(因，-1，，)，0，A,0)，k=0,1,2,, 其中o)=p0(A,),或者o)直接给出.这里pk就称为迭代函数 ⊙若Pk都是线性的，则称为线性迭代法，否则为非线性迭代法 ⊙若存在正整数(，当k≥时，P与k无关，则称为定常迭代法，否则是非定常的 O对于定常迭代，有P=p+1=…,此时x+1)只与因，x-1),,k-+)有关。 若+)只与因有关，则称为单步迭代，否则就称为多步迭代 本讲主要关注基于矩阵分裂的单步线性迭代方法（简称矩阵分裂迭代法） http://math.ecmu.edu.cn/-jypan 11/109
迭代法一般格式 一般来说, 迭代格式可表示为 x (k+1) = φk x (k) , x (k−1) , . . . , x (1) , x (0) , A, b , k = 0, 1, 2, . . . , 其中 x (0) = φ0(A, b), 或者 x (0) 直接给出. 这里 φk 就称为迭代函数. 若 φk 都是线性的, 则称为线性迭代法, 否则为非线性迭代法 若存在正整数 ℓ, 当 k ≥ ℓ 时, φk 与 k 无关, 则称为定常迭代法, 否则是非定常的 对于定常迭代, 有 φℓ = φℓ+1 = · · · ≜ φ, 此时 x (k+1) 只与 x (k) , x (k−1) , . . . , x (k−ℓ+1) 有关. 若 x (k+1) 只与 x (k) 有关, 则称为单步迭代, 否则就称为多步迭代. 本讲主要关注基于矩阵分裂的单步线性迭代方法 (简称矩阵分裂迭代法) http://math.ecnu.edu.cn/~jypan 11/109
3-1-2 矩阵分裂与迭代法 定义（矩阵分裂Matrix splitting) 设A∈Rnxn非奇异，称 A=M-N 为A的一个矩阵分裂，其中M非奇异. 原方程组等价于Mx=Nx+b.于是我们就可以构造迭代格式 xk+1)=M1Nz因+M1beGx因+g k=0,1, 其中G=1N称为该迭代格式的迭代矩阵。 迭代矩阵对算法的收敛性和收敛速度起着决定性作用 http://math.ecmu.edu.cn/-jypan 12/109
312 矩阵分裂与迭代法 定义 (矩阵分裂 Matrix splitting) 设 A ∈ R n×n 非奇异, 称 A = M − N 为 A 的一个矩阵分裂, 其中 M 非奇异. 原方程组等价于 Mx = Nx + b. 于是我们就可以构造迭代格式 x (k+1) = M−1Nx(k) + M−1 b ≜ Gx(k) + g , k = 0, 1, . . . , 其中 G = M−1N 称为该迭代格式的迭代矩阵. 迭代矩阵对算法的收敛性和收敛速度起着决定性作用. http://math.ecnu.edu.cn/~jypan 12/109
3-1-3 经典迭代法 将矩阵A分裂为 A=D-L-U 其中D为A的对角线部分，-L和一U分别为A的严格下三角和严格上三角部分. a11 0 a12· 22 D ,L= 021 an-1.n anl an,n-1 0 本小节介绍的经典迭代法包括：Jacobi,,G-S,SOR,SSOR,AOR,SAOR http://math.ecmu.edu.cn/-jypan 13/109
313 经典迭代法 将矩阵 A 分裂为 A = D − L − U , 其中 D 为 A 的对角线部分, −L 和 −U 分别为 A 的严格下三角和严格上三角部分. D = a11 a22 . . . ann , L = − 0 a21 . . . . . . . . . . . . an1 · · · an,n−1 0 , U = − 0 a12 · · · a1n . . . . . . . . . . . . an−1,n 0 . 本小节介绍的经典迭代法包括: Jacobi, G-S, SOR, SSOR, AOR, SAOR http://math.ecnu.edu.cn/~jypan 13/109
Jacobi迭代法 )取M=D,N=L+U,则可得Jacobi迭代法 xk+)=D(L+U0x肉+D-1b k=0,1,2,.. 迭代矩阵： G=D1(L+0 分器卖"-（三时2 http://math.ecmu.edu.cn/-jypan 14/109
Jacobi 迭代法 取 M = D, N = L + U, 则可得 Jacobi 迭代法 x (k+1) = D −1 (L + U)x (k) + D −1 b , k = 0, 1, 2, . . . . 迭代矩阵: GJ = D −1 (L + U) 分量形式: x (k+1) i = 1 aii bi − Xn j=1,j̸=i aijx (k) j , i = 1, 2, . . . , n. http://math.ecnu.edu.cn/~jypan 14/109
算法1求解线性方程组的Jacobi迭代法 1: Choose an initial guess (0) 2:while not converge do 3: for i=1 to n do 4 (k+1) 5: end for 6:end while 由于Jacobi迭代中+)的更新顺序与i无关，因此非常适合并行计算. http://math.ecmu.edu.cn/-jypan 15/109
算法 1 求解线性方程组的 Jacobi 迭代法 1: Choose an initial guess x (0) 2: while not converge do 3: for i = 1 to n do 4: x (k+1) i = bi − Pn j=1,j̸=i aijx (k) j ! . aii 5: end for 6: end while 由于 Jacobi 迭代中 x (k+1) i 的更新顺序与 i 无关, 因此非常适合并行计算. http://math.ecnu.edu.cn/~jypan 15/109