שיטת גאוס-זיידל

באלגברה ליניארית נומרית, שיטת גאוס-זיידל (באנגלית: Gauss–Seidel method) היא שיטה איטרטיבית לפתרון מערכת של משוואות ליניאריות. היא קרויה על שמם של המתמטיקאים הגרמנים קרל פרידריך גאוס ופיליפ לודוויג פון זיידל, ודומה מאוד לשיטת יעקובי. אף על פי שניתן ליישמה לכל מטריצה בעלת איברים שונים מאפס על האלכסון הראשי, התכנסותה מובטחת אך ורק אם המטריצה היא אלכסונית דומיננטית, או שהיא סימטרית וחיובית. היא הוזכרה לראשונה במכתב פרטי של גאוס לתלמידו גרלינג מ-1823. עם זאת, הפרסום הראשון שלה הוא של זיידל, ב-1874.

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

תיאור

שיטת גאוס-זיידל היא טכניקה איטרטיבית לפתרון מערכת ריבועית של n משוואות ליניאריות עם וקטור נעלמים x:

<math>A\mathbf x = \mathbf b</math>.

היא פועלת באמצעות האיטרציה:

<math> L_* \mathbf{x}^{(k+1)} = \mathbf{b} - U \mathbf{x}^{(k)}, </math>

כאשר <math>\mathbf{x}^{(k)}</math> הוא הקירוב ה-k ל- <math>\mathbf{x}</math>, ואילו <math> \mathbf{x}^{(k+1)}</math> הוא הקירוב הבא או האיטרציה ה-1 + k של <math>\mathbf{x}</math>, בעוד המטריצה A מפורקת לסכום של מטריצה משולשית תחתונה <math>L_*</math>, ולמטריצה משולשית עליונה בהחלט U: כלומר <math> A = L_* + U </math>.

ביותר פירוט, אם נכתוב את A, x ו- b לרכיביהם:

<math>A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \qquad \mathbf{x} = \begin{bmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.</math>

אז הפירוק של A למרכיב של מטריצה משולשית תחתונה ולמרכיב של מטריצה משולשית עליונה ניתן על ידי:

<math>A=L_*+U \qquad \text{where} \qquad L_* = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \quad U = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end{bmatrix}. </math>

אנליטית, איטרציית גאוס-זיידל ניתנת לכתיבה מחדש כ-:

<math> \mathbf{x}^{(k+1)} = L_*^{-1} (\mathbf{b} - U \mathbf{x}^{(k)}). </math>

עם זאת, באמצעות ניצול הצורה המשולשית של המטריצה <math>L_*</math>, האיברים של x^(k+1) ניתנים לחישוב באופן סדרתי על ידי ההצבה:

<math> x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1}a_{ij}x^{(k+1)}_j - \sum_{j=i+1}^{n}a_{ij}x^{(k)}_j \right),\quad i=1,2,\dots,n. </math>

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

התכנסות

ההתכנסות של שיטת גאוס-זיידל תלויה במטריצה A. ידוע כי התהליך מתכנס אם אחד משני התנאים הבאים מתקיים:

• A היא סימטרית וחיובית, או
• A היא אלכסונית דומיננטית (diagonally dominant), הווה אומר כאשר כל איבר באלכסונה הראשי מקיים שערכו המוחלט גדול מסכום הערכים המוחלטים של כל האיברים האחרים באותה שורה, כלומר כאשר <math>|a_{ii}| > \sum_{j\neq i} |a_{ij}| \quad\text{for all } i, \,</math>.

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

• שיטת גאוס-זיידל, באתר MathWorld (באנגלית)
• שיטות יעקבי וגאוס-זיידל - שיעור באתר Youtube.