Root-Finding & Nonlinear Equations

a multiple root

Most roots cross the axis cleanly: the curve comes down from above, passes through zero, and continues below — a simple root. A multiple root is different: the curve touches zero and turns back without crossing, or flattens out as it passes through, lingering against the axis. Algebraically, the factor (x - r) appears more than once in the function near r, and this 'lingering' makes the root both harder to detect and harder to compute accurately.

Formally, r is a root of multiplicity m if f(r) = 0 and the derivatives f'(r), f''(r), ..., up to the (m-1)th all vanish too, while the m-th does not. For a polynomial this is the (x - r)^m factor: x^2 = 0 has a double root (m = 2) at 0; (x - 1)^3 has a triple root. The consequences for root-finding are real. First, bracketing by sign change FAILS at an even-multiplicity root because f does not change sign — bisection and regula falsi cannot even start. Second, and more insidious, Newton's method LOSES its quadratic speed at a multiple root: because f' also vanishes there, the error recurrence becomes e_{n+1} is approximately ((m - 1)/m) * e_n, which is merely LINEAR, with the slowdown worse the higher the multiplicity.

There is also an accuracy ceiling that no method escapes: a multiple root is intrinsically ILL-CONDITIONED. Near a double root f is nearly flat, so floating-point noise of size epsilon in f corresponds to an uncertainty of size about sqrt(epsilon) in x — for double precision that means you can trust only about HALF the digits (roughly 8 instead of 16). The remedies are to find the multiplicity m and use the modified Newton step x_{n+1} = x_n - m * f(x_n)/f'(x_n) (which restores quadratic order), or to apply Newton to the deflated function f/f' (whose roots are all simple), or to compute polynomial roots via companion-matrix eigenvalues, which handle clustered roots more gracefully.

Newton on f(x) = (x - 1)^2 (double root at 1) from x_0 = 2 gives 1.5, 1.25, 1.125, 1.0625, ... — the error merely halves each step (linear), not squares, because f'(1) = 0 too. The modified step x_{n+1} = x_n - 2*f/f' recovers the doubling-digits behaviour. Meanwhile bisection cannot even bracket this root: f stays nonnegative, never changing sign.

At a multiple root Newton slows to linear and accuracy is capped near half precision.

A multiple root is ill-conditioned: even a perfect algorithm gives only about half the usual digits (sqrt(machine epsilon)). And an even-multiplicity root cannot be bracketed by sign change at all, so derivative-free bracketing methods miss it entirely.

Also called
repeated rootroot of multiplicity m重根多重根