שיטת ברוידן

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

שיטת ניוטון לפתרון f(x) = 0 משתמשת במטריצת היעקוביאן, J, בכל איטרציה. עם זאת, חישוב היעקוביאן היא פעולה מורכבת ויקרה חישובית. מטרת שיטת ברוידן היא לחשב את היעקוביאן רק באיטרציה הראשונה ולבצע עדכונים מדרגה אחת בכל שאר האיטרציות האחרות.

בשנת 1979 די. אמ. גיי הוכיח שכאשר שיטת ברוידן מיושמת על מערכת משוואות ליניאריות מגודל n × n, היא מתכנסת ב 2 n שלבים,^[2] אם כי כמו כל השיטות הקוואזי-ניוטוניות, היא עשויה שלא להתכנס למערכות לא ליניאריות.

תיאור השיטה

פתרון עבור משתנה יחיד

בשיטת הססקנט, נחליף את הנגזרת הראשונה f′ ב- x_n בקירוב הליניארי:

${\displaystyle f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}}$

ונמשיך בדומה לשיטת ניוטון:

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f^{\prime }(x_{n})}}}$

כאשר n הוא אינדקס האיטרציה.

פתרון עבור מספר משתנים

תהי מערכת מערכת של k משוואות לא ליניאריות

${\displaystyle \mathbf {f} (\mathbf {x} )=\mathbf {0} ,}$

כאשר f היא פונקציה וקטורית של וקטור x:

${\displaystyle \mathbf {x} =(x_{1},x_{2},x_{3},\dotsc ,x_{k}),}$

${\displaystyle \mathbf {f} (\mathbf {x} )={\big (}f_{1}(x_{1},x_{2},\dotsc ,x_{k}),f_{2}(x_{1},x_{2},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},x_{2},\dotsc ,x_{k}){\big )}.}$

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

${\displaystyle \mathbf {J} _{n}(\mathbf {x} _{n}-\mathbf {x} _{n-1})\simeq \mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1}),}$

כאשר n הוא אינדקס האיטרציה. למען הבהירות, נגדיר:

${\displaystyle \mathbf {f} _{n}=\mathbf {f} (\mathbf {x} _{n}),}$

${\displaystyle \Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},}$

${\displaystyle \Delta \mathbf {f} _{n}=\mathbf {f} _{n}-\mathbf {f} _{n-1},}$

כך שניתן לשכתב את האמור לעיל בתור

${\displaystyle \mathbf {J} _{n}\Delta \mathbf {x} _{n}\simeq \Delta \mathbf {f} _{n}.}$

המשוואה לעיל אינה ניתנת לפתרון אנליטי כאשר k גדול מאחד. בשיטת ברוידן נשתמש באומדן הנוכחי של המטריצה היעקוביאנית J_n−1 ונשפר אותה על ידי לקיחת הפתרון למשוואת הססקנט שהיא שינוי מינימלי ל-J_n−1:

${\displaystyle \mathbf {J} _{n}=\mathbf {J} _{n-1}+{\frac {\Delta \mathbf {f} _{n}-\mathbf {J} _{n-1}\Delta \mathbf {x} _{n}}{\|\Delta \mathbf {x} _{n}\|^{2}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }.}$

חישוב זה מביא לערך מינימלי עבור נורמת פרובניוס:

${\displaystyle \|\mathbf {J} _{n}-\mathbf {J} _{n-1}\|_{\rm {F}}}$

לאחר מכן נוכל להמשיך בצורה זהה לשיטת ניוטון:

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}).}$

ברוידן אף הציע להשתמש בנוסחת שרמן-מוריסון על מנת לעדכן ישירות את המטריצה היעקוביאנית ההופכית:

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}.}$

שיטה ראשונה זו ידועה כ"שיטת ברוידן הטובה".

ניתן לחשב בטכניקה דומה על ידי שימוש בשינוי קטן ל- J_n−1 . צורה זו מניבה שיטה שנייה, מה שמכונה "שיטת ברוידן הרעה" (אך ראה):^[3]

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\|\Delta \mathbf {f} _{n}\|^{2}}}\Delta \mathbf {f} _{n}^{\mathrm {T} }.}$

זה ממזער נורמה שונה מזו של פרובניוס:

${\displaystyle \|\mathbf {J} _{n}^{-1}-\mathbf {J} _{n-1}^{-1}\|_{\rm {F}}.}$

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

שיטות דומות לשיטת ברוידן

ישנן מספר שיטות אשר פורסמו בצמוד לשיטת ברוידן אשר נוקטות גישה דומה לחישוב שורש של פונקציה

• שיטת דוידון-פלטשר-פאוול היא השיטה היחידה הזו שמתפרסם לפני שני החברים שהוגדרו על ידי ברוידן.^[1]
• אלגוריתם שוברט או שיטת ברוידן הדלילה - שינוי למטריצות יעקוביאניות דלילות.^[4]
• Klement (2014) - משתמש בפחות איטרציות כדי לפתור מערכות משוואות רבות.^[5][6]

ראו גם

• שיטת המיתר
• שיטת ניוטון-רפסון

לקריאה נוספת

• Dennis, J. E.; Schnabel, Robert B. (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice Hall. pp. 168–193. ISBN 0-13-627216-9.
• Fletcher, R. (1987). Practical Methods of Optimization (Second ed.). New York: John Wiley & Sons. pp. 44–79. ISBN 0-471-91547-5.

קישורים חיצוניים

• הסבר בסיסי פשוט: סיפורו של הקשת העיוור
• שיטת ברוידן, באתר MathWorld (באנגלית)

הערות שוליים

1. Broyden, C. G. (באוקטובר 1965). "A Class of Methods for Solving Nonlinear Simultaneous Equations". Mathematics of Computation. American Mathematical Society. 19 (92): 577–593. doi:10.1090/S0025-5718-1965-0198670-6. JSTOR 2003941.
2. Gay, D. M. (באוגוסט 1979). "Some convergence properties of Broyden's method". SIAM Journal on Numerical Analysis. SIAM. 16 (4): 623–630. doi:10.1137/0716047.
3. Kvaalen, Eric (בנובמבר 1991). "A faster Broyden method". BIT Numerical Mathematics. SIAM. 31 (2): 369–372. doi:10.1007/BF01931297.
4. Schubert, L. K. (1970-01-01). "Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian". Mathematics of Computation. 24 (109): 27–30. doi:10.1090/S0025-5718-1970-0258276-9. ISSN 0025-5718.
5. Klement, Jan (2014-11-23). "On Using Quasi-Newton Algorithms of the Broyden Class for Model-to-Test Correlation". Journal of Aerospace Technology and Management (באנגלית). 6 (4): 407–414. doi:10.5028/jatm.v6i4.373. ISSN 2175-9146.
6. "Broyden class methods – File Exchange – MATLAB Central". www.mathworks.com. נבדק ב-2016-02-04.