Is there any guarantee that Parks-Mcclellan eventually stop? If so, is there any formula that shows number of maximum interations that ensure that the algorithm stops?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You have to distinguish between the algorithm and a specific implementation. The Parks McClellan algorithm is based on the Remez exchange algorithm, which is guaranteed to converge. So in principle any correct implementation of the algorithm should converge. However, convergence of the algorithm is only guaranteed if all intermediate results are computed with infinite precision, which is not the case in a practical implementation. Some design specifications can result in numerically ill-conditioned problems that will prevent correct convergence of the algorithm.
In short, yes, the algorithm is guaranteed to converge. However, in some cases, numerical problems can prevent convergence to the optimal solution. But even in the usual case of convergence, the number of necessary iterations cannot be determined beforehand.
$\begingroup$
$\endgroup$
There is a theorem from Tang that proves the Remez algorithm, of which Parks-McClellan is a variant, to be quadratically convergent.
The paper doesn't give an explicit number of iterations for convergence, though it does give some sample numbers of sweeps.
Ping Tak Peter Tang, "A Fast Algorithm for Linear Complex Chebyshev Approximations," Mathematics of Computation, Vol. 51, No. 184 (Oct., 1988), pp. 721-739 Published by: American Mathematical Society, Stable URL: https://www.jstor.org/stable/2008772, Accessed: 31-12-2018 17:38 UTC
