Вычислительная сложность итерационных методов. Число итераций.

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

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

.

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

, (3.6)

где – некоторая малая величина, определяющая желаемую погрешность искомого приближенного решения. Количество итераций для достижения заданной точности можно оценить, зная норму матрицы итерационного процесса. Если положить, что при нулевом начальном приближении относительная погрешность равна 100%, тогда, например, для достижения точности с учетом оценки (3.4) потребуется число итераций такое, что

. (3.7)

Норма матрицы итерационного процесса характеризует скорость его сходимости. Максимальная скорость сходимости достигается при минимальном значении . Оценка (3.7) показывает, что минимальное число итераций для достижения заданной точности может неограниченно возрастать при .

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

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

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

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