Convergence rate of Newton's method

Let $f(x)$ be a polynomial in one variable $x$ and let $\alpha$ be its $\delta$-multiple root ($\delta\ge2$).

Show that in the Newton's $x_{k+1}=x_k-f(x_k)/f'(x_k)$, the rate of convergence to $\alpha$ is not quadratic.

My solution: Suppose that $\alpha$ is one regular root of equation.Then $$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}=\phi(x_k)$$ convergence rate to $\alpha$:

$$x_k-\alpha=\phi(x_k)-\phi(\alpha)=(x_k-\frac{f(x_k)}{f'(x_k)})-(x-\frac{f(x)}{f'(x)})$$ $$(x_k-\alpha)=(f'(x_k))^{-1}(f(x_k)-f(x))=(x_k-\alpha)+(f'(x_k))^{-1}\{ f'(x_k)(x_k-\alpha)+O((x_k-\alpha)^2)\}=f'(x_k)^{-1}O((x_k-\alpha)^2)) \tag{1}$$

so the convergence rate to $\alpha$ is quadratic.

But if $\alpha$ is not regular root, then $(f'(x))^{-1}$ has no meaning. We need do slightly change in $(1)$, $$(x_k-f'(x_k)^{-1}f(x_k))-(x-f^{(\delta)}(x)\delta!f(x))=(x_k-x)-f'(x_k)(f(x_k)-f(x))$$ $$=(x_k-x)-f'(x_k)^{-1}(\frac{f^{(\delta)}(x_k) (x_k-x)^{\delta}}{\delta!}+O((x_k-x)^{\delta+1}))$$

convergence rate to non regular root $\alpha$ is one.

Is my solution correct?

Then I do same thing to next nonlinear equation:

$$f(x)=x^2(x-1) $$, m is integer.

so the newton's formula is above, and how about convergence rate to $0,1$? I think convergence to 1 is one, absolutely convergence to 0 is quadratic. when convergence rate is 1, the how about the convergence rate?

Solution 1:

For iterative methods, we have a fixed point formula in the form:

$$\tag 1 x_{n+1} = g(x_n)$$

The Newton iteration is given by:

$$\tag 2 \displaystyle x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

So, $(2)$ is of the form $(1)$.

Since $r$ is a root of $f(x) = 0, r = g(r)$. Since $x_{n+1} = g(x_n)$, we can write:

$$x_{n+1} - r = g(x_n) - g(r).$$

Lets expand $g(x_n)$ as a Taylor series in terms of $(x_n -r)$, with the second derivative term as the remainder:

$$g(x_n) = g(r)+g'(r)(x_n-r) + \frac{g''(\xi)}{2}(x_n-r)^2$$

where $\xi$ lies in the interval from $[x_n, r]$, since:

$$g'(r) = \frac{f(r)f''(r)}{[f'(r)]^2} = 0.$$

Because $f(r) = 0$ ($r$ is a root), we have:

$$g(x_n) = g(r) + \frac{g''(\xi)}{2}(x_n-r)^2.$$

Letting $x_n-r = e_n$, we have:

$$e_{n+1} = x_{n+1}-r = g(x_n) - g(r) = \frac{g''(\xi)}{2}(e_n)^2.$$

Each successive error term is proportional to the square of the previous error, that is, Newton's method is quadratically convergent.

Multiple Root

Following the same sort of reasoning, if $x_n$ is near a root of multiplicity $\delta \ge 2$, then:

$$f(x) \approx \frac{(x-\xi)^\delta}{\delta !}f^{(m)}(\xi)$$

$$f'(x) \approx \frac{(x-\xi)^{\delta-1}}{(\delta-1) !}f^{(m)}(\xi)$$

So we have:

$$\tag 3 x_{n+1} -\xi = x_n - \xi -\frac{f(x_n)}{f'(x_n)} = \left(\frac{\delta -1}{\delta}\right)(x_n - \xi)$$

The $\delta$ term on the RHS of $(3)$ in not quadratic, hence we have linear convergence.

You should be able to use with your approach to clean up what you did.

I am confused about what you wrote after your derivation, but I am going to guess that you want to figure out the convergence rate for this $f(x)$.

We are given:

$$f(x) =x^2(x-1)$$

There are two roots to this equation at:

• $x = 0$ (a double root)
• $x = 1$ (a single root)

So, we would expect linear convergence at the double root and quadratic convergence at the single root.

The Newton iteration is given by:

$$x_{n+1} = x_n - \frac{(x_n-1) x_n^2}{x_n^2+2 (x_n-1) x_n}$$

For the first root, lets pick a starting point of $x = 0.1$, we get the following cycle:

• $24$ steps to converge to the root $x = 5.341441708552285 \times 10^{-9}$ (yikes!)

For the second root, lets pick a starting point of $x = 1.4$, we get the following cycle:

• $6$ steps to converge to the root $x = 1.000000000000000$ (much better!)

Now, you would use the exact results and compare them numerically and show the convergence rates for each of the cases.

Note: one must choose a sufficient starting point that will converge to one root or the other. Based on that initial selection, the rate is going to be quadratic when the algorithm converges to $1$ and linear when it converges to $0$. We pick a nearby starting point and see where we end up. You could also graph the function to have an idea about starting points. We typically do not know apriori what roots will give us what behavior. Obviously there is a range where convergence happens to one root or the other. I am not sure how one would calculate that analytically because you may as well figure out the roots without numerical methods in that case.

Solution 2:

You are making it too hard.

If $x_{k+1}=x_k-af(x_k)/f'(x_k) $ and $f(x_k)$ is small and $f'(x_k)$ is bounded away from zero, then, since $f(x+h) =f(x)+hf'(x)+O(h^2) $,

$\begin{array}\\ f(x_{k+1}) &=f(x_k-af(x_k)/f'(x_k))\\ &=f(x_k)-(af(x_k)/f'(x_k))f'(x_k)+O((af(x_k)/f'(x_k))^2\\ &=f(x_k)-af(x_k)+O((f(x_k)/f'(x_k))^2)\\ &=f(x_k)(1-a)+O((f(x_k)/f'(x_k))^2)\\ \end{array}\\ $

If $a=1$ then $f(x_{k+1}) =O((f(x_k)/f'(x_k))^2) $ and the convergence is quadratic.

If $a\ne 1$ then $f(x_{k+1}) =f(x_k)(1-a)+O((f(x_k)/f'(x_k))^2) $ and the convergence is linear.