РЕШЕНИЕ УРАВНЕНИЙ МЕТОДОМ ИТЕРАЦИЙ

Итерационные методы (методы последовательных приближений) решения систем Ax = b являются бесконечными методами и вычисляют только приближенные ответы. Их эффективно применяют для решения задач большой размерности, когда использование прямых методов невозможно из-за ограничений в доступной оперативной памяти ЭВМ или из-за необходимости выполнения чрезмерно большого числа арифметических операций. Большие системы уравнений, возникающие в приложениях, как правило, разряженные. Итерационные методы привлекательны для разряженных матриц, поскольку они требуют гораздо меньше оперативной памяти, чем прямые методы, и могут быть использованы, несмотря на то, что требуют больше времени на исполнение.

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

По-прежнему рассматриваем систему линейных алгебраических уравнений:

Ax = b (1)

Определение 1. Линейным одношаговым итерационным методом называют метод вида

х_k+1 = B_k∙x_k + g_k, (2)

где k – это номер итерации. Если матрица B_k и вектор g_k зависят от номера итерации, то метод называется нестационарным, в противном случае – стационарным.

Чтобы связать метод (2) с системой (1), поступают следующим образом. От итерационных методов требуют, чтобы после подстановки в них точного решения x = A^-1b системы (7.1) получалось тождество. Итак,подставляя x = A^-1b в (2), имеем

A^-1b = B_k∙ A^-1b + g_k.

Отсюда

g_k = (Е - B_k) A^-1b = С_kb,

где через C_k обозначили матрицу (E - B_k)A^-1. Следовательно, линейный одношаговый итерационный метод для решения системы (1) имеет вид

х_k+1 = B_k∙x_k + С_kb, С_kA+ B_k = E, k = 0,1,... (3)

Первый вопрос, который возникает при применении методов последовательного приближения, это вопрос сходимости.

Для сходимости нестационарного одношагового итерационного метода (3) достаточно, чтобы нормы всех матриц B_i были меньше единицы: || B_i ||<1, i = 0,1,...,m.

Рассмотрим одношаговый стационарный метод

х_k+1 = B∙x_k + Сb, СA+ B = E, k = 0,1,... (4)

Для сходимости стационарного метода (4) необходимо и достаточно, чтобы все собственные числа матрицы B по модулю были меньше единицы.

Для сходимости стационарного метода (4) достаточно, чтобы какая-либо из норм матрицы B была меньше единицы.

Метод простой итерации рассмотрен в вопросе 8. Рассмотрим еще один итерационный метод.

МЕТОД ЗЕЙДЕЛЯ

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

х₁ = (1/a₁₁)(b₁ – а₁₂х₂ – … – а_1nx_n)

х₂ = (1/a₂₂)(b₂ – а₂₁х₁ – … – а_2nx_n) …............ (1)

x_n = (1/a_nn)(b_n – а_n1х₁ – … – а_n(n-1)x_n-1)

при обязательном условии a_ii ¹ 0, i = 1, …, n.

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

х₁^(k) = (1/a₁₁)(b₁ – а₁₂х₂^(k-1) – … – а_1nx_n^(k-1))

х₂^(k) = (1/a₂₂)(b₂ – а₂₁х₁^(k) – а₂₃х₃^(k-1) … – а_2nx_n^(k-1))

х₃^(k) = (1/a₃₃)(b₃ – а₃₁х₁^(k) – а₃₂х₂^(k) – а₃₄х₄^(k-1) … – а_3nx_n^(k-1)) (2)

……………………………..

x_n^(k) = (1/a_nn)(b_n – а_n1х₁^(k) – … – а_n(n-1)x_n-1^(k))

Достаточные условия сходимости метода простой итерации являются достаточными и для метода Зейделя.

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

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

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

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

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

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

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

Следовательно, если матрица А – положительно-определенная, то сходимость гарантируется; если нет, то исходную систему можно привести к эквивалентной с положительно-определенной матрицей коэффициентов путем умножения слева на транспонированную матрицу А, т. е. путем перехода от системы Ах = b к системе A^tAx = A^tb или

A'x = b', (3)

где А' = А^tА; b' = A^tb.

Если исходная система имеет решение, т. е. если А – неособенная, то матрица А' – положительно-определенная и итерационный процесс по методу Зейделя сходится к решению.

Преобразование системы уравнений к виду (3) позволяет обеспечить сходимость метода Зейделя, однако при этом надо учитывать два важных для практики фактора:

1) при переходе от А к А' возрастает заполненность матрицы коэффициентов решаемой системы уравнений (вместо нулевых элементов появляются ненулевые), т. е. возрастает объем вычислений на каждом шаге итерационного процесса и требуемый объем памяти ЭВМ;

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