V matematice (lineární algebra ), Algoritmus Faddeev – LeVerrier je rekurzivní metoda pro výpočet koeficientů charakteristický polynom str ( λ ) = det ( λ Já n − A ) { displaystyle p ( lambda) = det ( lambda I_ {n} -A)} matice , A , pojmenoval podle Dmitrij Konstantinovič Faddeev a Urbain Le Verrier . Výpočet tohoto polynomu vede k vlastní čísla z A jako jeho kořeny; jako polynom matice v matici A sám zmizí základem Cayley-Hamiltonova věta . Výpočet determinantů je však výpočetně těžkopádný, zatímco tento efektivní algoritmus je výpočetně významně efektivnější (v Třída složitosti NC ).
Algoritmus byl nezávisle znovuobjeven několikrát, v té či oné podobě. Poprvé byla vydána v roce 1840 autorem Urbain Le Verrier , následně přestavěn P. Horstem, Jean-Marie Souriau , ve své současné podobě zde Faddeev a Sominsky a dále J. S. Frame a další.[1] [2] [3] [4] [5] [6] Newtonovy polynomy , představil Hou.[7] [8]
Algoritmus Cílem je vypočítat koeficienty Ck n ×n A ,
str ( λ ) ≡ det ( λ Já n − A ) = ∑ k = 0 n C k λ k , { Displaystyle p ( lambda) ekviv det ( lambda I_ {n} -A) = součet _ {k = 0} ^ {n} c_ {k} lambda ^ {k} ~,} kde evidentně Cn C 0 = (−1)n A .
Koeficienty jsou určovány rekurzivně shora dolů, pomocí pomocných matic M ,
M 0 ≡ 0 C n = 1 ( k = 0 ) M k ≡ A M k − 1 + C n − k + 1 Já C n − k = − 1 k t r ( A M k ) k = 1 , … , n . { displaystyle { begin {sladěno} M_ {0} & equiv 0 & c_ {n} & = 1 qquad & (k = 0) M_ {k} & equiv 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 {zarovnáno}}} Tím pádem,
M 1 = Já , C n − 1 = − t r A = − C n t r A ; { displaystyle M_ {1} = I ~, quad c_ {n-1} = - mathrm {tr} A = -c_ {n} mathrm {tr} A;} M 2 = A − Já t r A , C n − 2 = − 1 2 ( t r A 2 − ( t r A ) 2 ) = − 1 2 ( C n t r A 2 + C n − 1 t r A ) ; { displaystyle M_ {2} = AI 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 t r A − 1 2 ( t r A 2 − ( t r A ) 2 ) Já , { displaystyle M_ {3} = A ^ {2} -A mathrm {tr} A - { frac {1} {2}} { Bigl (} mathrm {tr} A ^ {2} - ( mathrm {tr} A) ^ {2} { Bigr)} já,} C n − 3 = − 1 6 ( ( tr A ) 3 − 3 tr ( A 2 ) ( tr A ) + 2 tr ( A 3 ) ) = − 1 3 ( C n t r A 3 + C n − 1 t r A 2 + C n − 2 t r A ) ; { displaystyle 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);} atd.,[9] [10]
M m = ∑ k = 1 m C n − m + k A k − 1 , { displaystyle M_ {m} = součet _ {k = 1} ^ {m} c_ {n-m + k} A ^ {k-1} ~,} C n − m = − 1 m ( C n t r A m + C n − 1 t r A m − 1 + . . . + C n − m + 1 t r A ) = − 1 m ∑ k = 1 m C n − m + k t r A k ; . . . { displaystyle c_ {nm} = - { 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} ~; ...} Pozorovat A−1 = - M.n /C0 = (−1)n −1Mn / detA λ . To by mohlo být použito k získání inverzní nebo determinantu A .
Derivace Důkaz se opírá o režimy adjugovaná matice , Bk ≡ Mn − k
( λ Já − A ) B = Já str ( λ ) { displaystyle ( lambda I-A) B = I ~ p ( lambda)} a je tedy úměrná rozpouštědlo
B = ( λ Já − A ) − 1 Já str ( λ ) . { displaystyle B = ( lambda I-A) ^ {- 1} I ~ p ( lambda) ~.} Je to evidentně maticový polynom v λ n − 1
B ≡ ∑ k = 0 n − 1 λ k B k = ∑ k = 0 n λ k M n − k , { Displaystyle B ekviv součet _ {k = 0} ^ {n-1} lambda ^ {k} ~ B_ {k} = součet _ {k = 0} ^ {n} lambda ^ {k} ~ M_ {nk},} kde lze definovat neškodné M 0
Vkládání explicitních polynomických forem do definující rovnice pro adjugát výše,
∑ k = 0 n λ k + 1 M n − k − λ k ( A M n − k + C k Já ) = 0 . { displaystyle sum _ {k = 0} ^ {n} lambda ^ {k + 1} M_ {nk} - lambda ^ {k} (AM_ {nk} + c_ {k} I) = 0 ~. } Nyní, v nejvyšším řádu, první člen zmizí o M 0 λ , z definující rovnice adjugátu výše),
M n A = B 0 A = C 0 , { displaystyle M_ {n} A = B_ {0} A = c_ {0} ~,} takže posunutí fiktivních indexů prvního funkčního období se získá
∑ k = 1 n λ k ( M 1 + n − k − A M n − k + C k Já ) = 0 , { displaystyle sum _ {k = 1} ^ {n} lambda ^ {k} { Big (} M_ {1 + nk} -AM_ {nk} + c_ {k} I { Big)} = 0 ~,} což tedy diktuje rekurzi
∴ M m = A M m − 1 + C n − m + 1 Já , { displaystyle proto qquad M_ {m} = AM_ {m-1} + c_ {n-m + 1} I ~,} pro m =1,...,n . Všimněte si, že vzestupný index je sestupný v mocninách λ , ale polynomiální koeficienty C je třeba ještě určit z hlediska M s a A .
Toho lze nejsnadněji dosáhnout pomocí následující pomocné rovnice (Hou, 1998),
λ ∂ str ( λ ) ∂ λ − n str = tr A B . { displaystyle lambda { frac { částečné p ( lambda)} { částečné lambda}} - np = operatorname {tr} AB ~.} Toto je jen stopa určující rovnice pro B podle Jacobiho vzorec ,
∂ str ( λ ) ∂ λ = str ( λ ) ∑ m = 0 ∞ λ − ( m + 1 ) tr A m = str ( λ ) tr Já λ Já − A ≡ tr B . { displaystyle { frac { částečné p ( lambda)} { částečné lambda}} = p ( lambda) součet _ {m = 0} ^ { infty} lambda ^ {- (m + 1 )} operatorname {tr} A ^ {m} = p ( lambda) ~ operatorname {tr} { frac {I} { lambda IA}} equiv operatorname {tr} B ~.} Vložením polynomiálních režimů se do této pomocné rovnice získá
∑ k = 1 n λ k ( k C k − n C k − tr A M n − k ) = 0 , { displaystyle sum _ {k = 1} ^ {n} lambda ^ {k} { Big (} kc_ {k} -nc_ {k} - operatorname {tr} AM_ {nk} { Big)} = 0 ~,} aby
∑ m = 1 n − 1 λ n − m ( m C n − m + tr A M m ) = 0 , { displaystyle sum _ {m = 1} ^ {n-1} lambda ^ {nm} { Big (} mc_ {nm} + operatorname {tr} AM_ {m} { Big)} = 0 ~ ,} a nakonec
∴ C n − m = − 1 m tr A M m . { displaystyle proto qquad c_ {n-m} = - { frac {1} {m}} operatorname {tr} AM_ {m} ~.} Tím je dokončena rekurze předchozí části, která se odvíjí v sestupných silách λ .
Dále si všimněte v algoritmu, že přímo
M m = A M m − 1 − 1 m − 1 ( tr A M m − 1 ) Já , { displaystyle M_ {m} = AM_ {m-1} - { frac {1} {m-1}} ( operatorname {tr} AM_ {m-1}) I ~,} a v souladu s Cayley-Hamiltonova věta ,
adj ( A ) = ( − ) n − 1 M n = ( − ) n − 1 ( A n − 1 + C n − 1 A n − 2 + . . . + C 2 A + C 1 Já ) = ( − ) n − 1 ∑ k = 1 n C k A k − 1 . { displaystyle operatorname {adj} (A) = (-) ^ {n-1} M_ {n} = (-) ^ {n-1} (A ^ {n-1} + c_ {n-1} A ^ {n-2} + ... + c_ {2} A + c_ {1} I) = (-) ^ {n-1} sum _ {k = 1} ^ {n} c_ {k} A ^ {k-1} ~.}
Konečné řešení může být pohodlněji vyjádřeno z hlediska úplné exponenciality Polynomy zvonu tak jako
C n − k = ( − 1 ) n − k k ! B k ( tr A , − 1 ! tr A 2 , 2 ! tr A 3 , … , ( − 1 ) k − 1 ( k − 1 ) ! tr A k ) . { displaystyle c_ {nk} = { frac {(-1) ^ {nk}} {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)}.} Příklad A = [ 3 1 5 3 3 1 4 6 4 ] { displaystyle { displaystyle A = left [{ begin {array} {rrr} 3 & 1 & 5 3 & 3 & 1 4 & 6 & 4 end {array}} right]}} M 0 = [ 0 0 0 0 0 0 0 0 0 ] C 3 = 1 M 1 = [ 1 0 0 0 1 0 0 0 1 ] A M 1 = [ 3 1 5 3 3 1 4 6 4 ] C 2 = − 1 1 10 = − 10 M 2 = [ − 7 1 5 3 − 7 1 4 6 − 6 ] A M 2 = [ 2 26 − 14 − 8 − 12 12 6 − 14 2 ] C 1 = − 1 2 ( − 8 ) = 4 M 3 = [ 6 26 − 14 − 8 − 8 12 6 − 14 6 ] A M 3 = [ 40 0 0 0 40 0 0 0 40 ] C 0 = − 1 3 120 = − 40 { displaystyle { 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 {re d} 40} & 0 0 & 0 & mathbf { color {red} 40} end {array}} right] qquad & c_ {0} &&& = - { frac {1} { mathbf { color {modrá } 3}}} mathbf { color {red} 120} && = & - 40 end {zarovnáno}}}}
Dále M 4 = A M 3 + C 0 Já = 0 { displaystyle { displaystyle M_ {4} = A ~ M_ {3} + c_ {0} ~ I = 0}}
Charakteristický polynom matice A je tedy str A ( λ ) = λ 3 − 10 λ 2 + 4 λ − 40 { displaystyle { displaystyle p_ {A} ( lambda) = lambda ^ {3} -10 lambda ^ {2} +4 lambda -40}} A je det ( A ) = ( − 1 ) 3 C 0 = 40 { displaystyle { displaystyle det (A) = (- 1) ^ {3} c_ {0} = 40}} C 2 ; a inverzní k A je
A − 1 = − 1 C 0 M 3 = 1 40 [ 6 26 − 14 − 8 − 8 12 6 − 14 6 ] = [ 0 . 15 0 . 65 − 0 . 35 − 0 . 20 − 0 . 20 0 . 30 0 . 15 − 0 . 35 0 . 15 ] { displaystyle { displaystyle A ^ {- 1} = - { frac {1} {c_ {0}}} ~ M_ {3} = { frac {1} {40}} vlevo [{ start { 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 {pole}} vpravo] }} Ekvivalentní, ale zřetelný výraz Kompaktní determinant m ×m - maticové řešení pro výše uvedený Jacobiho vzorec může alternativně určovat koeficienty C ,[11] [12]
C n − m = ( − 1 ) m m ! | tr A m − 1 0 ⋯ tr A 2 tr A m − 2 ⋯ ⋮ ⋮ ⋮ tr A m − 1 tr A m − 2 ⋯ ⋯ 1 tr A m tr A m − 1 ⋯ ⋯ tr A | . { displaystyle c_ {nm} = { frac {(-1) ^ {m}} {m!}} { begin {vmatrix} operatorname {tr} A & m-1 & 0 & cdots operatorname {tr} A ^ {2} & operatorname {tr} A & m-2 & cdots 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}} ~.} Viz také Reference ^ Urbain Le Verrier : Sur les varitions séculaires des éléments des orbites pour les sept planètes principales , J. de Math. (1) 5 , 230 (1840), Online ^ Paul Horst: Metoda stanovení koeficientů charakteristické rovnice . Ann. Matematika. Stat. 6 83-84 (1935), doi :10.1214 / aoms / 1177732612 ^ Jean-Marie Souriau , Une méthode pour la décomposition spectrale et l'inversion des matrices , Comptes Rend. 227 , 1010-1011 (1948).^ D. K. Faddeev a I. S. Sominsky, Sbornik zadatch po vyshej algebře (Problémy ve vyšší algebře , Mir Publishers, 1972), Moskow-Leningrad (1949). Problém 979 . ^ J. S. Rám: Jednoduchý rekurzní vzorec pro invertování matice (abstrakt) , Býk. Dopoledne. Matematika. Soc. 55 1045 (1949), doi :10.1090 / S0002-9904-1949-09310-2 ^ Majitel domácnosti, Alston S. (2006). Teorie matic v numerické analýze . Dover knihy o matematice. ISBN 0486449726 CS1 maint: ref = harv (odkaz) ^ Hou, S. H. (1998). „Poznámka k učebně: Jednoduchý důkaz Leverriera - Faddeevův charakteristický polynomiální algoritmus“ Recenze SIAM 40(3) 706-709, doi :10.1137 / S003614459732076X . ^ Gantmacher, F.R. (1960). Teorie matic . NY: Chelsea Publishing. ISBN 0-8218-1376-5 CS1 maint: ref = harv (odkaz) ^ Zadeh, Lotfi A. a Desoer, Charles A. (1963, 2008). Teorie lineárního systému: Státní vesmírný přístup (Mc Graw-Hill; Dover Civil and Mechanical Engineering) ISBN 9780486466637 , str. 303–305; ^ Abdeljaoued, Jounaidi a Lombardi, Henri (2004). Méthodes matricielles - Úvod do komplexu algébrique (Mathématiques et Applications, 42) Springer, ISBN 3540202471 . ^ Brown, Lowell S. (1994). Teorie kvantového pole , Cambridge University Press. ISBN 978-0-521-46946-3, str. 54; Viz také Curtright, T. L., Fairlie, D. B. a Alshal, H. (2012). „A Galileon Primer“, arXiv: 1212.6972, část 3. ^ Reed, M .; Simon, B. (1978). Metody moderní matematické fyziky . Sv. 4 Analýza operátorů. USA: ACADEMIC PRESS, INC. S. 323–333, 340, 343. ISBN 0-12-585004-2 
![{ displaystyle { displaystyle A = left [{ begin {array} {rrr} 3 & 1 & 5 3 & 3 & 1 4 & 6 & 4 end {array}} right]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a23cfdb69eb826865d3072075b17bad2eb66200)
![{ displaystyle { 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 {re d} 40} & 0 0 & 0 & mathbf { color {red} 40} end {array}} right] qquad & c_ {0} &&& = - { frac {1} { mathbf { color {modrá } 3}}} mathbf { color {red} 120} && = & - 40 end {zarovnáno}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fa5cc6fd02037d69ce3d4fa21722e16e4ff3f31)
![{ displaystyle { displaystyle A ^ {- 1} = - { frac {1} {c_ {0}}} ~ M_ {3} = { frac {1} {40}} vlevo [{ start { 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 {pole}} vpravo] }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2985cc7310a9c0e4eec2529d5d6012ce4d5b4bbf)
