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

Матрица Вандермонда — это квадратная матрица специального вида, строки или столбцы которой содержат последовательные степени некоторого набора чисел. Названа в честь французского математика Александра Теофила Вандермонда (1735–1796), хотя исторически её свойства были известны и ранее. Матрица Вандермонда играет ключевую роль в задачах интерполяции, теории кодирования, численном анализе и алгебре.

Определение

Пусть даны числа \(x_1, x_2, \dots, x_n\) (обычно попарно различные). Матрица Вандермонда \(V\) размера \(n \times n\) определяется как:

\[ V = \begin{pmatrix} 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 & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1} \end{pmatrix} \]

Элемент на пересечении \(i\)-й строки и \(j\)-го столбца равен \(x_i^{j-1}\) (при нумерации строк и столбцов с единицы). В некоторых вариантах матрица транспонируется, то есть степени располагаются по строкам, а не по столбцам, но структура остаётся аналогичной.

Свойства

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

Определитель матрицы Вандермонда (также называемый вандермондианом) вычисляется по формуле:

\[ \det(V) = \prod_{1 \le i < j \le n} (x_j - x_i) \]

Это произведение всех разностей между элементами набора \(x_1, \dots, x_n\) в порядке возрастания индексов. Отсюда следует, что матрица Вандермонда является невырожденной (обратимой) тогда и только тогда, когда все числа \(x_i\) попарно различны. Если среди них есть совпадающие, определитель обращается в нуль.

Ранг

Ранг матрицы Вандермонда равен числу различных значений среди \(x_1, \dots, x_n\). Если все числа различны, ранг максимален и равен \(n\).

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

Обратная матрица к матрице Вандермонда может быть выражена через интерполяционные многочлены Лагранжа. В общем случае её элементы вычисляются с помощью симметрических многочленов от \(x_i\). Для численных расчётов часто используют алгоритмы, основанные на быстром преобразовании Фурье (БПФ) при специальном выборе узлов (например, корни из единицы).

Применение

Интерполяция многочленов

Матрица Вандермонда возникает при решении задачи интерполяции: найти многочлен степени не выше \(n-1\), проходящий через заданные точки \((x_i, y_i)\). Система линейных уравнений для коэффициентов многочлена имеет вид:

\[ V \cdot \mathbf{a} = \mathbf{y} \]

где \(\mathbf{a}\) — вектор коэффициентов, \(\mathbf{y}\) — вектор значений. Решение этой системы даёт коэффициенты интерполяционного многочлена. Однако на практике из-за плохой обусловленности матрицы (особенно при большом \(n\) и неравномерных узлах) прямое решение через матрицу Вандермонда используется редко; предпочтительнее методы Лагранжа или Ньютона.

Теория кодирования

В кодах Рида — Соломона матрица Вандермонда применяется для построения порождающих матриц. Эти коды используются в системах хранения данных (например, RAID 6), спутниковой связи и цифровом телевидении. Свойства матрицы позволяют эффективно исправлять ошибки и восстанавливать утерянные данные.

Быстрое преобразование Фурье

Дискретное преобразование Фурье (ДПФ) является частным случаем матрицы Вандермонда, где \(x_i\) — корни \(n\)-й степени из единицы. В этом случае матрица принимает вид:

\[ F_{jk} = \omega^{(j-1)(k-1)}, \quad \omega = e^{-2\pi i / n} \]

Такая матрица унитарна (с точностью до нормировки) и позволяет выполнять преобразование за \(O(n \log n)\) операций с помощью алгоритма БПФ.

Численный анализ

Матрицы Вандермонда используются в задачах аппроксимации функций, численного дифференцирования и интегрирования. Например, при построении квадратурных формул Гаусса узлы и веса вычисляются через корни ортогональных многочленов, что связано с матрицами Вандермонда.

Обобщения

Матрица Вандермонда с весами

Обобщённая матрица Вандермонда включает весовые коэффициенты \(w_i\):

\[ V_{ij} = w_i x_i^{j-1} \]

Такие матрицы возникают в задачах взвешенной интерполяции и аппроксимации.

Матрица Коши — Вандермонда

Комбинация матриц Коши и Вандермонда используется в теории рациональных интерполяций и в некоторых моделях кодирования.

Блочная матрица Вандермонда

Применяется в многомерной интерполяции и в задачах, где узлы заданы в виде векторов.

Вычислительные аспекты

Матрица Вандермонда часто является плохо обусловленной при больших \(n\) и неравномерном расположении узлов. Число обусловленности растёт экспоненциально с размером матрицы, что делает прямое решение систем с ней неустойчивым. Для преодоления этого используются:

• Метод Ньютона с разделёнными разностями.
• Быстрое преобразование Фурье для равномерных узлов.
• Сингулярное разложение (SVD) для регуляризации.

Пример

Для набора чисел \(x = [1, 2, 3]\) матрица Вандермонда размера \(3 \times 3\) имеет вид:

\[ V = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{pmatrix} \]

Её определитель: \(\det(V) = (2-1)(3-1)(3-2) = 1 \cdot 2 \cdot 1 = 2\).

Интересные факты

• Александр Вандермонд был одним из первых математиков, систематически изучавших определители, хотя сама матрица была известна ещё в работах Гаусса и Лагранжа.
• Матрица Вандермонда используется в криптографии, в частности, в схемах разделения секрета (например, схема Шамира).
• В теории графов матрица Вандермонда возникает при изучении спектров графов и их собственных значений.

Источники

• Гантмахер Ф. Р. Теория матриц. — М.: Наука, 1967.
• Хорн Р., Джонсон Ч. Матричный анализ. — М.: Мир, 1989.
• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином, 2008.
• Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. — М.: Наука, 1984.