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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Nuvola apps edu mathematics blue-p.svg

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

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

תיאור[עריכת קוד מקור | עריכה]

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

סדר הפעולות הוא כדלקמן:

  1. בחר נקודה קרובה לשורש שאתה מחפש.
  2. חשב את שיפוע המשיק לפונקציה בנקודה זו; זוהי הנגזרת של הפונקציה באותה נקודה.
  3. חשב את משוואת המשיק, באמצעות גאומטריה אנליטית.
  4. מצא את שורש המשיק, כלומר את הנקודה בה הוא חותך את ציר ה-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). זהו למעשה הקירוב הלינארי לפונקציה \ f בנקודה \!\,x_0. על פי הגאומטריה האנליטית נקבל שמשוואה זו היא 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)=x^x-2=e^{x \ln x}-2:

הנגזרת היא: \ (\ln x+1)e^{x \ln x}.

נסמן: \!\,x_0=2

x_1=\frac{2}{1}-\frac{2}{6.77}=1.704691945

x_2=\frac{1.704}{1}-\frac{0.48}{3.8}=1.577944557

x_3=\frac{1.5779}{1}-\frac{0.0538}{2.99}=1.559924538

x_4=\frac{1.5599}{1}-\frac{0.000907}{2.89}=1.559610563

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

הרחבה[עריכת קוד מקור | עריכה]

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

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

במקרים אלו ניתן גם לתחום את גודל השגיאה, על ידי אי השוויון |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 סביב \!\,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.

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

מעל המרוכבים[עריכת קוד מקור | עריכה]

בשנת 1879 פרסם המתמטיקאי ארתור קיילי לראשונה הכללה של השיטה לפונקציות מרוכבות.

השוואה לשיטות אחרות[עריכת קוד מקור | עריכה]

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

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

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

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