Алгоритм Фаддеева – Леверье

Урбен Леверье (1811–1877)
Первооткрыватель Нептуна .

В математике ( линейной алгебре ) алгоритм Фаддеева–Леверье — рекурсивный метод вычисления коэффициентов характеристического многочлена. $p_{A}(\lambda )=\det(\lambda I_{n}-A)$ квадратной матрицы А и , названной в честь Дмитрия Константиновича Фаддеева Урбена Леверье . Вычисление этого многочлена дает собственные значения A ; как его корни как матричный полином в самой матрице A , он обращается в нуль по теореме Кэли-Гамильтона . Вычисление характеристического полинома непосредственно из определения определителя является вычислительно громоздким, поскольку оно вводит новую символьную величину. $\lambda$; алгоритм Фаддеева-Леверье, напротив, работает непосредственно с коэффициентами матрицы $A$.

Алгоритм несколько раз независимо переоткрывался в разных формах. Впервые оно было опубликовано в 1840 году Урбеном Леверье , впоследствии переработано П. Хорстом, Жаном-Мари Сурио , в современном здесь виде Фаддеевым и Соминским, а далее Ж. С. Фреймом и другими. (Исторические моменты см. Householder. Элегантный упрощенный способ доказательства в обход полиномов Ньютона был предложен Хоу. Основная часть презентации следует из Gantmacher, p. 88. )

Алгоритм

Цель состоит в том, чтобы вычислить коэффициенты c _k характеристического многочлена n × n матрицы A ,

$p_{A}(\lambda )\equiv \det(\lambda I_{n}-A)=\sum _{k=0}^{n}c_{k}\lambda ^{k}~,$

где, очевидно, c _n = 1 и c ₀ = (−1) ^н это А. ​

Коэффициенты c _n-i определяются индукцией по i с использованием вспомогательной последовательности матриц

${\begin{aligned}M_{0}&\equiv 0&c_{n}&=1\qquad &(k=0)\\M_{k}&\equiv AM_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AM_{k})\qquad &k=1,\ldots ,n~.\end{aligned}}$

Таким образом,

$M_{1}=I~,\quad c_{n-1}=-\mathrm {tr} A=-c_{n}\mathrm {tr} A;$

$M_{2}=A-I\mathrm {tr} A,\quad c_{n-2}=-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2}{\Bigr )}=-{\frac {1}{2}}(c_{n}\mathrm {tr} A^{2}+c_{n-1}\mathrm {tr} A);$

$M_{3}=A^{2}-A\mathrm {tr} A-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2}{\Bigr )}I,$

$c_{n-3}=-{\tfrac {1}{6}}{\Bigl (}(\operatorname {tr} A)^{3}-3\operatorname {tr} (A^{2})(\operatorname {tr} A)+2\operatorname {tr} (A^{3}){\Bigr )}=-{\frac {1}{3}}(c_{n}\mathrm {tr} A^{3}+c_{n-1}\mathrm {tr} A^{2}+c_{n-2}\mathrm {tr} A);$

и т. д.,   ...;

$M_{m}=\sum _{k=1}^{m}c_{n-m+k}A^{k-1}~,$

$c_{n-m}=-{\frac {1}{m}}(c_{n}\mathrm {tr} A^{m}+c_{n-1}\mathrm {tr} A^{m-1}+...+c_{n-m+1}\mathrm {tr} A)=-{\frac {1}{m}}\sum _{k=1}^{m}c_{n-m+k}\mathrm {tr} A^{k}~;...$

Наблюдайте за А ⁻¹ = − M _n /c ₀ = (−1) ^{п -1} M _n /det A завершает рекурсию в точке λ . Это можно использовать для получения обратного или определителя A .

Вывод

Доказательство опирается на моды матрицы сопряженной B _k ≡ M _n−k , встречающихся вспомогательных матриц.  Эта матрица определяется

$(\lambda I-A)B=I~p_{A}(\lambda )$

и, таким образом, пропорциональна резольвенте

$B=(\lambda I-A)^{-1}I~p_{A}(\lambda )~.$

Очевидно, это матричный многочлен от λ степени n−1 . Таким образом,

$B\equiv \sum _{k=0}^{n-1}\lambda ^{k}~B_{k}=\sum _{k=0}^{n}\lambda ^{k}~M_{n-k},$

где можно определить безвредное M ₀ ≡0.

Вставляя явные полиномиальные формы в определяющее уравнение для сопряженного, приведенное выше,

$\sum _{k=0}^{n}\lambda ^{k+1}M_{n-k}-\lambda ^{k}(AM_{n-k}+c_{k}I)=0~.$

Теперь в высшем порядке первое слагаемое обращается в нуль при M ₀ =0; тогда как в нижнем порядке (постоянная по λ из определяющего уравнения сопряжения выше),

$M_{n}A=B_{0}A=c_{0}~,$

так что сдвиг фиктивных индексов первого члена дает

$\sum _{k=1}^{n}\lambda ^{k}{\Big (}M_{1+n-k}-AM_{n-k}+c_{k}I{\Big )}=0~,$

что, таким образом, диктует рекурсию

$\therefore \qquad M_{m}=AM_{m-1}+c_{n-m+1}I~,$

для m =1,..., n . Обратите внимание, что возрастающий индекс означает убывание по степени λ , но полиномиальные коэффициенты c еще предстоит определить с точки зрения M s и A .

Этого проще всего достичь с помощью следующего вспомогательного уравнения (Хоу, 1998):

$\lambda {\frac {\partial p_{A}(\lambda )}{\partial \lambda }}-np=\operatorname {tr} AB~.$

Это всего лишь след определяющего уравнения для B посредством формулы Якоби :

${\frac {\partial p_{A}(\lambda )}{\partial \lambda }}=p_{A}(\lambda )\sum _{m=0}^{\infty }\lambda ^{-(m+1)}\operatorname {tr} A^{m}=p_{A}(\lambda )~\operatorname {tr} {\frac {I}{\lambda I-A}}\equiv \operatorname {tr} B~.$

Подставляя формы полиномиального режима в это вспомогательное уравнение, получаем

$\sum _{k=1}^{n}\lambda ^{k}{\Big (}kc_{k}-nc_{k}-\operatorname {tr} AM_{n-k}{\Big )}=0~,$

так что

$\sum _{m=1}^{n-1}\lambda ^{n-m}{\Big (}mc_{n-m}+\operatorname {tr} AM_{m}{\Big )}=0~,$

и наконец

$\therefore \qquad c_{n-m}=-{\frac {1}{m}}\operatorname {tr} AM_{m}~.$

На этом рекурсия предыдущего раздела завершается, разворачиваясь в убывающих степенях λ .

Далее отметим в алгоритме, что, более конкретно,

$M_{m}=AM_{m-1}-{\frac {1}{m-1}}(\operatorname {tr} AM_{m-1})I~,$

и в соответствии с теоремой Кэли– Гамильтона

$\operatorname {adj} (A)=(-1)^{n-1}M_{n}=(-1)^{n-1}(A^{n-1}+c_{n-1}A^{n-2}+...+c_{2}A+c_{1}I)=(-1)^{n-1}\sum _{k=1}^{n}c_{k}A^{k-1}~.$

Окончательное решение было бы удобнее выразить через полные экспоненциальные полиномы Белла как

$c_{n-k}={\frac {(-1)^{n-k}}{k!}}{\mathcal {B}}_{k}{\Bigl (}\operatorname {tr} A,-1!~\operatorname {tr} A^{2},2!~\operatorname {tr} A^{3},\ldots ,(-1)^{k-1}(k-1)!~\operatorname {tr} A^{k}{\Bigr )}.$

Пример

${\displaystyle A=\left[{\begin{array}{rrr}3&1&5\\3&3&1\\4&6&4\end{array}}\right]}$

${\displaystyle {\begin{aligned}M_{0}&=\left[{\begin{array}{rrr}0&0&0\\0&0&0\\0&0&0\end{array}}\right]\quad &&&c_{3}&&&&&=&1\\M_{\mathbf {\color {blue}1} }&=\left[{\begin{array}{rrr}1&0&0\\0&1&0\\0&0&1\end{array}}\right]&A~M_{1}&=\left[{\begin{array}{rrr}\mathbf {\color {red}3} &1&5\\3&\mathbf {\color {red}3} &1\\4&6&\mathbf {\color {red}4} \end{array}}\right]&c_{2}&&&=-{\frac {1}{\mathbf {\color {blue}1} }}\mathbf {\color {red}10} &&=&-10\\M_{\mathbf {\color {blue}2} }&=\left[{\begin{array}{rrr}-7&1&5\\3&-7&1\\4&6&-6\end{array}}\right]\qquad &A~M_{2}&=\left[{\begin{array}{rrr}\mathbf {\color {red}2} &26&-14\\-8&\mathbf {\color {red}-12} &12\\6&-14&\mathbf {\color {red}2} \end{array}}\right]\qquad &c_{1}&&&=-{\frac {1}{\mathbf {\color {blue}2} }}\mathbf {\color {red}(-8)} &&=&4\\M_{\mathbf {\color {blue}3} }&=\left[{\begin{array}{rrr}6&26&-14\\-8&-8&12\\6&-14&6\end{array}}\right]\qquad &A~M_{3}&=\left[{\begin{array}{rrr}\mathbf {\color {red}40} &0&0\\0&\mathbf {\color {red}40} &0\\0&0&\mathbf {\color {red}40} \end{array}}\right]\qquad &c_{0}&&&=-{\frac {1}{\mathbf {\color {blue}3} }}\mathbf {\color {red}120} &&=&-40\end{aligned}}}$

Более того, ${\displaystyle M_{4}=A~M_{3}+c_{0}~I=0}$, что подтверждает приведенные выше расчеты.

характеристический полином матрицы A равен Таким образом, ${\displaystyle p_{A}(\lambda )=\lambda ^{3}-10\lambda ^{2}+4\lambda -40}$; определитель A равен ${\displaystyle \det(A)=(-1)^{3}c_{0}=40}$; след равен 10=− c ₂ ; и обратное значение A равно

${\displaystyle A^{-1}=-{\frac {1}{c_{0}}}~M_{3}={\frac {1}{40}}\left[{\begin{array}{rrr}6&26&-14\\-8&-8&12\\6&-14&6\end{array}}\right]=\left[{\begin{array}{rrr}0{.}15&0{.}65&-0{.}35\\-0{.}20&-0{.}20&0{.}30\\0{.}15&-0{.}35&0{.}15\end{array}}\right]}$.

Эквивалентное, но отличное выражение

Компактный определитель матричного решения размера m × m для приведенной выше формулы Якоби может альтернативно определять коэффициенты c ,

$c_{n-m}={\frac {(-1)^{m}}{m!}}{\begin{vmatrix}\operatorname {tr} A&m-1&0&\cdots &0\\\operatorname {tr} A^{2}&\operatorname {tr} A&m-2&\cdots &0\\\vdots &\vdots &&&\vdots \\\operatorname {tr} A^{m-1}&\operatorname {tr} A^{m-2}&\cdots &\cdots &1\\\operatorname {tr} A^{m}&\operatorname {tr} A^{m-1}&\cdots &\cdots &\operatorname {tr} A\end{vmatrix}}~.$

См. также

• Характеристический полином
• метод Горнера
• Определитель Фредгольма

Ссылки

Барбареско Ф. (2019) Алгоритм экспоненциального отображения Сурио для машинного обучения на матричных группах Ли. В: Нильсен Ф., Барбареско Ф. (ред.) Геометрическая наука об информации. GSI 2019. Конспекты лекций по информатике, том 11712. Springer, Cham. https://doi.org/10.1007/978-3-030-26980-7_10