Power iteratie

In wiskunde, Power iteratie (Ook bekend als de vermogensmethode) is een eigenwaarde -algoritme: Gegeven een diagonaliseerbaar Matrix ${\ displaystyle a}$, het algoritme zal een nummer produceren ${\ DisplayStyle \ Lambda}$, wat de grootste is (in absolute waarde) eigenwaarde van ${\ displaystyle a}$, en een niet -nul vector ${\ DisplayStyle v}$, wat een overeenkomst is eigenvector van ${\ DisplayStyle \ Lambda}$, dat is, ${\ displaystyle av = \ lambda v}$.Het algoritme staat ook bekend als de Von mises iteratie.^[1]

Power iteratie is een heel eenvoudig algoritme, maar het kan langzaam samenkomen.De meest tijdrovende werking van het algoritme is de vermenigvuldiging van matrix ${\ displaystyle a}$ door een vector, dus het is effectief voor een zeer grote schaarse matrix met de juiste implementatie.

De methode

Animatie die het power iteratie -algoritme op een 2x2 -matrix visualiseert.De matrix wordt afgebeeld door zijn twee eigenvectoren.Fout wordt berekend als ${\ displayStyle || {\ text {benadering}}-{\ text {grootste eigenvector}} ||}$

Het power iteratie -algoritme begint met een vector ${\ DisplayStyle B_ {0}}$, wat een benadering kan zijn voor de dominante eigenvector of een willekeurige vector.De methode wordt beschreven door de Herstelrelatie

${\ displaystyle b_ {k+1} = {\ frac {ab_ {k}} {\ | ab_ {k} \ |}}}$

Dus bij elke iteratie, de vector ${\ DisplayStyle B_ {k}}$ wordt vermenigvuldigd door de matrix ${\ displaystyle a}$ en genormaliseerd.

Als we aannemen ${\ displaystyle a}$ heeft een eigenwaarde die strikt groter is dan zijn andere eigenwaarden en de startvector ${\ DisplayStyle B_ {0}}$ heeft een niet -nulcomponent in de richting van een eigenvector geassocieerd met de dominante eigenwaarde, vervolgens een deel ${\ displaystyle \ links (b_ {k} \ rechts)}$ convergeert naar een eigenvector geassocieerd met de dominante eigenwaarde.

Zonder de twee bovenstaande veronderstellingen, de volgorde ${\ displaystyle \ links (b_ {k} \ rechts)}$ komt niet noodzakelijkerwijs samen.In deze volgorde,

${\ displaystyle b_ {k} = e^{i \ phi _ {k}} v_ {1}+r_ {k}}$,

waar ${\ displaystyle v_ {1}}$ is een eigenvector geassocieerd met de dominante eigenwaarde, en ${\ displaystyle \ | r_ {k} \ | \ rightarrow 0}$.De aanwezigheid van de term ${\ displaystyle e^{i \ phi _ {k}}}$ impliceert dat ${\ displaystyle \ links (b_ {k} \ rechts)}$ convergeert niet tenzij ${\ displaystyle e^{i \ phi _ {k}} = 1}$.Onder de twee hierboven genoemde veronderstellingen, de volgorde ${\ displaystyle \ links (\ mu _ {k} \ rechts)}$ gedefinieerd door

${\ displaystyle \ mu _ _ {k} = {\ frac {b_ {k}^{*} ab_ {k}} {b_ {k}^{*} b_ {k}}}}}$

convergeert naar de dominante eigenwaarde (met Rayleigh quotiënt).^{[verduidelijking nodig]}

Men kan dit berekenen met het volgende algoritme (getoond in Python met Numpy):

#!/usr/bin/env python3 importeren numpy net zo NP def power_iteration(A, num_iterations: inteken):  # Kies idealiter een willekeurige vector  # Om de kans te verminderen dat onze vector  # Is orthogonaal voor de eigenvector  b_k = NP.willekeurig.rand(A.vorm geven aan[1]))  voor _ in bereik(num_iterations):  # Bereken het Matrix-By-Vector-product AB  B_K1 = NP.punt(A, b_k)  # Bereken de norm  b_k1_norm = NP.linalg.norm(B_K1)  # Normaliseer de vector opnieuw  b_k = B_K1 / b_k1_norm  opbrengst b_k power_iteration(NP.reeks([[0,5, 0,5], [0,2, 0,8]]), 10) 

De vector ${\ DisplayStyle B_ {k}}$ aan een bijbehorende eigenvector.Idealiter zou men de Rayleigh quotiënt Om de bijbehorende eigenwaarde te krijgen.

Dit algoritme wordt gebruikt om de Google Paginabeoordeling.

De methode kan ook worden gebruikt om de spectrale straal (de eigenwaarde met de grootste grootte, voor een vierkante matrix) door het rayleigh quotiënt te berekenen

${\ displayStyle \ rho (a) = \ max \ links \ {| \ lambda _ {1} |, \ dotsc, | \ lambda _ {n} | \ rechts \} = {\ frac {b_ {k}^{\ top} ab_ {k}} {b_ {k}^{\ top} b_ {k}}} = {\ frac {b_ {k+1}^{\ top} b_ {k}} {b_ {k}^{\ top} b_ {k}}}.}$

Analyse

Laten ${\ displaystyle a}$ worden ontbonden in zijn Jordan canonieke vorm: ${\ displaystyle a = vjv^{-1}}$, waar de eerste kolom van ${\ DisplayStyle v}$ is een eigenvector van ${\ displaystyle a}$ overeenkomend met de dominante eigenwaarde ${\ DisplayStyle \ Lambda _ {1}}$.Sinds de dominante eigenwaarde van ${\ displaystyle a}$ is uniek, het eerste Jordan -blok van ${\ displaystyle j}$ is de ${\ DisplayStyle 1 \ maal 1}$ Matrix ${\ displaystyle [\ lambda _ {1}],}$ waar ${\ DisplayStyle \ Lambda _ {1}}$ is de grootste eigenwaarde van A in grootte.De startvector ${\ DisplayStyle B_ {0}}$ kan worden geschreven als een lineaire combinatie van de kolommen van V:

${\ displaystyle b_ {0} = c_ {1} v_ {1}+c_ {2} v_ {2}+\ cdots+c_ {n} v_ {n}.}$

Door veronderstelling, ${\ DisplayStyle B_ {0}}$ heeft een niet -nulcomponent in de richting van de dominante eigenwaarde, dus ${\ displaystyle c_ {1} \ neq 0}$.

Het computationeel nuttige Herstelrelatie voor ${\ displaystyle b_ {k+1}}$ kan worden herschreven als:

${\ displayStyle b_ {k+1} = {\ frac {ab_ {k}} {\ | ab_ {k} \ |}} = {\ frac {a^{k+1} b_ {0}} {\ |A^{k+1} b_ {0} \ |}},}$

waar de uitdrukking: ${\ displayStyle {\ frac {a^{k+1} b_ {0}} {\ | a^{k+1} b_ {0} \ |}}}$ is meer vatbaar voor de volgende analyse.

${\ displayStyle {\ begin {aligned} b_ {k} & = {\ frac {a^{k} b_ {0}} {\ | a^{k} b_ {0} \ |}}}} \ & = {\ frac {\ links (vjv^{-1} \ rechts)^{k} b_ {0}} {\ | \ left (vjv^{-1} \ rechts)^{k} b_ {0} \ |}} \\ & = {\ frac {vj^{k} v^{-1} b_ {0}} {\ | vj^{k} v^{-1} b_ {0}}}}}}}} \\ &= {\ frac {vj^{k} v^{-1} \ links (c_ {1} v_ {1}+c_ {2} v_ {2}+\ cdots+c_ {n} v_ {n} \ rechts)} {\ | Vj^{k} v^{-1} \ links (c_ {1} v_ {1}+c_ {2} v_ {2}+\ cdots+c_ {n} v_ {n} \ rechts) \ |}} \\ & = {\ frac {vj^{k} \ links (c_ {1} e_ {1}+c_ {2} e_ {2}+\ cdots+c_ {n} e_ {n}\ rechts)} {\ | vj^{k} \ links (c_ {1} e_ {1}+c_ {2} e_ {2}+\ cdots+c_ {n} e_ {n} \ rechts) \ |}} \\ & = \ left ({\ frac {\ lambda _ {1}} {| \ lambda _ {1} |}} \ rechts)^{k} {\ frac {c_ {1}} {| c_ {1} |}} {\ frac {v_ {1}+{\ frac {1} {c_ {1}}} v \ links ({\ frac {1} {\ lambda _ {1}}} j \ rechts)^{k} \ links (c_ {2} e_ {2}+\ cdots+c_ {n} e_ {n} \ rechts)} {\ links \ | v_ {1}+{\ frac {1} {c_ {1}}} v \ left ({\ frac {1} {\ lambda _ {1}}} j \ rechts)^{k} \ links (c_ {2} e_ {2} +\ cdots +c_ {n}e_ {n} \ rechts) \ rechts \ |}} \ end {uitgelijnd}}}$

De bovenstaande uitdrukking vereenvoudigt ${\ displaystyle k \ to \ infty}$

$1} {\ lambda _ {1}}} j_ {2} \ rechts)^{k} &&& \\ && \ ddots & \\ &&& \ left ({\ frac {1} {\ lambda _ {1}}}{\ text {as}} \ quad k \ to \ infty.}$

De limiet volgt uit het feit dat de eigenwaarde van ${\ displaystyle {\ frac {1} {\ lambda _ {1}}} j_ {i}}$ is minder dan 1 in grootte, dus

${\ displayStyle \ left ({\ frac {1} {\ lambda _ {1}}} j_ {i} \ rechts)^{k} \ naar 0 \ quad {\ text {as}} \ quad k \ to \ to \infty.}$

Het volgt dat:

${\ displayStyle {\ frac {1} {c_ {1}}} v \ left ({\ frac {1} {\ lambda _ {1}}} j \ rechts)^{k} \ left (c_ {2}e_ {2} +\ cdots +c_ {n} e_ {n} \ rechts) \ tot 0 \ quad {\ text {as}} \ quad k \ to \ infty}$

Dit feit gebruiken, ${\ DisplayStyle B_ {k}}$ kan worden geschreven in een vorm die de nadruk legt op zijn relatie met ${\ displaystyle v_ {1}}$ wanneer k is groot:

${\ displaystyle {\ begin {uitgelijnd} b_ {k} & = \ left ({\ frac {\ lambda _ {1}} {| \ lambda _ {1} |}}} \ rechts)^{k} {\ frac{c_ {1}} {| c_ {1} |}} {\ frac {v_ {1}+{\ frac {1} {c_ {1}}} v \ left ({\ frac {1} {\ lambda_ {1}}} j \ rechts)^{k} \ links (c_ {2} e_ {2} +\ cdots +c_ {n} e_ {n} \ rechts)} {\ links \ | v_ {1}+{\ frac {1} {c_ {1}}} v \ links ({\ frac {1} {\ lambda _ {1}}} j \ rechts)^{k} \ left (c_ {2} e_ {2} +\ cdots +c_ {n} e_ {n} \ rechts) \ rechts \ |}} \\ [6pt] & = e^{i \ phi _ {k}} {\ frac {c_ {1}}{| c_ {1} |}} {\ frac {v_ {1}} {\ | v_ {1} \ |}}+r_ {k} \ end {uitgelijnd}}}$

waar ${\ displaystyle e^{i \ phi _ {k}} = \ left (\ lambda _ {1}/| \ lambda _ {1} | \ rechts)^{k}}$ en ${\ displaystyle \ | r_ {k} \ | \ to 0}$ net zo ${\ displaystyle k \ to \ infty}$

De reeks ${\ displaystyle \ links (b_ {k} \ rechts)}$ is begrensd, dus het bevat een convergente deeling.Merk op dat de eigenvector die overeenkomt met de dominante eigenwaarde alleen uniek is tot een scalair, dus hoewel de volgorde ${\ displaystyle \ links (b_ {k} \ rechts)}$ mag niet samenkomen,${\ DisplayStyle B_ {k}}$ is bijna een eigenvector van A voor groot k.

Als alternatief, als A is diagonaliseerbaar, dan levert het volgende bewijs hetzelfde resultaat op

Laat λ₁, λ₂, ..., λ_m wees de m eigenwaarden (geteld met veelheid) van A en laat v₁, v₂, ..., v_m Wees de overeenkomstige eigenvectoren.Stel dat dat ${\ DisplayStyle \ Lambda _ {1}}$ is de dominante eigenwaarde, zodat ${\ displaystyle | \ lambda _ {1} |> | \ lambda _ {j} |}$ voor ${\ DisplayStyle J> 1}$.

De eerste vector ${\ DisplayStyle B_ {0}}$ kan worden geschreven:

${\ displaystyle b_ {0} = c_ {1} v_ {1}+c_ {2} v_ {2}+\ cdots+c_ {m} v_ {m}.}$

Als ${\ DisplayStyle B_ {0}}$ wordt willekeurig gekozen (met uniforme waarschijnlijkheid), dan c₁ ≠ 0 met waarschijnlijkheid 1. Nutsvoorzieningen,

${\ DisplayStyle {\ begin {aligned} a^{k} b_ {0} & = c_ {1} a^{k} v_ {1}+c_ {2} a^{k} v_ {2}+\ cdots+c_ {m} a^{k} v_ {m} \\ & = c_ {1} \ lambda _ {1}^{k} v_ {1}+c_ {2} \ lambda _ {2}^{k1}+{\ frac {c_ {2}} {c_ {1}}} \ left ({\ frac {\ lambda _ {2}} {\ lambda _ {1}}} \ rechter)^{k} v_{2} +\ cdots +{\ frac {c_ {m}} {c_ {1}}} \ links ({\ frac {\ lambda _ {m}} {\ lambda _ {1}}} \ rechter)^{k} v_ {m} \ rechts) \\ & \ to c_ {1} \ lambda _ {1}^{k} v_ {1} && \ left | {\ frac {\ lambda _ {j}} {\lambda _ {1}}} \ rechts | <1 {\ text {for}} j> 1 \ end {uitgelijnd}}}$

Aan de andere kant:

${\ displaystyle b_ {k} = {\ frac {a^{k} b_ {0}} {\ | a^{k} b_ {0} \ |}}.}$

Daarom, ${\ DisplayStyle B_ {k}}$ convergeert naar (een veelvoud van de eigenvector ${\ displaystyle v_ {1}}$.De convergentie is geometrisch, met verhouding

${\ displaystyle \ links | {\ frac {\ lambda _ {2}} {\ lambda _ {1}}} \ rechts |,}$

waar ${\ DisplayStyle \ Lambda _ {2}}$ geeft de tweede dominante eigenwaarde aan.Aldus convergeert de methode langzaam als er een eigenwaarde in grootte is ten opzichte van de dominante eigenwaarde.

Toepassingen

Hoewel de power iteratiemethode slechts één eigenwaarde van een matrix benadert, blijft deze nuttig Computationele problemen. Bijvoorbeeld, Google gebruikt het om de Paginabeoordeling van documenten in hun zoekmachine,^[2] en Twitter Gebruikt het om gebruikers aanbevelingen te tonen van wie ze moeten volgen.^[3] De power iteratiemethode is vooral geschikt voor schaarse matrices, zoals de webmatrix, of als de matrixvrije methode dat vereist niet de coëfficiëntmatrix opslaan ${\ displaystyle a}$ expliciet, maar kan in plaats daarvan toegang krijgen tot een functie die matrix-vectorproducten evalueert ${\ displaystyle ax}$.Voor niet-symmetrische matrices die zijn goed geconditioneerd De power iteratiemethode kan beter presteren dan complexer Arnoldi iteratie.Voor symmetrische matrices wordt de power iteratiemethode zelden gebruikt, omdat de convergentiesnelheid ervan gemakkelijk kan worden verhoogd zonder de kleine kosten per iteratie op te offeren;zie, bijv. Lanczos iteratie en Lobpcg.

Sommige van de meer geavanceerde eigenwaarde -algoritmen kunnen worden opgevat als variaties van de kracht iteratie.Bijvoorbeeld de omgekeerde iteratie Methode past de kracht iteratie toe op de matrix ${\ displaystyle a^{-1}}$.Andere algoritmen kijken naar de hele subruimte die wordt gegenereerd door de vectoren ${\ DisplayStyle B_ {k}}$.Deze subruimte staat bekend als de Krylov subruimte.Het kan worden berekend door Arnoldi iteratie of Lanczos iteratie.

Zie ook

• Rayleigh quotiënt iteratie
• Omgekeerde iteratie

Referenties