Approximating the \(p\)th root by composite rational functions. (English) Zbl 1471.41006
It is shown that a rational function \(r\) of the form \(r(x)=r_k(x,r_{k-1}(x,r_{k-2}(\dots (x,r_1(x,1)))))\) approximates the function \(x^{1/p}\) on the interval \([0,1]\) with superalgebraic accuracy close to \(p\)th root exponential convergence. This convergence is doubly exponential with respect to the number of degree of freedom. The error is \(O(\exp(-c_1\exp(c_2d)))\) for some constants \(c_1,c_2>0\) and \(d\) is the number of parameters expressing the rational function, \(d=\sum_{i=1}^k m_i+l_i+1\) if \(r_i\) is of the type \((m_i,l_i), i=1,2,\dots,k\).
Reviewer: Josef Kofroň (Praha)
MSC:
| 41A20 | Approximation by rational functions |
| 41A25 | Rate of convergence, degree of approximation |
| 41A50 | Best approximation, Chebyshev systems |
| 65D15 | Algorithms for approximation of functions |
Keywords:
rational approximation; function composition; minimax; zolotarev; square root; \(p\)th root; sign function; sector functionSoftware:
mftoolboxReferences:
| [1] | Akhiezer, N. I., (Elements of the Theory of Elliptic Functions. Elements of the Theory of Elliptic Functions, Translations of Mathematical Monographs, vol. 79 (1990), American Mathematical Society) · Zbl 0694.33001 |
| [2] | B. Beckermann, Optimally scaled Newton iterations for the matrix square root, FUN13: Advances in Matrix Functions and Matrix Equations workshop, 2013. |
| [3] | Beckermann, B.; Townsend, A., On the singular values of matrices with displacement structure, SIAM J. Matrix Anal. Appl., 38, 4, 1227-1248 (2017) · Zbl 1386.15024 |
| [4] | Bogatyrev, A., Rational functions admitting double decompositions, Trans. Moscow Math. Soc., 73, 161-165 (2012) · Zbl 1284.30014 |
| [5] | Boullé, N.; Nakatsukasa, Y.; Townsend, A., Rational neural networks, Adv. Neural Inf. Process. Syst., 33, 14243-14253 (2020) |
| [6] | Braess, D., Nonlinear Approximation Theory (1986), Springer · Zbl 0656.41001 |
| [7] | Gawlik, E. S., Zolotarev iterations for the matrix square root, SIAM J. Matrix Anal. Appl., 40, 2, 696-719 (2019) · Zbl 1420.65057 |
| [8] | Gawlik, E. S., Rational minimax iterations for computing the matrix pth root, Constr. Approx. (2021), (in press) · Zbl 1510.65079 |
| [9] | Gončar, A., On the rapidity of rational approximation of continuous functions with characteristic singularities, Math. USSR-Sbornik, 2, 4, 561 (1967) |
| [10] | Higham, N. J., Functions of Matrices: Theory and Computation, xx+425 (2008), SIAM: SIAM Philadelphia, PA, USA · Zbl 1167.15001 |
| [11] | King, R. F., Improved Newton iteration for integral roots, Math. Comp., 25, 114, 299-304 (1971) · Zbl 0215.55502 |
| [12] | LeCun, Y.; Bengio, Y.; Hinton, G., Deep learning, Nature, 521, 7553, 436 (2015) |
| [13] | Meinardus, G.; Taylor, G., Optimal partitioning of Newton’s method for calculating roots, Math. Comp., 35, 152, 1221-1230 (1980) · Zbl 0458.65031 |
| [14] | Nakatsukasa, Y.; Freund, R. W., Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of Zolotarev’s functions, SIAM Rev., 58, 3, 461-493 (2016) · Zbl 1383.15012 |
| [15] | Ninomiya, I., Best rational starting approximations and improved Newton iteration for the square root, Math. Comp., 24, 110, 391-404 (1970) · Zbl 0213.16402 |
| [16] | Petrushev, P. P.; Popov, V. A., Rational Approximation of Real Functions (2011), Cambridge University Press · Zbl 1209.41002 |
| [17] | Rickards, J., When is a polynomial a composition of other polynomials?, Amer. Math. Monthly, 118, 4, 358-363 (2011) · Zbl 1233.12002 |
| [18] | Ritt, J. F., Prime and composite polynomials, Trans. Amer. Math. Soc., 23, 1, 51-66 (1922) · JFM 48.0079.01 |
| [19] | Rutishauser, H., Betrachtungen zur quadratwurzeliteration, Monatshefte für Mathematik, 67, 5, 452-464 (1963) · Zbl 0143.39203 |
| [20] | Shieh, L. S.; Tsay, Y. T.; Wang, C. T., Matrix sector functions and their applications to systems theory, (IEE Proceedings D, Control Theory and Applications, vol. 131 (1984), IET), 171-181 · Zbl 0568.93011 |
| [21] | Stahl, H. R., Best uniform rational approximation of \(x^\alpha\) on [0, 1], Acta Math., 190, 2, 241-306 (2003) · Zbl 1077.41012 |
| [22] | Trefethen, L. N., Approximation Theory and Approximation Practice (2013), SIAM: SIAM Philadelphia · Zbl 1264.41001 |
| [23] | E. Wachspress, Positive definite square root of a positive definite square matrix, Unpublished, 1962. |
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.
