Numerical Analysis: Trapezoidal and Simpson's Rule

1 NumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , PhDNumerical analysis : Trapezoidal andSimpson s RuleNatasha S. Sharma, PhDNumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , PhDMathematical question we are interested innumerically answeringHow to we evaluateI= baf(x)dx?Calculus tells us that if F(x) is the antiderivative of afunctionf(x) on the interval [a,b], thenI= baf(x)dx=F(x)|ba=F(b) F(a).Practically, most integrals cannot be evaluated using thisapproach. For example, 10dx1 +x5has a complicated antiderivative and it easier to adopt anumerical method to approximate this :Trapezoidaland Simpson sRuleNatasha , PhDNumerical Integration: A General FrameworkIf you cannot solve a problem, then replace it with a near-by problem that you can solve!

2 Our problem:EvaluateI= baf(x) do so, many of the Numerical schemes are based onreplacingf(x) with some approximate function f(x) so thatI ba f(x)dx= : f(x) could be an easy to integrate functionapproximatingf(x).NumericalAnaly sis:Trapezoidaland Simpson sRuleNatasha , PhDNumerical Integration: A General FrameworkThen, the approximation error in this case isE=I I= ba(f(x) f(x))dx (b a) maxa x b|f(x) f(x)|The inequality above tells us that the approximation errorEdepends on:1the maximum error in the approximatingf(x) that ismaxa x b|f(x) f(x)|, and2(b a), the width of the Goal: How to choose f(x)?NumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , PhDPolynomial Approximations tof(x)Goal Choose an approximation f(x) tof(x) that is easilyintegrable and a good approximation tof(x).

3 Two natural candidates:1 Taylor polynomials approximatingf(x).One caveat: We needf(x) to have derivatives at a toexist of a higher order to improve the approximation!2 Interpolating polynomials approximatingf(x).NumericalAnalysis:Trap ezoidaland Simpson sRuleNatasha , PhDExampleExampleConsider evaluatingI= 10ex2dxUse the Taylor expansion to approximatef(x) = is,f(x) = 1 +t+t22!+ +tnn!+tn+1(n+ 1)!ec remainder termRn(x),t=x2,wherecis an unknown number between 0 andt= :Trapezoidaland Simpson sRuleNatasha , PhDSolutionSolution:I= 10(1 +x2+x42!+ +x2nn!)dx+ 10x2(n+1)(n+ 1)! 3, we haveI= 1 +13+110+142+E= +E,whereE= 10x2(n+1)(n+1)!ecdxand we need a bound on this remainder <E e24 10x8dx=e216= :Trapezoidaland Simpson sRuleNatasha , PhDUsing Interpolating PolynomialsIn spite of the simplicity of the above example, it is generallymore difficult to do Numerical integration by constructingTaylor polynomial approximations than by constructingpolynomial , we construct the function f(x) as the polynomialinterpolatingf(x) such that baf(x)dx ba f(x) I: Use linear interpolating polynomialp1(x) approximatingf(x) at two points.

4 We :Trapezoidaland Simpson sRuleNatasha , PhDUsing Linear Interpolating Polynomails f(x) =p1(x) wherep1(x) =(b x)f(a) + (x a)f(b)b , baf(x)dx bap1(x)dx ba(b x)f(a) + (x a)f(b)b adx=b a2[f(a) +f(b)] T1(f)NumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , PhDTrapezoidal RuleDefinition ( Trapezoidal Rule)The integration rule baf(x)dx b a2[f(a) +f(b)]=T1(f)is called the Trapezoidal :Trapezoidaland Simpson sRuleNatasha , PhDExample using Trapezoidal RuleExampleEvaluate /20sinx dxusing the Trapezoidal rule. /20sinx dx 4[sin 0 + sin( /2)]= /4 we know the true valueI= /20sinx dx= cos( /2) + cos(0) = 1, /20sinx dx T1(f) = 1 = :Trapezoidaland Simpson sRuleNatasha , PhDHow to improve the accuracy of the integrationrule?

5 An intuitive solution is to improve the accuracy off(x) byapplying the Trapezoidal rule on smaller subintervals of [a,b]instead of applying it to the original interval [a,b] that is applyit to integrals off(x) on smaller subintervals. For example, letc=a+b2then, baf(x)dx= caf(x)dx+ bcf(x)dx c a2[f(a) +f(c)]+b c2[f(c) +f(b)]=h2[f(a) + 2f(c) +f(b)] T2(f),whereh=b :Trapezoidaland Simpson sRuleNatasha , PhDTesting on the previous exampleExampleEvaluateI= /20sinx dxusing the three point Trapezoidal the approximation errorI T2(f).Please use the Fundamental theorem of calculus to directlycalculateI. /20sinx dx 8[sin 0 + 2 sin( /4) + sin( /2)] /20sinx dx T2(f) 1 = :Trapezoidaland Simpson sRuleNatasha , PhDGeneral Trapezoidal RuleTn(f)1We saw the Trapezoidal ruleT1(f) for 2 ruleT2(f) for 3 points involves three equidistantpoints:a,a+ observed the improvement in the accuracy ofT2(f)overT1(f) so inspired by this,we would like to apply this rule ton+ 1 equally spacedpointsa=x0<x1<x2 xn=bwith the space between any two points being denoted byhthat ish=xi+1 xi,i= 0.

6 Trapezoidaland Simpson sRuleNatasha , PhDGeneral Trapezoidal RuleTn(f)DefinitionI h[12f(a) +f(x1) + f(xn 1) +f(b)2] Tn(f)1 The subscript n refers to the number of subintervalsbeing used;2the pointsx0,x1, xnare called the numericalintegration node :Trapezoidaland Simpson sRuleNatasha , PhDPerformance ofTn(f)f(x) = sinxwe want to approximateI= /20f(x)dxusingthe Trapezoidal ruleTn(f)nTn(f)I Tn(f) that the errors are decreasing by a constant factor of do we always doublen?NumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , PhDHow to improve the accuracy of the integrationrule?An intuitive solution is to improve the accuracy off(x) byusing a better interpolating polynomial say a quadraticpolynomialp2(x) instead.

7 Letc=a+b2andh=b a2then, thequadratic polynomial isp2(x) =(x c)(x b)(a c)(a b)f(a) +(x a)(x b)(c a)(c b)f(c)+(x a)(x c)(b a)(b c)f(b). baf(x)dx bap2(x)dx=h3[f(a) + 4f(c) +f(b)] S2(f).This is called Simpson s :Trapezoidaland Simpson sRuleNatasha , PhDSimpson s rule applied to the previous exampleExampleEvaluate /20sinx dxusing the Simpson s rule. /20sinx dx /23[sin 0 + 4 sin( /4) + sin( /2)] /20sinx dx S2(f) = :Trapezoidaland Simpson sRuleNatasha , PhDGeneral Simpson s RuleSn(f)DefinitionI h3[(f(a) + 4f(x1) + 2f(x2))+ 4f(x3) + 2f(x4) + 4f(x5) 4f(xn 1) +f(b)] Sn(f)NumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , PhDPerformance ofSn(f)Forf(x) = sinxwe want to approximateI= /20f(x)dxusing the Simpson s ruleSn(f)nSn(f)I Sn(f) :Trapezoidaland Simpson sRuleNatasha , PhDError Formulas: Trapezoidal RuleTheoremLet f(x)have two continuous derivatives on[a,b].

8 Then,ETn(f) = baf(x)dx Tn(f) = h2(b a)12f (cn),where cnlies in[a,b].The error decays in a manner proportional to doubling n (and halvingh) should cause the error todecrease by a factor of approximately is what we observed with a past :Trapezoidaland Simpson sRuleNatasha , PhDExampleExampleConsider the task of evaluatingI= 20dx1 +x2using the Trapezoidal ruleTn(f).How large shouldnbe chosen in order to ensure that|ETn(f)| 5 10 6?NumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , begin by calculating the derivatives involved:f (x) = 2x(1 +x2)2,f (x) = 2 + 6x2(1 +x2)3,it is easy to check thatmax0 x 2|f (x)|= 2thus,|ETn(f)|=| h2(b a)12f (cn)| 2h212 2 = bound|f (cn)|since we do not know the exact value ofcnand hence, we must assume the worst possible value ofcnthatmakes the error formula the :Trapezoidaland Simpson sRuleNatasha , do we have|ETn(f)| 5 10 6?

9 We need to choosehso small thath23 5 10 6which is possible ifh (verify!). This is equivalentto choosingn=b ah=2 0h ,n 517 will make the error smaller than 5 10 :Trapezoidaland Simpson sRuleNatasha , PhDError Formulas: Simpson s RuleTheoremLet f(x)have four continuous derivatives on[a,b]. Then,ESn(f) = baf(x)dx Sn(f) = h4(b a)180f(4)(cn),where cnlies in[a,b].The error decays in a manner proportional to doubling n should cause the error to decrease by a factorof approximately is what we observed with a past :Trapezoidaland Simpson sRuleNatasha , PhDExampleExampleConsider the task of evaluatingI= 20dx1 +x2using the Simpson s ruleTn(f).How large shouldnbe chosen in order to ensure that|ESn(f)| 5 10 6?

10 NumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , compute the fourth derivativef(4)(x) = 245x4 10x2+ 1(1 +x2)5max0 x 1|f(4)(x)|=f(4)(0) = ,ESn(f) = h4(b a)180f(4)(cn) h4 2180 24 =4h415 5 10 6providedh ,thus choosingn 32 will give the desired error with the Trapezoidal rule:n 517!NumericalAnalysis:Trapezoidaland Simpson sRuleNatasha , PhDOne more exampleConsider the application of Trapezoidal and Simpson s rule toapproximate 10 x dxnETn(f)RatioESn(f) that the rate of convergence is slower sincef(x) = xis not sufficiently differentiable on [0,1]. Both converge at arate proportional