Newton’s Method Algorithms

Return to List of Lectures

Previous Lecture

• Misc
  • Solution to numerical integration lab is online via exercises page
  • Math colloquium
    • Today, 2:30 PM
    • Newton 201
    • Tony Macula, Geneseo
    • “An Example of Using Maple in Abstract Algebra”
    • Extra credit for going and writing summary
• Questions?
• Newton’s Method
  • Process
    • x_i+1 = x_i - f(x_i)/f′(x_i)
    • ε_a = 100 | (x_i+1 - x_i)/x_i+1 |
    • Check |ε_a| ≤ |ε_s|
    • Repeat if not until |ε_a| ≤ |ε_s|
  • Slightly more detailed pseudocode algorithm
    

    function newton( f, x )
        εs = ...some small number ...
        εa = ... some large number ...
        % x is current estimate
        % x1 next estimate
        while |εa| > εs
            x1 = x - f(x) / f′(x)
            εa = 100 | (x1 - x)/x1 | 
            x = x1
        return x1

• How to Numerically Differentiate a Function?
  • Classic definition of derivative: lim_h→0 ( f(x+h) - f(x) ) / h
  • “Centered difference quotient” is usually numerically more accurate
    • lim_h→0 ( f(x+h) - f(x-h) ) / 2h
      
  • This is computable:
    

    function derivative( f, x )
        h = ... some small value ...
        return ( f(x+h) - f(x-h) ) / (2h)

• Next
  • If statements
  • Read sections 4.1 - 4.3
  • Optional video lecture at http://www.see.ed.ac.uk/teaching/courses/matlab/unit04/if-else-statement.shtml

Next Lecture