Lecture note 2 Numerical Analysis -a>1 There exists Ni such that for all n N1, Pm+1-1≤C. IPn-pl Then,when nN pn+m-pl≤Clpm+m-1-p≤C.Clpn+m-2-pla ≤C.Coopn+m-3-p2≤C.Ca.Ca.Ca.Ca-pm-plm =C(o"-1)/(a-1)lpn-plo" =(C点pn-p0a"/C立. Since pnp,we can find a N2,when n>N2, B=Ca-Tlpn -pl<1. Then,when n max{N1,N2),we have lpn+m-pl≤Ba"/Ca÷ This is very fast! Linearly convergent:C,C2,C3,C4,C5 Quadratically convergent:B2,B4,B8,B16,B32 ●Example: Linearly Convergent:limp= Pn-p Step 10:error 10-3. Step11:error0.5×10-3=5×10-4. Step 12:error 2.5 x 10-4. Quadratically convergent:limp→+ePat'二=3. Pn-P Step 10:error 10-3. Step11:error3(×10-3)2=3×10-6 Step12:eror3(3×10-6)2=2.7×10-11 Fixed point iteration converges linearly. Newton's method converges quadratically. Theorem 8 (Theorem 4.1)Suppose that 1.p is a fired point of g. 2.Pn+1=g(Pn)converges to p. Then 18Lecture note 2 Numerical Analysis – α > 1 There exists N1 such that for all n ≥ N1, |pn+1 − p| |pn − p| ≤ C. Then, when n > N1 |pn+m − p| ≤ C|pn+m−1 − p| α ≤ C · C α |pn+m−2 − p| α 2 ≤ C · C αC α 2 |pn+m−3 − p| α 3 ≤ C · C α · C α 2 · C α 3 · C αm−1 |pn − p| αm = C (αm−1)/(α−1)|pn − p| αm = (C 1 α−1 |pn − p|) αm /C 1 α−1 . Since pn → p, we can find a N2, when n > N2, β = C 1 α−1 |pn − p| < 1. Then, when n > max{N1, N2}, we have |pn+m − p| ≤ β αm /C 1 α−1 . This is very fast! • : Linearly convergent: C, C 2 , C 3 , C 4 , C 5 Quadratically convergent: β 2 , β 4 , β 8 , β 16 , β 32 • Example: Linearly Convergent: limp→+∞ |pn+1−p| pn−p = 1 2 . Step 10: error 10−3 . Step 11: error 0.5 × 10−3 = 5 × 10−4 . Step 12: error 2.5 × 10−4 . Quadratically convergent: limp→+∞ |pn+1−p| pn−p = 3. Step 10: error 10−3 . Step 11: error 3(×10−3 ) 2 = 3 × 10−6 . Step 12: error 3(3 × 10−6 ) 2 = 2.7 × 10−11 . • Fixed point iteration converges linearly. • Newton’s method converges quadratically. Theorem 8 (Theorem 4.1) Suppose that 1. p is a fixed point of g. 2. pn+1 = g(pn) converges to p. Then 18