Итерационные методы решения систем линейных алгебраических уравнений

Будем полагать, что матрица А невырожденная. В наиболее про­стой форме итерационный метод решения системы АХ = В можно записать в виде вычислительной процедуры:

где F^(k) — некоторая последовательность операторов, действующих для заданных A и В.

Вектор называют начальным вектором (начальным прибли­жением), а векторы = — X, где X — точное решение, на­зывают векторами ошибок. Векторы = - В называют векторами невязок.

Широко распространено в литературе по электротехнике описание метода простой итерации, который в развернутой форме имеет следу­ющий вид:

 

 

где последовательность k итераций завершается, если все элементы вектора невязок меньше заданной точности расчета 1,2,…, n (получено приемлемое решение), либо превышено зара­нее заданное количество итераций .

В матричной форме

,

где .

Для ускорения сходимости в правой части приведенных выраже­ний возможно использовать не только значения неизвестных х_р, вы­численные на предыдущих итерациях, но также рассчитанные ранее на этой же итерации и имеющие индексы р < i. В этом случае гово­рят о методе ускоренной итерации, часто называемом также мето­дом Гаусса-Зейделя. Схема решения имеет следующий вид:

,

i =1, 2, …, n; k =1, 2, ….

В матричной форме

,

где U, L — верхняя и нижняя треугольные матрицы, содержащие нули на главной диагонали, и такие, что А — L + D + U.

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

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

Методы простой и ускоренной итерации сходятся к точному реше­нию, если матрица А имеет диагональное преобладание. В противном случае решение не гарантировано.

При построении реальных вычислительных схем часто пытаются ускорить процесс решения введением специальных ускоряющих коэф­фициентов.

Тогда полученное значение переменной x_i^(k) можно скорректировать следующим образом:

 

где , - коэффициенты ускорения и замедления, часто принимают = 1,3, =0,4, - разность решений на двух итерациях.

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

Такой подход требует выполнения дополнительных операций и до­полнительной памяти для хранения вектора приращений переменных Y.