\myAddDate{13}{02}{2009}
	Докажем существование и единственность факторизации матрицы A.
	\begin{myUnnumberedStatement}
		Пусть все главные миноры марицы А отличны от 0:
		\begin{equation*}
			%\label{eq_1_2_1}
			A_1 = a_{11} \neq 0, 
			A_2 = \begin{vmatrix}
					a_{1,1} & a_{1,2} \\
					a_{2,1} & a_{2,2}
				  \end{vmatrix}
			\neq 0,
			\cdots,
			A_i \neq 0,\ \forall i = \overline{1,m}
		\end{equation*}
		Тогда разложение в форме \eqref{eq_1_2_2} существует и единственно.
	\end{myUnnumberedStatement}
	\begin{proof}
		По свойству определителей:
		\[ \det{A_i} = \det{B_i} \cdot \det{C_i} \]
		Так как все элементы главной диагонали матрицы С равны 1, то \( \det{C_i} = 1,\ \forall i = \overline{1,m}\).
		\[ \det{B_i} = b_{11} \cdot b_{22} \cdot \ldots \cdot b_{ii} \Rightarrow \det{A_i} = \det{B_i}\]
		Исходя из этого утверждения, а также из вида определителя \( \det{B_i} \), следует:
		\[ b_{ii} = \frac{det{A_i}}{det{A_{i-1}}}, \det{A_0} = 1 \Rightarrow b_{11} = a_{11} \]
		А так как все главные миноры \eqref{eq_1_2_1} отличны от нуля, то все \( b_{ii} \)
		существуют и единственны по построению.
	\end{proof}
	
    \subsection{Связь метода Гаусса с разложением матрицы на множители}	
	Рассмотрим метод Гаусса для решения СЛАУ с применением факторизации.
	Пусть \( A = B \cdot C \), где B и C --- матрицы в разложении в форме 
		\eqref{eq_1_2_2} (матрицы НПТФ и ВТФ соответственно).\\
	В этом случае исходная система будет выглядеть следующим образом:
	\begin{equation}
		\label{eq_1_2_5}
			B \cdot C \cdot x = f
	\end{equation}
	Обозначим \( C \cdot x = y \).
	Тогда система \eqref{eq_1_2_5} распадается на две системы:
	\begin{equation}
		\label{eq_1_2_6}
	  		B \cdot y = f
	\end{equation}
	\begin{equation}
		\label{eq_1_2_7}
	  		C \cdot x = y,
	\end{equation}
	Выпишем уравнения системы \eqref{eq_1_2_6}:
	\begin{equation*}
		%\label{eq_1_2_8}
		b_{i1}y_1 + b_{i2}y_2 + \ldots + b_{ii}y_i = f_i, \forall i = \overline{1,m}
	\end{equation*}
	Поскольку \( b_{ii} \neq 0 \), мы можем разделить на \( b_{ii} \), откуда получим:
	\begin{equation}
		\label{eq_1_2_8}
		y_i = \frac{f_i - \sum_{l=1}^{i-1}b_{il}y_l}{b_{ii}}, i = \overline{1,m}
	\end{equation}
	Посчитаем число операций умножения и деления, требуемых для реализации полученной формулы.
	Для каждого уравнения этой системы получаем (i -- 1) операций умножения и 1 операцию деления.
	То есть при каждом фиксированном i получается i операций. А так как i может меняться от 1 до m,
	получаем формулу:
	\[
		\sum_{i=1}^mi = 1 + 2 + \ldots + (m-1) + m = \frac{m \cdot (m+1)}{2}
	\]
	Мы получили в точности число шагов, требуемых для преобразования правых частей 
	системы \eqref{eq_1_2_6} при прямом ходе.

		Для системы \eqref{eq_1_2_7} оценка \( \frac{m \cdot (m-1)}{2} \) получается аналогично.
	\begin{myUnnumberedTask}
		Показать, что факторизация матрицы А требует \( \frac{m^3-m}{3} \) операций умножения и деления.
	\end{myUnnumberedTask}
	\begin{proof}
		Воспользуемся формулами для факторизации из предыдущего параграфа:
		\[
			b_{ij}=a_{ij} - \sum \limits_{l=1}^{j-1} b_{il}c_{lj},\quad i \geq j
		\]
		Для вычисления каждого \(b_{ij}\) потребуется j-1 операция умножения. Отпустим индекс j:
		\[
			\sum_{j=1}^i(j - 1) = \frac{i(i - 1)}{2}
		\]
		Теперь отпустим индекс i:
		\[
			\sum_{i=1}^m\frac{i(i - 1)}{2} = \frac{1}{2}\sum_{i=1}^mi^2 - \frac{1}{2}\sum_{i=1}^mi
		\]
		Вторая сумма вычисляется элементарно, значение первой суммы нам известно из школьного курса -- \(  \frac{m(m+1)(2m+1)}{6} \).
		\[
			\frac{m(m+1)(2m+1)}{12} - \frac{m(m+1)}{4} = \frac{(m-1)m(m+1)}{6}
		\]
		Далее следующая формула:
		\[
			c_{ij}=\frac{a_{ij} - \sum \limits_{l=1}^{i-1} b_{il}c_{lj}}{b_{ii}},\quad i<j
		\]
		Для вычисления каждого \(c_{ij}\) потребуется j-1 операция умножения и 1 операция деления.
		Отпустим индекс i:
		\[
			\sum_{i=1}^{j-1}j = \frac{(j-1)j}{2}
		\]
		Отпустим индекс j:
		\[
			\frac{1}{2}\sum_{j=1}^{m}(j-1)j = \frac{1}{2}\sum_{j=1}^{m}j^2 - \frac{1}{2}\sum_{j=1}^{m}j =
			\frac{m(m+1)(2m+1)}{12} - \frac{m(m+1)}{4} = 
		\]
		\[
			\frac{(m-1)m(m+1)}{6}
		\]
		Суммируя с предыдущем результатом, получаем окончательный ответ:
		\[
			2\frac{(m-1)(m+1)m}{6} = \frac{(m^3-m)}{3}
		\]
	\end{proof}
	Получается, что суммарная сложность метода совпадает со сложностью классического метода Гаусса.
	\begin{myUnnumberedNote}
		Факторизация дает существенный выигрыш в том случае, если решается СЛАУ с построяной матрицей \(A\)
		и меняющимися правыми частями \(f\).
	\end{myUnnumberedNote}



	\section{Обращение матриц методом Гаусса-Жордана}
	Рассмотрим систему линейных алгебраических уравнений:
	\begin{equation}
		\label{eq_1_3_1}
		Ax = f, \\
		A \in R^{m \times m}, |A| \neq 0
	\end{equation}

	\begin{myUnnumberedDefinition}
		Матрица \(A^{-1}\) называется обратной к матрице \(A\), если выполнено:
		\[	
			A \cdot A^{-1} = A^{-1} \cdot A = E
		\]
	\end{myUnnumberedDefinition}
	Обозначим \( X = A^{-1} \):
	\[	
		A \cdot X = E, X = x_{ij} \ i,j \in \overline{1,m}		
	\]
	Запишем СЛАУ порядка m (c \(m^2\) неизвестными):
	\begin{equation}
		\label{eq_1_3_2}
		A \cdot X = E
	\end{equation}
	Для решения подобной системы классическим методом Гаусса потребуется порядка \(m^6\) операций.
	Покажем, что число действий можно снизить до \(m^3\).
	Для этого обозначим:
	\begin{equation}
		\label{eq_1_3_3}
		\delta_{ij} = \sum_{l=1}^{m}{a_{il}X_{lj}}
	\end{equation}
	\begin{equation}
		\label{eq_1_3_4}
		X^{(j)}=(x_{1j}, x_{2j}, \ldots, x_{mj})^T, j = \overline{1,m}
	\end{equation}
	\begin{equation}
		\label{eq_1_3_5}
		\delta^{(j)}=(\underbrace{0}_1, 0, \ldots, \underbrace{0}_{j-1}, \underbrace{1}_j, 
			\underbrace{0}_{j+1}, \ldots ,  \underbrace{0}_{m})
	\end{equation}
	Теперь система \eqref{eq_1_3_2} сводится к m системам с m уравнениями в каждой. При этом матрица А
		одна и та же для всех систем:
	\begin{equation}
		\label{eq_1_3_6}
		A \cdot x^{(j)} = \delta^{(j)}, \ j = \overline{1,m}
	\end{equation}
	Факторизуем матрицу А и перепишем полученные системы \eqref{eq_1_3_6}:
	\[
		A = B \cdot C
	\]
	\[
		B = \{b_{i,j}\ ,\ i \geq j;\ i,j \in \overline{1,m}\} \text{ (Нижняя почти треугольная форма)}
	\]
	\[
		C = \left\{ 
			\begin{array}{l l l}
		  		1,\ i = j; \\
		  		c_{i,j},\ i < j; \\
		  		0,\ i > j; \\
			\end{array}
			\right\rbrace (i,j \in \overline{i,m})
			\text{ (Верхняя треугольная форма)}
	\]
	Обозначим \(Cx^{(j)}=y^{(j)}\). Система уравнений примет вид:
	\begin{equation}
		\label{eq_1_3_7}
		By^{(j)}=\delta^{(j)}
	\end{equation}
	\begin{equation}
		\label{eq_1_3_8}
		Cx^{(j)}=y^{(j)}
	\end{equation}
	Ещё раз отметим тот факт, что матрица A остается одинаковой для всех m систем. 
	Соответственно, факторизацию матрицы А нужно проводить только один раз.
	При фиксированном j для решения формул \eqref{eq_1_3_7} и \eqref{eq_1_3_8} 
	требуется \(m^2\) операций.	А поскольку общее количество систем равно m,
	общая сложность решения составляет \(m^3\). Суммируя этот показатель с
	числом операций, требуемых для факторизации матрицы A ( \( \frac{m^3-m}{3} \) )
	получаем общую сложность \( \frac{4m^3-m}{3} \).
	Полученная оценка --- не предел. Для ее улучшения
	рассмотрим структуру матрицы B подробнее. \\
	Распишем систему \eqref{eq_1_3_7}:
	\[
		b_{11}y_1^{(j)} = 0 \Rightarrow y_1^{(j)} = 0
	\]
	\[
		b_{21}y_1^{(j)} + b_{22}y_2^{(j)} = 0 \Rightarrow y_2^{(j)} = 0
	\]
	\[
		\ldots
	\]
	\[
		y_{j-1}^{(j)} = 0
	\]
	\[
		b_{jj}y_j^{(j)} = 1
	\]
	Таким образом \( y_i^{(j)} = 0,\)\  \( i < j; \) \( y_j^{(j)} = \frac{1}{b_{jj}},\)\  \( i = j \).\\
	Оставшиеся уравнения:
	\[
		b_{i,j}y_j^{(j)} + b_{i,j+1}y_{j+1}^{(j)} + \ldots + b_{i,i}y_i^{(j)} = 0, b_{ii} \neq 0 \Rightarrow
	\]
	\[
		y_i^{(j)} = -\frac{\sum_{l=j}^{i-1}{b_{i,l}y_l^{(j)}}}{b_{ii}}, i=\overline{j+1,m}.
	\]
	Оценим число операций для реализации указанного метода решения. Фиксируем индексы i и j:
	в этом случае нам потребуется \( (i-j) \) умножений	и 1 деление. 
	Сначала отпустим индекс i ( \(i = \overline{j+1, m} \) ), тогда число операций будет равно:
	\[
		(m - j + 1) + (m - j) + \ldots + 2 + 1 = \frac{(m - j + 1)(m - j + 2)}{2}
	\]
	Далее отпустим индекс j ( \(j = \overline{1, m}\) ):
	\begin{equation}
		\label{eq_1_3_9}
			\sum_{j=1}^m{\frac{(m - j + 1)(m - j + 2)}{2}}
	\end{equation}
	\begin{myUnnumberedTask}
		Показать, что сумма \eqref{eq_1_3_9} равна \(\frac{m(m+1)(m+2)}{6}\).
	\end{myUnnumberedTask}
	\begin{proof}
		Проведем замену: \( k = m - j + 1 \):
		\[
			\sum_{k=1}^m { \frac{ k(k + 1) }{ 2 } } = \sum_{k=1}^m{\frac{k}{2}} + \sum_{k=1}^m{\frac{k^2}{2}}
		\]
		Откуда следует, что первая сумма равна \( \frac{k(k+1)}{4}\), а вторая -- \( \frac{k(k+1)(2k+1)}{12} \), 
		что в сумме и дает требуемую оценку.
	\end{proof}
	Система \eqref{eq_1_3_8} требует \( \frac{m(m-1)}{2} \) действий, а, поскольку таких систем m штук (т.к. \( j=\overline{1,m}\) ),
	то для их решения потребуется \( \frac{m^2(m-1)}{2} \) операций.
	Таким образом, суммарное количество операций, требуемых на решение \eqref{eq_1_3_1} равно:
	\[
		\underbrace{ \frac{m^3-m}{3}}_{\text{факторизация }\eqref{eq_1_3_1}} + \underbrace{\frac{m(m+1)(m+2)}{6}}_{\text{решение }\eqref{eq_1_3_7}} + \underbrace{\frac{m^2(m-1)}{2}}_{\text{решение }\eqref{eq_1_3_8}} = m^3
	\]
	
	\section{Метод квадратного корня}
	Рассмотрим систему линейных алгебраических уравнений:
	\begin{equation}
		\label{eq_1_4_1}
		Ax = f, \\
		A \in \mathbb{C}^{m \times m} (\mathbb{R}^{m \times m}), |A| \neq 0
	\end{equation}
	\begin{myUnnumberedDefinition}
		Матрица A называется эрмитовой (или самосопряженной) матрицей, если
		\[
			A = A^*, a_{ij} = \overline{a_{ji}}
		\]
	\end{myUnnumberedDefinition}
	Пусть A - эрмитова матрица. Представим ее в виде:
	\begin{equation}
		\label{eq_1_4_2}
		A = S^*DS
	\end{equation}
	где:\\
	\( D \) - диагональная матрица \( d_{ii} = \pm 1; \quad i=\overline{1,m}\),\\
	\( S \) - верхняя треугольная матрица \( s_{ij} > 0, \, i < j, \, i, j=\overline{1,m}\),\\
	\( S^* \) - матрица, сопряженная к S.\\
	Рассмотрим метод нахождения матриц \(S\) и \(D\) на примере вещественных матриц второго порядка:
	\[
		A = 
		\begin{pmatrix}
			a_{11} & a_{12} \\
			a_{21} & a_{22}
		\end{pmatrix}
		\text{ , }
		S = 
		\begin{pmatrix}
			s_{11} & s_{12} \\
			0 & s_{22}
		\end{pmatrix}
	\]
	\[
		S^* = 
		\begin{pmatrix}
			s_{11} & 0 \\
			s_{12} & s_{22}
		\end{pmatrix}
		\text{ , }
		D = 
		\begin{pmatrix}
			d_{11} & 0 \\
			0 & d_{22}
		\end{pmatrix}
	\]
	Перемножим матрицы \(S^* D \text{ и }S \):
	\[
		DS =
		\begin{pmatrix}
			d_{11}s_{11} & d_{11}s_{12} \\
			0 & d_{22}s_{22}
		\end{pmatrix}
	\],
	\[
		S^*DS =
		\begin{pmatrix}
			s_{11} & 0 \\
			s_{12} & s_{22}
		\end{pmatrix}
		\begin{pmatrix}
			d_{11}s_{11} & d_{11}s_{12} \\
			0 & d_{22}s_{22}
		\end{pmatrix}
		=
		\begin{pmatrix}
			d_{11}s_{11}^2 & d_{11}s_{11}s_{12} \\
			d_{11}s_{11}s_{12} & d_{11}s_{12}^2 + d_{22}s_{22}^2
		\end{pmatrix}		
	\]
	Из \eqref{eq_1_4_2} и условия равенства матриц получаем соотношения:
	\begin{equation}
		\label{eq_1_4_3}
		a_{11} = d_{11}s_{11}^2
	\end{equation}
	\begin{equation}
		\label{eq_1_4_4}
		a_{12} = d_{11}s_{11}s_{12}
	\end{equation}
	\begin{equation}
		\label{eq_1_4_5}
		a_{22} = d_{11}s_{12}^2 + d_{22}s_{22}^2
	\end{equation}