User:Matt Kwan/Newton's Method

to prove: if $f(a)<0,f(b)>0,f'(x)>0,f''(x)>0\!$, then Newton's method $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$ converges; $\lim _{n\rightarrow \infty }x_{n}=r$ such that f(r)=0.

${\begin{aligned}g_{n}(x)&=f'(x_{n})(x-x_{n})+f(x_{n})\\g_{n}(x_{n}+h)&=hf'(x_{n})+f(x_{n})\\{\frac {f(x_{n}+h)-f(x_{n})}{h}}&=f'(c),c>x_{n}\\f(x_{n}+h)&=hf'(c)+f(x_{n})\\&>g_{n}(x_{n}+h)\end{aligned}}$

Now define $h_{1}$ and $h_{2}$ such that $g_{n}(x_{n}+h_{1})=0,f(x_{n}+h_{2})=0\!$. If $h_{1}\leq h_{2}$, then $g_{n}(x_{n}+h_{1})=f(x_{n}+h_{1})+k,k\geq 0$, so $g_{n}(x_{n}+h_{1})\geq f(x_{n}+h_{1})$, a contradiction. So $h_{1}>h_{2},x_{n}+h>r\!$.

$g_{n}(x_{n}+h)=0$ implies $x_{n}+h=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$ so $f\left(x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\right)=f(x_{n+1})>f(r)>0$.

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$ so $x_{n+1}<x_{n}$ for n>0 so $f(x_{n+1})<f(x_{n})$ so $f(x_{1})>f(x2)>\cdots >0$ so $x_{1}>x2>\cdots >r$ so by the monotone sequence theorem, $x_{n}$ converges. So $\lim _{n\rightarrow \infty }\left(x_{n}-x_{n+1}\right)=0$. But $f(x_{n})=f'(x_{n})(x_{n}-x_{n-1})\!$ and $f'(x_{n})\leq \max \left\{f'(x):r\leq x\leq x_{1}\right\}$ so $\lim _{n\rightarrow \infty }f(x_{n})=0$ so $x_{n}\rightarrow r$ as required.