Lecture note 2 Numerical Analysis or g()=x- f(x)f(x) (f'()2-ff"() Converges quadratically! 1.4 Error Analysis for Iterative Methods Newton's method converges fast. -Pati =g(pa),where g()= -gp)=0. Use a figure to illustrate it! -Closer pn is to p,flatter the graph of g is. -Small Ipn-pl yields small k. -If Ipn-pl close to 0,k:close to 0. -Quantitative analysis needed! Use a graph to illustrate it! ·Convergence order:Suppose that limn-→opn=p and Pn≠p for all n.If there exists positive numbers入，a such that lim pn+1-刊=入. n→lpn-pla then, -a-convergence order. -入一asymptotic error constant -The iteration generate pn is of order a. .a =1 (it must holds A<1.Why?)linearly convergent. .a =2,quadratically convergent. Generally,higher order means much faster convergence. ·It implies:: -a=1 There exists Ni such that for all n>N1, 2n+1-卫≤C. IPn -p Then lpn+m-pl≤Clpn+m-1-pl≤C2lpn+m-2-pl≤Cm{pn-pl. 17Lecture note 2 Numerical Analysis or g(x) = x − f(x)f ′ (x) (f ′(x))2 − f(x)f ′′(x) Converges quadratically! 1.4 Error Analysis for Iterative Methods • Newton’s method converges fast. – pn+1 = g(pn), where g(x) = x − f(x) f ′(x) . – g ′ (p) = 0. – Use a figure to illustrate it! – Closer pn is to p, flatter the graph of g is. – Small |pn − p| yields small k. – If |pn − p| close to 0, k close to 0. – Quantitative analysis needed! • Use a graph to illustrate it! • Convergence order: Suppose that limn→∞ pn = p and pn 6= p for all n. If there exists positive numbers λ, α such that limn→∞ |pn+1 − p| |pn − p| α = λ. then, – α — convergence order. – λ — asymptotic error constant – The iteration generate {pn} +∞ n=0 is of order α. • α = 1 (it must holds λ < 1. Why?) linearly convergent. • α = 2, quadratically convergent. • Generally, higher order means much faster convergence. • It implies: – α = 1 There exists N1 such that for all n ≥ N1, |pn+1 − p| |pn − p| ≤ C. Then |pn+m − p| ≤ C|pn+m−1 − p| ≤ C 2 |pn+m−2 − p| ≤ C m|pn − p|. 17