בהמשך לפעמים הקודמות, ראינו דרכים לחישוב שורש ריבועי שלם של מספר שלם.
קיימת שיטה נומרית לחישוב שורש של מספר ממשי. לשיטה קוראים שיטת הרון והיא מוגדרת כך:
אנחנו רוצים לחשב את השורש של המספר $ a $.
הגדר $x_0$ כניחוש הראשוני של השורש של המספר. בכל שלב הגדר את $x_{n + 1}$ כך:
$ \displaystyle{x_{n + 1} = \frac{1}{2} \left( \frac{a}{x_n} + x_n \right)} $
קרי: הגדר את $x_{n + 1}$ בתור הממוצע של $ x_n $ ו$ \displaystyle{\frac{a}{x_n}} $.
השיטה הזאת מתכנסת לשורש של a בצורה מאוד מהירה (למי שלמד אנליזה נומרית – ההתכנסות היא ריבועית, כלומר באיטרציה ה$ n $ יש פוטנציאלית $ 2^n$ ספרות מדויקות אחרי הנקודה)
השיטה היא מקרה פרטי של שיטת ניוטון רפסון המאפשרת לחשב שורש של פונקציה. שיטת ניוטון רפסון מוגדרת כך:
אנחנו רוצים לחשב שורש של פונקציה $ f(x) $, כלומר למצוא $ x_0$ כך ש $ f(x_0) = 0 $.
הגדר את $x_0$ להיות ניחוש לשורש של הפונקציה. בכל שלב הגדר את $x_{n + 1}$ כך:
$ \displaystyle{x_{n + 1} = x_n - \frac{f(x_n)}{f’(x_n)}} $
השיטה בתנאי התחלה מסוימים מתכנסת לשורש של המספר, ובמקרים מסוימים (ש($ f’(x_0) $ הוא לא 0 למשל), מתקיים שההתכנסות ריבועית.
אם נגדיר $ f(x) = x^2 - a $ נקבל בדיוק את שיטת הרון.
בד”כ בפועל מה שעושים זה משלבים את שיטת ניוטון רפסון עם שיטת חיפוש כלשהו (כמו חיפוש בינארי) על מנת למצוא ניחוש ראשוני מספיק טוב, ואז מתחילים לבצע את תהליך ניוטון רפסון כדי להתקרב לשורש של הפונקציה.
המשך יום נומרי טוב!