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

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

תיאור הבעיה

בהינתן m פונקציות $f_{i}(x_{1},...,x_{n})$ כאשר $1\leq i\leq m$, וכן $\ m\geq n$,

בעיית האופטימיזציה היא למצוא וקטור $\ p=(x_{1},...,x_{n})$ כך שהסכום $\ S(p)=\sum _{i=1}^{m}(f_{i}(p))^{2}$ הוא מינימלי, כלומר לכל וקטור $\ q=(y_{1},...,y_{n})$ מתקיים $S(p)\leq S(q)$.

האלגוריתם

אלגוריתם גאוס-ניוטון הוא תהליך איטרטיבי. כלומר, יש לספק ערך התחלתי ל-$\ 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$.

את המטריצה ההופכית אין צורך לחשב במפורש.

במקומה נוכל לסמן את $\delta _{k}=-{\Big (}J_{f}(p^{k})^{\top }J_{f}(p^{k}){\Big )}^{-1}J_{f}(p^{k})^{\top }f(p^{k})$ מתקיים

• $p^{k+1}=p^{k}+\delta _{k}$
• ${\Big (}J_{f}(p^{k})^{\top }J_{f}(p^{k}){\Big )}\delta _{k}=J_{f}(p^{k})^{\top }f(p^{k})$ ע"י הכפלה של שני הצדדים ב ${\Big (}J_{f}(p^{k})^{\top }J_{f}(p^{k}){\Big )}$

נסמן $A={\Big (}J_{f}(p^{k})^{\top }J_{f}(p^{k}){\Big )},b=J_{f}(p^{k})^{\top }f(p^{k})$

וקיבלנו אם כך מערכת משוואות לינאריות $A\delta _{k}=b$ למציאת $\delta _{k}$.