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

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

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

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

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

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

ערכים עוקבים של ${\displaystyle \ p^{k}}$ ניתנים אחר כך על ידי חזרה על היחס:

${\displaystyle \ 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})}$

כאשר:

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

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

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

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

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

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

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