# zbMATH — the first resource for mathematics

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
##### Software:
AMPL; Chebfun; Chebfun2; HE-E1GODF; Matlab; Sollya; Sostools
Full Text:
##### References:
  Bochnak, J., Coste, M., Roy, M.-F.: Real algebraic geometry, A series of modern surveys in Mathematics, vol. 36. Springer (1998)  Bojanovic, R., Devore, R. A.: On polynomials of best one side approximation. L’enseignement mathématique 12 (1966)  Chatelin, F, A computational journey into the mind, Nat. Comput., 11, 67-79, (2012) · Zbl 1251.30054  Chevillard, S; Harrison, J; Joldes, M; Lauter, Ch, Efficient and accurate computation of upper bounds of approximation errors, Theoretical Computer Science, 412, 1523-1543, (2011) · Zbl 1211.65025  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  Choi, MD; Lam, TY; Reznick, B, Sum of squares of real polynomials, Proceedings of Symposia in Pure Mathematics, 58, 103,26, (1995)  Conrad, K.: Quaternions algebras, expository paper online at K. Conrad webpage http://www.math.uconn.edu/ kconrad/blurbs/ringtheory/quaternionalg.pdf · Zbl 0487.41008  Després, B.: Polynomials with bounds and numerical approximation, Hal preprint server 2016 https://hal.archives-ouvertes.fr/hal-01307999v3/document · Zbl 1159.17321  Després, B., Perthame, B.: Uncertainty propagation; intrusive kinetic formulations of scalar conservation laws, submitted to SIAM J Uncertainty Quantification (2015)  Després, B., Trelat, E.: Space-time two sided $$l$$\^{1} approximation and optimal control of polynomial systems in preparation (2016)  Devore, R. A., Lorenz, G. G.: Constructive approximation. Springer (1981)  Driscoll, T. A., Hale, N., Trefethen, L. N. (eds.): Chebfun Guide. Pafnuty Publications, Oxford (2014)  Ebbinghaus, H. -D., et al.: Numbers. Springer-Verlag, New York (1991)  Foucart, S., Rauhut, H.: A mathematical introduction to compressive sensing, Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York (2013) · Zbl 1315.94002  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  fminunc (Find minimum of unconstrained multivariable function), Matlab online reference manuel http://fr.mathworks.com/help/optim/ug/fminunc.html (2016)  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  Govil, NK; Mohapatra, RN, Markov and bernsteintype inequalities for polynomials, J. of lnequal. & Appl., 3, 349-387, (1999) · Zbl 0933.30003  Griebel, M; Hullmann, A; Oswald, P, Peter optimal scaling parameters for sparse grid discretizations, Numer. Linear Algebra Appl., 22, 76-100, (2015) · Zbl 1349.65557  Lasserre, J. B.: Moments, positive polynomials and their applications. Imperial college press (2010) · Zbl 1211.90007  LeVeque, R. J.: Numerical methods for conservation laws. ETHZ Zurich, Birkhauser, Basel (1992) · Zbl 0847.65053  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  Magron, V., Allamigeon, X., Gaubert, S., Werner, B.: Formal proofs for nonlinear optimization. Journal of Formalized Reasoning 8(1) (2014)  Markov, A. A.: On a problem of D.I. Mendeleev, Zap. Imp. Akad. Nauk, St Petersburg 62(in russian), 1-24 (1889)  Maunder, C. M. C.: Algebraic topology. Dover, New York (1997) · Zbl 0205.27302  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  Mitrinovic, D.S.: Analytic inequalities. Springer Verlag (1970) · Zbl 0199.38101  Oneto, A, Alternative real division algebras of finite dimension, Divulgaciones Matemàticas, 10, 161-169, (2002) · Zbl 1159.17321  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  Poëtte, G; Després, B; Lucor, D, Uncertainty quantification for systems of conservation laws, Journal of Computational Physics, 228, 2443-2467, (2009) · Zbl 1161.65309  Rack, HJ, A generalization of an inequality of V. Markov to multivariate polynomials, J. Approx. Theory, 35, 94-97, (1982) · Zbl 0487.41008  Risler, J. J.: Mathematical methods for CAD. Translated from the French edition, p 1992. Cambridge University Press, Cambridge (1990)  Risler, J. J.: Computer aided geometric design. Handbook of numerical analysis, vol. V, 715-818, Handb. Numer. Anal., vol. V. North-Holland, Amsterdam (1997)  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)  Shapiro, D.: Compositions of Quadratic Forms. de Gruyter, New York (2000) · Zbl 0954.11011  Shu, CW, Bound-preserving high order accurate schemes, Notes of the Canadian Mathematical Society (CMS Notes), v45, 24-25, (2013)  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  Szego, G.: Orthogonal polynomials. AMS (1939) · JFM 65.0278.03  Toro, E. F: Riemann solvers and numerical methods in fluid dynamics, a practical introduction. Springer (1997) · Zbl 0888.76001  Townsend, A; Trefethen, LN, An extension of chebfun to two dimensions, SIAM J. Sci. Comput., 35, 495-518, (2016) · Zbl 1300.65010  Videnskii, V. S.: On the estimates of the derivatives of polynomials. Izv. Akad. Nauk. SSSR, Ser. Mat. 15(in Russian) (1951)  Visser, C, A simple proof of certain inequalities concerning polynomials, Proc. Koninkl. Ned. Akad. Wetenshap., 48, 276-281, (1948) · Zbl 0060.14805  Weisse, A; Wellein, G; Alvermann, A; Fehske, H, The kernel polynomial method, Rev. Mod. Phys., 78, 275, (2006) · Zbl 1205.81090
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.