روش نیوتن را به یاد دارید؟ فرض کنید یک برابری (معادلهٔ) تکمتغیرهٔ $f(x)=0$ دارید. برای یافتن ریشه از یک مقدار اولیهٔ مناسب مانند $x_0$ شروع میکردید. سپس یک دنباله به شکل $x_{n}=x_{n-1}-\frac{1}{f'(x_{n-1})}f(x_{n-1})$ . اکنون به جای اینکه هر دفعه مشتق تابع را در نقاط دنبالهتان محاسبه کنید، به جای مقدار دقیق آن از تقریب آن یعنی $\frac{f(x_{n-1})-f(x_{n-2})}{x_{n-1}-x_{n-2}}$ استفاده کنید. توجه کنید که این کار تنها در نقطهٔ شروع ناممکن است چون تنها یک مقدار یعنی $f(x_0)$ را دارید و $x_{-1}$ در دنباله نیست. پس باید در گام نخست از خود مشتق استفاده کنید و سپس از تقریب آن. توجه کنید که این روش سادهتر است ولی خطای محاسبه را افزایش میدهد.
برویم سراغ دستگاههای چندمعادلهچندمجهولی. فرض کنید
$n$
متغیر
$x_1,\ldots,x_n$
و
$n$
تابع اسکالر مقدار
$n$
متغیره
$f_1,\ldots,f_n$
داریم.
بردار
$(f_1,\ldots,f_n)$
را با
$f$
و بردار
$(x_1,\ldots,x_n)$
را با
$x$
نشان میدهیم. ماتریس ژاکوبی
$f$
نسبت به
$x$
را با
$J=J_x(f)$
نمایش دهید. اگر
$z^\star$
یک ریشه از دستگاه
$f(x)=0$
باشد و
$z_0$
یک نقطهٔ شروع برای تقریب زدن آن، آنگاه روش نیوتن چندمتغیره به شکل زیر یک دنباله برای تقریب زدن ریشهٔ مورد نظر معرفی میکند.
$$z_k=z_{k-1}-J_{k-1}^{-1}f(z_{k-1})$$
که در آن
$J_{k-1}=J_x(f)\mid_{x=z_{k-1}}$
میباشد یعنی ماتریس حاصل از جایگذاری
$x=x_{k-1}$
در ماتریس ژاکوبی.
دوباره ایده این است که به جای استفاده از ماتریس ژاکوبی که تعمیم مشتق است، آن را تقریب بزنیم و از تقریبش به جایش در فرمول نیوتن استفاده کنیم. روشهای زیادی برای این کار وجود دارد. یکی از آنها به شرح زیر است.
روشهای شبهنیوتن رتبهیک
در اینجا یک خانواده از روشها را معرفی میکنیم (نه یک روش). به آنها شبهنیوتن میگویند چون شبیه روش نیوتن اند. رتبهیک گفته میشوند چون در هر گام بر روی یک یک زیرفضای یکبعدی (یک خط) حرکت میکنند. به شکل زیر دقت کنید (چون رایانهٔ دفترکارم در بنیانگاه لینوکس است و Paint ندارم بر روی تختهٔ دفترم رسم کردم پسینتر تصویر را جایگزین خواهمکرد).
نخست ماتریس ژاکوبی را در نقطهٔ شروع
$x=z_0$
محاسبه کنید. در روش نیوتن نقطهٔ پسین برابر میشد با
$z_1=z_0-J_0^{-1}f(z_0)$
اما در اینجا به جای این کار خطی که از نقطهٔ
$z_0$
بگذرد و بردار هادی آن
$v_0=-J_0^{-1}f(z_0)$
باشد را در نظر بگیرید. این خط را میتوان با ضابطهٔ تکپارامتری زیر نمایش داد
$$\ell_0\;\colon\;x=z_0+tv_0$$
اگر قرار دهیم
$t=1$
همان نقطهٔ پیشنهادی روش نیوتن را داریم. اما این آزادی را میدهیم که اگر
$t$
بهتری نامزد شد، از آن استفاده کنیم و نقطهٔ پسین را
$z_1=z_0+t_0v_0$
برداریم. اکنون برای ادامهٔ فرآیند نیاز داریم خط پسین را معرفی کنیم. همه چیز روشن است به جز بردار هادی آن خط و آن هم به این خاطر است که نمیخواهیم ماتریس ژاکوبی در نقطهٔ جدید را محاسبه کنیم بلکه میخواهیم از تقریبی از آن استفاده کنیم. به جای اینکه یک ماتریس معرفی کنیم دوباره مانند قضیهٔ انتخاب
$t$
یک جای دیگر برای انتخاب باز میگذاریم. فقط یک شرط معرفی میکنیم که انتظار داریم یک تقریب برای این ماتریس ژاکوبی در این شرط صدق کند.
تحدید تابع
$f$
بر روی خط گام پیشین یعنی
$\ell_0$
را در نظر بگیرید. یک تابع یک متغیره با متغیر
$t$
داریم. چون نقطهٔ جدید مشخص شدهاست پس یعنی قبل از وارد شدن به این مرحله
$t_0$
را انتخاب کردهاید. بسط تیلور این تابع یک متغیره را حول
$t=t_0$
بنویسید. در اینجا یک شرط جدید داریم. در هنگام انتخاب
$t_0$
باید به اندازهٔ کافی کوچک انتخاب شده بوده باشد که بتوانیم از جملات مرتبهٔ دوم به بعد بسط تیلور چشمپوشی کنیم. پس
$$f(z_0+tv_0)=f(z_0+t_0v_0)+(t-t_0)\frac{df}{dt}\mid_{t=t_0}+\mathcal{O}((t-t_0)^2)$$
مشتق تابع را محاسبه کنید
$$\begin{array}{l}
\frac{df}{dt}=\sum_{i=1}^n\frac{\partial f}{\partial x_i}\frac{dx_i}{dt}=(J_x(f))\cdot\begin{bmatrix}\frac{dx_i}{dt}\end{bmatrix}=J\cdot v_0\\
\frac{df}{dt}\mid_{t=t_0}=(J\cdot v_0)\mid_{x=z_0+t_0v_0}=J\mid_{x=z_0+t_0v_0}\cdot v_0=J_1v_0
\end{array}$$
اکنون بیایید مقدار این تابع یک متغیره را در
$t=0$
با کمک این بسط تقریب بزنیم.
$$f(z_0)\sim f(z_1)-t_0J_1v_0$$
پس اگر مقدار تابع در نقطهٔ جدید را بدست آوریم (با جایگذاری) آنگاه ماتریس ژاکوبی در نقطهٔ جدید در رابطهٔ زیر صدق میکند:
$$f(z_1)-f(z_0)\sim t_0J_1v_0$$
اکنون شرطی که روی تقریب آن میگذاریم این است که ماتریس نامزد جایگاه تقریب ماتریس ژاکوبی در نقطهٔ جدید باید در رابطهٔ بالا صدق کند.
پس خلاصهٔ کار این است که هر روشی که به شکل بالا دنبالهای از نقاط برای تقریب جواب دستگاهمان بسازد که در هر گام یک اسکالرِ
$t_i$
و یک ماتریس
$A_i$
معرفی کند که در شرط
$f(z_i)-f(z_{i-1})=t_iA_iv_{i-1}$
که
$v_i=-A_{i-1}^{-1}f(z_i)$
صدق کند، آنگاه یک روش شبهنیوتن رتبهیک نامیده میشود.
چندین نکته:
۱- این روشها یکی از تعمیمهای روش وتری است. زیرا اگر تابع تکضابطهای و یکمتغیره باشد، آنگاه با قرار دادن
$t=1$
در هر گام، عبارت زیر که یک ماتریس یک در یک است در رابطهٔ شرط صدق میکند.
برای نمونه بیایید گام دوم را چک کنیم (گام یک که خود مشتق در نقطهٔ شروع است).
$$\begin{array}{l}
v_0=-\frac{1}{f’(z_0)}f(z_0)\\
z_1=z_0-\frac{1}{f’(z_0)}f(z_0)\Longrightarrow v_0=z_1-z_0\\
f(z_1)-f(z_0)=1\cdot A_2\cdot v_0\Longrightarrow A_2=\dfrac{f(z_1)-f(z_0)}{z_1-z_0}
\end{array}$$
اما توجه کنید که تنها روشهای چندمتغیره که تعمیمی برای روش وتری بتوانند باشند روشهای شبهنیوتن رتبهیک نیستند. برای نمونه اگر همان روش نیوتن را برمیداشتیم و به هر
$n^2$
مشتقجزئی ماتریس ژاکوبی را که مشتق از یک متغیر هستند با یک تفاضل جایگزین میکردیم و سپس نقطه را جایگذاری میکردیم یک روش دیگر حاصل میشد که تحدیدش به حالت یکضابطهایِ یکمتغیره همان روش وتری میشود.
۲- ایدههای زیادی تا کنون برای انتخاب
$t_i$
ها و
$A_i$
ها معرفی شدهاند.
خود برُیْدِن
Broyden
چندین ایده ارائه کرد که یکی از آنها به شرح زیر است.
در هر گام ماتریس
$A_i$
را ماتریسی معرفی کنیم که علاوه بر صدق کردن در رابطهٔ داده شده در شرط روشهای شبهنیوتن رتبهیک، در این شرط صدق کند که برای هر بردار متعامد بر
$v_{i-1}$
مانند
$u$
داشته باشیم
$$A_iu=A_{i-1}u$$
این باعث میشود که تنها یک ماتریس یکتا نامزد گاممان باشد. دلیل آن این است که ماتریسمان
$n^2$
مجهول دارد. بردار
$v_{i-1}$
را با افزودن عناصر یک پایه از زیرفضای مکمل متعامدش به یک پایه برای کل فضا گسترش دهید. رابطهٔ شرط که متناظر به بردار
$v_{i-1}$
است یک تساوی برداری که در واقع
$n$
معادله هست به ما میدهد. اکنون
$n-1$
بردار دیگر این پایه که بر
$v_{i-1}$
متعامد هستند هر یک با توجه به شرط جدید یک تساوی برداری یعنی
$n$
معادله میدهند. پس در کل
$1\times n+(n-1)\times n=n^2$
معادله داریم. پس با یک
$n^2$
معادله
$n^2$
مجهول روبرو هستیم.
اکنون توجه کنید که ماتریس زیر
$$A_i=A_{i-1}+\dfrac{\big(f(x_i)-f(x_{i-1})-t_{i-1}A_{i-1}v_{i-1}\big)v_{i-1}^t}{t_{i-1}v_{i-1}^tv_{i-1}}$$
در رابطههای شرط روشهای شبهنیوتن رتبه یک و در شرط جدید صدق میکند. پس ماتریسی که میخواهیم دقیقا این ماتریس است.
این روش معمولا، روش برویدن گفته میشود هر چند این تنها روشی نیست که برویدن معرفی کردهاست. برخی ممکن است ایده یا فرمول دیگری از برویدن را با نام روش برویدن به کار ببرند.
