Метод минимальных поправок. Итерационные методы решения СЛАУ вариационного типа

Итерационные методы решения СЛАУ вариационного типа

Метод минимальных невязок

Рассмотрим систему

, (7.1)

с невырожденной симметричной положительно определенной матрицей и одношаговый итерационный метод, записанный в канонической форме

, (7.2)

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

Обозначим через

(7.3)

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

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

(7.4)

и перепишем его в виде

. (7.5)

Методом минимальных невязок называется итерационный метод (7.4), в котором параметр выбирается из условия минимума при заданной норме .

Получим явное выражение для итерационного параметра . Из (7.5) получаем

,

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

. (7.6)

Возводя обе части уравнения (7.6) скалярно в квадрат, получим

. (7.7)

Отсюда видно, что достигает минимума, если

. (7.8)

Таким образом, в методе минимальных невязок переход от -й итерации к -й осуществляется следующим образом. По найденному значению вычисляется вектор невязки и по формуле (7.8) находится параметр . Затем по формуле (7.5) досчитывается вектор .

Метод минимальных невязок (7.5), (7.8) сходится с той же скоростью, что и метод простой итерации с оптимальным параметром .

Теорема 1. Пусть симметричная положительно определенная матрица. Для погрешности метода минимальных невязок выполняется оценка

, (7.9)

где

, . (7.10)

Без доказательства.

Метод минимальных поправок.

Запишем неявный итерационный метод (7.2) в виде

, (7.11)

где невязка. Вектор

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

. (7.12)

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

Найдем выражение для итерационного параметра . Перепишем (7.12) в виде

и вычислим с учетом того, что (доказать):

,

Отсюда следует, что будет минимальной, если положить

. (7.13)

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

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

. (7.14)

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

, , (7.15)

где

, .

Без доказательства.

Метод скорейшего спуска.

Явным методом скорейшего спуска называется метод (7.4), где итерационный параметр выбирается из условия минимума при заданном векторе . Поскольку погрешность удовлетворяет уравнению

,

имеем, с учетом того что (доказать самостоятельно):

.

Следовательно, будет минимальной, если положить

.

Так как величина неизвестна (поскольку неизвестно решение ), надо учесть, что , и вычисление проводить по формуле

. (7.16)

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

, , (7.17)

где

, .

Неявным методом скорейшего спуска называется метод (7.2), в котором параметр выбирается из условия минимума . Так как погрешность удовлетворяет уравнению (доказать)

,

получим

,

или, учитывая, что , получим

.

Следовательно, будет минимальной, если положить

. (7.18)

Для неявного метода скорейшего спуска справедлива оценка (7.17), где

, .