×

Numerical experiments on the accuracy of the Chebyshev-Frobenius companion matrix method for finding the zeros of a truncated series of Chebyshev polynomials. (English) Zbl 1118.65032

Summary: For a function \(f(x)\) that is smooth on the interval \(x\in[a,b]\) but otherwise arbitrary, the real-valued roots on the interval can always be found by the following two-part procedure. First, expand \(f(x)\) as a Chebyshev polynomial series on the interval and truncate for sufficiently large \(N\). Second, find the zeros of the truncated Chebyshev series. The roots of an arbitrary polynomial of degree \(N\), when written in the form of a truncated Chebyshev series, are the eigenvalues of an \(N\times N\) matrix whose elements are simple, explicit functions of the coefficients of the Chebyshev series. This matrix is a generalization of the Frobenius companion matrix.
We show by experimenting with random polynomials, Wilkinson’s notoriously ill-conditioned polynomial, and polynomials with high-order roots that the Chebyshev companion matrix method is remarkably accurate for finding zeros on the target interval, yielding roots close to full machine precision. We also show that it is easy and cheap to apply Newton’s iteration directly to the Chebyshev series so as to refine the roots to full machine precision, using the companion matrix eigenvalues as the starting point.
Lastly, we derive a couple of theorems. The first shows that simple roots are stable under small perturbations of magnitude \(\varepsilon\) to a Chebyshev coefficient: the shift in the root \(x_*\) is bounded by \(\varepsilon/ df/dx(x_*)+O (\varepsilon^2)\) for sufficiently small \(\varepsilon\). Second, we show that polynomials with definite parity (only even or only odd powers of \(x)\) can be solved by a companion matrix whose size is one less than the number of nonzero coefficients, a vast cost-saving.

MSC:

65H05 Numerical computation of solutions to single equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
26C10 Real polynomials: location of zeros

Software:

Chebfun
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnett, S., Companion matrix analog for orthogonal polynomials, Linear Algebra Appl., 12, 197-208 (1975) · Zbl 0327.15026
[2] Battles, Z.; Trefethen, L. N., An extension of Matlab to continuous functions and operators, SIAM J. Sci. Comput., 25, 1743-1770 (2004) · Zbl 1057.65003
[3] Bender, C. M.; Orszag, S. A., Advanced Mathematical Methods for Scientists and Engineers (1978), McGraw-Hill: McGraw-Hill New York, 594pp · Zbl 0417.34001
[4] Booth, A. D., Numerical Methods (1955), Butterworths Scientific Publications: Butterworths Scientific Publications London · Zbl 0077.32203
[5] Boyd, J. P., A Chebyshev polynomial interval-searching method (Lanczos economization) for solving a nonlinear equation with application to the nonlinear eigenvalue problem, J. Comput. Phys., 118, 1-8 (1995) · Zbl 0823.65047
[6] Boyd, J. P., Chebyshev and Fourier Spectral Methods (2001), Dover: Dover Mineola, New York, 665pp · Zbl 0987.65122
[7] Boyd, J. P., Computing zeros on a real interval through Chebyshev expansion and polynomial rootfinding, SIAM J. Numer. Anal., 40, 1666-1682 (2002) · Zbl 1034.65028
[8] J.P. Boyd, A review of high-order methods for incompressible fluid flow by M.O. Deville, P.F. Fischer and E.H. Mund, SIAM Rev. 46 (2004) 151-157.; J.P. Boyd, A review of high-order methods for incompressible fluid flow by M.O. Deville, P.F. Fischer and E.H. Mund, SIAM Rev. 46 (2004) 151-157.
[9] Boyd, J. P., Computing real roots of a polynomial in Chebyshev series form through subdivision, Appl. Numer. Math., 56, 1077-1091 (2006) · Zbl 1119.65033
[10] Boyd, J. P., Computing real roots of a polynomial in Chebyshev series form through subdivision with linear testing and cubic solves, Appl. Math. Comput., 174, 1642-1648 (2006) · Zbl 1090.65052
[11] Clenshaw, C. W.; Curtis, A. R., A method for numerical integration on an automatic computer, Numer. Math., 2, 197-205 (1960) · Zbl 0093.14006
[12] Conway, J. B., Functions of One Complex Variable (1973), Springer: Springer New York · Zbl 0277.30001
[13] Day, D. M.; Romero, L., Roots of polynomials expressed in terms of orthogonal polynomials, SIAM J. Numer. Anal., 43, 1969-1987 (2005) · Zbl 1101.65048
[14] Gol’berg, E. M.; Malozemov, V. N., Estimates for the zeros of certain polynomials, Vestmol Leningrad Univ. Math., 6, 127-135 (1979), Translated from Vestnik Leningrad Univ. Mat. Mekh. Astronom. 7 (1973) 18-24 · Zbl 0418.26009
[15] Specht, W., Die Lage der Nullstellen eines Polynoms III, Math. Nachr., 16, 369-389 (1957) · Zbl 0078.01103
[16] Specht, W., Die Lage der Nullstellen eines Polynoms IV, Math. Nachr., 21, 201-222 (1960) · Zbl 0092.25701
[17] Stetter, H. J., Numerical Polynomial Algebra (2004), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 1058.65054
[18] Szegö, G., Orthogonal Polynomials (1959), American Mathematical Society: American Mathematical Society New York · JFM 65.0278.03
[19] Trefethen, L. N.; Bau, D., Numerical Linear Algebra (1997), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 0874.65013
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.