Итерационные методы

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

Найдем решение системы линейных уравнений

(1)

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

, отличные от :

(2)

Введем обозначения: - погрешности значений неиз­вестных, - невязки, т. е.

, , (3).

Вычитая каждое уравнение системы (2) из соот­ветствующего уравнения системы (1), с учетом обозначений (3) получаем

(4)

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

Таким же способом можно найти новые поправки к решениюи следующие приближения переменных и т. д. Процесс продолжается до тех пор, пока все очередные значения погрешностей (поправок) не станут достаточно малыми.

Рассмотренный процесс уточнения решения прёдставляет фактически итерационный метод решения системы линейных уравнений. При этом заметим, что для нахож­дения очередного приближения, т. е. на каждой итера­ции, решаются системы уравнений вида ,(4) с одной и той же матрицей, являющейся матрицей исходной си­стемы (1); при разных правых частях. Это позволяет строить экономические алгоритмы. Например, при использовании метода Гаусса сокращается объем вычислений на этапе прямого хода.

Решение систем уравнений с помощью рассмотренного метода, а также при использовании других итерационных методов сводится к следующему. Вводятся исходные данные, например коэффициенты уравнений и допустимое значение погрешности. Необходимо также задать начальные приближения значений неизвестных. Они либо вводятся в ЭВМ, либо вычисляются каким-либо спо­собом (в частности, путем решения системы уравнений с помощью прямого метода). Затем организуется цикли­ческий вычислительный процесс, каждый цикл которого представляет собой одну итерацию. В результате каждой итерации получается новые значения неизвестных. При малом (с заданной допустимой погрешностью) измене­нии этих значений на двух последовательных итерациях процесс прекращается, и происходит вывод значений не­известных, полученных на последней итерации.

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