שיטת ניוטון-רפסון

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

תוכן עניינים

1 תיאור
2 ניסוח מתמטי
3 דוגמה
4 הרחבה
- 4.1 הוכחה
  - 4.1.1 חלק א: הוכחת התכנסות
  - 4.1.2 חלק ב': הוכחת הערכת השגיאה
5 השוואה לשיטות אחרות

[עריכה] תיאור

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

סדר הפעולות הוא כזה:

בחר נקודה שקרובה לשורש שאתה מחפש.
חשב את שיפוע המשיק לפונקציה בנקודה זו. זוהי הנגזרת של הפונקציה באותה נקודה.
חשב את משוואת המשיק, מה שנעשה בקלות באמצעות גאומטריה אנליטית.
מצא את שורש המשיק, כלומר את הנקודה שבה הוא חותך את ציר ה-x.

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

[עריכה] ניסוח מתמטי

תהי $f:[a,b]\rarr\R$ פונקציה גזירה בקטע $\!\,[a,b]$ . נתחיל את האיטרציה מהנקודה $\!\,x_0$ . שיפוע המשיק לפונקציה בנקודה זו הוא $f'\left(x_0\right)$ .

אם כך, אנחנו מחפשים את משוואת הישר שעובר דרך הנקודה $\left(x_0,f(x_0)\right)$ ושיפועו $f'\left(x_0\right)$ . על פי הגאומטריה האנליטית נקבל שמשוואה זו היא $y-f(x_0)=f'\left(x_0\right)(x-x_0)$ . מאחר שאנו מחפשים את החיתוך של ישר זה עם ציר $\!\,x$ , נציב $\!\,y=0$ ונקבל, לאחר העברת אגפים:

$x_1=x_0-\frac{f(x_0)}{f'(x_0)}$

כאשר $\!\,x_1$ הוא נק' החיתוך המבוקשת.

נסתכל כעת בסדרה $\left\{x_n\right\}_{n=0}^\infty$ המוגדרת רקורסיבית על ידי

$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$

סדרה זו מתכנסת לשורש המבוקש, בהינתן בחירה מתאימה של $\!\,x_0$ .

[עריכה] דוגמה

נראה כיצד ניתן להשתמש בשיטה זו כדי לחשב בקלות שורשים. נניח כי אנו רוצים לחשב את $\sqrt{a}$ עבור $\!\,a>0$ כלשהו. מספר זה הוא השורש החיובי של הפונקציה $\!\,f(x)=x^2-a$ . נגזור ונקבל $\!\,f'(x)=2x$ . בתור אבר ראשון באיטרציה נבחר את $\!\,a$ עצמו (ניתן להוכיח כי בבחירה זו מובטח שהשיטה תיתן את הפתרון). כלומר, נביט בסדרה $\left\{x_n\right\}_{n=0}^\infty$ המוגדרת כך:

$\!\,x_0=a$

$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n^2-a}{2x_n}=x_n-\frac{x_n}{2}+\frac{a}{2x_n}=\frac{x_n}{2}+\frac{a}{2x_n}$

בעזרת משוואה זו, תוך לכל היותר 10 איטרציות ניתן לחשב ערך מדויק עד 10 ספרות אחרי הנקודה של כל מספר עד 1,000. במספר איטרציות גדול יותר, השיטה עובדת עבור כל מספר ממשי חיובי.

נדגים עבור $\sqrt{2}$ :

$\!\,x_0=2$

$x_1=\frac{2}{2}+\frac{2}{4}=\frac{3}{2}=1.5$

$x_2=\frac{\frac{3}{2}}{2}+\frac{2}{\frac{6}{2}}=\frac{17}{12}=1.416666667$

$x_3=\frac{\frac{17}{12}}{2}+\frac{2}{\frac{34}{12}}=1\frac{169}{408}=1.414215686$

$\!\,x_4=1.414213562$

בתוך ארבע איטרציות הושג קירוב עם דיוק של 10 ספרות אחרי הנקודה.

[עריכה] הרחבה

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

תהא $\!\,f(x)$ גזירה פעמיים ברציפות בקטע $\!\,[a,b]$ , יש לה שורש יחיד בקטע $\!\,c$ ונבחר $x_0\isin[a,b]$ , אז האיטרציה תתכנס לפתרון במקרים הבאים:

$\forall x\isin[a,b] \ f'(x)>0 \ , \ f''(x)>0, \ x_0>c$
$\forall x\isin[a,b] \ f'(x)<0 \ , \ f''(x)<0, \ x_0>c$
$\forall x\isin[a,b] \ f'(x)<0 \ , \ f''(x)>0, \ x_0<c$
$\forall x\isin[a,b] \ f'(x)>0 \ , \ f''(x)<0, \ x_0<c$

במקרים אלו ניתן לתחום את גודל השגיאה, על ידי אי השוויון הבא:

$|x_{n+1}-c|\le\frac{M}{2m}(x_{n+1}-x_n)^2$

כאשר

$M=\sup_{a<x<b}|f''(x)|,m=\inf_{a<x<b}|f'(x)|$

[עריכה] הוכחה

ההוכחה מתבססת על שימוש בטור טיילור מסדר שני. נראה אותה עבור המקרה הראשון - עבור שאר המקרים הרעיון זהה.

[עריכה] חלק א: הוכחת התכנסות

תהי $\left\{x_n\right\}_{n=0}^\infty$ הסדרה המתקבלת מאיטרצית ניוטון. נניח כי $\!\,x_n>c$ . כעת נפתח את טור טיילור של $\!\,f(c)$ מסדר שני סביב $\!\,x_n$ :

$0=f(c)=f(x_n)+f'(x_n)(c-x_n)+\frac{f''(\xi)}{2}(c-x_n)^2=$

$=f'(x_n)\left(c-x_n+\frac{f(x_n)}{f'(x_n)}\right)+\frac{f''(\xi)}{2}(c-x_n)^2=$

כעת נשתמש בהגדרת הסדרה $\left\{x_n\right\}_{n=0}^\infty$ ונקבל:

$=f'(x_n)(c-x_{n+1})+\frac{f''(\xi)}{2}(c-x_n)^2=0$

נעביר אגפים:

$f'(x_n)(x_{n+1}-c)=\frac{f''(\xi)}{2}(c-x_n)^2$

כעת נזכור כי על פי הנתון $\!\,f''(x)>0$ ולכן הביטוי באגף ימין חיובי. מכאן כי גם הביטוי באגף שמאל חייב להיות חיובי. על פי הנתון, $\!\,f'(x)>0$ ולכן בהכרח מתקיים:

$\!\,x_{n+1}-c>0$ כלומר $\!\,x_{n+1}>c$

הראינו שהסדרה חסומה מלרע על ידי $\,c$ . כעת נראה שזו סדרה יורדת: על פי הנוסחה ידוע כי $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$ . הנגזרת חיובית, כלומר הפונקציה עולה בקטע, ומאחר ש- $\!\,x_n>c$ הרי ש- $\!\,f(x_n)>f(c)=0$ ולכן $\frac{f(x_n)}{f'(x_n)}>0$ ומכאן שמתקיים $\!\,x_{n+1}<x_n$ . הראינו שהסדרה יורדת.

כידוע, כל סדרה יורדת וחסומה מלרע מתכנסת לגבול. נסמן $\lim_{n \to \infty}x_n=L$ . אז מתקיים: $\lim_{n \to \infty}x_n=\lim_{n \to \infty}x_{n+1}$ ולכן $L=L-\frac{f(L)}{f'(L)}$ ונקבל מיידית $\!\,f(L)=0$ . מכיוון ש- $\!\,c$ הוא השורש היחיד בקטע, $\!\,L=c$ . הראינו שהסדרה מתכנסת אל השורש המבוקש.

[עריכה] חלק ב': הוכחת הערכת השגיאה

נפתח הפעם את טור טיילור של $\!\,x_{n+1}$ סביב הנקודה $\!\,x_n$ :

$f(x_{n+1})=f(x_n)+f'(x_n)(x_{n+1}-x_n)+\frac{f''(\xi)}{2}(x_{n+1}-x_n)^2=$

$=f'(x_n)\left(x_{n+1}-x_n+\frac{f(x_n)}{f'(x_n)}\right)+\frac{f''(\xi)}{2}(x_{n+1}-x_n)^2=$

$=f'(x_n)(x_{n+1}-x_{n+1})+\frac{f''(\xi)}{2}(x_{n+1}-x_n)^2=\frac{f''(\xi)}{2}(x_{n+1}-x_n)^2$

כעת, לפי משפט הערך הממוצע של לגראנז' קיימת $\!\,\eta\in(c,x_{n+1})$ המקיימת:

$\frac{f(x_{n+1})-f(c)}{x_{n+1}-c}=f'(\eta)$ וקיבלנו:

$x_{n+1}-c=\frac{f(x_{n+1})}{f'(\eta)}$ . כעת נציב את $f\left(x_{n+1}\right)$ :

$x_{n+1}-c=\frac{f''(\xi)}{2f'(\eta)}(x_{n+1}-x_n)^2<\frac{M}{2m}(x_{n+1}-x_n)^2$ .

וההוכחה הושלמה.

[עריכה] השוואה לשיטות אחרות

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

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

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

אם השורש הוא בעל ריבוי גדול מ-1, השיטה תתכנס, אך קצב ההתכנסות לא יהיה ריבועי, אלא לינארי (סדר ההתכנסות הוא 1). אם השורש הוא מסדר $\,m$ השיטה האיטרטיבית המוגדרת על-ידי $x_{n+1}=x_n-m\frac{f(x_n)}{f'(x_n)}$ תתכנס, וקצב ההתכנסות יהיה ריבועי.

חשבון אינפיניטסימלי
מושגי יסוד:	חשבון אינפיניטסימלי \| סדרה \| גבול \| סדרת קושי \| טור \| אינפיניטסימל \| שדה המספרים הממשיים \| ערך מוחלט \| אי-שוויון המשולש \| אי-שוויון קושי-שוורץ
פונקציות:	פונקציה \| גרף פונקציה \| פונקציה לינארית \| פונקציה מונוטונית \| נקודת קיצון \| פונקציה קעורה \| פונקציה קמורה \| פונקציה רציפה \| רציפות במידה שווה \| נקודת אי רציפות \| נגזרת \| טור טיילור \| סדרת פונקציות \| התכנסות במידה שווה
משפטים:	משפט בולצאנו-ויירשטראס \| משפטי ויירשטראס \| משפט קנטור \| משפט ערך הביניים \|משפט פרמה \| משפט רול \| משפט הערך הממוצע של לגראנז' \| משפט הערך הממוצע של קושי \| משפט דארבו \| כלל השרשרת \| כלל הסנדוויץ' \| כלל לופיטל \| משפט שטולץ \| אריתמטיקה של גבולות
האינטגרל:	אינטגרל \| המשפט היסודי של החשבון הדיפרנציאלי והאינטגרלי \| אינטגרציה בחלקים \| שיטות אינטגרציה
אנליזה מתקדמת:	פונקציה מרוכבת \| אנליזה וקטורית \| שיטת ניוטון-רפסון \| משוואה דיפרנציאלית \| טופולוגיה \| תורת המידה
אנליזה מתמטית - אנליזה וקטורית - טופולוגיה - אנליזה מרוכבת - אנליזה פונקציונלית - תורת המידה

מקור: http://he.wikipedia.org../../../%D7%A9/%D7%99/%D7%98/%D7%A9%D7%99%D7%98%D7%AA_%D7%A0%D7%99%D7%95%D7%98%D7%95%D7%9F-%D7%A8%D7%A4%D7%A1%D7%95%D7%9F.html

קטגוריות: אנליזה מתמטית | אנליזה נומרית | אלגוריתמים | שיטות למציאת שורשים

שיטת ניוטון-רפסון

מתוך ויקיפדיה, האנציקלופדיה החופשית

תוכן עניינים

[עריכה] תיאור

[עריכה] ניסוח מתמטי

[עריכה] דוגמה

[עריכה] הרחבה

[עריכה] הוכחה

[עריכה] חלק א: הוכחת התכנסות

[עריכה] חלק ב': הוכחת הערכת השגיאה

[עריכה] השוואה לשיטות אחרות

Views

ניווט

קהילה

חיפוש

שפות אחרות