1. Prove the convergence of the bisection method.

Theorem 0.1 (Convergence and Error). Suppose the bisection method is applied to a continuous func- tion f  : [a, b] → R (f (a)f (b) s 0). Let [a0 , b0 ] = [a, b], [a1 , b1 ], [a2 , b2 ], . . . be the intervals generated by the method and let cn   = (an  + bn )/2 be the midpoint of [an , bn ].  Then limn→8 an   = limn→8 bn   =

limn→8 cn  = 长, where 长 e [a, b] satisfies f (长) = 0. Furthermore,

lcn - 长l s 2-(n+1)(b - a)

2. Suppose that the bisection method is started with the interval [50, 63]. How many steps should be taken to compute a root with an relative error that is smaller than 10-12 ?

3. Generalize the previous problem. That is, prove that if the bisection method is started with the interval [a0 , b0 ] (a0  3 0) to find a root of a continuous function (assume it exists), then for relative error to be smaller than e 3 0, it takes n steps, where

n 2  - 1.

Remember that we choose the midpoint of the last interval for our approximate solution.

4. Drive the Newton’s method for finding a root of f (x) = 0, if exists, following the steps below.

(a) Let 长 is a root, i.e., f (长) = 0.

(b) Expand Taylor series of f (长) around the current position, say, xn .

(c) Take the linear approximation, namely, truncate the second or higher order terms.

(d) Solve for 长, but call it xn+1 .