روش برویدن (Broyden's Method)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش برویدن (Broyden's Method) :
\[ J_{k+1} = J_k + \frac{(y_k - J_k s_k) s_k^T}{s_k^T s_k} \]توضیح ساده: روش برویدن یک روش شبه-نیوتن برای حل دستگاه های معادلات غیرخطی است (نه لزوما بهینه سازی). در این روش، ماتریس ژاکوبی به صورت تقریبی و با استفاده از اطلاعات دو تکرار متوالی به روز می شود. این روش برای دستگاه هایی که محاسبه ژاکوبی دقیق در آنها پرهزینه است، بسیار مفید است. برویدن اولین کسی بود که چنین ایده ای را در سال ۱۹۶۵ ارائه داد.
شرح گام به گام: هدف حل F(x)=0 است. با یک حدس اولیه x₀ و یک تخمین اولیه از ژاکوبی (مثلا J₀ با تفاضلات محدود) شروع می کنیم. در هر تکرار k:
۱. جهت جستجو را با حل Jₖ Δxₖ = -F(xₖ) پیدا می کنیم.
۲. xₖ₊₁ = xₖ + Δxₖ را به روز می کنیم.
۳. sₖ = Δxₖ (تغییر در x)
۴. yₖ = F(xₖ₊₁) - F(xₖ) (تغییر در F)
۵. ماتریس ژاکوبی را با فرمول برویدن به روز می کنیم:
\[ J_{k+1} = J_k + \frac{(y_k - J_k s_k) s_k^T}{s_k^T s_k} \]این فرمول کمترین تغییر را در J ایجاد می کند در حالی که شرط سکانت Jₖ₊₁ sₖ = yₖ را ارضا می کند.
۶. تکرار تا همگرایی.
مثال عددی: همان دستگاه قبل: F₁ = x²+y²-4، F₂ = x²-y-1 با x₀=[1,1]ᵀ، J₀ را با تفاضلات محدود تقریب می زنیم: مثلا J₀ = [[2,2],[2,-1]] (دقیق در این نقطه). تکرار اول: Δx = [0.6667,0.3333]ᵀ (همان قبلی)، x₁=[1.6667,1.3333]ᵀ. F(x₁)=[0.5556,0.4445]ᵀ، F(x₀)=[-2,-1]ᵀ s₀ = Δx = [0.6667,0.3333]ᵀ y₀ = F(x₁)-F(x₀) = [2.5556,1.4445]ᵀ J₀ s₀ = [[2,2],[2,-1]] [0.6667,0.3333]ᵀ = [2*0.6667+2*0.3333, 2*0.6667-1*0.3333] = [2, 1]ᵀ y₀ - J₀ s₀ = [2.5556-2, 1.4445-1] = [0.5556, 0.4445]ᵀ (y₀ - J₀ s₀) s₀ᵀ = [[0.5556*0.6667, 0.5556*0.3333], [0.4445*0.6667, 0.4445*0.3333]] ≈ [[0.3704, 0.1852], [0.2963, 0.1481]] s₀ᵀs₀ = 0.6667²+0.3333² = 0.4445+0.1111=0.5556 J₁ = J₀ + (1/0.5556)*[[0.3704,0.1852],[0.2963,0.1481]] = [[2,2],[2,-1]] + [[0.6667,0.3333],[0.5333,0.2667]] = [[2.6667,2.3333],[2.5333,-0.7333]] این J₁ تقریبی از ژاکوبی در نقطه جدید است.
مزایا: کاهش شدید هزینه محاسباتی نسبت به نیوتن (بدون نیاز به محاسبه مجدد ژاکوبی). همگرایی ابرخطی.
معایب: ممکن است ماتریس J به مرور زمان دقت خود را از دست بدهد و نیاز به بازنشانی داشته باشد. برای مسائل بسیار غیرخطی ممکن است کند شود.
کاربردها: در حل دستگاه های غیرخطی بزرگ، در شبیه سازی فرآیندهای شیمیایی، در دینامیک سیالات محاسباتی.
نکته: روش برویدن پایه گذار خانواده روش های شبه-نیوتن برای دستگاه های غیرخطی بود.
