You must solve f(x) = 0 for a smooth increasing f on [0,1] to an absolute accuracy of 10^{-12}. Give the number of iterations bisection needs, give the convergence order of Newton's method, and state the three situations where you would refuse to use Newton.

You must solve f(x) = 0 for a smooth increasing f on [0,1] to an absolute accuracy of 10^{-12}. Give the number of iterations bisection needs, give the convergence order of Newton's method, and state the three situations where you would refuse to use Newton.

Approach: Bisection halves the bracket each step, so count halvings. For Newton expand f around the root and read the error recursion, then look for the assumptions that recursion needs.

40 iterations for bisection, and Newton converges quadratically. Bisection halves the interval each step, so it needs log_2(1/10^{-12}) = 39.9, that is 40 steps, and it is guaranteed as long as the sign changes across the bracket. Newton's iteration x_{k+1} = x_k - f(x_k)/f'(x_k) has error recursion e_{k+1} = (f''(r)/(2 f'(r))) e_k^2 from a Taylor expansion about the root r, so the number of correct digits doubles each step and an error of 10^{-2} becomes 10^{-12} in about three further iterations. Refuse Newton when f'(r) is near zero, since the constant in the error recursion blows up and a multiple root degrades convergence to linear with rate 1/2. Refuse it when no good starting point is available, since the iteration can cycle or diverge with no bracket to fall back on. Refuse it when f' is unavailable or expensive, where the secant method at order 1.618 costs one evaluation per step instead. The practical answer is a bracketed hybrid that takes a Newton step when it lands inside the bracket and a bisection step otherwise.

Follow-up: How do you choose the tolerance when the function itself is only computable to 10^{-10} and what does that do to the achievable accuracy?

Key concepts: bisection, newton's method, quadratic convergence, bracketing.