שיטת ברוידן

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

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

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

תיאור השיטה

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

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

<math>f'(x_n) \simeq \frac{f(x_n) - f(x_{n-1})}{x_n - x_{n - 1}}</math>

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

<math>x_{n + 1} = x_n - \frac{f(x_n)}{f^\prime(x_n)}</math>

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

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

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

<math>\mathbf f(\mathbf x) = \mathbf 0 ,</math>

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

<math>\mathbf x = (x_1, x_2, x_3, \dotsc, x_k),</math>

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

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

<math>\mathbf J_n (\mathbf x_n - \mathbf x_{n - 1}) \simeq \mathbf f(\mathbf x_n) - \mathbf f(\mathbf x_{n - 1}),</math>

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

<math>\mathbf f_n = \mathbf f(\mathbf x_n),</math>

<math>\Delta \mathbf x_n = \mathbf x_n - \mathbf x_{n - 1},</math>

<math>\Delta \mathbf f_n = \mathbf f_n - \mathbf f_{n - 1},</math>

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

<math>\mathbf J_n \Delta \mathbf x_n \simeq \Delta \mathbf f_n.</math>

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

<math>\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}.</math>

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

<math>\|\mathbf J_n - \mathbf J_{n - 1}\|_{\rm F}</math>

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

<math>\mathbf x_{n + 1} = \mathbf x_n - \mathbf J_n^{-1} \mathbf f(\mathbf x_n) .</math>

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

<math>\mathbf J_n^{-1} = \mathbf J_{n - 1}^{-1} + \frac{\Delta \mathbf x_n - \mathbf J^{-1}_{n - 1} \Delta \mathbf f_n}{\Delta \mathbf x_n^{\mathrm T} \mathbf J^{-1}_{n - 1} \Delta \mathbf f_n} \Delta \mathbf x_n^{\mathrm T} \mathbf J^{-1}_{n - 1}.</math>

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

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

<math>\mathbf J_n^{-1} = \mathbf J_{n - 1}^{-1} + \frac{\Delta \mathbf x_n - \mathbf J^{-1}_{n - 1} \Delta \mathbf f_n}{\|\Delta \mathbf f_n\|^2} \Delta \mathbf f_n^{\mathrm T}.</math>

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

<math>\|\mathbf J_n^{-1} - \mathbf J_{n - 1}^{-1}\|_{\rm F}.</math>

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

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

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

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

ראו גם

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

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

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