הצגת המקור של הדף "מבוא לשיטות נומריות/פתרון מערכת משוואות לינאריות"

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

'''שיטות הפתרון:'''
#שיטת גאוס–זיידל
#שיטת יעקבי
#שיטת SOR – Succesive Over Relaxation

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

מערכת המשוואות תירשם כך:
:<math>\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}</math>
הפתרון ההתחלתי:
:<math>\vec x^{(0)}=\begin{pmatrix}x_1^{(0)}\\x_2^{(0)}\\x_3^{(0)}\end{pmatrix}</math>
*האינדקס העליון מציין את מספר האיטרציה.

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

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

נשתמש בפתרון העדכני ביותר בחישובים מאוחרים באיטרציה:
:<math>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}^na_{ij}x_j^{(k)}\right)</math>
*האינדקס המסומן באדום מציין את ההבדל משיטת יעקבי.
לדוגמא:
:<math>\begin{align}&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{align}</math>

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

עדכון הפתרון יבוצע ע"י האיטרציה הכללית:
:<math>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}^na_{ij}x_j^{(k)}\right)</math>
לדוגמא:
:<math>\begin{align}&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{align}</math>

*'''תנאי התכנסות לשיטה (שליטה אלכסונית):'''
:מדובר בתנאי מספיק אך לא הכרחי – השיטה עלולה להתכנס גם אם לא יתקיים, אך אם הוא מתקיים – השיטה בטוח תתכנס.
:<math>\sum_{i=1,j\ne i}^n|a_{ij}|\le|a_{ii}|</math>
הסבר:
:<math>\begin{pmatrix}\color{red}8&1&-1\\2&\color{red}1&9\\1&-7&\color{red}2\end{pmatrix}</math>
נוודא שכל אברי האלכסון גדולים, כל אחד, מסכום שאר האברים בשורה:

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

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


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

*התכנסות השיטה:
השגיאה באיטרציה <math>k+1</math> :
:<math>\varepsilon^{(k+1)}=|x^{(k+1)}-x|</math>

'''3) שיטת SOR – Successive Overrelaxation'''

האיטרציה הכללית בשיטת גאוס–זיידל:
:<math>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}^na_{ij}x_j^{(k)}\right)</math>
נוציא מהביטוי המסומן באדום את האיבר הראשון ונקבל:
:<math>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}^na_{ij}x_j^{(k)}\right)</math>
הנוסחה הכללית לאיטרציה בשיטה זו:
:<math>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}^na_{ij}x_j^{(k)}\right)</math>
*<math>\omega</math> הוא פרמטר לגודל הצעד בין האיטרציות. <math>\omega=1</math> עבור גאוס–זיידל.
*<math>0<\omega<1</math> השיטה תקרא underrelaxation והיא מתכנסת לעתים גם כאשר גאוס–זיידל לא מתכנסת (הצעדים בשיטה זו הם קטנים יותר).
*<math>1<\omega<2</math> השיטה תקרא overrelaxation והיא עשויה להאיץ התכנסות בהם גאוס–זיידל מתכנסת, במידה והמטריצה נשלטת אלכסונית.
*<math>\omega\ge2</math> או <math>\omega\le0</math> שיטת SOR לא תתכנס.

[[קטגוריה:מבוא לשיטות נומריות]]