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

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

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

הבעיה

בהינתן m פונקציות בעלות n פרמטרים כאשר mn , הבעיה היא להביא את הסכום S(p)=i=1m(fi(p)2)2 לערכו הקטן ביותר על ידי שינוי p , כאשר p=(p1,,pn) .

האלגוריתם

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

pk+1=pk(Jf(pk)Jf(pk))1Jf(pk)f(pk)

כאשר f=(f1,,fm) ו-Jf(p) היעקוביאן של f ב-p .

את המטריצה ההופכית אין צורך לחשב במפורש. במקומה, אנו משתמשים ב-pk+1=pk+δk ואז ניתן לחשב את העדכון δk על ידי פתירת מערכת לינארית: Jf(pk)Jf(pk)δk=Jf(pk)f(pk) .

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