מבוא לשיטות נומריות/מציאת שורשים של משוואה

הקדמה:

• באמצעות איטרציות נרצה למצוא פתרון (שורשים) של משוואה.

• ההנחה: $\ f(x)$ - פונקציה רציפה.

מתי:

• כאשר הפתרון האנליטי לא קיים או קשה לחישוב.

• בעיות מינימום ומקסימום.

• כשלב בפתרון בעיות מורכבות יותר.

שיטות פתרון:

א) שיטות תחום:

1) חציית התחום.

2) אינטרפולציה לינארית.

ב) שיטות פתוחות:

1) ניוטון-רפסון.

2) חיתוך.

3) איטרציות רצופות.

א) שיטת תחום:

1) חציית התחום:

התקדמות על גרף הפונקציה עד מציאת שינוי סימן בין $\ [X_{0},X_{1}]$. אז, בודקים את ערך הפונקציה במרכז $\ X_{2}={\frac {X_{0}+X_{1}}{2}}$ והמשך צמצום המרווח פי 2 עד להגעה לפתרון הקרוב ביותר לפי הקירוב הרצוי.

• שלבי פתרון:

1) מנחשים 2 פתרונות התחלתיים כך שסימני $\ f(X_{1}),f(X_{2})$ הפוכים.

2) מבצעים איטרציות עוקבות $\ X_{new}={\frac {x_{1}+x_{2}}{2}}$

3) אם $\ f(x_{new})\cdot f(x_{1})<0$ אז $\ X_{2}=X_{new}$

אם $\ f(x_{new})\cdot f(x_{1})>0$ אז $\ X_{1}=X_{new}$

תיאור גרפי:

תיאור גרפי

פתרון התחלתי: $\ f(X_{1})<0,f(X_{2})>0$

$\ X_{3}={\frac {X_{1}+X_{2}}{2}},f(X_{3})<0\Rightarrow [X_{3},X_{2}]$

$\ X_{4}={\frac {X_{3}+X_{2}}{2}},f(X_{4})>0\Rightarrow [X_{3},X_{4}]$

4) אם $\ f(X_{new})=0$ אז $\ X_{new}$ הוא הפתרון המבוקש ויש לעצור את האיטרציות.

התכנסות:

• $\ \epsilon _{n}$ הוא השגיאה בכל איטרציה $\ \epsilon ^{(n)}<|X_{2}^{(n)}-X_{1}^{(n)}|$

• בכל איטרציה תחום הפתרון קטן בחצי ולכן ניתן לרשום: $\ {\frac {|\epsilon ^{(n+1)}|}{|\epsilon ^{(n)}|}}\cong {\frac {1}{2}}$

• מדובר בקצב התכנסות לינארי $\ k={\frac {1}{2}}\quad ,\quad R=1$

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

$\ |\epsilon ^{(n)}|\cong \left({\frac {1}{2}}\right)^{n}|X_{2}^{(0)}-X_{1}^{(0)}|<\delta$

כאשר:

$\ \delta$ - הדיוק הנדרש מאיתנו

$\ |X_{2}^{(0)}-X_{1}^{(0)}|$ - גודל התחום הראשון

n - מספר האיטרציות

נחלץ את n (מספר האיטרציות):

$\ n>{\frac {log(|X_{2}^{(0)}-X_{1}^{(0)}|)-log\delta }{log2}}$

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

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

חסרונות השיטה:

• דרושים 2 פתרונות התחלתיים.
• ההתכנסות הלינארית איטית יחסית.
• אינו מנצל מידע על הפונקציה.

2) שיטת האינטרפולציה הלינארית

דומה לשיטת חציית התחום, השוני הוא באופן חישוב הנקודה החדשה $\ X_{new}$.

נבצע אינטרפולציה לינארית של 2 הפתרונות הנוכחיים, קירוב לינארי של f(X) וחיפוש השורש של הקירוב.

* משוואת הישר:

עבור 2 נקודות $\ (X_{1},f(X_{1})),(X_{2},f(X_{2}))$ נרצה למצוא את הישר המחבר בינהן

$\ f(x)=ax+b$

$\ \left\{{\begin{matrix}f(X_{1})=aX_{1}+b\\f(X_{2})=aX_{2}+b\end{matrix}}\right.\Rightarrow \left\{{\begin{matrix}a={\frac {f(X_{1})-f(X_{2})}{X_{1}-X_{2}}}\\b={\frac {f(X_{2})\cdot X_{1}-f(X_{1})\cdot X_{2}}{X_{1}-X_{2}}}\end{matrix}}\right.$

$\ f(X_{new})=aX_{new}+b=0$

נקודת החיתוך של ישר זה עם ציר X:

$\ X_{new}=-{\frac {b}{a}}={\frac {f(X_{2})\cdot X_{1}-f(X_{1})\cdot X_{2}}{f(X_{2})-f(X_{1})}}=X_{1}-{\frac {X_{2}-X_{1}}{f(X_{2})-f(X_{1})}}\cdot f(X_{1})$

• האלגוריתם:

1) נמצא שני פתרונות התחלתיים $\ X_{1}^{(0)},X_{2}^{(0)}$ כך ש: $\ f(X_{1}^{(0)})\cdot f(X_{2}^{(0)})<0$

2) נחשב פתרון חדש (שהוא החיתוך עם ציר X של הישר המחבר בין 2 פתרונות התחלתיים אל:

$\ X_{new}=X_{1}-{\frac {X_{2}-X_{1}}{f(X_{2})-f(X_{1})}}\cdot f(X_{1})$

3) נחשב את $\ f(X_{new})$

4) עדכון הפתרון:

• אם $\ f(X_{new})=0$ אז $\ X_{new}$ הוא הפתרון המבוקש.
• אם $\ f(X_{new})\cdot f(X_{1}^{(n)})>0$ אז $\ X_{new}=X_{1}^{(n+1)}\quad ,\quad X_{2}^{(n+1)}=X_{2}^{(n)}$
• אם $\ f(X_{new})\cdot f(X_{1}^{(n)})<0$ אז $\ X_{1}^{(n+1)}=X_{1}^{(n)},X_{2}^{(n+1)}=X_{new}$

• תיאור גרפי:

תיאור גרפי

• השיטה לא עובדת עבור פונקציות "שטוחות":

פונקציה שטוחה

ההפרש בין $\ f(X_{i})$ יהיה קטן, יתאים לתנאי $\ \epsilon$ ויגרום למציאת פתרון שגוי.

התכנסות:

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

ב) שיטות פתוחות

1) שיטת ניטון-רפסון:

• נעביר משיק לפונקציה בנקודה $\ x_{0}$ , $\ x_{1}$ תוגדר כנקודת חיתוך המשיק עם ציר x.

• נפתח ביטוי למשיק ע"י קירוב טיילור מסדר ראשון:

$\ {\hat {f}}(x)=f(x_{0})+{\frac {df(x_{0})}{dx}}(x-x_{0})$ - קירוב למשיק

• נחשב את נקודת החיתוך עם ציר x של קירוב זה:

$\ f(x_{0})+f'(x_{0})\cdot (x-x_{0})=0$

$\ x=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}$

• האיטרציה הכללית:

$\ x^{n+1}=x^{n}-{\frac {f(x^{(n)})}{f'(x^{(n)})}}$

• תיאור גרפי:

תיאור גרפי

• הפתרון עלול להתבדר כאשר הנגזרת הראשונה קרובה לאפס:

תיאור גרפי

• התכנסות:

$\ \epsilon ^{(n+1)}=x^{(n+1)}-x^{*}=x^{(n)}-{\frac {f(x^{(n)})}{f'(x^{(n)})}}-x^{*}=\epsilon ^{(n)}-{\frac {f(x^{(n)})}{f'(x^{(n)})}}$

כאשר:

$\ x^{*}$ - הוא הפתרון האמיתי - לא ידוע.

$\ \epsilon ^{(n+1)}$ - השגיאה באיטרציה n+1.

• קצב ההתכנסות ריבועי (R=2)

$\ \epsilon ^{(n+1)}\cong {\frac {1}{2}}{\frac {f''(x^{*})}{f'(x^{*})}}\cdot [\epsilon ^{(n)}]^{2}=O[|\epsilon ^{(n)}|]^{2}$

• הפתרון עלול לא להתכנס כאשר $\ f'(x)\rightarrow 0$ בסביבת הפתרון.

2) שיטת החיתוך:

• בשיטת ניוטון-רפסון נאלצנו לחשב נגזרת - כעת נחפש קירוב אחר לביטוי השיפוע.

• נשתמש בשני הפתרונות האחרונים שחושבו ונמתח בינהם מיתר.

שיפוע המיתר: $\ f'(x^{(n)})={\frac {f(x^{(n)})-f(x^{(n-1)})}{x^{(n)}-x^{(n-1)}}}$

• נציב ביטוי זה באיטרציה הכללית של ניוטון-רפסון:

$\ x^{(n+1)}=x^{(n)}-{\frac {x^{(n)}-x^{(n-1)}}{f(x^{(n)})-f(x^{(n-1)})}}$

  $\ x^{(n+1)}=x^{(n)}-{\frac {x^{(n)}-x^{(n-1)}}{f(x^{(n)})-f(x^{(n-1)})}}\cdot f(x^{(n)})$

• משתמשים בשני הפתרונות האחרונים ולא בקצוות התחום.

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

• תיאור גרפי:

תיאור גרפי

• בדומה לשיטת ניוטון-רפסון הפתרון עלול להתבדר:

תיאור גרפי

• התכנסות: נפתח ביטוי לשגיאה עבור האיטרציה ה- n+1 (בדומה לשיטת ניוטון-רפסון): $\ \epsilon ^{(n+1)}=x^{(n+1)}-x^{*}$

כאשר:

$\ x^{*}$ - הפתרון האמיתי והלא ידוע.

$\ \epsilon ^{(n+1)}$ - הגדרת השגיאה.

• קצב ההתכנסות:

$\ \epsilon ^{(n+1)}\approx \left({\frac {1}{2}}\cdot {\frac {f''(x^{*})}{f'(x^{*})}}\right)^{0.618}\cdot [\epsilon ^{[n]}]^{1.618}=O[|\epsilon ^{(n)}|^{1.618}]$

• R > 1 : מדובר בהתכנסות סופר-לינארית.

• אם $\ 1>>|f(x_{n})-f(x_{n-1})|$ אז השיטה קורסת.

3) שיטת האיטרציות הרצופות - משמשת לבעיות מסובכות במיוחד.

• נגדיר פונקציה חדשה $\ x=g(x)$ שתהיה טרנספורמציה לבעיה הנתונה $\ f(x)=0$.

• ניתן לבצע את הטרנספורמציה בדרכים רבות:

$\ f(x)=x^{3}+x=0$

$\ \rightarrow g(x)=x^{3}+x+x=x$

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

$\ x_{(n+1)}=g(x_{(n)})$

• תיאור גרפי:

תיאור גרפי

• שלבי הפתרון:

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

2) עדכון הפתרון: $\ x^{(n+1)}=g(x^{(n)})$

• ההתכנסות של השיטה לינארית רק כאשר $\ |g'(x^{*})|<1$ - תנאי להתכנסות

• $\ \epsilon ^{(n+1)}=x^{(n+1)}-x^{*}=g(x^{(n)})-x^{*}$ - השגיאה באיטרציה ה- n+1