Fixed-point Iteration

We first consider the special case of solving the equation #math195##tex2html_wrap_inline2606# when #tex2html_wrap_inline2608#. To find a solution #tex2html_wrap_inline2610# that satisfies the equation #tex2html_wrap_inline2612#, we can first convert it into an equation #tex2html_wrap_inline2614#, which is equivalent to #math196##tex2html_wrap_inline2616# in the sense that an #tex2html_wrap_inline2618# satisfying one of the equations will also satisfy the other. We then carry out an iteration #math197##tex2html_wrap_inline2620# from some initial value #tex2html_wrap_inline2622#. If the iteration converges at a point #tex2html_wrap_inline2624#, i.e., #tex2html_wrap_inline2626#, then we also have #tex2html_wrap_inline2628#, i.e., #tex2html_wrap_inline2630# is a solution of the equation #tex2html_wrap_inline2632#. Consider the following two examples:

Comparing these examples, one would naturally ask: why does this iterative method work in some cases but fail in other? To answer these questions we need to understand the theory behind the method, the <#446#>fixed point<#446#> of a <#447#>contraction function<#447#>.

If a single variable function #tex2html_wrap_inline2658# satisfies

#math213#   #tex2html_wrap_indisplay6308# (24)
it is said to be <#450#>Lipschitz continuous<#450#>, and #tex2html_wrap_inline2660# is a <#451#>Lipschitz constant<#451#>. If #tex2html_wrap_inline2662#, then #tex2html_wrap_inline2664# is a <#452#>non-expansive<#452#> function, if #tex2html_wrap_inline2666#, then #tex2html_wrap_inline2668# is a <#453#>contraction function<#453#> or simply a <#454#>contraction<#454#>. These concepts can be generalized to solving multivariate equations #math214##tex2html_wrap_inline2670#.

<#458#>Definition: <#458#> In a metric space #tex2html_wrap_inline2672# with certain distance #math215##tex2html_wrap_inline2674# defined between any two points #math216##tex2html_wrap_inline2676#, a function #math217##tex2html_wrap_inline2678# is a <#464#>contraction<#464#> if

#math218#   #tex2html_wrap_indisplay6320# (25)
The smallest #tex2html_wrap_inline2680# value that satisfies the above is called the <#473#>Lipschitz constant<#473#>.

Intuitively, a contraction reduces the distance between points in the space, i.e., it brings them closer together. A function #math219##tex2html_wrap_inline2682# may not be a contraction through out its entire domain, but it can be a contraction in the neighborhood of a certain point #math220##tex2html_wrap_inline2684#, composed of all points #tex2html_wrap_inline2686# satisfying #math221##tex2html_wrap_inline2688# (i.e., #tex2html_wrap_inline2690# is a neighbor of #tex2html_wrap_inline2692# as defined by #tex2html_wrap_inline2694#) so that

#math222#   #tex2html_wrap_indisplay6330# (26)

<#490#>Definition: <#490#> A <#491#>fixed point<#491#> #tex2html_wrap_inline2696# of a function #math223##tex2html_wrap_inline2698# is a point in its domain that is mapped to itself:

#math224#   #tex2html_wrap_indisplay6334# (27)
We immediately have
#math225#   #tex2html_wrap_indisplay6336# (28)
A fixed point #tex2html_wrap_inline2700# is an <#517#>attractive fixed point<#517#> if any point #tex2html_wrap_inline2702# in its neighborhood converges to #tex2html_wrap_inline2704#, i.e., #math226##tex2html_wrap_inline2706#.

We further consider two theorems regarding the fixed point and a contraction mapping.

<#524#>Fixed-Point Theorem <#524#>: Let #math227##tex2html_wrap_inline2708# be a contraction satisfying

#math228#   #tex2html_wrap_indisplay6343# (29)
then there exists a unique fixed point #math229##tex2html_wrap_inline2710#, which can be found by an iteration from an arbitrary initial point #tex2html_wrap_inline2712#:
#math230#   #tex2html_wrap_indisplay6347# (30)

<#555#>Contraction Mapping Theorem: <#555#> Let #math231##tex2html_wrap_inline2714# be a fixed point of a differentiable function #math232##tex2html_wrap_inline2716#, i.e, #math233##tex2html_wrap_inline2718# exists for any #tex2html_wrap_inline2720#. If the norm of the Jacobian matrix is smaller than 1, #math234##tex2html_wrap_inline2722#, then #math235##tex2html_wrap_inline2724# is a contraction at #tex2html_wrap_inline2726#.

The Jacobian matrix of #math236##tex2html_wrap_inline2728# is defined as

#math237#   #tex2html_wrap_indisplay6357# (31)

The proofs of the two theorems above are given in Appendix 3 of the chapter.

In the special case of a single-variable function #tex2html_wrap_inline2730# with #tex2html_wrap_inline2732#, its Jacobian is simply its derivative #tex2html_wrap_inline2734#, and we have

#math238#   #tex2html_wrap_indisplay6362# (32)
and
#math239#   #tex2html_wrap_indisplay6364# (33)
If #tex2html_wrap_inline2736#, then #tex2html_wrap_inline2738# is a contraction at #tex2html_wrap_inline2740#.

Now we should understand why in the examples of the previous section the iteration leads to convergence in some cases but divergence in other cases: if #tex2html_wrap_inline2742#, the iteration will converge to the root #tex2html_wrap_inline2744# of #tex2html_wrap_inline2746#, but if #tex2html_wrap_inline2748#, it never will never converge.

The iterative process #math240##tex2html_wrap_inline2750# for finding the fixed point of a single-variable function #tex2html_wrap_inline2752# can be shown graphically as the intersections of the function #tex2html_wrap_inline2754# and the identity function #tex2html_wrap_inline2756#, as shown below. The iteration converges in the first two cases as #tex2html_wrap_inline2758#, but it diverges in the last two cases as #tex2html_wrap_inline2760#.

<#6378#>Figure<#6378#> 1.6: <#6379#>Convergence and Divergence of Fixed Point Method<#6379#>
[width=100mm]<#595#>figures/fixedpoint.eps<#595#>

In general the fixed-point iteration converges linearly:

#math241#   #tex2html_wrap_indisplay6382# (34)
However, if the iteration function #tex2html_wrap_inline2762# has zero derivative at the fixed point #tex2html_wrap_inline2764#, we have
#math242#
#tex2html_wrap_indisplay6386# #tex2html_wrap_indisplay6387# #tex2html_wrap_indisplay6388#  
  #tex2html_wrap_indisplay6389# #tex2html_wrap_indisplay6390# (35)
and the iteration converges quadratically:
#math243#   #tex2html_wrap_indisplay6392# (36)
Moreover, if #tex2html_wrap_inline2766#, then the iteration converges cubically.

<#630#>Example 1<#630#>

#math244#   #tex2html_wrap_indisplay6395#  
This equation can converted into an equivalent form of #tex2html_wrap_inline2768# in two different ways:
#math245#   #tex2html_wrap_indisplay6398#  
In the figure below, the two functions #tex2html_wrap_inline2770# (left) and #tex2html_wrap_inline2772# (right) together with #tex2html_wrap_inline2774# and the identity function are plotted:

<#6402#>Figure<#6402#> 1.7: <#6403#>Fixed Point Example 4<#6403#>
[width=100mm]<#638#>figures/FPexample0.eps<#638#>

The iteration based on #tex2html_wrap_inline2776# converges to the solution #tex2html_wrap_inline2778# for any initial guess #math246##tex2html_wrap_inline2780#, as #tex2html_wrap_inline2782# is a contraction. However, the iteration based on #tex2html_wrap_inline2784# does not converge to #tex2html_wrap_inline2786# as it is not a contraction in the neighborhood of #tex2html_wrap_inline2788#. In fact, the iteration will diverge towards either #tex2html_wrap_inline2790# if #tex2html_wrap_inline2792# or #tex2html_wrap_inline2794# if #tex2html_wrap_inline2796#.

<#642#>Example 2<#642#>

#math247#   #tex2html_wrap_indisplay6417#  
we first convert it into the form of #tex2html_wrap_inline2798# in two different ways:
#math248#   #tex2html_wrap_indisplay6420#  

<#6421#>Figure<#6421#> 1.8: <#6422#>Fixed Point Example 5<#6422#>
[width=100mm]<#651#>figures/FPexample1.eps<#651#>

As can be seen in the plots, this equation has three solutions,

#math249#   #tex2html_wrap_indisplay6425#  
of which #tex2html_wrap_inline2800# and #tex2html_wrap_inline2802# can be obtained by the iteration based on #tex2html_wrap_inline2804# and #tex2html_wrap_inline2806# can be obtained by the iteration based on #tex2html_wrap_inline2808#. But neither of them can find all three roots.

  • As shown in the plot on the left, #tex2html_wrap_inline2810# for all #math250##tex2html_wrap_inline2812# except in the neighborhood of #tex2html_wrap_inline2814#, i.e., #tex2html_wrap_inline2816# is a contraction mapping everywhere except around #tex2html_wrap_inline2818#. Therefore the iteration starting from any initial guess #tex2html_wrap_inline2820# will converge to either #tex2html_wrap_inline2822# if #tex2html_wrap_inline2824#, or #tex2html_wrap_inline2826# if #tex2html_wrap_inline2828#.
    #math251#   #tex2html_wrap_indisplay6442#  
    However, as #tex2html_wrap_inline2830# is not a contraction mapping around #tex2html_wrap_inline2832#, the iteration will never converge to #tex2html_wrap_inline2834#.
  • As shown in the plot on the right, #tex2html_wrap_inline2836# for all #math252##tex2html_wrap_inline2838# except in the neighborhood of #tex2html_wrap_inline2840#, i.e., #tex2html_wrap_inline2842# is not a contraction mapping around either #tex2html_wrap_inline2844# or #tex2html_wrap_inline2846#. Therefore the iteration based on #tex2html_wrap_inline2848# will not converge to either #tex2html_wrap_inline2850# or #tex2html_wrap_inline2852#, but it may converge to #tex2html_wrap_inline2854#, if the initial guess #tex2html_wrap_inline2856# is in the range #tex2html_wrap_inline2858#. However, if #tex2html_wrap_inline2860# is outside this range the iteration will diverge toward either #tex2html_wrap_inline2862# if #tex2html_wrap_inline2864# of #tex2html_wrap_inline2866# if #tex2html_wrap_inline2868#.
    #math253#   #tex2html_wrap_indisplay6464#  

#math254#   #tex2html_wrap_indisplay6466#  

<#680#>Example 3<#680#>

#math255#   #tex2html_wrap_indisplay6468#  
This equation can be converted into the form #tex2html_wrap_inline2870# in different ways:
  • #math256#   #tex2html_wrap_indisplay6471#  
    #math257#   #tex2html_wrap_indisplay6473#  
  • #math258#   #tex2html_wrap_indisplay6475#  
  • #math259#   #tex2html_wrap_indisplay6477#  
  • #math260#   #tex2html_wrap_indisplay6479#  

#math261#   #tex2html_wrap_indisplay6481#  

<#714#>Example 4<#714#>

#math262#   #tex2html_wrap_indisplay6483#  

  • #math263#   #tex2html_wrap_indisplay6485#  

    The iteration from any initial guess #tex2html_wrap_inline2872# will converge to #math264##tex2html_wrap_inline2874#.

  • #math265#   #tex2html_wrap_indisplay6489#  

    Around #tex2html_wrap_inline2876#, #tex2html_wrap_inline2878#, the iteration does not converge.

  • #math266#   #tex2html_wrap_indisplay6493#  

<#733#>Example 5<#733#>

Consider a 3-variable linear vector function #math267##tex2html_wrap_inline2880# of arguments #math268##tex2html_wrap_inline2882#:

#math269#   #tex2html_wrap_indisplay6497#  

from which the g-function can be obtained:

#math270#   #tex2html_wrap_indisplay6499#  

The Jacobian #math271##tex2html_wrap_inline2884# of this linear system is a constant matrix

#math272#   #tex2html_wrap_indisplay6502#  
with the induced p=2 norm (maximum singular value) #math273##tex2html_wrap_inline2886#. Consequently, the iteration #math274##tex2html_wrap_inline2888# converges from an initial guess #math275##tex2html_wrap_inline2890# to the solution #math276##tex2html_wrap_inline2892#.

Alternatively, the g-function can also be obtained as

#math277#   #tex2html_wrap_indisplay6508#  

The Jacobian is

#math278#   #tex2html_wrap_indisplay6510#  
with the induced p=2 norm #math279##tex2html_wrap_inline2894#. The iteration does not converge.

<#793#>Example 6<#793#>

Consider a 3-variable nonlinear function #math280##tex2html_wrap_inline2896# of arguments #math281##tex2html_wrap_inline2898#:

#math282#   #tex2html_wrap_indisplay6515#  

The g-function can be obtained as

#math283#   #tex2html_wrap_indisplay6517#  
With #math284##tex2html_wrap_inline2900# and after #tex2html_wrap_inline2902# iterations #math285##tex2html_wrap_inline2904# converges to #math286##tex2html_wrap_inline2906#, with error #math287##tex2html_wrap_inline2908#. However, the iteration may not converge from other possible initial guesses.

Finally, we consider Aitken's method, by which the iteration #math288##tex2html_wrap_inline2910# can be accelerated based on two consecutive points #tex2html_wrap_inline2912# and #tex2html_wrap_inline2914#, as shown in the figure below.

<#6526#>Figure<#6526#> 1.9: <#6527#>Aitken's Method<#6527#>
[width=70mm]<#830#>figures/aitken.eps<#830#>

The secant line of #tex2html_wrap_inline2916# that goes through the two points #math289##tex2html_wrap_inline2918# and #math290##tex2html_wrap_inline2920# is represented by the equation in terms of its slope:

#math291#   #tex2html_wrap_indisplay6533# (37)
Solving for #tex2html_wrap_inline2922#, we get
#math292#   #tex2html_wrap_indisplay6536# (38)
To accelerate, instead of moving from #tex2html_wrap_inline2924# to #tex2html_wrap_inline2926#, we move to the point #tex2html_wrap_inline2928# at which this secant line intersects with the identity function #tex2html_wrap_inline2930#. We can therefore replace #tex2html_wrap_inline2932# in the equation above by #tex2html_wrap_inline2934# and solve the resulting equation
#math293#   #tex2html_wrap_indisplay6544# (39)
to get
#math294#   #tex2html_wrap_indisplay6546# (40)
where #tex2html_wrap_inline2936# and #tex2html_wrap_inline2938# are respectively the first and second order differences defined below:
#math295#   #tex2html_wrap_indisplay6550# (41)
#math296#   #tex2html_wrap_indisplay6552# (42)
This result can then be converted into an iterative process
#math297#   #tex2html_wrap_indisplay6554# (43)
Given #tex2html_wrap_inline2940#, we skip #math298##tex2html_wrap_inline2942# and #math299##tex2html_wrap_inline2944# but directly move to #tex2html_wrap_inline2946# computed based on #tex2html_wrap_inline2948# and #tex2html_wrap_inline2950#, thereby making a greater step towards the solution.

<#880#>Example<#880#>

Solve #tex2html_wrap_inline2952#. Construct #math300##tex2html_wrap_inline2954#. It takes 18 iterations for the regular fixed-point algorithm with initial guess #tex2html_wrap_inline2956#, to get #math301##tex2html_wrap_inline2958# that satisfies #math302##tex2html_wrap_inline2960#, but it only three iterations for Aitken's method to converge to the same result:

#math303#   #tex2html_wrap_indisplay6567#  

#math304#   #tex2html_wrap_indisplay6569#