$\DeclareMathOperator*{\argmin}{arg\,min}$ The Chebyshev polynomials $$T_n(x) := \cosh(n \, \cosh^{-1}(x))$$ (with potentially complex $\cosh^{-1}(x)$) are well known to satisfy $$ \frac{T_n\left(\tfrac{x - m}{b-a}\right)}{\left|T_n\left(\tfrac{- m}{b-a}\right)\right|} = \argmin_{p \in \mathcal{P}_n, \, p(0) = 1} \, \, \max_{x \in [a,b]} |p(x)|, \qquad a,b > 0, \, m := \tfrac{a+b}{2}. $$ Are there any results for the problem $$ \min_{p \in \mathcal{P}_n, \, p(0) = 1} \, \, \max_{x \in [-d,-c] \cup [a,b]} |p(x)|, \qquad a,b,c,d >0, $$ i.e. if we want to minimise the polynomial on two intervals on both sides of the origin?

The background to this question is that I want to estimate the rate of convergence of GMRES applied to a matrix with eigenvalues clustered in two intervals as described above.

  • $\begingroup$ About Chebyshev polynomials, I don't understand why you use $\cosh$ instead of $\cos$. $\endgroup$ – Jean Marie Aug 13 '16 at 13:01
  • $\begingroup$ I think that Legendre polynomials could have such a property. $\endgroup$ – Jean Marie Aug 13 '16 at 13:02
  • $\begingroup$ It doesn't really matter whether I use $\cos$ or $\cosh$. The two definitions only differ by a factor $i$. $\endgroup$ – gTcV Aug 13 '16 at 13:08

In case anyone is still looking for the solution, a special case where the two intervals have equal width is given on p53 of Greenbaum's book on Iterative Methods.

Here the polynomial is normalized to have value 1 at the origin.

enter image description here

A more general treatment is given in Sections 3.3 and 3.4 of "Polynomial Based Iteration Methods for Symmetric Linear Systems" by Fischer.


This is not an answer "per se" but a (double) hint, each one with a graphics.

1) First, a graphical representation of the modulus of the 30th Legendre Polynomial $P_{30}(x)$.

One can see that the big fluctuations are at the bounds of interval $[-1,1]$

This kind of polynomial seems to fit to your desire...

But, as regards a minimax property, I dont know if there is one...

enter image description here

2) In second, here is another family of polynomials (see graphics below) which might be of larger interest for you. They are almost not known outside the electronics community (with which I have had the opportunity to work at some time). They are conceived in order to be very smooth (stability) with a very sharp ascent (neat "cutting frequencies"). They are derived from the Legendre polynomials by different operations (change of variables, squaring, integration,...). The mode of generation is rather well described in the file called "Notes on "L" Optimal filters by C. Bond (2011)" that can be accessed through (https://en.wikipedia.org/wiki/Optimum_%22L%22_filter).

The polynomial associated with the figure (found in the final list given in the said document) is

$$P(x)=10x^4 - 120x^6 + 615 x^8 - 1624x^{10} + 2310x^{12} - 1680 x^{14} + 490x^{16}$$

Remark 1: With a degree 16, about half of the other, one achieves much better properties...

Remark 2: Thes polynomials are positive: no need to take their modulus (I know this is a "real values" concern, and not a "complex values" concern...)

enter image description here

  • $\begingroup$ I don't see how your hints help. I want a polynomial which is "large" (i.e. 1) in the centre, and small (i.e. much smaller than 1) on some intervals to the left and right. $\endgroup$ – gTcV Aug 13 '16 at 21:49
  • $\begingroup$ Taking $1-P(x)$ wouldn't work ? $\endgroup$ – Jean Marie Aug 14 '16 at 4:40
  • $\begingroup$ No. The point is that the desired function should have a bump in the centre. Both of your proposals are rather "flat" (in some suitable sense) in the centre. $\endgroup$ – gTcV Aug 14 '16 at 10:20
  • $\begingroup$ Allright, I had not catched this constraint. Sorry for having given you bad solutions... $\endgroup$ – Jean Marie Aug 14 '16 at 11:11
  • $\begingroup$ That's no problem at all. Thanks for your efforts anyway! $\endgroup$ – gTcV Aug 14 '16 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.