Изучение алгоритмов численного нахождения минимума функции нескольких переменных в Excel

Найдем минимум функции F(x,y)=sin(y)*cos(x) в области x[‑3,3], y[-3,0]. Чтобы представить себе тип исследуемой поверхности, постройте в программе MathCAD её график.

Метод покоординатного спуска.

Задание 1: Начинать можно с любой точки (x₀,y₀), принадлежащей указанной области.

1 шаг: фиксируем одну координату (присваиваем ей некоторое конкретное значение), например, координату x. Находим экстремум получившейся функции одной переменной y либо аналитически, либо любым из изученных численных методов. В результате получили некоторое промежуточное значение y_min1.

2 шаг: фиксируем другую координату y = y_min1. Находим экстремум получившейся функции одной переменной x. В результате получили некоторое промежуточное значение x_min1.

3 шаг: снова фиксируем первую координату x = x_min1. Находим экстремум получившейся функции одной переменной y любым из изученных методов. В результате получили некоторое промежуточное значение y_min2.

4 шаг: получаем значение x_min2.

И т.д.

Расчет заканчиваем в том случае, когда расстояние d от предыдущей точки (x_mini-1, y_mini-1) до точки, полученной в результате последней итерации (x_mini, y_mini), станет меньше выбранной вами точности. Результаты промежуточных вычислений оформите в виде таблицы.

Метод Хука-Дживса.

Задание 2: Исследующий поиск начинать можно с любой точки (x₀,y₀), принадлежащей указанной области. Далее нужно выбрать величину шага, которая может быть различной для разных координатных направлений. Для удобства выберите одинаковый шаг h=0,1.

1 шаг: считаем значение функции в базовой точке F₀=F(x₀,y₀). Делаем шаг вправо и считаем значение функции в найденной точке F₀₁=F(x₀+h,y₀). Если F₀₁<F₀, то мы сделали шаг в нужном направлении, в обратном случае делаем шаг влево и считаем значение функции в другой точке F₀₂=F(x₀-h,y₀). Если F₀₂<F₀, значит, мы сделали шаг в нужном направлении, в обратном случае координата x на этом шаге не изменяется.

Теперь делаем шаг вверх и считаем значение функции в найденной точке F₀₃=F(x₀,y₀+h). Если F₀₃<F₀, то мы сделали шаг в нужном направлении, в обратном случае делаем шаг влево и считаем значение функции в другой точке F₀₄=F(x₀,y₀-h). Если F₀₄<F₀, значит, мы сделали шаг в нужном направлении, в обратном случае нужно уменьшить значение шага (например, вдвое), так как мы подошли слишком близко к точке минимума.

В результате вышеописанных действий мы получили новое значение базовой точки (x₁,y₁).

2 шаг: Считаем значение функции в базовой точке F₁=F(x₁,y₁). Попытаемся выполнить поиск по образцу. Делаем такие же шаги в направлении обеих осей, которые привели к успеху на шаге 1. Получаем точку (x₂,y₂), считаем значение F₂=F(x₂,y₂). Если F₂<F₁, поиск по образцу завершился успехом, и шаг 2 можно повторить. В противном случае возвращаемся к шагу 1 с базовой точкой (x₁,y₁).

Результаты промежуточных вычислений можно оформить в виде таблицы со следующими заголовками:

Расчет заканчиваем, когда значение шага будет меньше выбранной вами точности (не более 0,01).

Метод градиентного спуска.

Задание 3: Будем двигаться к минимуму в направлении наиболее быстрого убывания функции (в антиградиентном направлении). Выберите некоторое начальное приближение (x₀,y₀) и найдите в данной точке значения градиента h_x=F/x при x = x₀ и h_y=F/y при y = y₀. Теперь нам нужно сделать шаг в антиградиентном направлении: x_i = x_i-1 - α·h_x, y_i = y_i-1 - α·h_y. Расчет заканчиваем в том случае, когда расстояние d от предыдущей точки (x_i-1, y_i-1) до точки, полученной в результате последней итерации (x_i, y_i), станет меньше выбранной вами точности. Результаты промежуточных вычислений оформите в виде таблицы: