Unlike the linear equation systems which can be solved under
the guidance of the fundamental theorem of linear algebra,
for nonlinear equation systems, there exists neither a theory
regarding the existence and uniqueness of their solutions, nor
closed-form solutions in general . We therefore have to rely
on numerical methods to find one or more solutions, if they
do exist, in an iterative manner from certain initial guess
of the solution, if the iteration converges, i.e., the
difference between two consecutive results will eventually
approach to zero.
Here we consider a set of methods that find a solution of a
single-variable nonlinear equation #tex2html_wrap_inline2440#, by searching
iteratively through a neighborhood of the domain, in which
a solution is known to be located.
- <#255#>The bisection search<#255#>
This method requires two initial guesses #tex2html_wrap_inline2442# satisfying
#math165##tex2html_wrap_inline2444#. As #tex2html_wrap_inline2446# and #tex2html_wrap_inline2448# are on opposite sides
of the x-axis #tex2html_wrap_inline2450#, the solution #tex2html_wrap_inline2452# at which #tex2html_wrap_inline2454# must
reside somewhere in between of these two guesses, i.e., #tex2html_wrap_inline2456#.
<#6151#>Figure<#6151#> 1.2:
<#6152#>Bisection Search<#6152#>
| [width=70mm]<#257#>figures/BisectionSearch.eps<#257#> |
Given such two end points #tex2html_wrap_inline2458# and #tex2html_wrap_inline2460#, we could find any point
#tex2html_wrap_inline2462# in between and use it to replace one of the end points at
which the function value #tex2html_wrap_inline2464# has the same sign as that of
#tex2html_wrap_inline2466#. The new search interval is #tex2html_wrap_inline2468# if #math166##tex2html_wrap_inline2470#,
or #tex2html_wrap_inline2472# if #math167##tex2html_wrap_inline2474#, either of which is smaller than
the previous interval #tex2html_wrap_inline2476#. This process is then carried
out iteratively until the solution is eventually approached, with
a guaranteed convergence.
To avoid the worst possible case in which the solution always
happens to be in the larger of the two sections #tex2html_wrap_inline2478# and #tex2html_wrap_inline2480#, we
typpically choose #tex2html_wrap_inline2482# to be the middle point #math168##tex2html_wrap_inline2484#
between the two end points, so that #math169##tex2html_wrap_inline2486#, i.e., the
new search interval is always halved in each step of the iteration:
#math170# #tex2html_wrap_indisplay6170#
(11)
Here, without loss of generality, we have assumed
#math171##tex2html_wrap_inline2488# and #tex2html_wrap_inline2490# is replaced by #tex2html_wrap_inline2492#.
For example, we assume the root is located at #tex2html_wrap_inline2494# between
the two initial values are #tex2html_wrap_inline2496# and #tex2html_wrap_inline2498#, then we get
#math172# #tex2html_wrap_indisplay6178#
(12)
Note that the error #math173##tex2html_wrap_inline2500# does not necessarily always
reduce monotonically. However, as in each iteration the search
interval is always halved, the worst possible error is also halved:
#math174# #tex2html_wrap_indisplay6181#
(13)
In general, to measure how quickly or slowly an iterative method
converges, we consider the following limit of the ratio of errors
of two consecutive iterations:
#math175# #tex2html_wrap_indisplay6183#
(14)
where #tex2html_wrap_inline2502# is the <#293#>order of convergence<#293#> and #tex2html_wrap_inline2504# is the
<#294#>rate of convergence<#294#>. The higher the order #tex2html_wrap_inline2506#, the more
rapidly the iteration converges. For the bisection method, we
have
#math176# #tex2html_wrap_indisplay6188#
(15)
We see that its order of convergence is #tex2html_wrap_inline2508# (it converges
linearly) with the rate of convergence #tex2html_wrap_inline2510#.
Compared to other methods to be considered later, the linear
convergence of the bisection method is rather slow, but its
has the advantage that no derivative #tex2html_wrap_inline2512# of the given
function is needed and the given function does not need to be
differentiable.
- <#305#>The Secant method<#305#>
Same as in the bisection method, we assume there are two initial
values #tex2html_wrap_inline2514# and #tex2html_wrap_inline2516# available, but they no longer have to
satisfy #math177##tex2html_wrap_inline2518#. Here the iteration is based on the
zero-crossing of the secant line passing through the two points
#tex2html_wrap_inline2520# and #tex2html_wrap_inline2522#, instead of the middle point between
them. The equation for the secant is:
#math178# #tex2html_wrap_indisplay6198#
(16)
Setting #tex2html_wrap_inline2524#, we get the zero crossing point:
#math179# #tex2html_wrap_indisplay6201#
(17)
where #tex2html_wrap_inline2526# is the finite difference that approximates
the derivative #tex2html_wrap_inline2528#:
#math180# #tex2html_wrap_indisplay6205#
(18)
<#6206#>Figure<#6206#> 1.3:
<#6207#>The Secant Method<#6207#>
| [width=70mm]<#327#>figures/Secant.eps<#327#> |
7
As shown in Fig. #Secant#331>, the new value #tex2html_wrap_inline2530# obtained above
is a better estimate of the root than either #tex2html_wrap_inline2532# or #tex2html_wrap_inline2534#, and
is used to replace one of them:
- If #math181##tex2html_wrap_inline2536#, then #math182##tex2html_wrap_inline2538# satisfying
#tex2html_wrap_inline2540# is replaced by #tex2html_wrap_inline2542# (same as the bisection
method);
- If #math183##tex2html_wrap_inline2544#, then #math184##tex2html_wrap_inline2546# with greater
#tex2html_wrap_inline2548# is replaced by #tex2html_wrap_inline2550#.
This process is then carried out iteratively to approach the root:
#math185# #tex2html_wrap_indisplay6221#
(19)
In case #math186##tex2html_wrap_inline2552#, the approximated derivative is zero
#math187##tex2html_wrap_inline2554#, and #tex2html_wrap_inline2556# cannot be found. In such a case,
a root may exist between #tex2html_wrap_inline2558# and #tex2html_wrap_inline2560#. Therefore the way to
resolve this problem is to combine the bisection search with the
secant method so that when #tex2html_wrap_inline2562#, the algorithm will switch
to bisection search. This is Dekker's method:
#math188# #tex2html_wrap_indisplay6229#
(20)
The order of convergence of the secant method is #tex2html_wrap_inline2564#
as shown in Appendix 1 of this chapter, i.e., the secant method
is converges more quickly than the bisection search method with
#tex2html_wrap_inline2566# (which does not take advantage of the information of the
specific function #tex2html_wrap_inline2568#).
- <#356#>The inverse quadratic interpolation<#356#>
Similar to the secant method that approximates the given function
#tex2html_wrap_inline2570# by a straight line that goes through two consecutive points
#math189##tex2html_wrap_inline2572# and #math190##tex2html_wrap_inline2574#, the inverse quadratic
interpolation method approximates the function by a quadratic curve
that goes through three consecutive points #math191##tex2html_wrap_inline2576#. As the function may be better approximated by
a quadratic curve rather than a straight line, the iteration is
likely to converge more quickly.
In general, any function #tex2html_wrap_inline2578# can be approximated by a quadratic
function #tex2html_wrap_inline2580# based on three points at #tex2html_wrap_inline2582#, #tex2html_wrap_inline2584#,
and #tex2html_wrap_inline2586# by the <#359#>Lagrange interpolation<#359#>:
#math192# #tex2html_wrap_indisplay6243#
(21)
However, here we use the interpolation #tex2html_wrap_inline2588# to approximate
the inverse function #tex2html_wrap_inline2590#:
#math193# #tex2html_wrap_indisplay6247#
(22)
Setting #tex2html_wrap_inline2592#, we get the zero-crossing point:
#math194# #tex2html_wrap_indisplay6250#
(23)
which can be used as an estimate of the root #tex2html_wrap_inline2594# of #tex2html_wrap_inline2596#.
This expression can then be converted into an iteration by which
the next root estimate #tex2html_wrap_inline2598# is computed based on the previous
three estimates at #tex2html_wrap_inline2600#, #tex2html_wrap_inline2602#, and #tex2html_wrap_inline2604#.