Nonlinear Equations PDF

Nonlinear Eqautions Prepared by drlmpaleta Contents 1 Introduction to Nonlinear Equations 2 2 Closed domain methods 3 2.1 Learning objectives....................

Nonlinear Eqautions Prepared by drlmpaleta Contents 1 Introduction to Nonlinear Equations 2 2 Closed domain methods 3 2.1 Learning objectives............................ 3 3 Bisection Method 3 3.1 Steps.................................... 4 4 Algorithm 5 5 Solved exercises 7 6 Convergence and Error Estimate of Bisection Method 7 7 Rates of Convergence 9 8 Comments on Bisection method 10 9 Examples with Scilab 12 10 MathLab codes 12 11 Exercise 13 1 1 Introduction to Nonlinear Equations One of the most frequently occurring problems in practical applications is to find the roots of equations of the form f (x) = 0 (1) where f : [a, b] → R is a given nonlinear function. It is well-known that not all nonlinear equations can be solved explicitly to obtain the exact value of the roots and hence, we need to look for methods to compute approximate value of the roots. By approximate root to equation 1, we mean a point x∗ ∈ R for which the value f (x) is very near to zero, i.e., f (x∗ ) = 0. In this chapter, we introduce various iterative methods to obtain an approximation to a real root of equations of the form 1 with f being a continuous nonlinear function. The key idea in approximating the real roots of 1 consists of two steps: Starting Step: Take one or more points (arbitrarily or following a procedure) xi ∈ [a, b], (i = 0, 1, · · · , m, m ∈ N) around a root of the equation 1. Consider xm as an approximation to the root of 1. Improving Step: If xm is not ‘close’ to the required root, then devise a procedure to obtain another point xm+1 that is ‘more close’ to the root than xm. Repeat this step until we obtain a point xn (n ≥ m) which is ‘sufficiently close’ to the required root. This process of improving the approximation to the root is called the iterative process (or iterative procedure), and such methods are called iterative methods. In an iterative method, we obtain a sequence of numbers xn which is expected to converge to the root of 1 as n ← ∞. We investigate conditions on the function f , its domain, and co-domain under which the sequence of iterates converge to a solution of the equation 1. We classify the iterative methods discussed in this chapter into two types, namely, Closed Domain Methods: As the starting step, these methods need the knowledge of an interval in which at least one root of the given nonlinear equation exists. Further iterations include the restriction of this interval to smaller intervals in which root lies. These methods are also called bracketing methods. Open Domain Methods: The x′i s mentioned in the starting step above are chosen arbitrarily and the consecutive iterations are based on a formula In the case of closed domain methods, the difficult part is to locate an interval containing a root. But, once this is done, the iterative sequence will surely converge 2 as we will see in the next Section. In this section, we discuss two closed domain methods, namely, the bisection method and the regula-falsi method. In the case of open domain methods, it is easy at the starting step as we can choose the x′i s arbitrarily. But, it is not necessary that the sequence converges. We discuss secant method, Newton-Raphson method and fixed point method in Section 4.3, which are some of the open domain methods. 2 Closed domain methods The idea behind the closed domain methods is to start with an interval (denoted by [a0 , b0 ]) in which there exists at least one root of the given nonlinear equations and then reduce the length of this interval iteratively with the condition that there is at least one root of the equation at each iteration. Note that the initial interval [a0 , b0 ] can be obtained using the intermediate value theorem (as we always assume that the nonlinear function f is continuous) by checking the condition that f (a0 )f (b0 ) < 0. That is, f (a0 ) and f (b0 ) are of opposite sign. The closed domain methods differ from each other only by the way they go on reducing the length of this interval at each iteration. In the following subsections we discuss two closed domain methods, namely, (i) the bisection method and (ii) the regula-falsi method. 2.1 Learning objectives At the end of this unit, students will be able to: 1. define bisection method 2. explain the steps of bisection method 3. give the algorithm of the bisection method 4. familiarize the bisection method code using SciLab 5. familiarize the bisection method code using SciLab 6. explore the codes using computer 3 Bisection Method Starting from this section, we study the most basic mathematics problem: root-finding problem f (x) = 0. The first numerical method, based on the Intermediate Value Theorem (IVT), is called the Bisection Method. 3  Suppose that f (x) is continuous on [a, b]. f (a) and f (b) have opposite sign. By IVT, there exists a numberp ∈ (a, b) such that f (p) = 0. That is, f (x) has a root in (a, b). The most simple way of reducing the length of the interval is to sub-divide the interval into two equal parts and then take the sub-interval that contains a root of the equation and discard the other part of the interval. This method is called the bisection method. Let us explain the procedure of generating the first iteration of this method. Step 1: Define x1 to be the mid-point of the interval [a0 , b0 ]. That is, ao + b0 x1 =. 2 Step 2: Now, exactly one of the following two statements hold. (a) x1 solves the nonlinear equation. That is, f (x1 ) = 0. (b) Either f (a0 )f (f (x1 )) < 0 or f (x1 )f (b0 ) < 0. If case (1) above holds, then x1 is a required root of the given equation f (x) = 0 and therefore we stop the iterative procedure. If f (x) ̸= 0, then case (2) holds as f (a0 ) and f (b0 ) are already of opposite signs. In this case, we define a subinterval [a1 , b1 ] of [a0 , b0 ] as follows. ( [a0 , x1 ], iff (a0 )f (x1 ) < 0, [a1 , b1 ] = [x1 , b0 ], iff (x1 )f (b0 ) < 0. The outcome of the first iteration of the bisection method is the interval [a1 , b1 ] and the first member of the corresponding iterative sequence is the real number x1. Observe that the length of the interval [a1 , b1 ] is exactly half of the length of [a0 , b0 ] and [a1 , b1 ] has at least one root of the nonlinear equation f (x) = 0. Similarly, we can obtain x2 and [a2 , b2 ] as the result of the second iteration and so on. Idea of Bisection Method: repeatedly halve the subinterval of [a, b], and at each step, locating the half containing the root. 3.1 Steps Set a1 ← a, b1 ← b. Calculate the midpoint p1 ← a1 +b1 2 If f (p1 ) = 0, then p ← p1, done. 4  Figure 1: Bisection Method If f (p1 ) ̸= 0, then f (p1 ) has the sam sign as either f (a) or f (b). – If f (p1 ) and f (a) have the same sign, thenp ∈ (p1 , b1 ). Set a2 ← p1 , and b2 ← b1. – If f (p1 ) and f (b) have the same sign, then p ∈ (a1 , p1 ). Set a2 ← a1 , and b2 ← p1. Repeat the process on [a2 , b2 ] 4 Algorithm We now present the algorithm for the bisection method. Hypothesis: There exists an interval [a0 , b0 ] such that the function f : [a0 , b0 ] → R is continuous, and the numbers f (a) and f (b) have opposite signs. Algorithm: Step 1: For n = 0, 1, 2, · · · , define the iterative sequence of the bisection method as an + bn xn+1 = 2 which is the midpoint of the interval [an , bn ]. Step 2: One of the following two cases hold. xn+1 solves the nonlinear equation. That is, f (xn+1 ) = 0. Either f (an )f (xn+1 ) < 0 or f (bn )f (xn+1 ) < 0. Define the subinterval [an+1 , bn+1 ] of [an , bn ] as follows. 5  ( [an , xn+1 ], if f (an )f (xn+1 ) < 0, [an+1 , bn+1 ] = [xn+1 , bn ], if f (bn )f (xn+1 ) < 0. Step 3: Stop the iteration if one of the following happens: the case (1) in step 2 holds. Then declare the value of xn+1 as the required roo. bn+1 −an+1 is sufficiently small (less than a pre-assigned positive quantity). Then declare the value of xn+2 as the required root up to the desired accuracy. If any of the above stopping criteria does not hold, then go to step 1. Continue this process till one of the above two stopping criteria is fulfilled. Remark 4.1 In practice, one may also use any of the stopping criteria listed in section 4.2, either single or multiple criteria. Assuming that, for each n = 1, 2, · · · , the number xn is not a solution of the nonlinear equation f (x) = 0, we get a sequence of real numbers xn. The question is whether this sequence converges to a solution of the nonlinear equation f (x) = 0. We now discuss the error estimate and convergence of the iterative sequence generated by the bisection method. Figure 2: Algorithm for Bisection Method This above algorithm will perform 20 times bisection iterations. The number 20 is artificial. 6 5 Solved exercises Example: Finding the root of the function f (x) = x3 − 2x − 5 using the bisection method on the interval [2, 3], with a tolerance of 10−6 and a maximum of 1000 iterations. 1. Initialization: Given the interval [2, 3]. 2. Iteration 1: Midpoint: c = 2+3 2 = 2.5 Evaluate f (2.5) = (2.5)3 − 2(2.5) − 5 = −0.125 Since f (2.5) < 0, the root lies in [2.5, 3]. 3. Iteration 2: Midpoint: c = 2.5+3 2 = 2.75 Evaluate f (2.75) = (2.75)3 − 2(2.75) − 5 = 1.1094 Since f (2.75) > 0, the root lies in [2.5, 2.75]. 4. Iteration 3: Midpoint: c = 2.5+2.75 2 = 2.625 Evaluate f (2.625) = (2.625)3 − 2(2.625) − 5 = 0.4551 Since f (2.625) > 0, the root lies in [2.5, 2.625]. This process continues until the desired tolerance is reached or the maximum number of iterations is reached. In this example, we converge to a root x ≈ 2.5156. Remark 5.1 Using MatLab, this converge to to a root within [2.0945, 2.0946]. So need to be re-evaluated. Example 5.2 The function f (x) = x3 − x2 − 1 has exactly one zero in [1, 2]. Use the bisection algorithm to approximate the zero of f to within 10−4. 6 Convergence and Error Estimate of Bisection Method Theorem 6.1 Convergence and Error Estimate of Bisection Method. Hypothesis: Let f : [a0 , b0 ] ← R be a continuous function such that the numbers f (a0 ) and f (b0 ) have opposite signs. Conclusion: There exists an r ∈ (a0 , b0 ) such that f (r) = 0 and the iterative sequence xn of the bisection method converges to r. 7  For each n = 0, 1, 2, · · · , we have the following error estimate 1 |xn+1 − r| ≤ ( )n+1 (b0 − a0 ). (2) 2 Proof : It directly follows from the construction of the intervals [an , bn ] that 1 1 bn − an = (bn−1 − an−1 ) = · · · = ( )n (b0 − a0 ). 2 2 For complete and detailed proof refer to , pages 122-123. Corollary 6.1 Let ϵ > 0 be given. Let f satisfy the hypothesis of bisection method with the interval [a0 , b0 ]. Let xn be as in the bisection method, and r be the root of the nonlinear equation f (x) = 0 to which bisection method converges. Then |xn − r| ≤ ϵ whenever n satisfies log(b0 − a0 ) − logϵ n≥ (3) log 2 Proof : By the error estimate of bisection method given by 2, we are sure that |xn − r| ≤ ϵ whenever n is such that 1 ( )n (b0 − a0 ) ≤ ϵ. 2 By taking logarithm on both sides of the last inequality, we get the desired estimate on n. Remark 6.2 The previous Corollary tells us that if we want an approximation xn to the root r of the given equation such that the absolute error is less than a pre-assigned positive quantity, then we have to perform n iterations, where n is the least integer that satisfies the inequality in 3. It is interesting to observe that to obtain this n, we don’t need to know the root r. Example 6.3 Let us find an approximate solution to the nonlinear equation sin x + x2 − 1 = 0 using bisection method so that the resultant absolute error is at most ϵ = 0.125. To apply Bisection method, we must choose an interval [a0 , b0 ] such that the function f (x) = sin x + x2 − 1 = 0 satisfies the hypothesis of bisection method. Note that f satisfies hypothesis of bisection on the interval [0, 1]. In order to achieve the required accuracy, we should first decide how many iterations are needed. The inequality 3, says that required accuracy is achieved provided n satisfies 8  log(b0 − a0 ) − logϵ n ≥ log 2 log(1) − log(0.125) ≥ log 2 = 3. Thus we have to compute x3. We will do it now. Iteration 1: We have a0 = 0, b0 = 1. Thus x1 = 0.5. Since, f (x1 ) = −0.27 < 0, f (0) < 0, and f (1) > 0, we take [a1 , b1 ] = [x1 , b0 ] = [0.5, 1]. Iteration 2: The mid-point is 0.5, 1 is x2 = 0.75 Since, f (x2 ) = 0.24 > 0, f (0.5) < 0, and f (1) > 0, we take [a2 , b2 ] = [a1 , b2 ] = [0.5, 0.75]. Iteration 3: The mid-point is 0.5, 0.75 is x3 = 0.625 Since, f (x3 ) = −0.024 < 0, f (0.5) < 0, and f (0.75) > 0, we take [a3 , b3 ] = [x3 , b2 ] = [0.625, 0.75]. As suggested by the formula 3 we stop the iteration here and take the approximate root of the given equation as the mid-point of the interval [a3 , b3 ], which is x4 ≈ 0.6875. Note that the true value is r ≈ 0.636733. The absolute error is 0.05 which is much less than the required accuracy of 0.125. 7 Rates of Convergence Let an be a sequence such that lim an = a. n→∞ We would like to measure the speed at which the convergence takes place. For example, consider 1 lim = 0. n→∞ 2n + 3 and 1 lim = 0. n2 n→∞ We feel that the first sequence goes to zero linearly and the second goes with a much superior speed because of the presence of n2 in its denominator. We will define the notion of order of convergence precisely. Definition 7.1 (Rate of Convergence or Order of Convergence) Let an be a sequence such that limn→∞ an = a. 1. We say that the rate of convergence is atleast linear if there exists a constant c < 1 and a natural number N such that |an+1 − a| ≤ c|an − a| for all n ≥ N. 9  2. We say that the rate of convergence is atleast superlinear if there exists a sequence ϵn that converges to zero, and a natural number N such that |an+1 − a| ≤ ϵn |an − a| for all n ≥ N. 3. We say that the rate of convergence is at least quadratic if there exists a constant C (not necessarily less than 1) and a natural number N such that |an+1 − a| ≤ C|an − a|2 for all n ≥ N. 4. Let α ∈ R+. We say that the rate of convergence is at least α if there exists a constant C (not necessarily less than 1) and a natural number N such that |an+1 − a| ≤ C|an − a|α for all n ≥ N. 8 Comments on Bisection method 1. Note that the mid-point of an interval [a, b] is precisely the x − coordinate of the point of intersection of the line joining the points (a, sgn((f (a))) and (b, sgn((f (b))) with the x-axis. 2. Let f , and the interval [a0 , b0 ] satisfy the hypothesis of bisection method. Even if the nonlinear equation f (x) = 0 has more than one solution in the interval [a, b], the bisection method chooses the root that it tries to approximate. In other words, once we fix the initial interval [a0, b0 ], the bisection method takes over and we cannot control it to find some specific root than what it chooses to find. 3. Given a function f , choosing an interval [a, b] such thatf (a)f (b) < 0 is crucial to bisection method. There is no general procedure to find such an interval. This is one of the main drawbacks of bisection method. 4. Bisection method cannot be used to find zero of functions for which graph touches x-axis but does not cross x-axis. 5. There is a misconception about bisection method’s order of convergence (see Definition 7.1, which is claimed to be 1. However there is no proof of |xn+1 − r| ≤ c|xn − r|. 10  If the sequence xn converges linearly to r, then we get |xn+1 − r| ≤ cn+1 |x0 − r|. In the case of bisection method, we have this inequality with c = 1/2, which is only a necessary condition for the convergence to be linear but not a sufficient condition. Example 8.1 The function f (x) = x3 − x2 − 1 has exactly one zero in [1, 2]. Use the Bisection Algorithm to approximate the zero of f to within 10−4. 11 9 Examples with Scilab // The equation $8* x^3-12*x^2-2*x+3==0$ has three real roots. // the graph of this function can be observed here. xset ( ’ window ’ ,0) ; x = -1:.01:2.5; //defining the range of x. deff(’[y]=f(x)’,’y=8* x^3-12*x^2-2*x+3’); //defining the function y=feavl(x,f); a=gca(); a.y_location="origin" a.x_location="origin" plot(x,y) //instruction to plot the graph title (’y=8* x^3-12*x^2-2*x+3’) \\from the above plot we can infer that the function has roots between the intervals (-1 ,0 ) , (0 , 1 ), ( 1 , 2 ). 10 MathLab codes function root = bisection_method(f, a, b, tol, max_iter) %’root’ is the name of the function if f(a)*f(b) > 0 error(’Function has same signs at interval endpoints. Bisection method cannot guarantee conve end iter = 0; while (b - a)/2 > tol c = (a + b)/2; if f(c) == 0 break; elseif f(a)*f(c) < 0 b = c; else a = c; end iter = iter + 1; if iter >= max_iter 12 disp(’Maximum iterations reached.’); break; end end root = (a + b)/2; end %CORRECT FORMAT OF FINDING THE ROOTS OF FUNCTION, follow below! %SOME EXAMPLES % root=bisection_method(@(x) x^3 - x^2 - 1, 1, 2, 1e-6, 1000); %Answer=1.4656 %root=bisection_method(@(x) x^3 + 2*x^2 -3*x- 1, 1, 2, 1e-6, 1000); %Answer=1.1987 %root=bisection_method(@(x) x^3 + 4*x^2 - 10, 1, 2, 1e-6, 1000); %root=1.365230013 after 13 iterations 11 Exercise 1. Do three iterations (by hand) of the bisection method applied to f (x) = x3 −2, using a = 0 and b = 2. 2. For each of the functions listed below, do a calculation by hand (i.e., with a calculator) to find the root to an accuracy of 0.1. This process will take at most five iterations for all of these, and fewer for several of them. 2 a. f (x) = x − e−x , [a, b] = [0, 1]; 1 b. f (x) = lnx + x, [a, b] = [ 10 , 1]; c. f (x) = x3 − 3, [a, b] = [1, 2]; 3. Determine the real roots of f (x) = −0.5x2 + 2.5x + 4.5 : Graphically. Using the quadratic formula. Using three iterations of the bisection method to determine the highest root. Employ initial guesses of xl = 5 and xu = 10. Compute the estimated error ϵa and the true error ϵt after each iteration. 4. Determine the real root of f (x) = 5x3 − 5x2 + 6x − 2 : Graphically. 13  Using bisection to locate the root. Employ initial guesses of xl = 0 and xu = 1 and iterate until the estimated error ϵa falls below a level of ϵs = 10%. References Baskar,S. and S. Sivaji Ganesh. Introduction to Numerical Analysis.Department of Mathematics, Indian Institute of Technology, Mumbai.India Epperson, J.F.2013. An Introduction to Numerical Methods and Analyses, 2nd Edition. Wiley https : //web.stanf ord.edu/class/math114/lecture notes/bisection method notes.pdf 14