§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‖ 充分条件:B<1→ 等价于对 任何算子范数有 必要条件 as lA-A1→>0ask→ 定义设: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 ) < 1 证明：“” 若 是 B 的eigenvalue, 则 k 是 Bk 的eigenvalue 。 则 [ (B)] k = [ max | | ]k = | m k | ( Bk ) || Bk || → 0 (B) < 1 ✓ “” 首先需要一个引理 /* Lemma */ 对任意 > 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)