\documentclass[12pt, a4paper]{report}
\usepackage[all]{xy}
\usepackage{amsmath,amsthm,amssymb,graphicx,tikz,fancyhdr,hyperref}
%\usepackage[pagebackref=false,colorlinks,linkcolor=blue,citecolor=magenta]{hyperref}
\usepackage[font={small}]{caption}
\usepackage{xepersian}
\setdigitfont{Yas}
\usepackage{fancyhdr}
\fancyhf{}
\fancyhead[L]{\nouppercase{\rightmark}}
\fancyhead[R]{\nouppercase{\leftmark}}
\usepackage[headheight=110pt, textwidth=6.35in]{geometry}
\pagestyle{fancy}
\fancyfoot{}
\fancyfoot[C]{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\settextfont[Scale=1]{XB Niloofar}
\setlatintextfont[Scale=0.9]{Times New Roman}\linespread{1.8}
\newtheorem{de}{تعریف}[chapter]
\newtheorem{thh}[de]{قضیه}
\newtheorem{pro}[de]{گزاره}
\newtheorem{re}[de]{تذکر}
\newtheorem{lee}[de]{لم}
\newtheorem{cor}[de]{نتیجه}
\newtheorem{exa}[de]{مثال}
\newtheorem{alg}[de]{الگوریتم}
\pagenumbering{Alph}
\renewcommand\listtablename{فهرست جدول ها}
\begin{document}
\begin{titlepage}
\begin{figure}[ht]
%\centerline{\includegraphics[width=2cm]{pic/1111}}
\begin{center}
 
\end{center}
\end{figure}
\begin{center}
سمینار کارشناسی ارشد رشته ی ریاضی کاربردی گرایش آنالیز عددی
\end{center}
\begin{center}
\large
\bfseries
الگوریتم های جدید برای تعیین معکوس ماتریس ها 
\end{center}
\vspace{1cm}
\center\small
استاد راهنما\\
دکتر \\
\vspace{1cm}
دانشجو\\

\vspace{1cm}
بهار ۱۳۹۶
\end{titlepage}
\newpage
\begin{figure}[ht]
%\centerline{\includegraphics[width=16cm]{pic/10}}
\end{figure}
\newpage
\tableofcontents
\listoftables
\newpage
\pagenumbering{arabic}
\chapter*{چکیده}
این سمینار الگوریتم های جدیدی برای تعیین معکوس ماتریس های $k$-سه قطری، $k$-پنج قطری و $k$-هفت قطری را با استفاده از تجزیه دولیتل $LU$ آن ها معرفی می کند.
مرتبه هر الگوریتم به کمک ارزیابی تعداد عملیات محاسباتی در هر گام از الگوریتم داده شده است. در انتهای هر فصل تعدادی مثال عددی را با توجه به الگوریتم ها بررسی می کنیم.\\
\textit{واژه های کلیدی:}
ماتریس های $k$-قطری، تجزیه دولیتل $LU$، معکوس ماتریس، الگوریتم.
\chapter*{پیش‌گفتار}
ماتریس های $k$-سه قطری، $k$-پنج قطری و $k$-هفت قطری اغلب در بسیاری از مسائل از جمله محاسبات موازی، تحلیل سیستم های مخابراتی، حل 
معادلات دیفرانسیل جزئی، مسائل مقدار اولیه و غیره بوجود می آیند. معکوس ماتریس های $k$-سه قطری و $k$-پنج قطری توسط بسیاری از نویسندگان مورد توجه قرار گرفته است.
برای مثال مراجع ببینید.
\newpage
\chapter{تعاریف و مفاهیم اولیه}
\newpage
\section{مقدمه}
این فصل به معرفی و بیان تعاریف مورد نیاز که در فصل های بعد مورد استفاده قرار می گیرند، پرداخته شده است.\\
در ابتدا به تعریف ماتریس هایی که در این سمینار به آن ها نیاز داریم، می پردازیم.

که در آن $1\leq k <\frac{n}{3}$. به ازای $\frac{n}{3}\leq k<\frac{n}{2}$ ماتریس $R_n^{(k)}$ یک ماتریس $k$-پنج قطری به صورت \eqref{eq:d}، به 
ازای $\frac{n}{2}\le k<n$ یک ماتریس $k$-سه قطری به شکل \eqref{eq:b}، به ازای $k\ge n$ یک ماتریس قطری و برای $k=1$ یک ماترس هفت قطری به صورت \eqref{eq:e} است.
\begin{de}
تجزیه یک ماتریس مربعی $n\times n$ به صورت ضرب دو ماتریس، $L$ و $U$ که $L$ یک ماتریس 
پایین مثلثی با عناصر روی قطر اصلی یک و $U$ یک ماتریس بالا مثلثی است را تجزیه دولیتل $LU$ یک ماتریس گویند.
\end{de}
\chapter{
الگوریتم معکوس ماتریس‌های $k$-سه‌قطری}
\newpage
\section{مقدمه}
این فصل از سمینار بر اساس مرجع تنطیم شده است. ماتریس \eqref{eq:a} اغلب در بسیاری از مسائل از جمله، محاسبات موازی، تحلیل سیستم های مخابراتی، حل معادلات دیفرانسیل با استفاده از تفاضلات متناهی، انتقال گرما و مسائل جریانات سیال پدیدار می شوند. خوانندگان علاقمند می توانند به مراجع  رجوع کنند. معکوس ماتریس های سه قطری \eqref{eq:a} توسط بسیاری از نویسندگان مورد بررسی قرار گرفته است.
ماتریس \eqref{eq:b} نقش مهمی در توصیف اعداد $k$-فیبونانچی \LTRfootnote{k-Fibonacci} تعمیم یافته دارد  و اخیرا مورد توجه برخی نویسندگان  قرار گرفته است.
عناصر غیر صفر ماتریس \eqref{eq:b} تنها در $3n-2k$ محل حافظه توسط سه 
بردار $\mathbf{a}=[a_{1}, a_{2}, \dots, a_{n-k}]$، $\mathbf{b}=[b_{1}, b_{2}, \dots, b_{n-k}]$ و $\mathbf{d}=[d_{1}, d_{2}, \dots, d_{n}]$ ذخیره می شوند و در نتیجه حافظه کمتری اشغال می شود.\\
معکوس ماتریس های ‌$k$-سه قطری \eqref{eq:b} به تازگی در موارد خاصی مورد توجه قرار گرفته است. در معکوس ماتریس های $k$-سه قطری توسط ساختار توپلیتز \LTRfootnote{Toeplitz} آن ها با تحمیل برخی شرایط محدود کننده مورد مطالعه قرار گرفته است. اما در اینجا ما معکوس هر ماتریس نامنفرد $T_{n}^{(k)}$ را بدون اعمال شرایط محدود کننده بررسی می کنیم. 
\section{ساخت الگوریتم}
در این بخش ما ساختمان یک الگوریتم محاسباتی را برای تعیین معکوس هر ماتریس $k$-سه قطری نامنفرد بررسی خواهیم کرد. برای این منظور
 بردار $n$-مؤلفه ای $\mathbf{c}=[c_1, c_2, \dots, c_n]$ که مؤلفه های آن به صورت زیر تعریف می شوند را در نظر می‌گیریم.
\begin{equation}
c_{i}=\begin{cases}
d_{i}, & i=1, 2, \dots, k \\
d_{i}-y_{i-k}b_{i-k} & i=k+1, k+2, \dots, n \\
\end{cases}
\label{eq1}
\end{equation}
که برای $i=1, 2, \dots, n-k$، $y_i=\tfrac{a_i}{c_i}$.
با استفاده از بردار $c$ در \eqref{eq1} نتایج زیر را داریم.
\begin{lee}
فرض کنید $T_{n}^{(k)}$ یک ماتریس $k$-سه قطری به صورت \eqref{eq:b} و به
 ازای هر $i=1, 2, \dots, n$،
 $c_{i}\neq 0$ و به ازای هر $i=1, 2, \dots, n-k$، $z_{i}=\dfrac{b_{i}}{c_{i}}$ باشد، آنگاه تجزیه دولیتل 
 $LU$ ماتریس $T_n^{(k)}$ به صورت $T_n^{(k)}=L_n^{(k)}U_n^{(k)}$ است که در آن
\begin{equation}
\setlength{\arraycolsep}{2pt}
\renewcommand{\arraystretch}{0.8}
L_n^{(k)}=\left[\begin{array}{*{8}{c}}
1 & 0 & \ldots & \quad & \quad & \quad & \ldots & 0 \\
0 & 1 & \ddots & \quad & \quad & \quad & \quad & \vdots \\
\vdots & 0 & \ddots & \ddots & \quad & \quad & \quad & \quad \\
0 & \vdots & \ddots & \ddots & \ddots & \quad & \quad & \quad \\
z_{1} & \ddots & \vdots & \ddots & \ddots & \ddots & \quad & \quad \\
0 & z_{2} & \ddots & \ldots & \ddots & \ddots & \ddots & \vdots \\
\vdots & \ddots & \ddots & \ddots & \ldots & 0 & \ddots & 0 \\
0 & \ldots & 0 & z_{n-k} & 0 & \ldots & 0 & 1 \\
\end{array}\right]
U_n^{(k)}=\left[\begin{array}{*{8}{c}}
c_{1} & 0 & \ldots & 0 & a_{1} & 0 & \ldots & 0 \\
0 & c_{2} & 0 & \ldots & 0 & a_{2} & \ddots & \vdots \\
\vdots & 0 & \ddots & \ddots & \ldots & \ddots & \ddots & 0 \\
\quad & \quad & \ddots & \ddots & \ddots & \ldots & \ddots & a_{n-k} \\
\quad & \quad & \quad & \ddots & \ddots & \ddots &\ldots & 0 \\
\quad & \quad & \quad & \quad & \ddots & \ddots & 0 & \vdots \\
\vdots & \quad & \quad & \quad & \quad & \ddots & c_{n-1} & 0 \\
0 & \ldots & \quad & \quad & \quad & \ldots & 0 & c_{n} \\
\end{array}\right]
\end{equation}
و
\begin{equation}
det(T_n^{(k)})=\prod_{i=1}^nc_i.
\label{eq2}
\end{equation}
\end{lee}
\begin{thh}
فرض کنید $T_n^{(k)}$ یک ماتریس $k$-سه قطری به صورت \eqref{eq:b} و به ازای $i=1, 2, \dots, n$، $c_i\neq0$ باشد، آنگاه ماتریس $T_n^{(k)}$ نامنفرد است.
اگر $(T_n^{(k)})^{-1}=H=(\alpha_{i,j})_{i,j=1}^n$، آنگاه برای $i,j=1, 2, \dots, n$ داریم،
\begin{equation}
\alpha_{ii}=\begin{cases}
\dfrac{1}{c_i} & i=n, n-1, \dots, n-k+1 \\
\dfrac{1}{c_i}+y_{i}z_{i}\alpha_{i+k,i+k} & i=n-k, n-k-1, \dots, 1\\
\end{cases}
\label{eq3}
\end{equation}
و
\begin{equation}
\alpha_{ij}=\begin{cases}
-y_{i}\alpha_{i+k,j} & i<j,\quad  j \equiv i\bmod (k) \\
-z_{j}\alpha_{i,j+k} & i>j,\quad  i \equiv j\bmod (k) \\
0 & \text{در غیر این صورت} \\
\end{cases}
\label{eq4}
\end{equation}
\label{thh1}
\end{thh}
\begin{re}
معادله \eqref{eq2} تا زمانی که به‌ازای $i=1, 2, \dots, n-k$، $c_i\neq0$ باشند، برقرار است. با این وجود اگر به‌ازای برخی $i\in\{1, 2, \dots, n-k\}$، $c_i=0$ باشد 
آنگاه $det(T_n^{(k)})$ با استفاده از الگوریتم نمادین \lr{k-DETGTR} که در  آمده است محاسبه می‌شود.
\end{re}
\begin{re}
از قضیه \ref{thh1} در می‌یابیم که هر الگوریتم عددی برای تعیین معکوس ماتریس $T_n^{(k)}$ با شکست مواجه می‌شود اگر به‌ازای برخی $i\in\{1, 2, \dots, n-k\}$، $c_i=0$ باشد. از این رو برای تعیین معکوس ماتریس $T_n^{(k)}$، الگوریتم نمادین زیر که هرگز با شکست مواجه نمی‌شود را معرفی می‌کنیم.
\end{re}
\begin{alg}
\begin{LTR}
\begin{latin}
\noindent
\textbf{
For $i=1, 2, \dots, k$ do\\
\hspace*{1cm}Set: $c_i=d_i$. If $c_i=0$ then $c_i=x$ end if.\\
end do.\\
For $i=k+1, k+2, \dots, n$ do\\
\hspace*{0.5cm}Compute and simplify:\\
\hspace*{0.5cm}$y_{i-k}=\dfrac{a_{i-k}}{c_{i-k}}$\\
\hspace*{0.5cm}$c_i=d_i-b_{i-k}y_{i-k}$ If $c_i=0$ then $c_i=x$ end if.\\
\hspace*{0.5cm}$z_i=\dfrac{b_{i-k}}{c_{i-k}}$\\
end do.}
\end{latin}
\end{LTR}
\noindent
گام دوم: از الگوریتم برای بررسی ناتکین بودن ماتریس \eqref{eq:b} استفاده کن.\\
گام سوم: درایه های قطر اصلی ماتریس معکوس $H=(\alpha_{i,j})_{i,j=1}^n$، $\alpha_{ii}$، $i=1, 2, \dots, n$ را محاسبه کن:
\begin{LTR}
\begin{latin}
\noindent
\textbf{
For $i=n, n-1, \dots, n-k+1$ do\\
\hspace*{1cm}Compute and simplify: $\alpha_{ii}=\dfrac{1}{c_i}$\\
end do.\\
For $i=n-k, n-k-1, \dots, 1$ do\\
\hspace*{1cm}Compute and simplify:\\
\hspace*{1cm}$\alpha_{ii}=\dfrac{1}{c_i}+y_{i}z_{i}\alpha_{i+k,i+k}$\\
end do.}
\end{latin}
\end{LTR}
گام چهارم: درایه های بالای قطر اصلی، $\alpha_{i,j}$، $i<j$، را محاسبه کن:
\begin{LTR}
\begin{latin}
\noindent
\textbf{
For $j=n, n-1, \dots, 2$ do\\
\hspace*{0.25cm}For $i=j-k, j-2k, \dots, 1$ do\\
\hspace*{1cm}Compute and simplify:\\
\hspace*{1cm}$\alpha_{i,j}=-y_{i}\alpha_{i+k,j}$\\
\hspace*{0.25cm}end do.\\
end do.}
\end{latin}
\end{LTR}

گام پنجم: درایه های زیر قطر اصلی، $\alpha_{i,j}$، $i>j$، را محاسبه کن:
\begin{LTR}
\begin{latin}
\noindent
\textbf{
For $i=n, n-1, \dots, 2$ do\\
\hspace*{0.25cm}For $ j=i-k, i-2k, \dots, 1$ do\\
\hspace*{1cm}Compute and simplify:\\
\hspace*{1cm}$\alpha_{i,j}=-z_{j}\alpha_{i,j+k}$\\
\hspace*{0.25cm}end do.\\
end do.}
\end{latin}
\end{LTR}
گام ششم: ماتریس معکوس، $H|_{x=0}$ است.
\end{alg}
\end{document}