\numberwithin{algorithm}{chapter}
\numberwithin{figure}{chapter}
\numberwithin{equation}{chapter}
\numberwithin{table}{chapter}
%%========================================
\chapter{پیش‌نیازها}
\label{Chapter1} 
\hspace{5mm}

 
 

در این بخش برخی از مفاهیم، تعاریف و قضایا که در  فصل‌های آینده به آنها نیاز داریم بیان  می‌کنیم.
\section{تعاریف و قضایا }  


ماتریس  
$ A\in {{\mathbb{R}}^{n\times n}}  $ 
 \gls{sym}
 نامیده می‌شود هرگاه $ A^{T}=A$ و ماتریس
$ A\in {{\mathbb{C}}^{n\times n}}  $ 
  \gls{her}
 گفته می‌شود هرگاه  
 $A^*=A$. 
 ماتریس  
$ A\in {{\mathbb{R}}^{n\times n}}  $ 
را  \gls{sksym}
%\LTRfootnote{Skew-symmetric}
 می‌نامند هرگاه $ A^{T}=-A$ و ماتریس
$ A\in {{\mathbb{C}}^{n\times n}}  $ 
را 
\gls{skher}
%\LTRfootnote{Skew-Hermitian}
 گویند هرگاه  $A^*=-A $.
 هر ماتریس 
 $A\in \mathbb{C}^{n\times n}$ 
 را می‌توان به‌صورت یکتا به صورت  مجموع یک ماتریس هرمیتی و هرمیتی کج نوشت که این تجزیه را تجزیه‌ی هرمیتی و هرمیتی کج ماتریس 
 $A$
 می‌نامند. قسمت هرمیتی  $A$ را   با 
 $A_H$ 
 نشان می‌دهیم. می‌توان دید 
 $A_H=\frac{1}{2}(A+A^*)$ 
 و در نتیجه قسمت هرمیتی کج برابر است با 
 $S=َA-A_H=\frac{1}{2}(A-A^*)$.

ماتریس حقیقی 
$ A \in {\mathbb{R}^{n\times n}}    $ 
یک ماتریس متعامد
%\LTRfootnote{Orthogonal}
 نامیده می‌شود، هرگاه 
$ A^{T}A=AA^{T}=I $ 
و   ماتریس مختلط 
 $A\in \mathbb{C}^{n\times n}$  
 را  یکانی
 %\LTRfootnote{Unitary}
  گویند هرگاه 
$ A^{*}A=AA^{*}=I $. 

 ماتریس 
$A\in \mathbb{C}^{n\times n}$ 
را 
\gls{hpd}
می‌گویند هرگاه 
$A^*=A$ 
و برای هر 
$x \in \mathbb{C}^n$
داشته باشیم 
$x^* A x>0$. 
به طور مشابه	 ماتریس 
$A\in \mathbb{C}^{n\times n}$ 
را \gls{hpsd}
 می‌نامند، هرگاه 
$A^*=A$ 
و برای هر 
$x \in \mathbb{C}^n$
داشته باشیم 
$x^* A x\geq 0$. 
ماتریس $A\in \mathbb{C}^{n\times n}$
\gls{pd}
%\LTRfootnote{Positive definiten}
  %\LTRfootnote{Positive semidefiniten}
   نامیده می‌شود، هرگاه ماتریس
$A+A^*$
یک ماتریس
 \gls{hpd}
  باشد. 

\gls{diag}
ماتریس 
$A$ 
برابر بردار عناصر روی قطر ماتریس
$A$
تعریف می‌شود که آن را با 
$\text{\rm diag}(A)$
نشان می‌دهیم. فرض کنید 
$A \in {{\mathbb{C}}^{n\times n}}$
به صورت 
$A=(a_{ij})   $ 
باشد. 
ماتریس 
$A$
را قطری
%\LTRfootnote{Diagonal} 
گویند، هرگاه به ازای
$ i \neq j$،
${a}_{ij}=0 $. 
یک ماتریس قطری را با 
$\diag_{n}(a_{11},a_{22}, ... ,a_{nn})$
نشان می‌دهیم.
اگر 
به ازای
$ i > j$،
${a}_{ij}=0 $، 
ماتریس 
$A$
 بالامثلثی و اگر به ازای
$ i \geq j$،
${a}_{ij}=0 $،
ماتریس 
$A$
بالامثلثی اکید نامیده می‌شود. ماتریس‌های پایین‌مثلثی و پایین‌مثلثی اکید نیز به همین صورت تعریف می‌شوند. 
فرض کنید ماتریس 
$A=(A_{ij})$
که در آن 
$(A_{ij})$
  بلوک‌های ماتریس 
  $A$ هستند. 
در این صورت 
ماتریس 
$A$
را قطری‌بلوکی گویند، هرگاه به ازای
$ i \neq j$،
$A_{ij}=0 $. 
یک ماتریس قطری‌بلوکی  را معمولاً به صورت  
$\diag_{n}(A_{11},A_{22}, ... ,A_{nn})$
نشان می‌دهیم.
اگر 
به ازای
$ i > j$،
$A_{ij}=0 $، 
ماتریس 
$A$
را بالامثلثی‌بلوکی و اگر به ازای
$ i \geq j$،
$A_{ij}=0 $، 
ماتریس 
$A$
را بالامثلثی‌بلوکی اکید می‌گویند. ماتریس‌های پایین‌مثلثی‌بلوکی و پایین‌مثلثی‌بلوکی اکید نیز به همین صورت تعریف می‌شوند. 

 
	فرض کنید
	$A = (a_{ij}) \in {{\mathbb{R}}^{n\times n}}$
	یا
	$.A \in {{\mathbb{C}}^{n\times n}}$
	در این صورت ماتریس $A$ را 
	\gls{upph}
	می‌گویند، هرگاه 
	$a_{ij} = 0 $
	به ازای 
	$.i - j >1$
	و همچنین ماتریس $A$  \gls{lowh} نامیده می‌شود، هرگاه 
	$a_{ij} = 0 $
	به ازای 
	$ .j-i >1$
	
	\begin{lemma}
		فرض کنید 
		$A\in{{\mathbb{C}}^{n\times n}}$،
		 معین مثبت هرمیتی باشد. در این صورت یک ماتریس معین مثبت هرمیتی مانند
		$B$
		وجود دارد به طوری که 
		$.B^{2}=A~$
		ماتریس 
		$B$
		را با 
		$A^{\frac{1}{2} }$
		نشان  می‌دهیم.
	\end{lemma}

\begin{remark}
	\begin{enumerate}[1)]
	\item
	اگر $P$ یک ماتریس معین مثبت (هرمیتی یا غیرهرمیتی) باشد، آنگاه  $P$ وارون‌پذیر است و 
	$P^{-1}$
	نیز یک ماتریس معین مثبت (هرمیتی یا غیرهرمیتی) است. 
	  \item 
	  اگر
	   $P$
	    یک ماتریس معین مثبت (هرمیتی یا غیرهرمیتی) باشد، آنگاه به ازای هر ماتریس 
	  $A$،
	   ماتریس 
	   $A^*PA$
	     یک ماتریس نیمه معین مثبت (هرمیتی یا غیرهرمیتی)  است. 
\item 
اگر 
$P_1$   و $ P_2$ 
دو ماتریس نیمه معین مثبت باشند، آنگاه ماتریس
$P_1+P_2$
یک ماتریس نیمه معین مثبت   است و به‌علاوه  اگر یکی از این دو ماتریس معین مثبت باشد، آنگاه ماتریس مجموع آنها نیز معین مثبت خواهد بود.  
	  \item 

	اگر $A\in{{\mathbb{C}}^{n\times n}}$،
	معین مثبت هرمیتی و 
	$P$ 
	و
	$S$
	به ترتیب ماتریس‌های معین مثبت و هرمیتی کج باشند، آنگاه ماتریس‌های
	$A^{\frac{1}{2}}PA^{\frac{1}{2}}$
	و
	$A^{\frac{1}{2}}SA^{\frac{1}{2}}$
	به ترتیب معین مثبت و هرمیتی کج هستند. 
		\end{enumerate}
\end{remark}
 




\gls{sigma}
ماتریس 
$A$
را با 
$\sigma(A)$
نشان می‌دهیم.  
 \gls{null}
  و 
 \gls{rang}
 ماتریس  
$A \in \mathbb{C}^{m \times n}$ 
 را که با 
 نمادهای 
 $\text{\rm nul}{(A)}$
 و 
${\rm range}(A)$
  نشان می‌دهند،  به صورت 
\begin{align*}
&{\rm range}(A) = \{ Ax: ~x\in{{\mathbb{C}}^{n}}\},\\
&{\rm null}(A) = \{ x\in{{\mathbb{C}}^{n}}: Ax=0\}.
\end{align*}
 تعریف می‌کنند.
\begin{remark}
	فرض کنید 
		$A \in \mathbb{C}^{n \times n}$.
		اگر 
		$A$
	 نیمه معین مثبت باشد، آنگاه 
	$\nul(A) \subseteq \nul(A+A^*)$
	و اگر
$A$ 	
	 نامنفرد باشد،  داریم 
	$\nul(A) =\{0\}$ و ${\rm range}(A)  =\mathbb{C}^{m}$.
\end{remark}

فرض کنید 
$A\in \mathbb{C}^{n\times n}$.
اگر عددی مانند  
$\lambda \in \mathbb{C}$
و بردار ناصفری متناظر با آن مانند 
$x \in \mathbb{C}^{n}$
وجود داشته باشد که 
$Ax=\lambda x$،
آنگاه $\lambda$
را یک مقدار ویژه‌ی ماتریس 
$A$ 
و 
$x$
را بردار ویژه‌ی متناظر با آن گویند.  زوج 
$(\lambda,x)$
را یک زوج ویژه‌ی ماتریس $A$ نامند. 
هر ماتریس 
$n \times n$
دارای 
$n$ 
مقدار ویژه می‌باشد که ممکن است بعضی از آنها تکراری باشند. 
به مرتبه‌ی تکرار هر مقدار ویژه، تکرار جبری آن مقدار ویژه گفته می‌شود. 
به  جذر هر مقدار ویژه از ماتریس 
$A^*A$،
یک مقدار تکین ماتریس
$A$
گویند.
 
 \gls{rho} 
 ماتریس 
$A$ 
را که با 
$\rho(A)$
نشان داده می‌شود، به صورت  
$$\rho(A)=\max\{|\lambda|:~~\lambda \in \sigma(A)\},$$
تعریف می‌شود. به‌علاوه   \gls{nu} ماتریس 
$A$ 
 که با 
$\nu(A)$
نشان داده می‌شود،    به صورت 
 \begin{align*}
 \nu(A)=\max\{|\lambda|:~~\lambda \in \sigma(A), \lambda \neq 1\},
 \end{align*}
  خواهد بود.
\begin{remark}
	\begin{enumerate}[1)]
		\item
		ماتریس
		$A$
		نامنفرد است اگر و تنها اگر مقدار ویژه‌ی  صفر نداشته باشد.
	 \item 
	 مقادیر ویژه‌ی ماتریس‌های هرمیتی، حقیقی هستند. 
	 \item 
	 مقادیر ویژه‌ی ماتریس‌های معین مثبت هرمیتی (نیمه معین مثبت هرمیتی)، مثبت (نامنفی) می‌باشند. 
	  \item 
	 قسمت حقیقی هر مقدار ویژه از ماتریس‌های معین مثبت   (نیمه معین مثبت )، مثبت (نامنفی) می‌باشد. 
	 \item 
	  مقادیر ویژه‌ی ماتریس‌های هرمیتی کج (پادمتقارن)، صفر یا موهومی محض هستند. 
	 \item 
	 اگر 
	 $\lambda \in \sigma(A)$،
	 آنگاه 
	  $\lambda +\alpha  \in \sigma(A+
	  \alpha I)$.
	  \item 
	  فرض کنید 
	  $P$،   $S$ و  $\Sigma$
	  به ترتیب ماتریس‌های نیمه‌ی معین مثبت، هرمیتی کج و معین مثبت هرمیتی باشند. در این صورت قسمت حقیقی مقادیر ویژه‌ی ماتریس‌های 
	    $P+\Sigma$    و $S+\Sigma$
	    مثبت است و در نتیجه این دو ماتریس نامنفردند. 	  
	   \item 
	  به ازای هر 
	  $A,B\in \mathbb{C}^{n\times n}$،
	  داریم
	  $\sigma(AB)=\sigma(BA)$.
	  \item
	   اگر 
	  $x \neq 0$
	  یک بردار ویژه‌ی   ماتریس 
	  $A$
	  باشد، آنگاه هر مضربی از $x$ نیز یک بردار ویژه‌ی ماتریس 
	  $A$
	  است. در نتیجه با تقسیم این بردار بر مقدار نرم خود،   بردار ویژه‌ای از   $A$ به دست می‌آید که اندازه نرم آن برابر 1 است. 
	\end{enumerate}
 
\end{remark}

 
\begin{definition} \textbf{(نرم طبیعی)}
	فرض کنید
	$ \|{\cdot}\|_* $
	یک نرم برداری روی
	$ \mathbb{C}^{ n}$
	باشد  و 
	$.A\in {\mathbb{C}^{m\times n}}$
	در این صورت، نرم طبیعی متناظر به این نرم برداری به صورت زیر تعریف می‌شود
	$$\|{A}\|_*=\max_{\|{x}\|_*\neq 0} \frac{\|{Ax}\|_*}{\|{x}\|_*}=\max_{\|{x}\|_*=1}\|{Ax}\|_*.$$
\end{definition}
\begin{remark}
روابط زیر برای هر  
\gls{normn}
$\|{\cdot}\|_*$
 و  نرم برداری  وابسته‌ی به آن  برقرار است. 
	\begin{enumerate}[1)]
	\item 
	برای هر ماتریس 
	$A\in \mathbb{C}^{n\times n}$
	و بردار
	$x\in \mathbb{C}^{n}$،
 داریم
	\begin{align*}
	\|{Ax}\|_* \leq \|{A}\|_* \|{x}\|_*.
	\end{align*}
		\item
	فرض کنید 
	$\lambda$
	یک مقدار ویژه‌ی ماتریس 
	$A$
	باشد. در این صورت  
	$|\lambda| \le\|{A}\|_*$
	و در نتیجه خواهیم داشت  	
	$\rho(A) \le \|{A}\|_*$.
\end{enumerate}
\end{remark}

 


به ازای هر
 $x \in \mathbb{C}^{n} $
  نرم طیفی    (اقلیدسی)   بردار 
  $x=[x_1, x_2, \ldots, x_n]^T$
  را که با 
  $\norm{x}$
  نشان می‌دهیم، به صورت 
  $$\norm{x}=\sqrt{x_1^2+x_2^2+ \cdots+x_n^2},$$
  تعریف می‌شود. متناظر با این نرم، به ازای هر 
  $A \in \mathbb{C}^{n \times n} $،
  نرم طیفی    (اقلیدسی) ماتریس $A$
  را   با 
  $\norm{A}$
  نشان داده که  به صورت
  $$\norm{A}=\max_{\norm{x}\neq 0} \frac{\norm{Ax}}{\norm{x}}=\max_{\norm{x}=1}\norm{Ax},$$
تعریف می‌شود. 

\begin{theorem}\,
	\begin{enumerate}[1)]
		روابط زیر برای نرم طیفی برقرار است.
	\item
	برای  هر 
	$A,B\in \mathbb{C}^{n\times n}$
	و
	$x\in \mathbb{C}^{n}$
	داریم:
	\begin{align*}
	\norm{Ax} \leq \norm{A} \norm{x},~~~\norm{AB}\leq \norm{A} \norm{B}.
	\end{align*} 
	\item
	برای هر ماتریس $A$ داریم:
	\begin{align*}
	\rho(A) \le \norm{A} , ~~~  ~~~ \norm{A}=\sqrt{\rho(A^*A)}=\sigma_{\max}(A),
	\end{align*}
	که در آن $\sigma_{\max}(A)$  بزرگ‌ترین   مقدار تکین ماتریس 
	$A$
	است.
	\item 
	اگر 
	$U$
	یک ماتریس یکانی باشد، آنگاه 
	$\norm{U}=1$.	
	\item 
	برای هر ماتریس
	$A $
	و 	یکانی 
	$U$
	داریم 
	$\norm{AU}=\norm{UA}=\norm{A}$.
	\item
	اگر ماتریس 
	$S\in \mathbb{C}^{n \times n}$
	هرمیتی کج و 
	$\alpha>0$
	 باشد، آنگاه ماتریس 
	$
	( \alpha   I -{  S}  )(\alpha   I +  S  )^{-1}$
	یکانی است و در نتیجه 
	$$\norm{( \alpha   I -{  S}  )(\alpha   I +  S  )^{-1}}=1.$$
	\item اگر 
	$A$
	نرمال باشد، آنگاه 
	$\norm{A}=\rho(A)$.
	\item
	اگر 
	$A$
	هرمیتی باشد، آنگاه 
	$\norm{A}=\max \{ |\lambda_{\max}(A)|, |\lambda_{\min}(A)| \}$،
	که در آن 
	$\lambda_{\min}(A)$
	و
	$\lambda_{\max}(A)$
	به ترتیب کوچک‌ترین و  بزرگ‌ترین   مقدار ویژه‌ی ماتریس 
	$A$
	می‌باشند.
	\item
	
	اگر 
	$A$
	معین مثبت هرمیتی باشد، آنگاه 
	$\norm{A}= \lambda_{\max}(A)$،
	که در آن 
	$\lambda_{\max}(A)$
   بزرگ‌ترین   مقدار ویژه‌ی ماتریس 
	$A$
	است.
\end{enumerate}
\end{theorem}
 
 \begin{proof}
 	به 
 	\cite{drkhojasteh1,horn1990}
 	مراجعه شود.
 \end{proof}
  
  \begin{theorem}(قضیه‌ی ریلی-ریتز)
  	فرض کنید  	$\lambda_n \leq \lambda_{n-1}\leq \cdots \leq \lambda_{2} \leq \lambda_1$
مقادیر ویژه   ماتریس هرمیتی
  	$A\in \mathbb{C}^{n \times n}$
  	باشند. آنگاه برای هر 
  	$x\in \mathbb{C}^n$ 
  	داریم
  	$	\lambda_n  \leq \frac{x^*Ax}{x^*x} \leq \lambda_1$
  	و
  	\begin{align*}
  	\lambda_n  = \min_{x\neq 0} \frac{x^*Ax}{x^*x} =\min_{\norm{x}=1}  {x^*Ax},~~~~\lambda_1  = \max_{x\neq 0} \frac{x^*Ax}{x^*x} =\max_{\norm{x}=1}  {x^*Ax}.
  	\end{align*}
  \end{theorem}
 \begin{proof}
 	به 
 	\cite{horn1990}
 	مراجعه شود.
 \end{proof}
  
   

 

 

 
%\begin{remark}	
%	زیرا 
%	\begin{align*}
%	&\left( ( \alpha \mathbf I -{\mathbf S}  )(\alpha \mathbf I +\mathbf S  )^{-1} \right)^*\left( ( \alpha \mathbf I -{\mathbf S}  )(\alpha \mathbf I +\mathbf S  )^{-1} \right)\\
%	&\quad\quad=
%	(\alpha \mathbf I +\mathbf S^*  )^{-1}  ( \alpha \mathbf I -{\mathbf S} ^* )  ( \alpha \mathbf I -{\mathbf S}  )(\alpha \mathbf I +\mathbf S  )^{-1}\\&\quad\quad=
%	(\alpha \mathbf I -\mathbf S  )^{-1}( \alpha \mathbf I -{\mathbf S}  )  ( \alpha \mathbf I +{\mathbf S}  )  (\alpha \mathbf I +\mathbf S  )^{-1}=\mathbf I
%	\end{align*}
%\end{remark}
%
%\begin{definition}
%	فرض کنید 
%	$ R $
%	و
%	$ S $
%	دو زیرفضای برداری از فضای برداری 
%	$ V $ 
%	باشند. می‌گوییم $T$ جمع مستقیم زیرفضاهای $ S $ 
%	و
%	$R$
%	است هرگاه 
%	${R}\cap{S}=\{0\}$
%	و 
%	$.R+S=T$
%	در این صورت، می‌نویسیم 
%	$.T={R}\oplus{S}$
%\end{definition}

 
  





 
 
 
\begin{definition}
	فرض کنید $V$ یک فضای برداری روی میدان 
	$\mathbb{F}$
	باشد.
	یک ضرب داخلی روی
	$ V $،
	تابعی است که به هر زوج از بردارهای 
	$ x $
	و
	$y$
	در
	$ V $
	یک اسکالر مثل 
	$(x,y)$
	در
	$ \mathbb{F} $
	را نسبت می‌دهد	به ‌طوری که در شرایط زیر صدق کند:
	\begin{enumerate}[1)]
		\item
	$(x,x)$ 
	حقیقی باشد و
	$(x,x) \ge 0$.
	 به‌علاوه 
	$(x,x)=0$
	اگر و تنها اگر
	$x=0$؛
	\item
	  برای هر
	$ \alpha \in \mathbb{F}$،
	$(x,\alpha y) = \alpha (x,y)$؛
	\item
  برای هر
	$(x, y+z) = (x,y)+ (x,z)$؛
	 \item
	$.(x,y)=   \overline{(y,x)}  $
		\end{enumerate}
	\noindent
	هر فضای برداری که یک ضرب داخلی روی آن تعریف شده باشد را یک فضای ضرب داخلی می‌نامند.
	
	
	فرض کنید 
	$V$
	یک فضای ضرب داخلی روی میدان 
	$\mathbb{F}$
	و
	$(\cdot,\cdot)$
	یک ضرب داخلی روی 
	$V$
	باشد. در این صورت، اگر به ازای هر
	$x \in V$،
	قرار دهیم
	$$\norm{x}= \sqrt{(x,x)},$$
	آنگاه 
	$\|{\cdot}\|$
	یک نرم روی 
	$V$
	تعریف می‌کند. 
\end{definition}
\begin{definition}
	دو بردار 
	$x$
	و
	$y$
	در یک فضای ضرب داخلی
	$V$
	با ضرب داخلی 
	$(\cdot,\cdot)$
	بر هم عمودند، هرگاه
	$	(x,y)=0$. این تعامد را با 
	$x \perp y‌$
	نشان می‌دهند.
	
\end{definition}
 
\begin{definition}
	مجموعه‌ی بردارهای 
	$B = \{u_{1},u_{2},\ldots,u_{n} \}$
	را یک مجموعه‌ی یکامتعامد\LTRfootnote{Orthonormal}
	می‌نامند، هرگاه به ازای هر 
	$i$،
	$	\norm{u_{i}}=1 $
	و به ازای هر
	$i$
	و
	$j$
	با شرط
	$i \neq j$، داشته باشیم 
	$.u_{i} \perp u_{j}$
	به عبارت دیگر
	\begin{align*}
	(u_{i} , u_{j}) = \left\{
	{\begin{array}{*{20}{c}}{1  , \qquad i=j,} \\
		{ 0,\qquad i \neq j.}
		\end{array}}
	%{\begin{array}{*{20}{c}}{ }\\{(e5 }\end{array}}
	\right.
	\end{align*}
\end{definition}
\begin{definition}
	ماتریس‌های
	$ A\in{{\mathbb{C}}^{n\times n}}$
	و
	$B\in{{\mathbb{C}}^{n\times n}}$
	را متشابه گویند، هرگاه یک ماتریس  نامنفرد مثل $ P$  وجود داشته باشد به طوری که 
	$  {P}^{-1}BP = A  $.
	اگر ماتریس 
	$P$
	یکانی باشد، می‌گوییم ماتریس 
	$A$
	با ماتریس
	$B$
	به طور یکانی متشابه است. 
\end{definition}
\begin{theorem}\textbf{(شکل شور\LTRfootnote{Schur}
		یک ماتریس)}
	 به ازای هر ماتریس 
	$A\in {\mathbb{C}^{n\times n}}$ 
	یک ماتریس بالامثلثی مانند $T\in {\mathbb{C}^{n\times n}}$   و یک ماتریس  یکانی مانند 
	$U\in {\mathbb{C}^{n\times n}}$ 
	وجود دارد به طوری که
	
	\[{{U}^*}AU=T=\renewcommand{\arraystretch}{0.6} \left( \begin{matrix}
	{{\lambda }_{1}} & * & \ldots  & \ldots  & *  \\
	{} & {{\lambda }_{2}} & \ddots  & {} & \vdots   \\
	{} & {} & \ddots  & \ddots  & \vdots   \\
	{} & {} & {} & \ddots  & *  \\
	{} & {} & {} & {} & {{\lambda }_{n}}
	\end{matrix} \right),\]
	که در آن 
	${{\lambda }_{i}}$، 
	$i=1,2,3,\ldots ,n$
	مقادیر ویژه‌ی 
	$ A $
	(نه لزوماً متمایز ) می‌باشند. ماتریس 
	$T $
	را شکل شور ماتریس  $A $ می‌گویند. 
\end{theorem}
بنابراین هر ماتریس $A\in {\mathbb{C}^{n\times n}}$  به صورت یکانی با یک ماتریس بالامثلثی متشابه است. 
\begin{remark}
	با توجه به شکل شور یک ماتریس نتایج زیر را خواهیم داشت.
	\begin{enumerate}[1)]
\item 
ماتریس 
$N\in \mathbb{C}^{n \times n}$
نرمال است، اگر و تنها اگر به صورت یکانی با یک ماتریس قطری  $\Lambda \in \mathbb{C}^{n \times n}$ متشابه باشد. عناصر قطری ماتریس 
$\Lambda$
مقادیر ویژه‌ی ماتریس $N$  هستند. 
\item 
ماتریس‌های هرمیتی و   متقارن، به‌صورت یکانی با یک ماتریس قطری متشابه هستند. 
\item 
ماتریس‌های هرمیتی کج و  پادمتقارن، به‌صورت یکانی با یک ماتریس قطری متشابه هستند. 
	\end{enumerate}	
\end{remark}

\begin{theorem}\textbf{(کیلی-همیلتون )}\label{کیلی - همیلتون }
	فرض کنید $ \chi $  چند‌جمله‌ای مشخصه‌ی ماتریس
	$A\in{{\mathbb{C}}^{n\times n}}$
	باشد. در این صورت، 
	$\chi(A)=0$.
\end{theorem}
 \begin{proof}
	به 
	\cite{drkhojasteh2}
	مراجعه شود.
\end{proof}

\begin{definition}
	فرض کنید 
	$.A\in{{\mathbb{C}}^{n\times n}}$
	چند‌جمله‌ای مینیمال  
	$ A $
	یک چند‌جمله‌ای تکین مثل   
	$ q $
	با کوچک‌ترین درجه‌ ممکن است به طوری که 
	$q(A)=0$.
\end{definition}
\begin{remark}
	\begin{enumerate}[1)]
		\item 
		ریشه‌های چندجمله‌ای مشخصه‌ی ماتریس 
		$A$ 
		برابر مقادیر ویژه‌ی ماتریس 
		$A$
		هستند. 
		\item 
		چندجمله‌ای مینیمال ماتریس 
		$A$
		چندجمله‌ای مشخصه‌ی آن را عاد می‌کند و در نتیجه ریشه‌های چندجمله‌ای مینیمال   ماتریس $A$ نیز، مقادیر ویژه‌ی ماتریس $A$ هستند.   
	\end{enumerate}
\end{remark}
%
%\begin{definition}
%	ماتریس 
%	$ A\in{{\mathbb{R}}^{n\times n}}$
%	را معین مثبت متقارن می‌گوییم، هرگاه
%	
%	الف) 
%	${A}^{T}=A$
%	($A$
%	متقارن باشد)؛
%	
%	ب) برای هر
%	$0\neq x \in{{\mathbb{R}}^{n}}$،
%	$ .x^{T}Ax>0$\\
%	ماتریس $A$ را نیمه معین مثبت متقارن\LTRfootnote{Symmetric positive semidefinite}
%	می‌گویند هرگاه (الف) برقرار باشد و برای هر 
%	$x \in{{\mathbb{R}}^{n}}$،
%	$ .x^{T}Ax\ge 0$
%\end{definition}
%
%\begin{definition}
%	ماتریس 
%	$ A\in{{\mathbb{C}}^{n\times n}}$
%	را معین مثبت هرمیتی می‌گوییم، هرگاه 
%	
%	الف)
%	$ {A}^*=A $
%	($A$
%	هرمیتی باشد)؛
%	
%	ب) برای هر
%	$ 0\neq x \in{{\mathbb{C}}^{n}}$،
%	$.x^*Ax>0$\\
%	ماتریس $A$ را نیمه معین مثبت هرمیتی\LTRfootnote{Hermitian positive semidefinite}
%	می‌گویند هرگاه (الف) برقرار باشد و برای هر 
%	$x \in{{\mathbb{C}}^{n}}$،
%	$ .x^*Ax\ge 0$
%\end{definition}


\begin{theorem}\textbf{( تجزیه‌ی مقدار تکین\LTRfootnote{Singular value decomposition} )}
	فرض کنید 
	$.A\in{{\mathbb{C}}^{m\times n}}$
	در این صورت، ماتریس‌های متعامد 
	$ U \in{{\mathbb{C}}^{m\times m}} $
	و 
	$ V \in{{\mathbb{C}}^{n\times n}}$
	و ماتریس 
	\begin{align*}
	\Sigma =   \begin{bmatrix}
		D_r & 0\\
		0 & 0
		\end{bmatrix}  \in \mathbb{C}^{m\times n} ,\qquad D_r=\diag_r\{ \sigma_1,\ldots,\sigma_r\},
	\end{align*}
	وجود  دارند به طوری که 
	$ A = U\Sigma{V}^{*} $، که در آن
	$.{\sigma}_{1}\ge{\sigma}_{2} \ge \ldots \ge {\sigma}_{r} > 0  $
	${\sigma}_{i}$  
	ها
	مقادیر تکین ماتریس $A$،
	ستون‌های 
	$ U = \left({u}_{1},\ldots,{u}_{m}\right) $
	را بردارهای تکین چپ  $A$
	و ستون‌های ماتریس
	$ V = \left({v}_{1},\ldots,{v}_{n}\right) $
	را بردارهای تکین راست $A$ می‌نامند. 
\end{theorem}
\noindent
\textbf{اثبات : }
به 
\cite{drkhojasteh1}
مراجعه شود.

%
%\begin{lemma}
%	فرض کنید $M$ یک ماتریس مربعی به صورت 
%	\begin{align*}
%	M =  \left( \begin{matrix}
%	A & B\\
%	C & D
%	\end{matrix} \right) ,
%	\end{align*}
%	
%	باشد که در آن 
%	$A$ و $D$
%	ماتریس‌های مربعی هستند و 
%	${A}^{-1}$
%	موجود است. در این صورت داریم
%	\begin{align*}
%	M=  \left( \begin{matrix}
%	I & 0\\
%	C{A}^{-1} & I\\
%	\end{matrix} \right)
%	\left( \begin{matrix}
%	A & 0\\
%	0 & S\\
%	\end{matrix} \right)
%	\left( \begin{matrix}
%	I & {A}^{-1}B\\
%	0 & I\\
%	\end{matrix} \right) ,
%	\end{align*}
%	که در آن
%	$ S = D - C{A}^{-1}B$. با توجه به این رابطه روشن است که 
%	${M}^{-1}$
%	موجود است اگر و تنها اگر $S$
%	نامنفرد باشد.  با فرض نامنفرد بودن
%	$A$
%	و 
%	$S$، معکوس ماتریس بلوکی $M$ به صورت زیر خواهد بود 
%	\begin{align*}
%	{M}^{-1} =  \left( \begin{matrix}
%	I & -{A}^{-1}B\\
%	0 & I\\
%	\end{matrix} \right)
%	\left( \begin{matrix}
%	{A}^{-1} & 0\\
%	0 & {S}^{-1}\\
%	\end{matrix} \right)
%	\left( \begin{matrix}
%	I & 0\\
%	-C{A}^{-1} & I\\
%	\end{matrix} \right).
%	\end{align*}
%\end{lemma}
\begin{definition}
	حداکثر تعداد ستون‌ها یا سطرهای مستقل خطی یک ماتریس را رتبه‌ی آن ماتریس می‌گویند. رتبه‌ی ماتریس 
	 $A$  
	 را با 
	 ${\rm Rank}(A)$
	 نشان می‌دهیم. 
	ماتریس  	 	$B \in{{\mathbb{C}}^{m\times n}}$ را رتبه کامل\LTRfootnote{Full rank}
	 	 گویند، هرگاه   
$${\rm Rank}(B)=\min \{m,n\}.$$
\end{definition}
\begin{remark} برای ماتریس‌های رتبه کامل روابط زیر برقرار است.
	\begin{enumerate}[1)]
	 \item 
	 اگر
	 $B \in{{\mathbb{C}}^{m\times n}}$، 
	$ (m\leq n)$، 
	 رتبه کامل باشد، آنگاه ماتریس 
	 $BB^*$
	 وارون‌پذیر است. 
	 \item  اگر
	 $B \in{{\mathbb{C}}^{m\times n}}$، 
	 $ (m\leq n)$، 
	 رتبه کامل باشد،  آنگاه
	 $B^*x=0$
	 اگر و تنها اگر 
	 $x=0$.
	 \item 
	 هر ماتریس مربعی  رتبه کامل است اگر و تنها اگر   وارون‌پذیر  باشد.
	 \item 
	 اگر 
	 $A \in{{\mathbb{C}}^{n\times n}}$   
	 یک ماتریس وارون‌پذیر و 
	  $B \in{{\mathbb{C}}^{m\times n}}$، 
	  $ (m\leq n)$،
	 یک ماتریس رتبه کامل باشد، آنگاه ماتریس 
	 $AB^*$
	 یک ماتریس وارون‌پذیر است. 
	 \item 
	 فرض کنید 
	 $B \in{{\mathbb{C}}^{m\times n}}$، 
	 $ (m\leq n)$،
	 یک ماتریس رتبه کامل باشد. در این صورت 	 اگر 
	 $A$   
	 یک ماتریس معین مثبت باشد،   آنگاه ماتریس 
	 $BAB^*$
	 نیز یک ماتریس معین مثبت  است و اگر 
	 $A$   
	 یک ماتریس نیمه معین مثبت باشد،   آنگاه ماتریس 
	 $BAB^*$
	 نیز یک ماتریس نیمه معین مثبت  می‌باشد. 
	\end{enumerate}
	
	 
\end{remark}
%\begin{theorem}\label{ghaz:null}
%	برای هر ماتریس 
%	$A\in{{\mathbb{C}}^{n\times n}}$
%	یک عدد صحیح مثبت $k$ وجود دارد به طوری که 
%	\begin{align} \label{1}
%	{{\mathbb{C}}^{n}} ={\rm range}{\left({A}^{k} \right)} \oplus {\rm null}{\left({A}^{k}\right)}.
%	\end{align}
%	% 		به‌علاوه کوچک‌ترین $k$ که در رابطه‌ی \eqref{1} صدق می‌کند برابر با اندیس $A$ است.
%\end{theorem}
%\noindent
%\textbf{اثبات : }
%به
%\cite{drkhojasteh2}
%مراجعه شود.
%\begin{lemma}\label{lem:daraje2}
%	معادله‌ی درجه‌ی دوم 
%	$z^{2} - rz + s = 0$
%	که در آن 
%	$r$
%	و
%	$s$
%	حقیقی می‌باشند دارای دو ریشه‌ی 
%	$z_{1}$
%	و
%	$z_{2}$
%	با شرط 
%	$ \max\{|z_{1}|,|z_{2}|\}\leq 1$
%	است، اگر و تنها اگر 
%	$|s|\leq1$
%	و
%	$.|r|\leq 1+s$
%\end{lemma}
%\noindent
%\textbf{اثبات : }
%به
%\cite{drkhojasteh2}
%مراجعه شود.
%\begin{lemma}\label{had}
%	فرض کنید 
%	$A \in	{\mathbb{C}^{n\times n}}$. در این صورت گزاره‌های زیر معادلند: 
%	
%	الف) سری  
%	${\displaystyle\sum ^ \infty _ {k=0} } A^{k}$
%	همگراست (توجه کنید که
%	$A^{0} = I$
%	)؛
%	
%	ب) 
%	$\rho(A)<1$؛
%	
%	ج)
%	$\displaystyle\lim_{k \to \infty } A^{k} = 0$.\\
%	در هر کدام از حالت‌های فوق 
%	$I-A$
%	معکوس‌پذیر است و
%	$.{\displaystyle\sum ^ \infty _ {k=0} } A^{k} = (I-A)^{-1}$
%	
%\end{lemma}
%\noindent
%\textbf{اثبات : }
%به
%\cite{drkhojasteh1}
%\begin{definition}
%	دستگاه
%	$Ax=b$
%را در نظر بگیرید که در آن 
%	$A \in \mathbb{C}^{m \times n}$، %
%	$b \in \mathbb{C}^{m}$
%و
%	$x \in \mathbb{C}^{n}$
%		بردار مجهول است. می‌خواهیم برداری مثل 
%	$x^{*} \in \mathbb{C}^{n}$
%	بیابیم به طوری که 
%	$$||A{x}^{*} - b||_{2} = \min_{x \in \mathbb{C}^{n}} ||Ax-b||_{2}.$$
%این مسأله به مسأله‌‌ی کمترین توان‌های دوم\LTRfootnote{Least squares} معروف است. 
%	\end{definition}
 

\section{عدد شرطی  و پیش‌شرط‌سازی دستگاه معادلات خطی}

\quad
  مسائلی وجود دارند که نسبت به داده‌های ورودی  خود بسیار حساس می‌باشند و با کوچک‌ترین تغییری در داده‌های ورودی، تغییرات بزرگی در جواب دقیق این مسائل پدید می‌آید. به عبارتی، یک خطای نسبی کوچک در داده‌های ورودی مسأله، باعث خطای نسبی بزرگی در جواب مسأله می‌شود. این خاصیت از مسأله، به ماهیت خود مسأله ارتباط دارد و مستقل از الگوریتم به‌کارگیری برای حل آن مسأله می‌باشد. چنین مسائلی را مسائل بدحالت یا بدشرط می‌گویند. در غیر این صورت مسأله  خوش حالت یا خوش شرط نامیده می‌شود. 
به دلیل وجود خطاهای مختلف،  از هر الگوریتمی که برای حل یک مسأله‌ی بدحالت استفاده شود، تضمینی برای درستی جواب به دست آمده از آن الگوریتم وجود ندارد و ممکن است، الگوریتم جواب غیر قابل قبولی ارائه دهد. در جبر خطی عددی، عددی به هر مسأله،   به عنوان عدد حالت یا عدد شرطی  نسبت داده می‌شود که نشان دهنده‌ی خوش حالتی یا بدحالتی آن مسأله می‌باشد. این عدد، برای حل  دستگاه معادلات خطی سازگار
\begin{align}\label{sysista}
Ax=b,
\end{align}
با 
$\cond(A)$
نشان داده می‌شود که  به ازای هر نرم  
$\|\cdot\|$
روی 
$\mathbb{ C}^{n\times n}$، 
اگر   ماتریس  $A$  نامنفرد باشد، به صورت  
$\cond(A)= \|A \|\| A^{-1}\|$
و اگر  ماتریس   $A$  منفرد باشد، به صورت 
$\cond(A)= \|A \|\| A^\dag \|$،
که در آن
 $A^\dag$
 وارون تعمیم یافته‌ی ماتریس 
 $A$
 می‌باشد ( 
 \cite{drkhojasteh1}
را ببینید)، تعریف می‌شود. در این رساله، از عدد حالت به دست آمده از نرم طیفی استفاده می‌کنیم.  بنابراین منظور ما از عدد حالت، مقدار 
$\cond(A)=\norm{A}\norm{A^{-1}}$
می‌باشد.  
\begin{theorem}\cite{datta2010}
	 خواص زیر برای عدد حالت برقرار است.
	\begin{enumerate}[1)]
		\item 
		عدد حالت هر ماتریس برای هر  نرم 
		$\|\cdot\|$
		 در 
		$\mathbb{ C}^{n\times n}$،
		 که دارای خاصیت
		$\|AB\|\leq \|A\|   \| B\|$
		باشد، بزرگتر یا مساوی 1 است .
		\item 
		برای  هر ماتریس یکانی 
		$A$، 
		$\cond(A)=1$.
	\item 
	$\cond(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}$
	که در آن $\sigma_{\min}(A) $
	و
	$\sigma_{\max}(A) $
	به ترتیب کوچک‌ترین و بزرگ‌ترین مقادیر تکین    ماتریس نامنفرد  
	$A$
	هستند.
	\item 
	برای ماتریس نامنفرد $A$،
	$\cond (A)  \geq \frac{\rho(A)}{|\lambda_{n}|}$،
	که  در آن 
	$| \lambda_n|=\min\{|\lambda_i|~:~\lambda_i \in \sigma(A)\}$.	
		\item
		$\cond(AB)\leq \cond(A)\cond(B)$.
		\item 
			$\cond(A^T)=\cond(A),~~
		\cond (AA^T)=\cond(A)^2, ~~ 
			\cond(\alpha A)=\cond(A)$ .
	\end{enumerate}
\end{theorem}

فرض کنید توسط یک الگوریتم،  جوابی مانند 
$\hat{x}$
برای دستگاه معادلات خطی   
\eqref{sysista}
  محاسبه شده باشد. 
برای تعیین دقت این جواب، می‌توان خطای نسبی جواب به دست آمده را محاسبه نمود. اما از آنجا که معمولا جواب  دستگاه در دست نمی‌باشد، می‌توان از مقدار  بردار مانده، که به صورت  
$r=b-Ax$ 
می‌باشد، 
و محاسبه‌ی خطای نسبی  
$\delta={\|r\|}/{\|b\|}$،
برای تعیین دقت جواب استفاده کرد.  اما در عمل، ممکن است   مقدار مانده برای بردار 
$\hat{x}$
 کوچک باشد، اما  
 $\hat{x}$ 
  با جواب اصلی مسأله اختلاف زیادی داشته باشد. به عنوان مثال، دستگاه معادلات خطی
   \eqref{sysista}
را با
\begin{align}
A=\begin{bmatrix}
1.0001&1\\
1&1
\end{bmatrix},~~~~
\begin{bmatrix}
2.0001\\2
\end{bmatrix},
\end{align}
در نظر بگیرید. می‌توان دید که بردار  
$x=[0;2]$،
تقریب خوبی برای جواب این دستگاه می‌باشد، زیرا  
$r=b-A\hat{x}=[0.0001;0]$
 مقدار کوچکی است. 
اما این جواب با جواب دقیق مسأله،  یعنی بردار 
$x=[1;1]$،
اختلاف زیادی دارد. از این رو    کوچک بودن نسبت نرم مانده، نمی‌تواند معیار خوبی برای دقت جواب به دست آمده باشد. 
میزان دقت جواب به دست آمده، توسط قضیه‌ی مانده مشخص می‌شود.
\begin{theorem}\cite{datta2010}(قضیه‌ی مانده)
	فرض کنید 
	$x$
	جواب اصلی دستگاه \eqref{sysista}  و 
	$\hat{x}$
	تقریبی برای این مقدار باشد. در این صورت 
	\begin{align}
	\label{threl}
	\frac{\norm{x-\hat{x}}}{\norm{x}} \leq \cond(A) \frac{\norm{b-A\hat{x}}}{\norm{b}}.
	\end{align}
\end{theorem} 
از این رو  در تعیین میزان  دقت جواب، نه تنها نسبت نرم مانده، بلکه  عدد شرطی ماتریس  ضرایب دستگاه  نیز   تاثیرگذار است. 
بنابراین، اگر عدد شرطی   ماتریس ضرایب دستگاه بزرگ باشد، آنگاه مقدار مانده‌ی بردار
 $\hat{x}$،
 هر اندازه   هم که کوچک باشد، اختلاف  جواب به دست آمده  با جواب اصلی می‌تواند  بسیار زیاد باشد.  
 با توجه به رابطه 
 \eqref{threl},
 دقت جواب به دست آمده زمانی می‌تواند بدتر باشد که علاوه بر عدد  شرطی، نسبت 
 ${\norm{x}}/{\norm{b}}$  
هم عدد  بزرگی باشد. بعنوان مثال، اگر     
 $\norm{r}=\norm{b-A \hat x}<10^{-8}$، 
 $\cond(A)=10^{9}$
 و
  ${\norm{x}}/{\norm{b}}=10^4$،
 آنگاه 
 $\norm{x-\hat{x}}<10^5$ 
 که  عدد بسیار بزرگی است. بنابراین، اگر دقت جواب به دست آمده از یک روش تکراری مهم باشد،   باید به عدد شرطی و نسبت
  ${\norm{x}}/{\norm{b}}$
   توجه داشت  و برای دست یافتن به دقت مطلوب،  شرط توقف   را متناسب با کرانی برای این مقادیر در نظر گرفت. 
   
البته برای افزایش دقت جواب، می‌توان دستگاهی را معادل دستگاه \eqref{sysista} حل نمود که دارای عدد شرطی کوچکتری نسبت به دستگاه اصلی باشد. از آنجا که 
 \begin{align}
 \cond(A)=\norm{A}\norm{A^{-1}}=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)},
 \end{align}
 که در آن 
  $\sigma_{\min}(A) $
  و
  $\sigma_{\max}(A) $
  به ترتیب کوچک‌ترین و  بزرگ‌ترین   مقدار تکین    ماتریس نامنفرد  
  $A$
  هستند،  این امر می‌تواند  با تغییر دادن مقادیر تکین ماتریس ضرایب، و بخصوص، افزایش کوچک‌ترین مقدار آن، 
   تحقق یابد. 
   
   بدین منظور،
   می‌توان با ضرب وارون یک ماتریس وارون‌پذیر  مانند  
   $P$
   در ماتریس 
   $A$
   آن را خوش حالت کرد و یکی از دستگاه‌های   معادل با دستگاه 
   \eqref{sysista}
    به صورت 
   \begin{align}\label{sys1}
   P^{-1}Ax=c,~~c=P^{-1}b,\\
   AP^{-1}y=b,~~~~y=Px,\label{sys2}
   \end{align}
   را حل نمود. هر یک از دو دستگاه بالا را دستگاه پیش‌شرط‌‌سازی شده می‌گویند. به ماتریس 
   $P$
   در دستگاه    
   \eqref{sys1}،  
    پیش‌شرط‌ساز  چپ و در دستگاه    
    \eqref{sys2}،
       پیش‌شرط‌ساز راست گویند و در هر دو آن را پیش‌شرط‌ساز  می‌نامند.
   دستگاه \eqref{sys1} را دستگاه پیش‌شرط‌سازی شده از چپ   و   دستگاه 
   \eqref{sys2}
    را دستگاه پیش‌شرط‌سازی  شده از سمت راست می‌نامند و   هر یک از این دو دستگاه را دستگاه پیش‌شرط‌سازی شده می‌گویند.
   
   البته دقت کنید اگر ماتریس ضرایب دستگاه 
   \eqref{sysista}
  نیمه معین مثبت باشد، آنگاه به جای  حل این دستگاه می‌توان دستگاه 
   \begin{align}
   \label{ssista}
   (A+\alpha I)x=b,~~~\alpha\approx 0, 
   \end{align}
   را حل نمود.
   که دارای عدد حالت بهتری نسبت به دستگاه  \eqref{sysista} می‌باشد.  زیرا 
در این حالت 
  \begin{align*}
  \sigma_{\min}^2(A+\alpha I)&=\lambda_{\min}\left((A+\alpha I)^*(A+\alpha I)\right)\\
  &=\lambda_{\min}(A^*A+\alpha(A+A^*)+\alpha^2 I)\\
  &\geq \lambda_{\min}(A^*A)+\alpha \lambda_{\min}(A^*+A)+\alpha^2\\
  &= \sigma_{\min}^2(A)+\alpha  \lambda_{\min}(A^*+A)+\alpha^2.
  \end{align*}
 چون ماتریس 
 $A$ 
  معین مثبت است، پس 
  $\lambda_{\min}(A^*+A)>0$
 که  نتیجه می‌دهد
 $ \sigma_{\min}^2(A+\alpha I)>\sigma^2_{\min}(A)$.
  لذا کوچکترین مقدار تکین دستگاه، افزایش می‌یابد.    
%   $\cond(A+\alpha I) < \cond(A)$ 
%  و در نتیجه 
% عدد حالت بهبود می‌یابد. اما باید توجه داشت که در این حالت باید مقدار 
%     کوچکی  برای  پارامتر    $\alpha$      
%      انتخاب شود تا جواب دو دستگاه به هم نزدیک باشند. 
  با استفاده از  قضیه‌ی تاثیر اختلال در چپ،  می‌توان تاثیر پارامتر 
  $\alpha$
  را   بر روی  دقت جواب به دست آمده  مشاهده نمود.
  \begin{theorem}  \cite[قضیه 4.23]{datta2010} (قضیه‌ی تاثیر اختلال در چپ)
  	فرض کنید
  	$A$  نامنفرد و 
  	$b \neq 0$.
  	اگر 
  	$\Delta A$ 
  	و 	$\delta(x)$،
  	به ترتیب میزان اختلال‌های 
  	$A$
  	و
  	$x$
  	در دستگاه معادلات خطی  
  	\eqref{sysista}
  	 و 
  	 $\norm{\Delta A} \leq \frac{1}{\norm{A^{-1}}}$.
  	 آنگاه 
  	 \begin{align*}
  	 \frac{\norm{ \delta(x)}}{\norm{x}} \leq  \frac{\cond(A)\frac{\norm{\Delta A}}{\norm{A}} }{1-\cond(A)\frac{\norm{\Delta A}}{\norm{A}}}.
  	 \end{align*}
  \end{theorem}
   بنابراین  در این روش داریم 
   \begin{align*}
 \frac{\norm{x- \hat x}}{\norm{x}} &\leq \frac{\cond(A)\frac{\alpha}{\norm{A}} }{1-\cond(A)\frac{\alpha}{\norm{A}}} 
=\frac{\norm{A^{-1} }\alpha} {1-\norm{A^{-1} }\alpha},
   \end{align*}
   که نتیجه می‌دهد اگر 
   $\norm{A^{-1}}\alpha $
   	عدد کوچکی باشد، آنگاه جواب به دست آمده از دستگاه 
   	\eqref{ssista}،
   	 به جواب دستگاه  
   	\eqref{sysista}،
   	 نزدیک خواهد بود. 
   

   
   
   \section{روش‌های تکراری ایستا}
   در این بخش شکل کلی یک روش تکراری ایستا  را برای حل یک دستگاه معادلات خطی معرفی می‌کنیم.  
    
   یک   شکافت\LTRfootnote{Splitting} 
    برای  ماتریس $A$   به صورت  $ A = M- N$ در نظر می‌گیریم  که در آن 
   $M$ نامنفرد است.
   ابتدا دستگاه  \eqref{sysista} را به صورت  
   $$ (M-N )x = b,$$
  و  سپس به صورت
   $$ x = {M}^{-1}Nx + {M}^{-1}b,$$
   می‌نویسیم. قرار می‌دهیم
   $ G = {M}^{-1}N$
   و
   $f = {M}^{-1}b$.
   در این صورت، با استفاده از رابطه‌ی  اخیر، دنباله‌ی  تکراری  
   \begin{align}
   \label{itG}
   {x}^{(k+1)} = G{{x}^{(k)}} + f,
   \end{align}
   را تولید می‌کنیم که در آن 
   $x^{(0)}$
   یک حدس اولیه‌ی دلخواه است. 
   در رابطه‌ی فوق  $G$ را ماتریس تکرار روش و این روش را روش تکراری وابسته به شکافت 
   $A=M-N$
    می‌گویند. 
    
    توجه داشته باشید،  اگر ماتریس 
    $A$ 
    نامنفرد باشد، آنگاه جواب دستگاه 
    \eqref{sysista}
     یکتاست. ولی اگر این ماتریس منفرد باشد، این دستگاه بینهایت جواب دارد.  
   اگر ماتریس   
   $A$
   نامنفرد باشد، دنباله‌ی تکراری تولید شده توسط رابطه‌ی 
   \eqref{itG}
   را همگرا گوییم،  اگر به ازای یک بردار اولیه‌ی 
   $x^{(0)}$
   به تنها جواب دستگاه معادلات خطی  \eqref{sysista}  همگرا شود.
   اگر ماتریس 
   $A$
   منفرد باشد، آنگاه دنباله‌ی تکراری  تولید شده  را نیمه همگرا گوییم، هرگاه  این دنباله به ازای یک بردار 
   $x^{(0)}$،
   به یکی از جواب های دستگاه \eqref{sysista} همگرا گردد.  
   
   قضایای زیر شرط لازم و کافی برای همگرایی یا  نیمه همگرایی یک روش ایستا را بیان می‌کند.
   \begin{theorem}
   	فرض کنید $ A= M- N$
   	یک شکافت از $A$ باشد،
   	$ G = {M}^{-1}N$
   	و
   	$ f = {M}^{-1}b$. در این‌صورت 
   	\begin{enumerate}[1)]  
   		\item 
   		روند تکراری
   		${x}^{(k+1)} = G{{x}^{(k)}} + f$
   		به ازای هر حدس اولیه‌ی
   		${x}^{(0)}$
   		به جواب دستگاه $ Ax=b$ همگراست اگر و تنها اگر 	  شعاع طیفی  ماتریس تکرار کمتر از یک باشد، یعنی
   		$\rho(G)<1$.
   		\item 
   		روند تکراری
   		${x}^{(k+1)} = G{{x}^{(k)}} + f$
   		به ازای هر حدس اولیه‌ی
   		${x}^{(0)}$
   		به یک جواب دستگاه $ Ax=b$ نیمه همگراست، اگر و تنها اگر 
   		\begin{enumerate}
   			\item 
   			شعاع طیفی ویژه‌ی ماتریس تکرار کمتر از یک باشد،  یعنی
   			$\nu(G)<1$. 
   			\item 
   			
   			${\rm Rank}(I-G)^2={\rm Rank}(I-G)$
   			 که معادل است با 
   		$	\nul((M^{-1}A)^2)=\nul(M^{-1}A)$.
   		\end{enumerate}
   		
   	\end{enumerate}
   	
   	
   \end{theorem}
   \begin{proof}
   	به
   	\cite{drkhojasteh1}
   	مراجعه شود. 
   \end{proof}

با ‌توجه به قضیه‌ی قبل  می‌بینیم که روند تکراری 
\eqref{itG}
همگراست اگر و تنها اگر
$$\rho(M^{-1}N )  <1.$$
همچنین، روند تکراری 
\eqref{itG}
همگراست اگر و تنها اگر  مقادیر ویژه‌ی 
$M^{-1}A$
درون دایره‌ای به مرکز
$(1,0)$
و به شعاع 1 قرار داشته باشند، یا به اصطلاح مقادیر ویژه در درون  این دایره حول نقطه‌ی 
$(1,0)$
خوشه شده باشند. علاوه بر این، هرچه مقادیر ویژه‌ی ماتریس 
$M^{-1}A$
حول نقطه‌ی 
$(1,0)$
بهتر خوشه شده باشند، آنگاه همگرایی سریع‌تر خواهد بود. این امر نشان می‌دهد که ماتریس پیش‌شرط‌ساز 
$M$
باید طوری انتخاب شود که مقادیر ویژه‌ی 
$M^{-1}A$
حول نقطه
$(1,0)$
خوشه شوند. در بهترین حالت اگر
$M=A$
اختیار شود، آنگاه خواهیم داشت 
$M^{-1}A= I$
و تمام مقادیر ویژه‌ی 
$M^{-1}A$
برابر با 1 خواهند بود و 
$$ G=M^{-1}N = I- M^{-1}A = 0.$$
این رابطه نشان می‌دهد که تمام مقادیر ویژه‌ی ماتریس تکرار برابر  با صفر خواهد بود و روش، سریع‌ترین همگرایی ممکن را خواهد داشت.  اما در عمل برای ماتریس‌های بزرگ، محاسبه‌ی 
$A^{-1}$
مقرون به صرفه نیست. بنابراین ماتریس 
$M$
یک تقریب از 
$A$
در ‌نظر گرفته می‌شود.


\section{  معرفی  روش‌های  مبتنی بر \gls*{krysub}  }
 
در این فصل ضمن معرفی  روش تکراری  مانده مینیمال تعمیم یافته، روش تکراری گرادیان مزدوج را  نیز معرفی می‌کنیم. 

%از مهمترین روش‌های تکراری موجود برای حل دستگاه‌های خطی بزرگ و تُنُک، روش‌های مبتنی بر فرایندهای تصویری بر زیرفضاهای کرایلف هستند. 
%	در ادامه می‌خواهیم ببینیم چگونه می‌توان یک پایه‌ی یکامتعامد برای زیرفضای 
%$ {{\mathcal{K}}_{m}}(A,r_{0})$
%یافت، برای این کار از الگوریتم گرام-اشمیت\cite{drkhojasteh1}
%استفاده می‌کنیم.

\subsection{الگوریتم مانده‌ی مینیمال تعمیم‌یافته \lr{(\gls*{gmres})}   }  
روش
 \gls{gmres}
ازجمله روش‌های تکراری غیرایستا و از جمله روش‌های مبتنی بر زیرفضای کرایلف برای حل  دستگاه معادلات خطی 
\begin{align} \label{2}
Ax=b,    
\end{align}
می‌باشد که در سال 1986 توسط  سعد و شولتز در
\cite{saad71986}
معرفی شد. این روش برای دستگاهی که ماتریس ضرایب آن یک ماتریس دلخواه باشد قابل استفاده است. دستگاه معادلات خطی 
\eqref{2}
را در نظر بگیرید که در آن ماتریس
$ A\in{{\mathbb{R}}^{n\times n}}$
نامنفرد است
و
$b,x \in {{\mathbb{R}}^{n}}$.
فرض کنید $p~$ چند‌جمله‌ای مشخصه‌ی  ماتریس $A~$ باشد. بنا به قضیه‌ی  کیلی-همیلتون  \ref{کیلی - همیلتون }،  داریم
$.p(A) = 0$
بنابراین اگر 
$$p(x) ={{x}^{n}} + {{a}_{n-1}}{{x}^{n-1}}+\cdots +{{a}_{1}}{x}+{{a}_{0}},$$
آنگاه 
$$ {{A}^{n}} + {{a}_{n-1}}{{A}^{n-1}}+\cdots +{{a}_{1}}{A}+{{a}_{0}}I = 0.$$
از اینکه $A~$ نامنفرد است، داریم 
$.(-1)^{n}{a}_{0}=\det(A) \neq 0~~$
لذا
\begin{align}
{{A}^{-1}} = -\frac{1}{{a}_{0}}\left( {{A}^{n-1}}+{{a}_{n-1}}{{A}^{n-2}} + \cdots + {{a}_{1}}I \right)= {q}_{n-1}(A),
\end{align}
که در آن 
$${{q}_{n-1}}(x) = -\frac{1}{{a}_{0}}\left( {{x}^{n-1}}+{{a}_{n-1}}{{x}^{n-2}} + \cdots + {{a}_{1}} \right).$$
از این‌ رو، اگر 
$x^{\ast}~$ 
جواب واقعی دستگاه \eqref{2} باشد، آنگاه
\begin{align}\label{3}
{x}^{\ast} = {{q}_{n-1}}(A)b \in span\{b,Ab, \ldots,{{A}^{n-1}}b\}.
\end{align}
\begin{definition}
	به ازای هر 
	$ m \in {\mathbb{N}} ~$،
	 \gls{krysub}
	$m$-بعدی 
	تولید شده توسط ماتریس
	$A \in {\mathbb{R}}^{n \times n}$
	و بردار 
	$ \upsilon \in {{\mathbb{R}}^{n}} $،
	به صورت 
	$$ {{\mathcal{K}}_{m}}(A,\upsilon) = span\{\upsilon,A\upsilon,\ldots,{{A}^{m-1}}\upsilon \},$$
	تعریف می‌شود.  
\end{definition}
حال با توجه به رابطه‌ی   \eqref{3}، می‌بینیم که
$ .{x}^{\ast} \in {{\mathcal{K}}_{n}}(A,b)$
بنابراین برای محاسبه‌ی  
${x}^{\ast}$
می‌توان این بردار را در 
${{\mathcal{K}}_{n}}(A,b)$
جستجو کرد. فرض کنید 
${x}_{0}~$
یک حدس اولیه برای جواب دستگاه  \eqref{2}  باشد. در این صورت، داریم
$$ Ax-A{{x}_{0}} = b-A{{x}_{0}}.$$
با فرض 
${{r}_{0}} =  b-A{{x}_{0}}~$
و 
$x- {{x}_{0}} = \delta~$، دستگاه  \eqref{2} معادل با 
\begin{align}\label{4}
A\delta = r_{0},
\end{align}
خواهد بود. لذا، اگر $\delta~$ از معادله  \eqref{4} محاسبه شود، آنگاه جواب واقعی دستگاه \eqref{2} به صورت 
$x = x_{0}+ \delta~~$
خواهد بود. همان طور که دیدیم 
$ .\delta \in {{\mathcal{K}}_{n}}(A,{r}_{0})~$
اما به ازای مقادیر بزرگ  $n~$ این جستجو بسیار پرهزینه است. بنابراین سعی می‌کنیم یک جواب تقریبی برای دستگاه محاسبه کنیم. برای این کار، یک $m~$ کوچک (معمولاً کمتر یا مساوی  50) انتخاب شده و یک جواب تقریبی مثل 
${\delta}_{m}~$
در 
$ {{\mathcal{K}}_{m}}(A,{r}_{0})~$
جستجو می‌گردد. این یعنی، به دنبال یک جواب تقریبی به صورت 
\begin{align}
{x}_{m} = {{x}_{0} + {\delta}_{m}} \in {{x}_{0} + {{\mathcal{K}}_{m}}(A,{r}_{0})},
\end{align}
هستیم. بنابراین چنین برداری را  در الگوریتم 
{\GMRES}
جستجو می‌کنیم به طوری که
\begin{align} \label{10}
 \norm{b - A{x}_{m}} = \min_{ x = {{x}_{0} +\delta} ~\in~ { {x}_{0} + \mathcal{K}_{m} ( A, r_0) }}     \norm{b - Ax}.
\end{align}
برای محاسبه‌ی  بردار 
${ {\delta}_{m}} \in { {\mathcal{K}_{m}}( A, {r}_{0}) }$
ابتدا بعضی از خواص فضای کرایلف 
${\mathcal{K}_{m}}( A, {r}_{0})$
را مطالعه می‌کنیم. فرض کنید 
$ . { w} \in { {\mathcal{K}_{m}}( A, {r}_{0}) }$
در این صورت، اعدادی مثل 
${{\alpha}_{i}} \in {\mathbb{R}}$،
$ i = 0, 1, \ldots , m $
وجود دارند به طوری که 
$$ w = {{\alpha}_{0}}{r}_{0} + {{\alpha}_{1}}A{r}_{0} + \cdots + {{\alpha}_{m-1}}{{A}^{m-1}}{r}_{0} = {{q}_{m-1}}(A){{r}_{0}} ,$$
که در آن 
$${{q}_{m-1}}(x) = {{\alpha}_{0}} + {{\alpha}_{1}}x+\cdots+  {{\alpha}_{m-1}}{{x}^{m-1}} . $$
از این رو، 
$ {w} \in { {\mathcal{K}_{m}}( A, {r}_{0}) }$
اگر و تنها اگر یک چندجمله‌ای، حداکثر از درجه‌ 
$m-1~$
مثل 
$ {q}_{m-1}~$
موجود باشد به طوری که 
$. w= { {q}_{m-1}}(A){r}_{0} $
\begin{lemma}
	اگر به ازای یک 
	$ j \ge 1~$
	داشته باشیم 
	$ {{A}^{j}}{{r}_{0}} \in {{\mathcal{K}}_{j}}(A,{r}_{0})~ $، آنگاه به ازای هر 
	$ k \ge j~ $
	خواهیم داشت
	$ .{{A}^{k}}{{r}_{0}} \in {{\mathcal{K}}_{j}}(A,{r}_{0})~ $ 
\end{lemma}
 \begin{proof}
 	به
 	\cite{drkhojasteh2}
 	مراجعه شود.
 \end{proof}
\begin{definition}
 فرض کنید
	$ A\in{{\mathbb{R}}^{n\times n}}$
	و 
	$. \upsilon \in {{\mathbb{R}}^{n}}$
	چندجمله‌ای مینیمال بردار $\upsilon~$ نسبت به $A~$ یک چندجمله‌ای تکین $p~$ با کوچک‌ترین درجه است به طوری که
	$ .p(A)\upsilon = 0~~$
	درجه‌ی چندجمله‌ای مینیمال بردار  $\upsilon~$
	نسبت به ماتریس $A~$،
	درجه بردار $\upsilon~$
	نسبت به $A~$ 
	نامیده می‌شود و با 
	${grade}_{A}(\upsilon)~$
	نشان می‌دهند.
\end{definition}

اگر $p~$ چندجمله‌ای مینیمال $A~$ باشد،  آنگاه 
$ p(A) = 0~$
و از این رو، 
$ . p(A) \upsilon = 0~$
لذا، 
$${grade}_{A}(\upsilon) \le deg(p) \le n .$$
\begin{theorem}\label{70}
	بعد زیرفضای کرایلف 
	$ {{\mathcal{K}}_{m}}(A,\upsilon)~$
	برابر   $m~$ است اگر و تنها اگر درجه بردار
	$ \upsilon$، 
	یعنی  
	$  \mu ={grade}_{A}(\upsilon)$، کوچکتر از $m$ نباشد. به عبارت دیگر 
	$$ \dim ( {{\mathcal{K}}_{m}}(A,\upsilon)) = m \iff {grade}_{A}(\upsilon) \ge m .$$
	از این رو،
	$$ \dim ( {{\mathcal{K}}_{m}}(A,\upsilon)) = \min \{m,{grade}_{A}(\upsilon)\}. $$
\end{theorem}
\begin{proof}
	به
	\cite{drkhojasteh2}
	مراجعه شود.
\end{proof}
برای محاسبه‌ی 
${ {\delta}_{m}} \in { {{\mathcal{K}}_{m}}( A, {r}_{0}) }$
یک پایه‌ی یکامتعامد برای 
$ {{\mathcal{K}}_{m}}( A, {r}_{0})$
می‌یابیم. برای این کار، از الگوریتم گرام-اشمیت  \cite{drkhojasteh1}،
استفاده می‌کنیم. 
بنابراین الگوریتم آرنولدی گرام-اشمیت را به صورت الگوریتم
\ref {alg1-2}
می‌نویسیم. 
%با مقایسه‌ی الگوریتم 
%\ref{alg1-1}%
%% و الگوریتم 
% \ref{alg1-2}  می‌بینیم که برای محاسبه‌ی بردار %
% $ {\upsilon}_{j+1}~$، به جای بردار %
% ${{A}^{j}}{r}_{0}~$
% از 
%  $A{\upsilon}_{j}~$
%  استفاده شده است. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
\begin{algorithm}[!ht]
	\caption{  الگوریتم روش گرام-اشمیت آرنولدی}\label{alg1-2}
	\begin{enumerate}[1)]
		\item 
		قرار دهید 
		$ \upsilon_1 = {r}_{0}/\beta~ \text{ و}~  \beta =\norm{r_0}~$
		\item 
		برای 
		$ j=1,2 , \ldots ,m ~$،
		 روند زیر را تکرار کنید:  
		 \begin{enumerate} 
		\item
		مقادیر
		$~ .\text{محاسبه کنید} ~i = 1,2, \ldots, j ~~ \text{را به ازای} ~h_{ij} = (A\upsilon_{j} , \upsilon_{i}) $  
		\item
		مقدار
		$\text{را محاسبه کنید }~ w_j = A\upsilon_j  -\displaystyle \sum_{i=1}^j h_{ij} \upsilon_i$.  
		\item
		$ h _{j+1, j }:=\norm{w_j} $  
		\item
		اگر
		$  h  _{j+1, j}= 0~ $، 
		  توقف کنید.  
		\item
		$ \upsilon_{j+1}:=w _{j} / \norm{w_j}$.
		\end{enumerate}
	\end{enumerate}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\thispagestyle{empty}

\begin{theorem}\label{ghaz:v}
	اگر 
	${V}_{m} = ( {\upsilon}_{1}, {\upsilon}_{2},\ldots, {\upsilon}_{m} ) $
	و ماتریس بالاهسنبرگی 
	$ (m+1) \times m~$
	با درایه‌های 
	${{h }_{ij}}~$
	تعریف شده در الگوریتم  \ref{alg1-2}، را با 
	$ {\overline{H}}_{m}~$
	و ماتریس حاصل از حذف سطر آخر 
	$ {\overline{H}}_{m}~$
	را با 
	${H}_{m}~$
	نشان  دهیم، آنگاه روابط
	\begin{align*}
	A{{V}_{m}} & = {{V}_{m}}{H}_{m} + {{w}_{m}} {{e}^{T}_{m}}\\
	& =  {{V}_{m+1}} {\overline{H}}_{m},\\
	{{V}^{T}_{m}}A {{V}_{m}} & =  {{H}_{m}}, 
	\end{align*}
	بر قرارند، که در آن 
	$ .{{V}_{m+1}} =  ({{V}_{m}} , {{\upsilon}_{m+1}}) ~ $
\end{theorem}
\begin{proof}
	به
	\cite{drkhojasteh2}
	مراجعه شود.
\end{proof}

فرض کنید 
$. {{h }_{j+1, j}} = 0 ~$
در این صورت،  با توجه به 
$~ {{w }_{j}} = A{{\upsilon}_{j}}  -\displaystyle \sum_{i=1}^{j} {{h}_{ij}}{{\upsilon}_{i}} ~$
از الگوریتم 
\ref{alg1-2}
داریم  
\begin{align}
A{{\upsilon}_{j}}  - \sum_{i=1}^{j} {{h}_{ij}}{{\upsilon}_{i}} = 0 , 
\end{align}
یعنی
$$ A{{\upsilon}_{j}}  = \sum_{i=1}^{j} {{h}_{ij}}{{\upsilon}_{i}}.$$
این رابطه نشان می‌دهد که بردار 
$ A^{j}{{r}_{0}}~$
به مجموعه بردارهای 
$\{{\upsilon}_{1}, {\upsilon}_{2},\ldots, {\upsilon}_{j}\}$
وابسته است. لذا
$$x^{\ast} \in {{x}_{0} + {{\mathcal{K}}_{j}}( A, {r}_{0}) } ,$$
که این خود یک موفقیت است. توجه کنید که اگر $j$ عدد کوچکی باشد، آنگاه 
${{x}_{0} + {{\mathcal{K}}_{j}}( A, {r}_{0}) }~$
یک زیرفضای کوچکی خواهد بود و می‌توانیم جواب واقعی مسأله را در یک فضای کوچک جستجو کنیم.\par
در عمل برای محاسبه‌ی پایه‌ی یکامتعامد از الگوریتم گرام-اشمیت آرنولدی اصلاح شده استفاده می‌شود که مشابه الگوریتم  \ref{alg1-2} به صورت \ref{alg1-3} جمع بندی می‌شود.\par
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
\begin{algorithm}[!ht]
	\caption{ الگوریتم روش گرام-اشمیت آرنولدی اصلاح شده}\label{alg1-3}
	\begin{enumerate}[1)]
		\item 
		قرار دهید 
		$~{\upsilon}_{1}= {r}_{0}/\beta~~ \text{و}~~\beta = \norm{ {r}_{0} } $
		\item 
		برای 
		$ j =1,2, \ldots, m ~$، روند زیر را تکرار کنید:  
		\begin{enumerate}
			\item
		$~. \text{را محاسبه کنید }~{{w}_{j}} = A{{\upsilon}_{j}}~  $  
		\item
		برای 
		$ i =1,2, \ldots, j ~ $، روند زیر را تکرار کنید:  
			\begin{itemize}\item
		$ ~{{h }_{i j}} := ({w}_{j} ,{\upsilon}_{i} )~ $  
		\item
		$~ {w}_{j} := {w}_{j} - {h }_{i j}{\upsilon}_{i}~ $  
		\item
		$ {{h }_{j+1, j}}= 0 ~~ \text{اگر } ~~ {{h }_{j+1, j}} := \norm{{w}_{j}}$، سپس متوقف می‌شود.  
	\end{itemize}
		\item
		$ ~{{\upsilon }_{j+1 }}=  {w}_{j}/{{h }_{j+1, j}} ‌~$
	\end{enumerate}
\end{enumerate}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


فرض کنید 
$ \{{\upsilon}_{1}, {\upsilon}_{2},\ldots, {\upsilon}_{m}\}$
 پایه‌ی یکامتعامدی باشد که توسط الگوریتم \ref{alg1-3} برای 
$ { {\mathcal{K}_{m}}( A, {r}_{0}) }$
فراهم شده باشد. در این صورت، هر بردار $x~ $ در 
$ {x}_{0} +  { {\mathcal{K}_{m}}( A, {r}_{0}) } $
به صورت 
$ x =  {x}_{0} + {{V}_{m}}y ~$
خواهد بود که در آن 
$ {V}_{m} = ( {\upsilon}_{1}, {\upsilon}_{2},\ldots, {\upsilon}_{m} )$ 
و
$. y \in { {\mathbb{R}} }^{m}$
بنابراین، داریم 
\begin{align} \label{11}
\norm{  b - Ax  } = \norm{ b - A ( {x}_{0} +{{V}_{m}}y )  }  = \norm{ {r}_{0} - A {{V}_{m}}y},
\end{align}
اما با استفاده از قضیه‌ی \ref{ghaz:v} و گام اول الگوریتم
\ref{alg1-3} 
می‌بینیم که  
$$ A {{V}_{m}}=  {{V}_{m+1}}  {\overline{H}}_{m} , \qquad {r}_{0} = {\beta}{\upsilon}_{1} = {\beta} {{V}_{m+1}}{e}_{1} ,$$
که در آن 
$ . { {e}_{1} = { ( 1 , 0, \ldots , 0 ) }^{T} } \in { {\mathbb{R}}^{m+1} } ~$
با جای‌گذاری این رابطه‌ها در (\ref{11}) خواهیم داشت
$$\norm{  b - Ax } = \norm{   {{V}_{m+1}} ( {\beta}{e}_{1} - { {\overline{H}}_{m} }y ) } = \norm{ {\beta}{e}_{1} - { {\overline{H}}_{m} }y  }.$$
بنابراین الگوریتم \GMRES  برداری مثل 
${x}_{m} = {x}_{0} + {{V}_{m}}{y}_{m}~$
محاسبه می‌کند که در آن 
$$ {y}_{m} = {argmin}_{y \in { {\mathbb{R}}^{m+1} } } \norm{  {\beta}{e}_{1} - { {\overline{H}}_{m} }y }, $$
در مسأ‌له‌ی  کمترین توان دوم فوق، ماتریس 
$ { {\overline{H}}_{m} }$
یک ماتریس کوچک از بعد 
$ (m+1) \times m$
و بالا‌هسنبرگی است.
بنابراین الگوریتم 	{\GMRES} را به صورت الگوریتم
\ref{alg2-1}
جمع بندی می‌کنیم.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
\begin{algorithm}[!ht]
	\caption{ الگوریتم روش مانده مینیمال تعمیم‌یافته \rl{(\GMRES)} }\label{alg2-1}
		\begin{enumerate}[1)]
		\item 
		محاسبه کنید 
		$~{\upsilon}_{1}:= {r}_{0}/\beta ~~ \text{و} ~~ \beta :=  \norm{ {r}_{0}  }~ \text{،} {r}_{0} = b - A{x}_{0}$.
		\item 
		ماتریس 
		$ { { {\overline{H}}_{m} } = ({h}_{ij}) } \in { {\mathbb{R}}^{(m+1) \times m} } $
		را تعریف کنید.
		$. { {\overline{H}}_{m} } = 0   ~~ \text{قرار دهید}$ 
		\item 
		برای 
		$j =1,2, \ldots, m ~$،  
		\begin{enumerate} 
		\item
		$~{{w}_{j}} := A{{\upsilon}_{j}}~ $ 
		را	محاسبه کنید 
		\item
		به ازای $i= 1,2, \ldots, j~$، روند زیر را تکرار کنید:
		 	\begin{itemize}	
		\item
		$~ {{h }_{i j}} = ({w}_{j} ,{\upsilon}_{i} )~$ 
		\item
		$~ {w}_{j} := {w}_{j} - {h }_{i j}{\upsilon}_{i}~$
		\item
		محاسبه کنید
		$~~.\text{و به گام 4 بروید}~ m := j ~\text{قرار دهید }~\text{،}{{h }_{j+1, j}}= 0 ~\text{اگر }~.{{h }_{j+1, j}} = \norm{{w}_{j}} $ 
			\end{itemize}
		\item
		$~ {{\upsilon }_{j+1 }}=  {w}_{j}/{{h }_{j+1, j}} ~$
			\end{enumerate}
		\item 
		${y}_{m}$  
		را به عنوان مینیمم‌کننده‌ی 
		$~ .{x}_{m} =  {x}_{0} + {{V}_{m}} {{y}_{m}}~ \text{ محاسبه کرده و قرار دهید}~ \norm{{\beta}{e}_{1} - {\overline{H} }_{m}y } ~$
	\end{enumerate}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
جوابی که الگوریتم 
\ref{alg2-1}
می‌دهد ممکن است تقریب مناسبی برای جواب مسأ‌له نباشد. برای بهبود جواب می‌توان از نسخه‌ی ''با شروع مجدد`` آن استفاده کرد. در نسخه‌ی با شروع مجدد یک حدس اولیه‌ی دلخواه 
$x_{0}$
و یک زیرفضای کرایلف 
$m$
بعدی انتخاب کرده و جواب تقریبی 
$x_m$
را به دست می‌آوریم. سپس جواب تقریبی 
$x_m$
را به عنوان حدس اولیه‌ی جدید
$x_0$
قرار داده و الگوریتم را برای به دست آوردن 
$x_m$
جدید، دوباره اجرا می‌کنیم. این روند را آنقدر تکرار می‌کنیم تا به یک جواب تقریبی با یک دقت مناسب دست پیدا کنیم. این روند در الگوریتم 
\ref{alg2-2}
جمع بندی شده است.    
\begin{algorithm}[H]
	\caption{ الگوریتم روش
	{\GMRES} 
		با شروع مجدد
		\lr{\GMRES$(m)$}}
	
	\label{alg2-2}
	\begin{enumerate}[1)]
		\item 
		محاسبه کنید 
		$~ {\upsilon}_{1}= {r}_{0}/\beta ~~\text{و} ~~\beta =  \norm{ {r}_{0}  }~ \text{،}{r}_{0} = b - A{x}_{0} ~$
		\item 
		پایه‌ی آرنولدی و ماتریس 
		$\overline{H}_m$
		با استفاده از الگوریتم آرنولدی با  شروع 
		$\nu_1$
		را بسازید.
		\item 
		${y}_{m}$
		را به عنوان مینیمم کننده‌ی 
		$ .{x}_{m} =  {x}_{0} + {{V}_{m}} {{y}_{m}}~ \text{	محاسبه کرده و قرار دهید}  \norm{{\beta}{e}_{1} - {\overline{H} }_{m}y}  ~$
		\item 
		اگر جواب تقریبی محاسبه‌ی شده در شرط توقف صدق کند سپس متوقف شود، در غیر این صورت قرار دهید 
		${x}_{0} :=  {x}_{m}$
		و به گام 1 بروید. 		
	\end{enumerate}
\end{algorithm}
%
%\subsubsection{الگوریتم 
%	\lr{\GMRES$(m)$}
%با 	پیش‌شرط‌ساز راست }
در روش تکراری 
\lr{\GMRES$(m)$}
و همچنین دیگر روش‌های تکراری مشابه برای حل دستگاه‌های نامتقارن هر سه نوع پیش‌شرط‌سازی (چپ، راست و دوطرفه) مورد استفاده قرار می‌گیرند. در اینجا ما نسخه‌ی 
\lr{\GMRES$(m)$}
با پیش‌شرط‌ساز راست را ارائه می‌نماییم. الگوریتم  
\lr{\GMRES$(m)$}
با پیش‌شرط‌‌ساز راست،  برای حل دستگاه 
$$AM^{-1} u= b, ~~~~u=Mx$$
استفاده می‌شود.
واضح است که 
$b-Ax_0=b-AM^{-1} u_0$.
 بنابراین کافی است در الگوریتم 
\lr{\GMRES$(m)$}
ماتریس 
$A$
 با ماتریس
$AM^{-1}$
جایگزین شود. 
در این صورت، روش 
\lr{\GMRES$(m)$}
با پیش‌شرط‌ساز راست به صورت الگوریتم 
\ref{rightgmres}
جمع بندی می‌شود.

\begin{algorithm}[H]
	\caption{الگوریتم روش \lr{\GMRES$(m)$}
		با پیش‌شرط‌ساز راست
	}\label{rightgmres}
	\begin{enumerate}[1)]
		\item 
	قرار دهید 
		${\upsilon}_{1}= {r}_{0}/\beta ~~ \text{و}~~ \beta =  {|| {r}_{0}  ||}_{2}~ \text{،}{r}_{0} = b - A{x}_{0} $.
		\item 
		برای 
		$ j =1,2, \ldots, m ~$، روند زیر را تکرار کنید:
		\begin{enumerate}
			\item 
			قرار دهید 
			$z_j=M^{-1}\upsilon_j$.
	\item
		قرار دهید 
		${w} := Az_{j}$. 
		\item
		به ازای $i= 1,2, \ldots, j~$، روند زیر را تکرار کنید:
		\begin{itemize}
		\item
		قرار دهید
		$~ {{h }_{i j}} = ({w} ,{\upsilon}_{i} )$.
		\item
			قرار دهید
		$~ {w} := {w} - {h }_{i j}{\upsilon}_{i}$.
				\end{itemize}
		\item
		$~{\upsilon}_{j+1} = w /{h }_{j+1, j}~\text{و }~{{h }_{j+1, j}} = {||{w}||}_{2}$
				محاسبه کنید.
				\end{enumerate}
		\item 
		تعریف کنید
		$\overline{H} _{m}= \{h_{ij}\}\displaystyle_{1\le i\le j+1,1 \le j \le m}~~\text{و}~~Z_{m} = [ {z}_{1},\ldots,{z}_{m} ]$.
		\item 
		$x_{m} = x_{0} +Z_{m} y_{m}~~\text{و}~~{y}_{m} = \text{argmin}_{y} || \beta e_{1} - \overline{H}_{m}y||_{2}~ $  را 	محاسبه کنید. 
		\item 
		اگر جواب تقریبی محاسبه‌ی شده در شرط توقف صدق می‌کند،  متوقف شوید و در غیر این صورت قرار دهید 
		${x}_{0} =  {x}_{m}$
		و به گام 1 بروید.
	\end{enumerate}
\end{algorithm}
حلقه‌ی گرام-اشمیت آرنولدی در الگوریتم 
\ref{rightgmres}
یک پایه‌ی یکامتعامد برای فضای کرایلف 
$$ span\left\{ r_{0}, AM^{-1}r_{0} , \ldots, (AM^{-1})^{m-1}r_{0}    \right\},$$
می‌سازد. 
همه‌ی بردارهای مانده و نرم آنها که از الگوریتم 
\ref{rightgmres}
محاسبه می‌شوند بردار مانده‌ی دستگاه  هستند، زیرا  
$b- Ax_{m}=b- AM^{-1}u_{m}$.
اگر در هر تکرار از روش
 \lr{\GMRES$(m)$}
  با پیش‌شرط‌ساز راست، ماتریس پیش‌شرط‌ساز 
$M$
تغییر کند، یعنی در هر گام داشته باشیم 
$z_j=M_j^{-1}\upsilon_j$، 
آنگاه الگوریتم
\gls{gmres}
% \lr{\GMRES$(m)$}
  با پیش‌شرط‌ساز راست، تبدیل به 
  \gls{fgmres}
%  ($\FGMRES$)
%\LTRfootnote{Flexible GMRES}
می‌شود.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
\subsection{ الگوریتم گرادیان مزدوج 
\lr{(\gls*{cg})}}
دستگاه معادلات خطی
\begin{align}\label{ax=b}
Ax=b,
\end{align}
را در نظر بگیرید که در آن 
$A$
یک ماتریس معین مثبت متقارن است. 
   \gls{cg} 
   از جمله الگوریتم‌های مهم برای حل این گونه دستگاه‌ها می‌باشد. تابع 
$\varphi : \mathbb{R}^{n} \to \mathbb{R} $
را به صورت 
$$\varphi(x ) = \frac{1}{2} x^T Ax - x^T b,$$
  تعریف می‌کنیم. محاسبه‌ی جواب واقعی  دستگاه 
\eqref{ax=b}
با مینیمم کردن تابع 
$\varphi $
روی
$ \mathbb{R}^{n}$
معادل است
\cite{drkhojasteh1}.  فرض کنید 
$x^{(0)}$
یک حدس اولیه‌ی برای جواب واقعی دستگاه 
\eqref{ax=b}
و
$r^{(0)}= b - Ax^{(0)}~$
مانده‌ی مربوطه باشد. در تکرار 
$(k+1)$-ام از روش \gls{cg} تقریب 
$x^{(k+1)}$
از حل مسأله‌ی  
$$\varphi(x^{(k+1)} ) = \min_{  x= x^{(0)} + \delta,~\delta \in span\{p^{(0)},p^{(1)},p^{(2)},\ldots,p^{(k)}\}  } \varphi(x ) ,$$
 به‌دست می‌آید که در آن بردارهای 
$p^{(k)}\text{،}\ldots\text{،}p^{(0)}$
معلوم هستند. الگوریتم \gls{cg} به صورت 
\ref{algmozdavaj}
نوشته می‌شود.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
\begin{algorithm}[H]
	\caption{الگوریتم  \gls*{cg}  برای حل دستگاه $Ax=b$}\label{algmozdavaj}       
	حدس اولیه‌ی $x^{(0)}$ مفروض است. قرار دهید 
	$r^{(0)}:=b-Ax^{(0)}$
و
	$ p^{(0)} :=r^{(0)}$. 
	به ازای $j=0, 1, \ldots$، روند زیر را تا حصول همگرایی دنباله‌ی $\{ x^{(k)}\}$  تکرار کنید:
	\begin{enumerate}[1)]
		\item 
		قرار دهید 
		$\alpha_{j}=\frac{(r^{(j)},r^{(j)})}{(Ap^{(j)},p^{(j)})}$.
		\item 
		قرار دهید 
		$x^{(j+1)}=x^{(j)}+\alpha_{j}p^{(j)}$.
		\item 
		قرار دهید 
		$r^{(j+1)}=r^{(j)}-\alpha_{j}Ap^{(j)}$.
		\item 
		قرار دهید
		$\beta_{j}=\frac{(r^{(j+1)},r^{(j+1)})}{(r^{(j)},r^{(j)})}$.
		\item 
		قرار دهید
		$p^{(j+1)}=r^{(j+1)}+\beta_{j}p^{(j)}$.
	\end{enumerate}
\end{algorithm}
\section{ الگوریتم گرادیان مزدوج پیش‌شرط‌سازی شده  (PCG)  }
فرض کنید ماتریس‌های 
$A$
و
$M$
هر دو معین مثبت متقارن باشند و
$.M \approx  A$
در این صورت،  ماتریس ضرایب دستگاه پیش‌شرط‌سازی شده‌ی 
$M^{-1} Ax = M^{-1}b~$
لزوماً متقارن نیست. بنابراین روش گرادیان مزدوج را نمی‌توان به طور مستقیم برای حل این     دستگاه استفاده نمود.    می‌دانیم  که ماتریس 
$M^{-1} A$
نسبت به 
$M$-ضرب‌داخلی
$(x,y)_{M} = (Mx,y) = (x,My)~$
خود‌الحاق است، زیرا  

\begin{align*}
\left(M^{-1}Ax,y\right)_M &=\left(Ax,y\right)=\left(x,Ay\right)=
\left(x,M(M^{-1} A\right)y)\\
& = \left(x,M^{-1} Ay\right)_M.
\end{align*}

بنابراین کافی است که در الگوریتم گرادیان مزدوج برای دستگاه پیش‌‌شرط‌سازی 
شده از چپ، بجای ضرب‌داخلی اقلیدسی، 
$M$-ضرب‌داخلی
  را جایگزین کنیم. در این صورت 
الگوریتم
\gls{pcg}
به صورت الگوریتم
\ref{mozdavajchap}
خواهد بود.
% فرض کنید 
% $r^{(j)}= b - Ax^{(j)}~$
% مانده‌ی دستگاه اولیه و
%$z^{(j)}=M^{-1}r^{(j)}$
% مانده‌ی دستگاه پیش‌شرط‌سازی شده باشد. در این صورت،
%\begin{equation*}
%	\left\{
%	{\begin{array}{*{20}{c}}{\alpha_{j}:=\frac{(z^{(j)},~z^{(j)})_{M} } {(M^{-1}Ap^{(j)},~p^{(j)})_{M}} = \frac{(Mz^{(j)},~z^{(j)})} {(Ap^{(j)},~p^{(j)})} = \frac{(r^{(j)},~z^{(j)})} {(Ap^{(j)},~p^{(j)})},~~~~~~} \\[0.4cm]
%	{x^{(j+1)}:=x^{(j)}+\alpha_{j}p^{(j)},~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\[0.4cm]
%	{r^{(j+1)}:=r^{(j)}-\alpha_{j}Ap^{(j)}, ~~ z^{(j+1)}:=M^{-1}r^{(j+1)} ,~~~~~~~~~~~~~~~~~~~}\\[0.4cm]
%{\beta_{j}:=\frac{(z^{(j+1)},~z^{(j+1)})_{M} } {(z^{(j)},~z^{(j)})_{M} }= \frac{(Mz^{(j+1)},~z^{(j+1)}) } {(Mz^{(j)},~z^{(j)}) } = \frac{(r^{(j+1)},~z^{(j+1)}) } {(r^{(j)},~z^{(j)}) },}\\[0.4cm]
%{p^{(j+1)}:=z^{(j+1)}+\beta_{j}p^{(j)},~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
%\end{array}}
%{\begin{array}{*{20}{c}}{ }\\{(e5 }\end{array}}
%	\right.
%	\end{equation*}
%باتوجه به این نتایج روش گرادیان مزدوج پیش‌شرط‌سازی شده\LTRfootnote{Preconditioned conjugate gradient}
%از چپ  به صورت الگوریتم 
%\ref{mozdavajchap}
% بدست می‌آید. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{algorithm}[!ht]
	\caption{الگوریتم روش گرادیان مزدوج با پیش‌شرط‌ساز چپ  }\label{mozdavajchap}       
	حدس اولیه $x^{(0)}$ مفروض است. قرار دهید 
	$r^{(0)}=b-Ax^{(0)}${،}
	$z^{(0)}=M^{-1}r^{(0)}$
	و
	$ p^{(0)} =z^{(0)}$. 
	به ازای $j=0, 1, \ldots$، روند زیر را تا حصول همگرایی دنباله‌ی $\{ x^{(k)}\}$  تکرار کنید:
	\begin{description}
		\item[1)]
		قرار دهید 
		$ \alpha_{j}:= \frac{(r^{(j)},~z^{(j)})} {(Ap^{(j)},~p^{(j)})}$.
		\item[2)]
		قرار دهید 
		$x^{(j+1)}:=x^{(j)}+\alpha_{j}p^{(j)}$.
		\item[3)]
		قرار دهید 
		$r^{(j+1)}:=r^{(j)}-\alpha_{j}Ap^{(j)}$.
		\item[4)]
		قرار دهید
		$  z^{(j+1)}:=M^{-1}r^{(j+1)}$.	
		\item[5)]
		قرار دهید
		$\beta_{j}:= \frac{(r^{(j+1)},~z^{(j+1)}) } {(r^{(j)},~z^{(j)}) }$.
		\item[6)]
		قرار دهید
		$p^{(j+1)}:=z^{(j+1)}+\beta_{j}p^{(j)}$.
	\end{description}
\end{algorithm}
\section{
	الگوریتم مینیمم درجه 
	\lr{(\gls*{md})}}
\gls{md}، 
الگوریتمی است که حافظه مورد نیاز برای محاسبه‌ی تجزیه چولسکی را کاهش داده  و باعث کاهش   عملیات محاسباتی، هنگام به کارگیری  تجزیه‌ی چولسکی یا  حالت ناقص آن می‌شود.
این الگوریتم، قبل از به کارگیری تجزیه‌ی چولسکی برای یک ماتریس هرمیتی مانند $A$،  با استفاده از  جایگشت سطرها و ستون‌ها،   تعداد    درایه‌های  ناصفر تجزیه‌ی   چولسکی  را  کاهش می‌دهد. در هر مرحله  از این الگوریتم، جایگشت‌های سطری و ستونی در مراحل حذفی گاوس، به گونه‌ای انجام می‌شوند تا تعداد درایه‌های ناصفر در بیرون از محدوده‌ی قطری را،  در محور سطری و ستونی به حداقل برسانند. 

  اگر   ماتریس جایگشت 
$P$،
توسط الگوریتم 
\gls{md}
برای ماتریس هرمیتی 
$A$
به دست آمده باشد، آنگاه   عامل تجزیه‌ی چولسکی ماتریس  هرمیتی
$P^TAP$،
دارای تعداد درایه‌های صفر کمتری  نسبت به عامل تجزیه‌ی چولسکی خود ماتریس  
$A$
دارد.  
لذا برای حل دستگاه معادلات خطی 
$Ax= b$ 
توسط الگوریتم 
\gls{md}،
ابتدا  یک ماتریس جایگشت مانند
$P $
جستجو می‌شود،  به طوری که تعداد درایه‌های مخالف صفر تجزیه‌ی چولسکی 
$P^{T}AP $
دارای کمترین تعداد  باشد. سپس دستگاه 
$({P^{T}}AP)(P^{T}x)=P^{T}b$
با استفاده از تجزیه‌ی چولسکی حل می‌گردد. 
اگر چه الگوریتم 
\gls{md}
به طور کلی روش موفقی است، اما در حالت خاص، زمانی که ماتریس
$A$
دارای سطرها و ستون‌های چگال (یا تقریباً چگال)   باشد،  ممکن است زمان اجرای آن  زیاد گردد. برای جزئیات این الگوریتم به 
\cite{saad822003}
مراجعه کنید. 

 
در برنامه‌ی متلب،   نسخه‌های متفاوتی از الگوریتم 
\gls{md}
با نام‌های 
\gls{amd}،
\gls{camd}
و     
\gls{symamd}
و ... وجود دارد. 
در الگوریتم‌های 
\gls{amd}
و
\gls{symamd}
ماتریس 
$A$ 
باید مربعی باشد. اما در الگوریتم 
\gls{camd}
ماتریس 
$A$
می‌تواند غیر مربعی باشد.  

شکل \ref{amd}، تاثیر  الگوریتم  
\gls{md} 
 بر  تعداد درایه‌های مورد نیاز برای  ذخیره‌سازی عامل تجزیه‌ی چولسکی یک ماتریس تنک را نشان می‌دهد.  برای این مثال، تعداد درایه‌های مخالف صفر عامل تجزیه‌ی چولسکی با ترکیب الگوریتم مینیمم درجه، حدود یک یازدهم درایه‌های  عامل تجزیه‌ی چولسکی آن بدون به کارگیری این الگوریتم می‌باشد. 
\begin{figure}[H]
	\label{amd}
	\begin{center}
			\includegraphics[scale=.85]{resources/amd}\caption[تاثیر الگوریتم مینیمم درجه]
		{تاثیر الگوریتم 
			\gls*{amd}
			بر روی تعداد درایه‌های ذخیره شده عامل تجزیه‌ی چولسکی}
	\end{center}
\end{figure}

