אלגוריתם לנצוש

אלגוריתם לָאנְצוֹשׁ (Lánczos) הוא אלגוריתם שפיתח המתמטיקאי ופיזיקאי ההונגרי-יהודי-אמריקאי קורנל לאנצוש ב-1950. האלגוריתם מוצא חלק (או את כל) הערכים עצמיים והווקטורים העצמיים של מטריצה הרמיטית (או סימטרית) בגודל $n\times n$ במספר מוגבל של פעולות. כמות הפעולות הנדרשת למציאת כל הערכים העצמיים והווקטורים העצמיים של מטריצה היא ${\mathcal {O}}(n^{3})$, אבל בעזרת אלגוריתם לאנצוש ניתן למצוא חלק מהערכים העצמיים בפחות פעולות.

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

האלגוריתם

קלט: מטריצה הרמיטית $A$ בגודל $n\times n$, ומספר איטרציות $m$ (בשביל לקבל את כל הערכים העצמיים והווקטורים העצמיים במדויק, יש לבחור $m=n$). למעשה, האלגוריתם לא צריך לקבל את המטריצה, אלא את היכולת להפעיל אותה על וקטורים.

פלט: מטריצה $V$ בגודל $n\times m$ עם עמודות אורתונורמליות ומטריצה תלת-אלכסונית $T=V^{*}AV$ בגודל $m\times m$. הערכים העצמיים של המטריצה $T$ "קרובים" לחלק מהערכים העצמיים של המטריצה המקורית $A$. בשביל לקבל את הערכים העצמיים של $T$ אפשר להשתמש למשל באלגוריתם QR. מכיוון שהמטריצה $T$ היא מטריצה תלת-אלכסונית, הערכים העצמיים שלה מחושבים ב ${\mathcal {O}}(m^{2})$ פעולות.

אלגוריתם:

1. יהי $v_{1}\in \mathbb {C} ^{n}$ וקטור שרירותי עם נורמה אוקלידית $1$.
2. צעד התחלתי:
   1. יהי $w_{1}'=Av_{1}$.
   2. יהי $\alpha _{1}=w_{1}'^{*}v_{1}$.
   3. יהי $w_{1}=w_{1}'-\alpha _{1}v_{1}$.
3. עבור $j=2,\dots ,m$ בצע:
   1. יהי $\beta _{j}=\left\|w_{j-1}\right\|$ (נורמה אוקלידית).
   2. אם $\beta _{j}\neq 0$ אז $v_{j}=w_{j-1}/\beta _{j}$,

      אחרת בחר את $v_{j}$ להיות וקטור שרירותי עם נורמה אוקלידית $1$ שיהיה אורתוגונלי לכל $v_{1},\dots ,v_{j-1}$.

   3. יהי $w_{j}'=Av_{j}$.
   4. יהי $\alpha _{j}=w_{j}'^{*}v_{j}$.
   5. יהי $w_{j}=w_{j}'-\alpha _{j}v_{j}-\beta _{j}v_{j-1}$.
4. תהי $V$ המטריצה עם עמודות $v_{1},\dots ,v_{m}$. תהי $T={\begin{pmatrix}\alpha _{1}&\beta _{2}&&&&0\\\beta _{2}&\alpha _{2}&\beta _{3}&&&\\&\beta _{3}&\alpha _{3}&\ddots &&\\&&\ddots &\ddots &\beta _{m-1}&\\&&&\beta _{m-1}&\alpha _{m-1}&\beta _{m}\\0&&&&\beta _{m}&\alpha _{m}\\\end{pmatrix}}$.

הערה $Av_{j}=w_{j}'=\beta _{j+1}v_{j+1}+\alpha _{j}v_{j}+\beta _{j}v_{j-1}$ עבור $1<j<m$.

מימוש

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

לקריאה נוספת

• Trefethen, Lloyd N., and David Bau III. Numerical linear algebra. Vol. 50. Siam, 1997.

• Stewart, Gilbert W. Matrix Algorithms: Volume II: Eigensystems. Society for Industrial and Applied Mathematics, 2001.

קישורים חיצוניים

• אלגוריתם לנצוש, באתר MathWorld (באנגלית)