Convergence of Newton's method for polynomials

610 Views Asked by At

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$ .

1

There are 1 best solutions below

3
On

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!