Lecture note 2 Numerical Analysis 1.Ifg∈C[a,andg(p)≠0，then pn converges linearly.. 2.fg∈C2[a,b,gp)=0andg"(p)≠0，then pn converges quadratically. Fixed point iteration is generally linearly convergent. To get a quadratically convergent algorithm for f(p)=0,we use fixed point iteration g(r)=x-h(r)f(x)with h()0. g(x)=1-'(x)f(x)-h(x)f'(x) In order that g'(p)=1-h(p)f'(p)=0,we have 1 h(p)=Jp) h()-ensures it.We get Newton's method again! Proof. 1.Mean Value Theorem: g(pn)-g(p)=g(En)(Pn-p) Here we use En because if depends on pn and p. pn+1-p)=g(ξn)pn-p) lpn+1-卫=lg'(snl Pn-pl Since En is between Pn and p _limξn=p, n→+00 （-p川≤imlp-pl=0) and lg'(r)is continuous,we have lim B2-=im=lg(ni平川=lgl n++olpn-pln→+oo 2.Taylor's expansion, aPa)=g)+)a)+(pp 2 Here we use En because if depends on pn and p. a41-=-pr Pm+1-卫- Ig"(n)I Pn -p2 2 19Lecture note 2 Numerical Analysis 1. If g ∈ C 1 [a, b] and g ′ (p) 6= 0, then pn converges linearly. 2. If g ∈ C 2 [a, b], g ′ (p) = 0 and g ′′(p) 6= 0, then pn converges quadratically. • Fixed point iteration is generally linearly convergent. • To get a quadratically convergent algorithm for f(p) = 0, we use fixed point iteration g(x) = x − h(x)f(x) with h(x) 6= 0. g ′ (x) = 1 − h ′ (x)f(x) − h(x)f ′ (x). In order that g ′ (p) = 1 − h(p)f ′ (p) = 0, we have h(p) = 1 f ′(p) . h(x) = 1 f ′(x) ensures it. We get Newton’s method again! Proof. 1. Mean Value Theorem: g(pn) − g(p) = g ′ (ξn)(pn − p) Here we use ξn because if depends on pn and p. (pn+1 − p) = g ′ (ξn)(pn − p) |pn+1 − p| |pn − p| = |g ′ (ξn)| Since ξn is between pn and p lim n→+∞ ξn = p, ( lim n→+∞ |ξn − p| ≤ lim |pn − p| = 0) and |g ′ (x)| is continuous, we have lim n→+∞ |pn+1 − p| |pn − p| = lim n→+∞ |g ′ (ξn)| = |g ′ ( lim n→+∞ ξn)| = |g ′ (p)| 2. Taylor’s expansion, g(pn) = g(p) + g ′ (p)(pn − p) + g ′′(ξn) 2 (pn − p) 2 . Here we use ξn because if depends on pn and p. (pn+1 − p) = g ′′(ξn) 2 (pn − p) 2 |pn+1 − p| |pn − p| 2 = |g ′′(ξn)| 2 19