Condition numbers of various bases
Nick Trefethen, September 2010
(Chebfun example linalg/CondNos.m)
Chebfun can compute the condition number of a set of functions on an interval. That's a condition number for continuous functions, not discrete approximations.
For example, here we take the first 12 Chebyshev polynomials on [-1,1]:
tic N = 11; A = chebpoly(0:N); plot(A) fprintf('Condition no. for Chebyshev polynomials: %8.3f\n',cond(A))
Condition no. for Chebyshev polynomials: 4.006
Legendre polynomials are not much different:
A = legpoly(0:N); plot(A) fprintf('Condition no. for Legendre polynomials: %8.3f\n',cond(A))
Condition no. for Legendre polynomials: 4.796
Here are the Legendre polynomials normalized by having unit norm rather than by taking the value 1 at x=1. Since the functions are orthonormal, the condition number is 1.
A = legpoly(0:N,'norm'); plot(A) fprintf('Condition no. for normalized Legendre polynomials: %8.3f\n',cond(A))
Condition no. for normalized Legendre polynomials: 1.000
All of these condition numbers are fine for numerical work. Monomials, by contrast, are exponentially ill-conditioned:
x = chebfun('x'); A = [1 x]; for j = 2:N A = [A x.^j]; end plot(A) fprintf('Condition no. for monomials: %8.3f\n',cond(A))
Condition no. for monomials: 7244.534
These experiments take a surprisingly long time, which is why we've looked at sets of only twelve functions:
fprintf('Total time: %5.2f (too long!)\n', toc)
Total time: 4.61 (too long!)
Unfortunately Chebfun's QR command, though very robust due to the use of continuous Householder reflectors , is slow.
Now what exactly do these condition numbers mean? Here is an explanation following Chapter 4 of . A is a "quasimatrix", a matrix with 12 "columns" that are not vectors but functions of the variable x on [-1,1]. This quasimatrix represents a mapping from the space R12 of vectors of dimension 12 into the 12-dimensional subspace of degree 11 polynomials in L2([-1,1]), the infinite-dimensional space of square-integrable functions defined on [-1,1]. Now suppose we consider the unit ball in R12, that is, the set of all 12-vectors whose 2-norm is <1. The quasimatrix A maps this ball into an 12-dimensional hyperellipsoid, a kind of 12-dimensional pancake. The condition number cond(A) is equal to the ratio of the largest dimension of the pancake to the smallest. When the columns of A are monomials, the pancake is very flat indeed.
 L. N. Trefethen, Householder triangularization of a quasimatrix, IMA Journal of Numerical Analysis 30 (2010), 887-897.
 L. N. Trefethen and D. Bau, III, Numerical Linear Algebra, SIAM, 1997.