newtons_method

Newton's Method for Root Finding

Overview

Newton's method (also known as the Newton-Raphson method) is an iterative algorithm for finding successively better approximations to the roots (or zeroes) of a real-valued function.

Given a function f(x) and an initial guess x_0, the method produces a sequence of approximations using the formula:

x_{n+1} = x_n - f(x_n) / f'(x_n)

At each step, the algorithm:

1. Evaluates the function at the current guess
2. Constructs the tangent line to the curve at that point
3. Uses the x-intercept of the tangent line as the next guess

Under favorable conditions, the method converges quadratically to the root.

Visualizations

Example 1: f(x) = x^2 - 57, starting at x = 9

The method converges to the square root of 57 (approximately 7.5498):

Example 2: f(x) = x^2 - 1, starting at x = 3

The method converges to x = 1 (a root of x^2 - 1):

In each plot:

• The green curve is the function f(x)
• Blue dots on the x-axis are the successive guesses
• Red dots on the curve show where f is evaluated
• Blue lines are the tangent lines at each iteration
• Dashed gray lines connect each guess to the curve

Files

File	Description
sage_code	Original SageMath implementation
newtons_method.py	Python 3 translation with matplotlib visualization
newtons_method_x2_57.png	Visualization for f(x) = x^2 - 57
newtons_method_x2_1.png	Visualization for f(x) = x^2 - 1

How to Run

python3 newtons_method.py

You can also run the original SageMath code on SageMathCell.

Key Takeaways

• Newton's method converges very quickly (quadratic convergence) when the initial guess is close to the root
• The method requires the derivative f'(x) to be known
• It may fail to converge if the initial guess is too far from the root, or if f'(x) = 0 at some iteration