Figure 1. 3 The relationship among P, Po, P1, P-Pol and IP-Pl Remark 1. It is assumed that po+P in statement(1.7 Remark 2. Because g is continuous on an interval containing P, it is permissible to use the simpler criterion lg(P)ls K< I and lg (P)l>l in(1.6)and(1, 7), respectively Proof. We first show that the points pn inso all lie in(a, b). Starting with po, we apply Theorem 0.6, the Mean Value Theorem. There exists a value co E(a, b)so that |P-p1|=|9(P)-9(po)=|9(co)(P-p0) g(co川‖P-pl|≤K|P-pol<|P-po Therefore, P1 is no further from P than Po was, and it follows that pi E(a, b)(see Figure 1. 3). In general, suppose that Pn-1 E(a, b);then P-pnl|=|9(P)-9(p1-1)=|g'(cn-1)(P-p2-1) g(cn-1川‖P-pn-1)≤KP-pn-1<|P-p-1) Therefore, Pn E(a, b)and hence, by induction, all the points ipn ingo lie in(a, b) o complete the proof of(1.6), we will show that lim P-pn=0 First, a proof by induction will establish the inequality P-pn|≤K"|P-pol 1.11 The case n= 1 follows from the details in relation(1.8). Using the induction hypothesis IP-Pn-ils kn-IP-pol and the ideas in(1.9), we obtain Pl|≤K|P-p-1≤KK-P-p0|=K|P-pol Thus, by induction, inequality(1.11)holds for all n, Since 0< K< 1, the term K goes to zero as n goes to infinity. Hence ≤l|P-pn|≤linK"|P The limit of IP-pnl is squeezed between zero on the left and zero on the right, so we can conclude that limn-ooP-pnI=0. Thus limn-oo Pn= P and, by Theorem 1.1 the iteration Pn =g(pn-1) converges to the fixed point P. Therefore, statement(1.6) of Theorem 1.3 is proved. We leave statement(1.7) for the reader to investigate
Figure 1.3 The relationship among P, p0, p1, |P − p0| and |P − p1 Remark 1. It is assumed that p0 6= P in statement (1.7) Remark 2. Because g is continuous on an interval containing P, it is permissible to use the simpler criterion |g 0 (P)| ≤ K < 1 and |g 0 (P)| > 1 in (1.6) and (1,7), respectively. Proof. We first show that the points {pn} ∞ n=0 all lie in (a, b). Starting with p0, we apply Theorem 0.6, the Mean Value Theorem. There exists a value c0 ∈ (a, b) so that |P − p1| = |g(P) − g(p0)| = |g 0 (c0)(P − p0)| = |g 0 (c0)||P − p0| ≤ K|P − p0| < |P − p0|. (1.8) Therefore, p1 is no further from P than P0 was, and it follows that p1 ∈ (a, b) (see Figure 1.3). In general, suppose that pn−1 ∈ (a, b); then |P − pn| = |g(P) − g(pn−1)| = |g 0 (cn−1)(P − pn−1)| = |g 0 (cn−1)||P − pn−1)| ≤ K|P − pn−1| < |P − pn−1)|. (1.9) Therefore, pn ∈ (a, b) and hence, by induction, all the points {pn} ∞ n=0 lie in (a, b). To complete the proof of (1.6), we will show that limn→∞ |P − pn| = 0. (1.10) First, a proof by induction will establish the inequality |P − pn| ≤ Kn |P − p0|. (1.11) The case n = 1 follows from the details in relation (1.8). Using the induction hypothesis |P − pn−1| ≤ Kn−1 |P − p0| and the ideas in (1.9), we obtain |P − pn| ≤ K|P − pn−1| ≤ KKn−1 |P − p0| = Kn |P − p0|. Thus, by induction, inequality (1.11) holds for all n, Since 0 < K < 1, the term Kn goes to zero as n goes to infinity. Hence 0 ≤ limn→∞ |P − pn| ≤ limn→∞ Kn |P − p0| = 0. (1.12) The limit of |P − pn| is squeezed between zero on the left and zero on the right, so we can conclude that limn→∞ |P − pn| = 0. Thus limn→∞ pn = P and, by Theorem 1.1, the iteration pn = g(pn−1) converges to the fixed point P. Therefore, statement (1.6) of Theorem 1.3 is proved. We leave statement (1.7) for the reader to investigate. 6
Figure 1.4(a)Monotone convergence when 0< g(P)<1 Figure 1. 4(a) Monotone convergence when -1< g(P)<o Corollary 1.1. Assume that g satisfies the hypothesis given in(1.6)of Theorem 1.3. Bounds for the error involved when using pn to approximate P are given by P-p|≤K"|P- Pol for all n≥1, P-pksA" P-Pol for all n2≥1
Figure 1.4 (a) Monotone convergence when 0 < g0 (P) < 1. Figure 1.4 (a) Monotone convergence when −1 < g0 (P) < 0. Corollary 1.1. Assume that g satisfies the hypothesis given in (1.6) of Theorem 1.3. Bounds for the error involved when using pn to approximate P are given by |P − pn| ≤ Kn |P − p0| for all n ≥ 1, (1.13) and |P − pn| ≤ Kn |P − p0| 1 − K for all n ≥ 1, (1.14) 7
Figure 1.5(a) Monntone divergence when 1<g(P) Figure 1.5 ( b)Divergent oscillation when g(P)<-1 1.1. 2 Graphical Interpretation of Fixed-point Iteration Since we seek a fixed point P to g(ar), it is necessary that the graph of the curve y= g(a) and the line y= a intersect at the point (P, P). Two simple types of convergent iteration, monotone and oscillating, are illustrated in Figure 1.4(a)and(b) respectively To visualize the process, start at po on the x-axis and move vertically to the point (po, P1) g(po)) on the g(a) the point(P1, Pi) on the line y =a. Finally, move vertically downward to Pi on the -axis. The recursion Pn+1 g(pn)is used to construct the point (pn, Pn+1) on the graph, then a horizontal motion locates(Pn+1, Pn+1) on the line y =a, and then a vertical movement ends up at pn+1 on the x-axis. The situation is shown in Figure1. 4
Figure 1.5 (a) Monntone divergence when 1 < g0 (P). Figure 1.5 (b) Divergent oscillation when g 0 (P) < −1. 1.1.2 Graphical Interpretation of Fixed-point Iteration Since we seek a fixed point P to g(x), it is necessary that the graph of the curve y = g(x) and the line y = x intersect at the point (P, P). Two simple types of convergent iteration, monotone and oscillating, are illustrated in Figure 1.4(a) and(b), respectively. To visualize the process, start at p0 on the x -axis and move vertically to the point (p0, p1) = (p0, g(p0)) on the curve y = g(x). Then move horizontally from (p0, p1) to the point (p1, p1) on the line y = x. Finally, move vertically downward to p1 on the x -axis. The recursion pn+1 = g(pn) is used to construct the point (pn, pn+1) on the graph, then a horizontal motion locates (pn+1, pn+1) on the line y = x, and then a vertical movement ends up at pn+1 on the x -axis. The situation is shown in Figure1.4. 8
If lg(P)> 1, then the iteration Pn+1=g(pn)produces a sequence that diverges away from P. The two simple types of divergent iteration, monotone and oscillatin are illustrated in Figure 1.5(a)and(b), respectively Example 1.4. Consider the iteration pn+1= g(pn)when the function g(r)=1+ C-22/ 4 is used. The fixed points can be found by solving the equation x = g(a). The two solutions(fixed points of g) are z=-2 and a=2. The derivative of the function is g(ar)=l-r/2, and there are only two cases to consider Case(i) Case(ii) P=2 Start with P0 =-205 Start with po= 1.6 then get p1=-2.100625 then ge P1=1.96 p2=-220378135 P=1.9996 3=-2.41794414 p3=1.99999996 lim pn lim pn =2. Since lg()l>2 on [-3,1],by The- Since 1g(a)l< 2 on [1, 3], by Theo- orem 1.3, the sequence will not converge rem 1.3, the sequence will converge to Theorem 1. 3 does not state what will happen when g (P)=l. The next has been specially constructed so that the sequence Ipn converges whenever po >P and it diverges if we choose po P Example 1.5. Consider the iteration Pn+1 =g(pn) when the function g(a)=2(r- 1)1/2 for z> 1 is used. Only one fixed point P= 2 exists. The derivative is g(a)=l/(r-1)1/2 and g' (2)=1, so Theorem 3. 3 does not apply. There are two cases to consider when the starting value lies to the left or right of P=2 Case(i) Start with po= 1.5 Case(ii Start with po=2.5 then get P1 then get p1=2.44948974 p2=1.28718851 P2=2.40789513 p3=1.07179943 D3=237309514 p4=0.53590832 P4=234358284 p5=2(-0.46409168)12 lim pn=2 nce outside the dor This sequence is converging too slowly g(r), the term ps cannot be comput to the value P= 2; indeed, P1ooo 2.00398714
If |g 0 (P)| > 1, then the iteration pn+1 = g(pn) produces a sequence that diverges away from P. The two simple types of divergent iteration, monotone and oscillating, are illustrated in Figure 1.5 (a) and (b), respectively. Example 1.4. Consider the iteration pn+1 = g(pn) when the function g(x) = 1 + x − x 2/4 is used. The fixed points can be found by solving the equation x = g(x). The two solutions (fixed points of g) are x = −2 and x = 2. The derivative of the function is g 0 (x) = 1 − x/2, and there are only two cases to consider. Case(i) P = −2 Case(ii): P = 2 Start with p0 = −2.05 Start with p0 = 1.6 then get p1 = −2.100625 then get p1 = 1.96 p2 = −2.20378135 p2 = 1.9996 p3 = −2.41794441 p3 = 1.99999996 . . . . . . limn→∞ pn = −∞ limn→∞ pn = 2. Since |g 0 (x)| > 3 2 on [−3, −1], by The- Since |g 0 (x)| < 1 2 on [1, 3], by Theoorem 1.3, the sequence will not converge rem 1.3, the sequence will converge to to P = −2 P = 2. Theorem 1.3 does not state what will happen when g 0 (P) = 1. The next example has been specially constructed so that the sequence [pn] converges whenever p0 > P and it diverges if we choose p0 < P. Example 1.5. Consider the iteration pn+1 = g(pn) when the function g(x) = 2(x − 1)1/2 for x ≥ 1 is used. Only one fixed point P = 2 exists. The derivative is g 0 (x) = 1/(x − 1)1/2 and g 0 (2) = 1, so Theorem 3.3 does not apply. There are two cases to consider when the starting value lies to the left or right of P = 2. Case(i) Start with p0 = 1.5 Case(ii): Start with p0 = 2.5 then get p1 = 1.41421356 then get p1 = 2.44948974 p2 = 1.28718851 p2 = 2.40789513 p3 = 1.07179943 p3 = 2.37309514 p4 = 0.53590832 p4 = 2.34358284 . . . . . . p5 = 2(−0.46409168)1/2 . limn→∞ pn = 2. Since p4 lies outside the domain of This sequence is converging too slowly g(x), the term p5 cannot be computed to the value P = 2; indeed, P1000 = 2.00398714. 9
1.1.3 Absolute and relative Error Considerations In Example 1.5, case(ii), the sequence converges slowly, and after 1000 iterations the three consecutive terms are F1000=2.00398714,P0o1=2.00398317,and1002=2.00397921 This should not be disturbing; after all, we could compute a few thousand more terms and find a better approximation! But what about a criterion for stopping the iteration? Notice that if we use the difference between consecutive terms p101-p100=|2.00398317-2.003979211=0.0000396 Yet the absolute error in the approximation P1ooo is known to be |P-po|=2.000002.00398714=0.00398714 This is about 1000 times larger than P1001-P1002 and it shows that closeness of consecutive terms does not guarantee that accuracy has been achieved. But it is usually the only criterion available and is often used to terminate an iterative procedure Program 1.1(Fixed-Point Iteration). To approximate a solution to the equation =g() starting with the initial guess Po and iterating Pn+1= g(pn Function[k, p, err, P]=fixpt(g, po, tol, max1) %%%%%%%% %Input- g is the iteration function input as a string g po is the initial guess for the fixed tol is the tolerance max1 is the maximum number of iterations %Output- k is the number of iterations that were carried out -p is the approximation to the fixed point err is the error in the approximation P contains the sequence ( pn) P(1)=po; for k=2. max1 P(k)=feval(g, P(k-1)) err=abs(P(k)-P(k-1 relerr=err/abs(P(k))+eps) if(err<tol)I(relerr<tol), break;end end if k== max1 disp(maximum number of iterations exceeded) d P=P Remark. When using the user-defined function fixpt, it is necessary to input the M-file g m as a string: 'g'(see MATLAB Appendix) 10
1.1.3 Absolute and Relative Error Considerations In Example 1.5, case (ii), the sequence converges slowly, and after 1000 iterations the three consecutive terms are P1000 = 2.00398714, P1001 = 2.00398317, and P1002 = 2.00397921. This should not be disturbing; after all, we could compute a few thousand more terms and find a better approximation! But what about a criterion for stopping the iteration? Notice that if we use the difference between consecutive terms, |p1001 − p1002| = |2.00398317 − 2.00397921| = 0.00000396. Yet the absolute error in the approximation P1000 is known to be |P − p1000| = |2.00000000 − 2.00398714| = 0.00398714. This is about 1000 times larger than |p1001 − p1002| and it shows that closeness of consecutive terms does not guarantee that accuracy has been achieved. But it is usually the only criterion available and is often used to terminate an iterative procedure. Program 1.1 (Fixed-Point Iteration). To approximate a solution to the equation x = g(x) starting with the initial guess p0 and iterating pn+1 = g(pn). Function [k, p, err, P] =fixpt(g, po, tol, max1) % Input − g is the iteration function input as a string 0 g 0 % − po is the initial guess for the fixed point % − tol is the tolerance % − max1 is the maximum number of iterations %Output− k is the number of iterations that were carried out % − p is the approximation to the fixed point % − err is the error in the approximation % − P contains the sequence {pn} P(1)= po; for k=2:max1 P(k)=feval(g, P(k−1)); err=abs(P(k)−P(k−1)); relerr=err/(abs(P(k))+eps); p=P(k); if (err<tol) | (relerr<tol), break; end end if k == max1 disp(’maximum number of iterations exceeded’) end P=P’; Remark. When using the user-defined function fixpt, it is necessary to input the M-file g.m as a string: ’g’ (see MATLAB Appendix). 10