Метод релаксации по линиям

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

Соответствующие формулы метода релаксации по линиям имеют вид /22/

(13)

(14)

Здесь n - номер итерации, ω- параметр верхней релаксации.

Из сравнения формул (13) и (I) ясно, что значения сеточной функции в порядке возрастания индекса j можно вычислить с помощью метода прогонки в i -х узлах j -й строки. При этом при расчете прогоночного коэффициента β величина q определяется формулой

(15)

коэффициенты которой представлены своими значениями, вычисляемыми заранее в соответствии с выражениями

где

На основании вычисленных значений определяется очередное приближение к решению в узлах j -й строки сетки, которое в свою очередь используется для расчета коэффициента q_i,j+1, а следовательно, и коэффициентa β_i+1,j+1, а следовательно, и значений , в узлах следующей j+1 -й строки.

Таким образом, метод релаксации по линиям (в данном случае по строкам) представляет собой неявный метод последовательных смещений по линиям сетки, и имеет место задача реализации этих последовательных смещений на параллельных вычислительных систе­мах. Установим соответствующую организацию параллельного вычислительного процесса. Она основана на обработке строк сетки по принципу конвейера. Процессоры вступают в работу поочередно, начиная с ПБ₁. Он обрабатывает информацию в узлах первой строки с помощью процедуры последовательной прогонки в соответствии с организацией вычислений, описанной в п.1.1. В частности, ПБ₁ по формуле (15) вычисляет значения коэффициента q_i,1, i=1,…,I, располагая значениями y_i,0 (заданные граничные условия) и (заданная нулевая итерация). Затем вычисляется прогоночный коэффициент β_i+1,1, i=1,…,I. Наконец, вычисляются значения сеточных функций по формулам (2) и (14). Соответственно с этого момента, располагая вычисленными значениями первой итерации решения и значениями нулевой итерации, можно перейти к аналогичному расчету значений первой итерации решения в узлах второй строки. Чтобы избежать простоя включенных в работу ПБ эти расчеты следует возложить такжена ПБ₁. После их выполнения определены значения и очевидно (см.формулу (15)) появляется возможность вычисления значений , второй итерации в узлах первой строки, что возлагается на ПБ₁, и значений первой итерации в узлах третьей строки, что требует включения в работу следующего процессора ПБ₂ ,в который поступает значение из ПБ₁ с помощью непосредственных связей, объединяющих соседние ПБ многопроцессорного вычислителя (рис.4). После вычисления значений , , ПБ₁, ПБ₂ вычисляют значения ,(для этого из ПБ₂ в ПБ₁ поступает вычисленное ), а затем снова возвращаются к обработке информации в узлах первой и третьей строки, определяя величины , . При этом включается в работу ПБ₃ и одновременно вычисляется значение первой итерации в узлах пятой строки и т.д. Таким образом, ПБ j предназначен для вычислений в узлах двух строк сетки: j– й и j+1- й и соответственно используется ПБ. Причем, для вычисления значений ПБ j принимает информацию ()из ПБ j-1, а при вычислении ПБ j принимает информацию ПБ j+1.

Сформулированный параллельный сеточный алгоритм метода релаксации по линиям иллюстрируется диаграммой работы ПБ на рис.11 где n -й импульс на j - й оси абсцисс обозначает вычисление на n- й итерации величин q, β, y в узлах j - й строки сетки, а необходимая циркуляция информация отражена пунктирными стрелками. Назовем процесс вычисления одной итерации в узлах одной стро­ки с помощью одного ПБ операционным тактом. Его длительность соответствует длительности импульсов на рис. 11, из которого ясно, что информация в узлах последней J - й строки сетки начнет обраба­тываться с задержкой J -1 операционных тактов относительно нача­ла вычислений. Кроме того, скважность импульсов равна двум и для вычисления всех n₀ итераций в узлах последней J - й строки потребуется еще 2n₀ операционных тактов, т.е. общее время вычислений составит 2n₀ +J-1 операционных тактов. Оценим его через время одного умножения и сложения. Для вычисления в одном узле сетки величины q необходимо время 2 (см. формулу (15)), величины β или - время (см. п. 1. 1), величины y - время несколько больше (так как в формулу (14) кроме умножения и сложения входит и вычи­тание). Однако, для наиболее вероятного использования ПБ с парал­лельно- последовательными алгоритмами (микропроцессоры) время ум­ножения на порядок превышает время сложения, и время вычисления значения y близко к . Таким образом, время вычислений в одном узле сетки оценивается значением 5, а длительность операционного такта - значением 5I . Следовательно, общее время параллельной реализации с пoмoщью ПБ n₀ итераций метода релаксации по линиям определяется формулой*

(16)

Очевидно, что для однопроцессорной ЭВМ время реализации метода релаксации по линиям можно оценить величиной 5n₀IJ . Отсюда с уче­том формулы (16) имеем ускорение и эффективность рассмотренного параллельного сеточного алгоритма

Метод релаксации по линиям можно определить и в виде последовательных смещений с прогонкой по столбцам узлов сетки. Выбор направлений прогонки при влияет на общее время решения. В частности, в работе /22/ в результате численного эксперимента по решению уравнения Лапласа в прямоугольнике получено распределение числа итераций n₀ метода релаксации по линиям в зависимости от значений I, J (табл.2). Из этих данных видно, что n₀ меньше, если прогонку вести вдоль линий сетки, имеющих большее число узлов.

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

Дата добавления: 2014-01-14