Каноническая запись итерационных процессов.
Лекция №14 Итерационные методы решения СЛАУ Методы решения уравнения Пуассона. Метод простых итераций. Рассмотрим итерационный метод (т.е. метод последовательных приближений) решения системы линейных уравнений:
Будем считать, что решение задачи (1) существует и единственно. Различные варианты метода простых итераций связаны с переходом от системы (1) к эквивалентной системе
Итерационный процесс строим следующим образом:
где - начальное приближение, - номер приближения. Укажем условия сходимости метода последовательных приближений (3). Теорема 1. Для сходимости итераций (3) к решению системы (2) достаточно, чтобы в какой‑либо норме выполнялось условие . Тогда независимо от выбора
где - точное решение системы (2). Доказательство При подстановке точного решения в (2) оно обращается в тождество:
Вычитая его из уравнения (3), (т.е. ), получим:
Здесь - погрешность -го приближения. Оценивая погрешность по какой‑либо норме (с которой согласована норма матрицы), получим: Ясно, что при . Теорема 2. (без доказательства) Для сходимости итерационного процесса (3) к решению системы (2) необходимо и достаточно, чтобы все собственные значения матрицы по абсолютной величине были меньше единицы. Опираясь на формулу (4), можно получить априорную оценку числа приближений
Разрешая последнее неравенство относительно , получим:
(Квадратные скобки означают ближайшее сверху целое число от того, которое заключено в скобки). Этой оценкой можно воспользоваться, если мажорировать . Упражнение. Показать, что в условиях Теоремы 1 справедлива оценка:
Задумаемся о том, зачем нужны итерационные методы, если мы можем найти решение, пользуясь, например, какой‑либо модификацией метода Гаусса. Ответ на это вопрос становиться понятным, если оценить эффективность различных подходов с точки зрения вычислительных затрат. Метод Гаусса (в простейшей интерпретации), при требует выполнения приблизительно арифметических операций. Метод итераций реализуется приблизительно за операций ( умножений и сложений связано с умножением матрицы на вектор , - число приближений). Если допустимая погрешность достигается при , то метод итераций становиться предпочтительней. Замечание. В практических задачах, как правило, . Кроме того, методы итераций могут оказаться предпочтительней с точки зрения устойчивости вычислений, т.е. в смысле влияния вычислительных погрешностей на результаты расчетов. Метод Якоби. Запишем каждое уравнение системы в виде, разрешенном относительно неизвестного с коэффициентом на главной диагонали матрицы :
Таким образом, мы переписали в виде , с матрицей Введём в рассмотрение диагональную матрицу:
то
Действительно, , где - алгебраическое дополнение к элементу , поэтому
Итерационный процесс, определенный такой матрицей , называется методом Якоби. Фактически вычисления проводятся по формулам
Утверждение. Для сходимости метода Якоби достаточно, чтобы для исходной матрицы A имело место диагональное преобладание, т.е. чтобы
В самом деле, тогда условие теоремы 1 выполнено для нормы :
Пусть теперь дано двумерное уравнение Пуассона в прямоугольнике
Выбирая для простоты сетку, равномерную и одинаковую по и , получим пятиточечный шаблон (Рис. 1):
Тогда в узле получим:
Итерационный процесс Якоби здесь реализуется следующим образом: 1. Значения функции на границе заданы, известны; 2. Зададим некоторое начальное приближение функции во внутренних узлах (близость этого значения к решению часто бывает очень важна); 3. Вычисляем по окружающим точкам нулевого приближения: и на границе, а также и ; 4. Затем по , и , и т.д. до , затем по аналогии и т.д После последовательного прохождения по всем линиям от до , от до , , до один цикл итераций выполнен. Число арифметических операций на шаге равно . Ясно, что при вычислении удобно воспользоваться уже известным значением с первого шага итерации. В этом случае погрешность предыдущей итерации последовательно оттесняется слева направо и снизу вверх. Такая модификация итерационного процесса называется методом Зейделя. Метода Зейделя Формулы метода Зейделя имеют вид:
Если представить матрицу в виде суммы ( - нижняя треугольная, верхняя треугольная и диагональная матрицы с элементами матрицы ), то методу Зейделя соответствует матрица: (для метода Якоби ). Можно доказать, что метод Зейделя гарантированно сходится, если выполнено условие диагонального преобладания матрицы A или матрица является симметричной () и положительно определенной. В одинаковых условиях (диагональное преобладание) метод Зейделя сходится примерно в два раза быстрее метода Якоби ( итераций и итераций). Для оценки сходимости итерационных методов часто используются модельные (тестовые) задачи. При решении пятиточечного уравнения Пуассона (схема “Крест”), возможна реализация не точечного, а “блочного” метода Зейделя. В этом случае уравнения записываются в виде: при :
При этом заданы и - граничные условия. Система решается методом прогонки (что можно сделать для любых граничных условий, а не только первого рода), и системе сеточных функций присваивается новое значение “ - той итерации”. Затем решается система уравнений при :
с граничными условиями справа и слева. При этом берется с уже посчитанного уравнения на линии , а - с предыдущей итерации. Таким образом, погрешность (невязка) “блочно”, линиями оттесняется “снизу вверх”.
После проведения первой итерации по строкам () эффективно выполнить первую итерацию с прогонками по столбцам (). Таким образом, происходит “утрясание” как в “решете” с фиксированными граничными условиями на краях. В случае граничных условий 2 или 3 рода (Рис. 2) сходимость итерационного процесса резко замедляется по вполне понятным причинам.
Каноническая запись итерационных процессов. Для решения различных линейных схем множество итерационных схем можно записать в канонической форме: - в этом случае это явные итерационные процессы, - неявные итерационные процессы, - стационарные итерационные процессы. Мы рассмотрели: 1) - метод Якоби. 2) - метод Зейделя.
Чтобы ускорить итерационный процесс, видоизменяют метод Зейделя, вводя итерационный параметр так, чтобы
Такой метод называется методом релаксации. Метод Зейделя соответствует значению . Если , то итерационный процесс называется методом верхней релаксации. Здесь стационарный неявный итерационный процесс. Условия сходимости: и . Скорость сходимости зависит от параметра . Существуют теоретические оценки для и скорости сходимости, но их применение требует знания спектра оператора , который не всегда легко найти. Поэтому на практике параметр подбирают так, чтобы минимизировать число итераций. Это особенно удобно, если решается класс однотипных задач. Для примера рассмотрим применение метода верхней релаксации в одной сложной численной схеме (нелинейные уравнения Навье - Стокса), где на каждом шаге по времени необходимо решать эллиптическое уравнение Пуассона
с граничными условиями первого рода. Запишем разностную схему в виде:
В данном случае используются цилиндрические координаты и неравномерная сетка, но это приводит лишь к появлению зависящих от индекса и прогоночных коэффициентов. Скорость сходимости процесса сильно зависит от нулевого начального приближения, за которое принято значение на прошлом шаге по времени.
Сначала, как и в методе Зейделя, выполняются прогонки по строкам от до . Вторая часть итерации состоит в выполнении прогонок по столбцам. Выполняя прогонку при (), вычисляем новое значение , но в ячейки заносим не это значение, а значение
При - это блочный метод Зейделя. При берется с некоторым “весом” предыдущей итерации. (Например, при : - запаздывание). При берется с избыточным “весом” с новой - той итерации. (Например, при : ) Предположим, необходима относительная точность вычислений:
На первых шагах итераций берется , затем, когда наступает условие , значение меняется на , а когда или , то можно взять , и итерации быстро сходятся до .
Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|