В математике ( линейная алгебра ) алгоритм Фаддеева – Леверье представляет собой рекурсивный метод вычисления коэффициентов характеристического полинома квадратной матрицы , А , названный в честь Дмитрия Константиновича Фаддеева и Леверье . Расчет этого полинома дает собственные значения из А , как его корни; как матричный полином от самой матрицы A , он обращается в нуль по фундаментальной теореме Кэли – Гамильтона . Вычисление определителя из определения характеристического полинома, однако, является громоздким с точки зрения вычислений, поскольку является новой символьной величиной, тогда как этот алгоритм работает напрямую с коэффициентами матрицы .
Алгоритм был независимо открыт несколько раз в той или иной форме. Впервые он был опубликован в 1840 году Урбеном Леверье , впоследствии переработан П. Хорстом, Жан-Мари Сурьо , в его нынешнем виде здесь - Фаддеевым и Соминским, а затем Дж. С. Фреймом и другими. [1] [2] [3] [4] [5] (Исторические моменты см. В статье Хаусхолдера. [6] Изящный путь к доказательству, минуя многочлены Ньютона , был введен Хоу. [7] Основная часть презентации) здесь следует Гантмахер, стр. 88. [8] )
Алгоритм
Цель состоит в том, чтобы вычислить коэффициенты c k характеристического полинома матрицы A размера n × n ,
где, по- видимому, с п = 1 и с 0 = (-1) п Det .
Коэффициенты определяются рекурсивно сверху вниз с помощью вспомогательных матриц M ,
Таким образом,
Заметьте, что A −1 = - M n / c 0 = (−1) n −1 M n / det A завершает рекурсию на λ . Это может быть использовано для получения обратного или определителя А .
Вывод
Доказательство опирается на модах матрицы adjugate , В к ≡ М н-к , вспомогательные матрицы встречаются. Эта матрица определяется как
и, таким образом, пропорционален резольвенте
Очевидно, это матричный полином от λ степени n - 1 . Таким образом,
где можно определить безобидное M 0 ≡0.
Подставляя явные полиномиальные формы в определяющее уравнение для сопряженного элемента, приведенное выше,
Теперь, в высшем порядке, первое слагаемое обращается в нуль при M 0 = 0; тогда как в нижнем порядке (константа по λ , из определяющего уравнения сопутствующего элемента, приведенного выше),
так что сдвиг фиктивных индексов первого члена дает
что, таким образом, диктует рекурсию
для m = 1, ..., n . Обратите внимание , что индекс восходящий составляет по убыванию по степеням Х , но полиномиальные коэффициенты с которые еще предстоит определить в терминах M с и А .
Проще всего этого добиться с помощью следующего вспомогательного уравнения (Hou, 1998),
Это всего лишь след определяющего уравнения для B посредством формулы Якоби ,
Подставляя формы полиномиальных мод в это вспомогательное уравнение, получаем
чтобы
и наконец
Это завершает рекурсию предыдущего раздела, развернутую в убывающих степенях λ .
Далее обратите внимание в алгоритме, что, более конкретно,
и, согласно теореме Кэли – Гамильтона ,
Окончательное решение могло бы быть более удобно выражено в терминах полных экспоненциальных многочленов Белла как
Пример
Более того, , что подтверждает приведенные выше расчеты.
Таким образом, характеристический многочлен матрицы A равен; определитель A равен; след 10 = - c 2 ; а обратное к A есть
- .
Эквивалентное, но отличное выражение
Компактный определитель решения m × m -матрицы для приведенной выше формулы Якоби может альтернативно определять коэффициенты c , [11] [12]
Смотрите также
Рекомендации
- ^ Urbain Le Verrier : Sur leschanges séculaires des éléments des orbites pour les sept planètes Principales , J. de Math. (1) 5 , 230 (1840), онлайн
- ^ Пол Хорст: Метод определения коэффициентов характеристического уравнения . Аня. Математика. Стат. 6 83-84 (1935), DOI : 10,1214 / АОМ / 1177732612
- ^ Жан-Мари Суро , Методика декомпозиции спектров и инверсии матриц , Comptes Rend. 227 , 1010-1011 (1948).
- ^ Фаддеев и IS Sominsky, Сборник zadatch ро vyshej алгебра ( Проблемы в высшей алгебре , Мир Издатели, 1972), Москва-Ленинград (1949). Проблема 979 .
- ^ JS Frame: простая формула рекурсии для инвертирования матрицы (аннотация) , Bull. Являюсь. Математика. Soc. 55 1045 (1949), DOI : 10.1090 / S0002-9904-1949-09310-2
- Перейти ↑ Householder, Alston S. (2006). Теория матриц в численном анализе . Дуврские книги по математике. ISBN 0486449726.
- Перейти ↑ Hou, SH (1998). «Класс Примечание: Простое доказательство Леверье - Фаддеев Характерный полиномиальный алгоритм» СИАМ обзор 40 (3) 706-709, DOI : 10,1137 / S003614459732076X .
- ^ Гантмахер, FR (1960). Теория матриц . Нью-Йорк: Издательство Челси. ISBN 0-8218-1376-5.
- ^ Заде, Лютфи А. и Дезоер, Чарльз А. (1963, 2008). Теория линейных систем: подход к государственному пространству (Mc Graw-Hill; Dover Civil and Mechanical Engineering) ISBN 9780486466637 , стр 303–305;
- ^ Abdeljaoued, Jounaidi и Lombardi, Анри (2004). Méthodes matricielles - Introduction à la complexité algébrique , (Mathématiques et Applications, 42) Springer, ISBN 3540202471 .
- ^ Браун, Лоуэлл С. (1994). Квантовая теория поля , Cambridge University Press. ISBN 978-0-521-46946-3 , стр. 54; Также см. Curtright, TL, Fairlie, DB и Alshal, H. (2012). "A Galileon Primer", arXiv: 1212.6972, раздел 3.
- ^ Рид, М .; Саймон Б. (1978). Методы современной математической физики . Vol. 4 Анализ операторов. США: ACADEMIC PRESS, INC. Стр. 323–333, 340, 343. ISBN 0-12-585004-2.
|volume=
имеет дополнительный текст ( справка )