3 Глава Параллельные вычисления при численном решении уравнений математической физики

2.3 Примеры решения системы линейных уравнений методом Гаусса

Пример 1. Найти общее решение системы линейных уравнений методом Гаусса:

Матричный вид записи: Ax=b, где

Для решения системы, запишем расширенную матрицу:

Обозначим через a_ij элементы i-ой строки и j-ого столбца.
Исключим элементы 1-го столбца матрицы ниже элемента a_{1 1}. Для этого сложим строки 2,3 со строкой 1, умноженной на -2/3,-1/2 соответственно:

Исключим элементы 2-го столбца матрицы ниже элемента a2 2. Для этого сложим строку 3 со строкой 2, умноженной на 9/8:

Делим каждую строку матрицы на соответствующий ведущий элемент (если ведущий элемент существует):

Из вышеизложенной таблицы можно записать:

Подставив верхние выражения в нижние, получим решение.
Решение:

, , .

Пример 2. Найти общее решение системы линейных уравнений методом Гаусса:

Матричный вид записи: Ax=b, где

Для решения системы, построим расширенную матрицу:

Обозначим через a_ij элементы i-ой строки и j-ого столбца.
Исключим элементы 1-го столбца матрицы ниже элемента a₁₁. Для этого сложим строки 2,3 со строкой 1, умноженной на -1/5,-6/5 соответственно:

Исключим элементы 2-го столбца матрицы ниже элемента a₂₂. Для этого сложим строку 3 со строкой 2, умноженной на -1:

Делим каждую строку матрицы на соответствующий ведущий элемент (если ведущий элемент существует):

Выразим переменные x₁, x₂ относительно остальных переменных.

где x₃, x₄− произвольные действительные числа.
Подставив верхние выражения в нижние, получим решение.
Решение:

где x₃, x₄− произвольные действительные числа.
Векторный вариант решения:
Запишем вышеизложенное решение, представив свободные переменные в виде тождеств:

Тогда векторное решение можно представить так:

где x₃, x₄− произвольные действительные числа.

2.4 Методы Адамса

Для того чтобы получить и_п+{ при заданном и_т используя схему Рунге — Кутта, необходимо вычислить функцию f(x, и) s раз в некоторых промежуточных точках. Эти вычисленные значения далее больше не используются. В схемах Адамса для вычисления следующего значения г/„₊₁ используется не только значение и_ю но и несколько предыдущих значений. В дополнение вычисление значения и_п+ требует только одного вычисления функции f{x_y и) независимо от порядка разностной схемы.
Схемы Адамса могут быть построены следующим образом. Пусть и(х) есть решение задачи (7.14). Введем обозначение f(x, и(х)) = F(x), тогда

Известно, что существует единственный полином РДж) степени не выше чем k, принимающий в точках х_т х_п_, ..., x_n_k заданные значения F(x_n), F(x_n_)> ..., F{x_n^) соответственно (глава 8). Для достаточно гладкой функции F(x) такой полином отклоняется от F(x) на интервале [х_т х„₊₁] на величину порядка /г т.е.

Тогда явные схемы Адамса имеют следующий вид:  Для k = О полином

и выражение (7.28) превращается в (7.22) (схема Эйлера). Для k = 1

И

Аналогичным способом можно получить разностные схемы для & = 2, 3,...
В общем, явные схемы Адамса могут быть представлены в следующем виде:

где параметры приведены в табл. 7.3.
Таблица 73
Коэффициенты для явных схем Адамса

Порядок аппроксимации, p	ak,k = 0, ...,p - 1
1	1
2	3/2	-1/2
3	23/12	-16/12	5/12
4	55/24	-59/24	37/24	-9/24

Для того чтобы начать вычисления по схеме (7.29), когда р> 2, необходимо знать р значений и% т = 0,..., р - 1, по только Uq¹⁾ = а задано. Эти недостающие значения могут быть вычислены либо по схеме Рунге — Кутта соответствующего порядка, либо разложением решения в ряд Тейлора в точке х = а. Рассмотрим эту возможность более детально.
Значение и(х_т) = и(а + mh) вычисляется на основе следующего разложения:

Используя уравнение (7.14), выразим производные функции и{х) через функцию f(x, и):

Тогда начальные значения определяются но формуле

Пример 7.5 (вычисление начальных значений в схеме Адамса)
Рассмотрим дифференциальную задачу

Предположим, мы хотим использовать схему Адамса чет-
(а) (а) (а)
вертого порядка, поэтому нам нужно знать и ,щ ' и щ , чтобы начать процесс вычислений. Производные d^ku/dx^k выражаются следующим образом:

Тогда начальные значения вычисляются по формулам

Одной из особенностей методов Адамса является то, что для определения и_п+ необходимо вычислить только значение f(x_m и_п), так как значения f(x_n_и_п__t), f(x_n_2> w„_₂), ... уже были вычислены в процессе определения и_п, и_{п Лу}... Таким образом, преимущество схем Адамса над схемами Рун- ге — Кутта состоит в том, что они требуют меньшего количества операций на один шаг вычислительного процесса.
Основные недостатки схем Адамса: требуется специальная процедура для вычисления дополнительных начальных значений, вычислительная схема усложняется при неравномерном шаге разностной сетки. Использование переменного шага необходимо в областях резкого изменения решения. Условия устойчивости явных схем Адамса, для модельного уравнения (7.16), приведены в Приложении В. Эти условия показывают, что схемы Адамса имеют более строгие ограничения на шаг разностной сетки по сравнению со схемами Рунге — Кутта.
Если мы будем использовать точку х^+ для построения полинома Рь(х) в формуле (7.28), то получим неявные схемы Адамса. Они могут быть представлены в следующей форме:

где параметры b* приведены в табл. 7.4.
Таблица 74
Коэффициенты для неявных схем Адамса

Порядок аппроксимации, р	Ьк,к = 0.....р - 1
1	1
2	1/2	1/2
3	5/12	8/12	-1/12
4	9/24	19/24	-5/24	1/24

Неявные схемы Адамса дают более точные результаты, чем явные схемы того же порядка. В дополнение неявные схемы имеют менее строгие ограничения на шаг разностной сетки по сравнению с явными схемами (схемы первого и второго порядка — безусловно, устойчивы, Приложение В).
Однако неявные схемы не эффективны с точки зрения вычислительных затрат. В общем случае невозможно выразить и_п+1 из разностного уравнения (7.30). Вместо этого мы должны решить нелинейное уравнение 
Относительно и_п+, используя тот или иной итерационный метод (глава 2), а это значительно увеличивает объем
вычислений. Тем не менее неявные схемы могут быть очень
%/
полезны в некоторых ситуациях, которые мы рассмотрим позднее.

• 
  11еявныс схемы можно использовать для повышения точности приближенного решения, полученного явным методом. Комбинация явной и неявной схемы называется методом предиктор-корректор. Общая процедура вычислений может быть организована следующим образом:
  
• 
  1) вначале вычислим приближенное решение й^, используя явную схему Адамса порядка р в качестве предиктора:
  

2) затем это приближение уточняется неявной схемой Адамса порядка р (корректор):

Из построения видно, что схемы предиктор-корректор являются явными схемами и, следовательно, они условно устойчивы, но эти схемы имеют менее строгие ограничения на шаг разностной сетки по сравнению с явными схемами Адамса (Приложение В).

Заключение

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

Литература

1. Самарский А.А. Введение в теорию раз ностных схем. М.: Наука, 1971.
2. Молчанов И.Н. Введение в алгоритмы параллельных вычислений. Киев: Науко ва думка, 1990.
3. Вальковский В.А., Комов В.Е., Марчук А.Г., Миренков Н.Н. Элементы параллельно го программирования. М.: Радио и связь, 1983.
4. Миренков Н.Н. Реализация продольно поперечных прогонок на ВС "Минск 222" // Вычислительные системы. 1968. Вып. 30.
5. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука. 1978.
6. Головашкин Д.Л., Дегтярев А.А., Сойфер В.А. Моделирование волноводного рас пространения оптического излучения в рамках электромагнитной теории// Ком пьютерная оптика. 1997. T.17.