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

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

.

При сходимости итер-го процесса норма погрешности убывает пропорционально невязке =>в качестве критерия остановки итераций традиционно используется условие (8)

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

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

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

6.1.  Неявные итерационные методы (Зейделя, Якоби, Последовательной верхней релаксации) - стационарные

(1) с невырожденной матрицей  

, , (2), где – матрица итерационного метода,  – начальное приближение. Последовательность ,  - итерационные приближения решения.

Итерационный процесс (2) приводит к решению (1) ó

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

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

Из 2 =>  и вектор могут быть заданы в виде: , (3)

где  – произвольная невырожденная матрица (для условия 1).

В случае плохо обусловленных матриц (число обусловленности большое, не стремится к 1) сходимость итерационных методов вида (2), (3) с оператором   может оказаться очень медленной => использование неявных итерационных методов или итерационных методов с переобусловливателем.

Неявный итерационный метод вида  (4) эквивалентен явному итерационному методу  (5), где .

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

 Второе при выборе переобусловливателя: возможности вычисления матрицы  (решения системы ) намного эффективнее, чем обращение матрицы  ().

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

       Метод Якоби. . В качестве переобусловливателя используется диагональная матрица, элементы которой совпадают с диагональными элементами матрицы . Выбор диагонального переобусловливателя практически не увеличивает вычислительную сложность отдельной итерации по сравнению с явным методом. Данный метод может оказаться полезным для разреженных матриц с диагональным преобладанием в случае, когда диагональные элементы матрицы  существенно отличаются друг от друга. Такие матрицы возникают, например, при дискретизации многомерных уравнений математической физики с сильно неоднородными коэффициентами. Если диагональные элементы матрицы  одинаковы (или почти совпадают), то метод Якоби не имеет преимуществ по сравнению с явным методом.

Метод Зейделя (Гаусса-Зейделя). Матрица  имеет треугольный вид и строится непосредственно из соответствующих элементов матрицы . В силу треугольности матрицы  данный метод имеет небольшой рост вычислительных затрат на одну итерацию и примерно вдвое (иногда более) сокращает число итераций для достижения заданной точности по сравнению с явным методом. Данный метод практически всегда имеет положительный эффект по сравнению с явным методом и Якоби.

Метод последовательной верхней релаксации. В некотором роде является обобщением метода Зейделя и метода Якоби. Переобусловливатель строится из верхней треугольной части матрицы   без главной диагонали:   и диагональных элементов матрицы: : , ,

(  нижняя релаксация, A=A^*>0, =>  метод релаксации сходится)

При  метод последовательной верхней релаксации совпадает с методом Зейделя, при  – метод совпадает с методом Якоби. Оптимальное значение параметра  обычно лежит в интервале . В большинстве случаев метод последовательной верхней релаксации превосходит по эффективности методы Якоби и Зейделя. Метод популярен для многомерных задач математической физики. -т модификации данного метода, основанные на чередовании верхней и нижней треугольных матриц в .

Для реализации этих трех методов не нужно знания спектра задачи.