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

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

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

Вместо L матрицу A. (u с точкой - производная по времени от u) (11). Получаем задачу на u не как на функцию непрерывного аргумента, а как на вектор, но каждая компонента пока зависит от времени (12), т.е. по времени пока ничего не аппроксимировали и не дискретизировали.

Как-то учли граничные условия и получили алгебраическую систему (12). , когда её отбросим, получим ОДУ (по времени). Потом саппроксимировав всё еще и по времени получаем просто САУ (13).

Если начальная система была нелинейной (коэффициенты зависят от u), то САУ тоже будет нелинейной. Такие системы решают методом квазилинеаризации, т.е. каким-то образом сводят к линейным системам, приближённо решают их, опять повторяют квазилинеаризацию, т.е. проводят итерации для нелинейной системы, решая на каждом шаге линейную. Т.е. в итоге так или иначе необходимо решать СЛАУ.

Последняя строка на слайде - примеры порядков систем. (10^7 - маленькая задачка).

Отметим, что матрицы получаются разреженными (много нулей). a_{l,l} -- диагональный элемент, w_l -- множество ненулевых внедиагональных элементов. Если к-во узлов в w_l =N_l, то N_l<

Решение СЛАУ занимает большую часть времени при решении таких задач (80-85%), т.е. если ускорить их решение, общий процесс тоже заметно ускорится.

Аппроксимируем уравнение (12). Пусть сетка по времени n, шаг . В -- полученная ранее матрица, после неё -- простейшая аппроксимация производной по времени (двухшаговая). А берём с весом: неявный член с весом , явный -- с весом . Т.е., если =0, то схема явная, а если больше 0, то неявная, если =1 -- чисто неявная.

При достигается наилучший порядок аппроксимации для схем такого вида -- О( ). Это схема Кранка-Николсона.

Какие лучше? Проблема устойчивости: неявные -- устойчивы, явные -- условно устойчивы . Исторически, неявные были лучше, но сейчас с суперкомпьютерами опять возник вопрос какие лучше, ведь явные проще распараллеливаются.

Примечание: когда написано Au -- это числовая матрица, умноженная на вектор u (т.е линейное выражение), а когда написано A(u) -- это матрица, нелинейно зависящая от u.

Последняя строка (15) -- нелинейная схема, чтобы решить нужен двухуровневый итерационный процесс. (верхний уровень - нелинейные итерации, нижний - линейные)

Если по времени рассматривается более сложная аппроксимация, см. вопрос №21.

20.Схемы предиктор-корректор

Теория итерационных алгоритмов работает с любым начальным приближением, но если начальное приближение лучше, то будет меньше итераций.

Схемы предиктор-корректор - семейство алгоритмов численного решения различных задач, которые состоят из двух шагов. На первом шаге (предиктор) вычисляется грубое приближение требуемой величины. На втором шаге при помощи иного метода приближение уточняется (корректируется). (Википедия)

Схемы предиктор-корректор заключается в следующем :

Вначале применяется явная аппроксимация (предиктор, на слайде схема сразу после названия). B - обычно, диагональная матрица. Новое n+1 решение (но неокончательно новое) вычисляется по этой схеме. Схема “предиктор” дает простое вычисление для ( с крышкой), считаем его начальным приближением для неявной схемы “корректор” (например, Кранка-Николсона) .

21.Неявные схемы Рунге-Кутты-Радо (Воропаева)

Из книги Ильина про диффуры, на лекции ничего не сказал

y’=f(t,y)

(не ильин:)

Суть простыми словами: в методе Рунге-Кутты в качестве узлов выбирать корни многочлена Радо

модельное уравнение: y’=ay

Разрывный метод Галёркина:

Тут Nt порядок метода галёркина вроде k из P^k

22.Выбор начальных приближений в неявных схемах (Адоньева) (Комментарии из видеолекции)

Простой снос

Для решения нестационарных задач есть один важный момент. Мы решаем задачу Коши, для t=0 задано решение и предположим мы используем неявные схемы (это главная для нас проблема). На каждом временном шаге нужно решать СЛАУ и для этой системы уравнений надо выбрать начальное приближение. Теория итерационных алгоритмов работает для любого начального приближения. Если мы лучшее начальное приближение возьмем, то будет меньше итераций. Мы решаем хорошие в каком-то смысле дифференциальные уравнения, гладкие решения, и если для 10-го временного шага нашли какое-то решение, то для 11 шага наверное оно очень сильно отличаться не будет.

Пусть найденное решение на n временном шаге, а начальное приближение для следующего временного шага . Функции гладкие, на соседних шагах с точностью до , если мало, то эти величины достаточно близки. Это простой снос .

Линейная интерполяция

В предположении гладкости можно использовать линейную интерполяцию. Можно взять еще предыдущий временной шаг (n-1). Простой отрезок ряда Тейлора по времени, остаточный член порядка тау квадрат, это будет точнее, чем простой снос, но требует хранения дополнительного массива данных.

23.Канонические представления итерационных методов. Модельные СЛАУ?

24.Общие характеристики итерационных методов. Блочные алгоритмы.

Для поточечного метода коэф. подавления ошибки - ( ), для блочного - 1-h².

Если D- диагональная матрица, то в методе Якоби операция D^-1 эквивалентна делению на число. Иначе ( если D как выше), то D^-1 будет требовать организации метода прогонки.

В конечном итоге, блочные методы сходятся в 2 раза быстрее, но каждая итерация требует реализации метода прогонки.

Матрица А имеет базис из собственных векторов. Представим А = D - L - U.

L и U не имеют ненулевых элементов на гл. диагонали. Выше мы рассматривали матрицу D как диагональную, но можно рассматривать как блочно-диагональную (т.е. D соответствует одному столбцу сетки).

Au=f => запишем метод Якоби. D - невырожденная, мы можем ее обратить, L и U уносим вправо и берем аппроксимацию с ними на предыдущем значении. Вообще блочный метод - неявный, но его частные случаи (например матрица D просто диагональная) могут быть явными. Чем больше элементов вне диагонали у D, тем труднее ее обращать, но итерационный метод будет быстрее сходится (чем сильнее неявность - тем быстрее сходимость). Можно метод усложнить и тем самым ускорить (блочный метод чебышевского ускорения).

25.Параллельные двучленные методы чебышевского ускорения (Семибратов).

Лекция 03.01.

Рассматривается задача Au=f. Задача дискретизируется, т.е. строим сетки. i - столбцы, j - строчки. Матрица аппроксимирует какой-то дифф-й оператор (например Лапласа, вспомните выч. методы). Пятиточечное уравнение (матрица 5-и диагональная).

e_ij - обозначаем диагональные, остальными буквами - недиагональные. Минусы перед коэф-ми ставим для того, чтобы сами коэф-ы были больше нуля. h - шаг сетки, если сетка неравномерная, то говорим шаг порядка h. Квазиравномерная сетка - это такая последовательность сеток, что при h -> 0 шаги сетки остаются одного порядка. Это очень хорошие сетки.

Модельная задача Дирихле. h_y и h_x - шаги по х и y, если шаги равны то просто пишем h (квадратная сетка). Рассматриваем квадратные сетки. Опечатка на слайдах: i меняется от 1 до I (и большое), j от 1 до J (нумерация узлов сетки). Для граничных узлов у нас задано краевое условие Дирихле (3 строчка на слайде). Матрицы А_1 и А_2 соответствуют аппроксимациям вторых производных по х и y. Матрицы имеют собственные числа . Здесь h = pi/(N+1). Минимальное с.з порядка h^2, максимальное - 4(1-h^2). Отношение минимального с.з. к максимальному называют числом обусловленности Cond(). Если мельчим сетку - число обусловленности увеличивается (матрица становится хуже). z_p,q - собственные векторы - произведение синусов (на слайде опечатка и стоит сумма).

Матрица А имеет базис из собственных векторов. Представим А = D - L - U. L и U не имеют ненулевых элементов на гл. диагонали. Выше мы рассматривали матрицу D как диагональную, но можно рассматривать как блочно-диагональную (т.е. D соответствует одному столбцу сетки). Au=f => запишем метод Якоби. D - невырожденная, мы можем ее обратить, L и U уносим вправо и берем аппроксимацию с ними на предыдущем значении. Вообще блочный метод - неявный, но его частные случаи (например матрица D просто диагональная) могут быть явными. Чем больше элементов вне диагонали у D, тем труднее ее обращать, но итерационный метод будет быстрее сходится (чем сильнее неявность - тем быстрее сходимость). Можно метод усложнить и тем самым ускорить (блочный метод чебышевского ускорения).

Блочный метод чебышевского ускорения. Вводим итерационный параметр тао. То, что стоит в первой скобке справа (предпоследняя строчка на слайде) - это невязка(она известна). (см билет 24 общие хар-ки итерационных методов).

Двучленный метод чебышевского ускорения.

Надо знать макс и мин с.з. матрицы A. Тогда можем построить двучленный периодический процесс чебышева. Периодический потому, что сначала мы вычисляем тао_1, тао_2, … тао_m, а потом они повторяются. P_m - нормированный полином Чебышева первого рода. T_m - классический многочлен Чебышева 1-го рода. Если меняется от до , то аргумент в скобке числителя меняется от -1 до +1. Числитель ограничен 1, а знаменатель как-то оценивается. Ошибка метода не будет превосходить модуля этого полинома P_m.

Число итераций n(eps_m) для того, чтобы уменьшить ошибку в eps раз не превосходит выражения указанного на слайде, где C - число обусловленности.

Число обусловленности равно h^(-2), тогда получается, что число итераций пропорционально 1/h. Что тут с устойчивостью? Она может нарушаться. Может случиться так, что в процессе выполнения итераций ошибка будет возрастать, притом достаточно сильно.

Про распараллеливание метода.

У нас матрица А по размерностям может быть очень большая (миллионы - миллиарды), но она разреженная (число ненулевых элементов в строке может быть небольшим: 10, 20, 30 ...). Для хранения таких матриц используется специальный формат. Существуют специальные библиотеки для умножения таких матриц (BLAS, MKL, SPAS). Библиотеки уже содержат параллельные алгоритмы, нам остается их только грамотно использовать.

26.Трёхчленные методы чебышевского ускорения

Распараллеливание и эффективность: умножение на невязку также присутствует (тоже м.б. сделано с помощью SPAS, BLAS), но здесь добавляется разность векторов, нужно запоминать n-1 посчитанный член. На некоторых конфигурациях этот метод может оказаться гораздо медленнее предыдущего.

27.Связанные двухчленные алгоритмы чебышевского ускорения

По трудоёмкости сопоставима с трёхчленной (вроде, умножение на матрицу присутствует в нескольких местах, но на деле происходит только один раз). Связанные двухчленные немного более устойчивы, чем 3-членные.

28.Методы Зейделя и последовательной верхней релаксации (Добшик)

Релаксационные методы — частный случай итерационных методов решения СЛАУ. Итерационные методы являются особенно эффективными при решении систем с большим количеством неизвестных (порядка 1000 и более).

В общем случае сначала задаётся некоторый вектор x0, называемый начальным приближением. В общем случае начальное приближение может быть любым. От него строится последовательность x1, x2,...,xk и так далее, где число k называют номером итерации. Итерационный метод называется одношаговым, если каждое последующее итерационное приближение строится только по одному предыдущему:

Если - линейная функция, то соответствующий итерационный метод называется линейным. Согласно определению, можно получить каноническую форму записи одношагового итерационного метода:

Если , то соответствующий метод называется явным, в противном случае – неявным.

Изложение метода

Релаксационные методы являются стационарными и неявными решения СЛАУ. Пусть нам требуется решить систему линейных алгебраических уравнений:

Представим матрицу в виде суммы трёх матриц , и :

,

Где - нижнетреугольная, - верхнетреугольная, - диагональная

Каноническая форма релаксационного метода записывается следующим образом

Где - некий числовой параметр.

Метод Зейделя

Канонический вид метода Зейделя:

Преобразовав эти уравнения, приведём их к следующему виду:

Отсюда полученная система будет выглядеть так:

Выразим из этой системы новое итерационное приближение:

где

Таким образом i-я компонента (k+1)-го приближения вычисляется по формуле:

Условие сходимости и оценка погрешности метода

Имеет место следующая теорема. Пусть

где A - симметрическая положительно определенная матрица и . Тогда метод релаксации является сходящимся для любого начального приближения.

Если для погрешности итерационного метода справедливо неравенство: , где то метод сходится со скоростью геометрической прогрессии.

Справедлива теорема (оценка погрешности одношаговых итерационных методов). Пусть матрицы A и B симметричны и положительно определены и существуют такие положительные константы и _2, что . Тогда итерационный метод, задаваемый уранением , где сходится для любого начального приближения со скоростью геометрической прогресии с коэффициентом q, где , .

Метод последовательной верхней релаксации является одним из наиболее эффективных и широко используемых итерационных методов для решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами А. Этот метод часто называют SOR-методом. Частично популярность SOR-метода можно объяснить его простотой и тем, что он хорошо известен широкому кругу прикладников.

Суть метода релаксации состоит в следующем. После вычисления очередной i-ой компоненты (k+1)-го приближения по формуле метода Зейделя

рис 6.2

29.Неявные методы переменных направлений

пятидиагональную А можно представить в виде суммы двух трёхдиагональных.

m-типа h^2, M - типа 4.

30.Проекционные методы Качмажа

http://www.mathnet.ru/links/f2fbba16368b99f753263b3c9f9c96b8/sjim219.pdf

31.Проекционные методы Чиммино

ftp://ftp.pdmi.ras.ru/pub/publicat/znsl/v472/p103.pdf

32.Итерационный метод наискорейшего спуска. Итерационный метод минимальных невязок

33.Метод сопряжённых градиентов. Метод сопряжённых невязок

34.Мультипредобусловленные методы полусопряженных направлений (Киселёва)

https://icmmg.nsc.ru/sites/default/files/pubs/ilinslau.pdf

Математическая проблема решения СЛАУ:

Но симметричность при этом не требуется. Иногда матрицы представляются в блочной форме: где Ωq означает множество номеров ненулевых матричных вычислительных блоков, расположенных в q-й блочной строке. В случае сеточных алгебраических уравнений блочное представление СЛАУ можно наглядно ассоциировать с геометрической декомпозицией сеточной расчётной области Ω на непересекающиеся подобласти Ωq : Ω=Ω1 +...+ΩР, где Ωq∩Ωr =0 приq≠ r (5)

Соотношения (5) можно интерпретировать также как алгебраическую декомпозицию, если Ωq рассматривать просто как множество из Nq индексов, соответствующих подвектору uq или fq .

Главные современные подходы к решению больших (с числом неизвестных N порядка – ) разреженных (с преимущественно нулевыми элементами) СЛАУ – это предобусловленные итерационные методы в подпространствах Крылова. Для решения несимметричных систем рассмотрим эквивалентные по скорости сходимости итераций методам обобщенных минимальных невязок, методы полусопряженных направлений, являющиеся непосредственным обобщением методов сопряженных градиентов и сопряженных невязок на несимметричные СЛАУ. Формальное изложение этих итерационных процессов в “мультипредобусловленном” варианте с возможностью использования на каждом шаге по нескольку предобуславливающих матриц (P предобуславливатель для матрицы A, если у матрицы число обусловленности меньше, чем у A ), количество и форма которых при этом может изменяться. Такие методы относятся к классу блочных, поскольку они используют по нескольку направляющих векторов, а порождаемые ими крыловские подпространства естественно рассматривать как блочные. вектор невязки (ошибка приближенного равенства)

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

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