A MULTIPLE-EXCHANGE ALGORITHM FOR COMPLEX CHEBYSHEV APPROXIMATION BY POLYNOMIALS ON THE UNIT CIRCLE

摘要

This paper presents a generalization of the Remez multiple-exchange (ME) algorithm for solving complex Chebyshev approximation by polynomials on the unit circle. The difficulties of implementing the two fundamental steps of the Remez algorithm in the complex case are pointed out and methods for overcoming these difficulties are proposed. It is shown that generalization of the first step, which involves solving a complex Chebyshev approximation subproblem over a set of guessed extremal points, can be implemented by solving a maximization problem with simple bound constraints using Newton's method. Furthermore, generalization of the second step, which involves finding a new set of guessed extremal points, can be realized by use of an effective exchange rule derived from the concept of extremal signatures. Numerical results suggest that the proposed ME algorithm has fast convergence rate and good numerical properties even for large-scale problems. [References: 19]