\chapter{ الگوریتم پیش‌شرطی‌شده گالرکین برای حل معادلات سیلوستر
}
\thispagestyle{empty}
\newpage

\section{مقدمه}
الگوریتم گالرکین یکی از روش‌های مؤثر مبتنی بر زیرفضای کریلوف برای حل معادلات خطی و معادلات ماتریسی نظیر معادله سیلوستر است. با این حال، زمانی که ماتریس‌های مسئله بزرگ و پراکنده باشند یا ویژگی‌های طیفی نامطلوبی داشته باشند، این روش ممکن است با چالش‌هایی نظیر سرعت پایین همگرایی یا افزایش هزینه محاسباتی مواجه شود.

به منظور بهبود کارایی و تسریع همگرایی، پیش‌شرط‌سازی به عنوان یک تکنیک مؤثر مطرح می‌شود. در این بخش، نسخه‌ای پیش‌شرطی‌شده از الگوریتم گالرکین برای حل معادله سیلوستر به صورت زیر معرفی می‌شود:
\begin{equation}\begin{aligned}\label{z00001}
AX - XB = C,
\end{aligned}\end{equation}
که در آن
$ A, B, C, X \in \mathbb{R}^{n \times n} $
هستند. با اعمال پیش‌شرط‌کننده‌های مناسب 
$M$
و
$ N$
برای ماتریس‌های 
$A$
و 
$B$
، معادله به فرم زیر تبدیل می‌شود،
$$MAXN - MXBN = MCN.$$
در این فصل، فرمول‌بندی دقیق الگوریتم گالرکین پیش‌شرطی‌شده ارائه شده و نحوه استفاده از فرآیند آرنولدی برای تولید زیرفضای کریلوف و کاهش مرتبه معادله سیلوستر شرح داده می‌شود. همچنین، روش‌های محاسبه باقیمانده، شرایط همگرایی و چگونگی به‌روزرسانی تقریب‌های عددی نیز بررسی خواهند شد.
\section{نحوه محاسبه الگوریتم پیش‌شرطی‌شده گالرکین}
فرض کنید
$M$
و 
$N$
ماتریس‌های پیش‌شرطی مناسب برای ماتریس‌های
$A$
و
$B$
باشند و
$ x_0 \in \mathbb{R}^{n^2}$
یک تقریب اولیه از جواب سیستم خطی زیر باشد،
\begin{equation}\begin{aligned}\label{z00002}
(N^{T}\otimes MA-N^{T}B^{T}\otimes M)x=(N^{T}\otimes M)c,
\end{aligned}\end{equation}
که در آن 
$\otimes$
ضرب کرونکر و
$x\in\mathbb{R}^{n^{2}}$
و
$c\in\mathbb{R}^{n^{2}}$
بردارهایی هستند که تمام اعضایشان به ترتیب از ماتریس های 
$X$
و
$C$
حاصل شده اند. بردار باقی‌مانده اولیه به صورت زیر تعریف می‌شود،
$$r_0 = (N^T \otimes M)c - (N^T \otimes MA + N^T B^T \otimes M)x_0.$$
ماتریس
$P_{M,N}$
و بردار
$ c_{M,N}$
را به صورت زیر تعریف کنیم،
$$ P_{M,N} = N^T \otimes MA - N^TB^T \otimes M, \quad c_{M,N} = (N^T \otimes M)c. $$
روش متعامدسازی کامل به دنبال یک جواب تقریبی
$x_m$
از زیرفضای افین
$ x_0 + K_m(P_{M,N},r_0) $
با بعد 
$m$
است که با اعمال شرط گالرکین زیر عمل می کند،
$$c_{M,N} - P_{M,N}x_m \perp K_m(P_{M,N},r_0). $$
این روش از فرآیند آرنولدی برای محاسبه یک پایه متعامد از زیرفضای کرایلف
$K_m(P_{M,N},r_0)$
استفاده می‌کند. ماتریس 
$P_{M,N}$
در کاربرد می‌تواند بسیار بزرگ باشد، بنابراین ممکن است ذخیره یک پایه از زیرفضای کرایلف 
$K_m(P_{M,N},r_0)$
در حافظه سریع کامپیوتر برای بعد 
$m$
که نرخ همگرایی قابل قبولی را ارائه می‌دهد، دشوار باشد. برای رفع این مشکل، زیرفضای کرایلف
$ K_m(P_{M,N},r_0) $
را با زیرفضایی از فرم 
$ K_m(N^TB^T,g) \otimes K_m(MA,f) $
برای بردارهای مشخص
$f,g \in \mathbb{R}^n $
جایگزین می‌کنیم. استراتژی‌هایی برای انتخاب 
$f$
و 
$g$
در مرجع 
\cite{12}
مورد بحث قرار گرفته‌اند. اجازه دهید برای لحظه‌ای 
$f$
و 
$g$
را به صورت دلخواه اما ثابت در 
$ \mathbb{R}^n $
در نظر بگیریم، و از الگوریتم گرام-اشمیت اصلاح‌شده برای تولید پایه‌های متعامد
$\{v_j\}_{j=1}^{m+1}$
و 
$\{w_j\}_{j=1}^{m+1}$
از 
$K_{m+1}(MA,f) $
و 
$K_{m+1}(N^TB^T,g)$
استفاده کنیم. با معرفی ماتریس‌های
$V_j = [v_1, v_2, \cdots, v_j] $
و 
$W_j = [w_1, w_2, \ldots, w_j] $
، برای 
$j \in \{m, m+1\} $
، الگوریتم گرام-اشمیت اصلاح‌شده عناصر ماتریس‌های هسنبرگ بالا 
$H_{MA}$
و 
$H_{NB}$
و ماتریس‌های شبه هسنبرگ
$\tilde{H}{MA} $
و 
$\tilde{H}{NB}$
را تولید می‌کند که به صورت زیر هستند،
$$H_{MA} = V_m^T MAV_m,\quad \quad H_B = W_m^T N^T B^T W_m.$$
برای ماتریس
$A$
و بردار اولیه
$f$
، زیرفضای کریلوف از مرتبه
$m$
به صورت زیر تعریف می‌شود،
$$K_m(A, f) = span\{f, Af, A^2f, \dots, A^{m-1}f\}.$$
هدف از فرآیند آرنولدی، تولید یک مجموعه متعامد یکه از این زیرفضا است. برای ماتریس 
$MA$
و بردار اولیه
$f$
داریم:
\begin{enumerate}
\item
ابتدا بردار
$v_1$
را به صورت نرمال‌شده از
$ f$
 انتخاب می‌کنیم به طوری که،
$$v_1 = \frac{f}{\|f\|}.$$
\item
سپس، برای تولید بردارهای متعامد یکه بعدی، مراحل زیر طی می‌شود،
\begin{align*}
&w = MA v_j,
\\&h_{i,j} = v_i^T w \quad \text{(محاسبه ضرایب تصویر)},
\\&w = w - \sum_{i=1}^j h_{i,j} v_i \quad \text{(متعامد سازی)},
\\&h_{j+1,j} = \|w\|,
\\&v_{j+1} = \frac{w}{h_{j+1,j}}.
\end{align*}
\end{enumerate}
با تکرار این فرآیند، ماتریس متعامد یکه
$ V_{m+1}$
تولید می‌شود و ضرایب
$ h_{i,j}$
وارد ماتریس هسنبرگ
$ \tilde{H}_{MA}$
می‌شوند. با توجه به گام‌های فوق، رابطه کلی به صورت زیر حاصل می شود،
$$MA V_m = V_{m+1} \tilde{H}_{MA},$$
که در آن:
\begin{enumerate}
\item
$V_m = [v_1, v_2, …, v_m]$
ماتریسی است با ستون‌های متعامد یکه تولیدشده.
\item 
$V_{m+1}$
 نیز ماتریسی است که شامل بردارهای 
$v_1$
تا
$ v_{m+1}$
است.
\item
$\tilde{H}{MA}$
یک ماتریس هسنبرگ با ابعاد
$ (m+1) \times m$
است که ضرایب 
$h_{i,j} $
حاصل از فرآیند آرنولدی را در خود جای داده است. \\
فرآیند مشابهی برای ماتریس 
$N^T B^T$
و بردار اولیه
$g$
طی می‌شود و رابطه مشابه زیر حاصل می‌گردد،
$$N^T B^T W_m = W_{m+1} \tilde{H}_{NB},$$
که در آن
$W_m$
و
$W_{m+1}$
ماتریس‌های متعامد یکه حاصل از فرآیند آرنولدی و
$\tilde{H}_{NB} $
ماتریس هسنبرگ حاصل برای این بخش است. در نتیجه داریم،
\begin{equation}\begin{aligned}\label{z00003}
MA V_m = V_{m+1} \tilde{H}_{MA},\quad\quad N^T B^T W_m = W_{m+1} \tilde{H}_{NB}.
\end{aligned}\end{equation}
در حل یک سیستم خطی به صورت کلی
$Ax = b$
اگر
$x_0$
یک تقریب اولیه از جواب باشد، باقی‌مانده آن به صورت زیر تعریف می‌شود،
$$r_0 = b - Ax_0.$$
این باقی‌مانده نشان‌دهنده میزان خطا در تخمین فعلی است. با توجه به اینکه معادله سیلوستر
\eqref{z00001}
، به صورت پیش‌شرطی‌شده زیر تبدیل شده است،
$$MAXN - MXBN = MCN,$$
با بازنویسی این معادله به صورت سیستم خطی با استفاده از حاصل‌ضرب کرونکر، داریم،
$$P_{M,N} x = c_{M,N},$$
پس از به‌دست‌آوردن اصلاح
$ z_0$
از طریق الگوریتم گالرکین، تقریب جدید از جواب به صورت زیر به‌روزرسانی می‌شود،
$$x_1 = x_0 + z_0.$$
با جایگذاری این مقدار در معادله باقی‌مانده داریم،
\begin{equation}\begin{aligned}\label{z00004}
r_1 = c_{M,N} - P_{M,N} x_1,
\end{aligned}\end{equation}
که در آن
$c_{M,N}$
همانند قبل، به صورت زیر تعریف شده است،
$$c_{M,N} = (N^T \otimes M)c.$$
$P_{M,N}$
نیز به صورت زیر تعریف شده است،
$$P_{M,N} = N^T \otimes MA + N^T B^T \otimes M,$$
به طوری که
\eqref{z00004}
با 
$K_{m}(N^{T}B^{T},g)\otimes K_{m}(MA,f)$
متعامد باشد.\\
در روش‌های گالرکین و حداقل باقیمانده، تصحیح 
$z_0$
باید در زیرفضایی انتخاب شود که بتواند بهترین کاهش را در باقی‌مانده ایجاد کند. این زیرفضا در این مقاله به صورت زیر در نظر گرفته شده است،
$$z_0 \in K_m(N^T B^T, g) \otimes K_m(MA, f),$$
این بدان معناست که 
$z_0$
باید از ترکیب خطی بردارهایی که توسط 
$W_m$
و 
$V_m$
تولید شده‌اند، ساخته شود. بنابراین، 
$z_0$
را می‌توان به صورت ترکیب خطی از این بردارها نوشت،
$$z_0 = \sum_{i=1}^m \sum_{j=1}^m y_{ij} (w_i \otimes v_j),$$
که در آن
$y_{ij}$
ضرایب این ترکیب خطی هستند. با توجه به خواص ضرب کرونکر و ساختار برداری، این رابطه را می‌توان به شکل ماتریسی ساده‌تر زیر نوشت،
\begin{equation}\begin{aligned}\label{z00005}
z_0 = (W_m \otimes V_m) y_0,
\end{aligned}\end{equation}
که در آن
$y_0$
برداری است با اندازه 
$m^2$
که شامل همه ضرایب
$y_{ij}$
است و 
$W_m \otimes V_m $
ماتریسی با ابعاد
$ n^2 \times m^2 $
می باشد که از حاصل‌ضرب کرونکر دو ماتریس 
$W_m$
و
$V_m$
به‌دست آمده است. \\
طبق رابطه
\eqref{z00004}
، باقی‌مانده پس از اصلاح
$ z_0$
به صورت زیر تعریف می‌شود،
$$r_1 = c_{M,N} - P_{M,N} x_1,$$
که با جایگذاری 
$x_1 = x_0 + z_0$
داریم،
$$r_1 = r_0 - P_{M,N} z_0.$$
با جایگذاری
$z_0$
از رابطه 
\eqref{z00004}
داریم،
$$z_0 = (W_m \otimes V_m) y_0,$$
بنابراین،
$$r_1 = r_0 - P_{M,N} (W_m \otimes V_m) y_0.$$
در روش گالرکین، شرط می‌شود که باقی‌مانده
$ r_1$
بر زیرفضای جستجو عمود باشد، یعنی،
$$(W_m \otimes V_m)^T r_1 = 0,$$
با جایگذاری
$ r_1$
داریم،
$$(W_m \otimes V_m)^T \left[ r_0 - P_{M,N} (W_m \otimes V_m) y_0 \right] = 0.$$
با توجه به تعریف
$ P_{M,N}$
داریم،
$$P_{M,N} = N^T \otimes MA + N^T B^T \otimes M,$$
با استفاده از خاصیت ضرب کرونکر نیز داریم،
$$P_{M,N} (W_m \otimes V_m) = (N^T W_m) \otimes (MA V_m) + (N^T B^T W_m) \otimes (M V_m).$$
با توجه به رابطه 
\eqref{z00003}
،
$$MA V_m = V_{m+1} \tilde{H}{MA}, \quad N^T B^T W_m = W{m+1} \tilde{H}_{NB},$$
و همچنین روابط متعامد یکه بودن، داریم،
$$W_m^T W_m = I, \quad V_m^T V_m = I.$$
با جایگذاری و ساده‌سازی، رابطه به صورت زیر در می‌آید،
$$\left(W_m^T N^T W_m\right) y_0 - H_{MA} y_0 - y_0 H_{NB} = \tilde{r}_0.$$
که با ساده‌سازی به شکل زیر درمی‌آید:
$$\tilde{r}_0 = (W_m \otimes V_m)^T r_0,$$
و
$$(W_m \otimes V_m)^T P_{M,N} (W_m \otimes V_m) y_0 = \tilde{r}_0.$$
در نهایت داریم،
\begin{equation}\begin{aligned}\label{z00006}
\left(W_m^T N^T W_m\right) y_0 - H_{MA} y_0 - y_0 H_{NB} = \tilde{r}_0,
\end{aligned}\end{equation}
که در آن:
\begin{enumerate}
\item[1.]
$W_m$
و 
$V_m $
ماتریس‌های متعامد یکه حاصل از فرآیند آرنولدی هستند.
\item[2.]
$N$
و
$M$
ماتریس‌های پیش‌شرطی برای 
$B$
و
$A$
هستند.
\item[3.]
$H_{MA}$
و
$H_{NB} $
و به ترتیب ماتریس‌های هسنبرگ بالا حاصل از فرآیند آرنولدی برای
$ MA$
و 
$N^T B^T $
هستند.
\item[4.]
$y_0 $
بردار ضرایب اصلاح است.
\item[5.]
$\tilde{r}_0 = (W_m \otimes V_m)^T r_0$
 بردار باقی‌مانده فشرده‌شده (تصویری) روی زیرفضای جستجو است.
\end{enumerate}
برای ساده‌سازی و حل راحت‌تر معادله
\eqref{z00006}
، تجزیه شور بر روی
$H_{MA}$
و
$H_{NB}$
انجام می‌شود،
$$H_{MA} = Q_{MA} R_{MA} Q_{MA}^, \quad H_{NB} = Q_{NB} R_{NB} Q_{NB},$$
که در آن:
\begin{enumerate}
\item[1.]
$Q_{MA}$
و 
$Q_{NB}$
ماتریس‌های یکانی هستند.
\item[2.]
$R_{MA} $
و 
$R_{NB} $
ماتریس‌های بالا مثلثی هستند.
\end{enumerate}
برای ساده‌سازی معادله، طرفین رابطه 
\eqref{z00006}
را در ماتریس یکانی
$Q_{NB} \otimes Q_{MA}$
ضرب می‌کنیم. این کار باعث ساده‌تر شدن ماتریس‌ها و افزایش پایداری عددی محاسبات می‌شود. بردارهای اصلاح‌شده را به صورت زیر تعریف می کنیم،
$$y_{0}^{'} = (Q_{NB} \otimes Q_{MA})^* y_0, \quad r_0^{'} = (Q_{NB} \otimes Q_{MA})^* \tilde{r}_0,$$
سپس با جایگذاری، رابطه به صورت زیر در می‌آید،
$$Q_{NB}^* W_m^T N^T W_m Q_{NB} \hat{y}_0 - R{MA} \hat{y}_0 - y_{0}^{'} R{NB} = r_{0}^{'}.$$
در نتیجه،
\begin{equation}\begin{aligned}\label{z00007}
Q_{NB}^* W_m^T N^T W_m Q_{NB}y_{0}^{'} - R{MA} y_{0}^{'} - y_{0}^{'} R{NB} = r_{0}^{'}.
\end{aligned}\end{equation}
که در آن،
\begin{equation}\begin{aligned}\label{z00008}
y_{0}^{'}=(Q_{NB}\otimes Q_{MA})^{*}y_{0},
\end{aligned}\end{equation}
و
$$r^{'}=(Q_{NB}\otimes Q_{MA})^{*}\tilde{r}_0.$$
در الگوریتم گالرکین، باقی‌مانده جدید پس از به‌روزرسانی جواب به صورت زیر تعریف می‌شود (بر اساس رابطه 
\eqref{z00004}
)،
$$r_1 = c_{M,N} - P_{M,N} x_1,$$
که با جایگذاری 
$x_1 = x_0 + z_0$
، خواهیم داشت،
$$r_1 = r_0 - P_{M,N} z_0.$$
با توجه به اینکه،
$$z_0 = (W_m \otimes V_m) y_0,$$
رابطه باقی‌مانده به صورت زیر بازنویسی می‌شود،
$$r_1 = r_0 - P_{M,N} (W_m \otimes V_m) y_0.$$
با توجه به اینکه،
$$P_{M,N} = N^T \otimes MA + N^T B^T \otimes M,$$
داریم،
$$P_{M,N} (W_m \otimes V_m) = (N^T W_m \otimes MA V_m) + (N^T B^T W_m \otimes M V_m).$$
همچنین با توجه به رابطه
\eqref{z00003}
، می‌توان نوشت،
$$MA V_m = V_{m+1} \tilde{H}{MA}, \quad N^T B^T W_m = W{m+1} \tilde{H}_{NB},$$
با جایگذاری این عبارات، داریم،
$$P_{M,N} (W_m \otimes V_m) = (N^T W_m \otimes V_{m+1} \tilde{H}{MA}) + (W{m+1} \tilde{H}_{NB} \otimes M V_m).$$
با جایگذاری این نتیجه در معادله باقی‌مانده، به رابطه زیر می‌رسیم،
\begin{equation}\begin{aligned}\label{z00009}
r_1 = r_0 - \left(N^T W_m \otimes V_{m+1} \tilde{H}{MA}\right) y_0 + \left(W{m+1} \tilde{H}_{NB} \otimes M V_m\right) y_0.
\end{aligned}\end{equation}
که در آن داریم:
\begin{enumerate}
\item[1.]
$r_1$
بردار باقی‌مانده پس از یک مرحله اصلاح و 
$r_0$
باقی‌مانده اولیه می باشد.
\item[2.]
$N^T W_m$
: نتیجه اعمال پیش‌شرطی 
$N^T$
بر ماتریس زیرفضای 
$W_m$
.
\item[3.]
$V_{m+1}$
و
$W_{m+1}$
: ماتریس‌هایی با بردارهای متعامد یکه از فرآیند آرنولدی برای زیرفضای کریلوف.
\item[4.]
$\tilde{H}{MA}$
و
$\tilde{H}{NB} $
ماتریس‌های هسنبرگ بالا حاصل از فرآیند آرنولدی برای ماتریس‌های
$ MA$
و
$ N^T B^T$
هستند.
\item[5.]
$M V_m$
: اعمال پیش‌شرطی 
$M$
روی زیرفضای
$ V_m$
.
\item[6.]
$	y_0:$
بردار ضرایب اصلاح است.
\end{enumerate}
حال به معرفی الگوریتمی می پردازیم که به حل معادله سیلویستر با استفاده از روش گالرکین پیش‌شرطی‌شده و گام به گام می‌پردازد. این روش به کمک زیرفضای کریلوف و فرآیند آرنولدی، مساله را به شکل مؤثرتری حل می‌کند.
\begin{al}
گام‌های الگوریتم به صورت زیر است،
\\\textbf{ورودی ها:}
\begin{enumerate}
\item[1.]
$x_0$
: یک تخمین اولیه برای جواب معادله.
\item[2.]
$\varepsilon > 0$
: مقدار تحمل خطا برای تعیین زمان توقف الگوریتم.
\item[3.]
$m$
: تعداد بُعد زیرفضای کریلوف در هر مرحله (تعداد بردارهای متعامد یکه تولید شده).
\end{enumerate}
\textbf{مراحل الگوریتم:}
\begin{enumerate}
\item[1.]
محاسبه باقی‌مانده اولیه: ابتدا باقی‌مانده اولیه محاسبه می‌شود،
$$r_0 = c_{M,N} - P_{M,N} x_0,$$
که در آن
$c_{M,N} = (N^T \otimes M) c$
و
$P_{M,N} = N^T \otimes MA + N^T B^T \otimes M$
.
\item[2.]
بررسی شرط توقف: اگر
$\|r_0\|_2 < \varepsilon$
الگوریتم متوقف می‌شود، زیرا تقریب فعلی به اندازه کافی به جواب دقیق نزدیک است.

\item[3.]
انتخاب بردارهای اولیه
$f$
و 
$g$
: دو بردار
$f$
و 
$g$
از
$\mathbb{R}^n$
به عنوان ورودی فرآیند آرنولدی انتخاب می‌شوند. این بردارها برای شروع فرآیند تولید زیرفضای کریلوف استفاده می‌شوند. 
\item[4.]
اجرای فرآیند آرنولدی و تولید زیرفضای کریلوف با استفاده از فرآیند آرنولدی: 
$V_m$
برای 
$MA$
و بردار 
$f$
، ماتریس‌های زیر تولید می‌شوند.\\
ماتریسی با ستون‌های متعامد یکه حاصل از زیرفضای کریلوف
$ K_m(MA, f)$
.\\
	$V_{m+1}$
: ماتریسی با یک ستون بیشتر از 
$V_m$
.\\
	$\tilde{H}_{MA}$
: ماتریس هسنبرگ حاصل از فرآیند آرنولدی.\\
برای 
$N^T B^T$
و بردار 
$g$
، ماتریس‌های مشابه تولید می‌شوند، یعنی،
$W_m$
،
$W_{m+1}$
و
$\tilde{H}_{NB}$
.
\item[5.]
باقی‌مانده فشرده‌شده
$\tilde{r}_0$
روی زیرفضای جستجو به صورت زیر محاسبه می‌شود،
$$\tilde{r}_0 = (W_m \otimes V_m)^T r_0.$$
\item[6.]
برای
$ \tilde{H}{MA} $
و
$ \tilde{H}{NB} $
تجزیه شور انجام می‌شود، یعنی،
$$\tilde{H}{MA} = Q{MA} R_{MA} Q_{MA},\quad \quad \tilde{H}{NB} = Q{NB} R_{NB} Q_{NB}.$$
\item[7.]
محاسبه باقی‌مانده اصلاح‌شده: باقی‌مانده اصلاح‌شده به صورت زیر محاسبه می‌شود،
$$r_{0}^{'} = (Q{NB} \otimes Q_{MA})^* \tilde{r}_0.$$
\item[8.]
حل معادله سیلویستر کوچک: معادله سیلویستر کوچک به صورت زیر حل می‌شود (بر اساس رابطه 
\eqref{z00007}
)،
$$Q_{NB}^* W_m^T N^T W_m Q_{NB} \, y_{0}^{'} - R{MA}y_{0}^{'} - y_{0}^{'} R{NB} = yr_{0}^{'},$$
که با استفاده از روش مستقیم حل می‌شود.
\item[9.]
ارزیابی 
$y_0$
: پس از حل معادله بالا،
$y_0$
به صورت زیر محاسبه می‌شود،
$$y_0 = (Q_{NB} \otimes Q_{MA})y_{0}^{'}.$$
\item[10.]
محاسبه بردار اصلاح
$ z_0$
: با استفاده از 
$y_0$
و رابطه 
\eqref{z00005}
، بردار اصلاح 
$ z_0$
محاسبه می‌شود:
$$z_0 = (W_m \otimes V_m) y_0.$$
\item[11.]
به‌روزرسانی جواب: تقریب جدید از جواب به صورت زیر به‌روزرسانی می‌شود،
$$x_0 = x_0 + z_0.$$
\item[12.]
به‌روزرسانی باقی‌مانده: باقی‌مانده جدید با استفاده از رابطه
\eqref{z00009}
به صورت بهینه محاسبه می‌شود،
$$r_0 = r_0 - \left(N^T W_m \otimes V_{m+1} \tilde{H}{MA}\right) y_0 + \left(W_{m+1} \tilde{H}_{NB} \otimes M V_m\right) y_0.$$
\item[13.]
بررسی شرط توقف و تکرار مراحل: اگر
$|r_0|_2 < \varepsilon$
الگوریتم متوقف می‌شود، در غیر این صورت، با بردارهای
$f$
و
$g$
جدید، مراحل از ابتدا تکرار می‌شوند.

\end{enumerate}
نکات مهم الگوریتم:
\begin{enumerate}
\item[1.]
این الگوریتم به صورت بازنشانی‌شده اجرا می‌شود، یعنی پس از هر 
$m$
گام، مجدداً از ابتدا با زیرفضای جدید شروع می‌شود.
\item[2.]
در هر مرحله، تلاش می‌شود با استفاده از زیرفضای کریلوف کوچک‌تر، محاسبات سریع‌تر و با هزینه کمتر انجام شوند.
\item[3.]
مزیت اصلی الگوریتم این است که به‌جای کار با ماتریس‌های بزرگ، مساله را به یک مسئله کوچک‌تر تبدیل می‌کند که به‌سرعت قابل حل است.
\end{enumerate}
\end{al}