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

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

где

Если матрица А не является симметрической и положительно определенной, как это предполагалось при выводе формул (3) и (4), то можно рассмотреть систему матрица которой симметрична и положительно определена. В этом случае вместо формул (3) и (4) мы получим:

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

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

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

то будем иметь:

Отсюда

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

Рассмотрим разность функция, определенная формулой (1) § 5. Простые вычисления дают

Для разности где точное решение системы, получим:

Таким образом,

Разложим вектор по собственным векторам матрицы А:

Тогда

и

Следовательно,

Деля каждую из скобок в знаменателе на скобку, стоящую в числителе, и обозначая

получим:

Докажем следующее неравенство: если то для любых действительных чисел имеет место неравенство

Введем вместо новые числа определяемые при помоши равенства

При

а левая часть доказываемого неравенства примет такую же форму, как и ранее:

Применим к последнему выражению теорему о том, что среднее геометрическое меньше или равно среднему арифметическому:

Функция

при убываете интервале (0,1), возрастает в интервале имеет наименьшее значение, равное 2, при и принимает наибольшее значение на отрезке равное

Заменяя в (27) каждое из выражений его наибольшим значением (29), получим:

что и требовалось доказать.

Применяя доказанное неравенство к (22), найдем:

причем Отсюда

где через с обозначено выражение Таким образом, для любого получаем:

Оценим теперь Имеем:

Легко проверить, что

Таким образом,

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

Можно усовершенствовать метод скорейшего спуска, осуществляя одновременно несколько шагов. Благодаря этому удается увеличить скорость сходимости.

Одновременное осуществление шагов по методу скорейшего спуска эквивалентно вычислению по формуле

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

или

Исследуем сходимость этого метода. Подберем постоянные так, чтобы многочлен

имел наименьшее возможное значение максимума модуля на отрезке При наш многочлен будет равен 1. Такое построение мы уже осуществили в § 8 и видели там, что просто выражается через многочлены Чебышева, наименее уклоняющиеся от нуля. При этом

Следовательно, собственные значения матрицы

которые равны -собственные значения матрицы А) также по модулю меньше единицы. Поэтому мы можем решать систему

относительно у методом простой итерации:

Так как простая итерация сходится, то система (42) имеет единственное решение. Таким решением может быть только Обозначим

В силу (43) имеем:

Таким образом,

Разложим вектор и по собственным ортонормированным векторам матрицы

Тогда

Итак,

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

Так как

Отсюда, как и ранее, получаем:

Постоянная определится в силу равенства (34) в § 9 выражением

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

ЛИТЕРАТУРА

(см. скан)

(см. скан)