שיטת החזקה ההפוכה

באנליזה נומרית שבמתמטיקה שיטת החזקה ההפוכה היא שיטה למציאת קירוב לערך עצמי כלשהו של מטריצה ואת הווקטור העצמי המתאים לו. השיטה מתבססת על רעיון דומה לרעיון של שיטת החזקה למציאת ערכים עצמיים.

השיטה מקבלת כקלט מטריצה $A$ ומספר $\lambda$, ומוצאת את הערך העצמי הכי קרוב ל-$\lambda$ ואת הווקטור העצמי המתאים לו. הרעיון של השיטה מתבסס על כך שהערך העצמי של $A$ הקרוב ביותר ל-$\lambda$ הוא הערך העצמי הגדול ביותר של $(A-\lambda I)^{-1}$ ואז פועלים על פי שיטת החזקה.

תיאור השיטה

עבור מטריצה ריבועית $A$ בגודל $n\times n$ ומספר $\lambda$.

התחל מוקטור אקראי $v_{0}$

חשב את $(A-\lambda I)^{-1}$ כאשר $I$ היא מטריצת היחידה בגודל $n\times n$

בכל איטרציה

חשב את $v_{i+1}=(A-\lambda I)^{-1}v_{i}$

הצב $v_{i+1}={\frac {v_{i+1}}{\|v_{i+1}\|}}$

חשב את $l_{i+1}=v_{i}^{*}Av_{i}$

$l_{i}$ יתכנס לערך העצמי הקרוב ביותר ל-$\lambda$.

אם הערך העצמי $\lambda$ בעל מרחב עצמי ממימד 1 (ללא ריבוי) אז הווקטור $v_{i}$ מתכנס לוקטור העצמי המתאים לערך העצמי שנמצא.

קצב התכנסות וסיבוכיות

בגלל שקצב ההתכנסות של שיטת החזקה תלוי בפער בין הערך העצמי הגדול לזה הבא אחריו, קצב ההתכנסות של שיטת החזקה ההפוכה תלוי במרחק בין הערך העצמי הקרוב ביותר ל-$\lambda$ לזה הבא אחריו. כיוון שהפעלה של $(A-\lambda I)^{-1}$ מגדילה את המרחק בין הערכים העצמיים שקרובים ל-$\lambda$ (במיוחד אם הם קרובים מאוד), מספר האיטרציות הנדרשות בשביל לקבל קירוב טוב הוא יחסית נמוך. החיסרון של השיטה הוא שכדי לחשב את $(A-\lambda I)^{-1}$ נדרשות ${\mathcal {O}}(n^{3})$ פעולות. לאחר שלב זה, כל איטרציה דורשת ${\mathcal {O}}(n^{2})$ פעולות.