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!

  • $\begingroup$ @ 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? $\endgroup$ – F.O May 19 '18 at 11:32
  • $\begingroup$ @FarhanOmar In both cases, use the fact that $$\frac{a}{b}=\frac{1}{\frac{b}{a}}$$ $\endgroup$ – Yiorgos S. Smyrlis May 19 '18 at 11:35
  • $\begingroup$ @ Yiorgos S. Smyrlis thank you for clarification . $\endgroup$ – F.O May 19 '18 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.