Newton's Method: finding more than one root?

178 Views Asked by At

I'm reading Wiki's page on Netwon's Method for root finding. I understand more than one root can be found, however unsure how it is accomplished. For instance, if the polynomial is degree $n$ it will have $n$ roots. Does anyone know how to accomplish this?

$$ x_{0A} = a, x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$

I recall reading something about repeating the process from $x_{0B} = x - a / 2$, however unsure what the variables in this are.

1

There are 1 best solutions below

3
On

Since this does provide one answer to your question (there are others), I'll make it official and walk you through an example. Suppose I want to find the roots of $f(x) = \sin x$ but somehow have no real idea how this function behaves. I calculate the recursion formula $$x_{n+1} = x_n - \frac{\sin x_n}{\cos x_n}=x_n - \tan x_n$$ I arbitrarily choose $x_0 = 1$ and start calculating $$\begin{array}{rl}x_0&\phantom{-}1\\x_1&-0.557407724654902\\x_2&\phantom{-}0.065936451924841\\x_3&-0.000095721919325\\x_4&\phantom{-}0.000000000000293\\x_5&\phantom{-}0\end{array}$$ (With perfect computing $x_5$ would not be zero. But in this special case, computing error has paid off with a direct hit.)

In general, after finding a root $r_0$, to get the next root, replace $f(x)$ with $f_1(x) = \frac{f(x)}{x-r_0}$. Then $$f_1'(x) = \frac{f'(x)(x - r_0) - f(x)}{(x - r_0)^2}$$ And the recursion formula becomes $$x_{n+1} = x_n - \frac{f_1(x_n)}{f_1'(x_n)} = x_n - \dfrac {(x_n - r_0)f(x_n)}{f'(x_n)(x_n - r_0) - f(x_n)}$$

For my example, $r_0 = 0$, so $f_1(x) = \frac {\sin x}x$. This isn't defined at $0$, but $\lim_{x \to 0} \frac{\sin x}x = 1$, so if we needed to, we could define $f_1(0) = 1$. But there really isn't a point. We've already found $0$ and are looking for a different root. Why would we want to put the root we've already found back in? It might turn up as a point in the recursion, but this is so unlikely I wouldn't bother with it.

So I calculate the new recursion formula: $$x_{n+1} = x_n - \frac {x_n\sin x_n}{x_n\cos x_n - \sin x_n} = x_n - \dfrac {1}{\cot x_n - \frac 1{x_n}}$$ And arbitrarily start off with $x_0 = 1$ again: $$\begin{array}{rl}x_0&1\\x_1&3.79401891249195 \\x_2&2.83731861081935\\x_3&3.12005206105673\\x_4&3.14144824538471\\x_5&3.14159264695285\\x_6&3.14159265358979 \end{array}$$ An interesting alternative approach is to just do one or two iterations of the new formula, then switch back to the original $x_{n+1} = x_n - \tan x_n$: $$\begin{array}{rl}x_0&1\\x_1&3.79401891249195 \\\hline x_2&3.14205845439180\\x_3&3.14159265355610\\x_4&3.14159265358979 \end{array}$$

Why does this work? Remember that $f_1$ is just $f$ modified to remove the first root. The roots of $f_1$ are also roots of $f$, and with the exception of that first root, the roots of $f$ are roots of $f_1$. The problem is that my starting value of $1$ happens to be in a region where the original formula converges to the root $0$. Different starting values may converge to other roots, but I have no idea what values to try. For well-behaved functions, Newton's method should move me towards a root. So using the 2nd formula for a single iteration moves me from $1$ to $\sim 3.794$, which is close enough to another root for the original iteration to converge to $\pi$ instead of $0$.