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

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

הבעיה

בהינתן $m$ פונקציות בעלות $n$ פרמטרים כאשר $m\leq n$ , הבעיה היא להביא את הסכום $S(p)=\sum _{i=1}^{m}\left({\frac {f_{i}(p)}{2}}\right)^{2}$ לערכו הקטן ביותר על ידי שינוי $p$ , כאשר $p=(p_{1},\ldots ,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},\ldots ,f_{m})$ ו-$Jf(p)$ היעקוביאן של $f$ ב-$p$ .

את המטריצה ההופכית אין צורך לחשב במפורש. במקומה, אנו משתמשים ב-$p^{k+1}=p^{k}+\delta ^{k}$ ואז ניתן לחשב את העדכון $\delta ^{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}$ , כאשר המספר $\alpha ^{k}$ הוא ברגע אופטימלי.