
\chapter{ مفاهیم و تعاریف پایه}
\thispagestyle{empty}
\newpage
\section{مقدمه}
معادلات ماتریسی سیلوستر نقش مهمی در نظریه کنترل و بسیاری از شاخه‌های دیگر مهندسی ایفا می‌کنند. بدون از دست دادن کلیت، در این پایان نامه فرض شده برای معادله سیلوستر است که 
$n = m$
. شرط لازم و کافی برای وجود جواب یکتا برای این معادله آن است که طیف‌های ماتریسی 
$A$
و
$B$
اشتراک نداشته باشند، یعنی،
$$S(A) \cap S(B) = \emptyset.$$
روش‌های بارتیلز-استوارت و گولوب-نش-ون لون از اولین روش‌های عددی پایدار برای حل معادله سیلوستر هستند. این روش‌ها برای ماتریس‌های متراکم کاربرد دارند، اما زمانی که ماتریس‌ها بزرگ و پراکنده باشند، استفاده از روش‌های تکراری مانند روش ضمنی با جهت متناوب پیشنهاد می‌شود. یکی از روش‌های کارآمد برای حل معادلات سیلوستر، استفاده از زیرفضای کریلوف با الگوریتم‌های گالرکین و حداقل باقیمانده است. نرخ همگرایی این روش‌ها به ویژگی‌های طیفی ماتریس وابسته است. بنابراین، استفاده از پیش‌شرط‌سازی می‌تواند طیف ماتریس را به شکلی مطلوب‌تر تبدیل کند و موجب تسریع همگرایی شود. اگر 
$M$
و 
$N$
پیش‌شرط‌های تقریبی معکوس برای ماتریس‌های
$A$
و
$B$
باشند، معادله سیلوستر به فرم زیر تبدیل می‌شود،
$$MAXN - MXBN = MCN.$$
هدف اصلی این پایان نامه، ارائه نسخه‌های پیش‌شرطی‌شده از الگوریتم‌های گالرکین و حداقل باقیمانده برای حل مؤثرتر معادله سیلوستر است. این الگوریتم‌ها با استفاده از فرآیند آرنولدی، پایه‌های متعامد از زیرفضای کریلوف را تولید کرده و مرتبه معادله را کاهش می‌دهند. آزمایش‌های عددی نشان داده‌اند که این نسخه‌های پیش‌شرطی‌شده، نسبت به نسخه‌های بدون پیش‌شرطی، هم از نظر دقت و هم از نظر کارایی برتری دارند. در این فصل به بیان مقدماتی می پردازیم که در سراسر پایان نامه به آن ها نیاز داریم.
\section{اهمیت و ضرورت تحقیق}
معادلات سیلوستر از جمله معادلات پایه‌ای در ریاضیات کاربردی هستند که در حوزه‌های مختلفی نظیر نظریه کنترل، پردازش سیگنال، تحلیل پایداری، محاسبات علمی، و مهندسی سیستم‌ها نقش حیاتی ایفا می‌کنند. حل دقیق و سریع این معادلات برای تحلیل و طراحی سیستم‌ها ضروری است. با این حال، حل این معادلات به ویژه زمانی که ماتریس‌های
$A$
و
$B$
بزرگ و پراکنده باشند، به دلیل پیچیدگی محاسباتی و محدودیت‌های حافظه، به یک چالش جدی تبدیل می‌شود.\\
روش‌های کلاسیک مانند الگوریتم‌های بارتیلز-استوارت و گولوب-نش-ون لون اگرچه برای ماتریس‌های کوچک و متراکم کارآمد هستند، اما در مواجهه با ماتریس‌های بزرگ و پراکنده ناکارآمد می‌شوند. به همین دلیل، استفاده از روش‌های تکراری مبتنی بر زیرفضای کریلوف (مانند روش‌های گالرکین و حداقل باقیمانده) به عنوان راهکارهای مناسب برای حل این معادلات مطرح شده‌اند. با این وجود، این روش‌ها نیز ممکن است در صورت داشتن طیف نامطلوب برای ماتریس‌های مسئله، نرخ همگرایی پایین داشته باشند. در اینجا ضرورت استفاده از پیش‌شرط‌سازی مطرح می‌شود. پیش‌شرط‌سازی، تکنیکی برای بهبود ویژگی‌های طیفی ماتریس‌ها است که منجر به تسریع همگرایی روش‌های تکراری می‌شود. این مقاله با هدف ارائه نسخه‌های پیش‌شرطی‌شده از روش‌های گالرکین و حداقل باقیمانده، اهمیت بالایی دارد زیرا:
\begin{enumerate}
\item
افزایش کارایی: نسخه‌های پیش‌شرطی‌شده می‌توانند سرعت همگرایی را به‌طور قابل توجهی افزایش دهند و نیاز به تکرارهای زیاد را کاهش دهند؛
\item
کاهش هزینه محاسباتی: کاهش تعداد تکرارها و کاهش نیاز به حافظه، موجب می‌شود این روش‌ها برای حل معادلات سیلوستر بزرگ و پراکنده مناسب‌تر شوند؛
\item
افزایش دقت و پایداری: الگوریتم‌های پیشنهادی، دقت بیشتری را در حل معادلات ارائه می‌دهند و از نظر عددی پایدارتر هستند؛
\item
گسترش کاربردها: ارائه این روش‌ها می‌تواند منجر به کاربردهای گسترده‌تر در حوزه‌های مختلف مهندسی و علوم شود.
\end{enumerate}
در نتیجه، این تحقیق با ارائه رویکردی نوین برای بهبود کارایی و دقت روش‌های عددی، گامی مؤثر در راستای حل چالش‌های مرتبط با معادلات سیلوستر برداشته است و 

\section{اهداف تحقیق}
در این پایان نامه با هدف بهبود روش‌های عددی برای حل مؤثر معادلات سیلوستر اهداف اصلی زیر را دنبال می کنیم:
\begin{enumerate}
\item
ارائه نسخه‌های پیش‌شرطی‌شده از الگوریتم‌های گالرکین و حداقل باقیمانده:
\\توسعه و معرفی نسخه‌های پیش‌شرطی‌شده از الگوریتم‌های 
$Galerkin$
و
$ Minimal Residual (MR)$
 برای حل معادله سیلوستر زیر،
$$AX - XB = C.$$
به‌کارگیری پیش‌شرط‌کننده‌های مناسب
$ M$
و
$ N $
برای ماتریس‌های
$ A $
و
$ B $
به‌منظور بهبود ویژگی‌های طیفی و تسریع همگرایی الگوریتم‌ها.
\item
کاهش پیچیدگی محاسباتی:
\\استفاده از فرآیند آرنولدی جهت تولید پایه‌های متعامد از زیرفضای کریلوف و کاهش مرتبه معادلات سیلوستر.
\\کاهش هزینه‌های محاسباتی و حافظه مورد نیاز با بهینه‌سازی مراحل محاسباتی در الگوریتم‌های پیشنهادی.
\item
 افزایش دقت و پایداری عددی الگوریتم‌ها:
\\بهبود دقت و پایداری الگوریتم‌ها از طریق اعمال پیش‌شرط‌سازی مؤثر، به‌گونه‌ای که راه‌حل‌های عددی با خطای کمتر و پایداری بیشتر به دست آیند.
\ارائه رویکردهای دقیق برای محاسبه باقیمانده‌ها و ارزیابی همگرایی روش‌ها.
\item
ارزیابی تجربی و مقایسه با روش‌های کلاسیک:
\\انجام آزمایش‌های عددی گسترده برای مقایسه کارایی نسخه‌های پیش‌شرطی‌شده با نسخه‌های بدون پیش‌شرطی.
\\بررسی تعداد تکرارها، میزان دقت و زمان محاسباتی برای نشان دادن مزایای روش‌های پیشنهادی.
\item
فراهم‌سازی الگوریتم‌های کارآمد برای حل مسائل بزرگ و پراکنده:
\\طراحی الگوریتم‌هایی که به‌ویژه برای معادلات سیلوستر با ماتریس‌های بزرگ و پراکنده مناسب باشند.
\\ارائه روش‌هایی که بتوانند در کاربردهای واقعی و مسائل صنعتی مورد استفاده قرار گیرند.
\end{enumerate}
این اهداف در راستای ارتقاء دانش و ارائه راهکارهای نوین برای حل مؤثر معادلات سیلوستر در مسائل علمی و مهندسی تدوین شده‌اند.
\section{تعاریف پایه}
\begin{definition}[مقادیر ویژه-بردار ویژه]
ماتریس مربعی
$A$
را در نظر بگیرید. 
$\lambda$
را یک مقدار ویژه
$A$
و بردار غیر صفر 
$x$
را یک بردار ویژه متناظر با 
$\lambda$
می نامیم هرگاه،
 \begin{align*}
Ax=\lambda x.
\end{align*}
\end{definition}
\begin{definition}[اثر ماتریس]\label{con2}
اثر ماتریس مربعی
$[A]_{n\times n}$
به صورت زیر تعریف می شود،
$$tr(A)=\sum_{i=1}^{n}a_{ii},$$
که در آن
$a_{ii}$
درایه های ستون 
$i$
اُم 
$A$
می باشند. 
\end{definition}
\begin{definition}[ماتریس وارون پذیر]
در جبرخطی یک ماتریس مربعی
$n\times n$
مانند 
$A$
را وارون پذیر(ناتکین) گویند، اگر ماتریس مانند 
$B$
یافت شود که:
\begin{align*}
AB=BA=I_{n}.
\end{align*}
که 
$I_{n}$
ماتریس همانی
$n\times n$
است و منظور از 
$AB$
ضرب ماتریسی است. اگر چنین باشد آنگاه\\می توان ماتریس 
$B$
را یگانه وارون 
$A$
خواند. وارون 
$A$
را با
$A^{-1}$
نمایش داده می شود.
\end{definition}
\begin{definition}
یک ماتریس مربعی را نامنفرد
\LTRfootnote{Non-singular}
 می نامیم اگر و تنها اگر دترمینانش ناصفر باشد. بنابراین یک ماتریس معکوس پذیر نیز است.
\end{definition}
\begin{definition}[ماتریس نیمه معین مثبت]
فرض کنید 
$A$
یک ماتریس متقارن باشد، آنگاه 
$A$
را نیمه معین مثبت
\LTRfootnote{positive semidefinite }
 می نامیم (با نماد 
$A\succeq\;0$
نشان می دهیم)، اگر تمام مقادیر ویژه 
$A$
نامنفی باشند. 
$A$
معین مثبت
\LTRfootnote{positive definite}
 می نامیم (با نماد 
$A\succ\;0$
نشان می دهیم)، اگر تمام مقادیر ویژه 
$A$
مثبت باشند.
\end{definition}

\begin{definition}[ماتریس یکانی]
ماتریس مربعی 
$U$
را یکانی 
\LTRfootnote{Unitary}
می نامیم اگر 
$U^{*}=U^{-1}$
باشد. به عنوان مثال ماتریس 
$A=\left[
\begin{array}{ccc}
2^{-\frac{1}{2}} &2^{-\frac{1}{2}}&0 \\
-2^{-\frac{1}{2}}i &2^{-\frac{1}{2}}i&0 \\
0&0&i \\
\end{array}\right]$
یک ماتریس یکانی است.

\end{definition}
\begin{definition}[شعاع طیفی]
شعاع طیفی ماتریس 
$A$
را به صورت زیر تعریف می کنیم،
$$\rho(A)=\sup\{\ |\lambda|:\hspace{0.1cm}\lambda\in\sigma(A)\}\ ,$$
که در آن 
$\sigma(A)$
مجموعه مقادیر ویژه 
$A$
می باشد.
\end{definition}
\begin{definition}[
$M$
-ماتریس
]
ماتریس 
$A$
را یک 
$M$
-ماتریس می نامیم اگر:
\begin{enumerate}
\item
دارای الگوی 
$Z$
باشد، یعنی عناصر غیر قطری
$A$
نامثبت باشند.
\item
وارون 
$A$
موجود و دارای اعضای نامنفی باشد، یعنی،
$$A^{-1}\ge\;0.$$
\end{enumerate}
\end{definition}
\begin{definition}[
کران طیفی
]
کران طیفی ماتریس 
$A$
بزرگترین بخش حقیقی از بین تمام مقادیر ویژه آن است، یعنی،
$$m(A)=\sup\{\ Re\lambda:\hspace{0.1cm}\lambda\in\sigma(A)\}\ .$$
\end{definition}
\begin{definition}[معادله سیلوستر]
معادله سیلوستر به صورت زیر تعریف می‌شود،
$$AX - XB = C,$$
که در آن:
\begin{enumerate}
\item
$A \in \mathbb{R}^{n \times n}$؛
\item
$B \in \mathbb{R}^{m \times m}$؛
\item
$C \in \mathbb{R}^{n \times m}$
\item
$X \in \mathbb{R}^{n \times m}$
ماتریس مجهول است.
\end{enumerate}
\end{definition}
\begin{lemma}[شرط وجود جواب یکتا برای معادله سیلوستر]
معادله 
$AX - XB = C$
دارای جواب یکتا است اگر و فقط اگر،
$$S(A) \cap S(B) = \emptyset,$$
که در آن
$ S(A)$
و
$S(B)$
به ترتیب طیف (مجموعه مقادیر ویژه) ماتریس‌های
$A$
و
$B$
هستند.
\end{lemma}
برای اثبات به مرجع 
\cite{02}
مراجعه کنید.
\begin{definition}[پیش‌شرطی‌سازی]
اگر
$M$
و 
$N$
پیش‌شرط‌های تقریبی معکوس ماتریس‌های
$A$
و 
$B$
باشند به‌طوری که،
$$MA \approx I \quad \text{و} \quad NB \approx I,$$
آنگاه معادله سیلوستر پیش‌شرطی‌شده به فرم زیر تبدیل می‌شود،
$$MAXN - MXBN = MCN.$$
\end{definition}
\begin{definition}[زیرفضای کریلوف]
زیرفضای کریلوف مرتبه 
$m$
برای ماتریس 
$A$
و بردار اولیه
$r$
به صورت زیر تعریف می‌شود،
$$\mathcal{K}_m(A, r) =span \{r, Ar, A^2r, \dots, A^{m-1}r\}.$$
\end{definition}
\begin{definition}[فرآیند آرنولدی]
برای تولید پایه‌های متعامد از زیرفضای کریلوف، فرآیند آرنولدی
\LTRfootnote{Arnoldi Process}
به صورت زیر عمل می‌کند:
\begin{enumerate}
\item
انتخاب بردار اولیه 
$v_1 = \frac{r}{\|r\|_2}$
؛
\item
برای 
$j = 1, 2, …, m$
محاسبه
$w = Av_j$؛
\item
برای
$ i = 1, …, j$ 
محاسبه
$ h_{ij} = v_i^T w$
؛
\item
به‌روزرسانی
$ w = w - h_{ij}v_i$
؛
\item
محاسبه
$h_{j+1,j} = \|w\|_2$
؛
\item
اگر
$h_{j+1,j} \neq 0$
، آنگاه 
$ v_{j+1} = \frac{w}{h_{j+1,j}}$
.
\end{definition}
\begin{definition}[روش گالرکین
]
روش گالرکین 
\LTRfootnote{Galerkin Method}
با استفاده از زیرفضای کریلوف به دنبال یافتن 
$x_m $
است که باقیمانده را بر این فضا عمود کند:
$$r_m = b - Ax_m,$$
و شرط گالرکین به صورت زیر تعریف می‌شود،
$$r_m \perp \mathcal{K}_m(A, r_0).$$

\end{definition}
\begin{definition}[روش حداقل باقیمانده]
در این روش، هدف یافتن 
$x_m$
است که نرم اقلیدسی باقیمانده را مینیمم کند، به عبارت دیگر،
$$x_m = \underset{x \in x_0 + \mathcal{K}_m(A, r_0)}{\operatorname{argmin}} \|b - Ax\|_2,$$
\end{definition}
\begin{definition}[ضرب کرونکر]
ضرب کرونکر بین دو ماتریس 
$A \in \mathbb{R}^{m \times n} $
و 
$B \in \mathbb{R}^{p \times q} $
به صورت زیر تعریف می‌شود،
$$A \otimes B =
\begin{bmatrix}
a_{11}B & a_{12}B & \cdots & a_{1n}B \\
a_{21}B & a_{22}B & \cdots & a_{2n}B \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1}B & a_{m2}B & \cdots & a_{mn}B
\end{bmatrix}.$$
\end{definition}
\begin{definition}[ فاکتورگیری شور ]
هر ماتریس مربعی
$A$
را می‌توان به فرم زیر فاکتورگیری کرد،
$$A = Q R Q^*,$$
که در آن:
\begin{enumerate}
\item
$Q$
ماتریسی واحدی است؛
\item
$R$
ماتریسی بالا مثلثی است؛
\item
$Q^*$
 ترانهاده مزدوج
$Q$
است.
\end{enumerate}
\end{difinition}
\begin{definition}[ بازنویسی معادله سیلوستر به صورت سیستم خطی]
با استفاده از ضرب کرونکر، معادله سیلوستر به صورت زیر بازنویسی می‌شود،
$$(I \otimes A - B^T \otimes I) \cdot vec(X) = vec(C),$$
که در آن:
\begin{enumerate}
\item
$vec(X) $
برداری است که با کنار هم قرار دادن ستون‌های ماتریس
$X$
ساخته می‌شود؛
\item
$\otimes $
ضرب کرونکر است.

\end{difinition}
\begin{definition}[ضرب آدامار]
فرض کنید
$A=(a_{ij})$
و
$B=(b_{ij})$
ماتریس های 
$m\times n$
باشند، ضرب آدامار 
\LTRfootnote{hadamard product}
،
$A$
و
$B$
را به صورت 
$AoB=(a_{ij}b_{ij})$
تعریف می کنیم.
\end{definition}
\begin{definition}[بُرد عددی]
بُرد عددی
\LTRfootnote{numerical range}
ماتریس 
$A\in\mathbb{M}_{n}(\mathbb{C})$
را به صورت زیر تعریف می کنیم:
$$W(A)=\{\ x^{*}Ax|\hspace{0.1cm}x\in\mathbb{C}^{n},\hspace{0.1cm}x^{*}x=1\}\ .$$
\end{definition}
\begin{definition}[قطاع]
برای 
$\alpha\in[0,\frac{\pi}{2})$
،
قطاع 
\LTRfootnote{sector}
در صفحه مختلط را به صورت زیر تعریف می کنیم:
$$S_{\alpha}=\{\ z\in\mathbb{C}|\hspace{0.1cm}\mathcal{R}z\ge\;0,\hspace{0.1cm}|\mathcal{I}z|\le\;(\mathcal{R}z)\tan(\alpha)\}\ ,$$
همچنین داریم:
$$S_{\alpha}^{'}=\{\ z\in\mathbb{C}|\hspace{0.1cm}\mathcal{R}z\ge\;0,\hspace{0.1cm}\mathcal{I}z\ge\;0,\hspace{0.1cm}\mathcal{I}z\le\;(\mathcal{R}z)\tan(\alpha)\}\ ,$$
\end{definition}
\begin{definition}
در جبر خطی رتبه ماتریس
\LTRfootnote{Rank of matrix}
$A$
برابر با بُعد فضای برداری تولید شده توسط ستون های آن است. این رتبه متناظر با تعداد حداکثر ستون های مستقل خطی 
$A$
است. رتبه ماتریس
$A$
را معمولاً با 
$rank(A)$
نشان می دهیم. رتبه ستونی ماتریس 
$A$
بُعد فضای ستونی 
$A$
است، در حالی که رتبه سطری 
$A$
، بُعد فضای سطری آن است. یک نتیجه اساسی در جبر خطی این است که رتبه ستونی و رتبه سطری همیشه با هم برابر هستند. این عدد(یعنی تعداد سطرها و ستون ها مستقل خطی) رتبه 
$A$
نامیده می شود.
\end{definition}
\begin{example}
ماتریس زیر را در نظر بگیرید:
\begin{align*}
M(T)=\left[
\begin{array}{ccc}
1 &0&1  \\
-2 &-3 &1  \\
3 &3&0 \\
\end{array}
\right].
\end{align*}
رتبه این ماتریس 
$2$
است. دو ستون اول این ماتریس مستقل خطی هستند. پس، رتبه ماتریس، حداقل 2 است؛ اما از آنجا که ستون سوم یک ترکیب خطی از دو ستون اول است(اولی منهای دومی)، سه بردار وابسته خطی هستند و به همین دلیل، رتبه ماتریس کمتر از 
$3$
است.
\end{example}
\begin{theorem}[شرط وجود و یکتایی جواب معادله سیلوستر
]
معادله سیلوستر
$AX - XB = C$
دارای جواب یکتا است اگر و فقط اگر طیف ماتریس‌های 
$A$
و 
$B$
اشتراک نداشته باشند،
$$S(A) \cap S(B) = \emptyset.$$
\end{theorem}
\proof
معادله سیلوستر را می‌توان به صورت سیستم خطی زیر بازنویسی کرد،
$$(I \otimes A - B^T \otimes I)vec(X) = vec(C),$$

که در آن
$vec(X)$
بردار حاصل از قرار دادن ستون‌های
$X$
به‌صورت پشت سر هم است. برای وجود جواب یکتا، باید ماتریس
$ (I \otimes A - B^T \otimes I) $
معکوس‌پذیر باشد. طبق ویژگی‌های ضرب کرونکر، مقادیر ویژه این ماتریس به صورت زیر هستند،
$$\lambda_i(A) - \lambda_j(B), \quad \forall i, j.$$
بنابراین، ماتریس فوق زمانی معکوس‌پذیر است که،
$$\lambda_i(A) \neq \lambda_j(B), \quad \forall i, j,$$
که معادل با شرط عدم اشتراک طیف‌ها است، یعنی،
$$S(A) \cap S(B) = \emptyset.$$
پس شرط وجود و یکتایی جواب اثبات می‌شود. 
\hfill\fbox{}
\endproof
\begin{theorem}[خواص ضرب کرونکر
]
برای ماتریس‌های 
$A, B, C, D$
با ابعاد مناسب، روابط زیر برقرار است،
\begin{enumerate}
\item	
$(A \otimes B)(C \otimes D) = (AC) \otimes (BD)$؛
\item
$(A \otimes B)^T = A^T \otimes B^T$؛
\item
$$(A \otimes B)^{-1} = A^{-1} \otimes B^{-1}, \quad  \text{ معکوس‌پذیر باشند}A \text{ و } B \text{اگر }.$$
\end{theorem}
\proof
\begin{enumerate}
\item

اثبات رابطه اول،
$$(A \otimes B)(C \otimes D) = A C \otimes B D.$$
این رابطه از تعریف ضرب کرونکر و خاصیت جابجایی در ضرب ماتریسی پیروی می‌کند.
\item
اثبات رابطه دوم،
$$(A \otimes B)^T = (a_{ij}B)^T = a_{ij}B^T = A^T \otimes B^T.$$
\item
اثبات رابطه سوم: اگر 
$(A \otimes B)(A^{-1} \otimes B^{-1}) $
را محاسبه کنیم:
$$(A A^{-1}) \otimes (B B^{-1}) = I \otimes I = I.$$
بنابراین،
$$(A \otimes B)^{-1} = A^{-1} \otimes B^{-1}.$$
\hfill\fbox{}
\endproof
\begin{theorem}[شرط همگرایی روش گالرکین
]
روش گالرکین برای حل معادله 
$Ax = b$
زمانی همگرا می‌شود که ماتریس
$A$
مثبت معین باشد.
\end{theorem}
برای اثبات به مرجع 
\cite{09}
مراجعه کنید.