# Convergence of Newton's method for polynomials

Let $p(x)=a_0+ a_1x....+ a_{n-1}x^{n-1}+a_nx^n,$ $n\ge 2$, be a polynomial with $a_n\neq 0$ and with all its roots real.

Assume that its roots are $$\lambda_1\leq\lambda_2\leq \ldots\leq \lambda_n.$$

Then how can I show that the Newton's method converges for all $x_0 ≥ λ_n$ to $λ_n$ .

If $p(x)=(x-\lambda_1)\cdots(x-\lambda_n)$, then $$\frac{p'(x)}{p(x)}=\frac{1}{x-\lambda_1}+\cdots+\frac{1}{x-\lambda_n},$$ and the sequence obtained by Newton's method is given by $$x_{k+1}=x_k-\frac{p(x_k)}{p'(x_k)}, \quad k\in\mathbb N.$$ If $x_1=\lambda_n$, then clearly, $x_k=\lambda_n$, for all $k$. Assume that $x_k>\lambda_n$.
Then $$x_{k+1}-\lambda_n=x_k-\lambda_n-\frac{1}{\frac{1}{x_k-\lambda_1}+\cdots+\frac{1}{x_k-\lambda_n}}=\frac{1}{\frac{1}{x_k-\lambda_n}}-\frac{1}{\frac{1}{x_k-\lambda_1}+\cdots+\frac{1}{x_k-\lambda_n}}>0.$$ Also, $$x_{k+1}-\lambda_n=x_k-\lambda_n-\frac{1}{\frac{1}{x_k-\lambda_1}+\cdots+\frac{1}{x_k-\lambda_n}}\le x_k-\lambda_n-\frac{1}{\frac{1}{x_k-\lambda_n}+\cdots+\frac{1}{x_k-\lambda_n}} \\ =x_k-\lambda_n-\frac{1}{\frac{n}{x_k-\lambda_n}}=\frac{n-1}{n}(x_k-\lambda_n).$$ Altogether $$0<x_{k+1}-\lambda_n\le \frac{n-1}{n}(x_k-\lambda)\le\cdots \le \left(\frac{n-1}{n}\right)^k(x_1-\lambda_n)\to 0,$$ and hence $x_k\to\lambda_n$.
Note. In reality $x_k\to\lambda_n$ much faster that exponentially fast!
• @ Yiorgos S. Smyrlis How yow get that $x_k-\lambda_n =\frac{1}{\frac{1}{x_k-\lambda_n}}$ in the first one and $\frac{n-1}{n}$ in the second one? – F.O May 19 '18 at 11:32
• @FarhanOmar In both cases, use the fact that $$\frac{a}{b}=\frac{1}{\frac{b}{a}}$$ – Yiorgos S. Smyrlis May 19 '18 at 11:35