Why does Newton-Raphson converge quadratically when solving x^2 - 2 = 0 for sqrt(2)?
answer
- tangent line at the current guess
- the error squares, it does not halve
- correct digits roughly double each step
- needs a simple root and a close start
basics
~20 sNewton-Raphson replaces the function by its tangent line at the current guess, so each new error is roughly proportional to the square of the previous one. Near the root the number of correct digits roughly doubles per step.
solid answer
~40 sThe update is `x_next = x - f(x)/f'(x)`, which for `f(x) = x^2 - 2` simplifies to `x_next = (x + 2/x)/2`. Geometrically you draw the tangent at the current point and take its x-intercept as the next guess. Expanding f around the root shows the new error satisfies `e_next ~= (f''/(2 f')) * e^2`, so the error squares rather than shrinking by a constant factor — that is quadratic convergence. Starting at x = 1 the iterates run 1.5, 1.41666..., 1.4142156..., 1.41421356..., adding roughly twice as many correct digits each time. The guarantee is local and needs a simple root (f' nonzero there), a twice-differentiable f, and a starting point close enough; a bad start or a repeated root drops it to linear convergence or divergence.
code
python · 10 linesx = 1.0
for step in range(1, 6):
x = (x + 2 / x) / 2
print(step, repr(x))
# 1 1.5
# 2 1.4166666666666665
# 3 1.4142156862745097
# 4 1.4142135623746899
# 5 1.414213562373095go deeper
Be ready to write the update x - f(x)/f'(x), specialise it to x^2 - 2, and say in one sentence that the tangent line is the whole idea.
You should be able to sketch the Taylor argument that produces an error term proportional to the previous error squared, and name the simple-root and closeness conditions it needs.
An interviewer expects you to talk about failure modes you have hit: near-zero derivatives, cycling, repeated roots, and the stopping rule you would actually ship rather than the textbook one.
Own the choice of whether the quadratic rate is worth the derivative you have to supply and safeguard, versus a slower method that converges from anywhere without tuning.
## The method Newton-Raphson solves `f(x) = 0` by repeatedly linearising. At the current iterate `x_k` you approximate f by its tangent line, `f(x) ~= f(x_k) + f'(x_k)(x - x_k)`, and take as the next iterate the point where that line crosses zero: ``` x_{k+1} = x_k - f(x_k) / f'(x_k) ``` For `f(x) = x^2 - 2`, whose positive root is sqrt(2), we have `f'(x) = 2x` and the update collapses to a famous averaging rule: ``` x_{k+1} = x_k - (x_k^2 - 2)/(2 x_k) = (x_k + 2/x_k)/2 ``` In words: average your current guess with 2 divided by the guess. If the guess is too small, 2/x is too big, and the average lands between them. ## Why the error squares Let r be the true root and `e_k = x_k - r` the error. Taylor-expand f about `x_k` and evaluate at r: ``` 0 = f(r) = f(x_k) - f'(x_k) e_k + (1/2) f''(c) e_k^2 ``` for some c between r and `x_k`. Divide by `f'(x_k)` and rearrange using the update rule, and you get ``` e_{k+1} = (f''(c) / (2 f'(x_k))) * e_k^2 ``` So the next error is proportional to the **square** of the current error, not to the error itself. That is the definition of quadratic convergence: `|e_{k+1}| <= C |e_k|^2`. Practically, once you are inside the basin, an error of 1e-2 becomes about 1e-4, then 1e-8, then machine precision. The count of correct decimal digits roughly doubles per iteration. Compare with linear convergence, where each step multiplies the error by a fixed factor below one and adds a constant number of digits per step. ## The concrete run Starting from `x_0 = 1`: ``` x_1 = (1 + 2/1)/2 = 1.5 x_2 = (1.5 + 2/1.5)/2 = 1.4166666666666665 x_3 = 1.4142156862745097 x_4 = 1.4142135623746899 x_5 = 1.414213562373095 ``` The true value is 1.41421356237309504..., so `x_2` is right to about 2 digits, `x_3` to about 5, `x_4` to about 11, and `x_5` is at double precision. The doubling pattern is exactly the `e^2` law. ## What the guarantee does not say Quadratic convergence is a **local** statement. Three conditions matter: 1. **Simple root.** The bound divides by `f'(x_k)`, so it needs `f'(r) != 0`. At a repeated root — say solving `x^2 = 0` — the derivative vanishes at the root and convergence degrades to linear, with the error only halving each step. 2. **Smoothness.** f must be twice differentiable with a bounded second derivative near the root, otherwise the `f''` factor is not controlled. 3. **Close enough start.** Far from the root the tangent line is a poor model of f. If `f'(x_k)` is close to zero the step `f/f'` is enormous and throws the iterate somewhere unrelated; with some functions the iterates cycle forever or run to infinity. For `x^2 - 2` with any positive start the method is unusually well behaved and converges monotonically from above after the first step, but that is a property of this convex function, not of the method in general. ## Why it matters for optimization Root finding is the same machinery used to minimise: to minimise a smooth function you look for a zero of its derivative, so you apply the same tangent-line idea to `f'` and end up dividing by the second derivative. The convergence story carries over — the same quadratic rate near a well-behaved minimum, and the same fragility far from it. This is why practical optimizers wrap the raw step in safeguards such as a line search or a trust region rather than trusting the pure update from an arbitrary starting point.
- What happens to the iteration when the derivative is near zero at the current iterate?The step `f(x)/f'(x)` blows up and throws the iterate far from the region where the tangent model was valid, so the sequence can jump away or cycle. A related failure is a repeated root, where the derivative vanishes at the root itself: the quadratic rate collapses to linear, with the error only shrinking by a constant factor each step.
- Does quadratic convergence mean the method converges from any starting point?No. The rate is a local property that only applies once the iterate is inside a neighbourhood of a simple root. From a poor start Newton-Raphson can diverge, oscillate between two values, or converge to a different root entirely. Practical implementations add a globalisation layer — bracketing, damping the step, or a line search — and only take full steps once they are near the solution.
- How would you decide when to stop iterating?Combine a small residual `|f(x)|` with a small relative change between successive iterates, and cap the iteration count. Because the error squares, the step size between the last two iterates is itself a good estimate of the remaining error near a simple root. Requiring `|f(x)|` alone is unsafe when the function is very flat near the root.
It is like sanding a curved surface with a straight ruler: near the target the curve looks straight, so one pass removes almost all the remaining gap, and each pass leaves a gap squared rather than merely reduced.
saying these in an interview costs you the question
- Claims Newton-Raphson converges from any starting point
- Says quadratic convergence means two iterations suffice
- Confuses quadratic convergence with solving a quadratic equation
- Thinks each iteration halves the error
- Ignores that a repeated root destroys the quadratic rate