BS Numerical Methods: Newton Iteration Cycle
A candidate in a numerical methods course solves f(x) = x³ − 2x + 2 = 0 with Newton–Raphson, starting at x₀ = 0. The first iterate is x₁ = 1. The next is x₂ = 0, and the sequence continues to alternate between 0 and 1. The candidate concludes that the equation has no real root and recommends switching to a graphical method. The instructor points out that f(−2) = −2 and f(−1) = 3. The candidate must diagnose the failure, choose a starting value that avoids it, and decide whether bisection or Newton–Raphson is the better choice when only ten function evaluations are allowed. The stopping criterion is |x_{n+1} − x_n| < 10⁻⁶, but the code reaches the iteration limit. The derivative is f′(x) = 3x² − 2. The candidate has a calculator and no computer.
1. Carry out two Newton iterations from x₀ = 0 and explain why the method fails here. Is the candidate's conclusion that no real root exists correct?
Read the worked answer
f(0) = 2, f′(0) = 0 − 2 = −2, so x₁ = 0 − 2/(−2) = 1. Then f(1) = 1 − 2 + 2 = 1, f′(1) = 3 − 2 = 1, so x₂ = 1 − 1/1 = 0.
The map returns to 0, so the iteration is a 2-cycle, not a root. The conclusion that no real root exists is wrong: f(−2) = −8 + 4 + 2 = −2 and f(−1) = −1 + 2 + 2 = 3, so by the intermediate value theorem a root lies in (−2, −1). Newton's failure is local, caused by starting where the derivative is small and the curvature sends the iterate across the root.
2. Use the sign change to bracket the root and propose a starting value that avoids the cycle. Justify your choice using f′(x).
Read the worked answer
Bracket the root: f(−2) < 0, f(−1) > 0. Use x₀ = −2, which is outside the region |x| < √(2/3) ≈ 0.816 where f′(x) = 3x² − 2 is negative and can be small.
One iteration: x₁ = −2 − f(−2)/f′(−2) = −2 − (−2)/10 = −1.8. Then f(−1.8) = −5.832 + 3.6 + 2 = −0.232, f′(−1.8) = 7.72, and x₂ = −1.8 + 0.232/7.72 ≈ −1.770. This is close to the root near −1.769. Starting at −2 avoids the cycle because the derivative is large and the first step moves toward the bracketed root.
3. With a budget of ten function evaluations, compare bisection on [−2, −1] with Newton from x₀ = −2. Which gives a guaranteed error bound? Estimate the bound.
Read the worked answer
Bisection on [−2, −1] gives a guaranteed error bound. After n evaluations the interval length is 2⁻ⁿ, so ten evaluations give 2⁻¹⁰ ≈ 0.001.
Newton from −2 will probably converge much faster: the first three iterates are about −2, −1.8, and −1.770, already within 0.001 after three evaluations. But Newton has no guarantee here. Bisection is the safer choice if a guaranteed bound is required. A hybrid-bisection to get close, then Newton-uses the budget best.