Lecture note 2 Numerical Analysis Letting m→+oo leads to Ip-pal=lim lpm -palslim k"lpi -pol(1++km1) m3+ m-n- kn =k"lp1-pol lim m++0 ∑-1广xi-ol i= 口 The convergence speed depends on k.Smaller k leads to faster convergence. Ipn -pl<k"max{po-a,b-po}. and -l≤1-m-ol,n≥L. 1.2.3 Using fixed-point iteration to find zeros of a function Many ways to transfer root-finding to fixed point problems. Example:g(x)=x-f(x) ·Example::g(r)=x-h(x)f(x),h(x)≠0. -h()Newton's method Example:Find a root of f(r)=3+4x2-10 in [1,2]. 1.91(x)=x-x3-4x2+10.(x-f(x)） g1(1)=6and91(2)=12,sog(x)年[1,2. Moreover,g'(r)=1-3x2-8r,so g'()>1 for all r [1,2]. The convergence is not guaranteed by the Fixed-point Theorem. Not converge by experiments. 2.93(x)=2(10-x3)1/2. g6(x)=-￥x2(10-x3)-1/2<0,z∈[1,2. g3 is strictly decreasing on [1,2].g(1.5)1.28 and g(1)=1.5,so g(1,1.5])c[1,1.5]. Moreover,lg(x≤lg(1.5)川≈0.66. The fixed point theorem guarantees its convergence.k=0.66 9a国=(0) g(x)∈[1,2]z∈[1,2.lg4(x1= -5 V10(4+x)3/2 ≤Ym≤0.15z∈ [1,2 Convergence guaranteed by the Fixed-point Theorem. faster than 93. 4.95(x)=x-3+42-10 Newton's method Converges very fast. Will be studied in the next lecture. 11Lecture note 2 Numerical Analysis Letting m → +∞ leads to |p − pn| = lim m→+∞ |pm − pn| ≤ lim m→+∞ k n |p1 − p0|(1 + k + k 2 + . . . + k m−n−1 ) = k n |p1 − p0| lim m→+∞ mX−n−1 i=1 k i = k n 1 − k |p1 − p0|. • The convergence speed depends on k. Smaller k leads to faster convergence. |pn − p| ≤ k n max{p0 − a, b − p0}. and |pn − p| ≤ k n 1 − k |p1 − p0|, ∀n ≥ 1. 1.2.3 Using fixed-point iteration to find zeros of a function • Many ways to transfer root-finding to fixed point problems. • Example: g(x) = x − f(x) • Example: g(x) = x − h(x)f(x), h(x) 6= 0. – h(x) = 1 f ′(x) ←− Newton’s method • Example: Find a root of f(x) = x 3 + 4x 2 − 10 in [1, 2]. 1. g1(x) = x − x 3 − 4x 2 + 10. (x − f(x)) g1(1) = 6 and g1(2) = 12, so g(x) 6∈ [1, 2]. Moreover, g ′ (x) = 1 − 3x 2 − 8x, so |g ′ (x)| > 1 for all x ∈ [1, 2]. The convergence is not guaranteed by the Fixed-point Theorem. Not converge by experiments. 2. g3(x) = 1 2 (10 − x 3 ) 1/2 . g ′ 3 (x) = −3 4 x 2 (10 − x 3 ) −1/2 < 0, ∀x ∈ [1, 2]. g3 is strictly decreasing on [1, 2]. g(1.5) ≈ 1.28 and g(1) = 1.5, so g([1, 1.5]) ⊂ [1, 1.5]. Moreover, |g ′ 3 (x)| ≤ |g ′ 3 (1.5)| ≈ 0.66. The fixed point theorem guarantees its convergence. k = 0.66 3. g4(x) =  10 4+x 1/2 g(x) ∈ [1, 2] ∀x ∈ [1, 2]. |g ′ 4 (x)| =    √ −5 10(4+x) 3/2    ≤ √ 5 1053/2 ≤ 0.15 ∀x ∈ [1, 2] Convergence guaranteed by the Fixed-point Theorem. faster than g3. 4. g5(x) = x − x 3+4x 2−10 3x2+8x . Newton’s method. Converges very fast. Will be studied in the next lecture. 11