שיטת ברוידן

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

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

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

תיאור השיטה

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

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

$f^{\prime }(x_n)\simeq \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$

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

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

כאשר תבנית:נוסחה הוא אינדקס האיטרציה.

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

תהי מערכת מערכת של תבנית:נוסחה משוואות לא ליניאריות

$𝐟(𝐱)=\mathrm{𝟎},$

כאשר תבנית:נוסחה היא פונקציה וקטורית של וקטור תבנית:נוסחה:

$𝐱=(x_1,x_2,x_3,\dots ,x_k),$

$𝐟(𝐱)=(f_1(x_1,x_2,\dots ,x_k),f_2(x_1,x_2,\dots ,x_k),\dots ,f_k(x_1,x_2,\dots ,x_k)).$

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

${𝐉}_n({𝐱}_n-{𝐱}_{n-1})\simeq 𝐟({𝐱}_n)-𝐟({𝐱}_{n-1}),$

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

${𝐟}_n=𝐟({𝐱}_n),$

$\mathrm{\Delta }{𝐱}_n={𝐱}_n-{𝐱}_{n-1},$

$\mathrm{\Delta }{𝐟}_n={𝐟}_n-{𝐟}_{n-1},$

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

${𝐉}_n\mathrm{\Delta }{𝐱}_n\simeq \mathrm{\Delta }{𝐟}_n.$

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

${𝐉}_n={𝐉}_{n-1}+\frac{\mathrm{\Delta }{𝐟}_n-{𝐉}_{n-1}\mathrm{\Delta }{𝐱}_n}{\Vert \mathrm{\Delta }{𝐱}_n{\Vert }^2}\mathrm{\Delta }{𝐱}_n^{\mathrm{T}}.$

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

$\Vert {𝐉}_n-{𝐉}_{n-1}{\Vert }_{\mathrm{F}}$

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

${𝐱}_{n+1}={𝐱}_n-{𝐉}_n^{-1}𝐟({𝐱}_n).$

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

${𝐉}_n^{-1}={𝐉}_{n-1}^{-1}+\frac{\mathrm{\Delta }{𝐱}_n-{𝐉}_{n-1}^{-1}\mathrm{\Delta }{𝐟}_n}{\mathrm{\Delta }{𝐱}_n^{\mathrm{T}}{𝐉}_{n-1}^{-1}\mathrm{\Delta }{𝐟}_n}\mathrm{\Delta }{𝐱}_n^{\mathrm{T}}{𝐉}_{n-1}^{-1}.$

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

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

${𝐉}_n^{-1}={𝐉}_{n-1}^{-1}+\frac{\mathrm{\Delta }{𝐱}_n-{𝐉}_{n-1}^{-1}\mathrm{\Delta }{𝐟}_n}{\Vert \mathrm{\Delta }{𝐟}_n{\Vert }^2}\mathrm{\Delta }{𝐟}_n^{\mathrm{T}}.$

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

$\Vert {𝐉}_n^{-1}-{𝐉}_{n-1}^{-1}{\Vert }_{\mathrm{F}}.$

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

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

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

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

ראו גם

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

לקריאה נוספת

• תבנית:Cite book
• תבנית:Cite book

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

• הסבר בסיסי פשוט: סיפורו של הקשת העיוור
• תבנית:MathWorld