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

שגיאה ביצירת תמונה ממוזערת:

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

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

תיאור

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

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

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

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

ניסוח מתמטי

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

שגיאה ביצירת תמונה ממוזערת:

הדמיה של שיטת ניוטון

תהי $f:[a,b]\rightarrow \mathbb {R}$ פונקציה גזירה בקטע $[a,b]$. נתחיל את האיטרציה מהנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} . שיפוע המשיק לפונקציה בנקודה זו הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'\left(x_0\right)} .

אם כך, אנחנו מחפשים את משוואת הישר שעובר דרך הנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(x_0,f(x_0)\right)} ושיפועו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'\left(x_0\right)} . זהו למעשה הקירוב הליניארי לפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f} בנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} . על פי הגאומטריה האנליטית נקבל שמשוואה זו היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y-f(x_0)=f'\left(x_0\right)(x-x_0)} . מאחר שאנו מחפשים את החיתוך של ישר זה עם ציר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , נציב $y=0$ ונקבל, לאחר העברת אגפים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1=x_0-\frac{f(x_0)}{f'(x_0)}} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} הוא נקודת החיתוך המבוקשת.

נסתכל כעת בסדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{x_n\right\}_{n=0}^\infty} המוגדרת רקורסיבית על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}} סדרה זו מתכנסת לשורש המבוקש, בהינתן בחירה מתאימה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} .

דוגמאות

נראה כיצד ניתן להשתמש בשיטה זו כדי לחשב בקלות שורשים. נניח כי אנו רוצים לחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{a}} עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a>0} כלשהו. מספר זה הוא השורש החיובי של הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)=x^2-a} . נגזור ונקבל $f'(x)=2x$. בתור אבר ראשון באיטרציה נבחר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} עצמו (ניתן להוכיח כי בבחירה זו מובטח שהשיטה תיתן את הפתרון). כלומר, נביט בסדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{x_n\right\}_{n=0}^\infty} המוגדרת כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0=a}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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. במספר איטרציות גדול יותר, השיטה עובדת עבור כל מספר ממשי חיובי.

נדגים עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{2}} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0=2}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1=\frac{2}{2}+\frac{2}{4}=\frac{3}{2}=1.5}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2=\frac{\frac{3}{2}}{2}+\frac{2}{\frac{6}{2}}=\frac{17}{12}=1.416666667}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3=\frac{\frac{17}{12}}{2}+\frac{2}{\frac{34}{12}}=1\frac{169}{408}=1.414215686}

$x_{4}=1.414213562$

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

דוגמה נוספת, מעט יותר מסובכת: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(x)=x^x-2=e^{x \ln x}-2} :

הנגזרת היא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (\ln x+1)e^{x \ln x}} .

נסמן: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0=2}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1=\frac{2}{1}-\frac{2}{6.77}=1.704691945}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2=\frac{1.704}{1}-\frac{0.48}{3.8}=1.577944557}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3=\frac{1.5779}{1}-\frac{0.0538}{2.99}=1.559924538}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_4=\frac{1.5599}{1}-\frac{0.000907}{2.89}=1.559610563}

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

התכנסות

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

תהא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} גזירה פעמיים ברציפות בקטע $[a,b]$, יש לה שורש יחיד בקטע זה - הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} , ונניח שהנגזרת והנגזרת השנייה אינן משנות סימן בקטע. אם כל הערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_0-c), f'(x), f''(x)} הם חיוביים, או ששניים מהם שליליים והשלישי חיובי, אז האיטרציה מתכנסת לפתרון.

במקרים אלו ניתן גם לתחום את גודל השגיאה, על ידי אי השוויון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_{n+1}-c|\le\frac{M}{2m}(x_{n+1}-x_n)^2} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=\sup_{a<x<b}|f''(x)|,\, m=\inf_{a<x<b}|f'(x)|} .

הוכחה

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

חלק א: הוכחת התכנסות

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{x_n\right\}_{n=0}^\infty} הסדרה המתקבלת מאיטרצית ניוטון. נניח כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n>c} . כעת נפתח את טור טיילור של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} סביב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n} , עם טעות מסדר שני:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}=$

כעת נשתמש בהגדרת הסדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{x_n\right\}_{n=0}^\infty} ונקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle =f'(x_n)(c-x_{n+1})+\frac{f''(\xi)}{2}(c-x_n)^2=0}

נעביר אגפים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'(x_n)(x_{n+1}-c)=\frac{f''(\xi)}{2}(c-x_n)^2}

כעת נזכור כי על פי הנתון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f''(x)>0} ולכן הביטוי באגף ימין חיובי. מכאן כי גם הביטוי באגף שמאל חייב להיות חיובי. על פי הנתון, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'(x)>0} ולכן בהכרח מתקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1}-c>0} כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1}>c}

הראינו שהסדרה חסומה מלרע על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \,c} . כעת נראה שזו סדרה יורדת: על פי הנוסחה ידוע כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}} . הנגזרת חיובית, כלומר הפונקציה עולה בקטע, ומאחר ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n>c} הרי ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_n)>f(c)=0} ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{f(x_n)}{f'(x_n)}>0} ומכאן שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1}<x_n} . הראינו שהסדרה יורדת.

משפט בסיסי באנליזה קובע כי סדרה יורדת וחסומה מלרע מתכנסת לגבול. אם כן, נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{n \to \infty}x_n=L} . אז מתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{n \to \infty}x_n=\lim_{n \to \infty}x_{n+1}} ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L=L-\frac{f(L)}{f'(L)}} ונקבל מיידית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(L)=0} . מכיוון ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} הוא השורש היחיד בקטע, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L=c} . הראינו שהסדרה מתכנסת אל השורש המבוקש.

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

נפתח הפעם את טור טיילור של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1}} סביב הנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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=}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle =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=}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle =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}

כעת, לפי משפט הערך הממוצע של לגראנז' קיימת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta\in(c,x_{n+1})} המקיימת:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{f(x_{n+1})-f(c)}{x_{n+1}-c}=f'(\eta)} וקיבלנו:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1}-c=\frac{f(x_{n+1})}{f'(\eta)}} . כעת נציב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\left(x_{n+1}\right)} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 פרסם המתמטיקאי ארתור קיילי לראשונה הכללה של השיטה לפונקציות מרוכבות.

בדומה, ניתן להכליל את השיטה גם לשדות סקלריים, באמצעות כלל הנסיגה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1} = x_n - \left(\mathbf{J}_f(x_n)\right)^{-1}f(x_n)} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{J}_f(\mathbf{x}_n)} הוא מטריצת יעקבי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} בנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{x}_n} .

לאופטימיזציה

במקרים רבים, אופטימיזציה מצריכה מציאת נגזרת של פונקציה והשוואתה לאפס. דרך אחת לבצע זאת היא על ידי שיטת ניוטון-רפסון לנגזרת. במילים אחרות, תחת קיומה של נגזרת שנייה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} ותנאים טכניים נוספים, הסדרה שמוגדרת על ידי כלל הנסיגה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1} = x_n - \frac{f'\left(x_n\right)}{f''\left(x_n\right)}} מתכנסת לנקודת קיצון של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} .

קיימת הרחבה גם של שיטה זו לממדים גבוהים יותר.

השוואה לשיטות אחרות

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

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

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

אם השורש הוא בעל ריבוי גדול מ-1, השיטה תתכנס, אך קצב ההתכנסות לא יהיה ריבועי, אלא ליניארי (סדר ההתכנסות הוא 1). אם השורש הוא מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} השיטה האיטרטיבית המוגדרת על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{n+1}=x_n-m\frac{f(x_n)}{f'(x_n)}} תתכנס, וקצב ההתכנסות יהיה ריבועי.

קישורים חיצוניים

מדיה וקבצים בנושא שיטת ניוטון-רפסון בוויקישיתוף

• שיטת ניוטון-רפסון, באתר MathWorld (באנגלית)   
• שיטת ניוטון רפסון במחשבון, סרטון באתר יוטיוב

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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