Using Taylor's inequality to prove Newton's method error bound

[DivGradCurl]

Problem

Newton's method gives an approximation to a root $$r$$ of the equation $$f(x)=0$$. From an initial approximation $$x_1$$ we obtain successive approximations $$x_2 , x_3 , \ldots ,$$ where

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

Use Taylor's Inequality with $$n=1$$, $$a=x_n$$, and $$x=r$$ to show that if $$f^{\prime \prime} (x)$$ exists on an interval $$I$$ containing $$r$$, $$x_n$$, and $$x_{n+1}$$, and $$\left| f^{\prime \prime} (x) \right| \leq M$$, $$\left| f^{\prime} (x) \right| \geq K$$ for all $$x \in I$$, then

$$\left| x_{n+1} - r \right| \leq \frac{M}{2K}\left| x_n - r \right| ^2$$

[This means that if $$x_n$$ is accurate to $$d$$ decimal places, then $$x_{n+1}$$ is accurate to about $$2d$$ decimal places. More precisely, if the error at stage $$n$$ is at most $$10^{-m}$$, then the error at stage $$n+1$$ is at most $$\left( \frac{M}{2K} \right) 10^{-2m}$$ .]

Comments

I'm acquainted with Newton's method

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

and Taylor's Inequality

$$\left| R_n (x) \right| \leq \frac{M}{\left( n+1 \right) !} \left| x-a \right| ^{n+1} \qquad \mbox{ for } \left| x-a \right| \leq d$$

However, it's not clear to me how I can join those concepts. Here is what I tried to do (without success ):

If

$$\int _{x_n} ^{r} f^{\prime \prime} (t) \, dt \leq \int _{x_n} ^{r} M \, dt$$

$$f^{\prime} (r) - f^{\prime} (x_n) \leq M (r-x_n)$$

$$f^{\prime} (r) \leq f^{\prime} (x_n) + M (r-x_n)$$

Then

$$\int _{x_n} ^{r} K \, dt \leq \int _{x_n} ^{r} f^{\prime} (t) \, dt \leq \int _{x_n} ^{r} \left[ f^{\prime} (x_n) + M (t-x_n) \right] \, dt$$

$$K (r-x_n) \leq f (r) - f(x_n) \leq f^{\prime}(x_n)(r-x_n) + \frac{M}{2} (r-x_n) ^2$$

I just need some tips. I probably am in the wrong direction.

Thank you

 

[Inquisitive_Mind]

I would suggest that you consider the function $$g(x)=x-\frac{f(x)}{f^{'}(x)}$$, using Taylor's inequality. Note that $$R_n(x)$$ can be expressed as $$|x_{n+1}-r|$$. Also, after differentiating g(x) once, you may need an estimate for |f(x)|. You may obtain such by noting that $$f(x)=\int^{x}_{r}f^{'}(y)dy$$

 

[DivGradCurl]

This seems close, but I'm not 100% sure.

$$x_{n+1} = x_n - \frac{f(x_n)}{f^{\prime}(x_n)} \Longrightarrow r \approx x_n - \frac{f(x_n)}{f^{\prime}(x_n)}$$

Let's rewrite that as follows

$$0 = f(x_n) + f^{\prime}(x_n) (r-x_n)$$

which is the first-degree Taylor polynomial approximation to $$r$$.

In order to gain further insight through Taylor's Inequality, we may find the second-degree Taylor polynomial approximation to $$r$$. Thus, we have

$$0 = f(x_n) + f^{\prime}(x_n) (r-x_n) + \frac{f^{\prime \prime}(x_n)}{2} (r-x_n) ^2$$

Then

$$0 = \frac{f(x_n)}{f^{\prime}(x_n)} + (r-x_n) + \frac{f^{\prime \prime}(x_n)}{2f^{\prime}(x_n)} (r-x_n) ^2$$

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

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

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

$$\left| r - x_{n+1} \right| = \frac{\left| f^{\prime \prime}(x_n) \right|}{2\left|f^{\prime}(x_n)\right|} \left| r-x_n \right| ^2$$

$$\left| r - x_{n+1} \right| \leq \frac{M}{2K} \left| r-x_n \right| ^2 \Longleftrightarrow \left| x_{n+1} - r \right| \leq \frac{M}{2K} \left| x_n - r \right| ^2$$