Algorytm Faddeeva-LeVerriera

Urbain Le Verrier (1811–1877) Odkrywca Neptuna .

W matematyce ( algebra liniowa ) algorytm Faddeeva – LeVerriera jest rekurencyjną metodą obliczania współczynników wielomianu charakterystycznego ${\ Displaystyle p_ {A} (\ lambda) = \det(\lambda I_{n}-A)}$ macierzy kwadratowej A , nazwanej na cześć Dmitrija Konstantinowicza Faddejewa i Urbaina Le Verriera . Obliczenie tego wielomianu daje wartości własne A jako pierwiastki; jako wielomian macierzowy w samej macierzy A znika na mocy podstawowego twierdzenia Cayleya-Hamiltona . Obliczanie wyznacznika z definicji wielomianu charakterystycznego jest jednak uciążliwe obliczeniowo, ponieważ jest $macierzy$$wielkością$ symboliczną, podczas gdy ten algorytm działa bezpośrednio ze współczynnikami

Algorytm był wielokrotnie niezależnie odkrywany na nowo, w takiej czy innej formie. Po raz pierwszy został opublikowany w 1840 roku przez Urbaina Le Verriera , następnie przebudowany przez P. Horsta, Jean-Marie Souriau , w obecnej formie tutaj przez Faddeeva i Sominsky'ego, a następnie przez JS Frame i innych. (Aby zapoznać się z punktami historycznymi, zobacz Householder. Elegancki skrót do dowodu, z pominięciem wielomianów Newtona , został wprowadzony przez Hou. Większa część prezentacji jest zgodna z Gantmacherem, s. 88.)

Algorytm

Celem jest obliczenie współczynników c _k wielomianu charakterystycznego macierzy n × n A ,

${\ Displaystyle p_ {A} (\ lambda) \ równoważnik \ det (\ lambda I_ {n} -A) = \sum _{k=0}^{n}c_{k}\lambda ^{k}~,}$

₀ gdzie oczywiście c _n = 1 i c = (−1) ⁿ det ZA .

Współczynniki są wyznaczane rekurencyjnie od góry do dołu, na podstawie ciągu macierzy pomocniczych M ,

${\ Displaystyle {\ rozpocząć {wyrównane} M_ {0} i \ równoważnik 0 i c_ {n} i = 1 \ qquad & (k = 0) \\ M_ {k} i \ równoważnik AM_ {k-1} + c_ {n -k+1}I\qquad \qquad &c_{nk}&=-{\frac {1}{k}}\mathrm {tr} (AM_{k})\qquad &k=1,\ldots ,n~. \end{wyrównane}}}$

Zatem,

${\ Displaystyle M_ {1} = ja ~, \ quad c_ {n-1} = - \ operatorname {tr} A = -c_ {n} \ operatorname {tr} A;}$

${\ Displaystyle M_ {2} = AI \ operatorname {tr} A \ quad c_ {n-2} = - {\ Frac {1} {2}} {\ Bigl (} \ operatorname {tr} A ^ {2 }-(\mathrm {tr} A)^{2}{\Bigr )}=-{\frac {1}{2}}(c_{n}\mathrm {tr} A^{2}+c_{n -1} \ operatorname {tr} ZA);}$

${\ Displaystyle M_ {3} = A ^ {2}-A\mathrm {tr} A-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2} {\ Biggr )} ja,}$

${\ Displaystyle c_ {n-3} = - {\ tfrac {1} {6}}} {\ Bigl (} (\ nazwa operatora {tr} A) ^ {3} -3 \ nazwa operatora {tr} (A ^ {2 })(\nazwa_operatora {tr} A)+2\nazwa_operatora {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);}$

itp., ...;

$~,}$

${\ Displaystyle M_ {m} = \ suma _ {k = 1} ^ {m} c_ {nm + k} A ^ { k-1$

${\ Displaystyle c_ {nm} = - {\ Frac {1} {m}} (c_ {n} \ operatorname {tr} A ^ {m} + c_ {n-1} \ operatorname {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}~;...}$

Zauważ A ⁻¹ = − M _n /c ₀ = (−1) ^{n −1} M _n /det A kończy rekurencję w λ . Można to wykorzystać do uzyskania odwrotności lub wyznacznika A .

Pochodzenie

Dowód opiera się na trybach macierzy pomocniczej , B _k ≡ M _n−k , napotkanych macierzach pomocniczych. Ta macierz jest zdefiniowana przez

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

a zatem jest proporcjonalny do rezolwenta

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

Jest to ewidentnie wielomian macierzowy w λ stopnia n−1 . Zatem,

${\ Displaystyle B \ równoważnik \ suma _ {k = 0} ^ {n-1} \ lambda ^ {k} ~B_{k}=\suma _{k=0}^{n}\lambda ^{k}~M_{nk},}$

gdzie można zdefiniować nieszkodliwe M ₀ ≡0.

Wstawienie jawnych form wielomianu do równania definiującego przymiotnik powyżej,

${\ Displaystyle \ suma _ {k = 0} ^ {n} \ lambda ^ {k + 1} M_ {nk} - \ lambda ^ {k} (AM_ {nk} + c_ {k} ja) = 0 ~. }$

Teraz, w najwyższym rzędzie, pierwszy wyraz znika o M ₀ = 0; podczas gdy w dolnym rzędzie (stała w λ , z równania definiującego adiugat, powyżej),

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

tak, że przesunięcie fikcyjnych indeksów pierwszego terminu daje plony

${\ Displaystyle \ suma _ {k = 1} ^ {n} \ lambda ^ {k} {\ Duży (}M_{1+nk}-AM_{nk}+c_{k}I{\Big )}=0~,}$

co w ten sposób dyktuje rekurencję

${\ Displaystyle \ dlatego \ qquad M_ {m} = AM_ {m-1} + c_ {nm + 1} ja ~,}$

dla m =1,..., n . Należy zauważyć, że indeks rosnący odpowiada malejącemu w potęgach λ , ale współczynniki wielomianu c nie zostały jeszcze określone w odniesieniu do M s i A .

Można to najłatwiej osiągnąć za pomocą następującego równania pomocniczego (Hou, 1998),

${\ Displaystyle \ lambda {\ Frac {\ częściowe p_ {A} (\ lambda)} {\ częściowe \ lambda}} -np = \ operatorname {tr} AB ~.}$

To jest tylko ślad równania definiującego B za pomocą wzoru Jacobiego ,

${\ Displaystyle {\ Frac {\ częściowe p_ {A} (\ lambda)} {\ częściowe \ lambda}} = p_ {A} (\ lambda) \ suma _ {m = 0} ^ {\ infty} \ lambda ^ {-(m+1)}\operatorname {tr} A^{m}=p_{A}(\lambda )~\operatorname {tr} {\frac {I}{\lambda IA}}\equiv \operatorname { tr} B~.}$

Wstawienie postaci trybu wielomianowego do tego równania pomocniczego daje wyniki

${\ Displaystyle \ suma _ {k = 1} ^ {n} \ lambda ^ {k} {\ duży (}kc_{k}-nc_{k}-\operatorname {tr} AM_{nk}{\Big )}=0~,}$

aby

${\ Displaystyle \ suma _ {m = 1} ^ {n-1} \ lambda ^ {nm} \Big (}mc_{nm}+\nazwa_operatora {tr} AM_{m}{\Big )}=0~,}$

i w końcu

${\ Displaystyle \ dlatego \ qquad c_ {nm} = - {\ Frac {1} {m}} \ operatorname {tr} AM_ {m} ~.}$

To kończy rekurencję z poprzedniej sekcji, rozwijającą się w malejących potęgach λ .

Dalsza uwaga w algorytmie, że bardziej bezpośrednio,

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

i zgodnie z twierdzeniem Cayleya-Hamiltona ,

${\ Displaystyle \ nazwa operatora {przym.} (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}\suma _{k=1}^{n}c_ {k}A^{k-1}~.}$

Ostateczne rozwiązanie można wygodniej wyrazić za pomocą pełnych wykładniczych wielomianów Bella jako

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

Przykład

${\ Displaystyle {\ Displaystyle A = \ lewo [{\ rozpocząć {tablica} {rrr} 3 i 1 i 5 \\ 3 i 3 i 1 \\ 4 i 6 i 4 \ koniec {tablica}} \ prawo]} }$

${\ Displaystyle {\ Displaystyle {\ rozpocząć {wyrównane} M_ {0} i = \ lewo [{\ rozpocząć { array}{rrr}0&0&0\\0&0&0\\0&0&0\end{tablica}}\right]\quad &&&c_{3}&&&&&=&1\\M_{\mathbf {\color {niebieski}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 {\kolor {czerwony}3} &1&5\\3&\mathbf {\kolor {czerwony}3} &1\\4&6&\mathbf {\kolor {czerwony}4} \end{tablica}}\right]&c_{2}&&&=-{ \frac {1}{\mathbf {\kolor {niebieski}1}}}\mathbf {\kolor {czerwony}10} &&=&-10\\M_{\mathbf {\kolor {niebieski}2}}&= \left[{\begin{array}{rrr}-7&1&5\\3&-7&1\\4&6&-6\end{array}}\right]\qquad &A~M_{2}&=\left[{\begin{ array}{rr}\mathbf {\kolor {czerwony}2} &26&-14\\-8&\mathbf {\kolor {czerwony}-12} &12\\6&-14&\mathbf {\kolor {czerwony}2} \ end{array}}\right]\qquad &c_{1}&&&=-{\frac {1}{\mathbf {\color {niebieski}2}}}\mathbf {\color {red}(-8)} && =&4\\M_{\mathbf {\color {niebieski}3}}&=\left[{\begin{tablica}{rrr}6&26&-14\\-8&-8&12\\6&-14&6\end{tablica} }\right]\qquad &A~M_{3}&=\left[{\begin{tablica}{rrr}\mathbf {\kolor {czerwony}40} &0&0\\0&\mathbf {\kolor {czerwony}40} &0\\0&0&\mathbf {\color {czerwony}40} \end{tablica}}\right]\qquad &c_{0}&&&=-{\frac {1}{\mathbf {\color {niebieski}3}} }\mathbf {\kolor {czerwony}120} &&=&-40\end{wyrównane}}}}$

Ponadto ${\ displaystyle {\ displaystyle M_ {4} = A ~ M_ {3} + c_ {0} ~ I = 0}}$ , co potwierdza powyższe obliczenia.

Charakterystyczny wielomian macierzy A jest zatem $\ Displaystyle {\ Displaystyle p_ {A} (\ lambda) = \ lambda ^ {3} -10 \ lambda ^{2}+4\lambda -40}}$ ; wyznacznik A to ${\ Displaystyle {\ Displaystyle \ det (A) = (-1) ^ {3} c_ {0} = 40}}$ ; ślad to 10=− c ₂ ; a odwrotnością A jest

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

Równoważne, ale odrębne wyrażenie

Zwarty wyznacznik rozwiązania macierzowego m × m dla powyższego wzoru Jacobiego może alternatywnie wyznaczać współczynniki c ,

${\ Displaystyle c_ {nm} = {\ Frac {(-1) ^ {m}} {m!}} {\ rozpocząć {vmatrix} \ nazwa operatora {tr} A&m-1&0&\ cdots \\\ nazwa operatora {tr} A ^{2}&\nazwa_operatora {tr} A&m-2&\cdots \\\vdots &\vdots &&&\vdots \\\nazwa_operatora {tr} A^{m-1}&\nazwa_operatora {tr} A^{m- 2}&\cdots &\cdots &1\\\nazwa_operatora {tr} A^{m}&\nazwa_operatora {tr} A^{m-1}&\cdots &\cdots &\nazwa_operatora {tr} A\end{ vmatrix}}~.}$

Zobacz też

• Wielomian charakterystyczny
• Algebra zewnętrzna § Algorytm Leverriera
• Metoda Hornera
• Wyznacznik Fredholma

Barbaresco F. (2019) Algorytm mapy wykładniczej Souriau dla uczenia maszynowego na macierzowych grupach kłamstw. W: Nielsen F., Barbaresco F. (red.) Geometric Science of Information. GSI 2019. Notatki z wykładów z informatyki, tom 11712. Springer, Cham. https://doi.org/10.1007/978-3-030-26980-7_10