Iteration in Numerical Analysis
In numerical analysis, iteration is a technique used to tackle mathematical problems, including algebraic equations, differential equations, optimization, and many others.
The concept is simple: start with an initial estimate of a solution and then refine that estimate through repeated steps in an iterative process.
Each cycle through this process is known as an iteration.
Why is it useful? Iterative methods are invaluable in numerical analysis because they allow us to solve problems that are otherwise difficult or impossible to handle analytically. Furthermore, these methods can be easily implemented on a computer.
A Practical Example
One of the most popular iterative techniques is Newton’s method for finding the roots of an equation.
Newton’s method is based on this formula:
$$ x_{n+1} = x_n - \frac{ f(x_n) }{ f'(x_n) } $$
We start with an initial guess x0 for the root.
Then, by applying the formula, we get a new estimate x1, which is closer to the true root of the equation.
This process is repeated, with each new estimate xn+1 being derived from the previous estimate xn, until we reach a satisfactory level of accuracy.
For example, consider the equation
$$ x^3 - 2x - 5 = 0 $$
We begin with an approximate solution of x0=2
$$ x_0 = 2 $$
Now we apply Newton’s formula, using the function f(x) = x3 - 2x - 5
The derivative is f'(x) = 3x2 - 2
$$ x_1 = x_0 - \frac{ f(x_0) }{ f'(x_0) } $$
$$ x_1 = 2 - \frac{ x_0^3 - 2x_0 - 5 }{ 3x_0^2 - 2 } $$
Given that x0=2
$$ x_1 = 2 - \frac{ 2^3 - 2 \cdot 2 - 5 }{ 3 \cdot 2^2 - 2 } $$
$$ x_1 = 2 - \frac{ 8 - 4 - 5 }{ 12 - 2 } $$
$$ x_1 = 2 - \frac{ -1 }{ 10 } $$
$$ x_1 = 2 + 0.1 $$
$$ x_1 = 2.1 $$
With x1=2.1, we apply the formula again to find x2
$$ x_2 = x_1 - \frac{ f(x_1) }{ f'(x_1) } $$
$$ x_2 = 2.1 - \frac{ x_1^3 - 2x_1 - 5 }{ 3x_1^2 - 2 } $$
Since x1=2.1
$$ x_2 = 2.1 - \frac{ 2.1^3 - 2 \cdot 2.1 - 5 }{ 3 \cdot 2.1^2 - 2 } $$
$$ x_2 = 2.1 - \frac{ 9.261 - 4.2 - 5 }{ 13.23 - 2 } $$
$$ x_2 = 2.1 - \frac{ 0.061 }{ 11.23 } $$
$$ x_2 = 2.1 - 0.0054 $$
$$ x_2 = 2.0946 $$
The iterative process continues until we achieve an approximation that’s close enough to the actual solution.
For instance, we could decide to stop when the difference between two consecutive estimates xn - xn+1 is less than a certain tolerance (e.g., 0.0001).
$$ | x_n - x_{n+1}| < 0.0001 $$
Note: Newton's method does not always guarantee convergence to the solution. Its success largely depends on the choice of the initial guess x0. Additionally, it requires that the function f be differentiable and that its derivative is non-zero.
And so on.
