Newton’s Method

Return to List of Lectures

Previous Lecture

• Questions?
• Newton’s Method
  • Video
    • Method for approximating roots of function
    • Use tangent at x to guess refined x = x - deltaX
      • deltaX = f(x)/f′(x)
    • Pseudocode for algorithm:
      

      newton( f, fPrime, x, tolerance )
          relativeDelta = tolerance * 2
          while relativeDelta > tolerance
              deltaX = f(x) / fPrime(x)
              relativeDelta = | deltaX / x |
              x = x - deltaX
          end
          return x

  • Examples and algorithms
    • Working by hand through a couple of examples of a problem helps you…
      • Understand the problem
      • Find or understand algorithms for solving it
      • Develop cases for testing programs for the problem
  • Example(s) for Newton’s method
    • Example 1: f(x) = x² - 4, x = 1, f′(x) = 2x, tolerance = 1/4
      • Initially: relativeDelta = 1/2, x=1
      • End of iteration 1: , deltaX = 3/2, relativeDelta = 3/2, x = 5/2
      • End of iteration 2: deltaX = 9/20, relativeDelta = 18/100, x = 2.05
      • Result: x = 2.05
    • Example 1a: same f, x = 2
      • Good test case to see if programs handle the unusual case of an initial guess that happens to be the root
    • Other examples
      • f(x) = sinx (root at x=0 among many other places), x=1
      • f(x) = e^x (pathological, does Newton diverge towards -∞ as expected)
      • f(x) = e^x - 1 (almost pathological, root at x=0)
• Next
  • Passing functions to other functions - function handles
  • Read sections 14.3 and 14.4 of textbook

Next Lecture