A Vandermonde matrix is defined in terms of scalars , , …, by
The are called points or nodes. Note that while we have indexed the nodes from , they are usually indexed from in papers concerned with algorithms for solving Vandermonde systems.
Vandermonde matrices arise in polynomial interpolation. Suppose we wish to find a polynomial of degree at most that interpolates to the data , that is, , . These equations are equivalent to
where is the vector of coefficients. This is known as the dual problem. We know from polynomial interpolation theory that there is a unique interpolant if the are distinct, so this is the condition for to be nonsingular.
is called the primal problem, and it arises when we determine the weights for a quadrature rule: given moments find weights such that , .
The determinant of is a function of the points . If for some then has identical th and th columns, so is singular. Hence the determinant must have a factor . Consequently, we have
where, since both sides have degree in the , is a constant. But contains a term (from the main diagonal), so . Hence
This formula confirms that is nonsingular precisely when the are distinct.
Now assume that is nonsingular and let . Equating elements in the th row of gives
where is the Kronecker delta (equal to if and otherwise). These equations say that the polynomial takes the value at and at , . It is not hard to see that this polynomial is the Lagrange basis polynomial:
We deduce that
where denotes the sum of all distinct products of of the arguments (that is, is the th elementary symmetric function).
From (1) and (3) we see that if the are real and positive and arranged in increasing order and has a checkerboard sign pattern: the element has sign .
Note that summing (2) over gives
where the second equality follows from the fact that is a degree polynomial that takes the value at the distinct points . Hence
so the elements in the th column of the inverse sum to for and for .
To illustrate the formulas above, here is an example, with and :
for which .
Vandermonde matrices are notorious for being ill conditioned. The ill conditioning stems from the monomials being a poor basis for the polynomials on the real line. For arbitrary distinct points , Gautschi showed that satisfies
with equality on the right when for all with a fixed (in particular, when for all ). Note that the upper and lower bounds differ by at most a factor . It is also known that for any set of real points ,
and that for we have , where the lower bound is an extremely fast growing function of the dimension!
These exponential lower bounds are alarming, but they do not necessarily rule out the use of Vandermonde matrices in practice. One of the reasons is that there are specialized algorithms for solving Vandermonde systems whose accuracy is not dependent on the condition number , and which in some cases can be proved to be highly accurate. The first such algorithm is an operation algorithm for solving of Björck and Pereyra (1970). There is now a long list of generalizations of this algorithm in various directions, including for confluent Vandermonde-like matrices (Higham, 1990), as well as for more specialized problems (Demmel and Koev, 2005) and more general ones (Bella et al., 2009). Another important observation is that the exponential lower bounds are for real nodes. For complex nodes can be much better conditioned. Indeed when the are the roots of unity, is the unitary Fourier matrix and so is perfectly conditioned.
Two ways in which Vandermonde matrices have been generalized are by allowing confluency of the points and by replacing the monomials by other polynomials. Confluency arises when the are not distinct. If we assume that equal are contiguous then a confluent Vandermonde matrix is obtained by “differentiating” the previous column for each of the repeated points. For example, with points we obtain
The transpose of a confluent Vandermonde matrix arises in Hermite interpolation; it is nonsingular if the points corresponding to the “nonconfluent columns” are distinct (that is, if in the case of (4)).
A Vandermonde-like matrix is defined in terms of a set of polynomials with having degree :
Of most interest are polynomials that satisfy a three-term recurrence, in particular, orthogonal polynomials. Such matrices can be much better conditioned than general Vandermonde matrices.
Algorithms for solving confluent Vandermonde-like systems and their rounding error analysis are described in the chapter “Vandermonde systems” of Higham (2002).
Gautschi has written many papers on the conditioning of Vandermonde matrices, beginning in 1962. We mention just his most recent paper on this topic: Gautschi (2011).
This is a minimal set of references, which contain further useful references within.
- T. Bella, Y. Eidelman. I. Gohberg. I. Koltracht, and V. Olshevsky, A Fast Björck–Pereyra-Type Algorithm for Solving Hessenberg-Quasiseparable-Vandermonde Systems, SIAM J. Matrix Anal. Appl. 31(2), 790–815, 2009.
- James W. Demmel and Plamen Koev, The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System, SIAM J. Matrix Anal. Appl. 2791, 142–152, 2005.
- Walter Gautschi, Optimally Scaled and Optimally Conditioned Vandermonde and Vandermonde-like matrices, BIT 51, 103–125, 2011.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002.
- Nicholas J. Higham, Stability Analysis of Algorithms for Solving Confluent Vandermonde-like Systems, SIAM J. Matrix Anal. Appl. 11, 23–41, 1990.