הצגת המקור של הדף "מבוא לשיטות נומריות/מציאת שורשים של משוואה"

'''הקדמה:'''

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

* ההנחה: <math>\ f(x) </math> - פונקציה רציפה.

'''מתי:'''

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

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

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

'''שיטות פתרון:'''

<u>א) שיטות תחום:</u>

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

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


<u>ב) שיטות פתוחות:</u>

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

2) חיתוך.

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


<u> '''א) שיטת תחום:'''</u>


1) <u>חציית התחום:</u>

התקדמות על גרף הפונקציה עד מציאת שינוי סימן בין <math>\ [X_0 , X_1] </math>.
אז, בודקים את ערך הפונקציה במרכז <math>\ X_2 = \frac{X_0 + X_1}{2} </math> והמשך צמצום המרווח פי 2 עד להגעה לפתרון הקרוב ביותר לפי הקירוב הרצוי.

* שלבי פתרון:

1) מנחשים 2 פתרונות התחלתיים כך שסימני
<math>\ f(X_1) , f(X_2) </math>
הפוכים.

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

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

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


תיאור גרפי:

[[קובץ: Numeriot (4).png|center|thumb|250px|תיאור גרפי]]

פתרון התחלתי:
<math>\  f(X_1)<0, f(X_2) >0 </math>

<math>\ X_3=\frac{X_1+X_2}{2} , f(X_3)<0  \Rightarrow [X_3,X_2] </math>

<math>\ X_4=\frac{X_3+X_2}{2} , f(X_4)>0  \Rightarrow [X_3,X_4] </math>


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



התכנסות:

* <math>\ \epsilon_n </math>  הוא השגיאה בכל איטרציה <math>\ \epsilon^{(n)} < |X_2^{(n)}-X_1^{(n)}| </math>

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

* מדובר <u>בקצב התכנסות</u> לינארי  <math>\ k= \frac{1}{2} \quad , \quad R=1 </math>

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

<math>\ |\epsilon^{(n)}|\cong \left( \frac{1}{2} \right)^n |X_2^{(0)}-X_1^{(0)}| < \delta </math>

כאשר:

<math>\ \delta </math> - הדיוק הנדרש מאיתנו

<math>\ |X_2^{(0)}-X_1^{(0)}|  </math> - גודל התחום הראשון

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



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

 <div style="text-align: center;">
<math>\ n > \frac{log(|X_2^{(0)}-X_1^{(0)}|)-log \delta}{log 2} </math>
</div>



<u>יתרונות השיטה:</u> 
* איטרציות פשוטות מאוד.
* מספר האיטרציות הדרוש ידוע מראש.
* התכנסות מכל פתרון התחלתי.
* מקבלים גבולות תחום לפתרון בכל איטרציה.

<u>חסרונות השיטה:</u>
* דרושים 2 פתרונות התחלתיים.
* ההתכנסות הלינארית איטית יחסית.
* אינו מנצל מידע על הפונקציה.



<u>'''2) שיטת האינטרפולציה הלינארית'''</u>

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

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

<u>* משוואת הישר:</u> 

עבור 2 נקודות
<math>\ (X_1, f(X_1)) , (X_2, f(X_2)) </math> נרצה למצוא את הישר המחבר בינהן

<math>\ f(x) = ax+b </math>

<math>\ \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. </math>

<math>\ f(X_{new})=aX_{new}+b=0 </math>

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

<math>\ 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) </math>


* <u>האלגוריתם:</u>

1) נמצא שני פתרונות התחלתיים <math>\ X_1^{(0)},X_2^{(0)} </math> כך ש: <math>\ f(X_1^{(0)}) \cdot f(X_2^{(0)}) <0 </math>

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

<math>\ X_{new} = X_1 - \frac {X_2-X_1}{f(X_2)-f(X_1)} \cdot f(X_1) </math>

3) נחשב את <math>\ f(X_{new}) </math>

4)<u> עדכון הפתרון:</u>
* אם <math>\ f(X_{new})=0 </math> אז <math>\ X_{new} </math> הוא הפתרון המבוקש.
* אם <math>\ f(X_{new}) \cdot f(X_1^{(n)}) >0 </math> אז <math>\ X_{new} = X_1^{(n+1)} \quad , \quad X_2^{(n+1)}=X_2^{(n)} </math>
* אם <math>\ f(X_{new}) \cdot f(X_1^{(n)}) <0 </math> אז <math>\ X_1^{(n+1)} = X_1^{(n)} , X_2^{(n+1)}=X_{new} </math>



* תיאור גרפי:

[[קובץ:MyGraph2.jpg|center|thumb|250px|תיאור גרפי]]

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

[[קובץ:MyGraph3.jpg|center|thumb|250px|פונקציה שטוחה]]

ההפרש בין <math>\ f(X_i) </math> יהיה קטן, יתאים לתנאי <math>\ \epsilon </math> ויגרום למציאת פתרון שגוי.


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


<u>'''ב) שיטות פתוחות'''</u>

<u>'''1) שיטת ניטון-רפסון:'''</u>

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

* נפתח ביטוי למשיק ע"י קירוב טיילור מסדר ראשון:
<math>\ \hat{f}(x) = f(x_{0})+ \frac{df(x_{0})}{dx}(x-x_{0}) </math> - קירוב למשיק

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

<math>\ f(x_{0}) + f'(x_{0}) \cdot (x-x_{0})=0 </math>

<math>\ x= x_{0} - \frac{f(x_{0})}{f'(x_{0})} </math>



* האיטרציה הכללית:
 <math>\ x^{n+1}= x^{n} - \frac{f(x^{(n)})}{f'(x^{(n)})} </math>



* תיאור גרפי:

[[קובץ: Numeriot (2).png|center|thumb|250px|תיאור גרפי]]




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

[[קובץ: Numeriot (1).png|center|thumb|250px|תיאור גרפי]]


* התכנסות:

<math>\ \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)})}</math>



כאשר: 

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

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

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

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

* הפתרון עלול לא להתכנס כאשר <math>\ f'(x) \rightarrow 0 </math> בסביבת הפתרון.



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

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

* נשתמש בשני הפתרונות <u>האחרונים</u> שחושבו ונמתח בינהם מיתר.

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

* נציב ביטוי זה באיטרציה הכללית של ניוטון-רפסון:
<math>\ x^{(n+1)}= x^{(n)}-\frac{x^{(n)}-x^{(n-1)}}{f(x^{(n)})-f(x^{(n-1)})} </math>

<div style="text-align: center;">
   <math>\ x^{(n+1)}= x^{(n)}-\frac{x^{(n)}-x^{(n-1)}}{f(x^{(n)})-f(x^{(n-1)})}\cdot f(x^{(n)})  </math>
</div>
*משתמשים בשני הפתרונות <u>האחרונים</u> ולא בקצוות התחום.

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

* תיאור גרפי:

[[קובץ: Numeriot (3).png|center|thumb|250px|תיאור גרפי]]



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

[[קובץ: Numeriot (6).png|center|thumb|250px|תיאור גרפי]]




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

כאשר: 

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

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


* <u>קצב ההתכנסות:</u>

<math>\ \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}] </math>

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

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


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

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

* ניתן לבצע את הטרנספורמציה בדרכים רבות:
<math>\ f(x) = x^{3}+x=0 </math> 

<math>\ \rightarrow g(x)=x^{3}+x+x=x </math> 

* האיטרציה תבוצע לפי המשוואה:
<math>\ x_{(n+1)}=g(x_{(n)}) </math> 

*תיאור גרפי:

[[קובץ: Numeriot (8).png|center|thumb|250px|תיאור גרפי]]





* <u>שלבי הפתרון:</u>

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

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

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

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

[[קטגוריה:מבוא לשיטות נומריות]]