Iterert kraftmetode

I matematikk , den itererte kraft -metoden eller krefter metode er en algoritme for beregning av den dominante eigenverdi av en matrise . Selv om denne algoritmen er enkel å implementere og populær, konvergerer den ikke veldig raskt.

Beregning av egenverdier

Gitt en matrise A , ser vi etter en egenverdi med større modul og en tilhørende egenvektor. Den beregning av egenverdiene er generelt ikke direkte er mulig (med en lukket formel): en bruker deretter iterative metoder, og fremgangsmåten av kreftene er den enkleste av dem.

Algoritme

Metoden er basert på følgende teorem, basert på Jordans reduksjon .

Teorem - La A være en kvadratmatrise av orden n og $(λ 1 , λ 2 , ..., λ n )$ dens egenverdier. Vi antar :

{\ displaystyle | \ lambda _ {1} |> \ max \ left (| \ lambda _ {2} |, ..., | \ lambda _ {n} | \ right).}

Vi betrakter den direkte summen ℂ n = E ⊕ F der E er det karakteristiske underområdet til A assosiert med egenverdien λ 1 , og F er det karakteristiske underområdet til A assosiert med de andre egenverdiene.

Så hvis w (0) ∉ F , sekvensen av vektorer ( w ( n ) ) definert av gjentakelsesforholdet

{\ displaystyle \ forall n \ in \ mathbb {N}, \ w ^ {(n + 1)} = {\ frac {1} {|| Aw ^ {(n)} ||}} Aw ^ {(n )}}

sjekket

w ( n ) ≠ 0 for alle n ∈ℕ.
${\ displaystyle || Aw ^ {(n)} || \ longrightarrow | \ lambda _ {1} |}$ når n → ∞ .
${\ displaystyle \ left ({\ frac {\ overline {\ lambda _ {1}}} {| \ lambda _ {1} |}} \ right) ^ {n} w ^ {(n)} \ longrightarrow v}$ når n → ∞ , hvor v er en enhetsvektor av A assosiert med egenverdien λ 1 .
Hvis j er en ikke-null komponent i vektoren v , når n → ∞ . ${\ displaystyle {\ frac {(Aw ^ {(n)}) _ {j}} {w_ {j} ^ {(n)}}} \ longrightarrow \ lambda _ {1}}$

Konvergens

Når de algebraiske og geometriske multiplikasjonene assosiert med egenverdien λ 1 er like, oppfører seg konvergenshastigheten til algoritmen , der λ 1 og λ 2 er de største og nest største egenverdiene (i absolutt verdi). Konvergens er ellers mye langsommere, og oppfører seg som generelt. ${\ displaystyle O \ left (| \ lambda _ {2} / \ lambda _ {1} | ^ {n} \ right)}$ ${\ displaystyle O \ left (1 / n \ right)}$

Historisk

Denne numeriske metoden ble designet av den italienske ingeniøren L. Vianello for å beregne kritisk belastning av spenning av elastisk nett, og unngå den sekulære determinanten . A. Stodola brukte det i sin avhandling om turbiner for å beregne de første egenfrekvensene til akslene til roterende maskiner .

Denne algoritmen brukes i sammenhenger der bruk av matrisen bare på tvers av produkter er en fordel, for eksempel for veldig store matriser som brukes i PageRank .

Andre metoder

Andre metoder for å beregne egenverdier, det er metoden for omvendt kraft (in) , Lanczos-algoritmen , iterasjonen Rayleigh , LOBPCG (in) og QR-algoritmen (in) (basert på QR-dekomponering ).

Merknader og referanser

Bernard Philippe og Yousef Saad, “ Beregning av egenverdier ” , på UMR Irisa .
Denis Serre , Matrisene: teori og praksis , Paris, Dunod ,2001, 168 s. ( ISBN 2-10-005515-1 , OCLC 491560333 )
" Graphische Untersuchung der Knickfestigkeit gerader Stäbe ", Zeitschrift des Vereines deutscher Ingenieure , vol. 42, n o 52,1898, s. 1436–1443.
Die Dampfturbinen und ihre Aussichten und über die als Wärmekraftmaschinen Gasturbine (1903).
Timoshenko, Historie om styrke av materialer , McGraw-Hill Book Co.,1953( repr. 1983, red. Dover), 452 s. , "Teorien om elastisitet i perioden 1900-1950", s. 418