1631124674-6a00ac47f208bd132d328527d69fe75d (848586), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

35.Рестартовые методы наименьших квадратов в подпространствах Крылова

Проблема для реализации методов выше, нам необходимо очень много памяти, тк нужно хранить все предыдущие итерации. Для этого воспользуемся методами рестарта: Возьмем какое-то число ( на слайдах - m) и будем каждые m итераций начинать как-бы заново. Т.е. первую невязку считаем как обычно из уравнения, далее по формулам, которые мы и раньше использовали, а n_l = m*l мы снова считаем из уранвения.
те если m=100, то мы сотую невязку считаем как 0-ую , 101 как первую и тд. то есть нам нужно будет хранить вместо всех итераций лишь итерации рестартов.
Для того чтобы определить коэффициенты c в приближении u(c чертой)_nl мы используем метод наименьших квадратов.
то есть хотим минимизировать невязку r_nl , положим ее = 0. Тогда получим что коэф. c, на которых это достигается ( обозначим их С с чертой) будут удовлетворять уравнению : Wc=r^nl и будет минимизировать r(с чертой)nl . W и r мы знаем, поэтому получаем систему для нахождения c_i
Но у нас коэффициентов c не много( в кол-ве рестартов), а вектор r^nl длинный, поэтому у нас будет переопределенная система.
Поэтому для упрощения домножаем на W^T , тем самым матрица перед С стала меньше и мы уменьшили размерность правой части. отсюда находим C.
( вообще можем это решать если произведение матриц W невырождено, но если вырождено, там можно использовать псведообратные матрицы, однако это выходит за рамки курса и не так важно.)

36.Общая идея методов декомпозиции областей (МДО) (операторы Пуанкаре -- Стеклова)

Представим общую идею МДО следующим образом. Пусть в расчетной трехмерной области Ω с границей Γ требуется решить краевую задачу

где линейные дифференциальные операторы L и l обеспечивают существование единственного решения u(r) в некотором функциональном пространстве. Разобъем область Ω на P пересекающихся или не пересекающихся подобластей Ωq и введем следующие обозначения:

где ωq есть множество номеров подобластей, соседних к Ωq, Γq — вся граница q-й подобласти, а Γq,0 — ее внешняя часть, т.е. Ω0 обозначает «внешнюю» подобласть — дополнение к Ω в R3 . Вместо исходной задачи (1) рассматриваем P краевых подзадач в подобластях Ωq:

где lq,q0 и gq,q0 при q 0 6= 0 определяют некоторые «внутренние» граничные условия такие, которые не «портили» бы исходное решение u, т.е. uq(~r) = u(~r) при ~r ∈ Ωq. Например, в достаточно общем случае эти условия имеют вид

причем для βq = βq 0 = 0 они соответствуют условию 1-го рода (Дирихле), при αq = αq 0 = 0 — условию 2-го рода (Неймана), а в остальных случаях — условию 3-го рода (Робина). Естественным методом решения системы краевых задач (3) является организация простых итераций, т.е. блочного метода Якоби вида

где правые части граничных условий для каждой подобласти определяются по значениям решения с прошлой итерации в смежных подобластях. Далее в качестве иллюстрации исходной задачи (1) мы будем рассматривать аппроксимацию уравнения Пуассона в кубической области с граничными условиями Дирихле на кубической сетке с общим числом узлов M3:

Отметим, что с точек зрения как скорости сходимости итераций, так и технологии распараллеливания, существенное значение имеет размерность декомпозиции, варианты которой представлены на рис. 1. Для простой расчетной области в форме параллелепипеда размерность очевидным образом определяется как количество типов координатных плоскостей, используемых при построении подобластей. Например, при 1-D декомпозиции область разбивается на P слоев с помощью параллельных плоскостей.

Итерационные процессы на основе операторов Пуанкаре–Стеклова

В данном пункте мы рассмотрим частный случай декомпозиции на две подобласти без пересечения (P = 2, ∆ = 0), в которых решаются уравнения Пуассона

совместно определяющие в расчетной области Ω =Ω1 ∩Ω2 решение задачи Дирихле, обладающее свойствами непрерывности на общей границе подобластей Γ1,2:

Задавая на внутренней границе произвольное начальное приближение и вычисляя решения соответствующих подзадач

для функций ошибки = −0 , q = 1, 2, мы получаем следующие уравнения:

Отметим, что в силу условий непрерывности исходного решения, имеет место равенство

Определяя теперь на Г1,2 операторы Пуанкаре–Стеклова

мы приходим к уравнению

которое фактически представляет новую формулировку метода декомпозиции областей. Очевидно, что умножение на оператор −1 включает решение краевой подзадачи в .

Оказывается, что уравнение выше может быть эффективно предобусловлено следующим образом:

Предобусловленный оператор A¯ (А с чертой из формулы выше) обладает при этом замечательными свойствами:

т.е. он представим в виде суммы перестановочных операторов A1, A2. Это позволяет, в частности, применять для решения (20) сверхбыстрые неявные методы переменных направлений [1, 2, 19]. Отметим также, что в работе [9] на основе операторов Пуанкаре–Стеклова построен оптимальный (сходящийся за 2 итерации) метод Шварца при декомпозиции области на две непересекающиеся подобласти

Пример:

Условие 1-го рода (Дирихле) - известно значение искомой функции на границе.

Условие 2-го рода (Неймана) - известна производная искомой функции на границе.

Условие 3-го рода (Робена) - смешанный тип 1 и 2.

Нужно решить в этой области задачу дирихле, на границе задано условие первого рода ()

Мультипликативный (альтернирующий метод Шварца)

Можно решать следующим образом:

Рассмотрим вертикальный прямоугольник 1, решим в нем задачу, причем на границе 1 ( на внутренней, которая не является границей внешней области) зададим произвольное значение (например 0), решили ее, теперь решаем в 2, но в нем на2 берем теперь то решение, которое получили из задачи для 1.

Это будет одна итерация решения исходной задачи в L-образной области.

Далее берем решение из 2 для внутренней границы и решаем в 1 и так далее. Так итеративно повторяем, пока метод не сойдется.

На 1 и 2 с некоторой точностью на каждой итерации результаты будут совпадать. И тогда будем считать, что мы решили в исходной области. Можно придумать более сложные геометрии, так же разбить их на подобласти с пересечениями

Плохо распараллеливается (из-за структуры алгоритма)

Аддитивный

Метод декомпозиции областей без налегания:

Эту же задачу можно рассмотреть как объединение 3-х прямоугольников (на рисунке это квадраты). Применим альтернирующий метод Шварца, но теперь у них нету пересечения. Если на 1 и 2 брать условие Дирихле, то ничего не выйдет, но если брать условие второго рода (условие Неймана). В каждой подобласти одновременно решим задачу.. Так как тут пересечения нет, можно решать одновременно во всех областях (в альт. методе последовательно решать, так как там области пересекаются). После решения, на внутренних границах берем значения функции, которые получились из решений в этих областях. И теперь можем взять условие Дирихле на 1 и 2 и решаем задачу во всех областях. Так и прорешиваем: берем сначала условие Неймана, потом Дирихле и так и чередуем.

Хорошо параллелится.

Если эти итерационные процессы сходятся, то мы получим решения для L-образной области. На дифференциальном уровне оба этих метода сходятся. Мультипликативный сходится тем быстрее, чем больше пересечение областей. Если декомпозиция без пересечений, то тут все зависит от краевых условия и как мы их используем (в частности, на 1 и 2 можно брать разные условия третьего рода

37. МДО с параметризированными пересечениями подобластей и с разными унтерфейсными условиями
http://www.mathnet.ru/links/6972608a2547e7e3cf56ee76b65d9034/vyurv116.pdf

Есть два подхода:

1. мы рассматриваем подобласти с пересечениями

2. без пересечений отдельно.

1) альтернирующий метод шварца . Мы задаем произвольные значение на границе Г1. решаем в прямоугольной области состоящей из Ω1 и Ω. Находим решение. Теперь на границе Г2 в качестве значений берем получившиеся значения. теперь решаем в горизонтальной прямоугольной области. Снова меняем значения на границе Г1 и решаем задачу в вертикальной прямоугольной области и т.д. В результате процесс ( мы так предполагаем вроде как) сойдется, те на границах Г результаты с какой-то точностью будут связаны. Этот метод аналогичен методу последовательных смещений.

2) мы рассматриваем разбиение на отдельные области, без пересечений. На обеих границах не можем одновременно задать сразу условия дирихле. Поэтому положим там условие Неймана. Т.е. зададим как-то нормальную производную.

Теперь в каждой подобласти одновременно решим задачу. Далее на каждой границе Г1 и Г2 возьмем уже значение этих найденных функций для условий Дирихле. Снова отрезаем в каждой подобласти. Вычислим нормальные производные на границах и снова будем решать с условиями уже Неймана. Так, если процесс сходится мы получим решение во всей L образной области. аналогичен методу одновременных смещений.

Причем. Альтернирующий Шварца сходится тем быстрее, чем больше пересечение областей! Однако, он плохо распараллеливается. Для 2-го же алгоритма, мы решение задачи в подобластях можем как раз таки искать параллельно.
На слайдах- формальная постановка методов. Те есть сама задача в q-ой подобласти и соответствующие граничные условия.
После аппроксимации получаем выражение с A_q,q. и фактически мы решаем паралельно в каждой подорбласти задачу, потом осуществляем обмен информации на границах.

м

38.Алгебраические МДО в подпространствах Крылова (Воропаева)

Комментарии с лекции 5.04

Характеристики

Список файлов ответов (шпаргалок)