Минимизация многомерных функций

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

2. Открыть программу lor2a.exe –” Минимизация функции многих переменных (демонстрационная программа)”. Диалоговое меню программы имеет следующие пункты:

1) просмотр функции в целом [для всех вариантов она имеет вид

F = (x ₁² + x ₂ - 11)² + (x ₁ + x ₂² - 7)²]);

2) просмотр функции по квадрантам;

3) метод золотого сечения;

4) метод квадратичной аппроксимации;

5) задание/снятие ограничений.

Просмотреть график функции (с линиями уровня) целиком и по квадрантам. Записать координаты начальной точки в тетрадь (в частности, для 1 варианта это x ₁ = -3,4 и х ₂ = -3,7),которую можно просмотреть ближе, записав указанный квадрант. Уточнить координаты точки двумя методами: золотого сечения и квадратичной аппроксимации. Координаты минимума, полученные этими методами (без задания ограничений), равны: х ₁ = -3,779, х ₂ = -3,283. Можно просмотреть направление движения точки по графику, выбрав соответствующий пункт меню. В тетрадь записать координаты точки минимума, количество итераций, за которое достигнуто решение, и оптимальное значение Alpha.

Далее накладывается ограничение на направление поиска минимума (для всех вариантов оно различно, в частности, для первого варианта имеет вид: - 2 х ₁ - 3 х ₂ + 5 = 0). Начальные значения координат точки минимума х ₁ = -4, х ₂ = 4,3. Зарисовать в тетради направление движения точки по графику. Вдоль данного направления координаты точки минимума имеют значения: х ₁= -2,557, х ₂ = 3,371 (метод золотого сечения дает этот результат после 2-й итерации при α = 0,002, метод квадратичной аппроксимации после 3-й итерации при α = 0,82).

3.Открыть программу lor4.exe. – ”Минимизация многомерной функции. Реализация градиентного метода”.

Диалоговое меню:

1) вычисление F(x1, x2);

2) Grad;

3) нормирование градиента;

4) формирование вектора положения;

5) выход.

Все данные заносить в таблицу, вид которой предложен в самой программе. Значения F1 и F2 получаются из значений нормированного градиента, взятых с противоположным знаком. Для взятой произвольно начальной точки х ₁ = 4, х ₂ = 3 градиентный метод дает следующие результаты.

Видно, что минимум функции равен 0,22662 в точке (1,215; 1,798) при alpha равном 7. Результат достигнут на седьмой итерации, но если процесс поиска минимума затянулся, то через 5 шагов alpha можно увеличивать вдвое. Построить график зависимости F=F(α).

4. Открыть программу lor.exe. – ”Программа минимизации функции многих переменных”.

Система меню ориентирована на реализацию всех этапов минимизации многомерной функции методом ДФП, который может использоваться для численной реализации других методов: координатного спуска в методе Гаусса-Зейделя, наискорейшего спуска и других градиентных методов.

1. Вычисление функции F(X₁, X₂) (в лабораторной работе только для простоты выполнения и наглядности визуализации исходных данных и результатов оптимизации число переменных n в целевой функции берут равным двум).

2. Вычисление GRAD(X₁, X₂) [реализация выражения (7)].

3. Нормирование градиента (осуществляется лишь в начальной точке поиска минимума, при дальнейших операциях эта итерация может опускаться).

4. Вычисление вектора направления [реализация выражения (3)].

5. Формирование вектора положения [реализация выражения (4)].

6. Сокращение интервала неопределенности методом золотого сечения [реализация выражения (8)]. При выполнении данной операции, если не соблюдается условие , принять и так до тех пор, пока не произойдет убывание функции.

7. Золотое деление отрезка (деление отрезка на две неравные части X и Y (X>Y)), при котором , где .

8. Вычисление вектора направления на второй и последующих итерациях [реализация последовательно выражений (6), (3)].

9. Поиск интервала неопределенности методом квадратичной аппроксимации [реализация выражения (10)]. Рекомендации по выбору α те же, что и в меню под номером 6.

10. Определение координаты минимума в методе квадратичной аппроксимации [реализация выражения (11)].

11. Построение графика функции (Х ₂ – ордината, Х ₁ - абсцисса).

12. Завершение работы.

Записать координаты начальной точки в тетрадь и начертить таблицу, как в программе lor4.exe.Проделать 2 итерации по поиску минимума функции (первые пять пунктов, т.е., alfa при этом равны 0 и 1 соответственно). Для дальнейшего определения значения alfa перейти к п. 6. Найти alfa по предлагаемой формуле и высчитывать далее по первым пяти пунктам вектор положения с учетом нового значения alfa. После нахождения точки минимума методом золотого сечения перейти ко второму методу. Для этого начертить еще одну такую же таблицу, переписать туда результаты первых двух итераций и перейти к п. 9 для определения значения alfa, далее продолжить работу по пяти пунктам и по п. 9.

5. Открыть программу lor5.exe – ”Программа минимизации функции многих переменных (со сбойными результатами)”.

Содержание отчета

1. Краткое описание алгоритма минимизации функции многих переменных.

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

3. Кратко изложить реализацию методов: координатного спуска в методе Гаусса-Зейделя, наискорейшего спуска.

Лабораторная работа № 4

МЕТОДЫ АППРОКСИМАЦИИ ФУНКЦИЙ

4.1. Быстрое преобразование Фурье

Матрица дискретного преобразования Фурье имеет вид:

где

.

Коэффициенты разложения сигнала имеют вид: .

Применяя обратное преобразование Фурье, получаем аппроксимированное представление сигнала где B_(m,l)=W^-lm.

Для сокращения числа операций целесообразно применять БПФ, представленный в матричной форме. Матрица преобразований имеет вид

, (1)

где I_n - единичная матрица размером (n ´ n), ÄA_j=A₁ÄA₂Ä…A_n – кронекеровское произведение, ÄA_i=A₁ÄA₂Ä…A_n – прямая сумма.

,

где , N = 2ⁿ – число отсчетов.

На основе формулы (1) для n = 4 получаем спектр:

(2)

где ; .

i = 2,4,6,8 j = 1,3,5,7

Результаты представлены FKP с двоично-инверсными номерами.

Пример представления спектра с двоично-инверсными номерами дан в таблице 1.

Таблица 1

Поиск по сайту: