(566f) Higher-Order Inclusions of Nonlinear Systems By Chebyshev Models

Estimators that consist of a polynomial approximant and an interval remainder on the approximation error have been successfully used to create bounds for nonlinear systems, with applications to validated ODE integration and global optimization. Taylor models in particular are generated by creating a Taylor expansion of a function at a point, with the approximation error bounded for the given approximation range [1,2]. There is an arithmetic linked to Taylor models which allows for univariate and bivariate operations to be carried out and therefore Taylor models to be built up operation-wise for (sufficiently smooth) factorable functions. Nonetheless, it may appear unnatural to create the polynomial approximation at a point and then bound the approximation error over a range. Instead, the main focus of this presentation is on Chebyshev polynomials, which provide a polynomial approximation of a function over a range.

A Chebyshev expansion consists of a multilinear combination of Chebyshev polynomials similar to how a Taylor polynomial is made up of a multilinear combination of monomials [3]. We have developed an equivalent to Taylor model arithmetic in Chebyshev model arithmetic, which includes rules on how to carry out a number of common univariate operations along with bivariate addition and multiplication and steps such as bounding the range of a Chebyshev expansion. An important challenge in creating such an arithmetic arises in the multiplication of Chebyshev polynomials which creates two terms, whereas for monomials only one term is created. This proves to be a particular challenge for n-variate Chebyshev models as 2ⁿ terms are created via multiplication. Besides, creating a Chebyshev expansion for intrinsic univariate functions proves to be more challenging than a Taylor expansion as the coefficients are calculated via integration as opposed to differentiation. Here, we have chosen to create a 'cheap' approximation via interpolation as we know the approximation error is no more than double that of the approximation created via integration. Moreover, we have developed a method for finding sharp remainder bounds for a subset of the univariate operations, which significantly reduces the width of the remainder term.

An implementation for Chebyshev models has been created using C++, which can deal with multivariate Chebyshev models and the commonly used operations. This can been used to compare the performance of Chebyshev models to Taylor models for function bounding, verified ODE integration, and bounding of the solutions of implicit equations. Our results show that we obtain tighter bounds with Chebyshev models in all the cases.

References:
[1] A. Neumaier (2002). Taylor forms - Use and limits. Reliable Computing, 9(1):43-79.
[2] K. Makino; M. Berz (2003). Taylor models and other validated functional inclusion functions. International Journal of Pure and Applied Mathematics, 4(4):379-456.
[3] L.N. Trefethen (2013). Approximation Theory and Approximation Practice. SIAM, Philadelphia.