הצגת המקור של הדף "שיטת גאוס-זיידל"

ב[[אלגברה ליניארית]] [[אנליזה נומרית|נומרית]], '''שיטת גאוס-זיידל''' (ב[[אנגלית]]: 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'''<sup>(''k''+1)</sup> ניתנים לחישוב באופן סדרתי על ידי ההצבה:

:<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}}
* [https://www.youtube.com/watch?v=BXwDlM6pPMU שיטות יעקבי וגאוס-זיידל] - שיעור באתר Youtube.

{{בקרת זהויות}}

[[קטגוריה:אלגברה ליניארית]]
[[קטגוריה:אנליזה נומרית]]
[[קטגוריה:קרל פרידריך גאוס]]