АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Анализ реализации функций системы самоменеджмента на предприятии (на примере ООО «ХХХ»)
  2. Введение барьерных штрафных функций.
  3. Введение штрафных функций Фиакко - Мак-Кормика.
  4. Возводим матрицу А в квадрат, используя мастер функций действие «МУМНОЖ».
  5. Выявление важных экономических функций
  6. Графики основных элементарных функций
  7. Делегирование функций
  8. Дифференцирование функций, заданных параметрически
  9. Значений функций. Задача линеаризации функции
  10. И изменениями функций управления персоналом
  11. Изменение эндокринных функций при выполнении физической работы.
  12. Интегрирование иррациональных функций.

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

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

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

F = (x 12 + x 2 - 11)2 + (x 1 + x 22 - 7)2]);

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

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

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

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

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

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

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

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

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

2) Grad;

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

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

5) выход.

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

X1 X2 Alpha F(x1,x2) Grad F F1 F2
      105,5014 61,043; 27,426 -0,137 -0,061
3,863 2,939   95,7047 58,150; 26,086 -0,133 -0,060
3,597 2,819   78,0116 52,523; 23,476 -0,125 -0,055
3,222 2,654   56,2257 44,620; 19,820 -0,114 -0,051
2,766 2,450   34,4881 34,985; 15,354 -0,101 -0,044
2,261 2,230   16,6662 24,360; 10,443 -0,088 -0,037
1,733 2,008   4,9695 13,307; 5,353 -0,074 -0,030
1,215 1,798   0,2662 2,52; 0,404 -0,064 -0,010
0,703 1,718   1,6029      

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Диалоговое меню программы имеет вид, как и у lor4.exe. Начертить в тетради исходную таблицу. Для начальной точки взять такие же координаты, как и в программе lor4.exe. Найти координаты точки минимума. При вычислении функции F убедиться, что налицо сбойный результат (при x 1= 4, x 2 = 3 значение F = 34684,888). При выполнении работы сбой постепенно ликвидируется, но результат будет достигнут за большее количество шагов (для уменьшения количества итераций целесообразно использовать рекомендации по изменению α из предыдущего пункта). Построить график зависимости F=F(α).

6. Открыть программу lor6.exe. - ”Программа минимизации функции многих переменных без сбойных результатов. Адаптация”.

Диалоговое меню программы имеет вид, как и у lor4.exe. Начертить в тетради исходную таблицу и найти координаты точки минимума (начальные данные такие же, как и в предыдущей программе). Сравнить результаты 5-й и 6-й программ. Построить график зависимости F=F(α).

Отметим, что использованные в программе алгоритмы минимизации многомерных функций являются стандартными и применяются во всех известных математических пакетах, разработанных в Windows (Excel, MathCad, MathLab, Mathematica).

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


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

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

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

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

 

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

 

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

 

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

 

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

где

.

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

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

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

, (1)

где In - единичная матрица размером (n ´ n), ÄAj=A1ÄA2Ä…An – кронекеровское произведение, ÄAi=A1ÄA2Ä…An – прямая сумма.

 

,

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

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

(2)

где ; .

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

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

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

Таблица 1

 

Номер Двоичное представление Двоичная инверсия (считывание в обратном порядке) Двоично-инверсный номер
  0 0 0 0  
  0 1 1 0  
  1 0 0 1  
  1 1 1 1  

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)