Newton Iteration At A Multiple Root

Why Multiplicity Changes Newton’s Method

Newton’s method is often associated with very rapid convergence near a root. Near a simple root, its error typically becomes proportional to the square of the previous error. A multiple root behaves differently: the error is usually reduced by a fixed fraction at each step, so convergence is only linear.

The distinction comes from the local shape of the function. At a root of multiplicity \(m\), the function contains a factor \((x-r)^m\). In the Newton quotient \(f(x)/f'(x)\), most of these powers cancel, leaving an update that is approximately \((x-r)/m\). The remaining error is therefore approximately \((m-1)/m\) times the old error.

To make that reasoning valid, we must control not only the function but also the derivative of the factor left over after \((x-r)^m\) is removed. The regularity condition below makes this explicit.

Multiplicity and the Newton Error

For a polynomial, this factorization is the usual meaning of a root of multiplicity \(m\). We focus on \(m\ge 2\). Write the error as \(e=x-r\). For \(x\ne r\), the product rule gives

When \(f'(x)\ne 0\), one Newton step is \(x_{\mathrm{new}}=x-f(x)/f'(x)\). Subtracting \(r\) and using the factorization yields the error recurrence

This formula applies to a non-root iterate where the denominator is nonzero. The formula does not define a Newton step at \(x=r\): there \(f(r)=f'(r)=0\). If an iterate is already exactly the root, the computation should stop.

Why the Error Factor Approaches \((m-1)/m\)

As \(x\to r\), continuity gives \(g(x)\to g(r)\ne 0\). Also, because \(g'\) is bounded near \(r\), the product \((x-r)g'(x)\) tends to zero. Thus the denominator in the recurrence tends to \(m g(r)\), which is nonzero, and the error factor tends to

The same conclusion holds if, instead of assuming \(g\) is continuously differentiable, one explicitly assumes \((x-r)g'(x)\to 0\) as \(x\to r\), along with the other conditions needed for the recurrence. Continuous differentiability is a convenient sufficient condition: it guarantees the required limit.

Proof of Local Convergence and the Error Factor

We first establish that the iteration is defined near, but not at, \(r\). The quantity \(mg(x)+(x-r)g'(x)\) tends to \(m g(r)\ne 0\). Therefore it is nonzero throughout some neighborhood of \(r\). For \(x\ne r\) in that neighborhood, the factor \((x-r)^{m-1}\) is also nonzero, so the formula for \(f'(x)\) shows \(f'(x)\ne 0\). Newton’s step is consequently defined there.

Let \(R(x)\) denote the error factor in the recurrence. The limit just proved is \(R(x)\to q\), where \(q=(m-1)/m\) and \(0<q<1\). Choose a number \(c\) with \(q<c<1\). By the definition of the limit, there is a neighborhood of \(r\) in which \(|R(x)|<c\) for all \(x\ne r\). In that neighborhood,

Choose the initial point inside this neighborhood. Each Newton step has smaller absolute error than the previous one, so every subsequent iterate stays in the neighborhood. The estimate can therefore be applied repeatedly, giving \(|e_n|\le c^n|e_0|\). Since \(0<c<1\), this bound tends to zero, so \(x_n\to r\). Finally, applying the limit of \(R(x)\) along these iterates gives \(e_{n+1}/e_n\to q=(m-1)/m\), as claimed.

Linear Convergence Versus Quadratic Convergence

Linear convergence means that the ratio of successive absolute errors approaches a constant strictly between zero and one. At a root of multiplicity \(m\), that constant is \((m-1)/m\). For example, it is \(1/2\) when \(m=2\), \(2/3\) when \(m=3\), and \(9/10\) when \(m=10\). As the multiplicity increases, the fraction of error remaining after each step becomes larger.

Quadratic convergence has a different error relationship: the next error is bounded by a constant times the square of the current error, for iterates sufficiently close to the root. The nonzero limiting ratio at a multiple root shows why ordinary Newton iteration does not have that behavior. Indeed, if \(|e_{\mathrm{new}}|/|e|\to q>0\), then \(|e_{\mathrm{new}}|/|e|^2\) grows without bound as \(|e|\to0\); it cannot remain bounded by a fixed quadratic error constant.

Worked Example: A Cubic Root of a Factored Polynomial

A Pitfall: Differentiability Alone Is Not Enough

A tempting argument is to say that \(g(x)\to g(r)\ne0\) and \(x-r\to0\), so \((x-r)g'(x)\to0\). This conclusion is not justified by differentiability of \(g\) alone: \(g'(x)\) can be unbounded near \(r\). The product of a quantity tending to zero and an unbounded quantity need not tend to zero.

What the Multiplicity Tells You

The factor \((m-1)/m\) describes the local behavior of ordinary Newton iteration when the multiplicity is known and the stated smoothness conditions hold. It explains why a multiple root can require substantially more iterations than a simple root, even when the starting point is close. The factor also indicates a practical caution: merely observing several decreasing errors does not mean quadratic convergence is occurring.

The multiplicity-based recurrence depends on a factorization around the root and on control of the derivative of the remaining factor. Without those conditions, the limiting error ratio does not follow just from the statement that the root is multiple. This is why assumptions about smoothness and the Newton denominator are part of the result, not technical decorations.