מבוא לשיטות נומריות/משוואות דיפרנציאליות רגילות

הקדמה:

- פתרון אנליטי נותן פונקציה $\ f(x)$

- פתרון נומרי נותן ערכים בנקודות מסויימות.

סוגי בעיות:

א) בעיית מד"ר מסדר ראשון:

1) שיטת אויילר.

2) שיטות סתומות.

3) שיטת קרנק-ניקולסון.

4) שיטת הנקודה המרכזית.

5) שיטת אויילר המשופרת.

ב) בעיית מד"ר מסדר שני או גבוה יותר:

• שיטת רונגה-טונגה.

ג) בעיית מערכת משוואות דיפרנציאליות:

• שימוש בשיטת אויילר.

ד) בעיית תנאי שפה (תנאי גבול)

1) shooting method.

2) הפרשים סופיים.

בעיית מד"ר מסדר ראשון

• צורה כללית: $\ {\frac {dy}{dx}}=f(x,y(x))$

• ת. התכולה: $\ y(x_{0})=y_{0}$

1) שיטת אויילר

דרך א:

• קירוב טיילור מסדר ראשון סביב $\ x_{0}$:

$\ y(x)=y(x_{0})+(x-x_{0}){\frac {dy}{dx}}(x_{0})$

• אנו רוצים את הערך בנקודה הבאה $\ \Leftarrow x_{1}=x_{0}+h$ נציב:

$\ y(x_{1})=y(x_{0})+(x_{1}-x_{0}){\frac {dy}{dx}}(x_{0})$

• הביטוי הכללי:

$\ y(x_{i+1})=y_{i}+f(x_{i},y_{i})\cdot h+O(h^{2})$

כאשר $\ O(h^{2})$ היא השגיאה.

דרך ב:

• במקום קירוב טיילור נבצע נגזרת קדמית:

$\ {\frac {dy}{dx}}(x_{i})={\frac {y(x_{i}+h)-y(x_{i})}{h}}={\frac {y(x_{i+1}-y(x_{i})}{h}}$

• הביטוי הכללי:

$\ y(x_{i+1})=y_{i}+f(x_{i},y_{i})\cdot h+O(h^{2})$

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

2) שיטות (סכמות) סתומות:

• בדומה לאוילר נחשב נגזרת אך ע"י צעד אחורנית:

$\ {\frac {dy}{dx}}(x_{i}+1)={\frac {y(x_{i+1})-y(x_{i})}{h}}$

$\ y_{i+1}=y(x_{i})+f(x_{i+1},y_{i+1})h$

• הבעייה בשיטה זו: הנעלם $\ y_{i+1}$ מופיע משני צידי המשוואה ולכן מדובר במשוואה סתומה.

3) שיטת קרנק-ניקולסון

• נחשב נגזרת ע"י קירוב מרכזי:

$\ {\frac {dy}{dx}}(x_{i+1/2})={\frac {y(x_{i+1})-y(x_{i})}{2\cdot {\frac {h}{2}}}}$

$\ {\frac {y(x_{i+1})-y(x_{i})}{h}}=f(x_{i+1/2},y_{i+1/2})$

• כעת נמצע:

$\ ={\frac {f(x_{i},y_{i})+f(x_{i+1},y_{i+1})}{2}}$

• נבודד את $\ y(x_{i+1})$

$\ y(x_{i+1})=y(x_{i})+{\frac {1}{2h}}[f(x_{i},y_{i})+f(x_{i+1},y_{i+1})]$

• גם בשיטה זו ישנה בעייתיות כי הנעלם $\ y(x_{i+1})$ מופיע משני צידי המשוואה ולכן מדובר במשוואה סתומה.

יציבות

• באופן כלי לשיטות סתומות תכונות יציבות-פתרון טובות יותר.

• שגיאות מצעדים קודמים אינן גדולות מצעד לצעד בפתרון.

• שיפורים לשיטת אויילר:

- קירוב טיילור מסדר גבוה (בעיה: הנגזרות של $\ f(x,y)$ עלולות להיות מסובכות.

- הקטנת h גודל הצעד (בעיה: מספר החישובים גדל, שגיאות עיגול).

- קירוב יותר טוב לשיפוע הנגזרת הראשונה (אויילר משתמש בקירוב קדמי).

4) שיטת הנקודה המרכזית

• כמו בשיטת קרנק-ניקולסון, נחשב נגזרת ע"י קירוב מרכזי:

$\ {\frac {y(x_{i+1})-y(x_{i})}{h}}=f(x_{i+1/2},y_{i+1/2})$

$\ y(x_{i+1})=y(x_{i})+hf(x_{i+1/2},y_{i+1/2})$

• ונחשב את $\ y_{i+1/2}$ לפי שיטת אויילר:

$\ y_{i+1/2}=y_{i}+{\frac {h}{2}}f(x_{i},y_{i})$

• אנו בעצם מחשבים את הנקודה החדשה ע"י ערך הנגזרת באמצע הקטע.

5) שיטת אויילר המשופרת

• שלבי פתרון:

1) לפי אויילר: $\ y_{i+1}^{0}=y_{i}+f(x_{i},y_{i})\cdot h$

2) נגדיר k=0.

3) חישוב השיפוע הממוצע: $\ {\bar {f}}_{i}^{k}={\frac {f(x_{i},y_{i})+f(x_{i+1},y_{i+1}^{k})}{2}}$

4) לפי קרנק-ניקולסון: תיקון הנקודה החדשה. $\ y_{i+1}^{(k+1)}=y_{i}+{\bar {f}}_{i}^{k}\cdot h$

5) k=k+1.

6) לולאה, חזרה לשלב 3.

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

• סדר גודל השגיאה בשיטה זו ובשיטת הנקודה המרכזית הוא מקומית $\ O(h^{3})$, גלובלית $\ O(h^{2})$

הקטנת הצעד משפרת דיוק.

ב) בעיית מד"ר מסדר שני או גבוה יותר

• צורה כללית: $\ {\frac {d^{2}y}{dx^{2}}}=f(x,y(x),y'(x))$

• תאנים - 2 תנאים נתונים באותה נקודה: $\ y(x_{0})=y_{0}\quad ,\quad y'(x_{0})=y_{0}*$

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

• הביטוי הכללי: $\ y_{i+1}=y_{i}+\Phi (x_{i},y_{i},h)\cdot h$

• הפונקציה $\ \Phi (y_{i},x_{i},h)$ מבטאת את השיפוע הממוצע.

עבור שיטה מסדר n: $\ \Phi (x_{i},y_{i},h)=a_{1}k+1+a_{2}k_{2}+\cdots +a_{n}k_{n}$

כאשר ישנם n נעלמים:

$\ k_{1}=f(x_{i},y_{i})$

$\ k_{2}=f(x_{i}+b_{1}h,y_{i}+c_{1}1k_{1}h)$

$\ \vdots$

$\ k_{n}=f(x_{i}+b_{n-1}\cdot h,y_{i}+c_{n-1,1}k_{1}h+c_{n-1,2}k_{2}h+\cdots +c_{n-1,n-1}k_{n-1}h)$

• עבור בעיה מסדר שני:

$\ y_{i+1}=y_{i}+(a_{1}k_{1}+a_{2}k_{2})h$

$\ k_{1}=f(x_{i},y_{i})$

$\ k_{2}=f(x_{i}+b_{1}h,y_{i}+c_{1}k_{1}h)$

תנאים לפרמטרים: $\ a_{1}+a_{2}=2b_{1}a_{2}=2c_{1}a_{2}=1$

- לפי אוילר המשופר: $\ a_{1}={\frac {1}{2}},a_{2}={\frac {1}{2}}$

- לפי נקודה מרכזית: $\ a_{1}=0,a_{2}=1$

• ניתן לפתור מד"ר מסדר גבוה ע"י הגדרת הבעיה מחדש במערכת משוואות מסדר I:

$\ {\begin{matrix}Z_{1}=y\\Z_{2}=y'\\Z_{3}=y''\\\vdots \\Z_{n}=y^{n-1}\end{matrix}}$

$\ \Leftarrow$ נפתור n משוואות מסדר I $\ \Leftarrow$

$\ {\begin{matrix}Z_{1}'=Z_{2}\\Z_{2}'=Z_{3}\\\vdots \\Z'_{n-1}=Z_{n}\\Z'_{n}=f(x,Z_{1},Z_{2},\cdots ,Z_{n})\end{matrix}}$

• דוגמא למד"ר מסדר II:

$\ {\frac {d^{2}y}{dx^{2}}}=f(x,y,y')$

$\ y(x_{0})=y_{0}\quad ,\quad y'(x_{0})=y_{0}'$

$\ Z_{1}=y\ quad,\quad Z_{2}=y'$

$\ Z_{1}'=Z_{2}=y'\quad ,\quad Z'_{2}=y''=f(x,Z_{1},Z_{2})$

תנאי התחלה: $\ Z_{1,0}=y_{0},z_{2,0}=y'_{0}$

ג) בעיית מערכת משוואות דיפרנציאליות:

• צורה כללית:

$\ y'_{1}=f_{1}(x,y_{1},y_{2},\cdots ,y_{n})$

$\ y'_{2}=f_{2}(x,y_{1},y_{2},\cdots ,y_{n})$

$\ \vdots$

$\ y'_{n}=f_{n}(x,y_{1},y_{2},\cdots ,y_{n})$

• תנאי התחלה:

$\ y_{1}(x_{0})=y_{1,0}$

$\ y_{2}(x_{0})=y_{2,0}$

$\ \vdots$

$\ y_{n}(x_{0})=y_{n,0}$

• הפתרון: n פונקציות

$\ y_{1}(x)$

$\ y_{2}(x)$

$\ \vdots$

$\ y_{n}(x)$

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

$\ =y_{1,i}+f_{1}(x_{i},y_{1,i},y_{2,i},\cdots ,y_{n,i})\cdot h$

$\ =y_{2,i}+f_{2}(x_{i},y_{1,i},y_{2,i},\cdots ,y_{n,i})\cdot h$

$\ \vdots$

$\ =y_{n,i}+f_{n}(x_{i},y_{1,i},y_{2,i},\cdots ,y_{n,i})\cdot h$

• בכתיב מטריציאלי:

- הבעיה: $\ Y'=f(x,Y(x)),Y(x_{0})=Y_{0}$

- הפתרון:

$\ Y=[y_{1},y_{2},\cdots ,y_{n}]^{T}$

$\ Y_{0}=[y_{1,0},y_{2,0},\cdots ,y_{n,0}]$

$\ Y_{i+1}=Y_{i}+f(x_{i},Y(x_{i}))h$

3) בעיית תנאי שפה:

• צורה כללית: $\ y=f(x,y,y)$

• תנאי התחלה:

$\ a\neq b$ הערכים של תנאי ההתחלה אינם באותה נקודה כמו שהיה עד כה.

$\ y(a)=y_{a}\quad ,\quad y(b)=y_{b}$

1) שיטת shooting method - ניחוש ותיקון ערכים התחלתיים.

• שלבי פתרון:

1) הנח תנאים התחלתיים.

2) פתרון בעיית הערך ההתחלתי.

3) חישוב תנאי הגבול שהתקבלו.

4) תיקון התנאים ההתחלתיים.

5) חזרה לשלב 2 בלולאה.

• כיצד מתקנים את התנאים ההתחלתיים? (שלב 4)

- מנחשים תנאים התחלתיים (שלב 1) ומתאימים עקום אינטרפולציה לשם תיקונם.

- פותרים את המשוואה הלא לינארית

$\ BC-g(IV)=0$

כאשר BC הוא תנאי הגבול - boundry conditions

ו- I הוא עקום האינטרפולציה של התנאים ההתחלתיים שניחשנו $\ g(InitialValue)$

2) שיטת ההפרשים הסופיים

• נבטא את הנגזרת השניה באמצעות "קירוב לנגזרת שנייה" (מפרק גזירה נומרית)

$\ y_{i-1}-2y_{i}+y_{i+1}=h^{2}\cdot y''=h^{2}\cdot f(x_{i},y_{i})$

• משוואה זו מוגדרת עבור הנקודות הפנימיות בלבד ולא עבור נקודות שפה (כי היא מצריכה גם צעד קדימה וגם צעד אחורה) ולכן עבור n+1 משתנים תתקבלנה n-1 משוואות.

$\ y_{0}-2y_{1}+y_{2}=h^{2}\cdot f(x_{1},y_{1})$ - נקודה 1

$\ \vdots$

$\ y_{n-2}-2y_{n-1}+y_{n}=h^{2}\cdot f(x_{n-1},y_{n-1})$ - נקודה n-1

• דרושות עוד 2 משוואות לפתרון:

- מקרה I: תנאי דריכילה: מוסיפים את שני תנאי השפה למשוואות: $\ y(a)=y_{a}\quad ,\quad y(b)=y_{b}$

- מקרה II: תנאי ניומן: תנאי גבול הנתונים באמצעות נגזרות: $\ y'(x_{0})=y_{0}'\quad ,\quad y'(x_{N})=y_{N}'$

• מוסיפים שתי משוואות שהן קירוב לנגזרת:

1. קירוב קדמי/ אחורי: $\ y_{N}'={\frac {y_{N}-y_{N-1}}{h}}$

חסרון: שגיאת הקיטוע גדולה יותר: $\ y_{0}'={\frac {y_{1}-y_{2}}{h}}$

2. קירוב נגזרת מרכזית: $\ y'_{N}={\frac {y_{N+1}-y_{N-1}}{2h}}$

חסרון: עלי להוסיף 2 משוואות כי נוספים כעת שני נעלמים: $\ x_{-1}\quad ,x_{N+1}$

$\ x_{0}mx_{N}$ הופכות להיות נקודות פנימיות.

נקודת דמי: חישוב נקודה נוספת מעבר לגבול

נוספו 2 משוואות מתנאי הגבול אבל נוספו 2 נעלמים חדשים $\ x_{-1},x_{N+1}$ ולכן יש צורך בעוד 2 משוואות:

$\ y_{N+1}=y_{N-1}+2h\cdot y_{N}'$

$\ y_{1}=y_{-1}+2h\cdot y'_{0}$\

3. קירוב קדמי או אחורי עם שגיאה מסדר גבוה יותר.

מתקבל על ידי קירוב טיילור מסדר II $\ y'_{N}={\frac {3y_{N}-4y_{N-1}+y_{N-2}}{2h}}$

וקירוב אחרוי לנגזרת השניה.

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

• לאחר שביטאנו n+1 משוואות עבור n+1 נעלמים, ניתן ליצור מטריצה תלת אלכסונית ולפתור באמצעות אלגוריתם תומאס.