Составить алгоритм поиска экстремума функции двух переменных

F (x₁, x₂) = x₁⁴ +x₁² + x₁x₂ – 2 x₂²

методом «тяжелого шарика

Метод тяжелого шарика.

Градиентный метод решения задачи безусловной минимизации

f (x) → min,

(1)

где f: R ^m → R, можно интерпретировать в терминах обыкновенных дифференциальных уравнений следующим образом. Рассмотрим дифференциальное уравнение

px ·+ f ′(x) = 0

(2)

(здесь точка над x обозначает производную по независимой переменной t, а f ′(x) как обычно обозначает градиент отображения f: R ^m → R; предполагается, что p > 0). Простейший разностный аналог уравнения (2), а именно, явная схема Эйлера

p xn +1 – xn h + f ′(xn) = 0

и есть градиентный метод для задачи (1):

xn +1 = xn – h p f ′(xn).

(3)

Рассмотрим теперь вместо уравнения (2) уравнение

mx ··+ px ·+ f ′(x) = 0,

описывающее движение шарика массы m в потенциальном поле f ′ при наличии силы трения. Потери энергии на трение вынудят шарик спуститься в точку минимума потенциала f, а силы инерции не дадут ему осциллировать так, как это изображено на рис. 8. Это позволяет надеяться, что изменение уравнения (2) введением в него инерционного члена mx ··улучшит сходимость градиентного метода (3). Конечно-разностный аналог уравнения, описыавющего движение шарика — это, например, уравнение

m xn +1 – 2 xn + xn –1 h 2 + p xn – xn –1 h + f ′(xn) = 0.

После простых преобразований и очевидных обозначений мы получаем

xn +1 = xn – α f ′(xn) + β(xn – xn –1).

(4)

Итерационная формула (4) задает метод тяжелого шарика решения задачи безусловной оптимизации (см. рис. 14; ср. с рис. 8).

Рис. 14.

Можно доказать, что в условиях теоремы 3.7 метод тяжелого шарика при α = 2/(√Λ + √λ)² и β = (√Λ – √λ)/(√Λ +√λ)² сходится со скоростью геометрической прогрессии со знаменателем q = (√Λ –√λ)/(√Λ + √λ).

Если теперь сравнить знаменатели q _гм = (Λ – λ)/(Λ + λ) и q _мтш = (√Λ – √λ)/(√Λ + √λ), характеризующие скорости сходимости градиентного метода и метода тяжелого шарика, соответственно, то для плохо обусловленных функций, т. е. для функций с μ = Λ /λ >> 1, очевидно, q _гм ≈ 1– 2/μ, а q _мтш ≈ 1 – 2/√μ. Поэтому для уменьшения погрешности в e ≈ 2.718 раз градиентный метод с постоянным оптимальным шагом требует –[ln(1 – 2/μ)]^–1 ≈ μ)/2 итераций, а метод тяжелого шарика –ln(1 – 2/√μ)]^–1 ≈ √μ/2. Для больших μ это весьма значительный выигрыш, поскольку объем вычислений в методе тяжелого шарика почти не отличается от объема вычислений в градиентном методе.