УказательРазделыОбозначенияАвторО проекте


§

Вспомогательный раздел к разделам МАТРИЦА и ИНТЕРПОЛЯЦИЯ.


Матрица и определитель Вандермонда

Пусть задан набор чисел (элементов поля) \{x_1,x_2,\dots,x_n \}, не обязательно различных. Матрицу вида

\mathbf V_{m,n}(x_1, x_2,\ldots,x_n) = \left( \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{m-1}& x_2^{m-1}& \ldots& x_n^{m-1} \end{array} \right)_{m\times n}

или ей транспонированную будем называть (m,n)-матрицей Вандермонда.

Частным случаем квадратной матрицы Вандермонда является матрица дискретного преобразования Фурье:

F=\left[ \varepsilon_j^{k} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_1 & \varepsilon_1^2 & \dots & \varepsilon_1^{n-1} \\ 1 & \varepsilon_2 & \varepsilon_2^2 & \dots & \varepsilon_2^{n-1} \\ 1 & \varepsilon_3 & \varepsilon_3^2 & \dots & \varepsilon_3^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{n-1} & \varepsilon_{n-1}^{2} & \dots & \varepsilon_{n-1}^{n-1} \end{array} \right)_{n\times n} \quad npu \quad \varepsilon_j = \cos \frac{2 \pi j}{n} + {\mathbf i} \, \sin \frac{2 \pi j}{n}

корне n-й степени из 1. Основываясь на свойстве \varepsilon_j=\varepsilon_1^j, матрицу часто записывают в эквивалентном виде

F= \left[ \varepsilon^{jk} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon & \varepsilon^2 & \dots & \varepsilon^{n-1} \\ 1 & \varepsilon^2 & \varepsilon^4 & \dots & \varepsilon^{2(n-1)} \\ 1 & \varepsilon^3 & \varepsilon^6 & \dots & \varepsilon^{3(n-1)} \\ \vdots & & & & \vdots \\ 1 & \varepsilon^{n-1} & \varepsilon^{2(n-1)} & \dots & \varepsilon^{(n-1)^2} \end{array} \right)_{n\times n} \quad npu \quad \varepsilon = \cos \frac{2 \pi}{n} + {\mathbf i} \, \sin \frac{2 \pi}{n} \ .

Определитель

Определитель квадратной (n,n)-матрицы Вандермонда называется определителем Вандермонда. При n=1 он, очевидно, равен 1. При n>1 будем обозначать его V(x_1,\dots,x_n):

V(x_1,\dots,x_n)= \left| \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{n-1}& x_2^{n-1}& \ldots& x_n^{n-1} \end{array} \right|= \left| \begin{array}{llll} 1& x_1& \ldots& x_1^{n-1}\\ 1& x_2& \ldots& x_2^{n-1}\\ \vdots& \vdots& & \vdots \\ 1 & x_n& \ldots & x_n^{n-1} \end{array} \right| \, .

Очевидно, этот определитель является полиномом от переменных x_1,\dots,x_n:

V(x_1,x_2)=x_2-x_1,\ V(x_1,x_2,x_3)= x_1^2x_3-x_1x_3^2+x_1x_2^2-x_1^2x_2+x_2x_3^2-x_2^2x_3, \dots ,

причем полиномом однородным степени n(n-1)/2 и с целыми коэффициентами. Этот полином оказывается приводимым над \mathbb Z.

T

Теорема. Имеет место тождество

V(x_1,\dots,x_n) \equiv \prod_{1\le j < k \le n} (x_k-x_j)\ .

Доказательство ЗДЕСЬ.

=>

Определитель Вандермонда порядка n\ge 2 отличен от нуля тогда и только тогда, когда все числа x_1,x_2,\dots,x_n различны.

П

Пример.

V(x_1,x_2,x_3)\equiv (x_2-x_1)(x_3-x_1)(x_3-x_2) \ ;
V(x_1,x_2,x_3,x_4) \equiv
\equiv (x_2-x_1)(x_3-x_1)(x_3-x_2)(x_4-x_1)(x_4-x_2)(x_4-x_3) \ .

=>

Определитель матрицы дискретного преобразования Фурье вычисляется по формулам:

\det F = n^{n/2} {\mathbf i}^{n(n-1)/2+1} при n_{} — четном,

\det F = n^{n/2} {\mathbf i}^{n(n-1)/2} при n_{} — нечетном.

Доказательство ЗДЕСЬ.

Интерполяция

Матрица Вандермонда естественным образом возникает в задаче полиномиальной интерполяции.

Задача. Построить полином y_{}=f(x), принимающий значения согласно следующей таблице:

\begin{array}{c|ccccc} x & x_1 & x_2 & \dots & x_n \\ \hline y & y_1 & y_2 &\dots & y_n \end{array}

Здесь числа \{ x_{j}, y_{j} \}_{j=1}^n — из \mathbb Q_{}, \mathbb R_{} или \mathbb C_{}, или вообще элементы произвольного поля, которое в дальнейшем будем обозначать через \mathbb A_{}. \{ x_{j} \}_{j=1}^n называются узлами интерполяции; искомый полином называется интерполяционным.

Т

Теорема. При x_{1},\dots,x_{n} различных существует единственный полином f(x) \in \mathbb A_{}[x] степени \le n_{}-1 такой, что f(x_{1})=y_{1},\dots,f(x_{n})=y_{n}.

Доказательство. Коэффициенты полинома f(x)=A_{0}+A_1x+\dots+A_{n-1}x^{n-1} можно определить из системы уравнений

\left\{\begin{array}{ccl} A_0+A_1x_1+\dots+A_{n-1}x_1^{n-1}&=&y_1 \\ A_0+A_1x_2+\dots+A_{n-1}x_2^{n-1}&=&y_2 \\ \dots & & \dots \\ A_0+A_1x_n+\dots+A_{n-1}x_n^{n-1}&=&y_n, \end{array} \right.

матрица которой как раз и является матрицей Вандермонда. По теореме из предыдущего пункта ее определитель отличен от нуля. На основании теоремы Крамера система имеет единственное решение.

Фактическое нахождение коэффициентов интерполяционного полинома посредством решения системы линейных уравнений по формулам Крамера достаточно громоздко. «Сходу» удается получить только выражения для A_0 и A_{n-1}.

П

Пример. Для n=4 имеем

A_0=\frac{\left| \begin{array}{clll} y_1 & x_1 & x_1^2 & x_1^3 \\ y_2 & x_2 & x_2^2 & x_2^3 \\ y_3 & x_3 & x_3^2 & x_3^3 \\ y_4 & x_4 & x_4^2 & x_4^3 \end{array} \right|}{V(x_1,x_2,x_3,x_4)}=

раскладываем определитель по первому столбцу:

=\frac{y_1x_2x_3x_4V(x_2,x_3,x_4)-y_2x_1x_3x_4 V(x_1,x_3,x_4)+y_3x_1x_2x_4V(x_1,x_2,x_4)-y_4x_1x_2x_3V(x_1,x_2,x_3)}{V(x_1,x_2,x_3,x_4)}=
=\frac{y_1x_2x_3x_4}{(x_1-x_2)(x_1-x_3)(x_1-x_4)}+\frac{y_2x_1x_3x_4}{(x_2-x_1)(x_2-x_3)(x_2-x_4)}+\frac{y_3x_1x_2x_4}{(x_3-x_1)(x_3-x_2)(x_3-x_4)} +\frac{y_4x_1x_2x_3}{(x_4-x_1)(x_4-x_2)(x_4-x_3)} \, .
A_4=\frac{\left| \begin{array}{clll} 1 & x_1 & x_1^2 & y_1 \\ 1 & x_2 & x_2^2 & y_2 \\ 1 & x_3 & x_3^2 & y_3 \\ 1 & x_4 & x_4^2 & y_4 \end{array} \right|}{V(x_1,x_2,x_3,x_4)}=

раскладываем определитель по последнему столбцу:

=\frac{y_1}{(x_1-x_2)(x_1-x_3)(x_1-x_4)}+\frac{y_2}{(x_2-x_1)(x_2-x_3)(x_2-x_4)}+\frac{y_3}{(x_3-x_1)(x_3-x_2)(x_3-x_4)} +\frac{y_4}{(x_4-x_1)(x_4-x_2)(x_4-x_3)} \, .

Однако, с помощью некоторых вспомогательных манипуляций удается свести вычисление интерполяционного полинома к определителю Вандермонда. С этой целью воспользуемся результатом упражнения 7 ЗДЕСЬ. Если f(x)=A_{0}+A_1x+\dots+A_{n-1}x^{n-1} при столбце коэффициентов, удовлетворяющем уравнению

\mathbf V \left[\begin{array}{l} A_0 \\ A_1 \\ \vdots \\ A_{n-1} \end{array} \right] = \left[\begin{array}{l} y_1 \\ y_2 \\ \vdots \\ y_{n} \end{array} \right] \, ,

то

f(x) \equiv \left| \begin{array}{llrrrc} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} & -y_1 \\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1} & -y_2 \\ \vdots & \vdots & & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} & -y_n \\ 1 & x & x^2 & \dots & x^{n-1} & 0 \end{array} \right| \Big/ \left| \begin{array}{lrrrr} 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1} \\ \vdots & \vdots & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} \end{array} \right| \equiv

Теперь разложим определитель из числителя по последнему столбцу

\equiv (-1)^{n-1} y_1\frac{V(x_2,\dots,x_n,{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)}+(-1)^{n-2}y_2\frac{V(x_1,x_3,\dots,x_n,{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)}+\dots+ y_n\frac{V(x_1,x_2,\dots,x_{n-1},{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)} \equiv

и переставим строки в определителях числителей

\equiv y_1\frac{V({\color{RubineRed} x},x_2,\dots,x_n)}{V(x_1,x_2,\dots,x_n)}+y_2\frac{V(x_1,{\color{RubineRed} x},\dots,x_n)}{V(x_1,x_2,\dots,x_n)}+\dots+ y_n\frac{V(x_1,x_2,\dots,x_{n-1},{\color{RubineRed} x})}{V(x_1,x_2,\dots,x_n)} \, .

Теперь воспользуемся теоремой предыдущего пункта и сократим общие множители числителей и знаменателей. Обозначим

W(x) = (x-x_1)\times \dots \times (x-x_n) \, ,
W_j(x) = \frac{W(x)}{x-x_j} =(x-x_1)\times \dots \times (x-x_{j-1}) (x-x_{j+1})\times \dots \times (x-x_n) \quad npu \quad j\in \{1,\dots,n\} .

Тогда получаем представление интерполяционного полинома в виде:

f(x) \equiv \sum_{j=1}^n \frac{y_jW_j(x)}{W_j(x_j)}=
\begin{array}{ll} = & \displaystyle y_1\frac{(x-x_2)\times \dots \times (x-x_n)}{(x_1-x_2)\times \dots \times (x_1-x_n)}+ \\ + & \displaystyle y_2\frac{(x-x_1)(x-x_3)\times \dots \times (x-x_n)}{(x_2-x_1)(x_2-x_3)\times \dots \times (x_2-x_n)}+ \\ + & \dots+ \\ + & \displaystyle y_n\frac{(x-x_1)\times \dots \times (x-x_{n-1})}{(x_n-x_1)\times \dots \times (x_n-x_{n-1})} . \end{array}

Это представление известно как интерполяционный полином в форме Лагранжа. Легко выводимое равенство

W_j(x_j)=W^{\prime}(x_j)

позволяет записать ту же форму в эквивалентном виде

f(x) \equiv \sum_{j=1}^n \frac{y_jW_j(x)}{W^{\prime}(x_j)} \, .

Полиномы

\widetilde W_j(x) = W_j(x)/W_j(x_j) \equiv W_j(x)/W^{\prime}(x_j) \quad npu \quad j \in \{1,\dots,n\} \, ,

участвующие в этом представлении, часто называют базисными интерполяционными полиномами. Они обладает следующим свойством:

\widetilde W_j(x_k) = \delta_{jk} \ ,

где \delta_{jk}символ Кронекера. Иными словами, \widetilde W_j(x) является интерполяционным полиномом для таблицы

\begin{array}{c|ccccc} x & x_1 & x_2 & \dots & x_{j-1} & x_j & x_{j+1} & \dots & x_n \\ \hline y & 0 & 0 & \dots & 0 & 1 & 0 & \dots & 0 \end{array}

Обратная матрица

Представление интерполяционного полинома в форме Лагранжа еще не дает явных формул для коэффициентов. Для этого еще нужно разложить базисные полиномы по степеням x_{}. Если это сделать:

{\widetilde W}_j(x)\equiv w_{j0}+w_{j1}x+\dots+ w_{j,n-1}x^{n-1} \, ,

то мы получим возможность обращения матрицы Вандермонда.

Т

Теорема. При условии различности всех x_1,x_2,\dots,x_n имеет место равенство

\left( \begin{array}{llll} 1& 1& \ldots& 1\\ x_1& x_2& \ldots& x_n\\ x_1^2& x_2^2& \ldots& x_n^2\\ \vdots& \vdots& & \vdots \\ x_1^{n-1}& x_2^{n-1}& \ldots& x_n^{n-1} \end{array} \right)^{-1}= \left( \begin{array}{llll} w_{10}& w_{11}& \ldots& w_{1,n-1}\\ w_{20}& w_{21}& \ldots& w_{2,n-1}\\ \dots & & & \dots \\ w_{n0}& w_{n1}& \ldots& w_{n,n-1}\\ \end{array} \right) \, .

Доказательство может быть произведено разными способами. Самый простой заключается в формальной проверке утверждения умножением матрицы \left[ w_{jk} \right]_{j=1,\dots,n,k=0,\dots,n-1} на матрицу Вандермонда слева. В результате получаем

\left(\begin{array}{llll} \widetilde W_1(x_1) & \widetilde W_1(x_2) & \dots & \widetilde W_1(x_n) \\ \widetilde W_2(x_1) & \widetilde W_2(x_2) & \dots & \widetilde W_2(x_n) \\ \dots & & & \dots \\ \widetilde W_n(x_1) & \widetilde W_n(x_2) & \dots & \widetilde W_n(x_n) \end{array} \right)

и эта матрица является единичной на основании свойства базисных интерполяционных полиномов.

§

Первоисточник этой теоремы мне не известен. Имеется в книге [1].

П

Пример. Вычислить

\left(\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9 \end{array} \right)^{-1} \, .

Решение. Имеем:

W(x)=(x-1)(x-2)(x-3) \ ,
\widetilde W_1(x)=\frac{(x-2)(x-3)}{(1-2)(1-3)} = 3 -\frac{2}{5}x+\frac{1}{2}x^2,\ \widetilde W_2(x)=\frac{(x-1)(x-3)}{(2-1)(2-3)} = -3 +4\,x-x^2,\ \widetilde W_3(x)=\frac{(x-1)(x-2)}{(3-1)(3-2)} = 1 -\frac{3}{2}x+\frac{1}{2}x^2 \, .

Ответ.

\left(\begin{array}{ccc} 3 & -5/2 & 1/2 \\ -3 & 4 & -1 \\ 1 & -3/2 & 1/2 \end{array} \right) \, .
?

Доказать, что сумма всех строк матрицы \mathbf V^{-1} равна [1,0,0,\dots,0].

Следующая задача — организовать параллелизацию вычисления коэффициентов базисных интерполяционных полиномов. С этой целью вычислим величины

\xi_1=\frac{1}{W^{\prime}(\lambda_1)},\dots, \xi_n=\frac{1}{W^{\prime}(\lambda_n)} \, .

и составим из них столбец

\Xi_0=\left[\xi_1,\dots, \xi_n\right]^{\top} \, .

Умножим его на столбец

\Lambda=\left[\lambda_1,\dots, \lambda_n\right]^{\top} \ ,

причем умножение векторов рассматривается адамарово, т.е. поэлементное

\Xi_1= \Xi_0 \otimes \Lambda= \left[\xi_1 \lambda_1 ,\dots, \xi_n \lambda_n \right]^{\top} \ .

Продолжив процесс умножения, сгененируем последовательность

\Xi_0, \Xi_1=\Xi_0 \otimes \Lambda, \Xi_2=\Xi_1 \otimes \Lambda, \dots, \Xi_{n-1}=\Xi_{n-2} \otimes \Lambda, \dots, \Xi_{2n-2} = \Xi_{2n-3} \otimes \Lambda \ .

На основании равенств Эйлера-Лагранжа сумма элементов любого из столбцов \Xi_0,\dots,\Xi_{n-2} равна 0_{}, а сумма элементов столбца \Xi_{n-1} равна 1.

Т

Теорема[2]. Вычислим суммы элементов столбцов \Xi_n, \Xi_{n+1},\dots, \Xi_{2n-2}, т.е. величины

\sigma_k = \sum_{j=1}^n \frac{\lambda_j^{n+k-1}}{W^{\prime}(\lambda_j)} , \quad k\in \{1,\dots,n-1\} \ .

Столбцы матрицы

\mathbf V^{-1}=\left[\mathbf V_{[1]}^{-1},\mathbf V_{[2]}^{-1},\dots, \mathbf V_{[n]}^{-1} \right]

связаны со столбцами \Xi_0, \Xi_{1},\dots, \Xi_{n-1} следующими рекурсивными соотношениями:

\left\{ \begin{array}{lcl} \mathbf V_{[n]}^{-1}&=&\Xi_0, \\ \mathbf V_{[n-1]}^{-1}&=&\Xi_1-\sigma_1 \mathbf V_{[n]}^{-1}, \\ \mathbf V_{[n-2]}^{-1}&=&\Xi_2-\sigma_1 \mathbf V_{[n-1]}^{-1} - \sigma_2 \mathbf V_{[n]}^{-1}, \\ \dots & & \dots \\ \mathbf V_{[1]}^{-1}&=&\Xi_{n-1}-\sigma_1 \mathbf V_{[2]}^{-1} - \sigma_2 V_{[3]}^{-1}- \dots - \sigma_{n-1} \mathbf V_{[n]}^{-1}. \end{array} \right.

Доказательство. На основании равенств Эйлера-Лагранжа имеем

\mathbf V\cdot \mathbf V_{[n]}^{-1}=\mathbf V\cdot \Xi_0=\left[\sum_{j=1}^n\frac{ 1}{W^{\prime}(\lambda_j)},\ \sum_{j=1}^n\frac{ \lambda_j}{W^{\prime}(\lambda_j)},\dots, \sum_{j=1}^n\frac{ \lambda_j^{n-1}}{W^{\prime}(\lambda_j)} \right]^{\top}= [0,0,\dots,0,1]^{\top} \, .

Далее, на основании только что выведенного равенства, получаем:

\mathbf V\cdot \mathbf V_{[n-1]}^{-1}=V\cdot \Xi_1-\sigma_1 \mathbf V \cdot \mathbf V_{[n]}^{-1} = [0,0,\dots,1,\sigma_1]^{\top} - \sigma_1 [0,0,\dots,0,1]^{\top} = [0,0,\dots,1,0]^{\top} \, .

Применением теперь уже двух полученных равенств, доказываем третье равенство из теоремы:

\mathbf V\cdot \mathbf V_{[n-2]}^{-1}=V\cdot \Xi_2-\sigma_1 \mathbf V \cdot \mathbf V_{[n-1]}^{-1} - \sigma_2 \mathbf V \cdot \mathbf V_{[n]}^{-1} =
=[0,0,\dots,1,\sigma_1,\sigma_2]^{\top} - \sigma_1 [0,0,\dots,1,0]^{\top} - \sigma_2 [0,0,\dots,0,1]^{\top} = [0,0,\dots,1,0,0]^{\top} \, .

И так далее.

§

Для вещественных матриц Вандермонда, формулы из теоремы можно рассматривать как процесс ортогонализации Грама-Шмидта, примененный к системе столбцов \{\Xi_0,\Xi_1,\dots,\Xi_{n-1}\} \subset \mathbb R^n при скалярном произведении в пространстве столбцов \mathbb R^n заданном равенством

\langle X,Y \rangle =X^{\top} (\mathbf V^{\top} \mathbf V) Y \quad npu \quad \forall \{X,Y\} \subset \mathbb R^n \, .

§

Подробности о величинах \sigma_k см. НИЖЕ.

П

Пример. Для приведенного выше примера

\mathbf V=\left(\begin{array}{ccc} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 4 & 9 \end{array} \right)

имеем

\lambda_1=1,\ \lambda_2=2,\ \lambda_3=3,\ W^{\prime}(1)=2,\ W^{\prime}(2)=-1,\ W^{\prime}(3)=2 \, .

Запишем последовательность столбцов \Xi_0, \Xi_{1},\Xi_{2},\Xi_{3}, \Xi_{4} в виде матрицы

\left[ \begin{array}{rrrrr} 1/2 & 1/2 & 1/2 & 1/2 & 1/2 \\ -1 & -2 & -4 & -8 & -16 \\ 1/2 & 3/2 & 9/2 & 27/2 & 81/2 \end{array} \right] \ .

Суммируем элементы двух последних столбцов:

\sigma_1=6, \ \sigma_2=25

и применяем теорему:

\begin{array}{lll} V_{[3]}^{-1}&=& \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right], \ \\ V_{[2]}^{-1}&=& \left[ \begin{array}{r} 1/2 \\ -2 \\ 3/2 \end{array} \right]- 6 \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right]= \left[ \begin{array}{r} -5/2 \\ 4 \\ -3/2 \end{array} \right], \\ V_{[1]}^{-1}&=& \left[ \begin{array}{rrrrr} 1/2 \\ -4 \\ 9/2 \end{array} \right] - 6\, \left[ \begin{array}{r} -5/2 \\ 4 \\ -3/2 \end{array} \right]-25\, \left[ \begin{array}{r} 1/2 \\ -1 \\ 1/2 \end{array} \right]= \left[ \begin{array}{r} 3\\ -3 \\ 1 \end{array} \right] \ . \end{array}

Т

Теорема. Матрица обратная к матрице дискретного преобразования Фурье вычисляется по формуле:

F^{-1}=\frac{1}{n}\left[ \varepsilon_{-j}^{k} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_{-1} & \varepsilon_{-1}^2 & \dots & \varepsilon_{-1}^{n-1} \\ 1 & \varepsilon_{-2} & \varepsilon_{-2}^2 & \dots & \varepsilon_{-2}^{n-1} \\ 1 & \varepsilon_{-3} & \varepsilon_{-3}^2 & \dots & \varepsilon_{-3}^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{-(n-1)} & \varepsilon_{-(n-1)}^{2} & \dots & \varepsilon_{-(n-1)}^{n-1} \end{array} \right) \quad npu \quad \varepsilon_{-j} = \cos \frac{2 \pi j}{n} - {\mathbf i} \, \sin \frac{2 \pi j}{n}

Основываясь на свойстве \varepsilon_{-j}=\varepsilon_{-1}^j=\overline{\varepsilon_1}^j (см. ЗДЕСЬ ), матрицу часто записывают в эквивалентном виде

F= \frac{1}{n}\left[ \overline{\varepsilon}^{jk} \right]_{j,k=0}^{n-1}=\frac{1}{n} \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \overline{\varepsilon} & \overline{\varepsilon}^2 & \dots & \overline{\varepsilon}^{n-1} \\ 1 & \overline{\varepsilon}^2 & \overline{\varepsilon}^4 & \dots & \overline{\varepsilon}^{2(n-1)} \\ 1 & \overline{\varepsilon}^3 & \overline{\varepsilon}^6 & \dots & \overline{\varepsilon}^{3(n-1)} \\ \vdots & & & & \vdots \\ 1 & \overline{\varepsilon}^{n-1} & \overline{\varepsilon}^{2(n-1)} & \dots & \overline{\varepsilon}^{(n-1)^2} \end{array} \right) \quad npu \quad \overline{\varepsilon} = \cos \frac{2 \pi}{n} - {\mathbf i} \, \sin \frac{2 \pi}{n} \ .

§

Образно говоря: обращение матрицы F_{} сводится к сопряжению каждого ее элемента и делению его на порядок матрицы.

Доказательство ЗДЕСЬ.

Обобщенная матрица Вандермонда

§

Материалы настоящего пункта взяты из [3].

Естественным обобщением матрицы Вандермонда является матрица1)

\widehat \mathbf V=\left( \begin{array}{cccc} x_1^{n_1} & x_1^{n_2} & \dots & x_1^{n_m} \\ x_2^{n_1} & x_2^{n_2} & \dots & x_2^{n_m} \\ \vdots & & & \vdots \\ x_m^{n_1} & x_m^{n_2} & \dots & x_m^{n_m} \end{array} \right) \quad npu \ \{n_1, n_2, \dots, n_m \} \subset \mathbb N \cup \{ 0 \} .

Ее определитель будем обозначать \widehat V.

По аналогии с ПУНКТОМ, обозначим

W(x)=\prod_{j=1}^m (x-x_j) \, .

Вычислим выражения

\sigma_k(x_1,\dots,x_m) = \sum_{j=1}^{m} \frac{x_j^{m+k-1}}{W^{\prime}(x_j)} \quad для \ k \in \{-(m-1),-(m-2),\dots,-1,0, 1,2, \dots \} \, .
§

В прочно забытой литературе XIX века (Якоби, Вронский, Костка и др.) эти функции назывались алеффункции2) и обозначались \aleph_k (x_1,\dots,x_m). Несмотря на их рациональный вид, они, на самом деле, являются полиномами.

Т

Теорема 1. Имеют место равенства:

\sigma_0 \equiv 1; \ \sigma_k \equiv 0 \quad npu \ k \in \{-1,-2,\dots,-(m-1)\} \, .

При k>0 выражение \sigma_k представляет собой симметрический полином от x_1,\dots,x_m, равный сумме всевозможных мономов степени k:

\sigma_k=\sum_{j_1+\dots+j_m=k}x_1^{j_1}\times \vdots \times x_m^{j_m} \, .

Равенства

\sum_{j=1}^m \frac{x_j^k}{W'(x_j)}=\left\{ \begin{array}{cc} 0 & npu \ k< m-1; \\ 1 & npu \ k= m-1. \end{array} \right.

известны как равенства Эйлера-Лагранжа; доказательство ЗДЕСЬ.

П

Пример. Для m=4:

\sigma_3=x_1^3+x_2^3+x_3^3+x_4^3+x_3^2x_2+x_3^2x_1+x_4x_3^2+x_3x_4^2+x_2^2x_3+x_1^2x_3
+x_2^2x_1+x_1^2x_2+x_1x_4^2+x_2^2x_4+x_2x_4^2+x_1^2x_4+x_3x_1x_2+x_1x_4x_3+x_2x_4x_3+x_1x_2x_4

Т

Теорема 2. Имеют место равенства

\sigma_k=\left| \begin{array}{cccc} 1 & 1 & \dots & 1 \\ x_1 & x_2 & \dots & x_m\\ \vdots & & & \vdots \\ x_1^{m-1} & x_2^{m-1} & \dots & x_m^{m-1}\\ x_1^{k+m-1} & x_2^{k+m-1} & \dots & x_m^{k+m-1} \end{array} \right| /\prod_{1\le \ell<j \le m} (x_j-x_{\ell}) \quad при \ k=1,2,\dots

Т

Теорема 3. Имеет место формула Crocchi, связывающая величины \sigma_k с суммами Ньютона s_k=x_1^k+x_2^k+\dots+x_m^k полинома W(x):

\sigma_{k-1} s_1+\sigma_{k-2} s_2+\dots+\sigma_{1} s_{k-1} + s_k = k \sigma_k \, .

Т

Теорема 4. Имеет место равенство

\widehat V=\left| \begin{array}{cccc} \sigma_{n_1} & \sigma_{n_1-1} & \dots & \sigma_{n_1-m} \\ \sigma_{n_2} & \sigma_{n_2-1} & \dots & \sigma_{n_2-m} \\ \vdots & & & \vdots \\ \sigma_{n_m} & \sigma_{n_m-1} & \dots & \sigma_{n_m-m} \end{array} \right| \prod_{1\le \ell <j \le m} (x_j-x_{\ell})

Ввиду равенств Эйлера-Лагранжа можно ожидать, что матрица в правой части этой формулы имеет достаточное количество нулевых элементов.

П

Пример.

\left| \begin{array}{cccc} x_1^{1} & x_1^{2} & x_1^4 & x_1^{6} \\ x_2^{1} & x_2^{2} & x_2^4 & x_2^{6} \\ x_3^{1} & x_3^{2} & x_3^4 & x_3^{6} \\ x_4^{1} & x_4^{2} & x_4^4 & x_4^{6} \end{array} \right|= \left| \begin{array}{cccc} 0 & 0 & \sigma_1 & \sigma_3 \\ 0 & 1 & \sigma_2 & \sigma_4 \\ 1 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right| \prod_{1\le \ell < j \le 4} (x_j-x_{\ell}) \, .

Для доказательства справедливости формулы выполним умножение матриц

\left( \begin{array}{cccc} 1/W^{\prime} (x_1) & 1/W^{\prime} (x_2) & 1/W^{\prime} (x_3) & 1/W^{\prime} (x_4) \\ x_1/W^{\prime} (x_1) & x_2/W^{\prime} (x_2) & x_3/W^{\prime} (x_3) & x_4/W^{\prime} (x_4) \\ x_1^2/W^{\prime} (x_1) & x_2^2/W^{\prime} (x_2) & x_3^2/W^{\prime} (x_3) & x_4^2/W^{\prime} (x_4) \\ x_1^3/W^{\prime} (x_1) & x_2^3/W^{\prime} (x_2) & x_3^3/W^{\prime} (x_3) & x_4^3/W^{\prime} (x_4) \end{array} \right) \left( \begin{array}{cccc} x_1^{1} & x_1^{2} & x_1^4 & x_1^{6} \\ x_2^{1} & x_2^{2} & x_2^4 & x_2^{6} \\ x_3^{1} & x_3^{2} & x_3^4 & x_3^{6} \\ x_4^{1} & x_4^{2} & x_4^4 & x_4^{6} \end{array} \right)

и, на основании равенств Эйлера-Лагранжа, имеем:

= \left( \begin{array}{cccc} \sigma_{-2} & \sigma_{-1} & \sigma_1 & \sigma_3 \\ \sigma_{-1} & \sigma_0 & \sigma_2 & \sigma_4 \\ \sigma_0 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right)= \left( \begin{array}{cccc} 0 & 0 & \sigma_1 & \sigma_3 \\ 0 & 1 & \sigma_2 & \sigma_4 \\ 1 & \sigma_1 & \sigma_3 & \sigma_5 \\ \sigma_1 & \sigma_2 & \sigma_4 & \sigma_6 \end{array} \right) \, .

Переходим в равенстве к определителям:

\left| \begin{array}{cccc} 1/W^{\prime} (x_1) & 1/W^{\prime} (x_2) & 1/W^{\prime} (x_3) & 1/W^{\prime} (x_4) \\ x_1/W^{\prime} (x_1) & x_2/W^{\prime} (x_2) & x_3/W^{\prime} (x_3) & x_4/W^{\prime} (x_4) \\ x_1^2/W^{\prime} (x_1) & x_2^2/W^{\prime} (x_2) & x_3^2/W^{\prime} (x_3) & x_4^2/W^{\prime} (x_4) \\ x_1^3/W^{\prime} (x_1) & x_2^3/W^{\prime} (x_2) & x_3^3/W^{\prime} (x_3) & x_4^3/W^{\prime} (x_4) \end{array} \right|=\frac{1}{\prod_{j=1}^4 W^{\prime} (x_j)} \left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_1 & x_2 & x_3 & x_4 \\ x_1^2 & x_2^2 & x_3^2 & x_4^2 \\ x_1^3 & x_2^3 & x_3^3 & x_4^3 \end{array} \right|=
=\frac{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})}{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})^2}=\frac{1}{\displaystyle \prod_{1\le \ell <j \le m} (x_j-x_{\ell})} \, .

В достаточно широком классе случаев можно гарантировать невырожденность обобщенной матрицы Вандермонда.

Т

Теорема 5 [5]. Если 0 \le n_1< n_2 < \dots < n_m и 0 < x_1< \dots < x_m, то

\widehat V > 0 \, .

Задачи

Источники

[1]. Кнут Д. Искусство программирования. Т.1., изд. Вильямс, 2002.

[2]. Маров А.В., Утешев А.Ю. Матричный формализм кодов Рида-Соломона Вестник СПбГУ. Серия 10. 2016. Вып. 4. 4-17.

[3]. Encyklopädie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen. Bd. I. Arithmetik und Algebra. Редактор — Meyer W.F. 1898-1904. Leipzig, Teubner

[4]. Проскуряков И.В. Сборник задач по линейной алгебре. М.Наука. 1974

[5]. Полиа Г., Сеге Г.Задачи и теоремы из анализа.Т. 2. М.Наука. 1972, с. 54

1) Будем рассматривать только случай квадратной матрицы.
2) Alephfunktionen (нем.)

2019/11/10 10:57 редактировал au