david/chebyshev-matrix

This problem was introduced in Ref. 1. The problem is \[\min\|p(A)\|_2\] where the minimization is over all polynomials (appropriately normalized) up to a prescribed degree. The idea was that it is an idealization of the problem \[\min\|p(A)b\|_2\] solved by GMRES for a particular \(b\).

For A normal matrix \(A\), it reduces to the classical least-deviation problem, over the set of eigenvalues of \(A\), which is a simplification of the problem studied in Ref. 3. For non-normal \(A\) it is more challenging, but still convex. It is solved numerically by semi-definite programming techniques in Ref. 2, where the important issue of basis conditioning is discussed. It is suggested that Faber polynomials may be used (other suggestions include a scaled monomial basis). Faber polynomials are explained in Ref. 4.

References:

  1. Greenbaum, Anne, and LN Trefethen. 1994. “GMRES/CR and Arnoldi/Lanczos as matrix approximation problems.” SIAM Journal on Scientific … 15(2): 359–368. http://people.maths.ox.ac.uk/trefethen/publication/PDF/1994_60.pdf (August 24, 2012).

  2. Toh, Kim-Chuan, and Lloyd N. Trefethen. 1998. “The Chebyshev Polynomials of a Matrix.” SIAM Journal on Matrix Analysis and Applications 20(2): 400. http://link.aip.org/link/SJMAEL/v20/i2/p400/s1&Agg=doi.

  3. Ketcheson, David I., and Aron J. Ahmadia. 2012. “Optimal stability polynomials for numerical integration of initial value problems.” http://arxiv.org/abs/1201.3035 (January 17, 2012).

  4. Curtiss, JH. 1971. “Faber polynomials and the Faber series.” The American Mathematical Monthly 78(6): 577–596. http://www.jstor.org/stable/10.2307/2316567 (August 24, 2012).