Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 2, 2004 #1
    Problem

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

    [tex] x_{n+1} = x_n - \frac{f(x_n)}{f^{\prime}(x_n)} [/tex]

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

    [tex] \left| x_{n+1} - r \right| \leq \frac{M}{2K}\left| x_n - r \right| ^2 [/tex]

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

    Comments

    I'm acquainted with Newton's method

    [tex] x_{n+1} = x_n - \frac{f(x_n)}{f^{\prime}(x_n)} [/tex]

    and Taylor's Inequality

    [tex] \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 [/tex]

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

    If

    [tex] \int _{x_n} ^{r} f^{\prime \prime} (t) \, dt \leq \int _{x_n} ^{r} M \, dt [/tex]

    [tex] f^{\prime} (r) - f^{\prime} (x_n) \leq M (r-x_n) [/tex]

    [tex] f^{\prime} (r) \leq f^{\prime} (x_n) + M (r-x_n) [/tex]

    Then

    [tex] \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 [/tex]

    [tex] 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 [/tex]

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

    Thank you :smile:
     
  2. jcsd
  3. Dec 2, 2004 #2
    I would suggest that you consider the function [tex]g(x)=x-\frac{f(x)}{f^{'}(x)}[/tex], using Taylor's inequality. Note that [tex]R_n(x)[/tex] can be expressed as [tex]|x_{n+1}-r|[/tex]. Also, after differentiating g(x) once, you may need an estimate for |f(x)|. You may obtain such by noting that [tex]f(x)=\int^{x}_{r}f^{'}(y)dy[/tex]
     
    Last edited: Dec 2, 2004
  4. Dec 3, 2004 #3
    This seems close, but I'm not 100% sure.

    [tex] 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)} [/tex]

    Let's rewrite that as follows

    [tex] 0 = f(x_n) + f^{\prime}(x_n) (r-x_n) [/tex]

    which is the first-degree Taylor polynomial approximation to [tex] r [/tex].

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

    [tex] 0 = f(x_n) + f^{\prime}(x_n) (r-x_n) + \frac{f^{\prime \prime}(x_n)}{2} (r-x_n) ^2 [/tex]

    Then

    [tex] 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 [/tex]

    [tex] 0 = -(x_{n+1}-x_n) + (r-x_n) + \frac{f^{\prime \prime}(x_n)}{2f^{\prime}(x_n)} (r-x_n) ^2 [/tex]

    [tex] 0 = r - x_{n+1} + \frac{f^{\prime \prime}(x_n)}{2f^{\prime}(x_n)} (r-x_n) ^2 [/tex]

    [tex] r - x_{n+1} = - \frac{f^{\prime \prime}(x_n)}{2f^{\prime}(x_n)} (r-x_n) ^2 [/tex]

    [tex] \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 [/tex]

    [tex] \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 [/tex]
     
    Last edited: Dec 3, 2004
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook