2.2 Fixed-Point Iteration 1. Fixed Point 1. Fixed Point 2. Fixed-Point Iteration 3. Fixed-Point Theorem C程式: ALG022 Fixed Point Iteration Definition 2.2 The number p is a fixed point for a given function g if g p p . 開課班級: 數學系資統組2A 數值分析 授課教師: 吳漢銘 (淡江大學 數學系) (1) Given a root-finding problem f p 0 , we can define g with a fixed point at p in a number of ways, for example, as g x x f x or as g x x 3f x . 教學網站: http://www.hmwu.idv.tw Textbook: Burden & Faires’ Numerical Analysis, 9/E 系級: 數學系資統組2A 數值分析 學號: (2) Conversely, if the function g has a fixed point at p, then the function defined by f x x g x has a zero at p . 姓名: 2.2 Fixed-Point Iteration September 14, 2014 1 / 16 Theorem 2.3 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 2 / 16 The Existence and Uniqueness of A Fixed Point Example 1 Determine any fixed points of the function g x Sol: x2 2. Let p be a fixed point for g, we have p g p p2 2. ➁ 0 p2 p 2 p 1 p 2 p 1, p 2. So g has two fixed points. end end Theorem 2.3 (i) If g C a, b and g x a, b for all at least one fixed point in a, b . x a, b , then g has (ii) If, in addition, g x exists on a, b and a positive constant k exists with g x k , for all x a, b , then there is fixed point in a, b . exactly one 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 1 3 / 16 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 4 / 16 Example 2(a) Show that g x 1, 1 . x2 Example 2(b) 1 3 has a unique fixed point on the interval x2 Find the fixed points of g x 3, 4 . Sol: 1 3 in the interval 1, 1 and Sol: ➀ Since g x 2x 3, the function g is continuous and g x exists on 1, 1 . ➁ The maximum and minimum values of g x occur at x 1, x 0, or x 1. ➂ maximum: g 1 0, g 1 0; minimum : g 0 1 3. ➃ Moreover 2x 2 g x , for all x 1, 1 . 3 3 So g satisfies all the hypotheses of Theorem 2.3 and has a unique fixed point in 1, 1 . end end 數學系資統組2A 數值分析 Example 2(b) 2.2 Fixed-Point Iteration September 14, 2014 5 / 16 p2 ➀ Let p be the fixed point. If g p p2 3p 1 0 1 3 3 p p p, then 13 2 13 2 3 1, 1 3, 4 ➁ However, g 4 5 and g 4 8 3 1, so g does not satisfy the hypotheses of Theorem 2.3 on 3, 4 . end end (1) The hypotheses of Theorem 2.3 are sufficient unique fixed point but are not necessary . 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration to guarantee a September 14, 2014 6 / 16 2. Fixed-Point Iteration (conti.) (1) To approximate the fixed point of a function g, we choose an initial approximation p0 and generate the sequence pn n 1 by letting pn g pn 1 , for each n 1. (2) If the sequence converges to p and g is continuous, then p limn pn limn g pn 1 pn 1 g limn g p , and a solution to x g x is obtained. This technique is called fixed-point, or functional iteration . 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 7 / 16 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 8 / 16 Fixed-Point Iteration ALGORITHM 022: Fixed-Point Iteration (conti.) To find a solution to p 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 數學系資統組2A 數值分析 9 / 16 Fixed-Point Iteration: illustration g p given an initial approximation p0 . 2.2 Fixed-Point Iteration Fixed-Point Iteration: illustration September 14, 2014 10 / 16 (conti.) [程式] Find the root of the equation x3 4x2 10 0 in 1, 2 using the fixed-point iteration approach with the following fixed-point form x g x . Suppose p0 1.5. Sol: (a) x g1 x (c) x g3 x (e) x g5 x x 10 x x3 x3 x3 4x2 1 2 10. 2. 4x2 10 (b) x (d) x g4 x 3x2 8x . g2 x 10 x 4x 1 2. 10 1 2 . 4 x ➀ The actual root is 1.365230013 . ➁ 以 (c) 為例: 原式 x3 4x2 10 0 4x2 10 x3 , so x2 10 x3 4 , and x 10 x3 1 2 2 . Choose a positive solution. ➁ Excellent results for choices (c), (d), and (e) (the Bisection method requires 27 iterations for this accuracy). ➂ (a) was divergent and (b) became undefined because it involved the square root of a negative number. 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 11 / 16 How to find a fixed-point problem that produces a sequence that and rapidly converges 數學系資統組2A 數值分析 reliably to a solution to a given root-finding problem? 2.2 Fixed-Point Iteration September 14, 2014 12 / 16 3. Fixed-Point Theorem Corollary 2.5 Corollary 2.5 Theorem 2.4 (Fixed-Point Theorem) Let g C a, b be such that g x a, b , for all x a, b . Suppose, in addition, that g exists on a, b and that a constant 0 k 1 exists with g x k , for all x a, b . Then for any number p0 a, b , the sequence defined by pn g pn 1 , n 1, converges to the unique fixed point p a, b . If g satisfies the hypotheses of Theorem 2.4, then bounds for the error involved in using pn to approximate p are given by pn p k n max p0 a, b p0 and kn pn p p1 p0 , for all n 1. 1 k Question: How can we find a fixed-point problem that produces a sequence that reliably and rapidly converges to a solution to a given root-finding problem? Answer: Manipulate the problem into a fixed point problem that satisfies the conditions of Fixed-Point Theorem 2.4 and has a derivative that is as small as possible near the fixed point . 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 13 / 16 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 14 / 16 C 程式: ALG022 Fixed Point Iteration Exercise Set 2.2 (0) 用程式跑出講義 12/16 頁之表格。 (1) 用手、 或計算機算: 1, 2 (2) 用電腦或寫程式算 (列出表格): 5, 9 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 15 / 16 數學系資統組2A 數值分析 2.2 Fixed-Point Iteration September 14, 2014 16 / 16

© Copyright 2019 ExploreDoc