הצגת המקור של הדף "אלגוריתם גאוס-ניוטון"

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

== תיאור הבעיה ==
בהינתן m [[פונקציה|פונקציות]] <math>f_i(x_1,...,x_n)</math> כאשר <math>1\leq i \leq m </math>, וכן <math>\ m\ge n</math>,

בעיית [[אופטימיזציה (מתמטיקה)|האופטימיזציה]] היא למצוא [[וקטור (אלגברה)|וקטור]] <math>\ p = (x_1,...,x_n) </math> כך שהסכום <math>\ S(p) = \sum_{i=1}^m (f_i(p))^2 </math> הוא מינימלי, כלומר לכל [[וקטור (פיזיקה)|וקטור]] <math>\ q = (y_1,...,y_n) </math> מתקיים <math>S(p) \leq S(q) </math>.

== האלגוריתם ==
אלגוריתם גאוס-ניוטון הוא תהליך [[איטרציה|איטרטיבי]]. כלומר, יש לספק ערך התחלתי ל-<math>\ p </math>, שנקרא לו <math>\ p^0</math>.

ערכים עוקבים של <math>\ p^k</math> ניתנים אחר כך על ידי חזרה על היחס:

<math>\ 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) </math>

כאשר:
:<math>\ f=(f_1,\dots,f_m)</math>
:ו- <math>\ Jf(p)</math> מסמן את ה[[יעקוביאן]] של <math>\ f </math> ב-<math>\ p </math>.

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

במקומה נוכל לסמן את <math>\delta_k = - \Big(J_f(p^k)^\top J_f(p^k)\Big)^{-1} J_f(p^k)^\top f(p^k) </math> מתקיים
* <math>p^{k+1}=p^k+\delta_k </math>
* <math>\Big(J_f(p^k)^\top J_f(p^k)\Big)\delta_k = J_f(p^k)^\top f(p^k) </math> על ידי הכפלה של שני הצדדים ב <math>\Big(J_f(p^k)^\top J_f(p^k)\Big) </math>

נסמן <math>A=\Big(J_f(p^k)^\top J_f(p^k)\Big), b = J_f(p^k)^\top f(p^k) </math>

וקיבלנו אם כך [[מערכת משוואות ליניאריות]] <math>A\delta_k = b </math> למציאת <math>\delta_k </math>.

[[קטגוריה:אופטימיזציה רציפה]]
[[קטגוריה:סטטיסטיקה]]
[[קטגוריה:אייזק ניוטון]]
[[קטגוריה:קרל פרידריך גאוס]]