2.2 Fixed-Point Iteration - University of Notre Dame

1 Fixed-Point Iteration 1. Basic Definitions A number is a fixed point for a given function if = . Root finding = 0 is related to Fixed-Point Iteration = . Given a root-finding problem = 0, there are many with fixed points at : Example: . + 3 .. If has fixed point at , then = ( ) has a zero at 2. Why study Fixed-Point Iteration ? 1. Sometimes easier to analyze 2. Analyzing Fixed-Point problem can help us find good root-finding methods A Fixed-Point Problem Determine the fixed points of the function = 2 2. 3. When Does Fixed-Point Iteration Converge? Existence and Uniqueness Theorem a.

2 If [ , ] and [ , ] for all . [ , ], then has a Fixed-Point in [ , ]. b. If, in addition, ( ) exists on ( , ) and a positive constant < 1 exists with , for all , , then there is exactly one fixed point in , . Note: 1. , is continuous in , . 2. , takes values in , . 4. Proof If = , or = , then has a fixed point at the endpoint. Otherwise, > and < . Define a new function = . = > 0 and = < 0. is continuous By intermediate value theorem, there exists ( , ) for which = . Thus, = . 5. b) < 1. Suppose we have two fixed points and . By the mean value theorem, there is a number.

3 Between and with . ( ). =.. Thus = = . < , which is a contradiction. This shows the supposition is false. Hence, the fixed point is unique. 6. Fixed-Point Iteration For initial 0 , generate sequence { } . =0 by = ( 1 ). If the sequence converges to , then = lim = lim ( 1 ) = lim 1 = ( ).. A Fixed-Point Problem Determine the fixed points of the function = cos( ) for , . Remark: See also the Matlab code. 7. The Algorithm 8. INPUT p0; tolerance TOL; maximum number of Iteration N0. OUTPUT solution p or message of failure STEP1 Set i = 1. // init. counter STEP2 While i N0 do Steps 3-6.

4 STEP3 Set p = g(p0). STEP4 If |p-p0| < TOL then OUTPUT(p); // successfully found the solution STOP. STEP5 Set i = i + 1. STEP6 Set p0 = p. // update p0. STEP7 OUTPUT( The method failed after N0 iterations );. STOP. 9. Convergence Fixed-Point Theorem Let [ , ] be such that , , for all , . Suppose, in addition, that exists on , and that a constant 0 < < 1 exists with , for all , . Then, for any number 0 in [ , ], the sequence defined by = ( 1 ). converges to the unique fixed point in [ , ]. Corollary If satisfies the above hypotheses, then bounds for the error involved using to approximating are given by max 0 , 0.

5 | | | 1 0 |. 1 10. Proof: = 1 . = 1 . 1 . Remark: Since < 1, the distance to fixed point is shrinking every Iteration Keep doing the above procedure: 1 2 2 . 0 . lim lim 0 = 0.. 11.