5.4. Multiple Roots

So far we have ignored the case \(f'(a)=0\). This case is typically described as a multiple root because if \(f(x)\) is a polynomial and \(f(a)=f'(a)=f''(a)=\ldots =f^{(k-1)}(a)=0\), this would imply that \((x-a)^k\) is a factor of \(f(x)\) (in other words, \(a\) is a root with multiplicity of \(k\)). Let us now assume that \(f(a)=f'(a)=f''(a)=\ldots =f^{(k-1)}(a)=0\), but \(f^{(k)}(a)\neq 0\). At first, it may appear that Newton’s method would be inapplicable in this case, because the denominator \(f'(x)\) becomes near-zero close to the solution. Consider, however, the example:

\[f(x)=(x-1)^3(x+2)\]

Newton’s method would give:

\[g(x)=x-\frac{f(x)}{f'(x)}=x-\frac{(x-1)^3(x+2)}{3(x-1)^2(x+2)+(x-1)^3}=x-\frac{(x-1)(x+2)}{4x+5}\]

whose denominator remains non-zero near the solution \(x=1\). In fact, we can show that \(g\) remains a contraction near \(a\) in this case.

Proof: Remember that

\[g'(x)=\frac{f(x)f''(x)}{[f'(x)]^2}\]

Taylor’s theorem applied on \(f(x)\) yields:

\[f(x)=\underbrace{f(a)}_{=0}+\underbrace{f'(a)}_{=0}(x-a)+\ldots +\underbrace{\frac{f^{(k-1)}(a)}{(k-1)!}}_{=0}(x-a)^{k-1}+\underbrace{\frac{f^{(k)}(c_1)}{k!}}_{\neq 0}(x-a)^k\]

Applying Taylor’s formula on the derivative \(f'(x)\) gives

\[f'(x)=\underbrace{f'(a)}_{=0}+\underbrace{f''(a)}_{=0}(x-a)+\ldots +\underbrace{\frac{f^{(k-1)}(a)}{(k-2)!}}_{=0}(x-a)^{k-2}+\underbrace{\frac{f^{(k)}(c_2)}{(k-1)!}}_{\neq 0}(x-a)^{k-1}\]

And one more on the second derivative \(f''(x)\)

\[f''(x)=\underbrace{f''(a)}_{=0}+\underbrace{f'''(a)}_{=0}(x-a)+\ldots +\underbrace{\frac{f^{(k-1)}(a)}{(k-3)!}}_{=0}(x-a)^{k-3}+\underbrace{\frac{f^{(k)}(c_3)}{(k-2)!}}_{\neq 0}(x-a)^{k-2}\]

where \(c_1, c_2, c_3\) are some numbers between \(x\) and \(a\). Combining the last three equations gives

\[g'(x)=\frac{\frac{f^{(k)}(c_1)}{k!}(x-a)^k\frac{f^{(k)}(c_3)}{(k-2)!}(x-a)^{k-2}}{\left[\frac{f^{(k)}(c_2)}{(k-1)!}(x-a)^{k-1}\right]^2}\xrightarrow{x\rightarrow a}\frac{\left[f^{(k)}(a)\right]^2}{\left[f^{(k)}(a)\right]^2}\frac{[(k-1)!]^2}{k!(k-2)!}=\frac{k-1}{k}\]

Since \(g'(a)=(k-1)/k<1\), there is an interval \((a-\delta,a+\delta)\) where \(|g'(x)|\leq L<1\) and thus, \(g\) is a contraction.

However, in all these cases, convergence is limited to be only linear, since \(g'(a)\neq 0\).

Caution: If we know, or suspect, that \(f(x)\) may have a multiple root, then Newton’s method is only safe (albeit slow) when we can write an analytic formula for \(f(x)/f'(x)\) and perform any cancellations “on paper” to avoid division by zero. Otherwise, for example in the case where both \(f\) and \(f'\) are given as black-box computer functions, any roundoff error in the value of the numerator or denominator could cause severe instabilities, by dividing two (inaccurate) near-zero quantities.