1
$\begingroup$

I have been recently taught Newton's method for finding roots of non-linear equations. I was told in class that if the multiplicity of the root is more than 1, then the order of convergence is not quadratic. We can compute the multiplicity of root using the usual Newton's method and it also gives approximate root. Now modified Newton's method involves multiplying $f(x)/f'(x)$ by the multiplicity of the root.

First thing I want to ask is that does this method always have an order of convergence of 2?

The second thing I want to ask is what's the use of modified Newton's method when we can get an approximate root using the normal method and isn't it a lengthy process to first calculate multiplicity and then use that to run a loop to calculate the root?

$\endgroup$
3
  • $\begingroup$ Note that if you know a priori you are searching for a root of order $m$, then you need not calculate the order of the root in your code and simply use the user-inputted multiplicity $m$ from the beginning of your iteration $\endgroup$
    – eepperly16
    Commented Jan 29, 2019 at 8:15
  • $\begingroup$ You can also mix both approaches and double the next step if the reduction in function value is be less than one-half. $\endgroup$ Commented Jan 29, 2019 at 9:39
  • $\begingroup$ I never heard that Newton's method allows you to compute the multiplicity of a root. $\endgroup$
    – user65203
    Commented Jan 29, 2019 at 10:04

2 Answers 2

6
$\begingroup$

The convergence for multiplicity $m$ is geometric with factor $1-\frac1m$. This means that you need more than 3 iterations for each digit of the result. Thus you can both detect the slow convergence and test for the behavior at a multiple root, and also speed up the computation of the remaining digits with the modified method. So if after say 5 or 10 iterations you detect that the reduction in step size is by a factor less than $1/2$, you can compute $m$ from the factor and apply the modified Newton method.

Note that due to floating point errors a multiple root of $f(x)$ will most likely manifest as a root cluster of size $\sqrt[m]\mu$ where $\mu$ is the machine constant. As also $f'(x)$ converges to $0$ at the multiple root, floating point errors will contribute a substantial distortion so that the computed Newton iterates can behave chaotically if the method is continued after reaching the theoretically possible maximum precision $\sqrt[m]\mu$.


One example is to take the expansion of $(x-5/7)^5$ in floating point coefficients and compute the roots of it. One finds the coefficient sequence

[ 1.         -3.57142857  5.10204082 -3.64431487  1.30154102 -0.18593443] 

and with a supplied root-finding method the roots

[0.71518695+0.j         0.7145639 +0.00085702j 0.7145639 -0.00085702j
 0.71355691+0.0005293j  0.71355691-0.0005293j ]

in accordance with the prediction of a root cluster of radius $\sqrt[5]{10^{-15}}=10^{-3}$.

To get an impression of what the numerical Newton method "sees" of this function, plot relevant quantities over intervals of radius $10^{-1},10^{-2},5\cdot 10^{-5}$ around the real root location. In the first row the graph of the floating point evaluation of the polynomial, then the unmodified Newton step, the quotient of the step sizes of two steps and lastly the modified Newton step, in blue with the computed multiplicity, in red with fixed multiplicity $5$.

One sees that well away from the root one gets geometric convergence with factor $0.8=1-\frac15$ towards the center of the cluster at $5/7=0.7143$. However getting close to the root the function value gets fuzzy over a rather long stretch of arguments, the Newton step takes rather random values. The fixed points are where the diagonal intersects the graph of the Newton step, the most massive part of it is in the segment $[0.7150, 0.7152]$.

So after a few iterations the multiplicity is correctly detected, and one step of the modified method gets as close to the root as one can get, the next iterations will most likely oscillate around the interval $[0.7150, 0.7152]$. Any value in that interval is a valid root approximation.

diverse plots on the Newton iteration

$\endgroup$
3
$\begingroup$

The rationale of the modified method is that in case of a root of multiplicity $n$,

$$\sqrt[n]{f}$$ has a simple root.

Then, the increment of the modified function is

$$\frac{\sqrt[n]{f}}{(\sqrt[n]{f})'}=n\frac f{f'}.$$

As the root is simple, quadratic convergence is restored (as long as the numerical errors allow it, see @lutzl's answer.).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .