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

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

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

הבעיה

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