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

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

הבעיה

בהינתן m פונקציות בעלות n פרמטרים, כאשר $\ m\geq n$, הבעיה היא להביא את הסכום $\ S(p)=\sum _{i=1}^{m}(f_{i}(p)/2)^{2}$ לערכו הקטן ביותר על ידי שינוי $\ p$, כאשר $\ p$ הוא הוקטור (p₁, ..., p_n).

האלגוריתם

אלגוריתם גאוס-ניוטון הוא הליך איטרטיבי, כלומר יש לספק ערך התחלתי ל-$\ p$, שנקרא לו $\ p^{0}$. ערכים עוקבים של $\ p^{k}$ ניתנים אחר כך על ידי חזרה על היחס:

$\ p^{k+1}=p^{k}-{\Big (}J_{f}(p^{k})^{\top }J_{f}(p^{k}){\Big )}^{-1}J_{f}(p^{k})^{\top }f(p^{k})$

כאשר:

$\ f=(f_{1},\dots ,f_{m})$

ו- $\ Jf(p)$ מסמן את היעקוביאן של $\ f$ ב-$\ p$.

את המטריצה ההופכית אין צורך לחשב במפורש. במקומה, אנו משתמשים ב-: $\ p^{k+1}=p^{k}+\delta ^{k},\,$ ואז ניתן לחשב את העדכון δ^k על ידי פתירת מערכת ליניארית: $\ J_{f}(p^{k})^{\top }J_{f}(p^{k})\,\delta ^{k}=-J_{f}(p^{k})^{\top }f(p^{k}).$.

יישום טוב של אלגוריתם גאוס-ניוטון מספק חיפוש אלגוריתם: במקום הנוסחה מלמעלה עבור p^k+1, אנו משתמשים ב-: $\ p^{k+1}=p^{k}+\alpha ^{k}\,\delta ^{k},$, כאשר המספר α^k הוא ברגע אופטימלי.