quadratic convergence

There are slow ways to close in on an answer and fast ways. Linear convergence chips away a fixed fraction of the error each step — like paying down a debt at 10% a year. Quadratic convergence does something dramatically better: it roughly SQUARES the error each step, so the number of correct digits doubles. Three correct digits become six, then twelve, then twenty-four. After a couple of steps it is simply done.

Precisely, a sequence x_n converging to x* has order p if the errors e_n = x_n - x* satisfy |e_{n+1}| <= C * |e_n|^p for some constant C, for all large n. Order p = 1 (with C < 1) is linear; p = 2 is quadratic; values between 1 and 2 are called superlinear. For quadratic order, once the error is small, squaring it makes it plummet: if e_n is about 10^-3, then e_{n+1} is about C * 10^-6, and the next is about 10^-12. Newton's method achieves p = 2 at a simple root because its error recurrence is e_{n+1} is approximately (f''(x*) / (2 f'(x*))) * e_n^2 — the linear term cancels, leaving the square.

Two honest caveats keep this in perspective. First, the squaring only kicks in ONCE you are close (in the 'basin' near the root); far away, a quadratically convergent method can behave erratically and may not converge at all. Second, the order is a property of the method ON a given problem: Newton drops to merely linear convergence at a MULTIPLE root (where f' also vanishes), and a poor problem conditioning can cap the achievable accuracy regardless of order. Higher order is wonderful, but it does not rescue a bad starting guess or an ill-conditioned root.