Extensions of Gauss Quadrature Via Linear Programming

详细信息    查看全文

• 作者：Ernest K. Ryu ; Stephen P. Boyd
• 关键词：Gauss quadrature ; Semi ; infinite programming ; Convex optimization ; 65D32 ; 90C34 ; 90C48
• 刊名：Foundations of Computational Mathematics
• 出版年：2015
• 出版时间：August 2015
• 年：2015
• 卷：15
• 期：4
• 页码：953-971
• 全文大小：1,272 KB
• 参考文献：1.M. Abramowitz and I. Stegun. Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables. Dover Publications, Incorporated, New York, 1964.
  2.C. Aliprantis and K. Border. Infinite Dimensional Analysis: A Hitchhiker鈥檚 Guide. Springer, New York, 3rd edition, 2006.
  3.E. Anderson and P. Nash. Linear Programming in Infinite-dimensional Spaces: Theory and Applications. Wiley, New York, 1987.
  4.E. Anderson and A. Philpott. Infinite Programming: Proceedings of an International Symposium on Infinite Dimensional Linear Programming, Churchill College, Cambridge, United Kingdom, September 7鈥?0, 1984. Springer-Verlag, New York, 1985.
  5.S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004.
  6.E. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2):489鈥?09, 2006.
  7.S. Chen, D. Donoho, and M. Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20(1):33鈥?1, 1999.
  8.P. Davis. A construction of nonnegative approximate quadratures. Mathematics of Computation, 21(100):578鈥?82, 1967.
  9.P. Davis and P. Rabinowitz. Methods of Numerical Integration. Academic Press, Orlando, 2nd edition, 1984.
  10.A Fiacco and K. Kortanek. Semi-infinite Programming and Applications: An International Symposium, Austin, Texas, September 8鈥?0, 1981. Springer-Verlag, New York, 1983.
  11.C. Gauss. Methodus nova integralium valores per approximationem inveniendi. Commentationes Societatis Regiae Scientarium Gottingensis Recentiores, 3:39鈥?6, 1814.
  12.A. Glaser, X. Liu, and V. Rokhlin. A fast algorithm for the calculation of the roots of special functions. SIAM Journal on Scientific Computing, 29(4):1420鈥?438, 2007.
  13.M. Goberna and M. L贸pez. Linear Semi-infinite Optimization. John Wiley, 1998.
  14.G. Golub and J. Welsch. Calculation of gauss quadrature rules. Mathematics of Computation, 23(106):221鈥?30, 1969.
  15.P. Hammer and A. Stroud. Numerical evaluation of multiple integrals II. Mathematics of Computation, 12:272鈥?80, 1958.
  16.J. Hiriart-Urruty and C. Lemarechal. Convex Analysis and Minimization Algorithms I: Fundamentals. Springer, New York, October 1993.
  17.S. Karlin and W. Studden. Tchebycheff Systems: With Applications in Analysis and Statistics. Interscience Publishers, New York, 1966.
  18.M. Krein. The ideas of P. L. Chebyshev and A. A. Markov in the theory of limiting values of integrals and their further development. American Mathematical Society Translations (Series 2), 12:1鈥?22, 1959.
  19.V. Krylov. Approximate Calculation of Integrals. Macmillan, New York, 1962.
  20.J. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11:796鈥?17, 2001.
  21.D. Luenberger. Optimization by Vector Space Methods. John Wiley & Sons, New York, 1967.
  22.D. Luenberger and Y. Ye. Linear and Nonlinear Programming. Springer, New York, third edition, 2008.
  23.J. Ma, V. Rokhlin, and S. Wandzura. Generalized Gaussian quadrature rules for systems of arbitrary functions. SIAM Journal on Numerical Analysis, 33(3):971鈥?96, 1996.
  24.A. Markov. On the limiting values of integrals in connection with interpolation. Zapiski Imperatorskoj Akademii Nauk po Fiziko-matematiceskomu Otdeleniju, 5:146鈥?30, 1898.
  25.G. Murty and S. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117鈥?29, 1987.
  26.J. Nocedal and S. Wright. Numerical Optimization. Springer, New York, 2nd edition, 2006.
  27.W. Peirce. Numerical integration over the planar annulus. Journal of the Society for Industrial and Applied Mathematics, 5(2):66鈥?3, 1957.
  28.J. Powell. Approximation Theory and Methods. Cambridge University Press, Cambridge, 1981.
  29.R. Rockafellar. Convex Analysis. Princeton University Press, Princeton, 1996.
  30.A. Stroud. Quadrature methods for functions of more than one variable. Annals of the New York Academy of Sciences, 86(3):776鈥?91, 1960.
  31.A. Stroud and D. Secrest. Gaussian Quadrature Formulas. Prentice-Hall, Englewood Cliffs, 1966.
  32.E. S眉li and D. Mayers. An Introduction to Numerical Analysis. Cambridge University Press, Cambridge, 2003.
  33.R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society (Series B), 58:267鈥?88, 1996.
  34.B. Vioreanu. Spectra of Multiplication Operators as a Numerical Tool. PhD thesis, Yale University, 2012.
  35.H. Xiao and Z. Gimbutas. A numerical algorithm for the construction of efficient quadrature rules in two and higher gimensions. Computational Mathematics with Applications, 59(2), 2010.
  
• 作者单位：Ernest K. Ryu (1)
  Stephen P. Boyd (2)
  
  1. Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA聽, 94305, USA
  2. Electrical Engineering, Stanford University, Stanford, CA聽, 94305, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Computer Science, general
  Math Applications in Computer Science
  Linear and Multilinear Algebras and Matrix Theory
  Applications of Mathematics
  
• 出版者：Springer New York
• ISSN：1615-3383

文摘

Gauss quadrature is a well-known method for estimating the integral of a continuous function with respect to a given measure as a weighted sum of the function evaluated at a set of node points. Gauss quadrature is traditionally developed using orthogonal polynomials. We show that Gauss quadrature can also be obtained as the solution to an infinite-dimensional linear program (LP): minimize the \(n\)th moment among all nonnegative measures that match the \(0\) through \(n-1\) moments of the given measure. While this infinite-dimensional LP provides no computational advantage in the traditional setting of integration on the real line, it can be used to construct Gauss-like quadratures in more general settings, including arbitrary domains in multiple dimensions.