Нахождение безусловного экстремума функции нескольких переменных градиентными методами (стр. 2 )

(Пример выполнения задания).

Пусть задана функция ; Начальные значения

Метод с постоянным шагом. (a1=1).

1.   Вычисляем градиент функции

2.   Производим вычисления по формуле (7).

Результаты сводим в таблицу 1.1.

Итера-ция
1	2	2	4	100	100	-0,04	-1,00
2	1,96	1	3,92	50	50,1	-0,078	-1,00
3	1,88	0	3,76	0	3,76	-1	0
4	0,88	0	1,76	0	1,76	-1	0
5	-0,12	0	-0,24	0	0,24	+1	0

и т. д.

Метод с дроблением шага.

Вычисления производим по формуле (7). Величину шага определяем с учетом неравенства (8).

Результаты сводим в таблицу 1.2.

N итерации	N
4	1	0,88	0	1,76	0	1,76	0,77	-2,56	1	-1	0
5	1	-0,24	0	-,024	0	0,24	0,014	-0,75	1	1	0
6	1	0,88	0	1,76	0	1,76	0,77	0,75	0,5	0,5	0
	2	0,38	0	0,76	0	0,76	0,144	0,13	0,25	0,25	0
	3	0,13	0	0,26	0	0,26	0,017	0,003	0,125	0,125	0

На 6 - ой итерации значение функции возросло, неравенство (8) не выполняется 0,75 > 0,5 1 1,76 = 0,88

поэтому необходимо выполнить дробление шага. Процедура дробления шага будет продолжена пока не выполнится условие (8). При этом получено следующее значение:

Пример выполнения работы на MATHCADе

Требования к оформлению отчета.

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

  Название работы.

  Цель работы.

  Задание на работу.

  Листинг программы (исходный текст).

  Результаты работы, представленные в виде таблиц 1.1 и 1.2.

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

Вопросы для самопроверки.

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

2.  В чем заключается условие стационарности функции нескольких переменных?

3.  Какая последовательность векторов X называется релаксационной?

4.  Обладают ли методы с дроблением шага какими - либо преимуществами по сравнению с методом с постоянным шагом?

5.  Чем определяется правило окончания, итеративной процедуры поиска безусловного экстремума?

работа №2.

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

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

Работа выполняется с использованием алгоритмических языков высокого уровня.

Метод наискорейшего спуска - это процесс, на каждой итерации которого шаг выбирается из условия минимума функции в направлении движения:

При этом на каждой итерации необходимо решать задачу одномерной оптимизации (одномерного поиска экстремума).

Существуют различные методы одномерного поиска. Одним из наиболее эффективных методов является метод золотого сечения. Метод работает при условии, что заданная функция унимодальная на интервале, в котором имеется экстремум.

Алгоритм метода золотого сечения [3].

1.  Ищется начальный отрезок , в котором находится экстремум:

от точки делается последовательная серия возрастающих шагов в направлении поиска.

При этом запоминаются 3 последние точки.

Процесс выполняется до тех пор, пока не будет больше, чем

Тогда искомый интервал равен

2.   Уточняется область нахождения экстремума: k:=0;

2.1. Находятся точки

2.2. Вычисляется значение функции

2.3. Переопределяется интервал и точки X1, X3:

если

если

если

то выбирается любой из рассмотренных выше вариантов

Процедура одномерного поиска продолжается до тех пор, пока не будет достигнута заданная точность, т. е. пока Dk не будет меньше D доп.

После определения величины a (в формуле 1) методом одномерного поиска, находится новое значение многомерной точки Xk+1, в которой вновь выделяется градиент функции

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

При небольшой размерности пространства En может быть найдено аналитическое выражение для оптимального значения a. Для этого формула (1) записывается в явном виде как функция от a:

Затем берется производная от по a и приравнивается нулю. В результате решения полученного уравнения находится оптимальное значение a.

Если минимизируемая функция квадратичная, то оптимальное значение a на k - ой итерации может быть определено из векторного равенства [2]

(2)

где X1 - вектор - строка X;

- нормированный антиградиент;

- норма вектора;

H - матрица вторых производных (матрица Гессе).

Рассмотренные выше методы предполагают вычисление градиента минимизируемой функции в аналитическом виде. Если целевая (минимизируемая) функция слишком сложна, чтобы ее дифференцировать аналитически, то составляющие градиента, являющиеся частными производными по оптимизируемым переменным, аппроксимируются разностными соотношениями:

(3)

где di - малые отклонения.

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

Задание на работу №2.

Для функции, заданной в лабораторной работе №1, отыскать безусловный экстремум методом наискорейшего спуска тремя способами:

а) используя аналитическое выражение для определения шага a;

б) применяя векторное уравнение (2) для той же цели;

Повторить расчеты по пункту в), применяя численные методы вычисления градиента (формула (3)). Результаты вычислений по каждому из способов свести в таблицу:

Таблица 2.1.

N итерации						a

При вычислении использовать следующие значения:

Методика выполнения работы.

(Пример выполнения задания).

Пусть задана функция двух переменных и вектор

Находим градиент функции:

1.   Находим экстремум, определяя величину a аналитически

Записываем выражение для

Находим :

Решаем уравнение Получаем

На первой итерации имеем:

Вычисляем a1:

Находим новую точку X1:

На второй итерации получаем:

2.   Находим экстремум , используя векторное уравнение (2).

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