\section{Разностные схемы для уравнения Пуассона (задача Дирихле)}
	Рассмотрим уравнение Пуассона в области G:
	\begin{equation}
		\label{eq_4_17_1}
		\frac{d^2u}{dx_1^2} + \frac{d^2u}{dx_2^2}=f(x_1, x_2), \quad (x_1, x_2) \in G
	\end{equation}	
	
	\[
		G=\{(x_1, x_2) : 0 < x_1 < l_1, 0 < x_2 < l_2\},
	\]
	\[
		\overline{G} = G \cup \Gamma
	\]
	
	\begin{equation}
		\label{eq_4_17_2}
		u|_\Gamma = \mu(x_1, x_2)
	\end{equation}

	\begin{center}


	\begin{picture}(100,100)
	\put(13,0){\vector(1,0){100}}
	\put(13,0){\vector(0,1){95}}

	\put(13,60){\line(1,0){70}}
	\put(83,0){\line(0,1){60}}

	%названия осей координат
	\put(0, 95){$x_2$}
	\put(103,-10){$x_1$}

	%высоты отрезков
	\put(0, 60){$l_2$}
	\put(83,-12){$l_1$}

	% Г и G
	\put(46, 29){G}
	\put(0, 30){Г}
	\put(88, 30){Г}
	\put(46,-12){Г}	
	\put(46,65){Г}
	\end{picture}
	\end{center}	
	
	Введем сетку:
	\[
		\omega_h = \{ (x_1^{(i)}, x_2^{(j)}): x_1^{(i)} = ih_1, i = \overline{1, N_1 - 1}, N_1h_1 = l_1;
	\]
	\[
		 x_2^{(j)} = jh_2, j = \overline{1, N_2 - 1}, N_2h_2 = l_2 \},
	\]
	\[
		\Gamma_h = \{ x_{0, j} \}^{N_2 - 1}_{j=1} \cup \{ x_{N_1, j} \} ^{N_2 - 1}_{j=1} \cup
		\{ x_{i, 0} \}^{N_1 - 1}_{i=1}  \cup \{ x_{i, N_2} \}^{N_1 - 1}_{i=1}
	\]
	\[
		\overline{\omega_h} = \omega_h \cup \Gamma_h
	\]
	
	\begin{center}
	\begin{picture}(100,100)(-20,-10)
		\put(13,0){\vector(1,0){100}}
		\put(13,0){\vector(0,1){95}}
	
		\put(13,60){\line(1,0){70}}
		\put(83,0){\line(0,1){60}}
	
		%названия осей координат
		\put(0, 95){$x_2$}
		\put(103,-10){$x_1$}
	
		%высоты отрезков
		\put(0, 60){$l_2$}
		\put(83,-12){$l_1$}
	
		% Г и D
		\put(46, 29){D}
		\put(0, 30){Г}
		\put(88, 30){Г}
		\put(46,-12){Г}	
		\put(46,65){Г}
	
		%сетка	
		\put(35,0){\line(0,1){60}}
		\put(25,0){\line(0,1){60}}

		\put(13, 15){\line(1,0){70}}
		\put(13,25){\line(1,0){70}}

		%круги
		\put(35,15){\circle{4}}
		\put(35,25){\circle{4}}
		\put(25,15){\circle{4}}
		\put(25,25){\circle{4}}

		\qbezier(25,0)(29,-10)(35,0)
		\put(29, -15){$h_1$}

		\qbezier(13,15)(3,19)(13,25)
		\put(-5, 15){$h_2$}

		%\put(24,24){\quad{33}}

	\end{picture}
	\end{center}	
	
	Пусть \( y_{ij} = y(x^i_1, x^j_2), f_{ij} = f(x^i_1, x^j_2) \). \\
	Запишем разностную схему для задачи \eqref{eq_4_17_1}, \eqref{eq_4_17_2}:	
	\begin{equation}
		\label{eq_4_17_3}
		y_{\overline{x_1}x_1, ij} + y_{\overline{x_2}x_2, ij} = f_{ij}, (x^i_1, x^j_2) \in \omega_h
	\end{equation}
	\begin{equation}
		\label{eq_4_17_4}
		y_{ij}|_{\Gamma_h}=\mu(x^i_1, x^j_2), (x^i_1, x^j_2) \in \Gamma_h
	\end{equation}
	\eqref{eq_4_17_3}и \eqref{eq_4_17_4} представляют собой СЛАУ. Распишем \eqref{eq_4_17_3}:
	\[
		\frac{y_{i+1,j}-2y_{ij}+y_{i-1,j} }{h_1^2} + \frac{y_{i,j+2}-2y_{ij}+y_{i,j-1} }{h_2^2} = f_{ii}
	\]
	\[
		y_{ij}|_{\Gamma_h}=\mu_{ij}, \quad i = \overline{1, N_1 - 1}, j = \overline{1, N_2 - 1}
	\]
	Погрешность разностного решения \( Z_{ij} = y_{ij}-U_{ij} \) удовлетворяет задаче
	\begin{equation}
		\label{eq_4_17_5}
		Z_{\overline{x_1}x_1,ij} + Z_{\overline{x_2}x_2,ij} = - \psi_{ij}
	\end{equation}
	\[
		Z_{ij}|_{\Gamma_h}=0
	\]
	Покажем существовение и единственность решения системы \eqref{eq_4_17_3}. Докажем, что решение, 
	соответствующее однородной системе, тривиально. Соответственно, решение неоднородной
	системы существует и единственно.
	Перепишем систему \eqref{eq_4_17_3} в виде:
	\begin{equation}
		\label{eq_4_17_6}
			(\frac{2}{h_1^2} + \frac{2}{h_2^2}) * V_{i,j} = \frac{V_{i+1,j} + V_{i-1,j}}{h_1^2} + \frac{V_{i,j+1} + V_{i,j-1}}{h_2^2},
	\end{equation}
	\[
		0 < i < N_1,
	\]
	\[
		0 < j < N_2.
	\]
	\begin{myUnnumberedTheorem}
		Система \eqref{eq_4_17_6} имеет только тривиальное решение. 
	\end{myUnnumberedTheorem}
	\begin{proof}
		Предположим, что найдется такой узел \(x_{ij}\), где \(v_{ij} \neq 0\). Тогда \( \exists i_0, j_0\), такие что: \\
		\\
			а) \[ |V_{i_0,j_0}|=\max_{\substack{0 \leq i \leq N_1 \\
				 0 \leq j \leq N_2} }|V_{ij}| \] \\
			b) хотя бы в одном узле 
			\( (i_0,j_0 \pm 1), (i_0 \pm 1, j_0) \text{ будет выполнено } |V_{ij}| < |V_{i_0,j_0}| \) \\
		\\
		Рассмотрим разностную схему в узле \( i_0, j_0\):
		\[
			(\frac{2}{h_1^2} + \frac{2}{h_2^2}) * V_{i_0,j_0} = \frac{V_{i_0+1,j_0} + V_{i_0-1,j_0}}{h_1^2} + \frac{V_{i_0,j_0+1} + V_{i_0,j_0-1}}{h_2^2}
		\]
		Оценим по модулю значение левой части уравнения:
		\[
			(\frac{2}{h_1^2} + \frac{2}{h_2^2}) * |V_{i_0,j_0}| \leq \frac{2||V_{i_0+1,j_0}||_C}{h_1^2} + 
				\frac{2||V_{i_0,j_0+1}||_C}{h_2^2}
		\]
		Так как \(|V_{i_0,j_0}| = ||V||_C\):
		\[
			(\frac{2}{h_1^2} + \frac{2}{h_2^2}) * ||V||_C < (\frac{2}{h_1^2} + \frac{2}{h_2^2}) * ||V||_C
		\]
		Пришли к противоречию. Следовательно, предположение неверно и теорема доказана.
	\end{proof}
	\begin{myUnnumberedCorollary}
		Разностная задача имеет единственное решение для любых функций f и \(\mu\).
	\end{myUnnumberedCorollary}

	\section{Сходимость разностной задачи Дирихле}
	
	Рассмотрим задачу:
	\begin{equation}
		\label{eq_4_17_7}
		Z_{\overline{x_1},x_1,ij} + Z_{\overline{x_2},x_2,ij} = - \psi, \quad x_{ij} \in \omega_h
	\end{equation}
	\[
		Z_{ij}|_{\Gamma_h} = 0, \quad x_{ij} \in \Gamma_h
	\]
	Введем разностный оператор:
	\[
		L_hV_{ij} = (\frac{2}{h_1^2} + \frac{2}{h_2^2}) * V_{ij} - \frac{V_{i_0+1,j_0} + V_{i_0-1,j_0}}{h_1^2} + \frac{V_{i_0,j_0+1} 
			+ V_{i_0,j_0-1}}{h_2^2},\quad x_{ij} \in \omega_h
	\]
	\begin{myUnnumberedStatement}
		Пусть \(V_{ij} \geq 0,  X_{ij} \in \Gamma_h,  L_nV_{ij} \geq 0, x_{ij} \in \omega_h\). Тогда \( V_{ij} \geq 0 \).
	\end{myUnnumberedStatement}
	\begin{proof}
		Докажем от противного. Предположим, что \(\exists (i_0, j_0)\) такие, что: \\
		\\
			a) 
			\[ |V_{i_0,j_0}|=\min_{\substack{0 \leq i \leq N_1 \\
				 0 \leq j \leq N_2} }|V_{ij}| \] \\
			b) хотя бы в одном узле \( (i_0,j_0 \pm 1), (i_0 \pm 1, j_0) \text{ будет выполнено } V_{i_0,j_0} < V_{ij} \) \\
		\\
		Тогда:
		\[
			L_hV_{i_0j_0} = \frac{V_{i_0,j_0} + V_{i_0+1,j_0}}{h_1^2} + \frac{V_{i_0,j_0} + V_{i_0-1,j_0}}{h_1^2} +
				\frac{V_{i_0,j_0} + V_{i_0,j_0+1}}{h_2^2} + \frac{V_{i_0,j_0} + V_{i_0,j_0-1}}{h_2^2} 
		\]
		Согласно условию, хотя бы одно из этих слагамых меньше 0. Следовательно сумма тоже меньше нуля.
		Противоречие завершает доказательство.
	\end{proof}
	\begin{myUnnumberedCorollary}
		Пусть у нас есть две задачи:
		\[
			L_hy_{ij} = \phi_{ij}, \quad x_{ij} \in \omega_h
		\]
		\[
			L_hY_{ij} = \Phi_{ij} \quad x_{ij} \in \omega_h
		\]
		Пусть на границе выполняются условия:
		\[
			y_{ij} \leq Y_{ij}, \quad x_{ij} \in \Gamma_h
		\]
		\[
			|\phi_{ij}| \leq \Phi_{ij}, \quad x_{ij} \in \omega_h
		\]
		Тогда всюду выполнено:
		\[
			|y_{ij}| \leq Y_{ij}, \quad x_{ij} \in \overline{\omega_h}
		\]
	\end{myUnnumberedCorollary}
	\begin{proof}
		В силу линейности задачи для V:
		\[
			L_hV_{ij} = \Phi_{ij} + \phi_{ij}
		\]
		\[
			L_h\omega_{ij} = \Phi_{ij} - \phi_{ij}
		\]
		Правые части обоих уравнений не меньше нуля в силу вышеуказанных условий. А это, в силу доказанного утверждения, 
		означает выполнение условия, которое требовалось доказать:
		\[
			|y_{ij}| \leq Y_{ij}, \quad x_{ij} \in \overline{\omega_h}
		\]
	\end{proof}
	
	Перепишем задачу для погрешности аппроксимации в виде:
	\begin{equation}
		\label{eq_4_17_8}
		L_hZ_{ij} = \psi_{ij} \quad x_{ij} \in \omega_h
	\end{equation}
	\[
		Z_{ij} = 0, \quad x_{ij} \in \Gamma_h
	\]

	Для доказательства сходимости разностной схемы необходимо подобрать мажоранту \( Y \) так, чтобы выполнялось условие:
	\[
		L_hY_{ij} = K_1, K_1 = \textit{const} > 0
	\]
	\( Y \) будем искать в виде:
	\[
		Y_{ij} = ( l_1^2 + l_2^2 - {(x_1^{(i)})}^2 - {(x_2^{(j)})}^2 )K, \text{ где } K > 0
	\]
	\[
		Y_{ij}L_h \geq 0, x_{ij} \in \overline{\omega_h}
	\]
	\[
		Y_{ij}L_h = 4K
	\]
	Положим \( 4K = ||\psi||_C\):
	\[
		\left.\begin{array}{l l}
	  		0 = |z_{ij}|_{\Gamma_h} \leq Y_{ij} |_{\Gamma_h}, \\
	  		4K = ||\psi||_C \geq |\psi_{ij}|, x_{ij} \in \omega_h \\
		\end{array}
		\right\rbrace (|z_{ij}| \leq Y_{ij}, z_{ij} \in \overline{\omega_h})		
	\]
	\[
		||z||_C \leq Y_{ij} \leq (l_1^2 + l_2^2)K = \frac{l_1^2 + l_2^2}{4} ||\psi||_C \Rightarrow ||z||_C = \leq M||\psi||_C
	\]
	\[
		\psi = O(h_1^2 + h_2^2)\Rightarrow ||\psi||_C \leq M(l_1^2 + l_2^2) \Rightarrow ||z||_C = \leq M^2(h_1^2 + h_2^2)
	\]
	Тем самым, мы доказали следующую теорему:
	\begin{myTheorem}
		Пусть \(U(x_1,x_2) \in C^4(\overline{D})\). Тогда разностная схема \eqref{eq_4_17_3} - \eqref{eq_4_17_4} 
		сходится и имеет место оценка:
		\[
			||y_{ij} - U_{ij}||_C \leq M_1(h_1^2+h_2^2)
		\]
		Где \(M_1\) не завсит от \(h_1\) и \(h_2\).
	\end{myTheorem}
	\begin{proof}
		Из полученной оценки:
		\begin{equation}
			||\psi||_C \leq M_2(h_1^2+h_2^2)
		\end{equation}
		\[
			||y_{ij} - U_{ij}||_C \leq M(\frac{l_1^2 + l_2^2}{4})(h_1^2+h_2^2)
		\]
	\end{proof}

	\section{Методы решения разностной задачи Дирихле}

	\begin{equation}
		\frac{d^2u}{dx_1^2} + \frac{d^2u}{dx_2^2}=f(x_1, x_2) \in D
	\end{equation}
	\begin{equation}
		U|_{\Gamma_u} = \mu(x_1, x_2)
	\end{equation}
	
	Разрешим систему относительно центрального узла:
	\begin{equation}
		(\frac{2}{h_1^2} + \frac{2}{h_2^2}) y_{ij} = \frac{y_{i+1,j} + y_{i-1,j}}{h_1^2} + \frac{y_{i,j+1} + y_{i,j-1}}{h_2^2} - f_{ij}
	\end{equation}
	Будем обозначать итерацию под номером \( s - y_{ij}^{(s)}\).

	\subsection{Простая итерация (метод Якоби)}
	Получаем следующий итерационный процесс:
	\[
	(\frac{2}{h_1^2} + \frac{2}{h_2^2})y_{ij}^{(s+1)} = \frac{y_{i+1,j}^{(s)} + y_{i-1,j}^{(s)}}{h_1^2} + 
		\frac{y_{i,j+1}^{(s)} + y_{i,j-1}^{(s)}}{h_2^2} - f_{ij}
	\]
	\[
		s = 0, 1, \ldots
	\]
	\[
		y_{ij}^{(s)} = \mu_{ij}
	\]
	\[
		y_{ij}^{(0)} - \text{задано}
	\]
	Для достижения заданной точности требуется порядка \(n_0(\epsilon) \sim (h^{-2}) \sim (N^2) \), где
	\( N = max( N_1, N_2 ) \).

	\subsection{Метод Зейделя}
	\[
	(\frac{2}{h_1^2} + \frac{2}{h_2^2})y_{ij}^{(s+1)} = \frac{y_{i-1,j}^{(s+1)} + y_{i+1,j}^{(s)}}{h_1^2} + 
		\frac{y_{i,j-1}^{(s+1)} + y_{i,j+1}^{(s)}}{h_2^2} - f_{ij}
	\]
	\[
		y_{ij}^{(s+1)} = \mu_{ij}, s = 0, 1, \ldots
	\]
	\[
		\text{ при s = 0, } y_{ij}^{0} - \text{задано}
	\]
	Покажем, как находить решение:
	Начнем с узла (1, 1), далее движемся вверх до (1, n), потом из точки (2, 1) движемся вверх и т.д.
	Здест будет рисунок метода.
	С точки зрения организации алгоритма - незначительное усложнение. С точки зрения сходимости метод 
	аналогичен методу Якоби: для получения требуемой точности требуется порядка \(n_0(\epsilon) \sim O(N^2) \)
	
	\subsection{Попеременно-треугольный итерационныя метод (метод Самарского)}
	Перепишем нашу систему в виде СЛАУ:
	\[
		Ay = \phi, \text{где } A^* = A > 0, A = R_1 + R_2
	\]
	\[
		R_1 = \begin{pmatrix}
	        0,5a_{11} &   0 & \hdotsfor{2} & 0 \\
	        \ldots & 0,5a_{22} &    0 & \hdots & 0 \\
	        \hdotsfor{5} \\
	        a_{m1} & a_{m2} & \hdotsfor{2} & 0,5a_{mm}     
    	\end{pmatrix}
	\]
	\[
		R_2 = \begin{pmatrix}
	        0,5a_{11} & \hdotsfor{4} \\
	        0 & 0,5a_{22} &    a_{ij} & \hdotsfor{2} \\
	        \hdotsfor{5} \\
	        0 & 0 & \hdotsfor{2} & 0,5a_{mm}     
    	\end{pmatrix}
	\]
	\[
		(E + \omega R_1)(E + \omega R_2)\frac{y^{(s+1)} + y^{(s)}}{\tau} + Ay^{(s)} = \phi
	\]
	Где \( \omega > 0, \tau > 0 \) - итерационные параметры, \( y_0 \) задано.
	При правильной организации процесса \( w^{(s+1)} \) вычисляется по явным формулам 
		(так как \( E + \omega R_1 \) - нижняя треугольная матрица):
	\[
		(E + \omega R_1)w^{(s+1)} = \phi - Ay^{(s)}
		(E + \omega R_2)v^{(s+1)} = w^{(s+1)}
		y^{(s+1)} = y^{(s)} + \tau v^{(s+1)}
	\]
	При \(\omega > \frac{\tau}{4}\) сходится для любых \(y^{(0)}\). \\
	При этом  \(n_0(\epsilon) \sim O(N) \).
	
	\section{Основные понятия теории разностных схем. Аппроксимация. Устойчивость. Сходимость.}

	Рассмотрим произвольную линейную дифференциальную задачу:
	\begin{equation}
		\label{eq_2_18_1}
		Lu(x) = f(x), x \in G
	\end{equation}
	
	Считаем, что краевые и начальные условия будут учитываться либо видом оператора \( L \), 
	либо видом правой части.
	Принципиально, что \( L \) - линейный ператор.
	Введем на множестве \(G\) сетку \(G_h\), где \(h\) - некоторая норма шагов сетки. 
	Тогда \(x\) из непрервыного превращется в дискретное:  \(x \in G_h\). Тем же образом
	ставим в соответствие функции \(y(x)\) ее разностный аналог \(y_h(x)\). Аналогично
	поступаем с оператором \(L: L_hy_h = \phi(x), x \in G_h \).
	Рассмотрим линейное нормированное пространство непрерывных функций \( B_0 \) с нормой
	\( ||u||_0\) и \( u(x) \in B_0 \).
	Соответственно \( B_h  -\) дискретное нормированное пространство с нормой
	\( ||u||_h\) и \( u_h(x) \in B_h \).
	\begin{myUnnumberedDefinition}
		Нормы \( B_0 \) и \( B_h \) согласованы, если
		\[
			\lim_{h \xrightarrow{} 0}{||u_h||_h} = ||u||_0
		\]
	\end{myUnnumberedDefinition}
	Если нормы несогласованы, то решение разностной схемы может сходиться к решению, 
	которое не является решением исходной задачи.
	Введем оператор проектрования \( P_h : B_0 \xrightarrow{} B_h \).\\
	Таким образом \( \forall u \in B_0 : P_h(u) = u_h \in B_h\).\\
	\\
	Например:
	\[	
		G = \{x : 0 \leq x \leq 1 \}.
	\]
	\[	
		G_h = x_i: x_i = hi, i = \overline{0, N}, hN = 1, h = \frac{1}{N} > 0;
	\]
	\[
		P_h(u|_{x_i}) : u_h(x_i) = u(x_i);
	\]
	\[
		B_h = \{ y = (y_0, y_1, \ldots, y_N) \};
	\]
	Рассмотрим примеры норм:\\
	1. \( ||u||_C = \max_{x \in G}| u_x | = ||u||_0 \) \\
	Согласованная с ней норма в \( B_h \): 
	\[
		||y||_C = \max_{0 \leq i \leq N}| y_i | = ||y||_h;
	\]
	2. \( ||u||_0  = ||u||_{L_2} = {( \int_0^1{u^2(x)dx})}^{1 / 2}, \) \\
	Согласованная с ней норма в \( B_h \):
	\[ 
		||y||_h = ||u||_{L_2} = {(\sum_{i=0}^{N}{y^2_ih})}^{1 / 2}
	\]
	3. Покажем, что норма \( {(\sum_{i=0}^{N}{y^2_i})}^{1/2} \) не согласована ни с одной из норм в \( B_0 \). \\
	От противного: пусть \( u(x) \equiv 1 \), тогда:
	\[
		||u_h||_h = {(\sum_{i=0}^N1)}^{1 / 2} = \sqrt{N+1}  
	\]
	Тогда, \( ||u_h||_h \xrightarrow[h \rightarrow{} 0]{} \infty \), чего быть не может. 
	
	\begin{myUnnumberedDefinition}
		Сеточная функция \( z_h(x)\) называется погрешностью разностной схемы: \\
		\( z_h(x) =  y_h(x) - u_h(x), x \in G_h \)
	\end{myUnnumberedDefinition}
	\begin{myUnnumberedDefinition}
		Сеточная функция \( \psi_h(x)\) называется погрешностью аппроксимации 
		разностной схемы на решении исходной задачи: \\
		\( \psi_h(x) =  \phi_h(x) - L_hu_h(x), x \in G_h \)
	\end{myUnnumberedDefinition}
	\begin{myUnnumberedDefinition}
		Разностная схема аппроксимирует задачу \eqref{eq_2_18_1}, если: \\
		\( ||\psi_h||_h \xrightarrow{} 0, h \xrightarrow{} 0 \).
	\end{myUnnumberedDefinition}
	\begin{myUnnumberedDefinition}
		Разностная схема имеет порядок аппроксимации \(k\), если \( \exists M_1 > 0, k > 0 \),
		которые не зависят от \(h\) и имеет место оценка: \\
		\( ||\psi_h||_h \leq M_1h^k\).
	\end{myUnnumberedDefinition}
	\begin{myUnnumberedDefinition}
		Дифференциальная задача называется поставленной корректно, если:
		\begin{enumerate}
			\item решение задачи существует и единственно,
			\item решение задачи непрерывно зависит от \( f(x) \).
		 \end{enumerate}
	\end{myUnnumberedDefinition}
	\begin{myUnnumberedDefinition}
		Разностная схема называется корректной, если при всех достаточно малых \( h \):
		1. \(\forall \phi(x) \) решение !\(\exists \),
		2. \( \forall M_2 = const > 0, M_2\) не завиcящая от \( h \), что:
		\begin{equation}
			\label{eq_2_18_2}
			||u_h||_h \leq M_2||\psi_h||_h
		\end{equation}
		Оценка \eqref{eq_2_18_2} называется априорной оценкой и означает устойчивость разностной схемы.
	\end{myUnnumberedDefinition}
	\begin{myUnnumberedNote}
		Слева и справа не обязательно одинаковые нормы.
	\end{myUnnumberedNote}
	\begin{myUnnumberedDefinition}
		Говорят, что разностная схема сходится к решению исходной задачи \eqref{eq_2_18_1}, если:
		\[
			||z_h||_h = ||y_h - u_h||_h \xrightarrow{} 0, h \xrightarrow{} 0
		\]
	\end{myUnnumberedDefinition}
	\begin{myUnnumberedDefinition}
		Говорят, что разностная схема имеет порядок точности \(k\), если \( \exists M_3 = const > 0\)
		и не завиcящая от \( h \), что:
		\[
			||z_h||_h \leq M_3h^k
		\]
	\end{myUnnumberedDefinition}