C++ for Engineers and Scientists Fourth Edition：工程師與科學家用C++第四版

1、Chapter 14:Numerical MethodsIn this chapter, you will learn about:Root findingThe bisection methodRefinements to the bisection methodThe secant methodNumerical integrationThe trapezoidal ruleSimpsons ruleCommon programming errorsObjectives2C+ for Engineers and Scientists, Fourth EditionRoot finding

2、is useful in solving engineering problemsVital elements in numerical analysis are: Appreciating what can or cant be solved Clearly understanding the accuracy of answers foundIntroduction to Root Finding3C+ for Engineers and Scientists, Fourth EditionExamples of the types of functions encountered in

3、root-solving problems:Introduction to Root Finding (continued)4C+ for Engineers and Scientists, Fourth EditionGeneral quadratic equation, Equation 14.1, can be solved easily and exactly by using the following equation:Introduction to Root Finding (continued)5C+ for Engineers and Scientists, Fourth E

4、ditionEquation 14.2 can be solved for x exactly by factoring the polynomialEquations 14.4 and 14.5 are transcendental equationsTranscendental equationsRepresent a different class of functionsTypically involve trigonometric, exponential, or logarithmic functionsCannot be reduced to any polynomial equ

5、ation in xIntroduction to Root Finding (continued)6C+ for Engineers and Scientists, Fourth EditionIrrational numbers and transcendental numbersRepresented by nonrepeating decimal fractions Cannot be expressed as simple fractionsResponsible for the real number system being dense or continuousClassify

6、ing equations as polynomials or transcendental and the roots of these equations as rational or irrational is vital to traditional mathematicsLess important to the computer where number system is continuous and finiteIntroduction to Root Finding (continued)7C+ for Engineers and Scientists, Fourth Edi

7、tionWhen finding roots of equations, the distinction between polynomials and transcendental equations is unnecessaryMany theorems learned for roots and polynomials dont apply to transcendental equationsBoth Equations 14.4 and 14.5 have infinite number of real roots Introduction to Root Finding (cont

8、inued)8C+ for Engineers and Scientists, Fourth EditionPotential computational difficulties can be avoided by providing:Best possible choice of methodInitial guess based on knowledge of the problemThis is often the most difficult and time consuming part of solutionArt of numerical analysis consists o

9、f balancing time spent optimizing the problems solution before computation against time spent correcting unforeseen errors during computationIntroduction to Root Finding (continued)9C+ for Engineers and Scientists, Fourth EditionSketch function before attempting root solvingUse graphing routines orG

10、enerate table of function values and graph by handGraphs are useful to programmers in: Estimating first guess for root Anticipating potential difficultiesIntroduction to Root Finding (continued)10C+ for Engineers and Scientists, Fourth EditionIntroduction to Root Finding (continued)11C+ for Engineer

11、s and Scientists, Fourth Edition Graph of e-x and sin(x) for locating the intersection pointsBecause the sine oscillates, there is an infinite number of positive rootsEstablish a procedure based on most obvious method of attackBegin at some value of x just before the rootStep along x-axis carefully

12、watching magnitude and sign of function Introduction to Root Finding (continued)12C+ for Engineers and Scientists, Fourth EditionIndicates root between these two x valuesIntroduction to Root Finding (continued)13C+ for Engineers and Scientists, Fourth EditionFor next approximation use midpoint value

13、, xNext approximation is midpoint, 0.425 Introduction to Root Finding (continued)14C+ for Engineers and Scientists, Fourth EditionIn this way, proceed systematically to a computation of the root to any degree of accuracyKey element in this procedure is monitoring the sign of functionWhen sign change

14、s, specific action is taken to refine estimate of rootIntroduction to Root Finding (continued)15C+ for Engineers and Scientists, Fourth EditionRoot-solving procedure previously explained is suitable for hand calculationsA slight modification makes it more systematic and easier to adapt to computer c

15、odingModified computational technique is known as the bisection methodSuppose you already know theres a root between x = a and x = bFunction changes sign in this intervalAssume Only one root between x = a and x = bFunction is continuous in this interval The Bisection Method16C+ for Engineers and Sci

16、entists, Fourth EditionThe Bisection Method (continued)17C+ for Engineers and Scientists, Fourth Edition A sketch of a function with one root between a and bAfter determining a second time whether the left or right half contains the root, interval is again replaced by the left or right half-interval

17、Continue process until narrow in on the root at previously assigned accuracyEach step halves intervalAfter n intervals, intervals size containing root is (b a)/2nThe Bisection Method (continued)18C+ for Engineers and Scientists, Fourth EditionIf required to find root to within the tolerance, the num

18、ber of iterations can be determined by:The Bisection Method (continued)19C+ for Engineers and Scientists, Fourth EditionProgram 14.1 computes roots of equationsNote the following features:In each iteration after the first one, there is only one function evaluationProgram contains several checks for

19、potential problems along with diagnostic messages along with diagnostic messagesCriterion for success is based on intervals sizeThe Bisection Method (continued)20C+ for Engineers and Scientists, Fourth EditionBisection method presents the basics on which most root-finding methods are constructedBrut

20、e force is rarely usedAll refinements of bisection method attempt to use as much information as available about the functions behavior in each iterationIn the ordinary bisection method, the only feature of the function that is monitored is its signRefinements to the Bisection Method21C+ for Engineer

21、s and Scientists, Fourth EditionEssentially same as bisection method, except it uses interpolated value for rootRoot is known to exist in interval ( x1 x2 )In drawing, f1 is negative and f3 is positiveInterpolated position of root is x2Length of sides is related, yielding: Value of x2 replaces the m

22、idpoint in bisectionRegula Falsi Method22C+ for Engineers and Scientists, Fourth Edition23C+ for Engineers and Scientists, Fourth Edition Estimating the root by interpolationRegula Falsi Method (continued)24C+ for Engineers and Scientists, Fourth Edition Illustration of several iterations of the reg

23、ula falsi methodRegula Falsi Method (continued)Perhaps the procedure can be made to collapse from both directions from both directionsThe idea is as follows: Modified Regula Falsi Method25C+ for Engineers and Scientists, Fourth Edition26C+ for Engineers and Scientists, Fourth Edition Illustration of

24、 the modified regula falsi methodModified Regula Falsi Method (continued)Using this algorithm, slope of line is reduced artificiallyIf root is in left of original interval, it: Eventually turns up in the right segment of a later intervalSubsequently alternates between left and right Modified Regula

25、Falsi Method (continued)27C+ for Engineers and Scientists, Fourth EditionModified Regula Falsi Method (continued)28C+ 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 iterat

26、ion before inserting them into the nextTrial and error shows that a less drastic increase in the slope results in improved convergenceUsing a convergence factor of 0.9 should be adequate for most problems Modified Regula Falsi Method (continued)29C+ for Engineers and Scientists, Fourth EditionBisect

27、ionSuccess based on size of intervalSlow convergencePredictable number of iterationsInterval halved in each iterationGuaranteed to bracket a root Summary of the Bisection Methods30C+ for Engineers and Scientists, Fourth EditionRegula falsiSuccess based on size of functionFaster convergenceUnpredicta

28、ble number of iterationsInterval containing the root is not smallSummary of the Bisection Methods (continued)31C+ for Engineers and Scientists, Fourth EditionModified regula falsiSuccess based on size of intervalFaster convergenceUnpredictable number of iterationsOf three methods, most efficient for

29、 common problemsSummary of the Bisection Methods (continued)32C+ for Engineers and Scientists, Fourth EditionIdentical to regula falsi method except sign of f(x) doesnt need to be checked at each iteration The Secant Method33C+ for Engineers and Scientists, Fourth EditionIntegration of a function of

30、 a single variable can be thought of as opposite to differentiation, or as the area under the curveIntegral 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 intervalIntegral designated as:Introduction to Numerical Integratio

31、n34C+ for Engineers and Scientists, Fourth Edition35C+ for Engineers and Scientists, Fourth Edition An integral as an area under a curveIntroduction to Numerical Integration (continued)Numerical integration is a stable processConsists of expressing the area as the sum of areas of smaller segmentsFai

32、rly safe from division by zero or round-off errors caused by subtracting numbers of approximately the same magnitudeMany integrals in engineering or science cannot be expressed in any closed form Introduction to Numerical Integration (continued)36C+ for Engineers and Scientists, Fourth EditionTrapez

33、oidal rule approximation for integralReplace function over limited range by straight line segmentsInterval x=a to x=b is divided into subintervals of size xFunction replaced by line segments over each subintervalArea under function is then approximated by area under line segments Introduction to Num

34、erical Integration (continued)37C+ for Engineers and Scientists, Fourth EditionApproximation of area under complicated curve is obtained by assuming function can be replaced by simpler function over a limited rangeA straight line, the simplest approximation to a function, lead to trapezoidal ruleTra

35、pezoidal rule for one panel, identified as T0The Trapezoidal Rule38C+ for Engineers and Scientists, Fourth Edition39C+ for Engineers and Scientists, Fourth Edition Approximating the area under a curve by a single trapezoidThe Trapezoidal Rule (continued)Improve accuracy of approximation under curve

36、by dividing interval in halfFunction is approximated by straight-line segments over each halfArea in example is approximated by area of two trapezoidsThe Trapezoidal Rule (continued)40C+ for Engineers and Scientists, Fourth Edition41C+ for Engineers and Scientists, Fourth Edition Two-panel approxima

37、tion to the areaThe Trapezoidal Rule (continued)Two-panel approximation T1 can be related to one-panel results, T0, as: Result for n panels is:The Trapezoidal Rule (continued)42C+ for Engineers and Scientists, Fourth EditionThe result for n panels was derived assuming that the widths of all panels i

38、s the same and equal to xnEquation can be generalized to a partition of the interval into unequal panelsBy restricting panel widths to be equal and number of panels to be a power of 2, This results in:Computational Form of the Trapezoidal Rule43C+ for Engineers and Scientists, Fourth Edition44C+ for

39、 Engineers and Scientists, Fourth Edition Four-panel trapezoidal approximation, T2Computational Form of the Trapezoidal Rule (continued)Computational Form of the Trapezoidal Rule (continued)45C+ for Engineers and Scientists, Fourth EditionProcedure using Equation 14.11 to approximate an integral by

40、the trapezoidal rule is:Compute T0Repeatedly apply Equation 14.11 for: k = 1, 2, . . . until sufficient accuracy is obtainedComputational Form of the Trapezoidal Rule (continued)46C+ for Engineers and Scientists, Fourth EditionGiven the following integral:Trapezoidal rule approximation to the integr

41、al with a = 1 and b = 2 begins with Equation 14.6 to obtain T0Example of a Trapezoidal Rule Calculation47C+ for Engineers and Scientists, Fourth EditionRepeated use of Equation 14.11 then yields:Example of a Trapezoidal Rule Calculation (continued)48C+ for Engineers and Scientists, Fourth EditionCon

42、tinuing the calculation through k = 5 yields:Example of a Trapezoidal Rule Calculation (continued)49C+ for Engineers and Scientists, Fourth EditionTrapezoidal rule is based on approximating the function by straight-line segmentsTo improve the accuracy and convergence rate, another approach is approx

43、imating the function by parabolic segmentsThis is known as Simpsons ruleSpecifying a parabola uniquely requires three points, so the lowest order Simpsons rule has two panelsSimpsons Rule50C+ for Engineers and Scientists, Fourth Edition51C+ for Engineers and Scientists, Fourth Edition Area under a p

44、arabola drawn through three pointsSimpsons Rule (continued)Simpsons Rule (continued)52C+ for Engineers and Scientists, Fourth Edition53C+ for Engineers and Scientists, Fourth Edition The second-order Simpsons rule approximation is the area under two parabolasSimpsons Rule (continued)Generalization o

45、f Equation 14.12 for n = 2k panels Simpsons Rule (continued)54C+ for Engineers and Scientists, Fourth EditionConsider this integral:Using Equation 14.13 first for k = 1 yields:Example of Simpsons Rule as an Approximation to an Integral55C+ for Engineers and Scientists, Fourth EditionRepeating for k

46、= 2 yields:Example of Simpsons Rule as an Approximation to an Integral (continued)56C+ for Engineers and Scientists, Fourth EditionContinuing the calculation yields:Example of Simpsons Rule as an Approximation to an Integral (continued)57C+ for Engineers and Scientists, Fourth Edition Trapezoidal an

47、d Simpsons rule results for integral Two characteristics of this type of computation:Round-off errors occur when the values of f(x1) and f(x3) are nearly equalPrediction of exact number of iterations is not availableExcessive and possibly infinite iterations must be preventedExcessive computation ti

48、me might be a problemOccurs if number of iterations exceeds fiftyCommon Programming Errors58C+ for Engineers and Scientists, Fourth EditionAll root solving methods described in chapter are iterativeCan be categorized into two classesStarting from an interval containing a rootStarting from an initial

49、 estimate of a rootBisection algorithms refine initial interval by:Repeated evaluation of function at points within intervalMonitoring the sign of the function and determining in which subinterval the root lies Summary59C+ for Engineers and Scientists, Fourth EditionRegula falsi uses same conditions

50、 as bisection methodStraight line connecting points at the ends of the intervals is used to interpolate position of rootIntersection of this line with x-axis determines value of x2 used in next stepModified regula falsi same as regula falsi except:In each iteration, when full interval replaced by sub