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$.

  • $\begingroup$ 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? $\endgroup$ – Vlad Apr 3 '17 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.