и нужно решить системуМетод простой итерации – один из простейших итерационных методов. Хотя метод Якоби не является приемлемым для большинства задач, он представляет собой удобную отправную точку для обсуждения итерационных методов.
Пусть А – невырожденная матрица
и нужно решить систему
,
где диагональные элементы матрицы А ненулевые. Тогда метод Якоби имеет вид
(3)
где верхние индексы указывают
номер итерации и предполагается, как и для всех итерационных методов, что
представляют собой заданную аппроксимацию решения системы .
Для многих целей удобно
переписать (3) в матричной форме. Пусть
-
диагональная матрица, образованная диагональными элементами А, и пусть
, т.е.
представляет собой разложение матрицы на диагональную и
недиагональную части. Тогда мы можем записать (*) в виде:
. (4)
Из (4) ясно, что все значения
можно вычислять параллельно; именно по этой причине метод
Якоби (простой итерации) иногда рассматривается в качестве прототипа
параллельного метода.
Рассмотрим вопросы, связанные с параллельными вычислительными системами.
Предположим, что параллельная
система образована сетью из p процессоров,
упорядоченных от 0 до p-1 и каждый
процессор связан со всеми процессорами. Предположим, что
.
Тогда естественно поручить каждому процессору обработку m
неизвестных. Это можно сделать множеством
способов. Один из простейших – распределить первые m
неизвестных на нулевой процессор, следующие m
неизвестных на первый и т.д.
В этом случае вычисления на
каждом процессоре будут выполняться следующим образом: вычисляется
m неизвестных
в процессоре pi; посылается значение
остальным процессорам.
Таким образом, на каждом этапе вычислительный шаг, реализуемый по формулам (4), сопровождается последующей передачей обновленных значений итерационного приближения всем процессорам, им эти значения потребуются для выполнения следующей итерации. Такое упорядочение демонстрирует идеальный параллелизм метода Якоби.
Для того, что обеспечить
корректное выполнение итераций Якоби, в предложенную вычислительную схему
необходимо ввести механизм синхронизации. Например, вычисление следующих
не может быть начато до тех пор, пока не будут получены
переменные
от остальных процессоров. Однако это не обязательно нанесет
ущерб итерационному процессу в целом, и в некоторых случаях с точки зрения общих
затрат может оказаться выгодным применять итерационные методы в асинхронном
варианте.
Применяя любой итерационный
метод, необходимо проверять сходимость итерационных приближений. Если
-
последовательность итерационных приближений, то часто
используется следующий метод проверки:
, где
- обозначает норму.
На рис. 59 приведен листинг параллельной Фортран-программы метода Якоби для решения СЛАУ.
