stringtranslate.com

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

В линейной алгебре матрица Вандермонда , названная в честь Александра-Теофиля Вандермонда , представляет собой матрицу с членами геометрической прогрессии в каждой строке: матрица

с записями - j- я степень числа для всех индексов , отсчитываемых от нуля, и . [1] Большинство авторов определяют матрицу Вандермонда как транспонированную вышеуказанную матрицу. [2] [3]

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

Это ненулевое значение тогда и только тогда, когда все различны (нет двух равных), что делает матрицу Вандермонда обратимой .

Приложения

Задача полиномиальной интерполяции состоит в том, чтобы найти полином , который удовлетворяет заданным точкам данных . Эту проблему можно переформулировать в терминах линейной алгебры с помощью матрицы Вандермонда следующим образом. вычисляет значения в точках посредством матричного умножения , где — вектор коэффициентов, а — вектор значений (оба записаны как векторы-столбцы):

Vобратимая матрицаVy[4]

.

То есть отображение коэффициентов в значения полиномов является биективным линейным отображением с матрицей V и задача интерполяции имеет единственное решение. Этот результат называется теоремой неразрешимости и является частным случаем китайской теоремы об остатках для многочленов .

В статистике это уравнение означает, что матрица Вандермонда является матрицей плана полиномиальной регрессии .

В численном анализе наивное решение уравнения методом исключения Гаусса приводит к алгоритму с временной сложностью O( n3 ). Используя структуру матрицы Вандермонда, можно использовать метод разделенных разностей Ньютона [5] (или формулу интерполяции Лагранжа [6] [7] ) для решения уравнения за время O( n 2 ), что также дает UL- факторизацию . Полученный алгоритм дает чрезвычайно точные решения, даже если он плохо обусловлен . [2] (См. полиномиальную интерполяцию .)

Определитель Вандермонда используется в теории представлений симметрической группы . [8]

Когда значения принадлежат конечному полю , определитель Вандермонда также называется определителем Мура и обладает свойствами, которые важны в теории кодов БЧХ и кодов исправления ошибок Рида – Соломона .

Дискретное преобразование Фурье определяется конкретной матрицей Вандермонда, матрицей ДПФ , где выбраны корни n- й степени из единицы . Быстрое преобразование Фурье вычисляет произведение этой матрицы на вектор за время O( n log 2 n ). [9]

В физической теории квантового эффекта Холла определитель Вандермонда показывает, что волновая функция Лафлина с коэффициентом заполнения 1 равна определителю Слейтера . Это уже не так для коэффициентов заполнения, отличных от 1 в дробном квантовом эффекте Холла .

В геометрии многогранников матрица Вандермонда дает нормированный объем произвольных -граней циклических многогранников . В частности, если -грань циклического многогранника, соответствующая , то

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

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

которое не равно нулю тогда и только тогда, когда все они различны.

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

Формула определителя доказывается ниже тремя способами. Первый использует свойства полиномов, особенно свойство уникальной факторизации многомерных полиномов . Хотя концептуально он прост, он включает в себя неэлементарные понятия абстрактной алгебры . Второе доказательство основано на понятиях линейной алгебры о смене базиса в векторном пространстве и определителе линейного отображения . При этом он вычисляет LU-разложение матрицы Вандермонда. Третье доказательство более элементарное, но и более сложное, в нем используются только элементарные операции со строками и столбцами .

Первое доказательство: полиномиальные свойства

Первое доказательство опирается на свойства многочленов.

По формуле Лейбница , является полиномом от , с целыми коэффициентами. Все записи -го столбца имеют суммарную степень . Таким образом, опять же по формуле Лейбница, все члены определителя имеют полную степень

(т. е. определитель представляет собой однородный многочлен данной степени).

Если вместо заменить на , получится матрица с двумя равными строками, которая, таким образом, имеет нулевой определитель. Таким образом, рассмотрение определителя как одномерного в факторной теореме подразумевает, что является делителем. Отсюда следует, что для всех и является делителем

Теперь это будет усилено, чтобы показать, что произведение всех этих делителей является делителем Действительно, пусть это многочлен с множителем, тогда для некоторого многочлена Если является другим множителем то становится нулевым после замены на Если множитель становится нулевым после этой замены, поскольку фактор остается отличным от нуля. Итак, по факторной теореме делит и делит

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

где – многочлен. Поскольку произведение всех и имеет одинаковую степень , полином фактически является константой. Эта константа равна единице, потому что произведение диагональных элементов равно , что также является мономом , который получается путем взятия первого члена всех множителей в . Это доказывает это и завершает доказательство.

Второе доказательство: линейные карты

Пусть F — поле , содержащее все и векторное пространство F полиномов степени меньше или равной n с коэффициентами из F . Позволять

быть линейным отображением , определяемым

.

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

Изменение базиса равносильно умножению матрицы Вандермонда на матрицу изменения базиса M (справа). Это не меняет определитель, если определитель M равен1 .

Полиномы , , , … являются моническими соответствующих степеней 0, 1, …, n . Их матрица на мономиальном базисе представляет собой верхнетреугольную матрицу U (если мономы упорядочены по возрастанию) со всеми диагональными элементами, равными единице. Таким образом, эта матрица представляет собой матрицу замены детерминанта. Матрица на этом новом базисе имеет вид

.

Таким образом, определитель Вандермонда равен определителю этой матрицы, который является произведением ее диагональных элементов.

Это доказывает желаемое равенство. Более того, можно получить LU - разложение V как .

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

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

Таким образом, вычитая из каждого столбца, кроме первого, предыдущий столбец, умноженный на , определитель не меняется. (Эти вычитания необходимо выполнять, начиная с последних столбцов, для вычитания столбца, который еще не был изменен). Это дает матрицу

Применяя формулу разложения Лапласа по первой строке, получаем , при этом

Поскольку все записи в -й строке имеют коэффициент , можно вычесть эти коэффициенты и получить

,

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

Ранг матрицы Вандермонда

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

Как объяснялось выше в разделе «Приложения», задача полиномиальной интерполяции эквивалентна матричному уравнению , имеющему единственное решение . Существуют и другие известные формулы, решающие задачу интерполяции, которые должны быть эквивалентны уникальной , поэтому они должны давать явные формулы для обратной матрицы . В частности, интерполяция Лагранжа показывает, что столбцы обратной матрицы

являются коэффициентами полиномов Лагранжа

где . Это легко продемонстрировать: полиномы явно удовлетворяют условиям while , поэтому мы можем вычислить произведение , единичную матрицу.

Сливные матрицы Вандермонда

Как описано ранее, матрица Вандермонда описывает интерполяционную задачу линейной алгебры по нахождению коэффициентов многочлена степени на основе значений , где - различные точки. Если они не различны, то эта задача не имеет единственного решения (и соответствующая матрица Вандермонда сингулярна). Однако если указать значения производных в повторяющихся точках, то задача может иметь единственное решение. Например, проблема

где , имеет единственное решение для всех с . В общем, предположим, что это числа (не обязательно разные), и для простоты предположим, что равные значения соседствуют:

где и различны. Тогда соответствующая интерполяционная задача имеет вид

Соответствующая матрица для этой задачи называется конфлюэнтной матрицей Вандермонда и задается следующим образом. Если , то для единственного (обозначающего ). Мы позволим

Это обобщение матрицы Вандермонда делает ее неособой , так что существует единственное решение системы уравнений, и она обладает большинством других свойств матрицы Вандермонда. Его строки являются производными (некоторого порядка) исходных строк Вандермонда.

Другой способ получить эту формулу — взять предел матрицы Вандермонда при приближении друг к другу. Например, чтобы получить случай , вычтите первую строку из второй в исходной матрице Вандермонда и пусть : это дает соответствующую строку в конфлюэнтной матрице Вандермонда. Это выводит обобщенную задачу интерполяции с заданными значениями и производными как предел исходного случая с различными точками: предоставление аналогично предоставлению для малых . Геометры изучили проблему отслеживания сливающихся точек вдоль их касательных линий, известную как компацитификация конфигурационного пространства .

Смотрите также

Рекомендации

  1. ^ Роджер А. Хорн и Чарльз Р. Джонсон (1991), Темы матричного анализа , Cambridge University Press. См. раздел 6.1 .
  2. ^ аб Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (2013). Матричные вычисления (4-е изд.). Издательство Университета Джонса Хопкинса. стр. 203–207. ISBN 978-1-4214-0859-0.
  3. ^ аб Мейкон, Н.; А. Шпицбарт (февраль 1958 г.). «Обратные матрицы Вандермонда». Американский математический ежемесячник . 65 (2): 95–100. дои : 10.2307/2308881. JSTOR  2308881.
  4. ^ Франсуа Вьет (1540-1603), формулы Виеты, https://en.wikipedia.org/wiki/Vandermonde_matrix/Vieta%27s_formulas
  5. ^ Бьорк, Å .; Перейра, В. (1970). «Решение систем уравнений Вандермонда». Американское математическое общество . 24 (112): 893–903. дои : 10.1090/S0025-5718-1970-0290541-1 . S2CID  122006253.
  6. ^ Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 2.8.1. Матрицы Вандермонда». Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
  7. ^ Обратная матрица Вандермонда (2018), https://proofwiki.org/wiki/Vandermonde_matrix/Inverse_of_Vandermonde_Matrix
  8. ^ Фултон, Уильям ; Харрис, Джо (1991). Теория представлений. Первый курс . Тексты для аспирантов по математике , Чтения по математике. Том. 129. Нью-Йорк: Springer-Verlag. дои : 10.1007/978-1-4612-0979-9. ISBN 978-0-387-97495-8. МР  1153249. OCLC  246650103. В лекции 4 рассматривается теория представлений симметричных групп, включая роль определителя Вандермонда .
  9. ^ Готье, Дж. «Быстрая многоточечная оценка по n произвольным точкам». Университет Саймона Фрейзера, Техн. Реп (2017).
  10. ^ Тернер, Л. Ричард (август 1966 г.). Обратная матрица Вандермонда с приложениями (PDF) .
  11. ^ «Обратная матрица Вандермонда». 2018.

дальнейшее чтение

Внешние ссылки