Newton's Method for Optimization

Problem

Implement Newton's method for finding the minimum of a single-variable function. Given a function, its first derivative, and its second derivative, iteratively update the estimate until convergence.

Solution

def newtons_method(f, df, ddf, x0: float, tol: float = 1e-6, max_iter: int = 100) -> float:
    x = x0
    for _ in range(max_iter):
        first_deriv = df(x)
        second_deriv = ddf(x)
        if abs(second_deriv) < 1e-12:
            break
        x_new = x - first_deriv / second_deriv
        if abs(x_new - x) < tol:
            return round(x_new, 6)
        x = x_new
    return round(x, 6)

Explanation

1. Start at initial guess x0.
2. At each iteration, compute the update: x_new = x - f'(x) / f''(x).
3. This uses a local quadratic approximation of the function to jump to the estimated minimum.
4. Stop when the change is below the tolerance or max iterations are reached.
5. Guard against near-zero second derivative to avoid division issues.

Complexity

• Time: O(k) where k is the number of iterations (typically converges quadratically)
• Space: O(1)