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.
Best Answer
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:
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$.