Taylor's Inequality/Newton's Method (Tips, Please)

[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 :cry:):

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 :smile:

[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