Matematikada (chiziqli algebra ), the Faddeev - LeVerrier algoritmi a rekursiv ning koeffitsientlarini hisoblash usuli xarakterli polinom p ( λ ) = det ( λ Men n − A ) { displaystyle p ( lambda) = det ( lambda I_ {n} -A)} matritsa , A nomi bilan nomlangan Dmitriy Konstantinovich Faddeev va Urbain Le Verrier . Ushbu polinomni hisoblash natijasida hosil bo'ladi o'zgacha qiymatlar ning A uning ildizi sifatida; matritsada matritsali polinom sifatida A o'zi, u fundamental tomonidan g'oyib bo'ladi Keyli-Gemilton teoremasi . Determinantlarni hisoblash, ammo hisoblashda noqulay, ammo bu samarali algoritm hisoblashda ancha samaraliroq ( NC murakkabligi sinfi ).
Algoritm bir necha marta mustaqil ravishda biron bir shaklda yoki boshqacha tarzda kashf etilgan. Birinchi marta 1840 yilda nashr etilgan Urbain Le Verrier , keyinchalik P. Xorst tomonidan qayta ishlab chiqilgan, Jan-Mari Souriau , hozirgi shaklda bu erda Faddeev va Sominskiy, shuningdek J. S. Frame va boshqalar.[1] [2] [3] [4] [5] [6] Nyuton polinomlari , Hou tomonidan kiritilgan.[7] [8]
Algoritm
Maqsad koeffitsientlarni hisoblashdir vk n ×n A ,
p ( λ ) ≡ det ( λ Men n − A ) = ∑ k = 0 n v k λ k , { displaystyle p ( lambda) equiv det ( lambda I_ {n} -A) = sum _ {k = 0} ^ {n} c_ {k} lambda ^ {k} ~,} qaerda, aniq, vn v 0 = (−1)n A .
Koeffitsientlar rekursiv tarzda yuqoridan pastga qarab, yordamchi matritsalarning zarbalari bilan aniqlanadi M ,
M 0 ≡ 0 v n = 1 ( k = 0 ) M k ≡ A M k − 1 + v n − k + 1 Men v n − k = − 1 k t r ( A M k ) k = 1 , … , n . { displaystyle { 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_ {nk} & = - { frac {1} {k}} mathrm {tr} (AM_ {k}) qquad & k = 1, ldots, n ~. end {hizalangan}}} Shunday qilib,
M 1 = Men , v n − 1 = − t r A = − v n t r A ; { displaystyle M_ {1} = I ~, quad c_ {n-1} = - mathrm {tr} A = -c_ {n} mathrm {tr} A;} M 2 = A − Men t r A , v n − 2 = − 1 2 ( t r A 2 − ( t r A ) 2 ) = − 1 2 ( v n t r A 2 + v 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 ) Men , { displaystyle M_ {3} = A ^ {2} -A mathrm {tr} A - { frac {1} {2}} { Bigl (} mathrm {tr} A ^ {2} - ( mathrm {tr} A) ^ {2} { Bigr)} I,} v n − 3 = − 1 6 ( ( tr A ) 3 − 3 tr ( A 2 ) ( tr A ) + 2 tr ( A 3 ) ) = − 1 3 ( v n t r A 3 + v n − 1 t r A 2 + v n − 2 t r A ) ; { displaystyle c_ {n-3} = - { tfrac {1} {6}} { Bigl (} ( operatorname {tr} A) ^ {3} -3 operatorname {tr} (A ^ {2) }) ( operator nomi {tr} A) +2 operator nomi {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);} va boshqalar.,[9] [10]
M m = ∑ k = 1 m v n − m + k A k − 1 , { displaystyle M_ {m} = sum _ {k = 1} ^ {m} c_ {n-m + k} A ^ {k-1} ~,} v n − m = − 1 m ( v n t r A m + v n − 1 t r A m − 1 + . . . + v n − m + 1 t r A ) = − 1 m ∑ k = 1 m v 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} ~; ...} Kuzatib boring A−1 = - Mn / c0 = (−1)n −1Mn / detA λ . Buning teskari yoki determinantini olish uchun foydalanish mumkin A .
Hosil qilish
Dalil rejimlariga asoslanadi yordamchi matritsa , Bk ≡ Mn − k
( λ Men − A ) B = Men p ( λ ) { displaystyle ( lambda I-A) B = I ~ p ( lambda)} va shu bilan mutanosib hal qiluvchi
B = ( λ Men − A ) − 1 Men p ( λ ) . { displaystyle B = ( lambda I-A) ^ {- 1} I ~ p ( lambda) ~.} Bu, shubhasiz, matritsa polinomidir λ n-1
B ≡ ∑ k = 0 n − 1 λ k B k = ∑ k = 0 n λ k M n − k , { displaystyle B equiv sum _ {k = 0} ^ {n-1} lambda ^ {k} ~ B_ {k} = sum _ {k = 0} ^ {n} lambda ^ {k} ~ M_ {nk},} bu erda zararsizni aniqlash mumkin M 0
Yuqoridagi yordamchi uchun aniq polinom shakllarini aniqlovchi tenglamaga kiritish,
∑ k = 0 n λ k + 1 M n − k − λ k ( A M n − k + v k Men ) = 0 . { displaystyle sum _ {k = 0} ^ {n} lambda ^ {k + 1} M_ {nk} - lambda ^ {k} (AM_ {nk} + c_ {k} I) = 0 ~. } Endi, eng yuqori tartibda, birinchi muddat yo'qoladi M 0 λ , yordamchining aniqlovchi tenglamasidan, yuqorida),
M n A = B 0 A = v 0 , { displaystyle M_ {n} A = B_ {0} A = c_ {0} ~,} shuning uchun birinchi davrning qo'pol indekslari o'zgarishi hosil beradi
∑ k = 1 n λ k ( M 1 + n − k − A M n − k + v k Men ) = 0 , { displaystyle sum _ {k = 1} ^ {n} lambda ^ {k} { Big (} M_ {1 + nk} -AM_ {nk} + c_ {k} I { Big)} = 0 ~,} bu esa rekursiyani belgilaydi
∴ M m = A M m − 1 + v n − m + 1 Men , { displaystyle Shuning uchun qquad M_ {m} = AM_ {m-1} + c_ {n-m + 1} I ~,} uchun m =1,...,n . Ko'tarilayotgan indeksning kuchi bo'yicha kamayib borishiga e'tibor bering λ , lekin polinom koeffitsientlari v jihatidan hali aniqlanmagan M s va A .
Bunga quyidagi yordamchi tenglama orqali erishish mumkin (Hou, 1998),
λ ∂ p ( λ ) ∂ λ − n p = tr A B . { displaystyle lambda { frac { qismli p ( lambda)} { qismli lambda}} - np = operator nomi {tr} AB ~.} Bu faqat uchun belgilovchi tenglamaning izidir B tomonidan Jakobining formulasi ,
∂ p ( λ ) ∂ λ = p ( λ ) ∑ m = 0 ∞ λ − ( m + 1 ) tr A m = p ( λ ) tr Men λ Men − A ≡ tr B . { displaystyle { frac { qismli p ( lambda)} { qismli lambda}} = p ( lambda) sum _ {m = 0} ^ { infty} lambda ^ {- (m + 1 )} operator nomi {tr} A ^ {m} = p ( lambda) ~ operator nomi {tr} { frac {I} { lambda IA}} equiv operator nomi {tr} B ~.} Ushbu yordamchi tenglamada polinom rejimini qo'shish hosil bo'ladi
∑ k = 1 n λ k ( k v k − n v 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 ~,} Shuning uchun; ... uchun; ... natijasida
∑ m = 1 n − 1 λ n − m ( m v n − m + tr A M m ) = 0 , { displaystyle sum _ {m = 1} ^ {n-1} lambda ^ {nm} { Big (} mc_ {nm} + operator nomi {tr} AM_ {m} { Big)} = 0 ~ ,} va nihoyat
∴ v n − m = − 1 m tr A M m . { displaystyle Shuning uchun qquad c_ {n-m} = - { frac {1} {m}} operatorname {tr} AM_ {m} ~.} Bu avvalgi qismning kamayish kuchlari bo'yicha takrorlanishini yakunlaydi λ .
Algoritmda qo'shimcha ravishda to'g'ridan-to'g'ri,
M m = A M m − 1 − 1 m − 1 ( tr A M m − 1 ) Men , { displaystyle M_ {m} = AM_ {m-1} - { frac {1} {m-1}} ( operatorname {tr} AM_ {m-1}) I ~,} va bilan kelishilgan holda Keyli-Gemilton teoremasi ,
adj ( A ) = ( − ) n − 1 M n = ( − ) n − 1 ( A n − 1 + v n − 1 A n − 2 + . . . + v 2 A + v 1 Men ) = ( − ) n − 1 ∑ k = 1 n v k A k − 1 . { displaystyle operator nomi {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} ~.}
Yakuniy echim to'liq eksponensial jihatdan qulayroq ifodalanishi mumkin Qo'ng'iroq polinomlari kabi
v 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 (} operator nomi {tr} A, - 1! ~ Operator nomi {tr} A ^ {2}, 2! ~ Operator nomi {tr} A ^ {3}, ldots, (- 1) ^ {k-1} (k-1)! ~ Operator nomi {tr} A ^ {k} { Bigr)}.} Misol
A = [ 3 1 5 3 3 1 4 6 4 ] { displaystyle { displaystyle A = chap [{ begin {array} {rrr} 3 & 1 & 5 3 & 3 & 1 4 & 6 & 4 end {array}} o'ng]}} M 0 = [ 0 0 0 0 0 0 0 0 0 ] v 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 ] v 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 ] v 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 ] v 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} & = chap [{ 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} & = chap [{ 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 {blue } 3}}} mathbf { color {red} 120} && = & - 40 end {hizalanmış}}}}
Bundan tashqari, M 4 = A M 3 + v 0 Men = 0 { displaystyle { displaystyle M_ {4} = A ~ M_ {3} + c_ {0} ~ I = 0}}
Matritsaning xarakterli polinomiyasi A shunday p A ( λ ) = λ 3 − 10 λ 2 + 4 λ − 40 { displaystyle { displaystyle p_ {A} ( lambda) = lambda ^ {3} -10 lambda ^ {2} +4 lambda -40}} A bu det ( A ) = ( − 1 ) 3 v 0 = 40 { displaystyle { displaystyle det (A) = (- 1) ^ {3} c_ {0} = 40}} v 2 ; va teskari A bu
A − 1 = − 1 v 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}} chap [{ begin { massiv}} {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 va 0 {.} 30 0 {.} 15 & -0 {.} 35 & 0 {.} 15 end {array}} o'ng] }} Ekvivalent, ammo aniq ifoda
An ning ixcham determinanti m ×m Yuqoridagi Jakobi formulasi uchun matritsali eritma koeffitsientlarni muqobil ravishda belgilashi mumkin v ,[11] [12]
v 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}} ~.} Shuningdek qarang
Adabiyotlar
^ Urbain Le Verrier : Sur les variations séculaires des éléments des orbites pour les sept planètes principales. , J. de Matematik. (1) 5 , 230 (1840), Onlayn ^ Pol Xorst: Xarakteristik tenglamaning koeffitsientlarini aniqlash usuli . Ann. Matematika. Stat. 6 83-84 (1935), doi :10.1214 / aoms / 1177732612 ^ Jan-Mari Souriau , Une méthode pour la décomposition spectrale et l'inversion des matrices , Comptes Rend. 227 , 1010-1011 (1948).^ D. K. Faddeev va I. S. Sominskiy, Sbornik zadatch po vyshej algebra (Oliy algebra masalalari , Mir nashriyotlari, 1972), Moskov-Leningrad (1949). Muammo 979 . ^ J. S. ramkasi: Matritsani teskari aylantirish uchun oddiy rekursiya formulasi (mavhum) , Buqa. Am. Matematika. Soc. 55 1045 (1949), doi :10.1090 / S0002-9904-1949-09310-2 ^ Uy egasi, Alston S. (2006). Raqamli analizda matritsalar nazariyasi . Matematikadan Dover kitoblari. ISBN 0486449726 CS1 maint: ref = harv (havola ) ^ Hou, S. H. (1998). "Sinf uchun eslatma: Leverrierning oddiy isboti - Faddeevning xarakterli polinom algoritmi" SIAM sharhi 40(3) 706-709, doi :10.1137 / S003614459732076X . ^ Gantmaxer, F.R. (1960). Matritsalar nazariyasi . Nyu-York: Chelsi nashriyoti. ISBN 0-8218-1376-5 CS1 maint: ref = harv (havola ) ^ Zadeh, Lotfi A. va Desoer, Charlz A. (1963, 2008). Lineer tizim nazariyasi: Davlat kosmik yondashuvi (Mc Graw-Hill; Dover Fuqarolik va mashinasozlik) ISBN 9780486466637 , 303-305 betlar; ^ Abdelxouid, Jounaidi va Lombardi, Anri (2004). Méthodes matricielles - Kirish à la complexité algébrique , (Mathématiques et Applications, 42) Springer, ISBN 3540202471 . ^ Brown, Lowell S. (1994). Kvant maydoni nazariyasi , Kembrij universiteti matbuoti. ISBN 978-0-521-46946-3 , p. 54; Shuningdek qarang: Curtright, T. L., Fairlie, D. B. va Alshal, H. (2012). "Galiley astarlari", arXiv: 1212.6972, 3-qism. ^ Rid, M.; Simon, B. (1978). Zamonaviy matematik fizika metodikasi . Vol. 4 Operatorlar tahlili. AQSh: ACADEMIC PRESS, Inc. 323–333, 340, 343-betlar. ISBN 0-12-585004-2 
![{ displaystyle { displaystyle A = chap [{ begin {array} {rrr} 3 & 1 & 5 3 & 3 & 1 4 & 6 & 4 end {array}} o'ng]}}](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} & = chap [{ 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} & = chap [{ 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 {blue } 3}}} mathbf { color {red} 120} && = & - 40 end {hizalanmış}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fa5cc6fd02037d69ce3d4fa21722e16e4ff3f31)
![{ displaystyle { displaystyle A ^ {- 1} = - { frac {1} {c_ {0}}} ~ M_ {3} = { frac {1} {40}} chap [{ 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 va -0 {.} 20 va 0 {.} 30 0 {.} 15 & -0 {.} 35 & 0 {.} 15 end {array}} o'ng] }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2985cc7310a9c0e4eec2529d5d6012ce4d5b4bbf)
