Циклический метод Ричардсона: формулы и сходимость

Теорема.

Если и известны оценки ее спектра: , то циклический метод Ричардсона (с длиной цикла ) решения системы : с чебышевскими параметрами сходится и .

Об устойчивости метода Ричардсона

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

Рассмотрим модельный пример, в котором ошибка округления возникает только на шаге с ( ):

Проверить: .

Проверить: , , если , т.е. фактически ошибка не уменьшилась.

Изменим упорядочение параметров: :

Проверить: ,

т.е. реализация с точностью до ошибок округления.

Из этого примера следует, что переупорядочение параметров существенно влияет на устойчивость вычислений в методе Ричардсона. Задача об оптимальном упорядочении параметров ставится следующим образом.

Пусть	– перестановка –ки , , .
Найти	: .

Решением этой задачи для является следующая процедура:

Трехчленные формулы реализации метода Ричардсона с чебышевскими параметрами

Для решения системы попытаемся построить приближения :

.

Т.к. и (проверить!), то

.

Если ввести обозначение , то

построена:

Преобразуем эту формулу:

.

Введем обозначение , т.к. , то

Тогда

– двухшаговый (трехслойный) итерационный процесс.

Лекция 10. Многошаговые методы. Вариационная оптимизация

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

.

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

Т.к.

где ,

то

.

Параметры удовлетворяют системе уравнений

,

или

.

Матрица этой системы – матрица Грамма базиса в .

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

Если базис является –ортогональным, т.е. , то

,

а вычисление осуществляется аналогично.

Метод сопряженных градиентов

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

1. – базис в	, .
	Заметим, что
Предположим, что выполнили шагов: и . Определим : , т.е. , т.к. . Заметим, что и
–шаг. – базис в	.
	, т.к. . Т.к. и , то предположения мат. индукции выполнены, мы построили метод сопряженных градиентов.

Теорема.

Если , то метод сопряженных градиентов продолжается до получения решения системы за итераций (пока ) и

.

Доказать теорему в качестве упражнения.