资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,C+ for Engineers and Scientists, Fourth Edition,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,C+ for Engineers and Scientists, Fourth Edition,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,C+ for Engineers and Scientists, Fourth Edition,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,C+ for Engineers and Scientists, Fourth Edition,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,C+ for Engineers and Scientists, Fourth Edition,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,C+ for Engineers and Scientists, Fourth Edition,*,Chapter 14:Numerical Methods,In this chapter, you will learn about:,Root finding,The bisection method,Refinements to the bisection method,The secant method,Numerical integration,The trapezoidal rule,Simpsons rule,Common programming errors,Objectives,2,C+ for Engineers and Scientists, Fourth Edition,Root finding is useful in solving engineering problems,Vital elements in numerical analysis are:,Appreciating what can or cant be solved,Clearly understanding the accuracy of answers found,Introduction to Root Finding,3,C+ for Engineers and Scientists, Fourth Edition,Examples of the types of functions encountered in root-solving problems:,Introduction to Root Finding (continued),4,C+ for Engineers and Scientists, Fourth Edition,General quadratic equation, Equation 14.1, can be solved easily and exactly by using the following equation:,Introduction to Root Finding (continued),5,C+ for Engineers and Scientists, Fourth Edition,Equation 14.2 can be solved for,x,exactly by factoring the polynomial,Equations 14.4 and 14.5 are,transcendental equations,Transcendental equations,Represent a different class of functions,Typically involve trigonometric, exponential, or logarithmic functions,Cannot be reduced to any polynomial equation in,x,Introduction to Root Finding (continued),6,C+ for Engineers and Scientists, Fourth Edition,Irrational numbers and transcendental numbers,Represented by nonrepeating decimal fractions,Cannot be expressed as simple fractions,Responsible for the real number system being dense or continuous,Classifying equations as polynomials or transcendental and the roots of these equations as rational or irrational is vital to traditional mathematics,Less important to the computer where number system is continuous and finite,Introduction to Root Finding (continued),7,C+ for Engineers and Scientists, Fourth Edition,When finding roots of equations, the distinction between polynomials and transcendental equations is unnecessary,Many theorems learned for roots and polynomials dont apply to transcendental equations,Both Equations 14.4 and 14.5 have infinite number of real roots,Introduction to Root Finding (continued),8,C+ for Engineers and Scientists, Fourth Edition,Potential computational difficulties can be avoided by providing:,Best possible choice of method,Initial guess based on knowledge of the problem,This is often the most difficult and time consuming part of solution,Art of numerical analysis consists of balancing time spent optimizing the problems solution before computation against time spent correcting unforeseen errors during computation,Introduction to Root Finding (continued),9,C+ for Engineers and Scientists, Fourth Edition,Sketch function before attempting root solving,Use graphing routines,or,Generate table of function values and graph by hand,Graphs are useful to programmers in:,Estimating first guess for root,Anticipating potential difficulties,Introduction to Root Finding (continued),10,C+ for Engineers and Scientists, Fourth Edition,Introduction to Root Finding (continued),11,C+ for Engineers and Scientists, Fourth Edition,Graph of,e,-x,and sin(,x,) for locating the intersection points,Because the sine oscillates, there is an infinite number of positive roots,Establish a procedure based on most obvious method of attack,Begin at some value of,x,just before the root,Step along,x,-axis carefully watching magnitude and sign of function,Introduction to Root Finding (continued),12,C+ for Engineers and Scientists, Fourth Edition,Indicates root between these two,x,values,Introduction to Root Finding (continued),13,C+ for Engineers and Scientists, Fourth Edition,For next approximation use midpoint value,x,Next approximation is midpoint, 0.425,Introduction to Root Finding (continued),14,C+ for Engineers and Scientists, Fourth Edition,In this way, proceed systematically to a computation of the root to any degree of accuracy,Key element in this procedure is monitoring the sign of function,When sign changes, specific action is taken to refine estimate of root,Introduction to Root Finding (continued),15,C+ for Engineers and Scientists, Fourth Edition,Root-solving procedure previously explained is suitable for hand calculations,A slight modification makes it more systematic and easier to adapt to computer coding,Modified computational technique is known as the,bisection method,Suppose you already know theres a root between,x = a,and,x = b,Function changes sign in this interval,Assume,Only one root between,x = a,and,x = b,Function is continuous in this interval,The Bisection Method,16,C+ for Engineers and Scientists, Fourth Edition,The Bisection Method (continued),17,C+ for Engineers and Scientists, Fourth Edition,A sketch of a function with one root between,a,and,b,After determining a second time whether the left or right half contains the root, interval is again replaced by the left or right half-interval,Continue process until narrow in on the root at previously assigned accuracy,Each step halves interval,After,n,intervals, intervals size containing root is,(,b a)/2n,The Bisection Method (continued),18,C+ for Engineers and Scientists, Fourth Edition,If required to find root to within the tolerance, the number of iterations can be determined by:,The Bisection Method (continued),19,C+ for Engineers and Scientists, Fourth Edition,Program 14.1 computes roots of equations,Note the following features:,In each iteration after the first one, there is only one function evaluation,Program contains several checks for potential problems along with diagnostic messages along with diagnostic messages,Criterion for success is based on intervals size,The Bisection Method (continued),20,C+ for Engineers and Scientists, Fourth Edition,Bisection method presents the basics on which most root-finding methods are constructed,Brute force is rarely used,All refinements of bisection method attempt to use as much information as available about the functions behavior in each iteration,In the ordinary bisection method, the only feature of the function that is monitored is its sign,Refinements to the Bisection Method,21,C+ for Engineers and Scientists, Fourth Edition,Essentially same as bisection method, except it uses interpolated value for root,Root is known to exist in interval (,x,1, x,2,),In drawing,f,1,is negative and,f,3,is positive,Interpolated position of root is,x,2,Length of sides is related, yielding:,Value of,x,2,replaces the midpoint in bisection,Regula Falsi Method,22,C+ for Engineers and Scientists, Fourth Edition,23,C+ for Engineers and Scientists, Fourth Edition,Estimating the root by interpolation,Regula Falsi Method (continued),24,C+ for Engineers and Scientists, Fourth Edition,Illustration of several iterations of the regula falsi method,Regula Falsi Method (continued),Perhaps the procedure can be made to collapse from both directions from both directions,The idea is as follows:,Modified Regula Falsi Method,25,C+ for Engineers and Scientists, Fourth Edition,26,C+ for Engineers and Scientists, Fourth Edition,Illustration of the modified regula falsi method,Modified Regula Falsi Method (continued),Using this algorithm, slope of line is reduced,artificially,If root is in left of original interval, it:,Eventually turns up in the right segment of a later interval,Subsequently alternates between left and right,Modified Regula Falsi Method (continued),27,C+ for Engineers and Scientists, Fourth Edition,Modified Regula Falsi Method (continued),28,C+ for Engineers and Scientists, Fourth Edition,Comparison of Root-Finding Methods Using the Function,f,(,x,)=2e,-2x,-sin(,x,),Relaxation factor:,Number used to alter the results of one iteration before inserting them into the next,Trial and error shows that a less drastic increase in the slope results in improved convergence,Using a convergence factor of 0.9 should be adequate for most problems,Modified Regula Falsi Method (continued),29,C+ for Engineers and Scientists, Fourth Edition,Bisection,Success based on size of interval,Slow convergence,Predictable number of iterations,Interval halved in each iteration,Guaranteed to bracket a root,Summary of the Bisection Methods,30,C+ for Engineers and Scientists, Fourth Edition,Regula falsi,Success based on size of function,Faster convergence,Unpredictable number of iterations,Interval containing the root is not small,Summary of the Bisection Methods (continued),31,C+ for Engineers and Scientists, Fourth Edition,Modified regula falsi,Success based on size of interval,Faster convergence,Unpredictable number of iterations,Of three methods, most efficient for common problems,Summary of the Bisection Methods (continued),32,C+ for Engineers and Scientists, Fourth Edition,Identical to regula falsi method except sign of,f(x),doesnt need to be checked at each iteration,The Secant Method,33,C+ for Engineers and Scientists, Fourth Edition,Integration of a function of a single variable can be thought of as opposite to differentiation, or as the area under the curve,Integral of function,f(x),from,x=a,to,x=b,will be evaluated by devising schemes to measure area under the graph of function over this interval,Integral designated as:,Introduction to Numerical Integration,34,C+ for Engineers and Scientists, Fourth Edition,35,C+ for Engineers and Scientists, Fourth Edition,An integral as an area under a curve,Introduction to Numerical Integration (continued),Numerical integration is a stable process,Consists of expressing the area as the sum of areas of smaller segments,Fairly safe from division by zero or round-off errors caused by subtracting numbers of approximately the same magnitude,Many integrals in engineering or science cannot be expressed in any closed form,Introduction to Numerical Integration (continued),36,C+ for Engineers and Scientists, Fourth Edition,Trapezoidal rule approximation for integral,Replace function over limited range by straight line segments,Interval,x=a,to,x=b,is divided into subintervals of size ,x,Function replaced by line segments over each subinterval,Area under function is then approximated by area under line segments,Introduction to Numerical Integration (continued),37,C+ for Engineers and Scientists, Fourth Edition,Approximation of area under complicated curve is obtained by assuming function can be replaced by simpler function over a limited range,A straight line, the simplest approximation to a function, lead to trapezoidal rule,Trapezoidal rule for one panel, identified as,T,0,The Trapezoidal Rule,38,C+ for Engineers and Scientists, Fourth Edition,39,C+ for Engineers and Scientists, Fourth Edition,Approximating the area under a curve by a single trapezoid,The Trapezoidal Rule (continued),Improve accuracy of approximation under curve by dividing interval in half,Function is approximated by straight-line segments over each half,Area in example is approximated by area of two trapezoids,The Trapezoidal Rule (continued),40,C+ for Engineers and Scientists, Fourth Edition,41,C+ for Engineers and Scientists, Fourth Edition,Two-panel approximation to the area,The Trapezoidal Rule (continued),Two-panel approximation,T,1,can be related to one-panel results,T,0, as:,Result for,n,panels is:,The Trapezoidal Rule (continued),42,C+ for Engineers and Scientists, Fourth Edition,The result for,n,panels was derived assuming that the widths of all panels is the same and equal to ,x,n,Equation can be generalized to a partition of the interval into unequal panels,By restricting panel widths to be equal and number of panels to be a power of 2,This results in:,Computational Form of the Trapezoidal Rule,43,C+ for Engineers and Scientists, Fourth Edition,44,C+ for Engineers and Scientists, Fourth Edition,Four-panel trapezoidal approximation,T,2,Computational Form of the Trapezoidal Rule (continued),Computational Form of the Trapezoidal Rule (continued),45,C+ for Engineers and Scientists, Fourth Edition,Procedure using Equation 14.11 to approximate an integral by the trapezoidal rule is:,Compute,T,0,Repeatedly apply Equation 14.11 for:,k,= 1, 2, . . .,until sufficient accuracy is obtained,Computational Form of the Trapezoidal Rule (continued),46,C+ for Engineers and Scientists, Fourth Edition,Given the following integral:,Trapezoidal rule approximation to the integral with,a,= 1,and,b,= 2,begins with Equation 14.6 to obtain,T,0,Example of a Trapezoidal Rule Calculation,47,C+ for Engineers and Scientists, Fourth Edition,Repeated use of Equation 14.11 then yields:,Example of a Trapezoidal Rule Calculation (continued),48,C+ for Engineers and Scientists, Fourth Edition,Continuing the calculation through,k,= 5,yields:,Example of a Trapezoidal Rule Calculation (continued),49,C+ for Engineers and Scientists, Fourth Edition,Trapezoidal rule is based on approximating the function by straight-line segments,To improve the accuracy and convergence rate, another approach is approximating the function by parabolic segments,This is known as Simpsons rule,Specifying a parabola uniquely requires three points, so the lowest order Simpsons rule has two panels,Simpsons Rule,50,C+ for Engineers and Scientists, Fourth Edition,51,C+ for Engineers and Scientists, Fourth Edition,Area under a parabola drawn through three points,Simpsons Rule (continued),Simpsons Rule (continued),52,C+ for Engineers and Scientists, Fourth Edition,53,C+ for Engineers and Scientists, Fourth Edition,The second-order Simpsons rule approximation is the area under two parabolas,Simpsons Rule (continued),Generalization of Equation 14.12 for,n,= 2,k,panels,Simpsons Rule (continued),54,C+ for Engineers and Scientists, Fourth Edition,Consider this integral:,Using Equation 14.13 first for k = 1 yields:,Example of Simpsons Rule as an Approximation to an Integral,55,C+ for Engineers and Scientists, Fourth Edition,Repeating for k = 2 yields:,Example of Simpsons Rule as an Approximation to an Integral (continued),56,C+ for Engineers and Scientists, Fourth Edition,Continuing the calculation yields:,Example of Simpsons Rule as an Approximation to an Integral (continued),57,C+ for Engineers and Scientists, Fourth Edition,Trapezoidal and Simpsons rule results for integral,Two characteristics of this type of computation:,Round-off errors occur when the values of,f,(,x,1,) and,f,(,x,3,) are nearly equal,Prediction of exact number of iterations is not available,Excessive and possibly infinite iterations must be prevented,Excessive computation time might be a problem,Occurs if number of iterations exceeds fifty,Common Programming Errors,58,C+ for Engineers and Scientists, Fourth Edition,All root solving methods described in chapter are iterative,Can be categorized into two classes,Starting from an interval containing a root,Starting from an initial estimate of a root,Bisection algorithms refine initial interval by:,Repeated evaluation of function at points within interval,Monitoring the sign of the function and determining in which subinterval the root lies,Summary,59,C+ for Engineers and Scientists, Fourth Edition,Regula falsi uses same conditions as bisection method,Straight line connecting points at the ends of the intervals is used to interpolate position of root,Intersection of this line with x-axis determines value of,x,2,used in next step,Modified regula falsi same as regula falsi except:,In each iteration, when full interval replaced by subinterval containing root, relaxation factor used to modify functions value at the fixed end of the subinterval,Summary (continued),60,C+ for Engineers and Scientists, Fourth Edition,Secant method replaces the function by:,Secant line through two points,Finds point of intersection of the line with,x,-axis,Algorithm requires two input numbers:,x,0,and ,x,0,Pair of values then replaced by pair (,x,1,and ,x,1,) where,x,1,=,x,0,+,x,0,and,Summary (continued),61,C+ for Engineers and Scientists, Fourth Edition,Secant method processing continues until ,x,is sufficiently small,Success of a program in finding the root of function usually depends on the quality of information supplied by the user,Accuracy of initial guess or search interval,Method selection match to circumstances of problem,Execution-time problems are usually traceable to:,Errors in coding,Inadequate user-supplied diagnostics,Chapter Summary (continued),62,C+ for Engineers and Scientists, Fourth Edition,Trapezoidal rule results from replacing the function,f,(,x,) by straight-line segments over the panels ,x,i,Approximate value for integral is given by following formula,Summary (continued),63,C+ for Engineers and Scientists, Fourth Edition,If panels are equal size and the number of panels is,n,= 2,k,where,k,is a positive integer, the trapezoidal rule approximation is then labeled,T,k,and satisfies the equation,where,Summary (continued),64,C+ for Engineers and Scientists, Fourth Edition,In next level of approximation,Function,f,(,x,) is replaced by,n,/2 parabolic segments over pairs of equal size panels, ,x,= (,b,-,a,)/,n,Results in formula for the area known as Simpsons rule:,Summary (continued),65,C+ for Engineers and Scientists, Fourth Edition,
展开阅读全文