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

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

הבעיה

בהינתן $ 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} $ הוא ברגע אופטימלי.