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

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

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

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

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

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

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

$\begin{array}{c}{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{array}\to \{\begin{array}{c}{x}_1=\frac{b_1-a_{12}{x}_2-a_{13}{x}_3}{a_{11}}\\ x_2=\frac{b_2-a_{21}{x}_1-a_{23}{x}_3}{a_{22}}\\ x_3=\frac{b_3-a_{31}{x}_1-a_{32}{x}_2}{a_{33}}\end{array}$

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

${\overrightarrow{x}}^{(0)}=\left(\begin{array}{c}{x}_1^{(0)}\\ x_2^{(0)}\\ x_3^{(0)}\end{array}\right)$

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

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

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

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

$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j^{(k+1)}-\sum _{j=i+1}^n{a}_{ij}{x}_j^{(k)})$

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

לדוגמא:

$\begin{array}{cc}& 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}}\\ & ⋮\end{array}$

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

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

$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j^{(k)}-\sum _{j=i+1}^n{a}_{ij}{x}_j^{(k)})$

לדוגמא:

$\begin{array}{cc}& 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}}\\ & ⋮\end{array}$

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

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

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

הסבר:

$\left(\begin{array}{ccc}8& 1& -1\\ 2& 1& 9\\ 1& -7& 2\end{array}\right)$

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

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

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

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

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

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

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

3) שיטת SOR – Successive Overrelaxation

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

$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j^{(k+1)}-\sum _{j=i+1}^n{a}_{ij}{x}_j^{(k)})$

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

$x_i^{(k+1)}=x_i^{(k)}+\frac{1}{a_{ii}}(b_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j^{(k+1)}-\sum _{j=i}^n{a}_{ij}{x}_j^{(k)})$

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

$x_i^{(k+1)}=x_i^{(k)}+\frac{\omega }{a_{ii}}(b_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j^{(k+1)}-\sum _{j=i}^n{a}_{ij}{x}_j^{(k)})$

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