Report

Dr. Marco A. Arocha Aug, 2014 1 “Roots” problems occur when some function f can be written in terms of one or more dependent variables x, where the solutions to f(x)=0 yields the solution to the problem. Examples: These problems often occur when a design problem presents an implicit equation (as oppose to an explicit equation) for a required parameter. 2 Finding the roots of these equations is equivalent to finding the values of x for which f(x) and g(x) are “zero” For this reason the procedure of solving equations (3) and (4) is frequently referred to as finding the “zeros” of the equations. 3 Methods that exploit the fact that a function typically changes sign in the vicinity of a root are called bracketing methods. Two initial guesses for the root are required. Guesses must “bracket” or be on either side of the root. The particular methods employ different strategies to systematically reduce the width of the bracket and, hence, home in on the correct answer. 4 A simple method for obtaining the estimate of the root of the equation f(x)=0 is to make a plot of the function as f(x) vs x and observe where it crosses the x-axis. Graphing the function can also indicate where roots may be and where some root-finding methods may fail: a) b) c) d) who is doing this one? Same sign, no roots Different sign, one root Same sign, two roots Different sign, three roots 5 Some difficult cases: Multiple roots that occurs when the function is tangential to the x axis. For this case, although the end points are of opposite signs, there are an even number of axis intersections for the interval. Discontinuous function where end points of opposite sign bracket an even number of roots. Special strategies are required for determining the roots for these cases. 6 Graphical techniques alone are of limited practical value because they are not precise. However, graphical methods can be utilized to obtain rough estimates of roots. These estimates can be employed as starting guesses for numerical methods. Graphical interpretations are important tools for understanding the properties of the functions and anticipating the pitfalls of the numerical methods. 7 The bisection method is a search method in which the interval is progresively divided in half. If a function changes sign over an interval, the function value at the midpoint is evaluated. The location of the root is then determined as lying within the subinterval where the sign change occurs. The absolute error is reduced by a factor of 2 for each iteration. 8 9 A simple termination criteria can be used: (1) An approximate error εa can be calculated: = − where is the root lower bound and is the root upper bound from the present iteration. The absolute value is used because we are usually concerned with the magnitude of εa rather than with its sign. 10 Another forms of termination criteria can be used: (2) An approximate percent relative error εa can be calculated: = − 100% where is the root for the present iteration and is the root from the previous iteration. The absolute value is used because we are usually concerned with the magnitude of εa rather than with its sign. 11 INPUT xl, xu, es, imax xr = (xl + xu) / 2 iter = 0 DO xrold = xr xr = (xl + xu) / 2 iter = iter + 1 IF xr ≠ 0 THEN % to avoid division by zero ea = ABS((xr - xrold) / xr) * 100 END IF test = f(xl) * f(xr) IF test < 0 THEN xu = xr ELSE IF test > 0 THEN xl = xr ELSE ea = 0 END IF IF ea < es OR iter ≥ imax EXIT END DO BisectResult = xr END PROGRAM 12 An alternative method to bisection, sometimes faster. Exploits a graphical perception, join f(xl) and f(xu) by a straight line. The intersection of this line with the x axis represents an improved estimate of the root. The fact that the replacement of the curve by a straight line gives a “false position” of the root is the origin of the name, method of false position, or in Latin, regula falsi. It is also called the linear interpolation method. 13 Can derive the method’s formula by using similar triangles. The intersection of the straight line with the x axis can be estimated as which can be solved for xr 14 The value of xr so computed then replaces whichever of the two initial guesses, xl or xu, yields a function value with the same sign as f(xr). By this way, the values of xl and xu always bracket the true root. The process is repeated until the root is estimated. The algorithm is identical to the one for bisection with the exception that the above eq. is used for step 2 (slide 9). The same stopping criteria are used to terminate the computation (slides 10 and 11). 15 for some cases false-position method may show slow convergence 16