אלגוריתם גאוס-ניוטון

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

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

הבעיה

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

האלגוריתם

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

כאשר ו- היעקוביאן של ב- .

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

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