Русская Википедия:Определитель Вандермонда

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Определителем Вандермонда называется определитель

<math>\begin{vmatrix} 1 & x_1 & \ldots & x_1^{n-1} \\ 1 & x_2 & \ldots & x_2^{n-1} \\ \vdots & \vdots & \ddots & \vdots\\ 1 & x_n & \ldots & x_n^{n-1} \\ \end{vmatrix} \ \ = \prod\limits_{1 \leqslant i<j \leqslant n}(x_i - x_j), </math>

названный в честь французского математика Александра Теофила Вандермонда. Данная формула показывает, что определитель Вандермонда равен нулю тогда и только тогда, когда существует хотя бы одна пара <math>\left(x_i, x_j \right)</math> такая, что <math>x_i=x_j, i \neq j</math>.

Свойства

Матрица Вандермонда представляет собой частный случай альтернативной матрицы, в которой <math>f_i(\alpha)=\alpha^{i-1}</math>.

Если <math>\zeta</math> — первообразный корень <math>n</math>-й степени из единицы и <math>A=(a_{i,j})</math> — матрица Вандермонда с элементами <math>a_{i,j}=\zeta^{ij}</math>, то обратная матрица <math>B=(\tilde{a}_{i,j})</math> с точностью до диагональной матрицы имеет вид <math>\tilde{a}_{i,j}=\zeta^{-ij}</math>: <math>AB=n\cdot E</math>.

Применение

Определитель Вандермонда имеет многочисленные применения в разных областях математики. Например, при решении задачи интерполяции многочленами, то есть задачи о нахождении многочлена степени <math>n-1</math>, график которого проходит через <math>n</math> заданных точек плоскости с абсциссами <math>x_1, \ldots, x_{n}</math>, определитель Вандермонда возникает как определитель системы линейных уравнений, из которой находятся неизвестные коэффициенты искомого многочлена.

Быстрое умножение вектора на матрицу Вандермонда

Быстрое умножение вектора <math>(a_0,\dots,a_n)^t</math> на матрицу Вандермонда эквивалентно нахождению <math>n</math> значений <math>x_i</math> многочлена <math>f(x)=a_0 + a_1x + \ldots + a_nx^n</math> и может быть вычислено за <math>O(\log(n)\cdot M(n))</math> операций, где <math>M(n)</math> — затраты на умножения двух полиномов. Метод быстрого нахождения <math>n</math> значений многочлена строится на том факте, что <math>f(x_i) \equiv a_0 + a_1x + \ldots + a_nx^n \pmod{x-x_i}</math>. Используя алгоритм быстрого умножения многочленов (а также его модификацию операцию взятия по модулю многочлена), такой как Метод умножения Шёнхаге — Штрассена, применив парадигму разделяй и властвуй, за <math>O(\log(n))</math> умножений многочленов (и операций по модулю многочленов) строится дерево, листьями которого будут многочлены (значения) <math>f(x)\,\bmod\,(x-x_i)</math>, а корнем дерева будет многочлен <math>f(x)\,\bmod\,{(x-x_1)(x-x_2)\cdots (x-x_n)}</math>.

Литература

• Курош А. Г. Курс высшей алгебры. — М.: Наука 1968.
• Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Наука — Физматлит, 1999.
• Шафаревич И. Р., Ремизов А. О. Линейная алгебра и геометрия, — Физматлит, Москва, 2009.