# Condition number for polynomial interpolation matrix

We want to interpolate a function $\,f:\mathbb{R}\to\mathbb{R}$ on the interval $[0,1]$ with, say, monomials. Assume we have set $\left\{x_i\right\}_{i=0}^{n}$ of $n+1$ points $x_i\in\left[0,1\right],\; i = 0,\dots, n,$ which are not uniformly distributed and for which we know values $\,f_i = f\left(x_i\right)$ of function $\,f$.

Following standard interpolation techniques, we write approximating polynomial $P_n(x)$ as linear combination of monomials:

$$P_n\left(x\right) = a_0 + a_1 x + a_2 x^2 + \dots + a_nx^n = \sum_{i=0}^{n} a_ix^i$$

where $a_i\in \mathbb R,\; i=0,\dots,n$ are unknown coefficients we need to determine. Estimating monomials at points $\left\{x_i\right\}_{i=0}^{n}$ yields system of linear equations

$$\underbrace{ \begin{bmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^n \\ 1 & x_2 & x_2^2 & \cdots & x_2^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^n \\ \end{bmatrix}}_{\quad\;\style{display: inline-block; transform-origin: 50% 50% 0px; transform: rotate(30deg); }{:= \boldsymbol{M}} } \cdot \underbrace{ \begin{bmatrix}a_0 \\ a_1 \\ \vdots \\ a_n\end{bmatrix} }_ {\quad\style{display: inline-block; transform-origin: 50% 50% 0px; transform: rotate(30deg); }{:= \overline{\boldsymbol{a}}} } = \underbrace{\begin{bmatrix}f_0 \\ f_1 \\ \vdots \\ f_n\end{bmatrix} }_ {\quad\style{display: inline-block; transform-origin: 50% 50% 0px; transform: rotate(30deg); }{:= \overline{\boldsymbol{f}}} } %\qquad \iff \qquad %\boldsymbol{M} \cdot\overline{\boldsymbol{a}} = \overline{\boldsymbol{f}}$$

which we can rewrite as $\;\boldsymbol{M} \cdot\overline{\boldsymbol{a}} = \overline{\boldsymbol{f}}$.

I am trying to figure out how does condition number $\,\kappa\left(\boldsymbol{M}\right)$ of the matrix depends on the minimal distance $h$ between points $\left\{ x_i \right\}_{i=0}^{n}$:

$$h=\min_{i,j=0\ldots n} \left\lVert x_i - x_j\right\rVert.$$

Intuitively $\kappa\left(\boldsymbol{M}\right)$ should grow as $h\to0$, which matches results of numerical experiments. However, I am clueless about the exact type of relation between $\kappa$ and $h$. Any help is appreciated.

Surely you cannot obtain any useful upper bound from $h$. If you translate all data points $x_i$ by the same amount $t$, then $h$ remains unchanged but the matrix becomes closer and closer to singular when $t\to\infty$.

For lower bounds, if you google "vandermonde matrix condition number", there are a handful of results that seem relevant. E.g., the first result, How Bad are Vandermonde Matrices by Victor Pan (2015, arXiv:1504.02118) looks quite interesting. To quote the author:

Our results … indicate that the condition number of an $n\times n$ Vandermonde matrix is exponential in $n$ unless its knots are more or less equally spaced on or about the unit circle $C(0,1)$.

He has derived several lower bounds for the condition number. You may see if they are useful or if you can relate them to your $h$.

• The example with Vandermonde Matrix is only one special case of polynomial interpolation. Are there similar results for other systems of polynomials, in particular for orthonormal bases?