The Newton's method: a way to approximate any value

This method consists in computing an approximate value of a real root of a function through successive iterations, starting from a well-chosen initial point.

Let $ f $ be a convex function (resp. concave) and strictly increasing (resp. decreasing) on an interval $ I $.

We denote by $ x_0 \in I $ the unique real number such that $ f(x_0) = 0 $.

To ensure the global and systematic convergence of the method toward this root without risking divergence, the choice of the starting point $a_0$ must satisfy Fourier's conditions.

Fourier's Convergence Conditions

Formalized by Joseph Fourier, four strict criteria on the interval $\bigl[a, b \bigr]$ guarantee the absolute convergence of Newton's sequence:

$ f(a) $ and $ f(b) $ have opposite signs (existence of a root $ x_0 $ via the IVT).
$ f'(x) \neq 0 $ across the entire interval (the function is strictly monotonic, ensuring both the uniqueness of the root and that no tangent is horizontal).
$ f''(x) $ does not change sign (the function maintains a constant convexity or concavity, preventing slope fluctuations).
The initial point $ a_0 $ satisfies: $ f(a_0) \times f''(a_0) > 0 $.

Overview of Newton's method through successive derivations

This target value $ x_0 $ is obtained as the limit of the Newton-Raphson sequence:

$$ x_0 = \lim_{n \to +\infty} a_n $$

With $ (a_n)_{n \in \mathbb{N}} $ being the recurrence sequence defined by:

$$ a_{n + 1} = a_n - \frac{f(a_n)}{f'(a_n)} $$

Proofs

Let $ f $ be a convex function and strictly increasing on an interval $ I $.

We denote by $ x_0 \in I $ the unique real number such that $ f(x_0) = 0 $.

To ensure the global and systematic convergence of the method toward this root without risking divergence, the choice of the starting point $a_0$ must satisfy Fourier's conditions.

Fourier's Convergence Conditions

Formalized by Joseph Fourier, four strict criteria on the interval $\bigl[a, b \bigr]$ guarantee the absolute convergence of Newton's sequence:

$ f(a) $ and $ f(b) $ have opposite signs (existence of a root $ x_0 $ via the IVT).
$ f'(x) \neq 0 $ across the entire interval (the function is strictly monotonic, ensuring both the uniqueness of the root and that no tangent is horizontal).
$ f''(x) $ does not change sign (the function maintains a constant convexity or concavity, preventing slope fluctuations).
The initial point $ a_0 $ satisfies: $ f(a_0) \times f''(a_0) > 0 $.

This final condition requires starting from the side where the function and its concavity share the same sign. If $ f $ is convex ($ f'' > 0 $), one must choose $ a_0 $ such that $ f(a_0) > 0 $ (to the right of the root) to build a stable and monotonic sequence of approximations.

We know that this function will cancel at some point, but we don't know yet for what value $ x_0 $.

We have represented the tangent to this curve at point $ x = a_0 $, and corresponding to the following equation:

$$ T_{a_0}(x) = f'(a_0)(x - a_0) + f(a_0)$$

We will thus try to find out when this function will cancel itself. We do have:

$$ T_{a_0}(x) = 0 $$

$$ f'(a_0)(x - a_0) + f(a_0) = 0 $$

$$ f'(a_0)x - f'(a_0).a_0 + f(a_0) = 0 $$

$$ f'(a_0)x = f'(a_0).a_0 - f(a_0) $$

At this stage, we know that $ f'(a_0) > 0 $, then we can divide by $ f'(a_0) $.

$$ x = \frac{f'(a_0).a_0 - f(a_0)}{f'(a_0)} $$

$$ x = a_1 = a_0 - \frac{ f(a_0)}{f'(a_0)} $$

If we continue and do the same thing, this time not starting from $ a_1 $, we will obtain:

$$ a_2 = a_1 - \frac{ f(a_1)}{f'(a_1)} $$

We then obtain a recurring sequence $ (a_n)_{n \in \mathbb{N}} $ such as:

$$ \enspace a_{n + 1} = a_n - \frac{f(a_n)}{f'(a_n)} $$

The more successive iterations we establish, the more we will tend towards the desired value, namely:

$$ x_0 = \lim_{n \to +\infty} \enspace (a_n) $$

With $ (a_n)_{n \in \mathbb{N}} $ a recurring sequence such as:

$$ a_{n + 1} = a_n - \frac{f(a_n)}{f'(a_n)} $$

We can repeat this same reasoning for a concave and/or decreasing and/or negative function, and adapt a such process according to the case.

Example

We will try to find an approximate value of $ \sqrt{2} $ by this method.

Let $ f $ be a function such as $ x_0 = \sqrt{2}$ be a solution for$ f(x_0) = 0 $. Let's start from this hypothesis and try to determine this function.

$$ x_0 = \sqrt{2} $$

$$ x_0^2 = 2 $$

$$ x_0^2 - 2 = 0 $$

We will then study the function $ f $ defined by:

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

And thus find an approximate value of $ x_0 $ for which $ f(x_0) = 0 $.

We are definitely in the case of a convex function and strictly increasing function, we can then apply the method.

This involves computing the different values of the following:

$$ a_{n + 1} = a_n - \frac{f(a_n)}{f'(a_n)} $$

With $ f(x) = x^2 - 2 $ and its derivative function $ f'(x) = 2x $.

So,

$$ a_{n + 1} = a_n - \frac{a_n^2 - 2}{2a_n} $$

Furthermore, by finding a common denominator, we recover the result of Heron's method:

$$a_{n+1} = \frac{2a_n^2 - (a_n^2 - 2)}{2a_n} = \frac{a_n^2 + 2}{2a_n} = \frac{1}{2} \left( a_n + \frac{2}{a_n} \right)$$

Here are the results of the calculation with different value for $ a_0 $: