הצגת המקור של הדף "שיטת ניוטון-רפסון"

[[קובץ:NewtonIteration Ani.gif|ממוזער|350px|שיטת ניוטון-רפסון היא [[שיטה איטרטיבית]] למציאת השורש של הפונקציה (בכחול), הנעשית באמצעות סדרת קירובים תוך שימוש במשיק (באדום)]]
'''שיטת ניוטון-רפסון''' (או '''כלל ניוטון''') היא [[אלגוריתם]] יעיל ב[[אנליזה נומרית]], למציאת [[שורש (של פונקציה)|שורשים]] של [[פונקציה ממשית]] כלשהי, דהיינו נקודות בהן הפונקציה מתאפסת. השיטה פותחה באופן בלתי תלוי בידי [[אייזק ניוטון]] וג'וזף רפסון.

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

סדר הפעולות בשיטת ניוטון רפסון הוא:
# בחירת נקודה קרובה לשורש המבוקש.
# חישוב שיפוע המשיק לפונקציה בנקודה זו; זוהי ה[[נגזרת]] של הפונקציה באותה נקודה.
# חישוב משוואת המשיק באמצעות [[גאומטריה אנליטית]].
# מציאת שורש המשיק, כלומר הנקודה בה המשיק חותך את ציר ה-x.

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

==ניסוח מתמטי==
{{סימון מתמטי}}
[[קובץ:newton_iteration.svg|ממוזער|שמאל|250px|הדמיה של שיטת ניוטון]]

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

אם כך, אנחנו מחפשים את משוואת הישר שעובר דרך הנקודה <math>\left(x_0,f(x_0)\right)</math> ושיפועו <math>f'\left(x_0\right)</math>. זהו למעשה ה[[קירוב ליניארי|קירוב הליניארי]] לפונקציה <math>\ f</math> בנקודה <math>x_0</math>. על פי הגאומטריה האנליטית נקבל שמשוואה זו היא <math>y-f(x_0)=f'\left(x_0\right)(x-x_0)</math>. מאחר שאנו מחפשים את החיתוך של ישר זה עם ציר <math>x</math>, נציב <math>y=0</math> ונקבל, לאחר העברת אגפים:
<math display="block">x_1=x_0-\frac{f(x_0)}{f'(x_0)}</math>
כאשר <math>x_1</math> הוא נקודת החיתוך המבוקשת.

נסתכל כעת בסדרה <math>\left\{x_n\right\}_{n=0}^\infty</math> המוגדרת רקורסיבית על ידי
<math display="block">x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}</math>
סדרה זו מתכנסת לשורש המבוקש, בהינתן בחירה מתאימה של <math>x_0</math>.

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

<math>x_0=a</math>

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

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

נדגים עבור <math>\sqrt{2}</math>:

<math>x_0=2</math>

<math>x_1=\frac{2}{2}+\frac{2}{4}=\frac{3}{2}=1.5</math>

<math>x_2=\frac{\frac{3}{2}}{2}+\frac{2}{\frac{6}{2}}=\frac{17}{12}=1.416666667</math>

<math>x_3=\frac{\frac{17}{12}}{2}+\frac{2}{\frac{34}{12}}=1\frac{169}{408}=1.414215686</math>

<math>x_4=1.414213562</math>

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

דוגמה נוספת, מעט יותר מסובכת: <math>\ f(x)=x^x-2=e^{x \ln x}-2</math>:

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

נסמן: <math>x_0=2</math>

<math>x_1=\frac{2}{1}-\frac{2}{6.77}=1.704691945</math>

<math>x_2=\frac{1.704}{1}-\frac{0.48}{3.8}=1.577944557</math>

<math>x_3=\frac{1.5779}{1}-\frac{0.0538}{2.99}=1.559924538</math>

<math>x_4=\frac{1.5599}{1}-\frac{0.000907}{2.89}=1.559610563</math>

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

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

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

במקרים אלו ניתן גם לתחום את גודל השגיאה, על ידי אי השוויון
<math>|x_{n+1}-c|\le\frac{M}{2m}(x_{n+1}-x_n)^2</math>
כאשר
<math>M=\sup_{a<x<b}|f''(x)|,\, m=\inf_{a<x<b}|f'(x)|</math>.

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

====חלק א: הוכחת התכנסות====
תהי <math>\left\{x_n\right\}_{n=0}^\infty</math> הסדרה המתקבלת מאיטרצית ניוטון. נניח כי <math>x_n>c</math>. כעת נפתח את טור טיילור של <math>f</math> סביב <math>x_n</math>, עם טעות מסדר שני:
<center>
<math>0=f(c)=f(x_n)+f'(x_n)(c-x_n)+\frac{f''(\xi)}{2}(c-x_n)^2=
</math>

<math>
=f'(x_n)\left(c-x_n+\frac{f(x_n)}{f'(x_n)}\right)+\frac{f''(\xi)}{2}(c-x_n)^2=</math>
</center>

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

<center>
<math>=f'(x_n)(c-x_{n+1})+\frac{f''(\xi)}{2}(c-x_n)^2=0</math>
</center>

נעביר אגפים:

<center>
<math>f'(x_n)(x_{n+1}-c)=\frac{f''(\xi)}{2}(c-x_n)^2</math>
</center>

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

<math>x_{n+1}-c>0</math> כלומר <math>x_{n+1}>c</math>

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

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

====חלק ב': הוכחת הערכת השגיאה====
נפתח הפעם את טור טיילור של <math>x_{n+1}</math> סביב הנקודה <math>x_n</math>:

<math>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=</math>

<math>=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=</math>

<math>=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</math>

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

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

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

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

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

==הכללות==

=== לפונקציות מרוכבות ===
בשנת [[1879]] פרסם המתמטיקאי [[ארתור קיילי]] לראשונה הכללה של השיטה ל[[פונקציה מרוכבת|פונקציות מרוכבות]].
[[קובץ:Newtroot 1 0 0 0 0 m1.png|ממוזער|נקודות משיכה עבור <math>x^5-1=0</math>. נקודות כהות יותר משמעותן כי נדרשות יותר איטרציות כדי להתכנס.]]
כאשר עוסקים בפונקציות מורכבות, ניתן ליישם ישירות את שיטת ניוטון כדי למצוא את האפסים שלהן<ref>{{צ-ספר|מחבר=Peter Henrici|שם=Applied and Computational Complex Analysis|שנת הוצאה=1974}}</ref>. לכל אפס יש נקודת משיכה במישור המרוכב, קבוצת כל ערכי ההתחלה שגורמים לשיטה להתכנס לאפס המסוים הזה. ניתן למפות קבוצות כאלה כמו בתמונה המוצגת. עבור פונקציות מורכבות רבות, גבולות אגני המשיכה הם [[פרקטל|פרקטלים]].

במקרים מסוימים ישנם אזורים במישור המורכב שאינם נמצאים באף אחד מאגני המשיכה הללו, כלומר האיטרציות אינן מתכנסות. לדוגמה<ref>{{צ-מאמר|שם=A Chaotic Search for i|קישור=https://doi.org/10.1080/07468342.1991.11973353|כתב עת=The College Mathematics Journal|שנת הוצאה=1991-01-01|עמ=3–12|כרך=22|doi=10.1080/07468342.1991.11973353|מחבר=Gilbert Strang}}</ref>, אם משתמשים בתנאי התחלתי ממשי כדי לחפש שורש של <math>x^2+1</math>, כל האיטרציות הבאות יהיו מספרים ממשיים ולכן האיטרציות לא יכולות להתכנס לאף אחד מהשורשים, מכיוון ששני השורשים אינם ממשיים. במקרה זה כמעט כל התנאים ההתחלתיים האמיתיים מובילים להתנהגות [[תורת הכאוס|כאוטית]], בעוד שמצבים ראשוניים מסוימים חוזרים עד [[אינסוף]] או למחזורים חוזרים בכל אורך סופי.

המתמטיקאי קורט מקמלן הראה כי לכל אלגוריתם איטרטיבי אפשרי טהור הדומה לשיטת ניוטון, האלגוריתם יתפצל בחלק מהאזורים הפתוחים של המישור המורכב כשהוא מיושם על [[פולינום]] כלשהו בדרגה 4 ומעלה. עם זאת, מקמולן נתן אלגוריתם מתכנס בדרך כלל לפולינומים בדרגה 3.<ref>{{צ-מאמר|שם=Families of Rational Maps and Iterative Root-Finding Algorithms|קישור=https://www.jstor.org/stable/1971408|כתב עת=Annals of Mathematics|שנת הוצאה=1987|עמ=467–493|כרך=125|doi=10.2307/1971408|מחבר=Curt McMullen}}</ref>

===לממדים גבוהים===
ניתן להכליל את שיטת ניוטון-רפסון גם ל[[שדה וקטורי|שדות וקטורים]] על ידי החלפת השימוש בנגזרת לשימוש ביעקוביאן:

בהינתן פונקציה וקטורית <math>\mathbf{F}:\mathbb{R}^k\to\mathbb{R}^m</math> נרצה למצוא וקטור <math>\mathbf{x}</math> כך ש-<math>\mathbf{F}(\mathbf{x})=0</math>. כלומר, לפתור מערכת של m משוואות (לא בהכרח ליניאריות) ב-k נעלמים.

אם k=m, נוכל לעשות זאת באמצעות [[כלל נסיגה|כלל הנסיגה]],<math display="block">x_{n+1} = x_n - \left(\mathbf{J}_\mathbf{F}(x_n)\right)^{-1}\mathbf{F}(x_n)</math>כאשר <math>\mathbf{J}_\mathbf{F}(\mathbf{x}_n)</math> היא [[מטריצת יעקבי|מטריצת היקוביאן]] של <math>\mathbf{F}</math> בנקודה <math>\mathbf{x}_n</math>.

אם m>k, מטריצת היעקוביאן בהכרח איננה [[מטריצה הפיכה|הפיכה]] ולכן אין לה [[מטריצה]] הופכית. במקרה זה נחליף את המטריצה ההופכית בנוסחה לעיל במטריצה:

<math display="block">\mathbf{J}^+=(\mathbf{J}^T\mathbf{J})^{-1}\mathbf{J}^T</math>מטריצה זו מהווה תחליף טוב למטריצה ההופכית בהקשר זה.
===לאופטימיזציה===
במקרים רבים, [[אופטימיזציה (מתמטיקה)|אופטימיזציה]] מצריכה מציאת נגזרת של פונקציה והשוואתה לאפס. דרך אחת לבצע זאת היא על ידי שיטת ניוטון-רפסון לנגזרת. במילים אחרות, תחת קיומה של נגזרת שנייה ל-<math>f</math> ותנאים טכניים נוספים, הסדרה שמוגדרת על ידי כלל הנסיגה
<math display="block">x_{n+1} = x_n - \frac{f'\left(x_n\right)}{f''\left(x_n\right)}</math>
מתכנסת ל[[נקודת קיצון]] של <math>f</math>.

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

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

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

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

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}
*{{יוטיוב|TubaZsza4eg|שם=שיטת ניוטון רפסון במחשבון}}
==הערות שוליים==
{{הערות שוליים}}
{{אנליזה מתמטית}}

{{בקרת זהויות}}

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