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

אלגוריתם לָאנְצוֹשׁ (Lánczos) הוא אלגוריתם שפיתח המתמטיקאי ופיזיקאי ההונגרי-יהודי-אמריקאי קורנל לאנצוש ב-1950[1]. האלגוריתם מוצא חלק (או את כל) הערכים עצמיים והווקטורים העצמיים של מטריצה הרמיטית (או סימטרית) בגודל n×n במספר מוגבל של פעולות. כמות הפעולות הנדרשת למציאת כל הערכים העצמיים והווקטורים העצמיים של מטריצה היא 𝒪(n3), אבל בעזרת אלגוריתם לאנצוש ניתן למצוא חלק מהערכים העצמיים בפחות פעולות.[2]

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

האלגוריתם

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

פלט: מטריצה V בגודל n×m עם עמודות אורתונורמליות ומטריצה תלת-אלכסונית T=V*AV בגודל m×m. הערכים העצמיים של המטריצה T "קרובים" לחלק מהערכים העצמיים של המטריצה המקורית A. בשביל לקבל את הערכים העצמיים של T אפשר להשתמש למשל באלגוריתם QR. מכיוון שהמטריצה T היא מטריצה תלת-אלכסונית, הערכים העצמיים שלה מחושבים ב 𝒪(m2) פעולות.

אלגוריתם:

  1. יהי v1n וקטור שרירותי עם נורמה אוקלידית 1.
  2. צעד התחלתי:
    1. יהי w1=Av1.
    2. יהי α1=w1'*v1.
    3. יהי w1=w1α1v1.
  3. עבור j=2,,m בצע:
    1. יהי βj=wj1 (נורמה אוקלידית).
    2. אם βj0 אז vj=wj1/βj,
      אחרת בחר את vj להיות וקטור שרירותי עם נורמה אוקלידית 1 שיהיה אורתוגונלי לכל v1,,vj1.
    3. יהי wj=Avj.
    4. יהי αj=wj'*vj.
    5. יהי wj=wjαjvjβjvj1.
  4. תהי V המטריצה עם עמודות v1,,vm. תהי T=(α1β20β2α2β3β3α3βm1βm1αm1βm0βmαm).
הערה Avj=wj=βj+1vj+1+αjvj+βjvj1 עבור 1<j<m.

מימוש

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

לקריאה נוספת

  • 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.

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

הערות שוליים

  1. ^ Lanczos, C. "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators", J. Res. Nat’l Bur. Std. 45, 255-282 (1950).
  2. ^ קיים אנלוג לאלגוריתם עבור מטריצות שאינן סימטריות בשם אלגוריתם ארנולדי
  3. ^ http://www.caam.rice.edu/software/ARPACK/
  4. ^ https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs