newtons-method.md

← Return to Index

Newton's Method

Another method of finding the roots of a function f(x).

Algorithm

1. Set n = 0 and make an initial guess, X₀
2. Compute X_n+1 = X_n - f(X_n)/f'(X_n)
3. If |X_n+1 / X_n | < threshold
   • Return X_n+1
4. Else, go to step 2

Intuition

• h = X₀ - X₁
• tan(θ) = f(X₀)/h
• Tangent of a curve f(X) at a point X₀ is f'(X₀)
• f'(X₀) = f(X₀)/h
• h = f(X₀)/f'(X₀) = X₀ - X₁
• Hence, X₁ = X₀ - f(X₀)/f'(X₀)

Limitations

Although Newton's method is a very powerful technique, and it converges on the root much faster than the Interval Bisection method:

• Calculating the derivative may be difficult or expensive
• The derivative may be 0 and will halt due to divison by 0
• May fail to converge
  • e.g. if f(x) = 1 - x² and initial guess is 0