הקדמה: עד כה פתרנו ע"י שיטת החילוץ של גאוס. כעת נפתח שיטות לפתרון המשתמשות באיטרציות.
שיטות הפתרון:
- שיטת גאוס–זיידל
- שיטת יעקבי
- שיטת SOR – Succesive Over Relaxation
בשיטות איטרטיביות:
- דורש פתרון התחלתי
- נשפר פתרון זה בכל איטרציה באמצעות שימוש בפתרון הקודם.
מערכת המשוואות תירשם כך:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c505943543d352d23e7f6d30998c418db417f1f)
הפתרון ההתחלתי:
![{\displaystyle {\vec {x}}^{(0)}={\begin{pmatrix}x_{1}^{(0)}\\x_{2}^{(0)}\\x_{3}^{(0)}\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5814d2610e6b8865ee31241954a833c21f50f4b1)
- האינדקס העליון מציין את מספר האיטרציה.
כעת נבצע איטרציות למציאת
שהוא פתרון קרוב ומדויק יותר מאשר
.
1) שיטת גאוס–זיידל
נשתמש בפתרון העדכני ביותר בחישובים מאוחרים באיטרציה:
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcdcd5ec687cc3fb3429c47736bda58973fc5631)
- האינדקס המסומן באדום מציין את ההבדל משיטת יעקבי.
לדוגמא:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05b30b60ae64a4f2b5f1d8e1a965a1b5a6b9d7f9)
2) שיטת יעקבי (Jacobi)
עדכון הפתרון יבוצע ע"י האיטרציה הכללית:
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4abc2761d1f0f446dc340d8ad278417559b02a2c)
לדוגמא:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19710297a4d50e2370f658cfabc553cb4bc52bbf)
- תנאי התכנסות לשיטה (שליטה אלכסונית):
- מדובר בתנאי מספיק אך לא הכרחי – השיטה עלולה להתכנס גם אם לא יתקיים, אך אם הוא מתקיים – השיטה בטוח תתכנס.
![{\displaystyle \sum _{i=1,j\neq i}^{n}|a_{ij}|\leq |a_{ii}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed840dc00a6caa1b9da65ea430336ada72213972)
הסבר:
![{\displaystyle {\begin{pmatrix}\color {red}8&1&-1\\2&\color {red}1&9\\1&-7&\color {red}2\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/596cb3c25273d4dd42c4809b969ffead50905a74)
נוודא שכל אברי האלכסון גדולים, כל אחד, מסכום שאר האברים בשורה:
שורה ראשונה:
מתקיים
שורה שניה:
לא מתקיים
שיטת יעקבי מתכנסת לאט יותר משיטת גאוס–זיידל מכיוון שבגאוס–זיידל כבר משתמשים בפתרון המעודכן בעת ביצוע האיטרציות.
השגיאה באיטרציה
:
![{\displaystyle \varepsilon ^{(k+1)}=|x^{(k+1)}-x|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07687bd0678a8f89fd0ff233077702c18c336c0)
3) שיטת SOR – Successive Overrelaxation
האיטרציה הכללית בשיטת גאוס–זיידל:
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcdcd5ec687cc3fb3429c47736bda58973fc5631)
נוציא מהביטוי המסומן באדום את האיבר הראשון ונקבל:
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d0ff0450494f15f1d8a29912c9c217e32629910)
הנוסחה הכללית לאיטרציה בשיטה זו:
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34eed59d047160e4081a8cdca61440281d034830)
הוא פרמטר לגודל הצעד בין האיטרציות.
עבור גאוס–זיידל.
השיטה תקרא underrelaxation והיא מתכנסת לעתים גם כאשר גאוס–זיידל לא מתכנסת (הצעדים בשיטה זו הם קטנים יותר).
השיטה תקרא overrelaxation והיא עשויה להאיץ התכנסות בהם גאוס–זיידל מתכנסת, במידה והמטריצה נשלטת אלכסונית.
או
שיטת SOR לא תתכנס.