A Chebyshev Polynomial Interval-Searching Method ("Lanczos Economization") for Solving a Nonlinear Equation with Application to the Nonlinear Eigenvalue Problem
✍ Scribed by John P. Boyd
- Publisher
- Elsevier Science
- Year
- 1995
- Tongue
- English
- Weight
- 362 KB
- Volume
- 118
- Category
- Article
- ISSN
- 0021-9991
No coin nor oath required. For personal study only.
✦ Synopsis
To search a given real interval for roots, our algorithm is to replace (f(\lambda)) by (f_{N}(\lambda)), its (N)-term Chebyshev expansion on the search interval (\lambda \in\left[\lambda_{\min }, \lambda_{\max }\right]), and compute the roots of this proxy. This strategy is efficient if and only if (f(\lambda)) itself is expensive to evaluation, such as when (f(\lambda)) is the determinant of a large matrix whose elements depend nonlinearly on (\lambda). For such expensive functions, it is much cheaper to search for zeros of (f_{N}(\lambda)), which can be evaluated in (O(N)) operations, than to iterate or look for sign changes on a fine grid with (f(\lambda)) itself. It is possible to systematically increase (N) until the Chebyshev series converges acceptably fast, without wasting previously computed values of (f(\lambda)), by imitating the Clenshaw-Curtis quadrature. Our strategy of replacing (f(\lambda)) by (f_{N}(\lambda)) is similar to Lanczos economization of power series, which also replaces an expensive function by a Chebyshev approximation that is more rapidly evaluated. The errors induced by the Chebyshev approximation can be eliminated by a final step of one or two iterations with (f(\lambda)) itself, using the zeros of (f_{N}(\lambda)) as initial guesses. We show through numerical examples that the algorithm works well. The only sour note is that it is sometimes necessary to split the search interval into subintervals, each with a separate Chebyshev expansion, when (f(\lambda)) varies by many orders of magnitude on the search interval. 1995 Academic Press, Inc.