Lecture note 2 Numerical Analysis y=g(x) y=T Figure 1.2:Fixed point The advantage of using fixed point. 1.Fixed point form is easier to analyze; 2.certain fix-point iterations lead to powerful root-finding techniques.(We have many freedoms to choose h():e.g.,h()) Example 1:Find the fixed point of g(x)=z2-2. g()=x÷x2-2=x分x2-x-2=0÷x=-1,x=2. Not all function exists a fixed point. Example 2:Find the fixed point of g(x)=2+z2. g(x)=x÷x2+2=x÷x2-x+2=0.No solution! No fixed points. From the examples.we see that the fixed points may not necessarily exist and be unique. Questions:When there exists a fixed point?When the fixed point is unique? Existence and uniqueness are two important aspects in numerical analysis. Theorem 2 (Theorem 2.1)(Eristence)If 1.g∈C[a,b 2.g(x)∈[a, Then g has a fired point in (a,b]. 6
Lecture note 2 Numerical Analysis p y = g(x) x y −2 −1 1 2 y = x b b Figure 1.2: Fixed point • The advantage of using fixed point. 1. Fixed point form is easier to analyze; 2. certain fix-point iterations lead to powerful root-finding techniques. (We have many freedoms to choose h(x): e.g., h(x) = 1 f ′(x) ) • Example 1: Find the fixed point of g(x) = x 2 − 2. g(x) = x ⇔ x 2 − 2 = x ⇔ x 2 − x − 2 = 0 ⇔ x = −1, x = 2. • Not all function exists a fixed point. Example 2: Find the fixed point of g(x) = 2 + x 2 . g(x) = x ⇔ x 2 + 2 = x ⇔ x 2 − x + 2 = 0. No solution! No fixed points. • From the examples, we see that the fixed points may not necessarily exist and be unique. • Questions: When there exists a fixed point? When the fixed point is unique? • Existence and uniqueness are two important aspects in numerical analysis. Theorem 2 (Theorem 2.1) (Existence) If 1. g ∈ C[a, b] 2. g(x) ∈ [a, b] Then g has a fixed point in [a, b]. 6
Lecture note 2 Numerical Analysis .Intuition:The graph of g(x)must cross the graph of y=x. Idea:construct a function and then apply intermediate value theorem. Proof.If g(a)=a and/or g(b)=b,then g has fixed points at a and/or b.Otherwise, then g(a)>a and g(b)<b.Define f(x)=g(x)-z. Then f(a)=g(a)-a>0,f(b)=g(b)-b<0. Applying IVT(intermediate value theorem)concludes immediately the proof. 口 Remarks: All the conditions in the above theorems are sufficient but not necessary. ●Example:g(z)=x2-2on【-2,0] It is decreasing on [-2,0]. g(-2)=2≤g(x)≤g(0)=-2. Then g(x)∈[-2,2]年[-2,0] Theorem 2.1 cannot be applied.However,g has a fixed point at-1. Recall the mean value theorem. Theorem 3 (Mean Value Theorem)If f E Cla,b]and f is differentiable on (a,b),then a number g in (a,b)exists with f()=f-f@ b-a Theorem 4(Theorem 2.2)(Uniqueness)In addition to the assumptions 1,2 in Theorem 2.1,if 3.g(）erists on(a,b). 4.There erists a k∈(0，l)with |g'(xl≤k for all x∈(a,b). Then the fired point in a,b is unique. Intuition:The derivative is the velocity.The mean velocity from one fixed point to another is 1.There must be a point whose velocity 181. Recall Mean Value Theorem. 7
Lecture note 2 Numerical Analysis • Intuition: The graph of g(x) must cross the graph of y = x. • Idea: construct a function and then apply intermediate value theorem. Proof. If g(a) = a and/or g(b) = b, then g has fixed points at a and/or b. Otherwise, then g(a) > a and g(b) < b. Define f(x) = g(x) − x. Then f(a) = g(a) − a > 0, f(b) = g(b) − b < 0. Applying IVT (intermediate value theorem) concludes immediately the proof. Remarks: • All the conditions in the above theorems are sufficient but not necessary. • Example: g(x) = x 2 − 2 on [−2, 0] It is decreasing on [−2, 0]. g(−2) = 2 ≤ g(x) ≤ g(0) = −2. Then g(x) ∈ [−2, 2] 6∈ [−2, 0] Theorem 2.1 cannot be applied. However, g has a fixed point at −1. Recall the mean value theorem. Theorem 3 (Mean Value Theorem) If f ∈ C[a, b] and f is differentiable on (a, b), then a number ξ in (a, b) exists with f ′ (ξ) = f(b) − f(a) b − a Theorem 4 (Theorem 2.2) (Uniqueness) In addition to the assumptions 1,2 in Theorem 2.1, if 3. g ′ (x) exists on (a, b). 4. There exists a k ∈ (0, 1) with |g ′ (x)| ≤ k for all x ∈ (a, b). Then the fixed point in [a, b] is unique. • Intuition: The derivative is the velocity. The mean velocity from one fixed point to another is 1. There must be a point whose velocity is 1. • Recall Mean Value Theorem. 7