32. Метод Бройдена

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

.

Это симметрическая матрица с пропорциональными строками, поэтому она имеет единичный ранг . Сформируем поправку ранга один в виде , где – некоторый вещественный коэффициент. По формуле (4.6)

. (4.9)

Система линейных алгебраических уравнений (4.5) принимает вид

.

Раскрывая скобки, имеем

,

То есть

,

Где скобки содержат скалярную величину. Это векторное равенство удовлетворяется, если положить и при условии . Тогда равенство (4.9) примет вид

. (4.10)

Эта формула коррекции аппроксимации обратной матрицы Гессе представлена в 1967 году английским математиком Ч. Д. Бройденом и называется Формулой Бройдена, а использующий ее квазиньютоновский метод называется Методом Бройдена. Таким образом, метод Бройдена основан на формулах (4.3), (4.7), (4.8) и (4.10). Первая итерация начинается из заданной начальной точки , и в направлении антиградиента выполняется одномерный поиск:

, , , . (4.11)

Последующие итерации для выполняются по формулам:

, , (4.12)

, , (4.13)

, , . (4.14)

Итерации продолжаются до тех пор, пока выполняется условие

,

Где – допустимая погрешность. По формулам (4.11)–(4.14) составим алгоритм метода Бройдена.

Алгоритм метода Бройдена.

Входные параметры: – начальная точка поиска, – процедура вычисления функции, – допустимая погрешность.

Выходной параметр – конечная точка поиска.

1. Вычислить и положить , .

2. Вычислить , .

3. Положить , .

4. Вычислить , , .

5. Положить .

6. Вычислить .

7. Если , то перейти к шагу 2.

8. Остановиться.

Пример 4.1. На рис. 4.1 представлена траектория минимизации квадратичной функции (1.3) методом Бройдена. Для вычисления точки минимума с допустимой погрешностью 10–3 метод затратил 3 итерации и 19 вычислений функции. За две итерации получено приближение точки минимума с погрешностью 9,7∙10–8. При этом траектория минимизации квадратичной функции методом Бройдена такая же, как и траектория минимизации этой же функции методом Флетчера – Ривса из примера 3.3, представленная на рис. 3.5.

Рис. 4.1. Минимизация квадратичной функции методом Бройдена

Пример 4.2. На рис. 4.2 представлена траектория минимизации функции Розенброка методом Бройдена. Вычисление точки минимума с допустимой погрешностью 10–3 потребовало 17 итераций и 269 вычислений функции, что сравнимо с результатами метода Полака – Рибьера из примера 3.7. Траектория поиска такая же, как и на рис. 3.8 для метода Полака – Рибьера.

< Предыдущая		Следующая >