Automatic integration using asymptotically optimal adaptive Simpson quadrature

详细信息    查看全文

• 作者：Leszek Plaskota
• 关键词：65Y20 ; 65D05 ; 41A10 ; 41A25
• 刊名：Numerische Mathematik
• 出版年：2015
• 出版时间：September 2015
• 年：2015
• 卷：131
• 期：1
• 页码：173-198
• 全文大小：907 KB
• 参考文献：1.Calvetti, D., Golub, G.H., Gragg, W.B., Reichel, L.: Computation of Gauss-Kronrod quadrature rules. Math. Comput. 69, 1035鈥?052 (2000)MATH MathSciNet View Article
  2.Clancy, N., Ding, Y., Hamilton, C., Hickernell, F.J., Zhang, Y.: The cost of deterministic, adaptive, automatic algorithms: cones, not balls. J. Complex. 30, 21鈥?5 (2014)MATH MathSciNet View Article
  3.Conte, S.D., de Boor, C.: Elementary numerical analysis鈥攁n algorithmic approach, 3rd edn. McGraw-Hill, New York (1980)MATH
  4.Davis, P.J., Rabinowitz, P.: Methods of numerical integration, 2nd edn. Academic Press, Orlando (1984)MATH
  5.Gander, W., Gautschi, W.: Adaptive quadrature鈥攔evisited. BIT 40, 84鈥?01 (2000)MathSciNet View Article
  6.Kincaid, D., Cheney, W.: Numerical analysis: mathematics of scientific computing, 3rd edn. AMS, Providence, RI (2002)
  7.Kruk, A.: Is the adaptive Simpson quadrature optimal? Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Master Thesis (in Polish) (2012)
  8.Lyness, J.N.: Notes on the adaptive Simpson quadrature routine. J. Assoc. Comput. Mach. 16, 483鈥?95 (1969)MATH MathSciNet View Article
  9.Lyness, J.N.: When not to use an automatic quadrature routine? SIAM Rev. 25, 63鈥?7 (1983)MATH MathSciNet View Article
  10.McKeeman, W.M.: Algorithm 145: adaptive numerical integration by Simpson鈥檚 rule. Commun. ACM 5, 604 (1962)View Article
  11.Malcolm, M.A., Simpson, R.B.: Local versus global strategies for adaptive quadrature. ACM Trans. Math. Softw. 1, 129鈥?46 (1975)MATH MathSciNet View Article
  12.Novak, E.: On the power of adaption. J. Complex. 12, 199鈥?38 (1996)MATH View Article
  13.Piessens, R., de Doncker-Kapenga, E., Uberhuber, C.W., Kahaner, D.K.: QUADPACK. A subroutine package for automatic integration. Springer, Berlin (1983)
  14.Plaskota, L.: Noisy Information and computational complexity. Cambridge University Press, Cambridge (1996)MATH View Article
  15.Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical recipes: the art of scientific computing, 3rd edn. Cambridge University Press, New York (2007)MATH
  16.Plaskota, L., Wasilkowski, G.W.: Adaption allows efficient integration of functions with unknown singularities. Numerische Mathematik 102, 123鈥?44 (2005)MATH MathSciNet View Article
  17.Traub, J.F., Wasilkowski, G.W., Wo藕niakowski, H.: Information-based complexity. Academic Press, New York (1988)MATH
  18.Wasilkowski, G.W.: Information of varying cardinality. J. Complex. 1, 107鈥?17 (1986)MathSciNet View Article
  
• 作者单位：Leszek Plaskota (1)
  
  1. Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Banacha 2, 02-097, Warsaw, Poland
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Mathematics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  Numerical and Computational Methods
  Applied Mathematics and Computational Methods of Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：0945-3245

文摘

We present a novel theoretical approach to the analysis of adaptive quadratures and adaptive Simpson quadratures in particular which leads to the construction of a new algorithm for automatic integration. For a given function \(f\in C^4\) with \(f^{(4)}\ge 0\) and possible endpoint singularities the algorithm produces an approximation to \(\int _a^bf(x)\,{\mathrm d}x\) within a given \(\varepsilon \) asymptotically as \(\varepsilon \rightarrow 0\). Moreover, it is optimal among all adaptive Simpson quadratures, i.e., needs the minimal number \(n(f,\varepsilon )\) of function evaluations to obtain an \(\varepsilon \)-approximation and runs in time proportional to \(n(f,\varepsilon )\).