Русская Википедия:Определитель Вандермонда
Определителем Вандермонда называется определитель
- <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>
названный в честь французского математика Александра Теофила Вандермонда[1]. Данная формула показывает, что определитель Вандермонда равен нулю тогда и только тогда, когда существует хотя бы одна пара <math>\left(x_i, x_j \right)</math> такая, что <math>x_i=x_j, i \neq j</math>[2].
Доказательство
Свойства
Матрица Вандермонда представляет собой частный случай альтернативной матрицы, в которой <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>, определитель Вандермонда возникает как определитель системы линейных уравнений, из которой находятся неизвестные коэффициенты искомого многочлена.[3]
Быстрое умножение вектора на матрицу Вандермонда
Быстрое умножение вектора <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> — затраты на умножения двух полиномов.[4] Метод быстрого нахождения <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>.[5]
Примечания
Литература
- Курош А. Г. Курс высшей алгебры. — М.: Наука 1968.
- Ильин В. А., Позняк Э. Г. Линейная алгебра. — М.: Наука — Физматлит, 1999.
- Шафаревич И. Р., Ремизов А. О. Линейная алгебра и геометрия, — Физматлит, Москва, 2009.
- ↑ Alexandre-Théophile Vandermonde Шаблон:WaybackШаблон:Ref-rus.
- ↑ Шаблон:Книга
- ↑ Шафаревич И. Р., Ремизов А. О. Линейная алгебра и геометрия, гл. II, пар. 4, — Физматлит, Москва, 2009.
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web