Numerical O.D.E.'s  Roots of a Single-Variable  Secant Method Convergence

Fixed-Point Iterations

Often times, the elusive solution to a nonlinear equation can be elicited from forming iterative schemes. These iteration schemes seek to produce a sequence which will converge to a fixed point.

    The idea of fixed-point iterations can be seen from Newton's formula. In the context of computing roots of equations, Newton's method can be viewed as a fixed-point iteration by viewing  .

    The fixed-point iteration framework allows for greater freedom in formulation of iteration schemes and provides a more rigorous framework for the analysis of convergence. The following theorem presents the idea of consistency. That is, if the sequence  converges, then it necessarily converges to a fixed point.

    The analysis of convergence of the fixed point iterations also produces additional information that can be used to examine the rate of convergence and a mechanism to detect convergence to within a certain amount of accuracy. The discussion of convergence for fixed-point iterations begins with a lemma which permits the existence of a fixed point.

  

Proof:

1. For this part, existence and uniqueness need to be shown. By Lemma 4.1, the existence of a fixed point is established. To show uniqueness, suppose that $$ and $$ are fixed points. That is, $= g()$ and $= g()$. Thus,



where $, $ using the Mean-Value theorem, Theorem 1.5. Taking absolute values,



Since $< 1$ by the statement of the theorem $1-> 0$. This implies $|-|=0$, or $= $ which establishes uniqueness.

2.  Let $x_0 [a,b]$. The assumption that $g : [a,b] [a,b] $ implies that $g(x_0)= x_1 [a,b]$ as well. Inductively, a similar argument shows that $x_n [a,b] n 0$. Hence ${x_n}_n=0^$ is in the domain of $g$.

Note that

  

where $c_n-1 , x_n-1 .$ Taking absolute values yields

  

Since $< 1$, $e_n 0$ and hence $x_n $.

3.  The result above shows that $|- x_n| ^n |- x_0|.$ In particular, then,



or



Thus, $|-x_0| 11-|x_1-x_0|$. This, in combination with Equation 4.16 completes the proof.

4.  From Equation 4.15,



for some $c_n , x_n+1$. Since $x_n+1 $ it follows that $c_n $. Using the continuity assumption on $g'(x)$, we have



Thus, for $x_n$ sufficiently close to $$,

  

  
 Numerical O.D.E.'s  Roots of a Single-Variable  Secant Method Convergence
Wed Oct 28 11:42:13 EST 1998