§4迭代法的收敛性/ Convergence of Iterative methods x6+)=B()+f的收敛条件 (k+1) (k+1) 元*=(B(+f-(欧*+∫)=B(x6)一x)=B6) →c(=B‘e0→‖2‖4‖B|l+|≤.‖B|-l‖ 充分条件:B0ask→ 定义设:A=a (k) R ij/nxn 2 nxn lim Ak In( (k) k→)0 A是指 对所有1si,≤n成立
§4 迭代法的收敛性 /* Convergence of Iterative methods */ x k Bx k f 的收敛条件 = + ( +1) ( ) * ( 1) ( 1) e x x k k = − + + ( ) ( ) ( ) ( ) ( * ) ( *) k k k Bx f Bx f B x x Be = + − + = − = ( ) (0) e B e k k = || || || || || || ... || || || || ( ) ( 1) (0) e B e B e k k k − 充分条件: ||B|| < 1 B → k → k || || 0 as || || 0 e (k ) → 必要条件: k k e → 0 as k → B ( ) ？ 定义 设： ( ) , ( ) . ( ) n n n n k A aij n n Ak aij R = = Ak A k = → lim 是指 ij k ij k a = a → ( ) lim 对所有 1 i, j n 成立。 等价于对 任何算子范数有 || Ak − A|| → 0 as k →
84 Convergence of Iterative methods 定理设x=B+存在唯—解,则任意出发, 迭代x(+=Bx)+f收敛台Bk→>0 ‖B^x 证明:B→0分‖魏‖一0mX →>0 But hey, you don't seriously expect me to compute B* VZ whenever I want to check the convergence, do you? Rl 从任意出:诹裂形.1-6,则 )=B则a联→如位 台{x(k)}收敛
|| B x || → 0 k 对任意非零向量 x 成立 §4 Convergence of Iterative methods 定理 设 x Bx f = + 存在唯一解，则从任意 出发， (0) x 迭代 x Bx f k k = + ( +1) ( ) 收敛 → 0 k B 证明： Bk → 0 || Bk || → 0 0 || || || || max 0 → x B x k x “”：对任意非零向量 x 有 || || 0 || || || || k → k B x B x “”：取 则 i T x (0...1...0) ( ) = 0 第 i 位 bij (k ) → 0 B k x → 对任意非零向量 x 成立 从任意 出发， 记 ，则 (0) x * (0) (0) e x x = − 0 ( ) (0) e k = B k e → as k → { } (k ) x 收敛 But hey, you don’t seriously expect me to compute Bk whenever I want to check the convergence, do you?
84 Convergence of Iterative methods 定理p→0p(B)<1 证明:对A做 Jordan分解,有PAP= ,其中 x110 1,∑n=n,1为A的 eigen value D 则有 D PAPD= λ6 易证:‖4|l=‖ D PAPD1=mx(|+6)=p(4)+ lsis 是由‖x=(PD)x导出的算子范数。 所以只要取<E,就有‖A|b<p(4)+E
§4 Convergence of Iterative methods 定理 Bk → 0 ( B ) 0, 存在算子范数 || · || 使得 || A || (A) + 。 由 (B) < 1 可知存在算子范数|| · || 使得 || B || < 1。 || Bk || || B ||k → 0 as k → Bk → 0 迭代从任意向量出发收敛 Bk → 0 ( B ) < 1 证明：对 A 做 Jordan 分解，有 ，其中 ， ， i 为 A 的 eigen value。 令 ，则有 易证： 是由 导出的算子范数。 所以只要取 < ，就有|| A || < (A) + 。 = − r J J P AP ... 1 1 ni ni i i Ji = 1 1 0 = = r i ni n 1 = −1 2 1 n D = − − r r D P APD 1 1 1 1 = = + = + − − || || || || max(| | ) ( ) 1 1 1 1 A D P APD i A i r 1 1 || x || || (PD) x || v − =
84 Convergence of Iterative methods 定理(充分条件)若存在一个矩阵范数使得‖B=q<1 则送代收敛,且有下列误差估计 ①‖x*一x∥≤、qN (k)-x ② x“-x (k)1<q l≤ d-d 证明:④x*-x()=B(无-(-) =B(x*-x()+x()-x-) →‖*-x(6)|≤q(x*-x(6)‖+6)-x(1√ ②x6-x4=B(x-x2)=…=B(x-x) lx()-x(6‖≤q4=0-xo
§4 Convergence of Iterative methods 定理 （充分条件）若存在一个矩阵范数使得 || B || = q < 1, 则迭代收敛，且有下列误差估计： ① || || 1 || * || ( ) ( ) ( −1) − − − k k k x x q q x x ② || || 1 || * || ( ) (1) (0) x x q q x x k k − − − 证明： ① ( * ) * ( * ) ( ) ( ) ( 1) ( ) ( 1) − − = − + − − = − k k k k k B x x x x x x B x x || * || (|| * || || ||) ( ) ( ) ( ) ( −1) − − + − k k k k x x q x x x x ✓ ② ( ) ... ( ) ( ) ( 1) ( 1) ( 2) 1 (1) (0) x x B x x B x x k k k k k − = − = = − − − − − || || || || ( ) ( 1) 1 (1) (0) x x q x x k k k − − − −
84 Convergence of Iterative methods 定理(充分条件)若4为严格对角占优阵 /* strictly diagonally dominant matriⅸx*则解AX=b的 Jacob和 Gauss Seidel迭代均收敛。 证明:首先需要一个引理 Lemma 显然 若4为SDD阵,则de(4)≠0,且所有的a≠0。 我们需要对 Jacobi迭代和 Gauss-Seidel迭代分别 证明:任何一个孔|≥1都不可能是对应迭代阵的 特征根,即|-B|≠0。 Jaco hi 关于 Gauss-Seidel迭代的证明 与此类似(p73)。 另一种证明引理的方法利用 Gersgorin Disc Theorem(p.72) HW: D p.76#1
§4 Convergence of Iterative methods 定理 （充分条件）若A 为严格对角占优阵 /* strictly diagonally dominant matrix */ 则解 的Jacobi 和 Gauss - Seidel 迭代均收敛。 Ax b = 证明：首先需要一个引理 /* Lemma */ 若A 为SDD阵，则det(A) 0，且所有的 aii 0。 证明：若不然，即det(A) = 0，则 A 是奇异阵。 存在非零向量 x0 (x1 , x2 , xn ) T 使得 = 0. 0 Ax = 记 | | max | | 1 i i n xm x = = = n i m i i a x 1 0 = i m m mi i m | amm xm | ami xi | x | | a | 显然 我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别 证明：任何一个| | 1 都不可能是对应迭代阵的 特征根，即 | I − B | 0 。 Jacobi: BJ = −D−1 ( L + U ) | | | ( )| 1 I − B = I + D L+U − | ( )| | || | 1 1 = D D + L+U = D D + L+U − − aii 0 ij a ij a nn a a 11 如果 | | 1 则 j i ai i ai i ai j | | | | | | 是SDD阵 | I − B | 0 ✓ HW: p.76 #1 关于Gauss-Seidel迭代的证明 与此类似 (p.73)。 另一种证明引理的方法利用 Geršgorin Disc Theorem (p.72)
§5松弛法/ Relaxation Methods 换个角度看 Gauss- Seidel方法 x+=1-2 .y(k+1) ∑qnx1 j=i+1 (k+1) (k) x:+ 其中=b-4n-4-2qx I 相当于在x的基础上加个余项生成x4+ 下面令x“"=x“+0"“,希望通过进敢台的来 加速收敛,这就是松弛法/ Relaxation Methods"。 01(渐次超松弛法 / Successive Over- Relaxation methods *
§5 松弛法 /* Relaxation Methods */ 换个角度看Gauss - Seidel 方法： = + − = + + = − − n j i k i j j i j k i i j i i i k i b a x a x a x 1 ( ) 1 1 ( 1) ( 1) [ ] 1 ii k k i i a r x ( 1) ( ) + = + 其中ri (k+1) = 1 (渐次)超松弛法 /* Successive Over- Relaxation methods */
85 Relaxation Methods 写成矩阵形式: (k+1) (k) (1-)x)+2-∑qnx+∑ax”+b (k+1) 1-O)x+aDLe (k+1) Ux+b x t=(D+OL)[(1-Q)D-QU()+(D+al)ob 迭代阵 定理「设A可逆,且41≠0,松孢法从任意x出发对 某个ω收敛分p(H)<1 Oooooh come on! Its way too complicated to compute h and you can't expect me to get its spectral radius right! There’ s gotta be a short cut…
§5 Relaxation Methods 写成矩阵形式： i i k k i i k i a r x x ( 1) ( 1) ( ) + + = + < + = − + − − + j i i k i j j j i k i j j i i k i a x a x b a (1 )x [ ] ( ) ( 1) ( ) (1 ) [ ] ( 1) ( ) 1 ( 1) ( ) x x D Lx Ux b k k k k = − + − − + + − + x D L D U x D L b k k ( 1) 1 ( ) 1 ( ) [(1 ) ] ( ) + − − = + − − + + H f 松弛迭代阵 定理 设 A 可逆，且 aii 0，松弛法从任意 出发对 某个 收敛 ( H ) < 1。 (0) x Oooooh come on! It’s way too complicated to compute H , and you can’t expect me to get its spectral radius right! There’s gotta be a short cut …
85 Relaxation Methods 定理|(khm必要条件)设A可逆,且≠0,松抛法 从任意x出发收敛→0<<2。 证明:从Ho=(D+L)(1-0)D-aU出发 利用de(H)=∏λ,而且收敛|4|<1总成立 可知收敛→|det(Ha)<1 det((D+al= det(D+ol) det(1-0)D-0U)=(1-) I det(H。)=(1-) →|de(H)|=|1-c|<1→0<m<2
§5 Relaxation Methods 定理 （Kahan 必要条件）设 A 可逆，且 aii 0，松弛法 从任意 x (0) 出发收敛 0 < < 2 。 证明：从 H = (D + L) −1 [(1−)D − U] 出发 = = n i H i 1 利用 det( ) ，而且收敛 | i | < 1 总成立 可知收敛 | det(H) | < 1 = − = + + = n D L i ai i D L 1 1 1 det( ) 1 det(( ) ) = − − = − n i i i n D U a 1 det((1 ) ) (1 ) n det(H ) (1 ) = − | det(H) | = | 1 − | n < 1 0 < < 2
85 Relaxation Methods 定理( Ostrowski-Reich充分条件)若4对称正定,且有 0<0<2,则松弛法从任意x出发收敛。 Q: What factor determines the speed of convergence? 考察迭代x=Bx)+∫:设B有特征根λ1、…、An对 应n个线性无关的特征向量v1,…,vn则从任意出 发 0) x0-元*可表为v,…,v的线性组合,即 ∑a c(6)=B′2=∑arv A: The smaller p(B)is, the faster the iterations wil( seByarge, 对于SOR法,希望找o使得p(H2)最小
§5 Relaxation Methods 定理 （Ostrowski-Reich 充分条件）若A 对称正定，且有 0 < < 2，则松弛法从任意 x (0) 出发收敛。 Q: What factor determines the speed of convergence? 考察迭代 x Bx f k k = + ( +1) ( ) ：设 B 有特征根 1、…、 n 对 应 n 个线性无关的特征向量 。则从任意 出 发， 可表为 的线性组合，即 n , ... , 1 (0) x * (0) (0) e x x = − n , ... , 1 = = n i i i e 1 (0) = = = n i i k i i k k e B e 1 ( ) (0) ~ (0) [ (B)] e k A: The smaller ( B ) is, the faster the iterations will converge. 对于SOR法，希望找 使得 ( H ) 最小
85 Relaxation Methods 定理|若A为对称正定三对角阵,则p(Ba)=1(B1)P<1 且SOR的最佳松弛因子/ optimal choice of o for SOR method 为 1+y-(B∥2,此时p(H0)=a-1。 例:A 考虑送代格式x+=x()+o(Ax)-b) 问:①o取何值可使迭代收敛? ②a取何值时迭代收敛最快? 解:考察B=I+oA的特征根→1=1+m,42=1+30 ①收敛要求p(B)<1 2/3<m<0 ②p(B)=max{|1+ob,|1+3a|} 当@取何值时最小? 0=-1/2 HW:p.77#5#7 2/3-1/30
§5 Relaxation Methods 定理 若 A 为对称正定三对角阵，则 且SOR的最佳松弛因子 /* optimal choice of for SOR method */ 为 ，此时 。 ( ) [ ( )] 1 2 BG−S = BJ < 2 1 1 [ ( )] 2 BJ + − = (H ) = −1 例： = = 2 1 , 1 2 2 1 A b ，考虑迭代格式 ( ) ( 1) ( ) ( ) x x Ax b k k k = + − + 问： 取何值可使迭代收敛？ 取何值时迭代收敛最快？ 解：考察 B = I + A 的特征根 1 = 1+ , 2 = 1+ 3 收敛要求 ( B )<1 −2/3 < < 0 (B) = max { | 1+ |, | 1+ 3 | } 当 取何值时最小？ −2/3 −1/3 0 = − 1/2 HW: p.77 #5 #7