Iterative Method for the Solution of Linear Equations →Introduction Fix point Iteration and convergence Jacobi,Gauss-Seidel and SOR Permutation and condition number More iterative method Copyright©2011，NA⊙Yin Last Modification:Oct.2011 2
Iterative Method for the Solution of Linear Equations ⇒ Introduction • Fix point Iteration and convergence • Jacobi, Gauss-Seidel and SOR • Permutation and condition number • More iterative method Copyright c 2011, NA Yin Last Modification: Oct. 2011 2
Matrix splitting Ax=b Assume that A=M-N,then (M-N)x=6 Mx=Nx+b If M nonsingular, x=M-INx+M-b Define T M-IN,g=M-16,then x=Tx+g Copyright©2011，NA⊙Yin Last Modification:Oct.2011 3
Matrix splitting Ax = b Assume that A = M − N, then (M − N)x = b Mx = Nx + b If M nonsingular, x = M−1Nx + M−1 b Define T = M−1N, g = M−1 b, then x = T x + g Copyright c 2011, NA Yin Last Modification: Oct. 2011 3
Why not Iterate? Iterates by xk+1=Txk十9 If converge,then x*=Tx*+g Note xk+1一x*=T(xk-x*) Define a kind of distant look for the condition so that xk+1-x*‖=T(k-x*≤‖lxk-x‖ Copyright©2011，NA⊙Yin Last Modification:Oct.2011 4
Why not Iterate? Iterates by xk+1 = T xk + g If converge, then x ∗ = T x∗ + g Note xk+1 − x ∗ = T(xk − x ∗ ) Define a kind of distant k · k, look for the condition so that kxk+1 − x ∗ k = kT(xk − x ∗ )k |{z} < ? kxk − x ∗ k Copyright c 2011, NA Yin Last Modification: Oct. 2011 4
Distant of Vector:Norm x∈R”,‖·‖：Rm→R+,s.t. 1.x∈R”,x‖≥0；x=0台x=0 2.a∈R,axl=lalllzll 3.x,y∈R",lx+yl≤lx+ly Let x=(z1,22,...,2n)T E Rn, l1=1+2+...+nl llll2= V好+喝+…+x说 lllloo max zil 1<i≤n Copyright©2011，NA⊙Yin Last Modification:Oct.2011 5
Distant of Vector: Norm ∀x ∈ R n , k · k : R n → R+, s.t. 1. ∀x ∈ R n , kxk ≥ 0; kxk = 0 ⇔ x = 0 2. ∀α ∈ R, kαxk = |α|kxk 3. ∀x, y ∈ R n , kx + yk ≤ kxk + kyk Let x = (x1, x2, . . . , xn) T ∈ R n, kxk1 = |x1| + |x2| + · · · + |xn| kxk2 = q x 2 1 + x 2 2 + · · · + x 2 n kxk∞ = max 1≤i≤n |xi | Copyright c 2011, NA Yin Last Modification: Oct. 2011 5
Norm of Matrix A∈Rmxm,‖·‖：Rmxm→R+,s.t 1.A∈Rmxm,‖Al≥0；A|=0台A=0 2.a∈R,aAl=lalllA 3.A,B∈Rmxm,A+B‖≤‖Al+IB‖ 4.A,B∈Rn×n,‖AB‖≤‖AIllB Copyright©2011，NA⊙Yin Last Modification:Oct.2011 6
Norm of Matrix ∀A ∈ R n×n , k · k : R n×n → R+, s.t. 1. ∀A ∈ R n×n , kAk ≥ 0; kAk = 0 ⇔ A = 0 2. ∀α ∈ R, kαAk = |α|kAk 3. ∀A, B ∈ R n×n , kA + Bk ≤ kAk + kBk 4. ∀A, B ∈ R n×n , kABk ≤ kAkkBk Copyright c 2011, NA Yin Last Modification: Oct. 2011 6
LetA={a}∈Rnxn, n IAl 1= max 1≤j≤n 2=1 llzll2= Vp(AT A)=maxtal,(A)} llalloo ∑ 三1 minim,nt lclr=】 a,P=VA4四=V空 =11=1 where (A)is the set of eigenvalues of A,p(A)=max,(A)}is called spectral radius. Copyright©2011，NAOYin Last Modification:Oct.2011
Let A = {aij} ∈ R n×n, kAk1 = max 1≤j≤n X n i=1 |aij| kxk2 = q ρ(ATA) = max{|λ|, λ ∈ σ(A)} kxk∞ = max 1≤i≤n X n j=1 |aij| kxkF = X n i=1 X n j=1 |aij| 2 = q tr(AAH) = vuut min X {m,n} i=1 σ 2 i where σ(A) is the set of eigenvalues of A, ρ(A) = max{|λ|, λ ∈ σ(A)} is called spectral radius. Copyright c 2011, NA Yin Last Modification: Oct. 2011 7
Compatible norms IAzl1≤IAlx1 ‖A2≤IAl2xll2 ‖Ax‖o≤‖lA‖llxl IAxl2≤‖A|Fx2 Another useful inequality between matrix norms is IAl2≤VIAlAIl Copyright©2011，NA⊙Yin Last Modification:Oct.2011 8
Compatible norms kAxk1 ≤ kAk1kxk1 kAxk2 ≤ kAk2kxk2 kAxk∞ ≤ kAk∞kxk∞ kAxk2 ≤ kAkF kxk2 Another useful inequality between matrix norms is kAk2 ≤ p kAk1kAk∞ Copyright c 2011, NA Yin Last Modification: Oct. 2011 8
Equivalence of norms LetA={a}∈Rmxn, lA2≤A‖F≤Vrllzlla2 ‖A‖F≤‖A*≤VTlxllE VA:≤4≤VmVF 1 VaAe≤Ae≤Vv where r rank(A) Copyright©2011，NAOYin Last Modification:Oct.2011 g
Equivalence of norms Let A = {aij} ∈ R m×n, kAk2 ≤ kAkF ≤ √ rkxk2 kAkF ≤ kAk∗ ≤ √ rkxkF 1 √ n kAk1 ≤ kAk2 ≤ √ m √ rkxk1 1 √ m kAk∞ ≤ kAk2 ≤ √ n √ rkxk∞ where r = rank(A). Copyright c 2011, NA Yin Last Modification: Oct. 2011 9
Permutation 2.0002 1.9998 1.9998 2.0002 2 =(④ Solution is x=(1,1)T. 0.0002 Let ob= -0.0002 2.0002 1.9998 4.0002 1.9998 2.0002 3.9998 Solution is=(1.5,0.5)T. lx-_1 lδblo-1 llalloo 2 bll∞ =2 Copyright©2011，NA⊙Yin Last Modification:Oct.2011 10
Permutation 2.0002 1.9998 1.9998 2.0002 x1 x2 = 4 4 Solution is x = (1, 1)T . Let δb = 0.0002 −0.0002 2.0002 1.9998 1.9998 2.0002 xe1 xe2 = 4.0002 3.9998 Solution is xe = (1.5, 0.5)T . kx − xek∞ kxk∞ = 1 2 kδbk∞ kbk∞ = 1 2 Copyright c 2011, NA Yin Last Modification: Oct. 2011 10
Permutation I Consider A(x+6x)=b+6b .Ax=6 .∴.A6x=6b →6x=A-16b →lδxl≤16bl From Ax=b →bl≤AlI 宁团≤A面 ≤4 ·x Copyright©2011，NA⊙Yin Last Modification:Oct.2011 11
Permutation I Consider A(x + δx) = b + δb ∵ Ax = b ∴ Aδx = δb ⇒ δx = A −1 δb ⇒ kδxk ≤ kδbk From Ax = b ⇒ kbk ≤ kAkkxk ⇒ 1 kxk ≤ kAk 1 kbk ∴ kδxk kxk ≤ kA −1 kkAk kδbk kbk Copyright c 2011, NA Yin Last Modification: Oct. 2011 11