API tools faq
paste
Advertisement
Jade39

йцу

Jade39
May 28th, 2014
265
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Latex 111.69 KB | None | 0 0
raw download clone embed print report
  1. \documentclass[a4paper,12pt,times]{extarticle}
  2. %\voffset=-1in
  3. %\hoffset=-1in
  4. \oddsidemargin=85pt
  5. %\textwidth=16cm
  6. %\textheight=24cm
  7. \usepackage{array}
  8. \usepackage{amssymb}
  9. \usepackage{amsmath}
  10. \usepackage{graphicx}
  11. \usepackage{multirow}
  12. \usepackage{longtable}
  13. \usepackage{indentfirst}
  14. \usepackage[T2A]{fontenc}
  15. \usepackage[cp1251]{inputenc}
  16. \usepackage[english,russian]{babel}
  17. \usepackage[colorlinks,urlcolor=blue]{hyperref}
  18. \usepackage{geometry}
  19. \geometry{left=3.5cm}
  20. \geometry{right=1.5cm}
  21. \geometry{top=2cm}
  22. \geometry{bottom=2.4cm}
  23. %\linespread{1.3} % полуторный интервал
  24. %\renewcommand{\rmdefault}{ftm} % Times New Roman
  25. \frenchspacing
  26. \renewcommand{\baselinestretch}{1.5}        % полуторный междустрочный интервал
  27. \makeatletter
  28. % запрещаем переносы в названиях секций
  29. \renewcommand{\section}{\@startsection{section}{1}{0pt}%
  30.                                 {-3.5ex plus -1ex minus -.2ex}%
  31.                                 {2.3ex plus .2ex}%
  32. {\centering\hyphenpenalty=10000\normalfont\Large\bfseries}}
  33.  
  34.  
  35. \begin{document}
  36. \large
  37. \thispagestyle{empty}
  38. %\begin{titlepage}
  39. \begin{center}
  40. {\small МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ\\
  41. Федеральное государственное автономное образовательное учреждение\\
  42. высшего профессионального образования\\
  43. Балтийский федеральный университет имени Иммануила Канта\\
  44. (БФУ им.И.Канта) \\}
  45. \vspace{1em}
  46. Институт прикладной математики и информационных технологий
  47. \end{center}
  48. \vspace{0.5em}
  49. \begin{flushright}
  50. \begin{tabular}{l}
  51. Кафедра прикладной математики\\
  52. ВКР допущена к защите\\
  53. и.о. Зав.кафедрой, к.ф.-м.н., доцент\\
  54. \underline{\hspace{3.5cm}} Милованов В.Ф.\\
  55. "\underline{\hspace{1.1cm}}"$~$\underline{\hspace{4cm}} 2014 г.
  56. \end{tabular}
  57. \end{flushright}
  58. \vspace{0.5em}
  59. \begin{center}
  60. \large Выпускная квалификационная работа
  61. \end{center}
  62. \begin{center}
  63. на тему: "Применение метода декомпозиции области к решению
  64. краевых задач
  65. "
  66. \end{center}
  67. \vspace{1em}
  68. \begin{tabular}{lll}
  69. ВКР защищена на оценку:&~~~~~~~~~~~~~~~~~~&Студент 5 курса\\
  70. \underline{\hspace{5.7cm}}& &специальности <<прикладная\\
  71. & &математика и информатика>>\\
  72. & &\underline{\hspace{3.5cm}} В.С. Каширин\\
  73. & &\\
  74. Руководитель:& &Рецензент:\\
  75. \underline{\hspace{4.7cm}}&~~~~~~~~~~~~~~~~~~& \underline{\hspace{4.7cm}}
  76. \end{tabular}
  77. \vspace{\fill}
  78. \begin{center}
  79. Калининград\\2014
  80. \end{center}
  81. %\end{titlepage}
  82.  
  83. \newpage
  84. \thispagestyle{empty}
  85. \tableofcontents
  86. \numberwithin{equation}{section}
  87.  
  88. \newpage
  89. \section*{Введение}
  90. \addcontentsline{toc}{section}{Введение}
  91. Многие важные научно--технические задачи приводят к исследованию процессов, описываемых дифференциальными уравнениями. Несмотря на значительные успехи, достигнутые в области численного решения этих уравнений, проблема дальнейшего совершенствования алгоритмов остается актуальной. Заметное место среди работ по методам решения дифференциальных уравнений занимают исследования, связанные с построением высоко эффективных алгоритмов для решения задач в областях специального вида. В данной работе рассматривается задача на L-- образной области. Эффективным методом решения таких задач является метод декомпозиции области.
  92.  
  93. Декомпозиция области главным образом относится к разбиению частичного дифференциального уравнения, или его приближения, в сочетаниях задач на меньших подобластях, формирующих разбиение исходной области. Это разложение может входить в непрерывный уровень, где различные физические модели могут использоваться в различных областях, или на уровне дискретности, где  можно удобно использовать различные методы приближения в различных областях, или в решении алгебраических систем, являющихся результатом приближения дифференциального уравнения в частных производных. Эти аспекты очень часто связываются практически.
  94.  
  95. Существует множество физических явлений, которые удается адекватно описывать, используя различные модели в разных подобластях. Для объединения моделей задаются дополнительные условия на границе раздела подобластей. Например, взаимодействие течения в канале, описываемого уравнениями Навье--Стокса, и течения в пористой среде (фильтрации), описываемого уравнением Дарси, подразумевает разбиение расчетной области на подобласть--канал и подобласть--пористую среду, на границе раздела которых налагается условие непрерывности потока жидкости и нормальной компоненты тензора напряжений. На основе методов декомпозиции можно построить такой итерационный алгоритм решения общей сеточной задачи, что на каждой итерации в каждой подобласти нужно будет решать свое уравнение с особым граничным условием, а полученное решение будет удовлетворять условиям "сшивки" на границе раздела.
  96.  
  97. В общем случае, имеется много способов разбиения большой задачи на части, много способов решения индивидуальных подзадач и много способов монтажа их решений. Теория декомпозиции области не имеет магического рецепта для выбора в каждом случае наилучших способов, однако она указывает набор вариантов, среди которых разумно сделать выбор. В некоторых случаях (например, для задач, достаточно похожих на уравнение Пуассона) эта теория приводит к «оптимальным методам».
  98.  
  99. Целью выпускной квалификационной работы состоит в том, что на примере модельной задачи для L--образной области реализовать, исследовать и сравнить методы решения. Будут рассмотрены методы представленные в [4] и [6]. А так же будут рассмотрены способы решения уравнения Пуассона, с различными граничными условиями Дирихле и Неймана на L--образной области. И будет показано на решение тестового задания, где область будет разбита на две области: малый квадрат и большой квадрат, с размерами квадратов 3 на 3 и 7 на 7 соответственно.
  100.  
  101. В первом параграфе предоставлена основная теория, цель которого дать основные понятия метода деокомпозиции области для помощи в дальнейшем изучении методов решения. Во втором параграфе изложена теория метода без перекрытия или прямого метода. Суть этого метода состоит в нахождение дополнения Шура, что оказывается очень трудоемкой операцией. Так же в этом параграфе написан алгоритм реализации этого метода. В третьем и четвертом параграфе идет речь об методе сопряженных градиентов, который выходит менее затраным, чем прямой метод. В них идет описания метода и способы улучшения этого метода для более эффективной работы, а так же алгоритмы реализации. В следующих четырех параграфах пойдет речь о
  102. методе Дирихле-Нейман,  методе Нейман-Нейман,  методе Дирихле-Дирихле и  методе Шварца, в каждом из них идет описания метода и способы решения поставленной задачи. В девятом параграфе показано описания решения тестового задания различным способами с пояснениями, методами которые были представлены в предыдущих параграфах.
  103. \newpage
  104. \section{Математические основы методов декомпозиции}
  105. \setcounter{equation}{0}
  106. Пусть $\Omega $~--- область в $ R^d $ где ищется решение уравнения. Для подобласти $\omega \subset \Omega $ скалярное произведение в пространстве $L_2(\omega)$ будем обозначать$(\cdot,\cdot)_{\omega} $. В случае, когда область интегрирования есть вся область $\Omega $, будем опускать индекс $(\cdot,\cdot)=(\cdot,\cdot)_{\Omega} $.
  107. \subsection*{Условие сшивки}
  108. Рассмотрим уравнение общего случая краевой задачи для эллиптического уравнения в частных производных:
  109. \begin{align*}
  110. - \sum_{i,j=1}^{d} \frac{\partial}{\partial x_i}(a_{i,j}(x)\frac{\partial u}{\partial x_j})+\sum_{i=1}^d b_i(x)\frac{\partial u}{\partial x_j}+c(x)u=f, \\
  111. u\big|_{\Gamma_1}=0,\:\: \frac{\partial u}{\partial n}\big|_{\Gamma_2}=h
  112. \end{align*}
  113.  в простейшем случае $a_{1,1}\:=\:a_{2,2}\:=\:1,\:a_{1,2}\:=\:a_{2,1}\:=\:0,\:\Gamma_1\:=\:\partial \Omega $ :
  114. \begin{equation}
  115. \begin{split}
  116. -\triangle u \: & = \: f \:\mbox{в}\: \Omega\\
  117. u\: & = \: 0 \: \mbox{на}\: \partial \Omega
  118. \end{split}
  119. \label{1-1}
  120. \end{equation}
  121. Предположим, что $\Omega$  разбита на две непересекающиеся подобласти $\Omega_1,\Omega_2$ с границей раздела $\Gamma$, в дальнейшем именуемой интерфейсом. Предположим также, что $\partial \Omega,\partial \Omega_1,\partial \Omega_2$~--- кусочно-гладкие, а решение (\ref{1-1}) $u\:\in C^1(\bar\Omega)$. Тогда задача (\ref{1-1}) эквивалентна двум подзадачам с условиями сшивки на $\Gamma$:
  122.  %\begin{equation}
  123.  \begin{eqnarray}
  124. \begin{split}
  125. -\triangle u_1  &= f\:\:\: \mbox{в} \:\:\: \Omega_1,\:\:\:\qquad \qquad              -\triangle u_2 = f \:\:\: \mbox{в}\:\:\: \Omega_2\\
  126. u_1\:   &= 0 \:\:\: \mbox{на} \:\:\: \partial \Omega_1 \setminus \Gamma, \qquad  \qquad u_2 =0\:\:\: \mbox{на}\:\:\: \partial \Omega_2 \setminus \Gamma \\
  127. \end{split}
  128. \label{1-2}
  129.  \end{eqnarray}
  130.   \begin{eqnarray}
  131. u_1\:=\:u_2\:\:\: \mbox{на}\:\:\:\Gamma,\:\:\:\frac{\partial u_1}{\partial n}=\frac{\partial u_2}{\partial n}\:\:\:\mbox{на}\:\:\:\Gamma
  132.  %\end{equation}
  133.  \label{1-3}
  134. \end{eqnarray}
  135. где $n$ обозначает нормаль к $\Gamma$.\par
  136. Для слабой постановки задачи (\ref{1-1}) можно также сформулировать соответствующий (\ref{1-2}-\ref{1-3}) аналог.Слабая постановка для задачи (\ref{1-1}) состоит в нахождение $u \in V$ такое, что
  137. \begin{equation}
  138. a(u,v)=(f,v),\:\: \forall v\in V,
  139. \label{1-4}
  140. \end{equation}
  141. где $V=H_0^1(\Omega),a(u,v)=(\nabla u,\nabla v).$Введем дополнительно следующие пространства:
  142. \begin{eqnarray}
  143. V_i &=&\:\{v\in H^1(\Omega_i):\: v\big|_{\partial \Omega_i\setminus \Gamma } =0\},\:\:i=1,2, \label{1-5}\\
  144. V_i^0 &=&\:\{v\in H^1(\Omega_i):\: v\big|_{\partial \Omega_i}=0\}\:\:i=1,2, \label{1-6}\\
  145. \Lambda &=&\:\:\{\eta \in H^{\frac{1}{2}}(\Gamma):\:\eta=v\big|_{\Gamma},v\in V\}.
  146. \label{1-7}
  147. \end{eqnarray}\par
  148. По поводу пространства следов $\Lambda$ отметим следующее. В случае \\$\Gamma \cup \partial \Omega = \varnothing$ интерфейс является замкнутым множеством, совпадающим, например, с $\partial \Omega_1$. Если $\Omega_1$, обладает регулярной формой и ее диаметр порядка единицы, то норма в пространстве $H^{\frac{1}{2}}(\Gamma)$ задается по формуле
  149. \begin{align*}
  150. \big\|\eta\big\|_{H^{\frac{1}{2}}(\Gamma)}=\left(\big\|\eta\big\|_{L_2(\Gamma)}^2=\int\limits_{\Gamma}\int\limits_{\Gamma} \frac{(\eta(s)-\eta(t))^2}{|s-t|^2}dsdt\right)^{\frac{1}{2}}
  151. \end{align*}
  152. В случае $\Gamma \cup \partial \Omega \not= \varnothing $ интерфейс выходит на границу $\partial \Omega$ в точках$x_a,x_b$. При этом пространство следов функций из $H_0^1(\Omega)$ на $\Gamma$ имеет в
  153. литературе специальное обозначение: $H_{00}{\frac{1}{2}}(\Gamma)$ и снабжено усиленной нормой
  154. \begin{align*}
  155. \big\|\eta\big\|_{H_{00}^{\frac{1}{2}}(\Gamma)}=\biggl(\big\|\eta\big\|_{L_2(\Gamma)}^2=\int\limits_{\Gamma}\int\limits_{\Gamma} \frac{(\eta(s)-\eta(t))^2}{|s-t|^2}dsdt + \\
  156. +\int\limits_{\Gamma} \frac{\eta^2(s)}{|s-x_a|^2}ds+\int\limits_{\Gamma} \frac{\eta^2(s)}{|s-x_b|^2}ds \biggl)^{\frac{1}{2}}
  157. \end{align*}
  158. Для нормы в пространстве $\Lambda$ верна оценка
  159. \begin{align*}
  160. \|\eta\|_{\Lambda} \ge \|\eta\|_{L_2(\Gamma)}
  161. \end{align*}
  162. Для подзадач с условиями сшивки на $\Gamma$ (\ref{1-2}-\ref{1-3})  слабая постановка выглядит следующим образом: найти $u_i \in V_i$ такие, что $u_1=u_2$ на $\Gamma$,
  163. \begin{eqnarray}
  164. a_i(u_i,v_i)=(f,v_i)_{\Omega_i} \:\:\: \forall v_i \in V_i^0 ,\:\:\: i=1,2 \label{1-8}\\
  165. a_1(u_1,R_{1} \mu)+a_2(u_2,R_{2} \mu)=(f,R_{1}\mu)_{\Omega_1}+(f,R_{2}\mu)_{\Omega_2}\:\:\: \forall \mu \in \Lambda.
  166. \label{1-9}
  167. \end{eqnarray}
  168.  
  169. Здесь $a_i(u,v)=(\nabla u,\nabla v)_{\Omega_i}$, а через $R_i$ обозначен оператор продолжения из $\Lambda$ в $V_i$, такой, что $(R_{i \eta})=\eta$.\\
  170.  
  171. {\bf Лемма 1.1 } {\em Задачи }(\ref{1-4}) {\em и} (\ref{1-8}-\ref{1-9}) {\em эквивалентны}.\\
  172. Доказательство. Пусть верно (\ref{1-4}). Положим $u_i=u\big|_{\Omega_i}$. Так как $V_i^0 \subset V,$ то
  173. \begin{align*}
  174. a(u_i,v_i)=a(u,v_i)=(f,v_i)\:\:\:\: \forall v_i \in V_i^0.
  175. \end{align*}
  176. Специально, для$u_i=u\big|_{\Omega_i} $выполняется (\ref{1-8}). Функция
  177. \begin{align*}
  178. R\mu=
  179. \begin{cases}
  180. R_1\mu\:\:\: \mbox{в}\:\Omega_1\\
  181. R_2\mu\:\:\: \mbox{в}\:\Omega_2
  182. \end{cases}
  183. \end{align*}
  184. принадлежит $V$, поэтому $a(u,R\mu)=(f,R\mu)$, то есть выполняется (\ref{1-9}).
  185. Теперь докажем утверждение в обратную сторону. Пусть верно (\ref{1-8}-\ref{1-9}). Положим
  186. \begin{align*}
  187. u=
  188. \begin{cases}
  189. u_1\:\:\:\mbox{в} \: \Omega_1\\
  190. u_2\:\:\:\mbox{в} \: \Omega_2.
  191. \end{cases}
  192. \end{align*}
  193. Функция $u$ принадлежит $V$, поскольку $u_1=u_2$ на $\Gamma$. Кроме того, для любого $v \in V$ определим $\mu=v|_{\Gamma}\in \Lambda$ и его продолжение $R\mu \in V$. Поскольку $v\big|_{\Omega_i} - R_i\mu \in V_i^0$, получаем из (\ref{1-8}) и (\ref{1-9}):
  194. \begin{align*}
  195. a(u,v)=a(u,v\pm R_i\mu)=\sum_{i=1}^2\{a_i(u,v\big|_{\Omega_i}-R_i\mu)+a_i(u_i,R_i\mu)\}\\
  196. =\sum_{i=1}^2\{(f,v\big|_{\Omega_i}-R_i\mu)_{\Omega_i}+(f,R_i\mu)_{\Omega_i}\}=(f,v).
  197. \end{align*}
  198. Применение Леммы $1.1$ для конечно-элементных пространств позволит сформулировать условия сшивки на сеточном уровне.
  199.  
  200. \subsection*{Теорема о продолжении и теорема о следах}
  201. Утверждения этого раздела являются техническими и приводятся без доказательства. Пусть $\Omega$ разбита на две непересекающиеся подобласти $\Omega_1$, $\Omega_2$ с кусочно-гладкими границами и интерфейсом $\Gamma$.\\ \par
  202.  
  203. {\bf Теорема 1.2}.{\em Существует оператор продолжения из $\Omega_2$ в $\Omega$, $R_{12}$:\\ $V_2 \rightarrow V$, такой, что
  204. \begin{eqnarray}
  205. \|R_{12}u_2\| \le \hat C_{12} \|u_2\|v_2 \:\:\: \forall u_2 \in V_2,
  206. \label{1.10}
  207. \end{eqnarray}
  208. где константа $\hat C_{12}$ зависит только от подобластей $\Omega_1$, $\Omega_2$.\par
  209. Замечание}. Существует такая константа $C_{12},$ зависящая от подобластей $\Omega_1$, $\Omega_2$ что
  210. \begin{eqnarray}
  211. a(R_{12}u_2,R_{12}u_2) \le C_{12}^2 a_2(u_2,u_2).
  212. \label{1-11}
  213. \end{eqnarray}
  214. {\bf Теорема 1.2.} {\em Для любой $u_i \in V_i$ существует, ее след $u_i\big|_{\Gamma}$ на $\Gamma$, причем
  215. \begin{eqnarray}
  216. \big\|u_i\big|_{\Gamma}\big\|_{\Lambda}\le \breve C_i\big\|u_i\big\|_{V_i},
  217. \label{1-12}
  218. \end{eqnarray}
  219. и существует оператор продолжения с $\Gamma$ в $\Omega_i$,$R_i$ : $ \Lambda \rightarrow V_i$, такой, что
  220. \begin{eqnarray}
  221. \big\|R_i\mu\big\|_{V_i}\le \hat C\big\|\mu\big\|_{\Lambda} \:\:\: \forall  \: \mu  \:\: in  \:\: \Lambda,
  222. \label{1-13}
  223. \end{eqnarray}
  224. где константы $\hat C_i$, $\breve C_i$ зависят только от подобластей $\Omega_1,\:\:\Omega_2.$} \\ \par
  225. Конечно-элементные аналоги теорем $1.1$, $1.2$ получаются формальной заменой пространств $V$, $V_i $, $\Lambda $ на их конечно-элементные подпространства \\$U^h,$ $ U_i^h$, $\Lambda^h $   при этом операторы продолжения $R_{12} $, $R_i$ заменяются на сеточные операторы продолжения $R_{12}^h,$ $R_q^h $. Независимость констант $\hat C_{12}, C_{12},$ $ \breve C_i, \hat C_i$ от размерности пространств $U_i^h $, (для квазиравномерных сеток это означает независимость от $h$), вообще говоря, не очевидна. Например, это не следует непосредственно из аппроксимационных свойств пространств $U_i^h $. Для определенных классов сеток независимость констант от размерности $V_i^h$ доказать удается. В частности, для конформных регулярных триангуляций, аппроксимирующих $\partial \Omega_1$ и $\partial \Omega_2$ со вторым порядком, константы $\hat C_{12},C_{12}, \breve C_i,\hat C_i$ не зависят от числа узлов сетки. Все триангуляции, рассмотренные ниже, принадлежат этому классу. Учитывая это замечание, мы будем ссылаться на теоремы $1.1$, $1.2$ как для соболевских пространств, так и для их конечно-элементных подпространств.
  226. \subsection*{Уравнение Пуанкаре-Стеклова}
  227.  
  228. Рассмотрим задачу (\ref{1-1}) в области $\Omega$,разбитой на две подобласти $\Omega_1$, $\Omega_2$ с интерфейсом $\Gamma$ так, что $ \partial \Omega_1 \not = \Gamma$ и $\partial \Omega_2 \not = \Gamma  $. Напомним, что пространство следов в этом случае $\Lambda=H_{00}^{\frac{1}{2}}(\Gamma)$. Для любой $\phi \in \Lambda$ определим гармоническое продолжение $H_i \varphi \in V_i$:
  229. \begin{eqnarray}
  230. \begin{split}
  231. -\triangle (H_i \varphi) &= 0 \qquad \mbox{в}\:\: \Omega_i,\\
  232. H_i \varphi              &= \phi \qquad \mbox{на}\:\: \Gamma,\\
  233. H_i \varphi              &= 0 \qquad \mbox{на}\:\: \partial \Omega_i \setminus \Gamma.
  234. \end{split}
  235. \label{1-14}
  236. \end{eqnarray}
  237. Для произвольной $f \in L_2(\Omega_i) $ обозначим через $T_i f \in H^1(\Omega_i) $  решение уравнения Пуассона в $\Omega_i$:
  238. \begin{eqnarray}
  239. \begin{split}
  240. -\triangle (T_i f) &= \:f \qquad \mbox{в}\:\: \Omega_i,\\
  241. T_i f              &= \:0 \qquad \mbox{на} \:\: \partial \Omega_i
  242. \end{split}
  243. \label{1-15}
  244. \end{eqnarray}
  245. Пусть $u$ --- решение уравнения (\ref{1-1}), а $\lambda$ ~--- след $u$ на $\Gamma$. В каждой подобласти и можно представить следующим образом:
  246. \begin{eqnarray}
  247. u_i=u\big|_{\Omega_i}=H_i \lambda + T_i f.
  248. \label{1-16}
  249. \end{eqnarray}
  250. Следовательно,
  251. \begin{eqnarray}
  252. \int\limits_{\Omega_i}(\nabla u_i)^2 dx=\int\limits_{\Omega_i}(\nabla H_i \lambda)^2 dx + \int\limits_{\Omega_i}(\nabla T_i f)^2 dx.
  253. \label{1-17}
  254. \end{eqnarray}
  255. Из равенства (\ref{1-17}) следует, что гармоническое продолжение $H_i \lambda$ обладает минимальной энергетической полунормой среди всех функций $v \in H^1(\Omega)$ таких, что $v\big|_{\Gamma}=\lambda$ и $v\big|_{\partial \Omega \setminus \Gamma}=0$.\par
  256. Наша цель --- получить операторное уравнение на $\lambda$, для этого воспользуемся непрерывностью потока на интерфейсе:
  257. \begin{align*}
  258. \frac{\partial u_1}{\partial n}=\frac{\partial u_2}{\partial n}
  259. \end{align*}
  260. Благодаря (\ref{1-16}) получаем
  261. \begin{eqnarray}
  262. \frac{\partial}{\partial n}(H_1-H_2)\lambda = \frac{\partial}{\partial n}(T_2-T_1)f.
  263. \label{1-18}
  264. \end{eqnarray}
  265. Определим оператор Пуанкаре-Стеклова $S=\frac{\partial}{\partial n}(H_1-H_2): \Lambda \rightarrow \Lambda' $ и правую часть $\chi=\frac{\partial}{\partial n}(T_2-T_1)f \in \Lambda'$, где $\Lambda' = H^{-\frac{1}{2}}(\Gamma)$. Уравнение $(2.18)$ в операторной форме принимает вид
  266. \begin{eqnarray}
  267. S\lambda=\chi
  268. \label{1-19}
  269. \end{eqnarray}
  270. и называется уравнением Пуанкаре-Стеклова. Это уравнение будет весьма полезно в дальнейшем, поэтому изучим свойства оператора $S$. Обозначим через $n_i$ нормаль к $\Gamma$, являющуюся внешней по отношению к $\Gamma_i$. \\ \par
  271.  
  272. {\bf Лемма 1.2 }{\em $\displaystyle \frac{\partial}{\partial n_i}H_i$~--- симметричный и положительно определенный оператор в $L_2(\Gamma)$.\\
  273. Доказательство.} Пусть $u,v$~--- произвольные гармонические функции в $\Omega_i$. С помощью формулы Грина получаем
  274. \begin{align*}
  275. \int\limits_{\Gamma} \frac{\partial v}{\partial n_i}u ds-(\nabla u, \nabla v)_{\Omega_i}=(u,\triangle)_{\Omega_i}=\int\limits_{\Gamma} \frac{\partial u}{\partial n_i}v ds-(\nabla u,\nabla v)_{\Omega_i}
  276. \end{align*}
  277. Принимая в данном соотношении $u=H_i \mu$ и $v=H_i \lambda$ для произвольных $\mu,\lambda,$ получаем симметрию оператора:
  278. \begin{align*}
  279. \int\limits_{\Gamma} \lambda \frac{\partial}{\partial n_i}H_i \mu ds=\int\limits_{\Omega_i} \nabla H_i \mu \cdot \nabla H_i \lambda dx = \int\limits_{\Gamma} \mu \frac{\partial}{\partial n_i} H_i \lambda ds
  280. \end{align*}
  281.  
  282. и положительную определенность оператора:
  283. \begin{align*}
  284. \int\limits_{\Gamma} \mu \frac{\partial}{\partial n_i} H_i \mu ds = \int \limits_{\Omega_i} \nabla H_i \mu \cdot \nabla H_i \mu dx &\ge \frac{1}{C(\Omega_i)^2 +1} \big\|H_i \mu \big\|_{V_i}^2 \\
  285. &\ge \frac{1}{(C(\Omega_i)^2 +1)\breve C_i^2} \big\|\mu\big\|_{L_2(\Gamma)^2}.
  286. \end{align*}
  287.  
  288. Здесь $C(\Omega)$~--- константа из неравенства Фридрикса \\ $ \left ( \int \limits_{\Omega} u^2 dx \right )^{\frac{1}{2}} \le C(\Omega) \left ( \int \limits_{\Omega} (\nabla u)^2 dx \right )^{\frac{1}{2}} $, которое также верно для функций, зануляющийся лишь на части границы $ \partial \Omega_i $. \par
  289. Пусть $n$ в определении оператора $S$ является внешней нормалью по отношению к $\Omega_1 $ тогда простым следствием леммы $1.2$ является симметричность и положительная определенность $S$.
  290. \newpage
  291. \section{Метод без перекрытия}
  292. \setcounter{equation}{0}
  293. \subsection{Описание метода}
  294. В литературе методы этого типа называют еще методами {\it подструктур}, или методами {\it дополнений Шура}. Такие методы используются уже несколько десятилетий, особенно специалистами по строительной механике, для разбиения больших задач на части, могущие быть размещенными в памяти компьютера.
  295.  
  296. Для простоты, проиллюстрируем данный тип методов с помощью обычного уравнения Пуассона с граничными условиями Дирихле, дискретизованного посредством 5-точечного шаблона. Однако уравнение будем рассматривать не на квадрате, а на {\it L--образной области}. Эту область можно разбить на две: малый квадрат и большой с вдвое большей стороной, причем малый квадрат примыкает к нижней части правой стороны большого квадрата. Построим метод, использующий нашу способность быстро решать задачи на квадратах.
  297.  
  298. Для грубой сетки, показанной на рисунке, каждый внутренний узел $L$--образной области помечен номером (стоящим слева сверху от узла).
  299. Нумерация ведется специальным образом:
  300. вначале пронумеруем внутренние узлы каждой из подобластей и только потом узлы
  301. на их общей границе.\\
  302. %\begin{figure}
  303. \includegraphics[width=0.7\linewidth]{lobl.png}\\
  304. %\end{figure}
  305. рис1.\\
  306.  
  307. %\begin{figure}
  308. %\begin{center}
  309. %\includegraphics[width=0.7\linewidth]{lobl.png}
  310. %\end{center}
  311. %\end{figure}
  312.  
  313. Получаем следующую матрицу:
  314.  
  315.  %\begin{figure}
  316. %\begin{center}
  317. \includegraphics[width=0.5\linewidth]{A.png}\par
  318. %\end{center}
  319. %\end{figure}
  320.  Одним из важнейших свойств этой матрицы является то, что $A_{12}=0$, поскольку между внутренними узлами двух подобластей нет прямого сцепления. Сцепление осуществляется лишь через занумерованные последними узлы общей границы подобластей (узлы 30 и 31). Таким образом, блок $A_{13}$ соответствует сцеплению между границей и малым квадратом, а блок $A_{23}$ — сцеплению между границей и большим квадратом.
  321.  
  322. Чтобы понять, как извлечь выгоду из специальной структуры матрицы $A$ при решении системы $Ax=b$, запишем блочное $LDU$-разложение этой матрицы в виде
  323. \begin{align*}
  324. A=\begin{bmatrix}
  325. I & 0 & 0 \\ 0 & I & 0 \\ A_{13}^T A_{11}^{-1} &  A_{23}^T A_{22}^{-1} & I
  326. \end{bmatrix}\cdot
  327. \begin{bmatrix}
  328. I&0&0\\0&I&0\\0&0&S
  329. \end{bmatrix}\cdot
  330. \begin{bmatrix}
  331. A_{11}&0&A_{13}\\0&A_{22}&A_{23}\\0&0&I
  332. \end{bmatrix},
  333. \end{align*}
  334. где матрица
  335. \begin{eqnarray}
  336. S=A_{33}-A_{13}^TA_{11}^{-1}A_{13}-A_{23}^{T}A_{23}^{-1}A_{23}
  337. \label{2-1}
  338. \end{eqnarray}
  339. называется {\it дополнением Шура} ведущей главной подматрицы, содержащей блоки $A_{11}$ и $A_{22}$. Следовательно, можно написать
  340. \begin{align*}
  341. A^{-1}=\begin{bmatrix}
  342. A_{11}^{-1}&0&-A_{11}^{-1}A_{13}\\0&A_{22}^{-1}&-A_{22}^{-1}A_{23}\\0&0&I
  343. \end{bmatrix}\cdot
  344. \begin{bmatrix}
  345. I&0&0\\0&I&0\\0&0&S^{-1}
  346. \end{bmatrix}\cdot
  347. \begin{bmatrix}
  348. I & 0 & 0 \\ 0 & I & 0 \\ -A_{13}^T A_{11}^{-1} &  -A_{23}^T A_{22}^{-1} & I
  349. \end{bmatrix}
  350. \end{align*}
  351. Таким образом, чтобы умножить вектор на $A^{-1}$, нам нужно умножать на блочные элементы этой факторизованной формы, а именно на блоки $A_{13}$ и $A_{23}$ (и транспонированные к ним), $A_{11}^{-1}$, $A_{22}^{-1}$ и $S^{-1}$. Умножение на $A_{13}$ и $A_{23}$ выгоднее, так как эти блоки очень разрежены. Умножение на  $A_{11}^{-1}$ и $A_{22}^{-1}$ тоже выгоднее: ведь подобласти были выбраны так, чтобы были применимы алгоритм $FFT$, метод сопряженных градиентов, многосеточный метод и некоторые другие быстрые методы. Остается объяснить, как происходит умножение на матрицу $S^{-1}$.
  352.  
  353. Поскольку на границе гораздо меньше узлов, чем в подобластях, порядок блоков $A_{33}$ и $S$ много меньше порядка блоков $A_{11}$ и $A_{22}$; этот эффект еще более выражен при сгущении сетки. Как и $A$, блок $S$ симметричен и положительно определен, но является (в данном случае) плотным. Чтобы вычислить его в явном виде, потребовалось бы решить по одной задаче для каждой подобласти на каждый из общих граничных узлов (что соответствует произведениям $A_{11}^{-1}A_{13}$ и $A_{22}^{-1}A_{23}$ в формуле (\ref{2-1})). Это, разумеется, можно сделать, после чего можно было бы факторизовать $S$ посредством итерационного метода, а затем решить систему с этой матрицей. Но такой способ действий был бы чересчур затратным, куда сложнее, чем простое умножение вектора на матрицу $S$, для чего, согласно (\ref{2-1}), понадобится лишь одно решение каждой задачи на подобласти. Это обстоятельство делает привлекательным применение итерационных методов,  поскольку в них матрица $S$ используется лишь в произведениях с векторами. Число матрично-векторных умножений в методах зависит от числа обусловленности матрицы $S$. Оказывается (и в этом состоит особая привлекательность метода декомпозиции области!), что $S$ гораздо лучше обусловлена, чем исходная матрица $A$.
  354.  
  355. В более общем случае имеется $k>2$ подобластей, разделенных границами (см. рис. 2, где подобласти разделены жирными линиями). Если пронумеровать последовательными числами узлы каждой подобласти и лишь затем граничные узлы, то получим матрицу вида\\[0.4cm]
  356. \includegraphics[width=0.5\linewidth]{A1.png}\\
  357. рис.2\\ \par
  358. Снова эту матрицу можно факторизовать, факторизуя независимо друг от друга диагональные блоки $A_{ii}$, а затем формируя дополнение Шура $S=A_{k+1,k+1}-\sum\limits_{i=1}^k A_{i,k+1}^T A_{i,i}^{-1} A_{i,k+1}$.
  359.  
  360. В том случае, если имеется более чем один граничный сегмент, $S$ обладает структурой, которую можно использовать для предобуславливания. Так, если внутренние узлы каждого граничного сегмента занумерованы прежде, чем узлы на пересечении таких сегментов, то возникает блочная структура, схожая со структурой матрицы $A$. Диагональные блоки в $S$ устроены сложно, но их можно аппроксимировать матрицей $T_N^{1/2}$. Мы можем резюмировать достижения в теории метода следующим образом: при подходящем выборе предобуславливателя для матрицы $S$ можно добиться, чтобы число шагов алгоритма не зависело от числа $N$ граничных узлов.
  361.  
  362. Недостаток этого метода состоит в том, чтобы построить матрицу $S$, нам нужно решить столько количество задач сколько узлов на интерфейсе и потом решить задачу с полной матрицей размерностью интерфейса это выходит очень затратно, но можно не посредственно применять итерационный метод поскольку оператор $S$ является симметричным и к задаче  $Su=f$ может быть применен метод сопряженных градиентов.
  363.  
  364. \subsection{Реализация прямого метода}
  365. \begin{enumerate}
  366. \item Разбиваем область на большой и малый квадрат.
  367. \item Решаем задачу на подобластях.
  368. \item Вычисляем невязку на линии сцепления областей.
  369. \item Вычисляем дополнение Шура $S$ следующим образом:
  370. \begin{enumerate}
  371. \item Решаем задачу на большом квадрате с правой частью, в узлах которой стоят нули
  372. и только в одном узле - единица.Таких задач будет $N$. В результате получаем $N$
  373. ($N$- число точек на линии сцепления) столбцов матрицы $A^T_{13} A^{-1}_{11} A_{13}$
  374. \item Аналогично для малого квадрата получаем матрицу $A^T_{23} A^{-1}_{22} A_{23}$
  375. \item Вычисляем $S = A_{33} - A^T_{13} A^{-1}_{11} A_{13} -A^T_{23} A^{-1}_{22} A_{23}$
  376. \end{enumerate}
  377. \item Решаем методом Гаусса систему $SU = F$ --- решение на линии сцепления
  378. \item С решением на линии сцепления решаем снова задачу на большом и малом квадрате.
  379. \item "Собираем" решение на всей области.
  380. \end{enumerate}
  381.  
  382. \newpage
  383. \section{Метод сопряженных градиентов.}
  384. \setcounter{equation}{0}
  385.  
  386. \subsection{Описание метода сопряженных градиентов.}
  387.  
  388.  
  389. Системы уравнений с положительно определенной матрицей, возникающие при
  390. дискретизации эллиптических краевых задач, чаще всего
  391. имеют большое число обусловленности. При решении таких задач
  392. простейшими итерационными методами заданная точность достигается
  393. за большое количество итераций. Примером таких методов является
  394. метод скорейшего спуска, метод верхней релаксации и др.  Для увеличения
  395. скорости сходимости в таких задачах используют метод сопряженных
  396. градиентов. Этот метод является одним из эффективных при решении
  397. систем  уравнений.
  398.  
  399. Метод сопряженных градиентов был создан в 1952 году Штифелем и
  400. Гестеном, но начал использоваться лишь в 1971 году, когда были разработаны
  401. простейшие методы предобуславливания.
  402.  
  403. Для решения систем уравнений, возникающих при дискретизации двух- и трехмерных
  404. задач второго порядка, этот метод является более эффективным, чем метод
  405. исключения неизвестных Гаусса, не говоря уже о существенно боле низкой
  406. потребности в  памяти.
  407.  
  408. Рассматривая итерационные методы для решения систем уравнений с
  409. положительно определенной матрицей $A,$  используют тот факт, что
  410. решением уравнения $Au=f$ является минимум функции
  411. $$
  412.   G(u)=\dfrac{1}{2}(u,Au)-(f,u).
  413. $$
  415. Возможностью увеличить скорость сходимости является применение в решении
  416. задач метода сопряженных градиентов. Основополагающая мысль его  состоит
  417. в том, чтобы направления, возникающие в процессе итераций, обратились
  418. в ортогональные в метрике, определяемой формулой  $||x||_A=(Ax,x).$
  420. Существуют различные реализации метода сопряженных градиентов.
  421. Приведем алгоритм реализации метода.
  422. Пусть $x_0\in R^n- $начальное приближение. Запишем алгоритм
  423. метода сопряженных векторов.
  425. \subsection{Реализация метода сопряженных градиентов.}
  428. Алгоритм метода сопряженных градиентов:
  430. 1. По заданному $x_0$
  432. 2. Вычисляется невязка $r_0=f-Ax_0$ , вектор $p_0$ полагается равным
  433. $r_0$: $p_0=r_0$
  435. для $m=0,1,2,\ldots$ если $r_m \neq 0$
  437. 3. вычисляется вектор
  438. $a_m=Ap_m$
  440. 4. Находится
  441. $$\lambda_{opt}(x_m,p_m)=\displaystyle\frac{(r_m,p_m)}{(a_m,p_m)}$$
  443. 5. Вычисляется следующее приближение
  444. $$x_{m+1}=x_m+\lambda_{opt}(x_m,p_m)p_m$$
  446. 6. Вычисляется вектор невязки
  448. $$r_{m+1}=r_m-\lambda_{opt}(x_m,p_m)a_m$$
  450. 7.  Находится вектор
  451. $$p_{m+1}=r_{m+1}-\displaystyle\frac{(r_{m+1},a_m)}{(a_m,p_m)}p_m$$
  453. Вместо 4) и 7) можно применять следующие формулы:
  455. 4а.$$\lambda_{opt}(x_m,p_m)=\displaystyle\frac{(r_m,r_m)}{(a_m,p_m)}$$
  458. 7a.$$p_{m+1}=r_{m+1}+\displaystyle\frac{(r_{m+1},r_{m+1})}{(r_m,r_m)}p_m$$
  461. \begin{center}
  462. {\bf  Теорема 3.1} Для оценки ошибки метода сопряженных градиентов
  463. \end{center}
  464. справедливо следующее утверждение: Пусть $m-$ номер итерации,
  465. $k-$ число обусловленности матрицы, т.е $k=\dfrac{b}{a},$ где
  466. $a,b-$ соответственно наименьшее и наибольшее собственные значения
  467. этой матрицы, $T_m(x)-$ полином Чебышева первого рода $T_m(x)=\dfrac{1}{2}[(x+\sqrt{x^2-1})^m+(x-\sqrt{x^2-1})^m],$ $m=0,1,\dots$
  468. Тогда при любом $x_0\in R^n,$ имеет место выражение
  469. \begin{eqnarray}
  470. \label{2.15}
  471. ||x_m-x^*||_A\le \dfrac{1}{T_m(\dfrac{k+1}{k-1})}||x_0-x^*||_A \le
  472.    2\dfrac{(\sqrt{k}-1)^m}{(\sqrt{k}+1)^m}||x_0-x^*||_A.
  473. \end{eqnarray}
  475. При реализации метода сопряженных градиентов обычно получается, что
  476. скорость сходимости лучше, чем приведенная теоретическая оценка.
  477. Отметим, что на практике наблюдают неравномерное уменьшение погрешности
  478. в ходе итераций.
  479. После значительного уменьшения погрешности в первых шагах часто
  480. встречается фаза, когда ошибка уменьшается медленно. Затем опять
  481. происходит быстрое уменьшение.
  483. \newpage
  484. \section{Метод сопряженных градиентов с предобуславливателем.}
  485. \setcounter{equation}{0}
  487. Метод оказывается еще более эффективным если он применяется с
  488. предобуславливателем. В качестве предобуславливателя рассматривается
  489. матрица $W,$  легко обратимая и положительно определенная. Она
  490. является приближением для матрицы $A.$ Рассмотрим выражение\\
  491. $x_1=x_0+\tau W^{-1}r_0, u_0\in R^n, r_0=f-Ax_0.$ Пусть $W=A,$
  492. тогда решение будет получено уже на первом шаге. Поэтому
  493. можно предположить,
  494. что каждое, даже грубое приближение $W$ для матрицы $A$ приводит
  495. быстрее к заданной точности, нежели тривиальный выбор $W=I.$
  498. \subsection{ Алгоритм метода сопряженных градиентов с предобуславливателем $W$:}
  501. 1. По заданному $x_0$ вычисляются вектор невязки $r_0=f-Ax_0,$
  502. поправка $p_0=W^{-1}r_0$ и величина $\varrho_0=(p_0,r_0)$
  504. для $m=0,1,2,\ldots$
  506. 2. Вычисляется вектор $a_m=Ap_m$
  508. 3. Находится
  509. $$\lambda_{opt}(x_m,p_m)=\displaystyle\frac{\varrho_m}{(a_m,p_m)}$$
  511. 4. Вычисляется следующее приближение
  512. $$x_{m+1}=x_m+\lambda_{opt}(x_m,p_m)p_m$$
  514. 5. Вычисляется вектор невязки
  516. $$r_{m+1}=r_m-\lambda_{opt}(x_m,p_m)a_m$$
  518. 6.Находятся новая поправка $q_{m+1}=W^{-1}r_{m+1}$ и величина\\
  519. $\varrho_{m+1}=(q_{m+1},r_{m+1})$
  521. 7.Находится вектор
  522. $$p_{m+1}=q_{m+1}+\displaystyle\frac{\varrho_{m+1}}{\varrho_m}p_m$$
  524. Для метода сопряженных градиентов существует теорема, аналогичная
  525. теореме 3.1
  527. {\bf Теорема 4.1} Можно утверждать, что при любом $x_0\in R^n,$ выполняется неравенство
  528. \begin{eqnarray}
  529. \label{4-1}
  530. ||x_m-x^*||_A\le \dfrac{1}{T_m\big(\dfrac{k+1}{k-1}\big)}||x_0-x^*||_A \le
  531.    2\dfrac{(\sqrt{k}-1)^m}{(\sqrt{k}+1)^m}||x_0-x^*||_A.
  532. \end{eqnarray}
  533. Однако в отличие от предыдущей теоремы, число $k$ является отношением
  534. наибольшего и наименьшего собственных значений обобщенной задачи
  535. на собственные значения $Ax=\lambda Wu,$ где $W-$ предобуславливатель.
  538. \subsection{ Предобуславливатель при помощи метода симметричной верхней релаксации.}
  541. Простой, но эффективный предобуславливатель получается из метода симметричной
  542. верхней релаксации. В этом случае вектор $q=W^{-1}r$ вычисляется по
  543. следующему алгоритму: начиная с некоторого начального приближения $u^0$
  544. вычисляются приближения $u^1, u^2,\dots$ по следующим формулам:
  546. \begin{eqnarray*}
  547.    u^{m+\frac{1}{2}}_{ij}&=&(1-\omega)u^{m}_{ij}-
  548.                     \omega(k_x(u^{m+\frac{1}{2}}_{i-1,j}+u^{m}_{i+1,j})
  549.                     \\
  550.                     &+&
  551.                            k_y(u^{m+\frac{1}{2}}_{i,j-1}+u^{m}_{i,j+1})+f_{i,j})/K,
  552. \end{eqnarray*}
  553. \begin{eqnarray*}
  554.    u^{m+1}_{ij}&=&(1-\omega)u^{m}_{ij}-
  555.                     \omega(k_x(u^{m+\frac{1}{2}}_{i-1,j}+u^{m+1}_{i+1,j})
  556.                     \\
  557.                     &+&
  558.                            k_y(u^{m+\frac{1}{2}}_{i,j-1}+u^{m+1}_{i,j+1})+
  559.                           f_{i,j})/K,
  560. \end{eqnarray*}
  562. где $\omega-$ параметр метода верхней релаксации.
  564. Чтобы реализовать первый процесс, начинаем вычисления с элемента $u_{111}$.
  565. Далее в циклах по $i=1..(N_x-1), j=1..(N_y-1)$
  566. (используем однородность
  567. граничных условий ) вычисляем последовательно элементы $u_{ij},$
  568. причем используем элементы $u_{ij},$ уже вычисленные в этой итерации
  569. ранее. Аналогично, для реализации второго процесса вычисления начинаются
  570. с элемента $\displaystyle u_{N_xN_y}$ и циклы идут в обратном направлении:
  571. $i=(N_x-1)..1, j=(N_y-1)..1$
  573. Для метода сопряженных градиентов в качестве предобуславливателя
  574. используется одна итерация метода симметричной верхней релаксации,
  575. т.е. вектор $q=W^{-1}r$ вычисляется по следующему правилу:  полагаем
  576. $u_0=0$ и вычисляем
  577. \begin{eqnarray*}
  578. u^{m+\frac{1}{2}}_{ij}=(1-\omega)u^{m}_{ij}- \omega(u^{m}_{i+1,j}+
  579.                          u^{m}_{i,j+1}+u^{m}_{i,j}+r_{i,j})/K.
  580. \end{eqnarray*}
  581. Затем уже вычисляется вектор
  582. \begin{eqnarray*}
  583.    W&=&(1-\omega)u^{m}_{ij}-
  584.          \omega(k_x(u^{m+\frac{1}{2}}_{i-1,j}+u^{m+1}_{i+1,j})
  585.          \\
  586.          &+&
  587.                 k_y(u^{m+\frac{1}{2}}_{i,j-1}+u^{m+1}_{i,j+1})
  588.                 +r_{i,j})/K.
  589. \end{eqnarray*}
  591. Можно показать, что оператор перехода будет симметричен. Поэтому
  592. использование метода сопряженных градиентов оправдано. Что же касается
  593. выбора параметра $\omega,$ то известно, что при $0<\omega<2,$ то метод
  594. верхней релаксации сходится.
  595. На практике было выяснено, что скорость сходимости метода верхней релаксации
  596. будет наибольшей в том случае, когда $\omega$ колеблется
  597. между 1.2 и 1.8.
  598. \newpage
  599. \section{Метод  Дирихле-Нейман}
  600. Основной алгоритм Дирихле-Неймана состоит из двух шагов, соответствующих этим двум подобластям $\Omega_i,\:\: i=1,2$. Учитывая начальное приближение $u^0_{\Gamma}$, мы сначала решаем задачу Дирихле в $\Omega_1$ с данными Дирихле $u^0_{\Gamma}$ на $\Gamma$, а затем смешанную задача Неймана-Дирихле , где $\Omega_2$ с условием Неймана на $\Gamma$ определяется решением в $\Omega_1$, полученного на предыдущем шаге, и с условиями Дирихле на остальной $\partial \Omega_2$. Новая итерация $u^1_{\Gamma}$ выбрана в качестве одного из шагов решения для $\Omega_2$, или, более обобщено, в виде линейной комбинации этого шага и $u^0_{\Gamma}$, используя надлежащим образом выбранный релаксации параметра $\theta$. С точки зрения дифференциальных операторов, мы можем написать, что $n\ge 0$:
  601. \begin{eqnarray}
  602. \begin{split}
  603. &(D)\begin{cases}
  604. -\triangle  u_1^{n+1/2}  &= \:\: f \:\: \mbox{в} \:\: \Omega_1\\
  605. \qquad u_1^{n+1/2} &= \:\:0 \:\: \mbox{на} \:\: \partial \Omega_1 \setminus \Gamma \\
  606. \qquad u_1^{n+1/2} &= \:\: u^n_{\Gamma} \:\:\mbox{на} \:\: \Gamma
  607. \end{cases}\\[0.5cm]
  608. &(N)\begin{cases}
  609. -\triangle  u_2^{n+1}  &= \:\: f \qquad \qquad \qquad  \mbox{в} \:\:\: \Omega_2\\
  610. \qquad u_2^{n+1} &= \:\:0 \qquad \qquad \qquad  \mbox{на} \:\: \partial \Omega_2 \setminus \Gamma \\
  611. \displaystyle \qquad \frac{\partial u_2^{n+1}}{\partial n_2} &= \displaystyle\:\:- \frac{\partial u_1^{n+1/2}}{\partial n_1} \qquad \: \mbox{на} \:\: \Gamma
  612. \end{cases}
  613. \end{split}
  614. \label{D-N1}
  615. \end{eqnarray}
  616. где  $\theta \in (0,\theta_{max})$. Используя наш приближение для производных по нормали, (\ref{D-N1}), мы можем получить соответствующую итерацию для дискретной задачи. Если мы определим векторы внутренних степеней свободы, как $v_1=u^{(1)}_I$ и $w_2=u^{(2)}_I$, смотри (\ref{D-N1}), то найдем
  617. \begin{eqnarray}
  618. \begin{split}
  619. &(D) \:\:\: A^{(1)}_{II} v^{n+1/2}_1 +A^{(1)}_{I\Gamma} u^n_{\Gamma}=f^{(1)}_I,\\[0.4cm]
  620. &(N) \:
  621. \begin{pmatrix}
  622. A^{(2)}_{II} & A^{(2)}_{I\Gamma} \\
  623. A^{(2)}_{\Gamma I} & A^{(2)}_{\Gamma \Gamma}
  624. \end{pmatrix}
  625. \begin{pmatrix}
  626. w^{n+1}_2\\
  627. \tilde u^{n+1}_{\Gamma}
  628. \end{pmatrix} =
  629. \begin{pmatrix}
  630. f^{(2)}_I \\
  631. f^{(2)}_{\Gamma}-\lambda^{n+1/2}_{\Gamma}
  632. \end{pmatrix}, \\[0.4cm]
  633. &u^{n+1}_{\Gamma}=\theta \tilde u^{n+1}_{\Gamma}+(1-\theta)u^n_{\Gamma},\\
  634. \end{split}
  635. \label{D-N2}
  636. \end{eqnarray}
  637. где
  638. \begin{align*}
  639. \lambda^{n+1/2}_{\Gamma}=A^{(1)}_{\Gamma I} v^{n+1/2}_1 + A^{(1)}_{\Gamma \Gamma} u^n_{\Gamma} - f^{(1)}_{\Gamma}.
  640. \end{align*}
  641. Ясно, что (\ref{D-N2}) возникает из разбиения исходной системы (\ref{D-N2}) и, следовательно, обеспечивает последовательный итерационный метод для ее решения, т. е. предел любой сходящейся последовательности удовлетворит правильный набор уравнений.\par
  642. Затем мы исключаем $v^{n+1/2}_1$ из (\ref{D-N2}) и находим
  643. \begin{align*}
  644. \lambda^{n+1/2}_{\Gamma}=-(g^{(1)}_{\Gamma} - S^{(1)} u^n_{\Gamma}).
  645. \end{align*}
  646. Используем затем блок разложение локальной матрицы $A^{(2)}$ и ликвидацию $w^{n+1}_2$ из (\ref{D-N2}) получаем следующее уравнение:
  647. \begin{align*}
  648. S^{(2)}(u^{n+1}_{\Gamma} - u^n_{\Gamma})=\theta (g_{\Gamma} - Su^n_{\Gamma}),
  649. \end{align*}
  650. которая показывает, что алгоритм Дирихле-Неймана является предобусловленная итерация  Ричардсона для дополнительной системы  Шура, с предобуславливателем  $S^{(2)^{-1}}$. Предобусловленный оператор
  651. \begin{align*}
  652. S^{(2)^{-1}} S=I+S^{(2)^{-1}} S^{(1)},
  653. \end{align*}
  654. применение которого к вектору возводит в степень решение задачи Дирихле (умножение на $S^{(1)}$), и умножение на $S^{(2)^{-1}}$, который соответствует решению проблемы с условиями Неймана на $\Gamma$ и в остальных $\partial \Omega_2$ условиях Дирихле. \par
  655. Отметим, что спектральная эквивалентность между $S^{(1)}$ и $S^{(2)}$и, следовательно, равномерная оценка для числа $S^{(2)^{-1}}S$, обеспечен существованием устойчивой, дискретной гармоничности, конечного расширения элемента $H_i u_{\Gamma}$ от интерфейса $\Gamma$ в подобласти  $\Omega_i$.
  656. Здесь и в дальнейшем, число обусловленности  выдержанного оператор представляет собой отношение наибольшего и наименьшего собственных значений симметричной обобщенной задачи на собственные значения, определенного оператора и его предобусловливателя. Мы используем следующее определение:\\
  657. {\bf Определение(Оптимальность)}. {\it Итерационный метод решения линейной системы называется оптимальным, если его скорость сходимости к точному решению не зависит от размера системы}
  658. \newpage
  659. \section{Метод Нейман-Нейман}
  660. Основной алгоритм Неймана-Неймана может быть описан следующим образом: мы начинаем с исходного приближения $u^0_{\Gamma}$. Шаг алгоритма Неймана-Неймана заключается в решении задач Дирихле  на каждой $\Omega_i$ с данными $u^0_{\Gamma}$ на $\Gamma$, и затем задачу на каждой подобласти, с условиями Неймана, на $\Gamma$, выбранном в качестве различия производных по нормали решений этих двух задач Дирихле. Значения на $\Gamma$ из решений задач Неймана тогда используются для исправления начальной $u^0_{\Gamma}$ и нахождения  новой итерации $u^1_{\Gamma}$. С точки зрения сравнения разных операторов, мы можем написать для $n\ge 0$:
  661. \begin{eqnarray}
  662. \begin{split}
  663. &(D_i)\begin{cases}
  664. \left.
  665. \begin{aligned}
  666. -\triangle  u_i^{n+1/2}  &= \:\: f \qquad \qquad \:\:\mbox{в} \:\: \Omega_i,\\
  667. \qquad u_i^{n+1/2} &= \:\:0 \qquad \qquad \:\:\mbox{на}  \:\: \partial \Omega_i\setminus \Gamma, \\
  668. \qquad u_i^{n+1/2} &= \:\: u^n_{\Gamma} \qquad \qquad \mbox{на}\:\:  \Gamma,
  669. \end{aligned}
  670. \right\},\:\:\: i=1,2,
  671. \end{cases}\\[0.6cm]
  672. &(N_i)\begin{cases}
  673. \left.
  674. \begin{aligned}
  675. -\triangle  \psi_i^{n+1}  &=0 \hspace{5cm}  \mbox{в} \:\: \Omega_i,\\
  676. \qquad \psi_i^{n+1} &=0 \hspace{5cm} \mbox{на} \:\: \partial \Omega_i \setminus \Gamma, \\
  677.  \frac{\partial \psi_i^{n+1}}{\partial n_i} &=  \frac{\partial u_1^{n+1/2}}{\partial n_1}+\frac{\partial u_2^{\!n+1/2}}{\partial n_2} \hspace{1.3cm} \mbox{на} \:\: \Gamma,
  678. \end{aligned}
  679. \right\},\:\:\: i=1,2,
  680. \end{cases}\\[0.5cm]
  681. &u^{n+1}_{\Gamma}=u^n_{\Gamma}-\theta(\psi^{n+1}_1 + \psi^{n+1}_2)\quad \mbox{на} \:\: \Gamma
  682. \end{split}
  683. \label{NN1}
  684. \end{eqnarray}
  685. с подходящим $\theta \in (0,\theta_{max}).$ Используя наше приближение для нормальных производных, можно получить итерации для дискретной задачи. Если мы определим векторы внутренних степеней свободы, как $v_i=u^{(i)}_I$ и $w_i=\psi^{(i)}$, мы находим
  686. \begin{eqnarray}
  687. \begin{split}
  688. &(D_i)\: A^{(i)}_{II} v^{n+1/2}_i + A^{(i)}_{I\Gamma} u^n_{\Gamma}=f^{(i)}_I,\quad i=1,2,\\
  689. &(N_i)\:\: \begin{pmatrix}
  690. A^{(i)}_{II} & A^{(i)} \\
  691. A^{(i)}_{\Gamma I} & A^{(i)}_{\Gamma \Gamma} \end{pmatrix} \begin{pmatrix}
  692. w^{n+1}_i \\ \eta^{n+1}_i \end{pmatrix}=\begin{pmatrix} 0\\r_{\Gamma} \end{pmatrix},\quad i=1,2, \\
  693. &u^{n+1}_{\Gamma}=u^n_{\Gamma}-\theta(\eta^{n+1}_1 + \eta^{n+1}_2),
  694. \end{split}
  695. \label{NN2}
  696. \end{eqnarray}
  698. где остаточный $r_{\Gamma}$ определяется как
  700. \begin{align*}
  701. \begin{split}
  702. r_{\Gamma}=(A^{(1)}_{\Gamma I} v^{n+1/2}_1 + A^{(1)}_{\Gamma \Gamma} u^n_{\Gamma} - f^{(1)}_{\Gamma})\\
  703. +(A^{(2)}_{\Gamma I} v^{n+1/2}_2 + A^{(2)}_{\Gamma \Gamma} u^n_{\Gamma} - f^{(2)}_{\Gamma})
  704. \end{split}
  705. \end{align*}
  706. Затем мы устраняем $v^{n+1/2}_i$ и $w^{n+1}_i$ из (\ref{NN2}). Проблемы $(D_i)$ дают
  707. \begin{eqnarray}
  708. r_{\Gamma}=-(g_{\Gamma}-Su^n_{\Gamma}),
  709. \label{NN3}
  710. \end{eqnarray}
  711. который показывает, что разница $r_{\Gamma}$ местных потоков равна разнице между  остаточными  дополнительной системы  Шура. Использование блок-разложение местной матрицы $A^{(i)}$, проблем $(N_i)$, дает то,
  712. \begin{align*}
  713. \eta^{n+1}_i=S^{(i)-1} r_{\Gamma} = -S^{(i)-1}(g_{\Gamma}-Su^n_{\Gamma},
  714. \end{align*}
  715. следовательно, мы находим
  716. \begin{align*}
  717. u^{n+1}_{\Gamma}-u^n_{\Gamma}=\theta(S^{(1)^{-1}} +S^{(2)^{-1}})(g_{\Gamma}-Su^n_{\Gamma}),
  718. \end{align*}
  719. который показывает, что алгоритм Неймана-Неймана также предобусловленная итерация Ричардсона для дополнительной системы  Шура, с предобусловливателем $S^{(1)^{-1}} +S^{(2)^{-1}}$.Предобусловленная матрица
  720. \begin{eqnarray}
  721. FS=(S^{(1)^{-1}} +S^{(2)^{-1}})S=(S^{(1)^{-1}} +S^{(2)^{-1}})(S^{(1)}+S^{(2)}),
  722. \label{NN4}
  723. \end{eqnarray}
  724. применение которого к вектору возводит в степень решение двух Задач Дирихле и двух задач условием Неймана на $\Gamma$.\par
  725. Оптимальность этого метода легко следует из результата  алгоритма Дирихле-Неймана использовании спектральной теоремы отображения; предобусловленная матрица в (\ref{NN4}) можно записать в виде
  726. $$ S^{(2)^{-1}}S^{(1)}+2I+(S^{(2)^{-1}}S^{(1)})^{-1},$$ где собственные значения $S^{(2)^{-1}}S^{(1)}$ равномерно ограничены сверху и снизу.\par
  727. Отметим, что, учитывая положительные значения $\delta^{\dag}_1$ и $\delta^{\dag}_2$ c
  728. \begin{align*}
  729. \delta^{\dag}_1+\delta^{\dag}_2=1,
  730. \end{align*}
  731. остаточную $r_{\Gamma}$ на правой стороне задач Неймана в (\ref{NN2}) можно заменить на $\delta^{\dag}_1 r_{\Gamma}$ и $\delta^{\dag}_2 r_{\Gamma}$ в  $\Omega_1$ и $\Omega_2$, соответственно. Аналогично, при нахождении новой итерации $u^{n+1}_{\Gamma} $ сумма этих двух исправлений $\eta^{n+1}_1$ и $\eta^{n+1}_2$ можно заменить на средне взвешенное значение:
  732. \begin{align*}
  733. u^{n+1}_{\Gamma}=u^n_{\Gamma}-\theta(\delta^{\dag}_1 \eta^{n+1}_1 + \delta^{\dag}_2 \eta^{n+1}_2).
  734. \end{align*}
  735. Это приводит к предобуславливателю
  736. \begin{align*}
  737. D^{(1)}S^{(1)^{-1}}D^{(1)}+D^{(2)}S^{(2)^{-1}}D^{(2)},
  738. \end{align*}
  740. где $D^{(i)}$ представляет собой диагональную матрицу, диагональные элементы которой равны $\delta^{\dag}_i$. Вычисление матрицы $D^{(i)}$ обычно используется на практике для того, чтобы улучшить сходимость алгоритма Неймана-Неймана для подобластей с точками  пересечения и, в частности, для задач с большими изменениями в коэффициентах.\par
  741. Обобщения алгоритмов Дирихле-Неймана и Неймана-Неймана возможно, с помощью более общих условий Робина. Отметим, что использование более общих условиях интерфейса часто требуется для некоторых несимметричных или неопределенных задач.
  743. \newpage
  744. \section{Метод Дирихле-Дирихле}
  745. Вернемся к разбиению $\Omega$ на две подобласти $\Omega_1,\Omega_2$ Формулировка двух подзадач с условиями сшивки (\ref{1-1}-\ref{1-2}) допускает следующую интегральную постановку. Обозначим $\lambda=\frac{\partial u}{\partial n}|_{\Gamma}$ и найдем такие $\lambda \in \Lambda',$ $u_i \in V_i,\: i=1,2,$ что
  746. \begin{gather}
  747. \int\limits_{\Omega_1} \nabla u_1 \cdot \nabla v_1\: dx+\int\limits_{\Gamma} \lambda v_1 \: ds = \int\limits_{\Omega_1} f v_1\:dx\:\:\:\:\forall v_1 \in V_1, \label{5-1}\\
  748. \int\limits_{\Omega_2} \nabla u_2 \cdot \nabla v_2\: dx-\int\limits_{\Gamma} \lambda v_2 \: ds = \int\limits_{\Omega_2} f v_2\:dx\:\:\:\:\forall v_2 \in V_2,\label{5-2}\\
  749. \int\limits_{\Gamma} (u_1 - u_2)\mu ds = 0\:\:\: \mu \in \Lambda'. \label{5-3}
  750. \end{gather}
  751. Одним из преимуществ данной постановки является то, что она применима к случаю триангуляций, не стыкующихся на интерфейсе(Две триангуляции называются нестыкующимися, если их следы на интерфейсе не совпадают), поскольку непрерывность функции на Г здесь понимается лишь в слабом смысле, т.е. в смысле равенства (\ref{5-3}). Мы ограничимся случаем стыкующихся триангуляций и заменим пространство $V_i$ на стандартное конечно-элементное подпространство $U^h$, а $\Lambda'$~--- на дискретное пространство функций Дирака $\Lambda'^h$, заданных во внутренних узлах $x_k$ интерфейса $\Gamma$:
  752. \begin{align*}
  753. \Lambda'^h=\{\delta(x_k)\}.
  754. \end{align*}
  755. Конечно-элементная формулировка заключается в поиске $\lambda^h \in \lambda'^h,\quad$ $u_i^h \in U_i^h$ таких, что
  756. %\begin{eqnarray}
  757. \begin{gather}
  758. \int\limits_{\Omega_1} \nabla u_1^h \cdot \nabla v_1^h\: dx+\int\limits_{\Gamma} \lambda^h v_1^h \: ds = \int\limits_{\Omega_1} f v_1^h\:dx\:\:\:\:\forall v_1^h \in U_1^h,\label{5-4}\\
  759. \int\limits_{\Omega_2} \nabla u_2^h \cdot \nabla v_2^h\: dx-\int\limits_{\Gamma} \lambda^h v_2^h \: ds = \int\limits_{\Omega_2} f v_2^h\:dx\:\:\:\:\forall v_2^h \in U_2^h,\label{5-5}\\
  760. \int\limits_{\Gamma} (u_1^h - u_2^h)\mu^h ds = 0\:\:\: \mu^h \in \Lambda'^h.\label{5-6}
  761. \end{gather}
  762. %\end{eqnarray}
  763. В частном случае стыкующихся триангуляций уравнение (\ref{5-6}) сводится к требованию равенства конечно-элементных функций $u_1^h,u_2^h$ в узлах интерфейса:
  764. \begin{align*}
  765. u_1^h(x_k) - u_2^h(x_k)=0
  766. \end{align*}
  767. Отметим, что (\ref{5-4}-\ref{5-6}) является неконформной аппроксимацией \\ (\ref{5-1}-\ref{5-3}), поскольку пространство $\Lambda'^h$ не является подпространством $\Lambda'$. Тем не менее, можно показать, что (\ref{5-4}-\ref{5-6}) и обычная дискретизация\\ $a(u^h,v^h)=(f,v^h)\:\:\forall v^h \in U^h$ порождают одно и то же сеточное решение.\par
  768. Алгебраическая формулировка для задачи (\ref{5-4}-\ref{5-6}) выглядит следующим образом:
  769. \begin{eqnarray}
  770. \begin{pmatrix}
  771. B_1 &   0   &  C_1^T \\
  772. 0  &  B_2  & -C_2^T \\
  773. C_1 & -C_2  &    0
  774. \end{pmatrix}
  775. \begin{pmatrix}
  776. u_1 \\ u_2 \\ \lambda
  777. \end{pmatrix} =
  778. \begin{pmatrix}
  779. f_1 \\ f_2 \\ 0
  780. \end{pmatrix}
  781. \label{5-7}
  782. \end{eqnarray}
  783. где ненулевые элементы матриц $C_1$ и $C_2$~--- только единицы. Исключение неизвестных $u_1$ и $u_2$ из (\ref{5-7}) приводит к системе для вектора $\lambda$ вида
  784. \begin{eqnarray}
  785. (C_1 B_1^{-1} C_1^T + C_2 B_2^{-1} C_2^T)\lambda = C_1 B_1^{-1}f_1 - C_2 B_2^{-1}f_2
  786. \label{5-8}
  787. \end{eqnarray}
  788. Таким образом, умножение вектора на $S_D\equiv C_1 B_1^{-1} C_1^T + C_2 B_2^{-1} C_2^T$ требует решения двух краевых задач с условием Неймана на интерфейсе $(B_i^{-1})$. Учитывая вид матриц $C_i^T\:=\:(0\:C_{i\Gamma}^T)$, перепишем матрицу $S_D$ следующим образом:
  789. \begin{align*}
  790. S_D=C_{1\Gamma}S_1^{-1}C_{1\Gamma}^T + C_{2\Gamma}S_2^{-1}C_{2\Gamma}^T
  791. \end{align*}
  792. где $S_i^{-1}$ ~--- интерфейсный блок матрицы $B_i^{-1}$, для которого верно
  793. \begin{align*}
  794. S_i = A_{\Gamma}^{(i)} - A_{\Gamma i} A_{ii}^{-1} A_{i \Gamma}, \:\: i=1,2.
  795. \end{align*}
  796. По аналогии с переобуславливателем Нейман-Нейман, выпишем переобуславливатель для $S_D$:
  797. \begin{align*}
  798. S_F=C_{1\Gamma}S_1 C_{1\Gamma}^T + C_{2\Gamma} S_2 C_{2\Gamma}^T,
  799. \end{align*}
  800. называемый переобуславливателем Дирихле-Дирихле по типу краевых задач $A_{ii}^{-1}$, которые необходимо решить при его реализации. Переобусловленная система на интерфейсе (\ref{5-8}) записывается так:
  801. \begin{align*}
  802. S_F S_D \lambda = S_F (C_1 B_1^{-1} f_1 - C_2 B_2^{-1} f_2).
  803. \end{align*}
  804. По аналогии с методом Нейман-Нейман, метод итераций Дирихле-Дирихле допускает обобщение на случай многих подобластей
  805. \newpage
  806. \section{Метод Шварца}
  807. Рассмотрим разбиение области $\Omega$ на $m$ перекрывающихся подобластей
  808. \begin{align*}
  809. \Omega=\bigcup\limits_{i=1}^m \Omega_i
  810. \end{align*}
  811. таких, что для любой $\Omega_i,\: i=1,\dots,m$ существует хотя бы одна подобласть $\Omega_i,\:j \not= i$, для которой $\Omega_i \cup \Omega_j \not= \varnothing $ (подобласть—открытое множество).\par
  812. Для решения краевой задачи (\ref{1-1}) применим метод Шварца (1869). Пусть приближение $u^n$ к решению (\ref{1-1}) $u$ на $n$-м шаге задано. Следующее приближение $u^{n+1}$ находится после применения т подшагов вида
  813. \begin{eqnarray}
  814. \begin{split}
  815. -\triangle u^{n+\frac{i}{m}} &= f \:\mbox{на} \: \Omega_i\\
  816. u^{n+\frac{i}{m}} &= u^{n+\frac{i-1}{m}}\: \mbox{на}\: \bar\Omega \setminus \Omega_i,\:\:\: i=1,\dots,m
  817. \end{split}
  818. \label{8-1}
  819. \end{eqnarray}
  820.  
  821. Метод Шварца можно сформулировать в терминах слабых постановок. Определим пространства $V_i^0=H_0^1(\Omega_i)\subset V,\:i=1,\dots,m$. Для нахождения решения обобщенной задачи (\ref{1-4}) введем поправку
  822. \begin{align*}
  823. z_i=u^{n+\frac{i}{m}} - u^{n+\frac{i-1}{m}} \:\in V_i^0
  824. \end{align*}
  825. к текущему приближению на $i$-м подшаге и применим итерации
  826. найти $z_i$:
  827. \begin{eqnarray}
  828. \begin{split}
  829. a(z_i,v) &= (f,v)-a(u^{n+\frac{i-1}{m}},v),\:\: \forall v \in V_i^0\\
  830. u^{n+\frac{i}{m}} &= u^{n+\frac{i-1}{m}} + z_i,\:\: i=1,\dots,m.
  831. \end{split}
  832. \label{8-2}
  833. \end{eqnarray}
  834.  
  835. Для обоснования сходимости метода Шварца введем в пространстве $V$ ортопроекторы $R_i: V \rightarrow V_i^0$
  836. \begin{align*}
  837. a(R_i u,v)=a(u,v) \qquad \forall v \in V_i^0
  838. \end{align*}
  839. и определим проектор $Q_i=I-R_i$, для которого
  840. \begin{align*}
  841. a(Q_i u,v)=0 \qquad \forall v \in V_i^0
  842. \end{align*}
  843. Следовательно,
  844. \begin{align*}
  845. (f,v)=a(u,v)=a(Q_i u,v) + a(R_i u,v)=a(R_i u,v)\:\: \forall v \in V_i^0,
  846. \end{align*}
  847. и из (\ref{8-2}) имеем
  848. \begin{eqnarray}
  849. a(z_i,v)=a(R_i u ,v) - a(u^{n+\frac{i-1}{m}},v)\:\:\: \forall v \in V_i^0
  850. \label{8-3}
  851. \end{eqnarray}
  852. Для произвольного $\omega \in V$ выберем $v=R_i \omega \in V_i^0$, тогда \\ $a(R_i u,V)=a(R_i u,R_i \omega)=a(R_i R_i u, \omega)=a(R_i u, \omega)$ и
  853. \begin{align*}
  854. a(R_i z_i,\omega) &= a(R_I u,\omega)-a(R_i u^{n\frac{i-1}{m}},\omega)\:\:\: \forall \omega \in V \\
  855. &z_i=R_i z_i =R_i u - R_i u^{n+\frac{i-1}{m}},
  856. \end{align*}
  857. поэтому
  858. \begin{eqnarray}
  859. u^{n+\frac{i}{m}}=u^{n+\frac{i-1}{m}}+z_i=(R_i+Q_i)u^{n+\frac{i-1}{m}} + z_i = Q_i u^{n+\frac{i-1}{m}}+R_i u.
  860. \label{8-4}
  861. \end{eqnarray}
  862. Введем ошибку на текущем подшаге
  863. \begin{align*}
  864. \varepsilon^{n+\frac{i}{m}}=u^{n+\frac{i}{m}}-u
  865. \end{align*}
  866. Из (\ref{8-4}) для ошибки получаем
  867. \begin{align*}
  868. \varepsilon^{n+\frac{i}{m}}=Q_i(u^{n+\frac{i-1}{m}} - u) + R_i u - R_i u = Q_i \varepsilon^{n+\frac{i-1}{m}}
  869. \end{align*}
  870.  
  871. Таким образом, ошибки метода Шварца связаны соотношением
  872. \begin{eqnarray}
  873. \varepsilon^{n+1}=T \varepsilon^n,\:\:\: T=Q_m Q_{m-1} \dots Q_1
  874. \label{8-5}
  875. \end{eqnarray}
  876. Сходимость метода Шварца обеспечивается оценкой нормы оператора перехода $\|T\|$. Обозначим $|[u]| =a(u,u)^{\frac{1}{2}} $.\\
  877.  
  878. {\bf Теорема 8.1.} {\em Рассмотрим следующие два утверждения:\\ $1)$ Для любого $v \in V$ существует такие $v_i \in V_i^0,\: i=1,\dots,m$, что}
  879. \begin{eqnarray}
  880. v=v_1+v_2+\dots+v_m,\label{8-6}\\
  881. |[v_i]|\le \gamma |[v]| \label{8-7}
  882. \end{eqnarray}
  883. {\em с некоторой константой} $\gamma$.
  884.  
  885. $2)${\em Для нормы оператора перехода имеет место оценка}
  886. \begin{eqnarray}
  887. \|T\| \le a<1. \label{8-8}
  888. \end{eqnarray}
  889. {\em Утверждение $1)$ влечет $2)$ с некоторой константой $q$, вообще говоря, зависящей от $m$, $\gamma$; утверждение $2)$ влечет $1) c \gamma = (1-q)^{-1}.$ \\
  890. Доказательство}. Пусть выполнено (\ref{8-6}). Тогда
  891. \begin{align*}
  892. I-T &= Q_1 + R_1 - Q_m \cdots Q_1 = R_1+(R_2 + Q_2)Q_1 - Q_m \cdots Q_1\\
  893. &= R_1+R_2 Q_1 + (R_3+Q_3) Q_2 Q_1 - Q_m \cdots Q_1 \\
  894. &= R_1 + R_2 Q_1 + R_3 Q_2 Q_1 + \cdots + R_m Q_{m-1} \cdots Q_1.
  895. \end{align*}
  896. Поскольку $\|T\|<1$, то $\|(I-T)^{-1}\|\le (1-\|T\|)^{-1}$, т.е. оператор $I-T$ имеет обратный, и
  897. \begin{align*}
  898. v &= (I-T)(I-T)^{-1} v \\
  899.  &= (R_1+ R_2 Q_1 + \cdots + R_m Q_{m-1} \cdots Q_1)(I-T)^{-1}\:\:\: v= v_1 + \cdots v_m,
  900. \end{align*}
  901. где
  902. \begin{align*}
  903. v_i=R_i Q_{i-1} \cdots Q_1(I-T)^{-1} \:\:\: v \in V_i^0,\:\:\: i=1,\dots,m
  904. \end{align*}
  905. Далее, поскольку $\|R_i\|=\|Q_i\|=1$, то
  906. \begin{align*}
  907. |[v_i]|\le \|(I-T)^{-1}\| |[v]| \le (1-\|T\|)^{-1} |[v]|=\gamma |[v]|.
  908. \end{align*}
  909. Теперь предположим, что выполнены $(6.6-6.7)$. Сперва рассмотрим оператор $R=\sum\limits_{i=1}^m R_i$. Так как все $R_i$ являются проекторами, то оператор $R$ самосопряжен в $V$ и $\|R\| \le m$. Более того,
  910. \begin{align*}
  911. |[u]| &= \sup\limits_{v \not= 0} \frac{|a(u,v)|}{|[v]|}=\sup\limits_{v \not= 0} \frac{|a(u,v_1 + \cdots + v_m)|}{|[v]|} \le \sup\limits_{v \not= 0} \sum\limits_{i=1}^m \frac{|a(u,v_i)|}{|[v]|} \\
  912.      &= \sup\limits_{v \not= 0} \sum\limits_{i=1}^m \frac{|a R_i u, v_i)|}{|[v]|} \le \sup\limits_{v \not= 0} \sum\limits_{i=1}^m \frac{|[R_i u]| |[v_i]|}{|[v]|} \le \gamma \sum\limits_{i=1}^m |[R_i u]|\\
  913.      &\le \gamma \sqrt{\,m} (\sum\limits_{i=1}^m a(R_i u,R_i u))^{\frac{1}{2}} = \gamma \sqrt{\,m}(\sum\limits_{i=1}^m a(R_i u,u))^{\frac{1}{2}} \\
  914.      &= \gamma \sqrt{\,m}\: a(R u , u)^{\frac{1}{2}}.
  915. \end{align*}
  916. Следовательно,
  917. \begin{align*}
  918. a(R u, u) \ge \frac{1}{m \gamma^2} a(u,u),
  919. \end{align*}
  920. и оператор $R$ осуществляет взаимно однозначное отображение $V$ на $V$ и имеет ограниченный обратный
  921. \begin{align*}
  922. \|R^{-1}\| \le m \gamma^2
  923. \end{align*}
  924. Докажем (\ref{8-8}) от противного, что $\|T\|<1$. Пусть $\|T\|=1$, т.е. для любого $\varepsilon >0$ существует такое $v_{\varepsilon} \in V$, что $|[v_{\varepsilon}]|=1,|[T v_{\varepsilon}]|^2 \ge 1-\varepsilon$. Тогда
  925. \begin{align*}
  926. 1-\varepsilon \le |[T v_{\varepsilon}]|^2 =|[Q_m \cdots Q_2 Q_1 v_{\varepsilon}]|^2 \le \|Q_m \cdots Q_2 \| \cdot |[Q_1 v_{\varepsilon}]| \le |[Q_1 v_{\varepsilon}]|^2
  927. \end{align*}
  928.  
  929. и в силу $|[R_1 v_{\varepsilon}]|^2 + |[Q_1 v_{\varepsilon}]|^2=1$ имеем
  930. \begin{align*}
  931. |[R_1 v_{\varepsilon}]|^2 \le \varepsilon \equiv \varepsilon_1
  932. \end{align*}
  933. Оценим $|[R_i v_{\varepsilon}]|^2$. Поскольку $T=Q_m \cdots Q_2(I-R_1)$, то
  934. \begin{align*}
  935. |[Q_m \cdots Q_2 v_{\varepsilon} ]|^2 \ge |[T v_{\varepsilon}]|^2 - |[Q_m \cdots Q_2 R_1 v_{\varepsilon}]|^2 \ge \sqrt{\,1-\varepsilon_1}\: - \sqrt{\,\varepsilon_1}=\sqrt{\,1-\varepsilon_2}
  936. \end{align*}
  937. где $\varepsilon_2=1-(\sqrt{\,1-\varepsilon_1}-\sqrt{\,\varepsilon_1})^2$.   Таким образом,
  938. \begin{align*}
  939. 1 - \varepsilon_2 \le |[Q_m \cdots Q_3 Q_2 v_{\varepsilon}]|^2 \le |[Q_2 v_{\varepsilon}]|^2,
  940. \end{align*}
  941. и в силу равенства $R_2 = I - Q_2$ имеет место оценка
  942. \begin{align*}
  943. |[R_2 v_{\varepsilon}]|^2 \le \varepsilon_2.
  944. \end{align*}
  945. Аналогично показываем, что для $i=3,\dots,m$
  946. \begin{align*}
  947. |[Q_i v_{\varepsilon}]|^2 \ge 1 - \varepsilon_i,\:\:\: |[R_i v_{\varepsilon}]|^2 \le \varepsilon_i,\:\:\: \varepsilon_i = 1- (\sqrt{\,1-\varepsilon_{i-1}} - \sqrt{\, \varepsilon_{i-1}})^2.
  948. \end{align*}
  949. Очевидно, что при $\varepsilon \rightarrow 0$ имеем $\varepsilon_i \rightarrow 0,\:\:i=2,\dots,m$ \\
  950. Теперь воспользуемся тем, что $R$ обратим и $R^{-1}$ ограничен:
  951. \begin{align*}
  952. 1=|[v_{\varepsilon}]|=|[R^{-1} R v_{\varepsilon}]|\le \|R^{-1}\| \sum\limits_{i=1}^m |[R_i v_{\varepsilon}]| \le \|R^{-1}\|\sum\limits_{i=1}^m \sqrt{\,\varepsilon_i} \le m \gamma^2 \sum\limits_{i=1}^m \sqrt{\,\varepsilon_i}.
  953. \end{align*}
  954. Получили противоречие для достаточно малого $\varepsilon >0$.\\[0.5cm]
  955. \subsection{Алгебраическая формулировка метода Шварца}
  956.  
  957. Пусть разбиение области $\Omega =\bigcup\limits_{i=1}^m \Omega_i$ и ее триангуляция $\Omega^h $ таковы, что границы $\partial \Omega_i$ проходят по ребрам $\Omega^h$. Заменим $V,V_i$ на их конечно-элементные аналоги $U^h,U_i^h$ размерности $n,n_i,$ где $n(n_i)$ ~--- количество внутренних узлов в $\Omega^h\:\:(\Omega_i^h)$, и зададим операторы сужения $r_i^h :    U^h \rightarrow U_i^h$
  958. \begin{align*}
  959. r_i^h u^h (x_k) = u^h (x_k)
  960. \end{align*}
  961. во всех внутренних узлах $x_k$ триангуляции $\Omega_i^h$.\par
  962. Матричное представление оператора сужения есть прямоугольная $n_i \times n $ матрица $R_i$, состоящая из нулей и единиц, в каждом столбце которой не более одной единицы. С помощью матрицы $R_i$ зададим \\$n_i \times n_i$--матрицу $A_i$ как сужение матрицы $A$ системы $Au=f$ на подобласти $\Omega_i$ :
  963. \begin{align*}
  964. A_i = R_i A R_i^T
  965. \end{align*} \par
  966. Алгебраический вариант метода Шварца для решения системы \\$ Au=f$ представляет собой итерационный процесс с $m$ подшагами для нахождения очередного приближения $u^{n+1}$, если задано текущее приближение $u^n$:
  967. \begin{eqnarray}
  968. \begin{split}
  969. A_i z_i &= R_i (f-A u^{n+\frac{i-1}{m}})\\
  970. u^{n+\frac{i-1}{m}} &= u^{n+\frac{i-1}{m}} + R_i^T z_i,\qquad i=1,\dots,m
  971. \end{split}
  972. \label{8-9}
  973. \end{eqnarray} \par
  974. Для ошибки итерационного приближения на подшаге $e^{n+\frac{i}{m}}=u^{n+\frac{i}{m}} - u$ верно уравнение
  975. \begin{align*}
  976. e^{n+\frac{i}{m}}=e^{n+\frac{i-1}{m}}-R_i^T A_i^{-1} R_i A e^{n+\frac{i-1}{m}} = (I-P_i)e^{n+\frac{i-1}{m}},
  977. \end{align*}
  978. где матрица $P_i=I-R_i^T A_i^{-1} R_i$ ~--- проектор:
  979. \begin{align*}
  980. P_i^2 = (R_i^T A_i^{-1} R_i A)^2 = R_i^T A_i^{-1} R_i A R_i^T A_i^{-1} R_i A = R_i^T A_i^{-1} A_i A_i^{-1} R_i A = P_i
  981. \end{align*} \par
  982. Таким образом, оператор перехода, связывающий $e^n$ и $e^{n+1}$, соответствует мультипликативному методу:
  983. \begin{eqnarray}
  984. e^{n+1} = (I-P_m) \cdots (I-P_1)e^n.
  985. \label{8-10}
  986. \end{eqnarray} \par
  987. Перепишем (\ref{8-10}), используя определение ошибки $e^n$ и обозначение\\ $T = (I-P_m) \cdots (I-P_1)$:
  988. \begin{align*}
  989. &u^{n+1} - u = T(u^n-u),\\
  990. &u^{n+1}= u^n+(I-T)u - (I-T)u^n=u^n +(I-T)A^{-1} f - (I-T)u^n.
  991. \end{align*}
  992. Поэтому метод Шварца есть метод простой итерации для системы
  993. \begin{align*}
  994. (I-T)u=(I-T)A^{-1}f
  995. \end{align*}
  996. \newpage
  997.  
  998. \subsection{Аддитивный метод Шварца}
  999.  
  1000. Аддитивная версия метода Шварца отличается от вышерассмотренной мультипликативной (\ref{8-9}) суммированием вкладов подобластей
  1001. \begin{eqnarray}
  1002. \begin{split}
  1003. A_i z_i &= R_i ( f- A u^n),\qquad i=1,\dots,m, \\
  1004. u^{n+1} &= u^n + \sum\limits_{i=1}^m R_i^T z_i.
  1005. \end{split}
  1006. \label{8-11}
  1007. \end{eqnarray}\par
  1008. Ошибки аддитивного метода связаны уравнением
  1009. \begin{eqnarray}
  1010. e^{n+1} = e^n - \sum\limits_{i=1}^m R_i^T A_i^{-1} R_i A e^n = (I-\sum\limits_{i=1}^m P_i)e^n.
  1011. \label{8-12}
  1012. \end{eqnarray}\par
  1013. Таким образом, аддитивный метод Шварца можно интерпретировать, как метод простой итерации для решения системы $Au=f$ с
  1014. переобуславливателем $B=(\sum\limits_{i=1}^m P_i)$.\par
  1015. Привлекательность аддитивного метода Шварца заключается в его параллельной структуре: подзадачи решаются независимо, по окончании каждой итерации необходимо обменяться данными с границ подобластей $\Omega_i$. Перекрывающиеся подобласти удобно строить расширением неперекрывающихся подобластей $\hat\Omega_i$, на которые область $\Omega$ разбита изначально.\par
  1016. Заметим, что матрично-векторную версию мультипликативного или аддитивного метода Шварца можно рассмотреть как метод последовательной или параллельной коррекции на подпространствах.
  1017.  
  1018.  
  1019. \subsection{Связь с классическими итерационными методами}
  1020.  
  1021. Рассмотрим случай минимального перекрытия между двумя триангуляциями $\Omega_1^h,\Omega_2^h$, когда любой узел из $\Omega_1^h \cap \Omega_2^h$ принадлежит либо $\partial \Omega_1$, либо $\partial \Omega_2$. Предположим, что сперва перенумерованы внутренние узлы $\Omega_1^h$, а затем~--- внутренние узлы $\Omega_2^h$. В этом случае для матриц $A,R_1,R_2$ верно представление
  1022. \begin{align*}
  1023. A=\begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix},\:\:\: R_1=(I_1 \:\: 0),\:\:\:R_2=(0\:\:I_2).
  1024. \end{align*} \par
  1025. Одна итерация аддитивного метода Шварца записывается в виде
  1026. \begin{align*}
  1027. u^{n+1} &= u^n + R_1^T A_{11}^{-1} R_1 (f-A u^n) + R_2^T A_22^{-1} R_2 (f-A u^n)\\
  1028.        &= u^n + \begin{pmatrix} A_{11} & 0 \\ 0 & A_{22} \end{pmatrix}^{-1} \:\: (f-A u^n),
  1029. \end{align*}
  1030. т.е. представляет собой одну итерацию блочного метода Якоби.\par
  1031. Одна итерация мультипликативного метода Шварца записывается в виде
  1032. \begin{align*}
  1033. \begin{cases}
  1034. u^{n+\frac{1}{2}} &= u^n + R_1^T A_{11}^{-1} R_1 (f - A u^n) \\[0.2cm]
  1035. u^{n+1} &= u^{n+\frac{1}{2}} + R_2^T A_{22}^{-1} R_2 (f- A u^{n+\frac{1}{2}})
  1036. \end{cases}
  1037. \end{align*}
  1038. или
  1039. \begin{align*}
  1040. u^{n+1} = u^n + \begin{pmatrix} A_{11} & 0 \\ A_{12} & A_{22} \end{pmatrix}^{-1} \:\:\: (f-A u^n),
  1041. \end{align*}
  1042. т.е. представляет собой одну итерацию блочного метода Гаусса - Зейделя.
  1043.  
  1044. \subsection{Метод Шварца для сингулярно возмущенных операторов}
  1045.  
  1046. Как уже было отмечено, скорость сходимости итераций (\ref{8-1}) зависит от ширины полосы налегания подобластей $d$: чем меньше перекрытие, тем ближе $\|T\|$ к единице и хуже скорость сходимости. Это замечание верно для задачи (\ref{1-1}) и других эллиптических уравнений. Если перекрытие большое, то большая часть неизвестных входит в решение двух или нескольких подзадач, что ухудшает параллельные свойства аддитивного метода Шварца.\par
  1047. При решении некоторых уравнений с сингулярно возмущенными операторами диффузии отпадает необходимость в больших перекрытиях, что открывает возможности построения эффективных параллельных алгоритмов.\par
  1048. Например, при дискретизации на фиксированной сетке уравнения диффузии-реакции $-\tau \triangle +I$ с малым параметром $\tau > 0$ (типичном при неявных дискретизациях параболических уравнений) норма оператора перехода (\ref{8-12}) стремится к $q < 1$ при $\tau \rightarrow 0$. Более того, для любого $\varepsilon > 0$, при разбиении области на множество регулярных подобластей с таким налеганием, что справедлива оценка
  1049. \begin{align*}
  1050. d> C \sqrt{\,\tau}\left(\ln \frac{\varepsilon h^2}{\tau}\right)^{-1}
  1051. \end{align*}
  1052. одна итерация аддитивного метода Шварца обеспечивает приближение к точному решению системы с точностью $\varepsilon$. Это наблюдение позволяет заменить неявную схему для простейшего уравнения теплопроводности
  1053. \begin{align*}
  1054. (-\tau \triangle + I) u^{n+1} = \tau f + u^n \:\: \mbox{в} \:\: \Omega, \:\: u^{n+1} = 0 \:\: \mbox{на} \:\: \partial \Omega
  1055. \end{align*}
  1056. набором независимых задач в подобластях $\Omega_i$ полученных расширением\\8 $\hat\Omega_i,\: i=1,\dots,m$:
  1057. \begin{align*}
  1058. (-\tau \triangle + I)\hat u_i = \tau f + u^n \:\:\mbox{в} \: \Omega_i,\:\:\: \hat u_i=0\:\: \mbox{на}\:\: \partial \Omega_i,
  1059. \end{align*}
  1060. и заданием
  1061. \begin{align*}
  1062. u^{n+1}|_{\hat \Omega_i}=\hat u_i|_{\hat \Omega_i}
  1063. \end{align*}
  1064. При решении уравнения с оператором конвекции-диффузии $-\tau \triangle + (\vec b \nabla)$ с малым параметром $\tau > 0$ скорость мультипликативного метода Шварца остается высокой даже при минимальном перекрытии между подобластями, если направление перебора подобластей $\Omega_i,\:i=1,\dots,m$ совпадает с вектором конвективного переноса $\vec b$ или ортогонально ему.
  1065.  
  1066. \newpage
  1067. \section{Описание тестового примера}
  1068.  
  1069. \subsection{Прямой метод}
  1070.  
  1071. 1. Находим решение на подобластях например матричной прогонки.
  1072.  
  1073.  \begin{center}  Решение на большой области :\end{center}
  1074. \begin{align*}
  1075. \begin{bmatrix}
  1076. 18.21  & 28.41 &  33.71 &  35.35 &  33.71 &  28.41 &  18.21\\
  1077. 28.41  & 45.74 &  55.06 &  58.00 &  55.06 &  45.74 &  28.41\\
  1078. 33.71  & 55.06 &  66.79 &  70.53 &  66.79 &  55.06 &  33.71\\
  1079. 35.35  & 58.00 &  70.53 &  74.53 &  70.53 &  58.00 &  35.35\\
  1080. 33.71  & 55.06 &  66.79 &  70.53 &  66.79 &  55.06 &  33.71\\
  1081. 28.41  & 45.74 &  55.06 &  58.00 &  55.06 &  45.74 &  28.41\\
  1082. 18.21  & 28.41 &  33.71 &  35.35 &  33.71 &  28.41 &  18.21
  1083. \end{bmatrix}
  1084. \end{align*}
  1085. \begin{center}  Решение на меньшей области:\end{center}
  1086. \begin{align*}
  1087. \begin{bmatrix}
  1088. 11.00 &  14.00 &  11.00\\
  1089. 14.00 &  18.00 &  14.00\\
  1090. 11.00 &  14.00 &  11.00
  1091. \end{bmatrix}
  1092. \end{align*}
  1093.  
  1094. 2. Невязка на линии сцепления:
  1095. \begin{align*}
  1096. f=\begin{bmatrix}
  1097. 60.705550\\
  1098. 58.411626\\
  1099. 45.206164
  1100. \end{bmatrix}
  1101. \end{align*}
  1102.  
  1103. 3. Вычисляем дополнение Шура
  1104. \begin{align*}
  1105. A_{33}=\begin{bmatrix}
  1106. 4  & -1 & 0\\
  1107. -1 &  4 &-1\\
  1108. 0  & -1 & 4
  1109. \end{bmatrix}
  1110. \end{align*}
  1111.  
  1112. \begin{align*}
  1113. A^T_{13} A^{-1}_{11} A_{13}=\begin{bmatrix}
  1114. 0.299107 & 0.098214 & 0.031250\\
  1115. 0.098214 & 0.330357 & 0.098214\\
  1116. 0.031250 & 0.098214 & 0.299107
  1117. \end{bmatrix}
  1118. \end{align*}
  1119. \begin{align*}
  1120. A^T_{23} A^{-1}_{22} A_{23}=\begin{bmatrix}
  1121. 0.352908 & 0.123065 & 0.041495\\
  1122. 0.123065 & 0.343653 & 0.104317\\
  1123. 0.041495 & 0.104317 & 0.302159
  1124. \end{bmatrix}
  1125. \end{align*}
  1126.  
  1127. 4. Получаем следующее доплнение Шура:
  1128. \begin{align*}
  1129. S=A_{33}-A^T_{13} A^{-1}_{11} A_{13}-A^T_{23} A^{-1}_{22} A_{23}=\begin{bmatrix}
  1130. 3.347985 &-1.221280 &-0.072745\\
  1131. -1.221280 &3.325990 &-1.202531\\
  1132. -0.072745 &-1.202531 &3.398734
  1133. \end{bmatrix}
  1134. \end{align*}
  1135.  
  1136. 5.Решение на линии сцепления:
  1137. \begin{align*}
  1138. \begin{split}
  1139. &SU=f\\[0.3cm]
  1140. &U=\begin{bmatrix}
  1141. 33.328494\\
  1142. 39.981758\\
  1143. 28.160384
  1144. \end{bmatrix}
  1145. \end{split}
  1146. \end{align*}
  1147. 6. Решение на подобластях с учетом найденного решения на линии сцепления:
  1148.  \begin{center}  Решение на большой области:\end{center}
  1149. \begin{align*}
  1150. \begin{bmatrix}
  1151. 18.39 &  28.79 &  34.28 &  36.11 &  34.58 &  29.25 &  18.76\\
  1152. 28.77 &  46.48 &  56.21 &  59.57 &  56.96 &  47.67 &  29.77\\
  1153. 34.22 &  56.14 &  68.53 &  73.01 &  70.01 &  58.70 &  36.66\\
  1154. 35.97 &  59.33 &  72.75 &  77.91 &  75.39 &  64.45 &  42.17\\
  1155. 34.34 &  56.45 &  69.22 &  74.50 &  73.20 &  65.54 &  51.56\\
  1156. 28.94 &  46.92 &  57.19 &  61.66 &  61.37 &  56.96 &  49.19\\
  1157. 18.51 &  29.10 &  34.97 &  37.57 &  37.67 &  35.72 &  32.27
  1158. \end{bmatrix}
  1159. \end{align*}\\
  1160. \begin{center}  Решение на меньшей области:\end{center}
  1161. \begin{align*}
  1162. \begin{bmatrix}
  1163. 25.78 &  20.53 &  13.49\\
  1164. 33.25 &  26.84 &  17.43\\
  1165. 24.39 &  20.16 &  13.40
  1166. \end{bmatrix}
  1167. \end{align*}
  1168.  
  1169. \begin{center}  Решение задачи:\end{center}
  1170. \setcounter{MaxMatrixCols}{20}
  1171. \begin{align*}
  1172. \begin{bmatrix}
  1173. 18.39 & 28.79 & 34.28 & 36.11 & 34.58 & 29.25 & 18.76 \\
  1174. 28.77 & 46.48 & 56.21 & 59.57 & 56.96 & 47.67 & 29.77 \\
  1175. 34.22 & 56.14 & 68.53 & 73.01 & 70.01 & 58.70 & 36.66 \\
  1176. 35.97 & 59.33 & 72.75 & 77.91 & 75.39 & 64.45 & 42.17 \\
  1177. 34.34 & 56.45 & 69.22 & 74.50 & 73.20 & 65.54 & 51.56 & 33.33 & 25.78 & 20.53 & 13.49\\
  1178. 28.94 & 46.92 & 57.19 & 61.66 & 61.37 & 56.96 & 49.19 & 39.98 & 33.25 & 26.84 & 17.43\\
  1179. 18.51 & 29.10 & 34.97 & 37.57 & 37.67 & 35.72 & 32.27 & 28.16 & 24.39 & 20.16 & 13.40
  1180. \end{bmatrix}\notag
  1181. \end{align*}
  1182.  
  1183.  
  1184. \subsection{Метод сопряженных градиентов}
  1185. 1. Находим решение на подобластях с помощью метода сопряженных градиентов.
  1186.  
  1187.  \begin{center}  Решение на большой области :\end{center}
  1188. \begin{align*}
  1189. \begin{bmatrix}
  1190. 18.21  & 28.41 &  33.71 &  35.35 &  33.71 &  28.41 &  18.21\\
  1191. 28.41  & 45.74 &  55.06 &  58.00 &  55.06 &  45.74 &  28.41\\
  1192. 33.71  & 55.06 &  66.79 &  70.53 &  66.79 &  55.06 &  33.71\\
  1193. 35.35  & 58.00 &  70.53 &  74.53 &  70.53 &  58.00 &  35.35\\
  1194. 33.71  & 55.06 &  66.79 &  70.53 &  66.79 &  55.06 &  33.71\\
  1195. 28.41  & 45.74 &  55.06 &  58.00 &  55.06 &  45.74 &  28.41\\
  1196. 18.21  & 28.41 &  33.71 &  35.35 &  33.71 &  28.41 &  18.21
  1197. \end{bmatrix}
  1198. \end{align*}
  1199. \begin{center}  Решение на меньшей области:\end{center}
  1200. \begin{align*}
  1201. \begin{bmatrix}
  1202. 11.00 &  14.00 &  11.00\\
  1203. 14.00 &  18.00 &  14.00\\
  1204. 11.00 &  14.00 &  11.00
  1205. \end{bmatrix}
  1206. \end{align*}
  1207.  
  1208. 2. Невязка на линии сцепления:
  1209. \begin{align*}
  1210. \begin{bmatrix}
  1211. 60.705550\\
  1212. 58.411626\\
  1213. 45.206164
  1214. \end{bmatrix}
  1215. \end{align*}
  1216.  
  1217. 3. Дальше находим $a_m=A p_m $ и $\lambda_{opt}(x_m,p_m)$.
  1218.  
  1219. Сначала мы решаем задачу в большой и меньшей области,где в правой части рядом с линией сцепления стоят значения вектора $p_m$, вначале он равен нашей невязке, а в остальных нули. После того как мы нашли решения, мы находим вектор $a_m$ по формуле:
  1220. \begin{align*}
  1221. \begin{split}
  1222. a_m&=A_{33}\cdot p_m-y_{11}-y_{12},\\[0.3cm]
  1223. a_1&=\begin{bmatrix}
  1224. 128.61584\\
  1225. 65.77612\\
  1226. 78.98604
  1227. \end{bmatrix}
  1228. \end{split}
  1229. \end{align*}
  1230. где $y_{11}$ и $y_{12}$ вектора решения задачи.
  1231.  
  1232. Когда мы нашли $a_m$,теперь есть все чтобы вычислить $\lambda_{opt}(x_m,p_m)$ по формуле:
  1233. \begin{align*}
  1234. \begin{split}
  1235. \lambda_{opt}(x_m,p_m)&=\frac{(r_m , p_m)}{(a_m , p_m)},\\[0.3cm]
  1236. \mbox{ получается начальная } \lambda_{opt}&=0.60055
  1237. \end{split}
  1238. \end{align*}
  1239.  
  1240. 4. Дальше мы вычисляем приближение с помощью методом сопряженных градиентовc предобуславливателем в виде  метода симметричной верхней релаксации, условие выхода берем отношение начальной невязки к следующей и когда отношение будет меньше $eps$ выходим.
  1241.  
  1242. \begin{center}Алгоритм:\end{center}
  1243. -Вычисляем следующее приближение
  1244. \begin{align*}
  1245. \begin{split}
  1246. x_{m+1}&=x_m+\lambda_{opt}(x_m,p_m)\cdot p_m \\[0.3cm]
  1247. x_{1}&=\begin{bmatrix}
  1248. 36.456890\\
  1249. 35.079268\\
  1250. 27.148690
  1251. \end{bmatrix}
  1252. \end{split}
  1253. \end{align*}
  1254. -Вычисляем вектор невязки
  1255. \begin{align*}
  1256. \begin{split}
  1257. r_{m+1}&=r_m - \lambda_{opt}(x_m,p_m)\cdot a_m\\[0.3cm]
  1258. r_{1}&=\begin{bmatrix}
  1259. -16.535058\\
  1260. 18.909592\\
  1261. -2.229126
  1262. \end{bmatrix}
  1263. \end{split}
  1264. \end{align*}
  1265. -Находим вектор
  1266. \begin{align*}
  1267. \begin{split}
  1268. p_{m+1}&=r_{m+1}-\frac{(r_{m+1},a_m)}{(a_m,p_m)} p_m\\[0.3cm]
  1269. p_{1}&=\begin{bmatrix}
  1270. -12.311555\\
  1271. 22.973498\\
  1272. 0.916028
  1273. \end{bmatrix}
  1274. \end{split}
  1275. \end{align*}
  1276.  
  1277. И находим ответ при наших размерах областей за 3 итерации.
  1278.  
  1279. \begin{center}  2 итерация :\end{center}
  1280.  
  1281. \begin{align*}
  1282. %\begin{gather}
  1283. \begin{split}
  1284. a_2=\begin{bmatrix}
  1285. -69.34261\\
  1286. 90.34391\\
  1287. -23.61741
  1288. \end{bmatrix}\qquad
  1289. \lambda_{opt}=0.21872 \qquad \qquad
  1290. x_{2}=\begin{bmatrix}
  1291. 33.764106\\
  1292. 40.104033\\
  1293. 27.349044
  1294. \end{bmatrix}\notag \\[0.8cm]
  1295. r_{2}=\begin{bmatrix}
  1296. -1.368436\\
  1297. -0.850435\\
  1298. 2.936475
  1299. \end{bmatrix}\:\:
  1300. \frac{(r_{2},a_2)}{(a_2,p_1)}=-0.01764091 \qquad
  1301. p_{2}=\begin{bmatrix}
  1302. -1.585623\\
  1303. -0.445162\\
  1304. 2.952635
  1305. \end{bmatrix}\notag
  1306. \end{split}
  1307. \end{align*}\\
  1308. %\end{gather}\\
  1309.  
  1310. \begin{center}  3 итерация :\end{center}
  1311.  
  1312.  
  1313. \begin{align*}
  1314. %\begin{gather}
  1315. \begin{split}
  1316. a_3=\begin{bmatrix}
  1317. -4.97974\\
  1318. -3.09474\\
  1319. 10.68588
  1320. \end{bmatrix}\qquad
  1321. \lambda_{opt}=0.27480\qquad \qquad
  1322. x_{3}=\begin{bmatrix}
  1323. 33.328380\\
  1324. 39.981704\\
  1325. 28.160426
  1326. \end{bmatrix}\notag \\[0.8cm]
  1327. r_{3}=\begin{bmatrix}
  1328. 0.000003\\
  1329. 0.000002\\
  1330. 0.000002
  1331. \end{bmatrix}\:\:
  1332. \frac{(r_{3},a_3)}{(a_3,p_2)}=-0.00000002  \qquad
  1333. p_{3}=\begin{bmatrix}
  1334. 0.000003\\
  1335. 0.000002\\
  1336. 0.000002
  1337. \end{bmatrix}\notag
  1338. \end{split}
  1339. \end{align*}
  1340. \\[0.6cm]
  1341. 5. Решение на подобластях с учетом найденного приближения:
  1342.  \begin{center}  Решение на большой области:\end{center}
  1343. \begin{align*}
  1344. \begin{bmatrix}
  1345. 18.39 &  28.79 &  34.28 &  36.11 &  34.58 &  29.25 &  18.76\\
  1346. 28.77 &  46.48 &  56.21 &  59.57 &  56.96 &  47.67 &  29.77\\
  1347. 34.22 &  56.14 &  68.53 &  73.01 &  70.01 &  58.70 &  36.66\\
  1348. 35.97 &  59.33 &  72.75 &  77.91 &  75.39 &  64.45 &  42.17\\
  1349. 34.34 &  56.45 &  69.22 &  74.50 &  73.20 &  65.54 &  51.56\\
  1350. 28.94 &  46.92 &  57.19 &  61.66 &  61.37 &  56.96 &  49.19\\
  1351. 18.51 &  29.10 &  34.97 &  37.57 &  37.67 &  35.72 &  32.27
  1352. \end{bmatrix}
  1353. \end{align*}\\
  1354. \begin{center}  Решение на меньшей области:\end{center}
  1355. \begin{align*}
  1356. \begin{bmatrix}
  1357. 25.78 &  20.53 &  13.49\\
  1358. 33.25 &  26.84 &  17.43\\
  1359. 24.39 &  20.16 &  13.40
  1360. \end{bmatrix}
  1361. \end{align*}
  1362.  
  1363. \begin{center}  Решение задачи:\end{center}
  1364. \setcounter{MaxMatrixCols}{20}
  1365. \begin{align*}
  1366. \begin{bmatrix}
  1367. 18.39 & 28.79 & 34.28 & 36.11 & 34.58 & 29.25 & 18.76 \\
  1368. 28.77 & 46.48 & 56.21 & 59.57 & 56.96 & 47.67 & 29.77 \\
  1369. 34.22 & 56.14 & 68.53 & 73.01 & 70.01 & 58.70 & 36.66 \\
  1370. 35.97 & 59.33 & 72.75 & 77.91 & 75.39 & 64.45 & 42.17 \\
  1371. 34.34 & 56.45 & 69.22 & 74.50 & 73.20 & 65.54 & 51.56 & 33.33 & 25.78 & 20.53 & 13.49\\
  1372. 28.94 & 46.92 & 57.19 & 61.66 & 61.37 & 56.96 & 49.19 & 39.98 & 33.25 & 26.84 & 17.43\\
  1373. 18.51 & 29.10 & 34.97 & 37.57 & 37.67 & 35.72 & 32.27 & 28.16 & 24.39 & 20.16 & 13.40
  1374. \end{bmatrix}\notag
  1375. \end{align*}
  1376. \subsection{Метод Дирихле-Нейман}
  1377. 1. Находим решение на подобластях с помощью метода сопряженных градиентовc предобуславливателем в виде  метода симметричной верхней релаксации.
  1378.  
  1379.  \begin{center}  Решение на большой области :\end{center}
  1380. \begin{align*}
  1381. \begin{bmatrix}
  1382. 18.21  & 28.41 &  33.71 &  35.35 &  33.71 &  28.41 &  18.21\\
  1383. 28.41  & 45.74 &  55.06 &  58.00 &  55.06 &  45.74 &  28.41\\
  1384. 33.71  & 55.06 &  66.79 &  70.53 &  66.79 &  55.06 &  33.71\\
  1385. 35.35  & 58.00 &  70.53 &  74.53 &  70.53 &  58.00 &  35.35\\
  1386. 33.71  & 55.06 &  66.79 &  70.53 &  66.79 &  55.06 &  33.71\\
  1387. 28.41  & 45.74 &  55.06 &  58.00 &  55.06 &  45.74 &  28.41\\
  1388. 18.21  & 28.41 &  33.71 &  35.35 &  33.71 &  28.41 &  18.21
  1389. \end{bmatrix}
  1390. \end{align*}
  1391. \begin{center}  Решение на меньшей области:\end{center}
  1392. \begin{align*}
  1393. \begin{bmatrix}
  1394. 11.00 &  14.00 &  11.00\\
  1395. 14.00 &  18.00 &  14.00\\
  1396. 11.00 &  14.00 &  11.00
  1397. \end{bmatrix}
  1398. \end{align*}
  1399.  
  1400. 2. Невязка на линии сцепления:
  1401. \begin{align*}
  1402. \begin{bmatrix}
  1403. 60.705550\\
  1404. 58.411626\\
  1405. 45.206164
  1406. \end{bmatrix}
  1407. \end{align*}
  1408.  
  1409. 3. Дальше мы решаем уравнение Пуассона, в узлах на лиции сцепления решаем по условию Неймана:
  1410.  
  1411. \begin{align*}
  1412. 2U_{ij}-\frac{1}{2}U_{i-1,j}-\frac{1}{2}U_{i+1,j}-U_{i,j+1}=(r-SY^{-})_{ij}
  1413. \end{align*}
  1414.  
  1415. А на в остльных узлах мы решаем с условием Дирихле.
  1416.  
  1417. Задаем матрицу, где первый столбец будет равен нашей невязке, а остальные элементы равны нули и решаем по условию Неймана. Первый столбец решения будет равняться поправке $p_0=W^{-1}r_0$, и теперь мы можем вычислить величину $\varrho_0=(p_0,r_0)$\\
  1418. \begin{align*}
  1419. p_0=\begin{bmatrix}
  1420. 64.0113\\
  1421. 77.6476\\
  1422. 55.0629
  1423. \end{bmatrix}\quad
  1424. \varrho_0=10910.6
  1425. \end{align*}
  1426.  
  1427. 4. Дальше решаем задачу в большой и меньшей области,где в правой части рядом с линией сцепления стоят значения вектора $p_m$, а в остальных нули. После того как мы нашли решения, мы находим вектор $a_m$ по формуле:
  1428. \begin{align*}
  1429. a_m&=A_{33}\cdot p_m-y_{11}-y_{12},\\[0.3cm]
  1430. a_1&=\begin{bmatrix}
  1431. 115.47406\\
  1432. 113.86441\\
  1433. 89.11418
  1434. \end{bmatrix}
  1435. \end{align*}
  1436. где $y_{11}$ и $y_{12}$ вектора решения задачи. Дальше по алгоритму с помощью
  1437. методом сопряженных градиентов c предобуславливателем в виде  метода симметричной верхней релаксации, находим приближение в процедуре Grad2 мы вычисляем приближение с помощью, условие выхода берем отношение начальной невязки к следующей и когда отношение будет меньше eps выходим.
  1438. \begin{center}Алгоритм:\end{center}
  1439. - Находим $\lambda_{opt}(x_m,p_m)$
  1440. \begin{align*}
  1441. \lambda_{opt}(x_m,p_m)&=\frac{\varrho_m}{(a_m,p_m)} \\
  1442. \lambda_{opt}&=0.5161
  1443. \end{align*}
  1444. -Вычисляем следующее приближение
  1445. \begin{align*}
  1446. x_{m+1}&=x_m+\lambda_{opt}(x_m,p_m)\cdot p_m\\
  1447. x_{1}&=\begin{bmatrix}
  1448. 33.03715\\
  1449. 40.07501\\
  1450. 28.41876
  1451. \end{bmatrix}
  1452. \end{align*}
  1453. -Вычисляем вектор невязки
  1454. \begin{align*}
  1455. r_{m+1}&=r_m - \lambda_{opt}(x_m,p_m)\cdot a_m\\
  1456. r_{1}&=\begin{bmatrix}
  1457. 1.10811\\
  1458. -0.3553\\
  1459. -0.7872
  1460. \end{bmatrix}
  1461. \end{align*}
  1462. -Находим новую поправку $q_{m+1}$ и величину $\varrho_{m+1}$
  1463. \begin{align*}
  1464. q_{m+1}&=W^{-1}r_{m+1} \qquad \quad \varrho_{m+1}=(q_{m+1},r_{m+1})\\
  1465. q_{1}&=\begin{bmatrix}
  1466. 0.573822\\
  1467. -0.1936389\\
  1468. -0.52036478
  1469. \end{bmatrix} \quad\: \varrho_{1}=1.11427
  1470. \end{align*}
  1471. -Находим вектор
  1472. \begin{align*}
  1473. p_{m+1}&=q_{m+1}-\frac{\varrho_{m+1}}{\varrho_m} p_m\\
  1474. p_{1}&=\begin{bmatrix}
  1475. 0.58036\\
  1476. -0.18571\\
  1477. -0.51474
  1478. \end{bmatrix}
  1479. \end{align*}
  1480.  
  1481. И находим при наших размерах областей, за 3 итерации.
  1482.  
  1483. \begin{center}  2 итерация :\end{center}
  1484. \begin{gather}
  1485. \begin{split}
  1486. a_2=\begin{bmatrix}
  1487. 2.20728\\
  1488. -0.7074\\
  1489. -1.56837
  1490. \end{bmatrix}
  1491. \lambda_{opt}=0.50199 \:\:
  1492. & x_{2}=\begin{bmatrix}
  1493. 33.3285\\
  1494. 39.9818\\
  1495. 28.1604
  1496. \end{bmatrix}
  1497. r_{2}=\begin{bmatrix}
  1498. 0.00007\\
  1499. -0.00017\\
  1500. 0.000137
  1501. \end{bmatrix}\notag \\[0.8cm]
  1502. q_{2}=\begin{bmatrix}
  1503. 0.000019\\
  1504. -0.00006\\
  1505. 0.000055
  1506. \end{bmatrix} &\varrho_{2}=2 \cdot 10^{-7}  \:\:
  1507. p_{2}=\begin{bmatrix}
  1508. 0.00002\\
  1509. -0.00006\\
  1510. 0.000055
  1511. \end{bmatrix}\notag
  1512. \end{split}
  1513. \end{gather}\\
  1514. \begin{center}  3 итерация :\end{center}
  1515. \begin{gather}
  1516. \begin{split}
  1517. a_3=\begin{bmatrix}
  1518. 0.00014\\
  1519. -0.00030\\
  1520. 0.00026
  1521. \end{bmatrix}
  1522. \lambda_{opt}=0.50001 \:\:
  1523. & x_{3}=\begin{bmatrix}
  1524. 33.328497\\
  1525. 39.981746\\
  1526. 28.160392
  1527. \end{bmatrix}
  1528. r_{3}=\begin{bmatrix}
  1529. -0.0000000044\\
  1530. -0.0000000021\\
  1531. -0.0000000009
  1532. \end{bmatrix}\notag \\[0.8cm]
  1533. q_{3}=\begin{bmatrix}
  1534. -0.0000000038\\
  1535. -0.0000000033\\
  1536. -0.0000000018
  1537. \end{bmatrix} &\varrho_{3}=3 \cdot 10^{-12}  \:\:
  1538. p_{3}=\begin{bmatrix}
  1539. -0.0000000038\\
  1540. -0.0000000033\\
  1541. -0.0000000018
  1542. \end{bmatrix}\notag
  1543. \end{split}
  1544. \end{gather}\\
  1545. 5. Решение на подобластях с учетом найденного приближения:
  1546.  
  1547.  \begin{center}  Решение на большой области:\end{center}
  1548. \begin{align*}
  1549. \begin{bmatrix}
  1550. 18.39 &  28.79 &  34.28 &  36.11 &  34.58 &  29.25 &  18.76\\
  1551. 28.77 &  46.48 &  56.21 &  59.57 &  56.96 &  47.67 &  29.77\\
  1552. 34.22 &  56.14 &  68.53 &  73.01 &  70.01 &  58.70 &  36.66\\
  1553. 35.97 &  59.33 &  72.75 &  77.91 &  75.39 &  64.45 &  42.17\\
  1554. 34.34 &  56.45 &  69.22 &  74.50 &  73.20 &  65.54 &  51.56\\
  1555. 28.94 &  46.92 &  57.19 &  61.66 &  61.37 &  56.96 &  49.19\\
  1556. 18.51 &  29.10 &  34.97 &  37.57 &  37.67 &  35.72 &  32.27
  1557. \end{bmatrix}
  1558. \end{align*}\\
  1559. \begin{center}  Решение на меньшей области:\end{center}
  1560. \begin{align*}
  1561. \begin{bmatrix}
  1562. 25.78 &  20.53 &  13.49\\
  1563. 33.25 &  26.84 &  17.43\\
  1564. 24.39 &  20.16 &  13.40
  1565. \end{bmatrix}
  1566. \end{align*}
  1567.  
  1568. \begin{center}  Решение задачи:\end{center}
  1569. \setcounter{MaxMatrixCols}{20}
  1570. \begin{align*}
  1571. \begin{bmatrix}
  1572. 18.39 & 28.79 & 34.28 & 36.11 & 34.58 & 29.25 & 18.76 \\
  1573. 28.77 & 46.48 & 56.21 & 59.57 & 56.96 & 47.67 & 29.77 \\
  1574. 34.22 & 56.14 & 68.53 & 73.01 & 70.01 & 58.70 & 36.66 \\
  1575. 35.97 & 59.33 & 72.75 & 77.91 & 75.39 & 64.45 & 42.17 \\
  1576. 34.34 & 56.45 & 69.22 & 74.50 & 73.20 & 65.54 & 51.56 & 33.33 & 25.78 & 20.53 & 13.49\\
  1577. 28.94 & 46.92 & 57.19 & 61.66 & 61.37 & 56.96 & 49.19 & 39.98 & 33.25 & 26.84 & 17.43\\
  1578. 18.51 & 29.10 & 34.97 & 37.57 & 37.67 & 35.72 & 32.27 & 28.16 & 24.39 & 20.16 & 13.40
  1579. \end{bmatrix}\notag
  1580. \end{align*}
  1581. \newpage
  1582. \section*{Заключение}
  1583. \addcontentsline{toc}{section}{Заключение}
  1584. В выпускной квалификационной работе были изучены и описаны методы декомпозиции, которые выделяются эффективностью решения задач в областях специального вида. После анализа всех методов можно установить, что прямой метод является очень трудоемким, так как в нем лишь для построения матрицы S нам надо решить в большой области и потом в малой, столько раз сколько узлов на линии сцепления и после этого надо решить задачу с полной матрицей размерностью равной размерностью интерфейса. Это требует довольно много времени, поэтому лучше использовать итерационные методы,
  1585. которые будут решать значительно быстрее. За то время пока в прямом методе находится матрица S,
  1586. в итерационных методах за это время решается сама задача, так как им не требуется обращать саму матрицу S, а просто вычисляют результат этой матрицы к вектору.
  1587. Была реализована модельная задача L-образной области в программной среде Delphi, решающие уравнение Пуассона, с различными граничными условиями Дирихле и Неймана. После реализации была проведена сравнительная оценка методов по устойчивости и количеству итераций
  1588.  
  1589. Вы не решали задачу Неймана для сложной области, а использовали ее решение в квадрате
  1590. для решения задачи Дирихле в сложной области в качестве предобуславливателя  Нейман-Дирихле.
  1591.  
  1592. \begin{center}
  1593.  
  1594. \begin{tabular}{|m{2cm}|c|c|c|c|}
  1595. \hline размер областей $N_1\times N_2$ & \multicolumn{2}{|c|}{метод сопряженных градиентов}& \multicolumn{2}{|c|}{метод Дирихле-Нейман}\\
  1596. \cline{2-5} & $R/R_1$ & кол-во итераций & $R/R_1$ & кол-во итераций \\
  1597.    \hline 7х3 & $7\cdot 10^{-9} $ & 3 & $3\cdot 10^{-9}$ & 3 \\
  1598.    \hline 16х8 & $6\cdot 10^{-9} $ & 8 & $1\cdot 10^{-7}$ & 3 \\
  1599.    \hline 32х16 & $8\cdot 10^{-5} $ & 12 & $2\cdot 10^{-6}$ & 3 \\
  1600.    \hline 64х32 & $5\cdot 10^{-5} $ & 18 & $2\cdot 10^{-5}$ & 3 \\
  1601.  \hline 128х64 & $9\cdot 10^{-5} $ & 25 & $9\cdot 10^{-5}$ & 3 \\
  1602.    \hline 256х128 & $8\cdot 10^{-5} $ & 36 & $3\cdot 10^{-7}$ & 4 \\
  1603.    \hline 512х256 & $9\cdot 10^{-5} $ & 51 & $2\cdot 10^{-7}$ & 4 \\
  1604.    \hline
  1605.    \end{tabular}
  1606. \vspace{5mm}
  1607. Таблица 1.\\
  1608. \end{center}
  1609.  
  1610.  
  1611. \newpage
  1612. \renewcommand{\refname}{Список литературы}
  1613. \addcontentsline{toc}{section}{Список литературы}
  1614. \bibliographystyle{gost705}
  1615. \begin{thebibliography}{99}
  1616. \bibitem{1}Carbey M., Kuznetsov Yu., Vassileuski Yu. Parallel Schwarz method for a convection-diffusion problem.: SIAM J.Sci.Comp. 2000
  1617. \bibitem{2}Mandel J. Balancing domain decomposition: Commun. Appl. Numer. Meth. 1993
  1618. \bibitem{3}Quarteroni A.. Valli A. Domain decomposition methods for partial differential equations.: Oxford Science Publications, 1999.
  1619. \bibitem{4}Деммель ДЖ. Вычислительная линейная алгебра. Теория и приложения. Пер. с англ.---М.:Мир, 2001.
  1620. \bibitem{5}Andrea Toselli, Olof B. Widlund. Domain Decomposition Methods - Algorithms and Theory:Springer, 2005.
  1621. \bibitem{6}Василевский Ю.В., Ольшанский М.А. Краткий курс по многосеточным методам декомпозиции области.- М.: МГУ им. М.В. Ломоносова, 2007.
  1622. \bibitem{7}Sergey Nepomnyaschikh. Domain decomposition methods. In Lectures on advanced computational methods in mechanics, volume 1 of Radon Ser. Comput. Appl. Math.,pages 89-159. Walter de Gruyter, Berlin, 2007
  1623. \bibitem{8}А.А. Самарский, Е.С. Николаев. Методы решения сеточных уравнений. М.: Наука, 1978.
  1624. \bibitem{9}Лебедев В.И. Метод композиции. М.: ОВМ АН СССР, 1986, 191 с.
  1625.  
  1626. \end{thebibliography}
  1627.  
  1628.  
  1629. \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!