### Journal Menu >>

 Interval IntegrationRevisitedSérgio GaldinoPolytechnic School ofPernambucoUniversityRua Benﬁca, 455- Madalena50.750-470 - Recife- PE- BrazilEmail: galdino@poli.brAbstract—We present an overview of approaches to self-validating one-dimensional integration quadrature formulas anda veriﬁed numerical integration algorithm with an adaptivestrategy. The new interval integration adaptive algorithm deliversa desired integral enclosure with an error bounded by a speciﬁederror bound.The adaptive technique isusually much moreefﬁcient than Simpson’s rule and narrow interval results canbe reached.Index Terms—Interval computing, self-validating methods,numerical integration & interval arithmetic.I. INTRODUCTIONNumerical integration(quadrature) formulas are ofthe formI=baf(x)dx =n∑i=0w(n)if(xi)+E,with a=x0 100019. disp(’1000 levels of recursion reached.’)20. X=infsup(a,b);21. wx=diam(X);22. int = (b-a)*(fa+4*fm+fb)/6 -wx^5/2880*f4(X);23. else24. % Divide the interval in half and apply interval25. % Simpson 1/3 rule on each half. As an verified26. % error estimate: rad(int) > 2*tol*h/D;27. a=inf(X);28. b=sup(X);29.h=b-a;30. wx=h/2;31. flm = feval(f,a+h/4);32. frm = feval(f,b-h/4);33. n=n+2;34. X=infsup(a,a+h/2);35. simpl = h*(fa + 4*flm + fm)/12 - wx^5/2880*f4(X);36. X=infsup(a+h/2,b);37. simpr = h*(fm + 4*frm + fb)/12 - wx^5/2880*f4(X);38. int = simpl + simpr;39. X=infsup(a,b);40. % err =rad(int) > 2*tol*h/D41. % tolerance not satisfied, recursively refine42. if rad(int) > 2*tol*h/D;43.m=(a+b)/2;44. XL=infsup(a,m);45. XR=infsup(m,b);46. int = Iadaptsmp(f,f4,XL,tol,lev+1,fa,flm,fm) ...47. + Iadaptsmp(f,f4,XR,tol,lev+1,fm,frm,fb);48. end49. endSample Matlab M-ﬂle with the Intlab Toolboxthat calls theabove functionis followed by running results:1.format long2.% intvalinit(’DisplayMidRad’)3.global n4.f = @(x)23/25*cosh(x)-cos(x)5.f4 = @(x)23/25*cosh(x)-cos(x)6. X=infsup(-1,1)7. err=1.0E-12;8. IADAPTSMP(f,f4,X,err)9. n10. err1=rad(ans)>> ADAPTXIintval ans =<0.47942822668878, 0.00000000000047>n=241err1 =4.607425552194400e-013>>IV. NUMERICAL EXPERIMENTSIn thefollowing, wewill use the“battery" test offunctionswhich are a subset ofthe set used by Gonnet [11].Thebattery of testfunctions arelistedin Table I. The resulthasbeen calculatedusing 20 digits ofprecision with theMathcadcomputer software.The main mechanism for get a narrow interval results isto increasethe numberof subdivisions. Nextwe considertheprogression of the discretizationerror as we increase n.TableII shows that in the early stages increasing nimproves thediscretization.Weobserve however that if the number ofsubdivisions wereextremelylarge thismightlead tosigniﬁcant round-of (moreterms in the sum, each with a round-off error to contribute).Veriﬁed trapezoidal rulewith105subdivisions is widerthan104subdivisions andveriﬁed Simpson1/3 rulewith 104subdivisionsis wider than 103. Anarrow interval implies highprecision; we can specify plausible values to within a tinyrange. Veriﬁed stepruleinterval results arenarrowing (from10 to 106subdivisions), but intervals are wider, comparedwith veriﬁedtrapezoidal and Simpson1/3 rules, impliespoorprecision.In Table III we present the resultsof numerical experimentswith interval adaptive Simpson 1/3 rule. The battery oftest functions are listed in Table I. Forthesetest functionswe will consider the usual metrics of efﬁciency,i.e. numberof function evaluations required for a given accuracy.Wehave tested the code on four radius interval tolerancesτ=10−3,10−6,10−9,10−12.Interval adaptiveSimpson 1/3 algorithm was moreefﬁcientthan interval Simpson 1/3, the only exception is withf1forτ=10−3. Should be stressed that interval toleranceτ=10−12is not reached, by the interval Simpson 1/3 algorithm, forf9,f10,f11 test functions,with theused precision.V. CONCLUSIONThe design ofintervaliterativeformulas for self-validatingone-dimensional integration quadratureformulas isvery im-portant andisalsoaninterestingtaskininterval computing.In thispaper, wehaveproposedanew (supposed) one-dimensional interval integration adaptive algorithm, togetrigorous boundsof adesired integral. Numerical testsdemon-strate that interval adaptive technique is usually more efﬁcientthan interval Simpson’s rule with narrow interval results.Finding self-validating one-dimensional deﬁnite integration byderivative-free interval methods shouldbe consideredinfuturestudies.110 Copyright © 2012 SciRes. TABLE ITHEFUNCTIONSUSEDFOR THE “BATTERY”TEST.f1=10exdx=1.7182818284590452354f2=1−12325 cosh(x)−cos(x)dx =0.47942822668880166736f3=1−1x4+x2+0.9−1dx =1.5822329637296729331f4=101+x4−1dx =0.86697298733991103757f5=102(2+sin(10πx))−1dx=1.154700538379251529f6=10(1+x)−1dx =0.69314718055994530942f7=10(1+ex)−1dx =0.37988549304172247537f8=10.1sin(100πx)/(πx)dx=0.0090986375391668429156f9=100√50 e−50πx2dx=0.5f10 =10025 e−25xdx =1.0f11 =10050π2500x2+1−1dx=0.49936338107645674464f12 =1−11.005 +x2−1dx=1.5643964440690497731f13 =101+(230x−30)2−1dx=0.013492485649467772692TABLE IIESTIMATES OF 1−1cosh(x)2325 −cos(x)dx=sinh(x)2325 −sin(x)1−1.Analytical Answer Bounds =[0.47942822668880,0.47942822668881]Step Rule withVeriﬁcationSubdivisionsVeriﬁedResult10 0.492244876649698,0.191866375632378 100 0.479556403654468,0.019186637563241 1000 0.479429508459513,0.001918663756343 10000 0.479428239506509,1.918663758142536e−004100000 0.479428226816973,1.918663937550136e−0051000000 0.479428226690078,1.918681864720995e−006Trapezoidal Rule withVeriﬁcationSubdivisionsVeriﬁedResult10 0.479421870930105,6.395545854416262e−004100 0.479428226049601,16.395545891768606e−0071000 0.479428226688739,6.395906027023557e−01010000 0.479428226688802,1.002808946992673e−012100000 0.479428226687608,3.629152534045943e−0121000000 0.479428226671977,3.620936883663717e−011Simpson 1/3 Rule with VeriﬁcationSubdivisionsVeriﬁedResult10 0.479428217025575,2.131848625963606e−007100 0.479428226688792,2.139066701545289e−0121000 0.479428226688796,7.244205235679146e−01410000 0.479428226688723,7.243095012654521e−013100000 0.479428226688001,7.241873767327434e−0121000000 0.479428226680795,7.241879318442557e−011REFERENCES[1]G.F.CorlissandL. B.Rall:Adaptive, self-validating numerical quadra-ture. SIAM J. Sci. Statist. Comput. 8(5):831–47,(1985)TABLE IIIRESULTS OF BATTERY TEST:ADAPTIVEAND SIMPSON 1/3RULESWITHVERIFICATIONAlgorithms:AdaptiveSimpson 1/3(Simpson 1/3)f(x)τ=10−3τ=10−6τ=10−9τ=10−12f15(3)9(12)33 (39)129(150)f25(6)17 (21)65(78)241 (306)f325 (30)97(108)361 (423)1441 (1701)f49(12)33 (45)109(174)429 (693)f5105 (135)393(522)1489(2064)5921 (8718)f65(6)13 (18)49(63)189 (252)f75(6)17 (18)65(69)257 (273)f8445 (516)1797(2070)7077 (8241)28125 (32922)f949 (684)133(2640)449(10488)1725 (−)f10 49 (531)125(2106)433 (8376)1681 (−)f11 89 (2916)305(10833)1193 (42870)4765 (−)f12 17 (24)57(84)241 (330)945 (1323)f13 57 (519)153(1872)541 (7323)2161 (29193)TABLE IVRESULTS OFBATTERYTEST:ADAPTIVESIMPSON 1/3RULEWITHVERIFICATIONIntegral AdaptiveSimpson1/3 (τ=10−12 )fVeriﬁedResultErrorf1<1.71828182845904,0.00000000000029 >0.29 ×10−12f2<0.47942822668878,0.00000000000047 >0.47 ×10−12f3<1.58223296372967,0.00000000000048 >0.48 ×10−12f4<0.86697298733961,0.00000000000072 >0.72 ×10−12f5<1.15470053839294,0.00000000000056 >0.56 ×10−12f6<0.69314718055994,0.00000000000056 >0.56 ×10−12f7<0.37988549304172,0.00000000000019 >0.19 ×10−12f8<0.00909863753917,0.00000000000044 >0.44 ×10−12f9<0.50000000000000,0.00000000000004 >0.04 ×10−12f10 <0.99999999999999,0.00000000000008 >0.08 ×10−12f11 <0.49936338107645,0.00000000000062 >0.62 ×10−12f13 <1.56439644405124,0.00000000000057 >0.57 ×10−12f13 <0.01349248564896,0.00000000000054 >0.54 ×10−12[2]R.Kelch. Ein adaptivesVerfahren zur numerischen Quadraturmitautomatischer Ergebnisveriﬁkation.PhDthesis, Universität Karlsruhe,(1989)[3]U.Storck. Numerical integration in two dimensions with automatic resultveriﬁcation. InE. Adams and U. Kulisch, editors,Scientiﬁc Computingwith Automatic Result Veriﬁcation,AcademicPress, New York, etc.,187–224, (1993) .[4]J.C. Burkill:Functions of intervals. Proceedings ofthe LondonMathe-matical Society, 22:375-446, (1924)[5]R.C. Young:The algebra of many-valuedquantities. Math. Ann. 104:260-290, (1931)[6]T. Sunaga: TheoryofanInterval AlgebraanditsApplication toNumerical Analysis. Gaukutsu Bunken Fukeyu-kai, Tokyo, (1958)[7]R.E.Moore: Interval Arithmetic andAutomatic ErrorAnalysis inDigitalComputing. PhD thesis, Stanford University, October, (1962)[8]R.E.Moore: Interval Analysis.Prentice Hall, EnglewoodClifs, NJ,USA,(1966)[9]G.F. Kuncir: Algorithm 103:Simpson’s rule integrator. Communicationsof the ACM 5(6): 347, (1962)[10]J.N.Lyness: Notes on the adaptive Simpson quadrature routine. Journalof the ACM 16 (3): 483–495, (1969)[11]P.Gonnet: Adaptivequadrature re-revisited. ETHZürich ThesisNr.18347 (2009). http://dx.doi.org/10.3929/ethz-a-005861903[12]S.M.Rump: INTLAB - INTerval LABoratory. Tibor Csendes, Develop-ments in Reliable Computing, Kluwer AcademicPublishers, Dordrecht,77–104, (1999), http://www.ti3.tu-harburg.de/rump/[13]DouglasN.Arnold: AConcise Introductionto NumericalAnalysis.Institute forMathematics andits Applications,Universityof Minnesota,Minneapolis, MN 55455 (2001). http://www.ima.umn.edu/~arnold/Copyright © 2012 SciRes.111