שיטת החזקה

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

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

תיאור השיטה

עבור מטריצה ריבועית <math> A </math> בגודל <math> n \times n </math>.

• התחל מווקטור אקראי <math> v_0 </math> (או קירוב לווקטור העצמי הדומיננטי)
• בכל איטרציה: חשב את <math> v_{i+1} = \frac{Av_i}{\|Av_i\|} </math> חשב את <math> l_{i+1} = v_i^*Av_i </math>

• <math> l_i </math> יתכנס לערך העצמי הגדול ביותר בערכו המוחלט.

ככל שהאיטרציות נמשכות, הווקטור המנורמל יתקרב יותר ויותר לווקטור העצמי הדומיננטי של המטריצה. את הערך העצמי המתאים ניתן למצוא, למשל, באמצעות מקדם ריילי (Rayleigh quotient). אם הערך העצמי הגדול ביותר של <math> A </math> גדול ממש מכל שאר הערכים העצמיים (בערכם המוחלט, כולל ריבוי) אז הווקטור <math> v_i </math> מתכנס לווקטור העצמי המתאים לערך העצמי הגדול ביותר.

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