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

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

В большинстве случаев при решении систем ЛАУ большой размерности приходится иметь дело с так называемыми разреженными матрицами, количество ненулевых элементов которых возрастает пропорционально при общем числе элементов . Нулевые элементы матрицы не несут полезной информации и могут быть проигнорированы в матричных вычислениях. В рамках прямых методов игнорирование нулевых элементов матрицы весьма нетривиальная задача. Основная проблема здесь в том, что в процессе матричных преобразований общее число ненулевых элементов не сохраняется – возрастает. Например, суммарное число ненулевых элементов матриц при разложении или при факторизации Холецкого может многократно превосходить число ненулевых элементов исходной матрицы. Предварительное упорядочение элементов матрицы при использовании алгоритмов факторизации позволяет в ряде случаев снизить остроту проблемы, однако полностью устранить рост числа ненулевых элементов в общем случае, по-видимому, не представляется возможным.

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

Общая схема большинства итерационных методов решения систем ЛАУ

(3.1)

с невырожденной матрицей и заданным вектором правой части имеет вид

, , (3.2)

где – матрица итерационного метода или матрицей перехода от k-ой итерации к (k+1)-ой, – произвольный вектор, называемый начальным приближением итерационного процесса. Последовательность , будем называть итерационными приближениями искомого решения.

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

Для того, чтобы итерационный процесс (3.2) действительно приводил к решению поставленной задачи (3.1) необходимо и достаточно выполнение двух вполне очевидных условий:

1. последовательность векторов , , сходится.

2. предел данной последовательности является решением (3.1).

Из условия 2 следует, что матрица и вектор могут быть заданы в виде:

, , (3.3)

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

.

Теорема 3.1. Пусть , – решение (3.1). Тогда итерационный процесс (3.2), (3.3) сходится со скоростью геометрической прогрессии к вектору и для погрешности итерационного метода выполняется оценка

. (3.4)

. Доказательство: Вычитая из (3.2) равенство для погрешности метода имеем:

.

Поскольку , то . Теорема доказана.

Разнообразие итерационных методов связано с выбором конкретного вида матрицы , которую принято называть переобусловливателем (preconditioner). Если матрица одинакова для всех итераций, то такой итерационный процесс называется стационарным. Среди нестационарных итерационных методов традиционно используются переобусловливатели вида , где итерационный параметр для каждой итерации выбирается из расчета наибольшей скорости сходимости. С точки зрения алгоритмической реализации итерационный процесс (3.2), (3.3) удобно представить в виде

. (3.5)

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

. (3.5')

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

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

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