1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Taylor's Inequality/Newton's Method (Tips, Please)
  1. Newton's Methods (Replies: 6)

Loading...