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

פרק זה טעון עריכה. אנא תרמו למכלול ועזרו לערוך אותו. הסיבה היא: תיקוני סגנון.

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

הבעיה

בהינתן $m$ פונקציות בעלות $n$ פרמטרים כאשר $m\le n$ , הבעיה היא להביא את הסכום $S(p)=\sum _{i=1}^m{\left(\frac{f_i(p)}{2}\right)}^2$ לערכו הקטן ביותר על ידי שינוי $p$ , כאשר $p=(p_1,\dots ,p_n)$ .

האלגוריתם

אלגוריתם גאוס-ניוטון הוא הליך איטרטיבי, כלומר יש לספק ערך התחלתי ל-$p$ , שנקרא לו $p^0$ . ערכים עוקבים של $p^k$ ניתנים אחר כך על ידי חזרה על היחס:

$p^{k+1}=p^k-(J_f(p^k{)}^{\mathrm{\top }}{J}_f(p^k){)}^{-1}{J}_f(p^k{)}^{\mathrm{\top }}f(p^k)$

כאשר $f=(f_1,\dots ,f_m)$ ו-$Jf(p)$ היעקוביאן של $f$ ב-$p$ .

את המטריצה ההופכית אין צורך לחשב במפורש. במקומה, אנו משתמשים ב-$p^{k+1}=p^k+{\delta }^k$ ואז ניתן לחשב את העדכון ${\delta }^k$ על ידי פתירת מערכת לינארית: $J_f(p^k{)}^{\mathrm{\top }}{J}_f(p^k){\delta }^k=-J_f(p^k{)}^{\mathrm{\top }}f(p^k)$ .

יישום טוב של אלגוריתם גאוס-ניוטון מספק חיפוש אלגוריתם: במקום הנוסחה מלמעלה עבור $p^{k+1}$ , אנו משתמשים ב-$p^{k+1}=p^k+{\alpha }^k{\delta }^k$ , כאשר המספר ${\alpha }^k$ הוא ברגע אופטימלי.