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

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

השיטה מקבלת כקלט מטריצה $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})$ פעולות.