1.1.4 Exercises for Iteration for Solving T=g(a) 1. Determine rigorously if each function has a unique fixed point on the given interval ( follow Example 1.3) (a)g(x)=1-x2/4on[0,1 (b)g(x)=2-zon0,1 (c)g(x)=1/ron0.5,5.2 2. Investigate the nature of the fixed-point iteration when g(x)=-4+4x-5x2 (a) Solve g(a)=r and show that P=2 and P=4 are fixed points (b) Use the starting value po= 1.9 and compute p1, P2, and p3 (c)Use the starting value po=3.8 and compute P1, P2, and p3 (d) Find the errors Ek and relative errors Rk for the values Pk in parts(b)and(c) (e) What conclusions can be drawn from Theorem 1.3? 3. Graph g(a), the line y=a, and the given fixed point P on the same coordinate system. Using the given starting value po, compute pi and p2. Construct figures similar to Figures 1.4 and 1.5. Based on your graph, determine geometrically if fixed-point iteration converges (a)g(x)=(6+x)1/2,P=3,andp=7 (b)9(x)=1+2/x,P=2, and po=4 (c)g(x)=x2/3,P=3,andp=35 (d)g(x)=-x2+2x+2,P=2,andp=25 4. Let g(r)=r2+I-4. Can fixed-point iteration be used to find the solution(s)to the equation =g(a)? Why? 5. Let g(a)=a cos( r). Solve r= g(a) and find all the fixed points of g(there are infinitely many). Can fixed-point iteration be used to find the solution(s)to the equation =g(ar)? Why? 6. Suppose that g(a)and g(a)are defined and continuous on(a, b); po, p1, P2 E(a, b) nd pi= g(po) and p2=9(p1). Also, assume that there exists a constant K such that lg(a)< K. Show that lp2-Pll KlPi-Po Hint. Use the Mean value Theorem 7. Suppose that g(a) and g (a) are continuous on(a, b) and that lg(a)>l on this interval. If the fixed point P and the initial approximations po and pi lie in interval(a, b), then show that Pi=g(po) implies that E1=IP-pil>P Eol. Hence statement(1.7)of Theorem 1.3 is established(local divergence) 8. Let g(a)=-00001 2+a and po= 1, and consider fixed-point iteration (a) Show that po>P1> (b) Show that
1.1.4 Exercises for Iteration for Solving x = g(x) 1. Determine rigorously if each function has a unique fixed point on the given interval (follow Example 1.3). (a) g(x) = 1 − x 2/4 on [0, 1] (b) g(x) = 2−x on [0, 1] (c) g(x) = 1/x on [0.5, 5.2] 2. Investigate the nature of the fixed-point iteration when g(x) = −4 + 4x − 1 2 x 2 . (a) Solve g(x) = x and show that P = 2 and P = 4 are fixed points. (b) Use the starting value p0 = 1.9 and compute p1, p2, and p3. (c) Use the starting value p0 = 3.8 and compute p1, p2, and p3. (d) Find the errors Ek and relative errors Rk for the values pk in parts (b) and (c). (e) What conclusions can be drawn from Theorem 1.3? 3. Graph g(x), the line y = x, and the given fixed point P on the same coordinate system. Using the given starting value p0, compute p1 and p2. Construct figures similar to Figures 1.4 and 1.5. Based on your graph, determine geometrically if fixed-point iteration converges. (a) g(x) = (6 + x) 1/2 , P = 3, and p0 = 7 (b) g(x) = 1 + 2/x, P = 2, and p0 = 4 (c) g(x) = x 2/3, P = 3, and p0 = 3.5 (d) g(x) = −x 2 + 2x + 2, P = 2, and p0 = 2.5 4. Let g(x) = x 2 + x − 4. Can fixed-point iteration be used to find the solution(s) to the equation x = g(x)? Why? 5. Let g(x) = x cos(x). Solve x = g(x) and find all the fixed points of g (there are infinitely many). Can fixed-point iteration be used to find the solution(s) to the equation x = g(x)? Why? 6. Suppose that g(x) and g 0 (x) are defined and continuous on (a, b); p0, p1, p2 ∈ (a, b); and p1 = g(p0) and p2 = g(p1). Also, assume that there exists a constant K such that |g 0 (x)| < K. Show that |p2 − p1| < K|p1 − p0|. Hint. Use the Mean Value Theorem. 7. Suppose that g(x) and g 0 (x) are continuous on (a, b) and that |g 0 (x)| > 1 on this interval. If the fixed point P and the initial approximations p0 and p1 lie in the interval (a, b), then show that p1 = g(p0) implies that |E1| = |P − p1| > |P − p0| = |E0|. Hence statement (1.7) of Theorem 1.3 is established (local divergence). 8. Let g(x) = −0.0001x 2 + x and p0 = 1, and consider fixed-point iteration. (a) Show that p0 > p1 > · · · > pn > pn+1 > · · ·. (b) Show that pn > 0 for all n. 11
(c)Since the sequence (pn is decreasing and bounded below, it has a limit. What s the limit? 9. Let g(a)=0.5.z +1.5 and po= 4, and consider fixed-point iteration (a) Show that the fixed point is P=3 (b)Show that P-pn=IP-Pn-1l/2 for n= 1, 2, 3 (c) Show that IP-Pn =IP-pol/ 2n for n= 1, 2, 3 10. Let g(a)=a/2, and consider fixed-point iteration (a)Find the quantity pk+1-P:l/pk+1 (b) Discuss what will happen if only the relative error stopping criterion were used in program 1.1 11. For fixed-point iteration, discuss why it is an advantage to have g (P)N 1.1.5 Algorithms and programs 1. Use Program 1. 1 to approximate the fixed points(if any) of each function. Answers should be accurate to 12 decimal places. Produce a graph of each function and the line y= that clearly sh shows any fixed points (a)g(x)=x5-3x3-2n2+2 (b)g(a)=cos(sin(a) (c)g(x)=x2-sin(x+0.15) (d)g(a) 1.2 Bracketing Methods for Locating a root Consider a familiar topic of interest. Suppose that you save money by making regular monthly deposits p and the annual interest rate is 1; then the total amount A after N A=P+P(1+ 12/+P(1+ The first term on the right side of equation(1.15)is the last payment. Then the next to-last payment, which has earned one period of interest, contributes P(1+1).The second-from-last payment has earned two periods of interest and contributes P(1+n) and so on. Finally, the last payment, which has earned interest for N-1 periods contributes P(1+b) -toward the total. Recall that the formula for the sum of the N terms of a geometric series is 12
(c) Since the sequence {pn} is decreasing and bounded below, it has a limit. What is the limit? 9. Let g(x) = 0.5x + 1.5 and p0 = 4, and consider fixed-point iteration. (a) Show that the fixed point is P = 3. (b) Show that |P − pn| = |P − pn−1|/2 for n = 1, 2, 3, . . .. (c) Show that |P − pn| = |P − p0|/2 n for n = 1, 2, 3, . . .. 10. Let g(x) = x/2, and consider fixed-point iteration. (a) Find the quantity |pk+1 − pk|/pk+1. (b) Discuss what will happen if only the relative error stopping criterion were used in Program 1.1. 11. For fixed-point iteration, discuss why it is an advantage to have g 0 (P) ≈ 0. 1.1.5 Algorithms and Programs 1. Use Program 1.1 to approximate the fixed points (if any) of each function. Answers should be accurate to 12 decimal places. Produce a graph of each function and the line y = x that clearly shows any fixed points. (a) g(x) = x 5 − 3x 3 − 2x 2 + 2 (b) g(x) = cos(sin(x)) (c) g(x) = x 2 − sin(x + 0.15) (d) g(x) = x x−cos(x) 1.2 Bracketing Methods for Locating a Root Consider a familiar topic of interest. Suppose that you save money by making regular monthly deposits P and the annual interest rate is I; then the total amount A after N deposits is A = P + P µ 1 + I 12¶ + P µ 1 + I 12¶2 + · · · + P µ 1 + I 12¶N−1 . (1.15) The first term on the right side of equation (1.15) is the last payment. Then the nextto-last payment, which has earned one period of interest, contributes P(1 + I 12 ). The second-from-last payment has earned two periods of interest and contributes P(1+ I 12 ) 2 , and so on. Finally, the last payment, which has earned interest for N − 1 periods, contributes P(1 + I 12 ) N−1 toward the total. Recall that the formula for the sum of the N terms of a geometric series is 1 + r + r 2 + r 3 + · · · + r N−1 = 1 − r N 1 − r . (1.16) 12
We can write(1.15) in the form A=P1+1 12 and use the substitution r=(1+I/12)in(1.16) to obtain A=P (1+ (1+) This can be simplified to obtain the annuity-due equation P I/12 (1.17) lep. The following example uses the annuity-due equation and requires a sequence of eated calculations to find an answer Example 1.6. You save $250 per month for 20 years and desire te total value of all payments and interest is $250,000 at the end of the 20 years interest rate I is needed to achieve your goal? If we hold N=240 fixed, then A is a function of I alone; that is A= A(I). We will start with two guesses, Io=0.12 and I1=0.13 and perform a sequence of calculations to narrow down the final answer. Starting with Io=0.12 yields 250 0.12\240 A(0.12) =247.314. 0.12/12 12 Since this value is a little short of the goal, we next try 11=0.13 250 0.13240 A(0.13) =282,311 0.13/12 This is a little high, so we try the value in the middle I2=0. 125 250 A(0.125) 0.125 This high and we conclude that the desired rate lies in the interval 0.12, 0.125 The next guess is the midpoint 13=0.1225 A(0.1223=0.121277,0-1225240 250 1)=255,803 12 This is high and the interval is now narrowed to 0.12, 0.1225]. Our last calculation uses the midpoint approximation 14=0. 12125 0.12125240 A(0.12125) 1=251,518 0.12125/12
We can write (1.15) in the form A = P à 1 + µ 1 + I 12¶ + µ 1 + I 12¶2 + · · · + µ 1 + I 12¶N−1 ! . and use the substitution r = (1 + I/12) in (1.16) to obtain A = P 1 − (1 + I 12 ) N 1 − (1 + I 12 ) . This can be simplified to obtain the annuity-due equation, A = P I/12 õ 1 + I 12¶N − 1 ! . (1.17) The following example uses the annuity-due equation and requires a sequence of repeated calculations to find an answer. Example 1.6. You save $250 per month for 20 years and desire that the total value of all payments and interest is $250,000 at the end of the 20 years. What interest rate I is needed to achieve your goal? If we hold N = 240 fixed, then A is a function of I alone; that is A = A(I). We will start with two guesses, I0 = 0.12 and I1 = 0.13, and perform a sequence of calculations to narrow down the final answer. Starting with I0 = 0.12 yields A(0.12) = 250 0.12/12 µ³ 1 + 0.12 12 ´240 − 1 ¶ = 247, 314. Since this value is a little short of the goal, we next try I1 = 0.13: A(0.13) = 250 0.13/12 µ³ 1 + 0.13 12 ´240 − 1 ¶ = 282, 311. This is a little high, so we try the value in the middle I2 = 0.125: A(0.125) = 250 0.125/12 µ³ 1 + 0.125 12 ´240 − 1 ¶ = 264, 623. This is again high and we conclude that the desired rate lies in the interval [0.12, 0.125]. The next guess is the midpoint I3 = 0.1225: A(0.1225) = 250 0.1225/12 µ³ 1 + 0.1225 12 ´240 − 1 ¶ = 255, 803. This is high and the interval is now narrowed to [0.12, 0.1225]. Our last calculation uses the midpoint approximation I4 = 0.12125: A(0.12125) = 250 0.12125/12 µ³ 1 + 0.12125 12 ´240 − 1 ¶ = 251, 518. 13
(a) If f(a) and f(c) have opposite signs then squeeze from the right (b)If f(c) and f(b) have opposite signs then squeeze from the left Figure 1.6 The decision process for the bisection process Further iterations can be done to obtain as many significant digits as required. The purpose of this example was to find the value of I that produced a specified level L of the function value, that is to find a solution to A(D)=L. It is standard practice to place the constant L on the left and solve the equation A(D)-L= Definition 1. 3(Root of an Equation, Zero of a Function). Assume that f(a) is a continuous function. Any number r for which f(r)=0 is called a root of the equation f(r)=0. Also, we say r is a zero of the function f(a) For example, the equation 20+52-3=0 has two real roots r1=0.5 and r3 whereas the corresponding function f(r)=2.x2+5.x-3=(2c-1)(a+3)has two real zeros, ri=0.5 and r2=-3 1.2.1 The bisection method of bolzano In this section we develop our first bracketing method for finding a zero of a continuous function. We must start with an initial interval a, bl, where f(a) and f(b) have opposite signs. Since the graph y= f() of a continuous function is unbroken, it will cross the r-axis at a zero r= r that lies somewhere in the interval(see Figure 1.6). The bisection method systematically moves the end points of the interval closer and closer together until we obtain an interval of arbitrarily small width that brackets the zero The decision step for this process of interval halving is first to choose the midpoint
0 0.5 1 1.5 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.5 y=f(x) (r,0) (c,f(c)) (a,f(a)) (b,f(b)) a b c 0 0.5 1 1.5 −1 −0.5 0 0.5 1 1.5 (a,f(a)) y=f(x) (r,0) (b,f(b)) (c,f(c)) (a) If f(a) and f(c) have opposite signs then squeeze from the right. (b) If f(c) and f(b) have opposite signs then squeeze from the left. Figure 1.6 The decision process for the bisection process. Further iterations can be done to obtain as many significant digits as required. The purpose of this example was to find the value of I that produced a specified level L of the function value, that is to find a solution to A(I) = L. It is standard practice to place the constant L on the left and solve the equation A(I) − L = 0. Definition 1.3 (Root of an Equation, Zero of a Function). Assume that f(x) is a continuous function. Any number r for which f(r) = 0 is called a root of the equation f(x) = 0. Also, we say r is a zero of the function f(x). For example, the equation 2x 2+5x−3 = 0 has two real roots r1 = 0.5 and r3 = −3, whereas the corresponding function f(x) = 2x 2 + 5x − 3 = (2x − 1)(x + 3) has two real zeros, r1 = 0.5 and r2 = −3. 1.2.1 The Bisection Method of Bolzano In this section we develop our first bracketing method for finding a zero of a continuous function. We must start with an initial interval [a, b], where f(a) and f(b) have opposite signs. Since the graph y = f(x) of a continuous function is unbroken, it will cross the x -axis at a zero x = r that lies somewhere in the interval (see Figure 1.6). The bisection method systematically moves the end points of the interval closer and closer together until we obtain an interval of arbitrarily small width that brackets the zero. The decision step for this process of interval halving is first to choose the midpoint 14
c=(a+b)/2 and then to analyze the three possibilities that might arise If f(a) and f(c) have opposite signs, a zero lies in [a, c (1.18 If f(c)and f(b) have opposite signs, a zero lies in [c, b (1.19) If f(c=0, then the zero is c (1.20 If either case(1.18)or(1.19)occurs, we have found an interval half as wide as the original interval that contains the root, and we are"squeezing down on it"(see Figure 1.6). To continue the process, relabel the new smaller interval a, b and repeat the process until the interval is as small as desired. Since the bisection process involves sequences of nested intervals and their midpoints, we will use the following notation te keep track of the details in the process bol is the starting interval andco= gob is the midpoint [a1, b1 is the second interval, which brackets the zero r, and cI is its midpoint the interval [a1, b1 is half as wide as [ ao, bol After arriving at thenth interval [an, bnl, which brackets r and has midpoint the interval an+1, bn+il is constructed, which also brackets r and is half as wide as [an, bnl It is left as an exercise for the reader to show that the sequence of left end points is increasing and the sequence of right end points is decreasing; that is a0<a1<…<an≤…<r<…<bn<…<b1<b, where cn= an*bn, and if f(an+1)f(bn+1)<0,then Lan+1, bn+1]=[an, Cn] or an+1, bn+1=[cn, bn for all n Theorem 1.4 (Bisection Theorem). Assume that f e Cla, b and that there exists a number r E [ a, b such that f(r)=0. If f(a) and f(b) have opposite signs, and Ienlnso represents the sequence of midpoints generated by the bisection process of (1.22)and(1.23),then r-cn|≤ (1.24) and there fore the sequence cn ioo converges to the zero r =r; that is m Proof. Since both the zero r and the midpoint lie in the interval [an, bn], the distance between Cn and r cannot be greater than half the width of this interval(see Figure 1.7). Thus Ir-cnlson t n for all n (1
c = (a + b)/2 and then to analyze the three possibilities that might arise: If f(a) and f(c) have opposite signs, a zero lies in [a, c]. (1.18) If f(c) and f(b) have opposite signs, a zero lies in [c, b]. (1.19) If f(c) = 0, then the zero is c. (1.20) If either case (1.18) or (1.19) occurs, we have found an interval half as wide as the original interval that contains the root, and we are ”squeezing down on it” (see Figure 1.6). To continue the process, relabel the new smaller interval [a, b] and repeat the process until the interval is as small as desired. Since the bisection process involves sequences of nested intervals and their midpoints, we will use the following notation to keep track of the details in the process: [a0, b0] is the starting interval andc0 = a0+b0 2 is the midpoint. [a1, b1] is the second interval, which brackets the zero r, and c1 is its midpoint; the interval [a1, b1] is half as wide as [a0, b0]. After arriving at thenth interval [an, bn], which brackets r and has midpoint cn, the interval [an+1, bn+1] is constructed, which also brackets r and is half as wide as [an, bn]. (1.21) It is left as an exercise for the reader to show that the sequence of left end points is increasing and the sequence of right end points is decreasing; that is, a0 ≤ a1 ≤ · · · ≤ an ≤ · · · ≤ r ≤ · · · ≤ bn ≤ · · · ≤ b1 ≤ b0, (1.22) where cn = an+bn 2 , and if f(an+1)f(bn+1) < 0, then [an+1, bn+1] = [an, cn] or [an+1, bn+1] = [cn, bn] for all n (1.23) Theorem 1.4 (Bisection Theorem). Assume that f ∈ C[a, b] and that there exists a number r ∈ [a, b] such that f(r) = 0. If f(a) and f(b) have opposite signs, and {cn} ∞ n=0 represents the sequence of midpoints generated by the bisection process of (1.22) and (1.23), then |r − cn| ≤ b − a 2 n+1 n = 0, 1, . . . , (1.24) and there fore the sequence {cn} ∞ n=0 converges to the zero x = r; that is, limn→∞ cn = r. (1.25) Proof. Since both the zero r and the midpoint lie in the interval [an, bn], the distance between cn and r cannot be greater than half the width of this interval (see Figure 1.7). Thus |r − cn| ≤ bn − an 2 for all n (1.26) 15