Lecture note 2 Numerical Analysis Note that the latter one is in [3,4].However,g(4)=5 and g(4)=>1,so the hypotheses in Theorem 2.2 are not satisfied but the fixed point in [3,4]is unique. .Example:Let g(z)=3-. g(z)=-3-xn3<0z∈[0,1] So g(z)is decreasing on 0,1].Therefore g0)=3≤96四≤1=90， x∈0,1 Ths,g(z)∈[0，l]for all∈[0,1].Hence g has a fixed point on[0,l]. However, g(0)=-n3≈-1.0986 lg'()1 on(0,1).Theorem 2.2 cannot be applied.However,g is decreasing, it is clear that the fixed point is unique. 1.2.2 Fixed point Algorithm Questions: Suppose that g has a fixed point at p.How to find a fixed point of g()? The fixed point gives naturally a iteration. Given an initial guess of po,we define Pn+1=g(pn).fixed point iteration. ·Two questions. 1.When pn a convergent sequence? 2.If it converges,what is the limit? -Denote p be the limit,i.e.,limn=p.Then by the continuity of 9 p=lim Pn lim g(Pn-1)=g(lim Pn-1)=g(p). n￥0g n-oo We can see that it has to be a fixed point! Theorem 5 (Theorem 2.3 Fixed-point Theorem)Suppose that 1.g∈C[a, 2.g(x)∈[a,b]for Vx∈[a,. 3.g'(x)erists on (a,b). 4.There erists a k∈(0,1)with |g'(rl≤k for all x∈(a,b). 9Lecture note 2 Numerical Analysis Note that the latter one is in [3, 4]. However, g(4) = 5 and g ′ (4) = 8 3 > 1, so the hypotheses in Theorem 2.2 are not satisfied but the fixed point in [3, 4] is unique. • Example: Let g(x) = 3−x . g ′ (x) = −3 −x ln 3 < 0 ∀x ∈ [0, 1] So g(x) is decreasing on [0, 1]. Therefore g(0) = 1 3 ≤ g(x) ≤ 1 = g(0), ∀x ∈ [0, 1] Thus, g(x) ∈ [0, 1] for all x ∈ [0, 1]. Hence g has a fixed point on [0, 1]. However, g ′ (0) = − ln 3 ≈ −1.0986 |g ′ (x)| 6≤ 1 on (0, 1). Theorem 2.2 cannot be applied. However, g is decreasing, it is clear that the fixed point is unique. 1.2.2 Fixed point Algorithm Questions: Suppose that g has a fixed point at p. How to find a fixed point of g(x)? • The fixed point gives naturally a iteration. • Given an initial guess of p0, we define pn+1 = g(pn). ←− fixed point iteration. • Two questions. 1. When pn a convergent sequence? 2. If it converges, what is the limit? – Denote p be the limit, i.e., limn→∞ = p. Then by the continuity of g p = limn→∞ pn = limn→∞ g(pn−1) = g( limn→∞ pn−1) = g(p). We can see that it has to be a fixed point! Theorem 5 (Theorem 2.3 Fixed-point Theorem) Suppose that 1. g ∈ C[a, b] 2. g(x) ∈ [a, b] for ∀x ∈ [a, b]. 3. g ′ (x) exists on (a, b). 4. There exists a k ∈ (0, 1) with |g ′ (x)| ≤ k for all x ∈ (a, b). 9