מבוא לשיטות נומריות/פתרון מערכת משוואות לינאריות

הקדמה: עד כה פתרנו ע"י שיטת החילוץ של גאוס. כעת נפתח שיטות לפתרון המשתמשות באיטרציות.

שיטות הפתרון:

1. שיטת גאוס–זיידל
2. שיטת יעקבי
3. שיטת SOR – Succesive Over Relaxation

בשיטות איטרטיביות:

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

מערכת המשוואות תירשם כך:

${\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+a_{23}x_{3}=b_{2}\\a_{31}x_{1}+a_{32}x_{2}+a_{33}x_{3}=b_{3}\end{matrix}}\to {\begin{cases}x_{1}={\dfrac {b_{1}-a_{12}x_{2}-a_{13}x_{3}}{a_{11}}}\\x_{2}={\dfrac {b_{2}-a_{21}x_{1}-a_{23}x_{3}}{a_{22}}}\\x_{3}={\dfrac {b_{3}-a_{31}x_{1}-a_{32}x_{2}}{a_{33}}}\end{cases}}$

הפתרון ההתחלתי:

${\vec {x}}^{(0)}={\begin{pmatrix}x_{1}^{(0)}\\x_{2}^{(0)}\\x_{3}^{(0)}\end{pmatrix}}$

• האינדקס העליון מציין את מספר האיטרציה.

כעת נבצע איטרציות למציאת ${\vec {x}}^{(n+1)}$ שהוא פתרון קרוב ומדויק יותר מאשר ${\vec {x}}^{(n)}$ .

1) שיטת גאוס–זיידל

נשתמש בפתרון העדכני ביותר בחישובים מאוחרים באיטרציה:

$x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{\color {Red}(k+1)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right)$

• האינדקס המסומן באדום מציין את ההבדל משיטת יעקבי.

לדוגמא:

${\begin{aligned}&x_{1}^{(k+1)}={\frac {b_{1}-a_{12}x_{2}^{(k+1)}-a_{13}x_{3}^{(k)}}{a_{11}}}\\&x_{2}^{(k+1)}={\frac {b_{2}-a_{21}x_{1}^{(k+1)}-a_{23}x_{3}^{(k)}}{a_{22}}}\\&\quad \qquad \vdots \end{aligned}}$

2) שיטת יעקבי (Jacobi)

עדכון הפתרון יבוצע ע"י האיטרציה הכללית:

$x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right)$

לדוגמא:

${\begin{aligned}&x_{1}^{(k+1)}={\frac {b_{1}-a_{12}x_{2}^{(k)}-a_{13}x_{3}^{(k)}}{a_{11}}}\\&x_{2}^{(k+1)}={\frac {b_{2}-a_{21}x_{1}^{(k)}-a_{23}x_{3}^{(k)}}{a_{22}}}\\&\quad \qquad \vdots \end{aligned}}$

• תנאי התכנסות לשיטה (שליטה אלכסונית):

מדובר בתנאי מספיק אך לא הכרחי – השיטה עלולה להתכנס גם אם לא יתקיים, אך אם הוא מתקיים – השיטה בטוח תתכנס.

$\sum _{i=1,j\neq i}^{n}|a_{ij}|\leq |a_{ii}|$

הסבר:

${\begin{pmatrix}\color {red}8&1&-1\\2&\color {red}1&9\\1&-7&\color {red}2\end{pmatrix}}$

נוודא שכל אברי האלכסון גדולים, כל אחד, מסכום שאר האברים בשורה:

שורה ראשונה: $|1-|+|1|<|8|$ מתקיים

שורה שניה: $|9|+|2|<|1|$ לא מתקיים

שיטת יעקבי מתכנסת לאט יותר משיטת גאוס–זיידל מכיוון שבגאוס–זיידל כבר משתמשים בפתרון המעודכן בעת ביצוע האיטרציות.

• התכנסות השיטה:

השגיאה באיטרציה $k+1$ :

$\varepsilon ^{(k+1)}=|x^{(k+1)}-x|$

3) שיטת SOR – Successive Overrelaxation

האיטרציה הכללית בשיטת גאוס–זיידל:

$x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{\color {Red}(k+1)}-\sum _{j=i+1}^{n}a_{ij}x_{j}^{(k)}\right)$

נוציא מהביטוי המסומן באדום את האיבר הראשון ונקבל:

$x_{i}^{(k+1)}=x_{i}^{(k)}+{\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i}^{n}a_{ij}x_{j}^{(k)}\right)$

הנוסחה הכללית לאיטרציה בשיטה זו:

$x_{i}^{(k+1)}=x_{i}^{(k)}+{\frac {\omega }{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}a_{ij}x_{j}^{(k+1)}-\sum _{j=i}^{n}a_{ij}x_{j}^{(k)}\right)$

• $\omega$ הוא פרמטר לגודל הצעד בין האיטרציות. $\omega =1$ עבור גאוס–זיידל.
• $0<\omega <1$ השיטה תקרא underrelaxation והיא מתכנסת לעתים גם כאשר גאוס–זיידל לא מתכנסת (הצעדים בשיטה זו הם קטנים יותר).
• $1<\omega <2$ השיטה תקרא overrelaxation והיא עשויה להאיץ התכנסות בהם גאוס–זיידל מתכנסת, במידה והמטריצה נשלטת אלכסונית.
• $\omega \geq 2$ או $\omega \leq 0$ שיטת SOR לא תתכנס.