Chapter 1 The solution of nonlinear Equations∫(x)=0 Consider the physical problem that involves a spherical ball of radius r that is sub- merged to a depth d in water(see Figure 1.1). Assume that the ball is constructed from a variety of longleaf pine that has a density of p=0.638 and that its radius measures r= 10 cm. How much of the ball will be submerged when it is placed in water? The mass Mw of water displaced when a sphere is submerged to a depth d is dx d2(3r-d) and the mass of the ball is Mb= 4rrp/3. Applying Archimedes' law Mo Mb produces the following equation that must be solved 丌(d3-3d2r+4r3p) Figure 1.1 The portion of a sphere of radius r that is to be submerged to depth d
Chapter 1 The Solution of Nonlinear Equations f(x) = 0 Consider the physical problem that involves a spherical ball of radius r that is submerged to a depth d in water(see Figure 1.1). Assume that the ball is constructed from a variety of longleaf pine that has a density of ρ = 0.638 and that its radius measures r = 10 cm. How much of the ball will be submerged when it is placed in water? The mass Mw of water displaced when a sphere is submerged to a depth d is Mw = Z d 0 π(r 2 − (x − r) 2 )dx = πd2 (3r − d) 3 . and the mass of the ball is Mb = 4πr3ρ/3. Applying Archimedes’ law Mw = Mb, produces the following equation that must be solved: π(d 3 − 3d 2 r + 4r 3ρ) 3 = 0. Figure 1.1 The portion of a sphere of radius r that is to be submerged to depth d. 1
1000 Figure 1.2 The cubic y=2552-30d2+d In our case(with r= 10 and p=0.638)this equation becomes x(252-302+=0 The graph of the cubic polynomial y=2552-30d2+ds is shown in Figure 1.2 and from it one can see that the solution lies near the value d=12 The goal of this chapter is to develop a variety of methods for finding numerical approximations for the roots of an equation. For example, the bisection method could be applied to obtain the three roots di=8. 17607212, d2= 11.86150151, and d3 26.31457061. The first root di is not a feasible solution for this problem, because d cannot be negative. The third root ds is larger than the diameter of the sphere and it is not the desired solution. The root d2=11.86150151 lies in the interval [0, 20 and is the proper solution. Its magnitude is reasonable because a little more than one-half of the sphere must be submerge 1.1 Iteration for Solving =g(a A fundamental principle in computer science is iteration. As the name suggests, process is repeated until an answer is achieved. Iterative techniques are used to find roots equations, solutions of linear and nonlinear systems of equations, and solutions of differential equations. In this section we study the process of iteration using repeated substitution A rule or function g(a)for computing successive terms is needed, together with starting value po. Then a sequence of values pk) is obtained using the iterative rule
0 2 4 6 8 10 12 14 16 18 20 −1500 −1000 −500 0 500 1000 1500 2000 2500 3000 d y y=2552−30d2+d3 Figure 1.2 The cubic y = 2552 − 30d 2 + d 3 . In our case (with r = 10 and ρ = 0.638) this equation becomes π(2552 − 30d 2 + d 3 ) 3 = 0. The graph of the cubic polynomial y = 2552 − 30d 2 + d 3 is shown in Figure 1.2 and from it one can see that the solution lies near the value d = 12. The goal of this chapter is to develop a variety of methods for finding numerical approximations for the roots of an equation. For example, the bisection method could be applied to obtain the three roots d1 = −8.17607212, d2 = 11.86150151, and d3 = 26.31457061. The first root d1 is not a feasible solution for this problem, because d cannot be negative. The third root d3 is larger than the diameter of the sphere and it is not the desired solution. The root d2 = 11.86150151 lies in the interval [0, 20] and is the proper solution. Its magnitude is reasonable because a little more than one-half of the sphere must be submerged. 1.1 Iteration for Solving x = g(x) A fundamental principle in computer science is iteration. As the name suggests, a process is repeated until an answer is achieved. Iterative techniques are used to find roots equations, solutions of linear and nonlinear systems of equations, and solutions of differential equations. In this section we study the process of iteration using repeated substitution. A rule or function g(x) for computing successive terms is needed, together with a starting value p0. Then a sequence of values {pk} is obtained using the iterative rule 2
Pk+1= g(pk). The sequence has the pattern starting value) g(po) p2=9(p1) pk=9(pk-1) Pk+1=9(Dk) What can we learn from an unending sequence of numbers? If the numbers tend to a limit, we feel that something has been achieved. But what if the numbers diverge or are periodic? The next example addresses this situation Example 1.1. The iterative rule po= 1 and pk+1= 1.001pk for k=0, 1,..pro- duces a divergent sequence. The first 100 terms look as follows 1.0010=(1.001)(1.000000=1 p2=1.001p1=(1.001)(1.001000)=1.002001, P3=1.001p2=(1.001)(1.002001)=1003003 p100=1.001p-9=(1.001)(1.104012)=1.105116 The process can be continued indefinitely, and it is easily shown that limn-oo Pn =+oo In Chapter 9 we will see that the sequence Ipk is a numerical solution to the differ ential equation y=0.001y. The solution is known to be y(a)=e0.00lzr. Indeed, if we compare the 100th term in the sequence with y(100), we see that P100=1.105116 R 1.105171=c1=y(100) In this section we are concerned with the types of functions g() that produce convergent sequences Pk) 1.1.1 Finding Fixed Points Definition 1.1(Fixed Point). A fired point of a function g(a) is a real number P such that P=g(P) Geometrically, the fixed points of a function y= g(r) are the points of intersectio of y= g(r) and y Definition 1.2(Fixed-point Iteration). The iteration Pn+1=g(pn)for n=0, 1 s called fisced-point iteration
pk+1 = g(pk). The sequence has the pattern p0 (starting value) p1 = g(p0) p2 = g(p1) . . . pk = g(pk−1) pk+1 = g(pk) . . . (1.1) What can we learn from an unending sequence of numbers? If the numbers tend to a limit, we feel that something has been achieved. But what if the numbers diverge or are periodic? The next example addresses this situation. Example 1.1. The iterative rule p0 = 1 and pk+1 = 1.001pk for k = 0, 1, . . . produces a divergent sequence. The first 100 terms look as follows: p1 = 1.001p0 = (1.001)(1.000000) = 1.001000, p2 = 1.001p1 = (1.001)(1.001000) = 1.002001, p3 = 1.001p2 = (1.001)(1.002001) = 1.003003, . . . . . . . . . p100 = 1.001p99 = (1.001)(1.104012) = 1.105116. The process can be continued indefinitely, and it is easily shown that limn→∞ pn = +∞. In Chapter 9 we will see that the sequence {pk} is a numerical solution to the differential equation y 0 = 0.001y. The solution is known to be y(x) = e 0.001x . Indeed, if we compare the 100th term in the sequence with y(100), we see that p100 = 1.105116 ≈ 1.105171 = e 0.1 = y(100). In this section we are concerned with the types of functions g(x) that produce convergent sequences {pk}. 1.1.1 Finding Fixed Points Definition 1.1 (Fixed Point). A fixed point of a function g(x) is a real number P such that P = g(P). Geometrically, the fixed points of a function y = g(x) are the points of intersection of y = g(x) and y = x. Definition 1.2 (Fixed-point Iteration). The iteration pn+1 = g(pn) for n = 0, 1, . . . is called fixed-point iteration. 3
Theorem 1.1. Assume that g is a continuous function and that ipn no is a se- quence generated by fixed-point iteration. If limn-oo pn= P, then P is a fixed point 9(x) Proof. If limn-oo Pn= P, then limn-oo Pn+1= P. It follows from this result, the continuity of 9, and the relation pn+1= g(pn)that g(P)=g(lim pn)= lim g(pn)= lim Pn+1= P (1.2) Therefore, P is a fixed point of g(a) Example 1.2. Consider the convergent iteration po=0.5 and Pk+1 =ePk for k=0, 1, The first 10 terms are obtained by the calculations P1=c-0.50000.606531 0.60031=0.545239 P3=e-0545239=0.579703 0.566409 =0.567560 p10=e-06750=0.566907 The sequence is converging, and further calculations reveal that lim pn2=0.567143. Thus we have found an approximation for the fixed point of the function y =e-r n The following two theorems establish conditions for the existence of a fixed point d the convergence of the fixed- point iteration process to a fixed point Theorem 1.2 Assume that g E Cla, b If the range of the mapping y= g(a)satisfies y E a, b for all x E [a, b],then g has a fixed point in a, b (1.3) Furthermore, suppose that g(a) is defined over (a, b) and that a positive constant K l exists with Ig(a)l< K< l for all E(a, b),then g has a(1.4) unique fixed point P in [a, b
Theorem 1.1. Assume that g is a continuous function and that {pn} ∞ n=0 is a sequence generated by fixed-point iteration. If limn→∞ pn = P, then P is a fixed point of g(x). Proof. If limn→∞ pn = P, then limn→∞ pn+1 = P. It follows from this result, the continuity of g, and the relation pn+1 = g(pn) that g(P) = g( limn→∞ pn) = limn→∞ g(pn) = limn→∞ pn+1 = P. (1.2) Therefore, P is a fixed point of g(x). Example 1.2. Consider the convergent iteration p0 = 0.5 and pk+1 = e −pk for k = 0, 1, . . . . The first 10 terms are obtained by the calculations p1 = e −0.500000 = 0.606531 p2 = e −0.606531 = 0.545239 p3 = e −0.545239 = 0.579703 . . . . . . p9 = e −0.566409 = 0.567560 p10 = e −0.567560 = 0.566907 The sequence is converging, and further calculations reveal that limn→∞ pn = 0.567143 . . . . Thus we have found an approximation for the fixed point of the function y = e −x . The following two theorems establish conditions for the existence of a fixed point and the convergence of the fixed-point iteration process to a fixed point. Theorem 1.2 Assume that g ∈ C[a, b]. If the range of the mapping y = g(x) satisfies y ∈ [a, b] for all x ∈ [a, b], then g has a fixed point in [a, b]. (1.3) Furthermore, suppose that g 0 (x) is defined over (a, b) and that a positive constant K < 1 exists with |g 0 (x)| ≤ K < 1 for all x ∈ (a, b) ,then g has a unique fixed point P in [a, b]. (1.4) 4
Proof of (1.3). If g(a)=a or g(b)=b, the assertion is true. Otherwise, the values of g(a) and g(b)must satisfy g(a E(a, b and g(b)e a, b). The function f(a)= -g(a) has the property that f(a=a-g(a)<0 and f(b)=b-g(b) Now apply Theorem 0.2, the Intermediate Value Theorem, to f(r), with the constant L=0, and conclude that there exists a number P with P E(a, b)so that f(P)=0 Therefore, P=g(P) and P is the desired fixed point of g(r) Proof of (1.4). Now we must show that this solution is unique. By way of contra- diction, let us make the additional assumption that there exist two fixed points Pi and P2. Now apply Theorem 0.6, the Mean Value Theorem, and conclude that there exists a number d e(a, b) so that 0(d)=9P2)-P Next, use the facts that g(Pi)= P and g(p2)= P2 to simplify the right side of quation(1.5) and obtain 9(d) P2-Pi P2-P1 But this contradicts the hypothesis in(1.4)thatll()l< l over(a, b), so it is not possible for two fixed points to exist. Therefore, g(a) has a unique fixed point P in [a, b under the conditions given in(1.4) Example 1. 3. Apply Theorem 1.2 to rigorously show that g(a)=cos(a)has a unique fixed point in 0 Clearly, g E C(0, 1] secondly, g(a)=cos(r)is a decreasing function on 0, 1, thus s range on 0, 1 is [cos(1),1]C [0, 1. Thus condition(3)of Theorem 2.2 is satisfied and g has a fixed point in [0, 1. Finally, if a E(0, 1), then lg'(a)l=|-sin(r)l= sin(a)< sin(1)<0.8415< 1. Thus K= sin(1)< 1, condition(1. 4)of Theorem 1.2 is satisfied, and g has a unique fixed point in [0,1] We can now state a theorem that can be used to determine whether the fixed-point iteration process given in(1.1) will produce a convergent or divergent sequence Theorem 1.3(Fixed-point Theorem). Assume that (i)g, g E Cla, b,(ii)K is a positive constant,(i)f∈(a,b),and(iv)g(x)∈a,列 for all ar∈@a,b If Ig()< K< l for all a E [a, b, then the iteration pn=g(pn-1)will he unique fixed point P E a, b]. In this case, P is said to be (1.6) If lg(a)> 1 for all r E a, b, then the iteration Pn=g(pn-1) will not con- verge to P. In this case, P is said to be a repelling fixed point and the iter-(1.7) ation exhibits local divergence
Proof of (1.3). If g(a) = a or g(b) = b, the assertion is true. Otherwise, the values of g(a) and g(b) must satisfy g(a) ∈ (a, b] and g(b) ∈ [a, b). The function f(x) = x − g(x) has the property that f(a) = a − g(a) < 0 and f(b) = b − g(b) > 0. Now apply Theorem 0.2, the Intermediate Value Theorem, to f(x), with the constant L = 0, and conclude that there exists a number P with P ∈ (a, b) so that f(P) = 0. Therefore, P = g(P) and P is the desired fixed point of g(x). Proof of (1.4). Now we must show that this solution is unique. By way of contradiction, let us make the additional assumption that there exist two fixed points P1 and P2. Now apply Theorem 0.6, the Mean Value Theorem, and conclude that there exists a number d ∈ (a, b) so that g 0 (d) = g(P2) − g(P1) P2 − P1 . (1.5) Next, use the facts that g(P1) = P1 and g(P2) = P2 to simplify the right side of equation (1.5) and obtain g 0 (d) = P2 − P1 P2 − P1 = 1. But this contradicts the hypothesis in (1.4) that|g 0 (x)| < 1 over (a, b), so it is not possible for two fixed points to exist. Therefore, g(x) has a unique fixed point P in [a, b] under the conditions given in (1.4). Example 1.3. Apply Theorem 1.2 to rigorously show that g(x) = cos(x) has a unique fixed point in [0, 1]. Clearly, g ∈ C[0, 1] secondly, g(x) = cos(x) is a decreasing function on [0, 1], thus its range on [0, 1] is [cos(1), 1] ⊆ [0, 1]. Thus condition (3) of Theorem 2.2 is satisfied and g has a fixed point in [0, 1]. Finally, if x ∈ (0, 1), then |g 0 (x)| = | − sin(x)| = sin(x) ≤ sin(1) < 0.8415 < 1. Thus K = sin(1) < 1, condition (1.4) of Theorem 1.2 is satisfied, and g has a unique fixed point in [0, 1]. We can now state a theorem that can be used to determine whether the fixed-point iteration process given in (1.1) will produce a convergent or divergent sequence. Theorem 1.3 (Fixed-point Theorem). Assume that (i) g, g0 ∈ C[a, b], (ii) K is a positive constant, (iii) P0 ∈ (a, b), and (iv) g(x) ∈ [a, b] for all x ∈ [a, b]. If |g 0 (x)| ≤ K < 1 for all x ∈ [a, b], then the iteration pn = g(pn−1) will converge to the unique fixed point P ∈ [a, b]. In this case, P is said to be an attractive fixed point. (1.6) If |g 0 (x)| > 1 for all x ∈ [a, b] ,then the iteration pn = g(pn−1) will not converge to P. In this case, P is said to be a repelling fixed point and the iteration exhibits local divergence. (1.7) 5