Error Analysis and Newton’s Method

MME 523      9/16/03

 

I am assuming by now that you have gotten Newton’s Method to work for you in both Excel and Maple. If this is not the case, I will be happy to help you clear up any problems.   This activity might be called “Numerical Methods” in many curricula – algorithms for approximating answers to problems that don’t yield nice, symbolic solutions.

 

Here we are interested in a little of the Numerical Analysis.  This means examining issues such as error analysis and efficiency of algorithms.  Right now we are specifically interested in how the accuracy of Newton’s increases with each iteration (step). To be more quantitative, we’d like to see how xn+1   and xn compare proportionally.  We know from the basic derivation that

 

                                                xn+1   = xn  -  f(xn)/f’(xn)

 

what we would like is instead something showing the ratio between xn+1   and xn.  One can use Taylor’s Formula and Newton’s Method to show that if  r denotes the real root then the error after n+1 and n iterations compares as

 

                                    | xn+1   - r | < (M/2m) | xn – r| 2

 

where:

                        M = max of abs value of second derivative of  f  on the interval you use

                             = max | f’’(x) |

                             = maximum curvature of graph

 

                        m = the minimum of | f’(x) | on the interval

                            = minimum slope on graph

 

The square on the right hand side is numerically most noteworthy! It means the accuracy may double at each step for reasonable M and m values!!  In other words, Newton’s is really fast in some cases!

 

How do you get M and m??  You could do it by hand but this is a nightmare in most cases. Better to use Maple, let it differentiate and plot and you just read off the values.

Problem 1:

Lets analyze finding  the square root of 2.  Clearly it’s in [1,2].  Estimate M and m.  Then estimate the biggest that  |x6 – Ö2 |  might be  if we take an initial guess as 1.5

 

Problem 2:   in each that follows, use Newton’s Method to estimate the root to 6 decimal places.  Also generate an error estimate as discussed above and check to see if the actual results did at least as well as theory predicted (improved as quickly). You will need Maple to estimate M and m  in each case. Pick one problem and compare how many steps the Bisection Method would have taken.

 

a)  x3 – 3x2 + 3  = 0   on  [2,3]

b)  x3 + 2x2 – x + 1 = 0  on  [-3, -2 ]

c)  sin(x) = x2  on [0,  Pi]

d)  cos(x) = x – 1  on [0, Pi/2]

e)  find a solution to  x6 – x5 + x3 = 3  to  5 places

 

Problem 3: 

Show that Newton’s Method fails for the problem

 

            9x4 – 16x3 – 36x2 +96x – 60 = 0    with x0 = 4/3

 

any thoughts on why?

 

Problem 4:   compute the 4th root of 47 to 5 places

 

Problem 5:  The Babylonians approximated square roots of integers by the following scheme:

 

                        xn+1   = ( xn  + N/ xn )/2

 

where N is the integer whose square root we want. 

 

a) try this out for an integer of your choice

b) show that it is consistent with Newton’s Method by deriving it.