Norm of inverse confluent Vandermonde matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T02:05:04Z http://mathoverflow.net/feeds/question/114972 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114972/norm-of-inverse-confluent-vandermonde-matrix Norm of inverse confluent Vandermonde matrix dima 2012-11-30T12:25:07Z 2012-12-03T11:56:02Z <p>Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as $$V= \begin{bmatrix} v_{1,0}&amp;v_{2,0}&amp;\dots&amp;v_{n,0}\\ v_{1,1}&amp;v_{2,1}&amp;\dots&amp;v_{n,1}\\ \vdots\\ v_{1,N-1}&amp;v_{2,N-1}&amp;\dots&amp;v_{n,N-1} \end{bmatrix}$$ where $v_{j,k}=\begin{bmatrix}x_j^k,&amp;kx_j^{k-1},&amp;\dots&amp;k(k-1)\times\dots\times (k-l_j+1) x_j^{k-l_j+1}\end{bmatrix}$. Let $\|\cdot\|$ denote the row sum matrix norm. In some applications (e.g. interpolation, signal processing) one would like to estimate the quantity $\|V^{-1}\|$.</p> <p>Gautschi [1] has shown that for $l_1=\dots=l_n=2$ one has $$\|V^{-1}\| \leq \max_{1\leq \lambda\leq n} \beta_{\lambda} \prod_{\nu=1,\nu\neq\lambda}^n \biggl(\frac{1+|x_{\lambda}|}{|x_{\nu}-x_{\lambda}|}\biggr)^2$$ where $\beta_{\lambda}=\max\biggl(1+|x_{\lambda}|,1+2(1+|x_{\lambda}|)\sum_{\nu\neq\lambda}{1\over |x_\nu-x_\lambda|}\biggr)$.</p> <p>I am interested in a somewhat cruder estimates, as follows: if $|x_j|\leq 1$ and $|x_i-x_j|\geq \delta$, then for the above case we have $$\|V^{-1}\| \leq C n 2^N\delta^{-N+1}\qquad (*)$$ for some absolute constant $C$.</p> <p><strong>Is it true that something like $(*)$ holds for the general configuration $\{l_1,\dots,l_n\}$?</strong></p> <p>EDIT: using [2], this seems to boil down to the following. Let $$h_j(x)=\prod_{i \neq j}(x-x_i)^{-l_i}.$$ <strong>For $t=0,1,\dots,l_j$ evaluate $h_j^{(t)}(x_j).$</strong></p> <p>[1] W.Gautschi, "On Inverses of Vandermonde and Confluent Vandermonde matrices II", Numerische Mathematik 5, 425-430, 1963.</p> <p>[2] R.Schapelle, "The Inverse of the Confluent Vandermonde Matrix", IEEE Trans. on Automatic Control, October 1972, pp.724-725.</p> http://mathoverflow.net/questions/114972/norm-of-inverse-confluent-vandermonde-matrix/115094#115094 Answer by dima for Norm of inverse confluent Vandermonde matrix dima 2012-12-01T17:55:31Z 2012-12-01T17:55:31Z <p>For $j=1,\dots,n$ and $k=0,1,\dots,l_j-1$ denote by $u_{j,k}$ the row with index $l_1+\dots +l_{j-1}+k$ of the matrix $V^{-1}$. By using a generalization of the Hermite interpolation formula (see [3]), in [2] it is shown that the elements of $u_{j,k}$ are the coefficients of the polynomial $${1\over k!} \sum_{t=0}^{l_j-1-k} {1\over t!} h_j^{(t)}(x_j) (x-x_j)^{k+t} \prod_{i\neq j} (x-x_i)^{l_i}$$</p> <p>Now thanks to the answer to <a href="http://math.stackexchange.com/q/248537/32051" rel="nofollow">this MSE question</a>, one has $$|h_j^{(t)}(x_j)|\leq N(N+1)\cdots (N+t-1)\delta^{-N-t}.$$</p> <p>The sum of absolute values of the coefficients of the polynomials $(x-x_j)^{k+t} \prod_{i\neq j} (x-x_i)^{l_i}$ is at most (see [4, Lemma]) $$(1+|x_j|)^{k+t} \prod_{i\neq j}(1+|x_i|)^{l_i} \leq 2^{N-(l_j-k-t)}.$$</p> <p>So now $$\|u_{j,k}\| \leq {1\over k!}\sum_{t=0}^{l_j-1-k} {1\over t!} {N(N+1)\cdots (N+t-1) \over {\delta^{N+t}}}2^{N-l_j+k+t}\\ \leq \biggl({2\over \delta}\biggr)^N {1\over {2^{l_j-k}k!}}\sum_{t=0}^{l_j-1-k} {l_j-1-k \choose t} {N(N+1)\cdots(N+t-1)\over (l_j-k-t)\cdots(l_j-k-2)(l_j-k-1)} \biggl({2\over \delta}\biggr)^t\\ \leq \biggl({2\over \delta}\biggr)^N {1\over {2^{l_j-k}k!}} \biggl(1+{2N\over \delta}\biggr)^{l_j-1-k}\\ =\biggl({2\over \delta}\biggr)^N {2\over k!} \biggl({1\over 2}+{N\over\delta}\biggr)^{l_j-1-k}.$$</p> <p>[3] A.Spitzbart, "A Generalization of Hermite's Interpolation Formula", The American Mathematical Monthly, Vol.67 No.1, p.42-46, 1960.</p> <p>[4] W.Gautschi, "On Inverses of Vandermonde and Confluent Vandermonde matrices", Numerische Mathematik 4, p.117-123, 1962.</p>