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

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

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

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

בהינתן m פונקציות בעלות n פרמטרים, כאשר , הבעיה היא להביא את הסכום לערכו הקטן ביותר על ידי שינוי , כאשר הוא הוקטור (p1, ..., pn).

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

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

כאשר:

ו- מסמן את היעקוביאן של ב-.

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

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