Lecture note 2 Numerical Analysis p∈[an,onl and pn=n,so Ipn-pl≤z(bn-an)=是 口 Corollary 1(Corollary 1.2) n limoe pn=p. For bisection method,we can stop it until the absolute lp-pil<e. Example:Determine the number of iterations necessary to solve 3x-e"=0 on [1,2]with accuracy 10-3.We have 6-a 1 pm-川≤2n=2a≤10-3 Solve 1 ≤10-3 Take logarithm on both hand sides, -n≤-31og210,s0n≥31og210≈9.96. We need at least 10 iterations! Summary of the bisection method ·PrOs 1.Simple and easy to implement 2.One function evaluation per iteration 3.No knowledge of the derivative is needed 4.Easy to converge (only need continuity) ·Cons 1.Have to find an interval [a,b]such that f(a)f(b)<0 2.The error depends on b-a and converges slowly 3.It is hard to generalize it to solutions of multi-variable nonlinear equa- tions 1.2 Fixed point iteration 1.2.1 Fixed point Definition:p is a fixed point of g of g(p)=p. Finding a root of f(z)is equivalent to finding a fixed point,e.g., g(x)=x-f(x),g(x)=x+3f(x),g(x)=x-h(x)f(r),h(x)≠0，… 5Lecture note 2 Numerical Analysis p ∈ [an, bn] and pn = an+bn 2 , so |pn − p| ≤ 1 2 (bn − an) = b−a 2n . • Corollary 1 (Corollary 1.2) lim n→+∞ pn = p. • For bisection method, we can stop it until the absolute |p − pi | < ǫ. • Example: Determine the number of iterations necessary to solve 3x − e x = 0 on [1, 2] with accuracy 10−3 . We have |pn − p| ≤ b − a 2 n = 1 2 n ≤ 10−3 . Solve 1 2 n ≤ 10−3 Take logarithm on both hand sides, −n ≤ −3 log2 10, so n ≥ 3 log2 10 ≈ 9.96. We need at least 10 iterations! Summary of the bisection method • Pros 1. Simple and easy to implement 2. One function evaluation per iteration 3. No knowledge of the derivative is needed 4. Easy to converge (only need continuity) • Cons 1. Have to find an interval [a, b] such that f(a)f(b) < 0 2. The error depends on b − a and converges slowly 3. It is hard to generalize it to solutions of multi-variable nonlinear equa￾tions 1.2 Fixed point iteration 1.2.1 Fixed point • Definition: p is a fixed point of g of g(p) = p. • Finding a root of f(x) is equivalent to finding a fixed point, e.g., g(x) := x − f(x), g(x) = x + 3f(x), g(x) = x − h(x)f(x), h(x) 6= 0, , ... 5