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