Введение
Математическая концепция
В линейной алгебре матрица Вандермонда, названная в честь Александра Теофила Вандермонда, представляет собой матрицу, в каждой строке которой расположены члены геометрической прогрессии: матрица размера , с элементами , являющимися j-й степенью числа , для всех индексов, начинающихся с нуля, и . Некоторые авторы определяют матрицу Вандермонда как транспонирование вышеуказанной матрицы. То есть, отображение из коэффициентов в значения многочленов является биективным линейным преобразованием с матрицей V, и задача интерполяции имеет единственное решение. Этот результат называется теоремой об однозначной определимости и является частным случаем китайской теоремы об остатках для многочленов. В статистике уравнение означает, что матрица Вандермонда является проектной матрицей полиномиальной регрессии. В численном анализе наивное решение уравнения методом Гаусса приводит к алгоритму со временной сложностью O(n³). Используя структуру матрицы Вандермонда, можно применить метод конечных разностей Ньютона (или формулу интерполяции Лагранжа) для решения уравнения за время O(n²), что также дает UL-разложение. Полученный алгоритм обеспечивает чрезвычайно точные решения, даже если матрица плохо обусловлена. Когда значения принадлежат конечному полю, определитель Вандермонда также называют определителем Мура, и он обладает свойствами, важными для теории кодов BCH и кодов коррекции ошибок Рида — Соломона. Дискретное преобразование Фурье определяется специальной матрицей Вандермонда, матрицей ДПФ, где выбраны n-е корни из единицы. Быстрое преобразование Фурье вычисляет произведение этой матрицы на вектор за время O(n log₂n). В физической теории квантового эффекта Холла определитель Вандермонда показывает, что волновая функция Лафлина с коэффициентом заполнения 1 равна определителю Слейтера. Это больше не верно для коэффициентов заполнения, отличных от 1, во фракционном квантовом эффекте Холла. В геометрии многогранников матрица Вандермонда дает нормализованный объем произвольных граней циклических политопов. В частности, если является гранью циклического политопа, соответствующей , то
In linear algebra, a Vandermonde matrix, named after Alexandre Théophile Vandermonde, is a matrix with the terms of a geometric progression in each row: an matrix
with entries , the jth power of the number , for all zero based indices and Some authors define the Vandermonde matrix as the transpose of the above matrix. That is, the map from coefficients to values of polynomials is a bijective linear mapping with matrix V, and the interpolation problem has a unique solution. This result is called the unisolvence theorem, and is a special case of the Chinese remainder theorem for polynomials. In statistics, the equation means that the Vandermonde matrix is the design matrix of polynomial regression. In numerical analysis, solving the equation naïvely by Gaussian elimination results in an algorithm with time complexity O(n3). Exploiting the structure of the Vandermonde matrix, one can use Newton's divided differences method (or the Lagrange interpolation formula) to solve the equation in O(n2) time, which also gives the UL factorization of The resulting algorithm produces extremely accurate solutions, even if is ill conditioned. When the values belong to a finite field, the Vandermonde determinant is also called the Moore determinant, and has properties which are important in the theory of BCH codes and Reed–Solomon error correction codes. The discrete Fourier transform is defined by a specific Vandermonde matrix, the DFT matrix, where the are chosen to be nth roots of unity. The Fast Fourier transform computes the product of this matrix with a vector in O(n log2n) time. In the physical theory of the quantum Hall effect, the Vandermonde determinant shows that the Laughlin wavefunction with filling factor 1 is equal to a Slater determinant. This is no longer true for filling factors different from 1 in the fractional quantum Hall effect. In the geometry of polyhedra, the Vandermonde matrix gives the normalized volume of arbitrary faces of cyclic polytopes. Specifically, if is a face of the cyclic polytope corresponding to , then
Определяющий фактор
Детерминант квадратной матрицы Вандермонда называют полиномом Вандермонда или определителем Вандермонда. Его значение — полином, который отличен от нуля тогда и только тогда, когда все различны. Определитель Вандермонда ранее иногда называли дискриминантом, но в современной терминологии дискриминант многочлена — это квадрат определителя Вандермонда его корней. Определитель Вандермонда является знакопеременной формой относительно , то есть обмен двух меняет знак, и, следовательно, зависит от порядка для . В отличие от этого, дискриминант не зависит от порядка, поэтому теория Галуа подразумевает, что дискриминант является полиномиальной функцией от коэффициентов . Формула определителя доказывается ниже тремя способами. Первый использует свойства полиномов, в особенности свойство единственной факторизации многомерных полиномов. Хотя концептуально он прост, он включает в себя неэлементарные понятия абстрактной алгебры. Второе доказательство основано на понятиях линейной алгебры, таких как изменение базиса в векторном пространстве и определитель линейного отображения. В процессе вычисляется LU-разложение матрицы Вандермонда. Третье доказательство более элементарное, но более сложное, использующее только элементарные преобразования строк и столбцов.
which is non zero if and only if all are distinct. The Vandermonde determinant was formerly sometimes called the discriminant, but in current terminology the discriminant of a polynomial is the square of the Vandermonde determinant of the roots The Vandermonde determinant is an alternating form in the , meaning that exchanging two changes the sign, and thus depends on order for the By contrast, the discriminant does not depend on any order, so that Galois theory implies that the discriminant is a polynomial function of the coefficients of
The determinant formula is proved below in three ways. The first uses polynomial properties, especially the unique factorization property of multivariate polynomials. Although conceptually simple, it involves non elementary concepts of abstract algebra. The second proof is based on the linear algebra concepts of change of basis in a vector space and the determinant of a linear map. In the process, it computes the LU decomposition of the Vandermonde matrix. The third proof is more elementary but more complicated, using only elementary row and column operations.
Ранги матрицы Вандермонде
М × n прямоугольная матрица Вандермонде, при условии m ≤ n, имеет ранг m тогда и только тогда, когда все xi различны. М × n прямоугольная матрица Вандермонде, при условии m ≥ n, имеет ранг n тогда и только тогда, когда среди xi существует n различных значений. Квадратная матрица Вандермонде обратима тогда и только тогда, когда все xi различны. Явная формула для обратной матрицы известна (см. ниже).
Инверсная матрица Вандермонде
Как объяснено выше в разделе «Приложения», задача полиномиальной интерполяции, заключающаяся в нахождении полинома, удовлетворяющего заданным условиям, эквивалентна матричному уравнению , которое имеет единственное решение . Существуют и другие известные формулы для решения задачи интерполяции, которые должны быть эквивалентны единственному решению , следовательно, они должны давать явные формулы для обратной матрицы. В частности, интерполяция Лагранжа показывает, что столбцы обратной матрицы являются коэффициентами полиномов Лагранжа, где . Это легко доказать: полиномы очевидно удовлетворяют условию для , а значит, мы можем вычислить произведение , которое является единичной матрицей.
are the coefficients of the Lagrange polynomials where This is easily demonstrated: the polynomials clearly satisfy for while , so we may compute the product , the identity matrix.
Конфлюентные матрицы Вандермонде
Как описано ранее, матрица Вандермонда описывает линейную алгебраическую задачу интерполяции, заключающуюся в нахождении коэффициентов многочлена степени *n* на основе значений *y<sub>i</sub>*, где *x<sub>i</sub>* – различные точки. Если *x<sub>i</sub>* не различны, то эта задача не имеет единственного решения (а соответствующая матрица Вандермонда является вырожденной). Однако, если мы зададим значения производных в совпадающих точках, то задача может иметь единственное решение. Например, задача
где *f(x<sub>1</sub>) = y<sub>1</sub>*, имеет единственное решение для всех *x<sub>1</sub>* при *n ≥ 1*. В общем случае, предположим, что *x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>* – (не обязательно различные) числа, и для простоты предположим, что равные значения идут подряд:
где *x<sub>i</sub>* и *x<sub>i+1</sub>* различны. Тогда соответствующая задача интерполяции имеет вид:
Соответствующая матрица для этой задачи называется конфлюэнтной матрицей Вандермонда и задается следующим образом. Если *x<sub>i</sub> = x<sub>i+1</sub>*, то *y<sub>i</sub>* и *y<sub>i+1</sub>* определены единственным образом (обозначая *f<sup>(k)</sup>(x<sub>i</sub>)*). Мы обозначим
Это обобщение матрицы Вандермонда делает ее невырожденной, так что существует единственное решение системы уравнений, и она обладает большинством других свойств матрицы Вандермонда. Ее строки являются производными (некоторого порядка) от исходных строк матрицы Вандермонда. Другой способ получить эту формулу – рассмотреть предел матрицы Вандермонда при стремлении *x<sub>i</sub>* друг к другу. Например, чтобы получить случай *n = 1*, вычтем первую строку из второй в исходной матрице Вандермонда и положим *x<sub>1</sub> = x<sub>2</sub>*: это даст соответствующую строку в конфлюэнтной матрице Вандермонда. Таким образом, обобщенная задача интерполяции с заданными значениями и производными получается как предел исходной задачи с различными точками: задание *f(x<sub>i</sub>)* близко к заданию *f<sup>(k)</sup>(x<sub>i</sub>)* при малых *Δx<sub>i</sub>*. Геометры изучали задачу отслеживания слияния точек вдоль их касательных линий, известную как компактификация конфигурационного пространства.