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

הקדמה: נרצה למצוא את וקטור הנעלמים $\ {\vec {x}}={\begin{pmatrix}x_{1}\\\vdots \\x_{n}\end{pmatrix}}$ שמקיים את כל n המשוואות:

$\ f_{1}(x_{1},\cdots ,x_{n})=0$

$\ \vdots$

$\ f_{n}(x_{1},\cdots ,x_{n})=0$

מתי:

- כשפותרים בעיות אופטימיזציה (מציאת מינימום/ מקסימום).

- פתרון משוואות דיפרנציאליות ע"י אלגוריתם נומרי.

- עבור משוואות כוחות בצירים שונים.

שיטות פתרון:

1) שיטת ניוטון

2) המרה לבעיית אופטימיזציה.

1) שיטת ניוטון:

קירוב טיילור עובר כל אחת מ- n המשוואות:

$\ {\color {Blue}f_{1}({\vec {x}}^{(k)})}+{\color {Red}\Sigma _{j=1}^{N}{\frac {\partial f_{1}({\vec {x}}^{(k)})}{\partial x_{j}}}}{\color {OliveGreen}(x_{j}^{(k+1)}-x_{j}^{(k)})}=0$

$\ \vdots$

$\ {\color {Blue}f_{N}({\vec {x}}^{(k)})}+{\color {Red}\Sigma _{j=1}^{N}{\frac {\partial f_{N}({\vec {x}}^{(k)})}{\partial x_{j}}}}{\color {OliveGreen}(x_{j}^{(k+1)}-x_{j}^{(k)})}=0$

החלק המסומן בכחול - [F] - הוא ערך הפונקציה בנקודה הנתונה $\ {\vec {x}}^{(k)}$

החלק המסומן באדום - [J] - מטריצת הנגזרות הראשונות של וקטור $\ {\vec {x}}^{(k)}$ (יעקוביאן)

החלק המסומן בירוק - זהו $\ [\Delta {\vec {X}}]$ : השינוי בפתרון בין האיטרציות העוקבות (גודל הצעד).

• בכתיב מטרציוני: $\ F+J\Delta {\vec {X}}=0$

$\ X^{k+1}=X^{k}+\Delta X\Rightarrow$

 $\ X^{k+1}=X^{k}-J^{-1}F$

שלבי פתרון:

1) מנחשים פתרון התחלתי $\ {\vec {x}}^{(0)}$

2) פותרים את מערכת המשוואות הלינאריות (מחשבים את $\ F(x^{(k)})$ ואת $\ J(x^{(k)})$ - הנגזרות).

3) נעדכן את הפתרון ונמצא את $\ {\vec {x}}^{(k+1)}$

$\ x_{1}^{(k+1)}=x_{1}^{(k)}+\Delta X_{1}^{(k)}$

$\ \vdots$

$\ x_{n}^{(k+1)}=x_{n}^{(k)}+\Delta X_{n}^{(k)}$

4) נחזור על צעדים 2-3 עד להשגת הדיוק הנדרש.

התנאי להתכנסות:

$\ ||{\vec {X}}^{k+1}-{\vec {X}}^{k}||={\sqrt {\Sigma _{J=1}^{n}(x_{j}^{k+1}-x_{j}^{k})^{2}}}<\epsilon$

$\ max||\Delta X||<\epsilon$

קריטריון התכנסות - נתון בגוף השאלה.

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

• התכנסות ריבועית

• חסרונות:

- דרושה נקודת התחלה טובה

- יש לחשב יעקוביאן [J] בכל איטרציה

- יש לפתור מערכת לינארית בכל איטרציה.

• סיבוכיות עבור כל איטרציה:

- $\ N^{2}$ עבור J ו- $\ N$ עבור F, סה"כ $\ N^{2}+N$ חישובי פונקציות.

- $\ O(N^{3})$ פעולות לפתרון המערכת הלינארית.

2) המרה לבעיית אופטימיזציה:

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

- נגדיר פונקציה חדשה $\ g({\vec {X}})$:

$\ g({\vec {X}})=g(x_{1},x_{2},...,x_{N})=\Sigma _{i=1}^{N}[f_{i}(x_{1},x_{2},...,x_{N})]^{2}$

- נדרוש $\ min_{x}g(x_{1},x_{2},...,x_{N})$ - פותרים באמצעות אלגוריתם נומרי לאופטימיזציה.

-יתרונות: אפשרות התכנסות גם מפתרון התחלתי לא טוב.

ניתן ליישם באמצעות פונקציית solver ב- Excel.