Newton's Method

Newton's method, also called the Newton–Raphson method, approximates a root using the function value and its first derivative at the current point. It replaces the nearby curve by its tangent line and uses that line's zero as the next approximation. This is an open method: one starting guess is sufficient to define an update, and a sign-changing bracket is not required. Near a smooth simple root, a sufficiently close starting guess can give quadratic convergence. From an arbitrary starting point, however, the tangent may lead away from the root, leave the function's domain, or have an unusable slope. The derivation below separates the update formula from the assumptions that make it converge.

Physically and geometrically, Newton's method can be viewed as follows: starting from an initial guess $x_0$, you draw the tangent line to the curve $y = f(x)$ at the point $(x_0, f(x_0))$. The intersection of this tangent line with the $x$-axis provides a better approximation to the root than $x_0$, assuming certain conditions on the function and the initial guess. Repeating this procedure iteratively refines the approximation.

Conceptual Illustration:

Imagine the curve $f(x) = x^2 -4$:

At $x_0 = 3$, the tangent line is drawn. Its intersection with the x-axis is the next approximation $x_1$. Repeating this yields even better approximations rapidly converging to the exact root $x=2$.

Mathematical formulation

Let $f:\mathbb{R} \to \mathbb{R}$ be a differentiable function. We wish to solve:

$$ f(x) = 0 $$

Newton's method starts with an initial guess $x_0$ and generates a sequence $\{x_n\}$ defined by:

$$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$ where $f'(x)$ is the first derivative of $f(x)$.

Geometric Derivation:

Consider the first-order Taylor expansion of $f$ around $x_n$:

$$ f(x) \approx f(x_n) + f'(x_n)(x - x_n) $$

If $x$ is the root we want (i.e., $f(x)=0$), we set the above approximation to zero and solve for $x$:

$$ 0 = f(x_n) + f'(x_n)(x - x_n) \implies x = x_n - \frac{f(x_n)}{f'(x_n)} $$

This gives the iterative scheme for Newton’s method.

Derivation

Step 1: Assumption of differentiability.

We assume $f$ is at least once differentiable near the root. This allows us to use local linearization.

Step 2: Local linear approximation.

Near a guess $x_n$, write:

$$ f(x) \approx f(x_n) + f'(x_n)(x - x_n) $$

Step 3: Solving for the root of the linear approximation.

Set $f(x)=0$ in the linear approximation:

$$ 0 \approx f(x_n) + f'(x_n)(x - x_n) $$

Hence:

$$ x \approx x_n - \frac{f(x_n)}{f'(x_n)} $$

Step 4: Iteration.

Define:

$$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$

As $n \to \infty$, if the sequence converges, $x_n \to x^*$ where $f(x^*)=0$. Under suitable conditions (e.g., if $f$ is well-behaved and the initial guess is sufficiently close to the actual root), Newton's method converges quadratically to the root.

Deriving quadratic convergence

Let $r$ be a simple root, let $e_n=x_n-r$, and suppose $f$ has a continuous second derivative near $r$. Taylor expansion about $x_n$ gives, for a point $\xi_n$ between $r$ and $x_n$,

$$ 0=f(r)=f(x_n)-f'(x_n)e_n+\frac{f''(\xi_n)}{2}e_n^2. $$

Rearranging and substituting the Newton update yields

$$ e_{n+1}=e_n-\frac{f(x_n)}{f'(x_n)}=\frac{f''(\xi_n)}{2f'(x_n)}e_n^2. $$

If $x_n$ starts sufficiently close to $r$ and $f'(r)\ne0$, the factor stays bounded. The error is then squared at each step, explaining the rapid local convergence. This conclusion needs more than differentiability alone and gives no guarantee from an arbitrary starting point.

For a root of multiplicity $m>1$, substituting $f(x)=(x-r)^m h(x)$ instead gives $e_{n+1}\approx(1-1/m)e_n$: ordinary Newton iteration is usually only linear. If $m$ is known, the modified update $x_{n+1}=x_n-m f(x_n)/f'(x_n)$ restores quadratic convergence under the corresponding smoothness assumptions.

The numerical example below rounds values for display. Keep full precision in the actual iteration, since feeding rounded values back into the update can conceal the expected convergence rate.

Extension to nonlinear systems

For a vector equation $F(x)=0$ with $x\in\mathbb R^n$, the first-order model is $F(x_k+p)\approx F(x_k)+J_F(x_k)p$, where $J_F$ is the Jacobian. Set the model to zero, solve

$$ J_F(x_k)p_k=-F(x_k),\qquad x_{k+1}=x_k+p_k, $$

and recompute the Jacobian at the new point. This is a linear-system solve at each iteration, rather than an instruction to form $J_F^{-1}$ explicitly.

For example, take $F(x,y)=(x^2+y^2-5,\ x-y-1)^\top$ and start at $(1.5,0.5)$. The first correction solves

$$ \begin{bmatrix}3&1\\1&-1\end{bmatrix} \begin{bmatrix}p_x\\p_y\end{bmatrix} =\begin{bmatrix}2.5\\0\end{bmatrix}, $$

so $p_x=p_y=0.625$ and the new point is $(2.125,1.125)$. Further steps approach the root $(2,1)$. The repository's newton_raphson_system uses this Jacobian-based update. Singular or poorly conditioned Jacobians require the same care as small derivatives in the scalar method; see linear systems for the solve and residual concepts.

Algorithm steps

Input:

• A differentiable function $f(x)$.
• Its derivative $f'(x)$.
• An initial guess $x_0$.
• A tolerance $\epsilon > 0$ or maximum iteration count $n_{\max}$.

Initialization:

Set iteration counter $n = 0$.

Iteration:

Step 1. Evaluate $f(x_n)$ and $f'(x_n)$.

II. If $f'(x_n)=0$ (or the step $f(x_n)/f'(x_n)$ is not a finite number), the method cannot proceed (division by zero). Stop with an error or choose a new $x_n$. Only an exactly zero (or overflowing) derivative is rejected; a merely small derivative is legitimate when $f$ itself is small, so no absolute threshold is used.

Step 3. Update:

$$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$

Step 4. Check Convergence:

• If $|x_{n+1} - x_n| < \epsilon$, stop and return $x_{n+1}$. (The residual $|f(x_{n+1})|$ is not tested. A small step can coexist with a noticeable residual when the derivative is large, and rounding can also cause stagnation; the step test alone is not a residual guarantee.)
• If $n_{\max}$ iterations have been performed without meeting this test, stop with an error (non-convergence).

Step 5. Increment $n = n+1$ and repeat from step I.

Output:

• Approximate root $x_{n+1}$.
• Number of iterations performed, if tracked as a diagnostic. The repository function newton_raphson returns only the approximate point, rather than a point-and-count pair.

Example

Function:

$$ f(x) = x^2 - 4. $$

Known Root:

$x=2$ satisfies $f(2)=0$.

Apply Newton's Method:

• Initial guess: $x_0 = 3$.
• Derivative:

$$ f'(x) = 2x. $$

Iteration 1:

• $f(x_0) = f(3) = 3^2 -4 = 9-4=5$
• $f'(3)=2\cdot3=6$
• Update:

$$ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = 3 - \frac{5}{6} = 3 - 0.8333 = 2.1667 $$

Iteration 2:

• Evaluate $f(2.1667)= (2.1667)^2 -4 \approx 4.6945 -4=0.6945$
• Evaluate $f'(2.1667)=2\cdot 2.1667=4.3333$
• Update:

$$ x_2 = 2.1667 - \frac{0.6945}{4.3333} \approx 2.1667 - 0.1602 = 2.0065 $$

Iteration 3:

• Evaluate $f(2.0065)=(2.0065)^2 -4 \approx 4.0260 -4=0.0260$
• $f'(2.0065)=2\cdot2.0065=4.013.$
• Update:

$$ x_3 = 2.0065 - \frac{0.0260}{4.013}\approx 2.0065 - 0.00648 = 2.0000 $$

After a few iterations, we have $x_3 \approx 2.0000$, which is very close to the actual root $x=2$.

Advantages

1. Fast convergence makes Newton's method highly efficient when the initial guess is close to the actual root and $f'(x) \neq 0$, as it exhibits quadratic convergence.
2. Simplicity in implementation requires only evaluations of the function and its derivative at each step, making the method conceptually straightforward.
3. Fewer iterations are typically needed to achieve a desired accuracy compared to bracketing methods like the bisection method, assuming the method converges.

Limitations

1. Requirement of the derivative means that $f'(x)$ must either be computable or approximated, which can be challenging or computationally expensive for certain functions.
2. No guaranteed convergence occurs if the initial guess is far from the root, or if $f'(x)$ is small or zero near the approximation, potentially leading to divergence.
3. Wrong root or complex behavior may arise in cases where the function has multiple roots or inflection points, causing convergence to an unintended root or erratic behavior.
4. Division by zero is a critical issue if $f'(x_n) = 0$ at any iteration, requiring safeguards or modifications to the standard algorithm to handle such cases.