To answer the question why the iterative method for solving nonlinear equations works in some cases but fails in others, we need to understand the theory behind the method, the fixed point of a contraction function. If a single variable function satisfies
(36) |
(37) |
(38) |
Definition: In a metric space with certain distance defined between any two points , a function is a contraction if
(39) |
In the following, we will use the p-norm of the vector defined below as the distance measurement:
(40) |
Intuitively, a contraction reduces the distance between points in the space, i.e., it brings them closer together. A function may not be a contraction through out its entire domain, but it can be a contraction in the neighborhood of a certain point , in which any is sufficiently close to so that
when | (41) |
Definition: A fixed point of a function is a point in its domain that is mapped to itself:
(42) |
(43) |
Fixed Point Theorem : Let be a contraction function satisfying
(44) |
(45) |
Proof
(46) |
(47) |
(48) |
Theorem: Let be a fixed point of a differentiable function , i.e, exists for any . If the norm of the Jacobian matrix is smaller than 1, , then is a contraction at .
The Jacobian matrix of is defined as
(49) |
(50) |
(51) |
(52) |
QED
In particular, for a single-variable function in an dimensional space, we have
(53) |
(54) |
Now we understand why in the examples of the previous section the iteration leads to convergence in some cases but divergence in other cases: if , the iteration will converge to the root of , but if , it never will never converge.
The iterative process for finding the fixed point of a single-variable function can be shown graphically as the intersections of the function and the identity function , as shown below. The iteration converges in the first two cases as , but it diverges in the last two cases as .
We next find the order of convergence of the fixed point iteration. Consider
(55) |
(56) |
constant | (57) |
Consider a specific iteration function in the form of , which is equivalent to , as if is the root of satisfying , it also satisfies , which is indeed a fixed point of . The derivative of this function is
(58) |
Example 1
Find the solution of the following equation:
and |
The iteration based on converges to the solution for any initial guess , as is a contraction. However, the iteration based on does not converge to as it is not a contraction in the neighborhood of . In fact, the iteration will diverge towards either if or if .
Example 2
To solve the following equation
As can be seen in the plots, this equation has three solutions,
Example 3
Example 4
The iteration from any initial guess will converge to .
Around , , the iteration does not converge.
Example 5
Consider a 3-variable linear vector function of arguments :
from which the g-function can be obtained:
The Jacobian of this linear system is a constant matrix
Alternatively, the g-function can also be obtained as
The Jacobian is
Example 6
Consider a 3-variable nonlinear function of arguments :
The g-function can be obtained as
By Aitken's method, the iteration can be accelerated based on two consecutive points and , as shown in the figure below.
The secant line of that goes through the two points and is represented by the equation in terms of its slope:
(59) |
(60) |
(61) |
(62) |
(63) |
(64) |
(65) |
Example Solve . Construct . It takes 18 iterations for the regular fixed point algorithm with initial guess , to get that satisfies , but it only three iterations for Aitken's method to converge to the same result: