אנליזה נומרית/פתרון מערכת משוואות לינאריות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 82:
==שיטות איטרטיביות==
מאחר והתרגלנו לסמן את מספר האיטרציה ב"n", נסמן את סדר המערכת ב-N.
===שיטת Jacobi===
שיטה זו משתמשת באיברי המטריצה A על מנת להתכנס לפתרון מתוך ניחוש התחלתי כלשהו. מבצעים איטרציות עד להתכנסות של כל וקטור הנעלמים. כלומר: לא מתבצעות איטרציות עבור כל אחד ואחד מהנעלמים בנפרד.
מתוך הסכום :<math>\ \sum_{j=1}^N a_{ij}x_j=b_i,\ i=1,..,N</math> נבודד את הנעלם x<sub>i</sub>:
:<math>\ a_{ii}x_i+ \sum_{j=1,j\neq i}^N a_{ij}x_j= b_i \quad\Rightarrow\ x_i= -\sum_{j=1,j\neq i}^N {a_{ij}\over a_{ii}} x_j+ {b_i\over a_{ii}}</math>
ואז השיטה האיטרטיבית היא:
:<math>\ x_i^{(n+1)}= -\sum_{j=1,j\neq i}^N {a_{ij}\over a_{ii}} x_j^{(n)}+ {b_i\over a_{ii}}\ ,\quad i=1,..,N;\ n=0,1,2,...</math>
כאשר מספקים ניחוש התחלתי כלשהו:
:<math>\ \underline{x}^{(0)}= \begin{Bmatrix} x_1^{(0)} \\ x_2^{(0)} \\ \vdots \\ x_N^{(0)} \end{Bmatrix}</math>
מה שמתרחש בפועל הוא 3 לולאות מקוננות אשר משתמשות בוקטור <math>\ \underline{x}^{(n)}</math> על מנת לייצר את הוקטור <math>\ \underline{x}^{(n+1)}</math> (ראו "קישורים חיצוניים" עבור האלגוריתם).
'''התכנסות:''' ניתן להשתמש באחד מן הקריטריונים הבאים:
* <math>\ \left| x_i^{(n+1)}- x_i^{(n)} \right| < \epsilon\ ,\quad 1\le i\le N</math>
* <math>\ \left| 1-\frac{x_i^{(n)}}{x_i^{(n+1)}} \right| < \epsilon\ ,\quad 1\le i\le N</math>
* <math>\ \sqrt{\sum_{i=1}^n \left( x_i^{(n+1)}-x_i^{(n)} \right)^2} < \epsilon</math>
בדרך כלל התכנסות השיטה היא איטית ולכן יש לבצע מספר רב של איטרציות. את בדיקת ההתכנסות נהוג לבצע בתום הלולאה עבור כל נעלם בנפרד, ולא עבור כל איטרציה בנפרד.
===שיטת Gauss-Seidel===
שיטת GS מפצלת את הסכימה לנעלמים לפני הנעלם הנוכחי ולנעלמים אחרי הנעלם הנוכחי:
:<math>\ x_i^{(n+1)}= -\sum_{j=1}^{i-1} {a_{ij}\over a_{ii}} x_j^{(n+1)} -\sum_{j=i+1}^{N} {a_{ij}\over a_{ii}} x_j^{(n)}+ {b_i\over a_{ii}}\ ,\quad i=1,..,N;\ n=0,1,2,...</math>
בשיטה זו, בכל איטרציה משתמשים בערכים האחרונים שהתקבלו. כלומר כאן i-1 הנעלמים בוקטור הנעלמים מתעדכנים לפי הסדר יחד עם הנעלם ה-i, עם התקדמות הלולאה. מסיבה זו ההתכנסות מהירה פי 2 משיטת Jacobi. בדיקת ההתכנסות תתבצע כמו בשיטה הקודמת.
===שיטת Successive Over-Relaxation===
שיטת SOR נועדה על מנת לזרז את התכנסותה של שיטת Gauss-Seidel.
:<math>\ x_i^{(n+1)}= x_i^{(n)}+ \Omega \left[ x_{i_{GS}}^{(n+1)}-x_i^{(n)} \right]</math>
Ω הוא פרמטר הרלקסציה אשר מקיים <math>\ 0<\Omega<2</math>. על מנת להאיץ תהליך התכנסות איטי לוקחים Ω>1 ואילו על מנת להבטיח התכנסות עבור שיטות מתבדרות, לוקחים Ω<1. שימו לב כי עבור Ω=1 מקבלים חזרה את שיטת GS.
כמו כן, עבור מטריצה A נתונה, קיים ערך אופטימלי של Ω אשר מביא להתכנסות המהירה ביותר.
ניתן להוכיח שאם שיטת GS מתכנסת, אז שיטת SOR תתכנס מהר יותר.
===קישורים חיצוניים===
{{מיזמים|ויקיפדיה=en:Jacobi method|שם ויקיפדיה=שיטת Jacobi (אנגלית)|ויקיפדיה 2=en:Gauss-Seidel method|שם ויקיפדיה 2=שיטת Gauss-Seidel (אנגלית)|ויקיפדיה 3=en:Successive over-relaxation|שם ויקיפדיה 3=שיטת SOR (אנגלית)}}
* הסברים באתר MathWorld: [http://mathworld.wolfram.com/JacobiMethod.html שיטת Jacobi], [http://mathworld.wolfram.com/Gauss-SeidelMethod.html שיטת Gauss-Seidel], [http://mathworld.wolfram.com/SuccessiveOverrelaxationMethod.html שיטת SOR]
| |||