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

אלגוריתם לָנְצוֹשׁ (Lanczos) הוא אלגוריתם שפיתח קורנליוס לנצוש ב-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.

הערות שוליים

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

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