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

הקדמה:

- פתרון אנליטי נותן פונקציה $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) חישוב השיפוע הממוצע: ${\overline{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+{\overline{f}}_i^k\cdot h$

5) k=k+1.

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

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

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

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

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

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

• תאנים - 2 תנאים נתונים באותה נקודה: $y(x_0)=y_0,y^{\prime }(x_0)=y_0*$

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

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

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

עבור שיטה מסדר n: $\mathrm{\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)$

$⋮$

$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{array}{c}{Z}_1=y\\ Z_2=y^{\prime }\\ Z_3=y^{″}\\ ⋮\\ Z_n=y^{n-1}\end{array}$

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

$\begin{array}{c}{Z_1}^{\prime }=Z_2\\ {Z_2}^{\prime }=Z_3\\ ⋮\\ Z{\text{'}}_{n-1}=Z_n\\ Z{\text{'}}_n=f(x,Z_1,Z_2,\cdots ,Z_n)\end{array}$

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

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

$y(x_0)=y_0,y^{\prime }(x_0)={y_0}^{\prime }$

$Z_1=yquad,Z_2=y^{\prime }$

${Z_1}^{\prime }=Z_2=y^{\prime },Z{\text{'}}_2=y^{″}=f(x,Z_1,Z_2)$

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

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

• צורה כללית:

$y{\text{'}}_1=f_1(x,y_1,y_2,\cdots ,y_n)$

$y{\text{'}}_2=f_2(x,y_1,y_2,\cdots ,y_n)$

$⋮$

$y{\text{'}}_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}$

$⋮$

$y_n(x_0)=y_{n,0}$

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

$y_1(x)$

$y_2(x)$

$⋮$

$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$

$⋮$

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

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

- הבעיה: $Y^{\prime }=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\ne b$ הערכים של תנאי ההתחלה אינם באותה נקודה כמו שהיה עד כה.

$y(a)=y_a,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

$⋮$

$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,y(b)=y_b$

- מקרה II: תנאי ניומן: תנאי גבול הנתונים באמצעות נגזרות: $y^{\prime }(x_0)={y_0}^{\prime },y^{\prime }(x_N)={y_N}^{\prime }$

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

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

חסרון: שגיאת הקיטוע גדולה יותר: ${y_0}^{\prime }=\frac{y_1-y_2}{h}$

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

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

$x_{0}m{x}_N$ הופכות להיות נקודות פנימיות.

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

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

$y_{N+1}=y_{N-1}+2h\cdot {y_N}^{\prime }$

$y_1=y_{-1}+2h\cdot y{\text{'}}_0$\

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

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

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

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

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