Метод Гаусса-Зейделя. Это наиболее распространённый из итерационных методов

Это наиболее распространённый из итерационных методов. В нём каждое приближение вычисляется по формуле:

, ,

где – номер корня,

– порядок системы,

– номер текущей итерации.

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

Критерий близости можно, например, задать в следующем виде:

(1) , где – заданная допустимая погрешность.

Здесь определяется максимальное значение разности для всех . При выполнении критерия итерационный процесс следует остановить.

Этот критерий по абсолютным отклонениям можно заменить критерием по относительным разностям т.е. критерий близости будет выглядеть следующим образом:

(2)

При выполнении либо условия (1), либо условия (2) итерационный процесс метода Гаусса-Зейделя называется сходящимся.

Достаточными условиями сходимости итерационного процесса по методу Гаусса-Зейделя являются следующие условия:

1. Модули диагональных коэффициентов для любого уравнения системы должны быть не меньше сумм модулей всех остальных коэффициентов: , . При этом хотя бы для одного уравнения неравенство должно выполняться строго.

2. Система линейных уравнений должна быть неприводима.

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

Блок-схема метода Гаусса-Зейделя

Блок-схема приведена на рис. 3.4 a. и 3.4 б. На первом рисунке изображены дейсствия, связанные с вводом исходных данных и подготовкой к вычислениям. Начальное приближение принимается равным нулю, а счётчику количества итераций (ITER) присваивается 1.

Переменная BIG используется для того, чтобы определять наибольшее значение разности между и . Сначала этой переменной присваивается значение нуль, а затем с ней сравниваются абсолютные значения разностей .

Рис. 3.4.a. Блок-схема метода Гаусса-Зейделя

Рис.3.4.б. Блок-схема метода Гаусса-Зейделя (продолжение)

Если какая-либо разность оказывается по абсолютной величине больше BIG, то прежнее значение BIG заменяется этой разностью. После вычисления всех наибольшая разность будет равна значению переменной BIG.

Затем в блок-схеме следует группа действий, с помощью которых вычисляется сумма всех членов уравнения, кроме диагонального. По ходу программы удобнее сначала вычислять и суммировать члены, стоящие перед диагональным (т.к. в них используются новые значения ), а уже потом – члены, идущие после него (т.к. в них используются старые значения ). Необходимо несколько усложнить логику, т.к. в первом и соответственно в последнем уравнениях отсутствуют элементы, стоящие соответственно до и после диагонального.

В правой части блок-схемы указана группа действий, начинающаяся с вычисления нового значения ; определяется максимальная разность и запоминается новое значение , которое вычисляется под именем TEMP.

Если это было не последнее уравнение, то мы увеличиваем индекс i и начинаем вычислять очередное приближение для следующего неизвестного. В случае последнего уравнения мы сравниваем максимальную разность с и печатаем результаты, если процесс сошёлся.

Но процесс в действительности не всегда сходится. Причины могут быть различные – от ошибок в программе до неверных исходных данных. Поэтому в начале программы было введено целое число MAX, которое определяет максимально допустимое число итераций. (Ориентировочно MAX = 50 для системы из 50 уравнений.) Тогда, если по какой-то причине процесс не сошёлся, ЭВМ не будет считать бесконечно долго.