3 семестр / Задание №3 Поиск минимума функции двух переменных

Задание №3

ПОИСК МИНИМУМА ФУНКЦИИ ДВУХ ПЕРЕМЕННЫХ

Цель работы: изучение методов поиска минимума функций нескольких переменных.

ПОСТАНОВКА ЗАДАЧИ

Для поиска минимума функций нескольких переменных часто используются методы спуска. Простейшим из этих методов является координатный спуск, который строится следующим образом. Пусть x⁽⁰⁾ — начальное приближение к моде , которое должно быть задано. Зафиксируем координаты x⁽⁰⁾₂, x⁽⁰⁾₃, ..., x⁽⁰⁾_n и найдем значение x⁽¹⁾₁ как решение задачи

каким-либо методом поиска минимума функции одной переменной, например, методом «золотого сечения».

Геометрически это означает, что минимум отыскивается вдоль прямой, проходящей через точку x⁽⁰⁾ параллельно оси x₁, причем x⁽¹⁾₁ — координата точки, в которой эта прямая касается некоторой поверхности уровня (Рис. 1).

Рис.1 Выполнение итераций и траектория в методе координатного спуска

Далее, аналогично находим x⁽¹⁾₂, x⁽¹⁾₃, ..., x⁽¹⁾_n как решения задач одномерной минимизации.

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

Доказано, что в котловине метод координатного спуска сходится к минимуму со скоростью геометрической прогрессии, имеющей знаменатель q < 1:

(сходимость первого порядка). Однако, во многих случаях (например, если рельеф близок к разрешимому оврагу) знаменатель прогрессии может быть близок к 1:

q  1,

и сходимость оказывается очень медленной.

ВАРИАНТЫ ЗАДАНИЙ

Методом координатного спуска найти минимум функции двух переменных

a, b = 1÷0.001; m, n = 2,4,6; β = 0÷1.

Точные значения: x_min = y_min = 0; f(x_min, y_min) = 0.

В качестве начальной точки (0-й итерации) принять

x⁽⁰⁾=y⁽⁰⁾=d ,

где

_,

а в качестве интервала поиска минимумов по х и по y — интервал [ -d, d ].

Условия окончания итераций:

1)

( k = 1. 2. 3 ... - номер итерации);

2) k> k_max= 10000.

ПРОГРАММИРОВАНИЕ

Блок-схема программы поиска минимума функции двух переменных методом координатного спуска приведена на Рис.2. Метод реализован в цикле 4-10, блок 7 представляет собой подпрограмму вычисления минимума функции одной переменной, такую как, например, в предыдущем задании.

СОДЕРЖАНИЕ ОТЧЕТА

Отчет должен содержать:

• исходные данные a, b, β, m, n, ε;

• текст программы;

• график функции f(x,y);

• результаты решения: k, x^(k), y^(k), а также зависимость от k величины

q^(k)=-ln(δ^(k))/ln10.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие методы поиска минимума функций нескольких переменных вы знаете?

2. Как можно ускорить сходимость итераций в методе координатного спуска?

3. В чём суть метода наискорейшего спуска?

4. В чём идея метода сопряженных направлений?

5. Какие методы поиска минимума функций нескольких переменных можно использовать, если функция имеет овражный рельеф?

5