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

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

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

תיאור השיטה

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

התחל מווקטור אקראי

v_{0}

חשב את

(A - λ I)^{- 1}

כאשר

I

היא מטריצת היחידה בגודל

n \times n

בכל איטרציה

חשב את

v_{i + 1} = (A - λ I)^{- 1} v_{i}

הצב

v_{i + 1} = \frac{v_{i + 1}}{‖ v_{i + 1} ‖}

חשב את

l_{i + 1} = v_{i}^{*} A v_{i}

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

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

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

תיאור השיטה

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

תפריט ניווט

חיפוש