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

הקדמה: נרצה למצוא את וקטור הנעלמים $\overrightarrow{x}=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)$ שמקיים את כל n המשוואות:

$f_1(x_1,\cdots ,x_n)=0$

$⋮$

$f_n(x_1,\cdots ,x_n)=0$

מתי:

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

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

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

שיטות פתרון:

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

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

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

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

$f_1({\overrightarrow{x}}^{(k)})+{\mathrm{\Sigma }}_{j=1}^N\frac{\partial f_1({\overrightarrow{x}}^{(k)})}{\partial x_j}(x_j^{(k+1)}-x_j^{(k)})=0$

$⋮$

$f_N({\overrightarrow{x}}^{(k)})+{\mathrm{\Sigma }}_{j=1}^N\frac{\partial f_N({\overrightarrow{x}}^{(k)})}{\partial x_j}(x_j^{(k+1)}-x_j^{(k)})=0$

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

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

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

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

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

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

שלבי פתרון:

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

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

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

$x_1^{(k+1)}=x_1^{(k)}+\mathrm{\Delta }{X}_1^{(k)}$

$⋮$

$x_n^{(k+1)}=x_n^{(k)}+\mathrm{\Delta }{X}_n^{(k)}$

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

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

$||{\overrightarrow{X}}^{k+1}-{\overrightarrow{X}}^k||=\sqrt{{\mathrm{\Sigma }}_{J=1}^n(x_j^{k+1}-x_j^k{)}^2}<ϵ$

$max||\mathrm{\Delta }X||<ϵ$

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

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

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

• חסרונות:

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

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

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

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

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

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

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

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

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

$g(\overrightarrow{X})=g(x_1,x_2,...,x_N)={\mathrm{\Sigma }}_{i=1}^N[f_i(x_1,x_2,...,x_N){]}^2$

- נדרוש $mi{n}_{x}g(x_1,x_2,...,x_N)$ - פותרים באמצעות אלגוריתם נומרי לאופטימיזציה.

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

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