×

Polynomials with bounds and numerical approximation. (English) Zbl 1379.65010

Let \(P_n\) be the set of polynomials of degree at most \(n\) and \(U_n=\{p\in P_n: x\in I \Rightarrow p(x)\in I\}\) where \(I=[0,1]\). A large part of the paper is devoted to finding a good parametrization for such bounded polynomials. This is first obtained by using the Lukács theorem for nonnegative polynomials and Euler’s four squares identity which gives a \(2\pi\)-periodic solutions depending on three angles for \(n=1\) and by iteration for \(n>1\). This is used to prove that \(\inf_{p\in U_n}\|f-p\|\leq 2\inf_{p\in P_n}\|f-p\|\). Some ideas are given on how this can be generalized to bivariate polynomials. This requires to replace the four squares property by the eight squares identity of Degen. Some implementation details are given and illustrated with some numerical applications.

MSC:

65D15 Algorithms for approximation of functions
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Bochnak, J., Coste, M., Roy, M.-F.: Real algebraic geometry, A series of modern surveys in Mathematics, vol. 36. Springer (1998)
[2] Bojanovic, R., Devore, R. A.: On polynomials of best one side approximation. L’enseignement mathématique 12 (1966)
[3] Chatelin, F.: A computational journey into the mind. Nat. Comput. 11(1), 67-79 (2012) · Zbl 1251.30054 · doi:10.1007/s11047-011-9269-6
[4] Chevillard, S., Harrison, J., Joldes, M., Lauter, C. h.: Efficient and accurate computation of upper bounds of approximation errors. Theoretical Computer Science 412(16), 1523-1543 (2011) · Zbl 1211.65025 · doi:10.1016/j.tcs.2010.11.052
[5] Chevillard, S., Jolde, M., Lauter, C.: Sollya: an environment for the development of numerical codes. In: Mathematical Software - ICMS 2010, pp 28-31. Springer, Heidelberg, Germany (2010) · Zbl 1295.65143
[6] Choi, M. D., Lam, T. Y., Reznick, B.: Sum of squares of real polynomials. Proceedings of Symposia in Pure Mathematics 58(2), 103,26 (1995)
[7] Conrad, K.: Quaternions algebras, expository paper online at K. Conrad webpage http://www.math.uconn.edu/ kconrad/blurbs/ringtheory/quaternionalg.pdf · Zbl 0487.41008
[8] Després, B.: Polynomials with bounds and numerical approximation, Hal preprint server 2016 https://hal.archives-ouvertes.fr/hal-01307999v3/document · Zbl 1159.17321
[9] Després, B., Perthame, B.: Uncertainty propagation; intrusive kinetic formulations of scalar conservation laws, submitted to SIAM J Uncertainty Quantification (2015) · Zbl 1362.35342
[10] Després, B., Trelat, E.: Space-time two sided l1 approximation and optimal control of polynomial systems in preparation (2016)
[11] Devore, R. A., Lorenz, G. G.: Constructive approximation. Springer (1981)
[12] Driscoll, T. A., Hale, N., Trefethen, L. N. (eds.): Chebfun Guide. Pafnuty Publications, Oxford (2014)
[13] Ebbinghaus, H. -D., et al.: Numbers. Springer-Verlag, New York (1991) · doi:10.1007/978-1-4612-1005-4
[14] Foucart, S., Rauhut, H.: A mathematical introduction to compressive sensing, Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York (2013) · Zbl 1315.94002
[15] Fourer, R., Gay, D. M., Kernighan, B. W.: AMPL: A modeling language for mathematical programming, 2nd edn. Brooks/Cole-Thomson Learning (2003) · Zbl 0701.90062
[16] fminunc (Find minimum of unconstrained multivariable function), Matlab online reference manuel http://fr.mathworks.com/help/optim/ug/fminunc.html (2016)
[17] Godlevski, E., Raviart, P. A.: Numerical approximation of hyperbolic systems of conservation laws, vol. 118. Springer Verlag, New York (1996). AMS 118 · Zbl 1161.65309
[18] Govil, N. K., Mohapatra, R. N.: Markov and BernsteinType Inequalities for polynomials. J. of lnequal. & Appl. 3, 349-387 (1999) · Zbl 0933.30003
[19] Griebel, M., Hullmann, A., Oswald, P.: Peter Optimal scaling parameters for sparse grid discretizations. Numer. Linear Algebra Appl. 22(1), 76-100 (2015) · Zbl 1349.65557 · doi:10.1002/nla.1939
[20] Lasserre, J. B.: Moments, positive polynomials and their applications. Imperial college press (2010) · Zbl 1211.90007
[21] LeVeque, R. J.: Numerical methods for conservation laws. ETHZ Zurich, Birkhauser, Basel (1992) · Zbl 0847.65053 · doi:10.1007/978-3-0348-8629-1
[22] Maday, Y.; Mula, O.; Brezzi, F. (ed.), A Generalized empirical interpolation method: application of reduced basis techniques to data assimilation (2013), Italia · Zbl 1267.62013
[23] Magron, V., Allamigeon, X., Gaubert, S., Werner, B.: Formal proofs for nonlinear optimization. Journal of Formalized Reasoning 8(1) (2014) · Zbl 1451.90131
[24] Markov, A. A.: On a problem of D.I. Mendeleev, Zap. Imp. Akad. Nauk, St Petersburg 62(in russian), 1-24 (1889)
[25] Maunder, C. M. C.: Algebraic topology. Dover, New York (1997) · Zbl 0205.27302
[26] Milovanovic, G. V., Mitrinovic, D. S., Rassias, T. M.: Topics in polynomials: extremal problems, inequalities, zeros. World Scientific Publishing Co., Inc., River Edge, NJ (1994) · Zbl 0848.26001 · doi:10.1142/1284
[27] Mitrinovic, D.S.: Analytic inequalities. Springer Verlag (1970) · Zbl 0199.38101
[28] Oneto, A.: Alternative real division algebras of finite dimension. Divulgaciones Matemàticas 10(2), 161-169 (2002) · Zbl 1159.17321
[29] Papachristodoulou, A., Anderson, J., Valmorbida, G., Prajna, S., Seiler, P., Parrilo, P. A.: SOSTOOLS Sum of squares optimization toolbox for MATLAB User’s guide. file:///Users/despres/Desktop/PUB/Polynomes/Positive_poly/REVISED/SOSTOOLS (2016) · Zbl 0060.14805
[30] Poëtte, G., Després, B., Lucor, D.: Uncertainty quantification for systems of conservation laws. Journal of Computational Physics 228(7), 2443-2467 (2009) · Zbl 1161.65309 · doi:10.1016/j.jcp.2008.12.018
[31] Rack, H. J.: A generalization of an inequality of V. Markov to multivariate polynomials. J. Approx. Theory 35, 94-97 (1982) · Zbl 0487.41008 · doi:10.1016/0021-9045(82)90108-3
[32] Risler, J. J.: Mathematical methods for CAD. Translated from the French edition, p 1992. Cambridge University Press, Cambridge (1990)
[33] Risler, J. J.: Computer aided geometric design. Handbook of numerical analysis, vol. V, 715-818, Handb. Numer. Anal., vol. V. North-Holland, Amsterdam (1997)
[34] Shang, Y., Wan, Y., Fromherz, M. P.J., Crawford, L. S.: Towards adaptive cooperation between global and local solvers for continuous constraint problems. In: 7th International Conference on Principles and Practice of Constraint Programming (CP’01)-Workshop on Cooperative Solvers in Constraint Programming (2001)
[35] Shapiro, D.: Compositions of Quadratic Forms. de Gruyter, New York (2000) · Zbl 0954.11011 · doi:10.1515/9783110824834
[36] Shu, C. W.: Bound-preserving high order accurate schemes. Notes of the Canadian Mathematical Society (CMS Notes) v45, 24-25 (2013)
[37] Solovyev, A., Hales, T. C.: Formal verification of nonlinear inequalities with taylor interval approximations. Chapter NASA Formal Methods Volume 7871 of the series Lecture Notes in Computer Science, 383-397 (2013) · Zbl 0060.14805
[38] Szego, G.: Orthogonal polynomials. AMS (1939) · JFM 65.0278.03
[39] Toro, E. F: Riemann solvers and numerical methods in fluid dynamics, a practical introduction. Springer (1997) · Zbl 0888.76001
[40] Townsend, A., Trefethen, L. N.: An extension of Chebfun to two dimensions. SIAM J. Sci. Comput. 35(6), 495-518 (2016) · Zbl 1300.65010 · doi:10.1137/130908002
[41] Videnskii, V. S.: On the estimates of the derivatives of polynomials. Izv. Akad. Nauk. SSSR, Ser. Mat. 15(in Russian) (1951)
[42] Visser, C.: A simple proof of certain inequalities concerning polynomials. Proc. Koninkl. Ned. Akad. Wetenshap. 48, 276-281 (1948) · Zbl 0060.14805
[43] Weisse, A., Wellein, G., Alvermann, A., Fehske, H.: The kernel polynomial method. Rev. Mod. Phys. 78, 275 (2006) · Zbl 1205.81090 · doi:10.1103/RevModPhys.78.275
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.