Методические указания к лабораторным работам




Скачать 262.88 Kb.
НазваниеМетодические указания к лабораторным работам
страница1/3
Дата15.01.2013
Размер262.88 Kb.
ТипМетодические указания
  1   2   3


Министерство образования и науки

российской федерации

федеральное агентство по образованию

Федеральное государственное образовательное учреждение

высшего профессионального образования

«Чувашский государственный университет имени И. Н. Ульянова»


Методы оптимизации


Методические указания к лабораторным работам


Чебоксары 2006

УДК 519.852

Составители: П.В. Желтов,

В.П. Желтов,

С.С. Покалев,

А.П. Димитриев




Методы оптимизации: Метод. указания к лабораторным работам / Сост. П.В. Желтов и др.; Чуваш. ун-т. Чебоксары, 2006. 24 с.


Составлены в соответствии с государственным образовательным стандартом высшего профессионального образованиия направления подготовки дипломированного специалиста 230100 - Информатика и вычислительная техника специальности 230102 -Автоматизированные системы обработки информации и управления, утвержденным 27.03.2000 (регистрационнный номер 224 тех/дс) и веденным с 1 сентября 2000.

Содержат алгоритмы некоторых методов оптимизации и задания к лабораторным работам.

Для студентов III курса специальности 230102 – «Автоматизированные системы обработки информации и управления»


Утверждено Методическим советом университета

Отв. редактор: канд. физ.-мат. наук доцент Л.В. Желтова


5-7677-0528-3

Лабораторная работа 1

Одномерная оптимизация


А. Алгоритмы одномерной оптимизации.

1. Выбрать начальную точку x0, положить k = 0.

2. На k-й итерации определить точку f (xk) и f (xk), вычислить

.

3. Тест на остановку: если выполнено, то конец. Иначе: положить k k + 1 и вернуться к 2.

Б. Метод секущих.

1. Выбрать начальную точку x0, положить k = 0.

2. На k-й итерации определить точку f (xk).

Вычислить

.

3. Тест на остановку: если выполнено, то конец. Иначе: положить k k + 1 и вернуться к 2.

В. Метод Фибоначчи.

1. Задать число итераций N, интервал [A,B] и точность E, F(0):=0; F(1)=1.

Вычислить числа Фибоначчи:

F( I ) =F(I – 1) + F(I – 2) I = 2, N;

x1:= A; x2 = A + (BA)F(N – 1) + E(– 1)N / F(N); x3 := B;

F2 = f(x2); k:=1; выбрать начальную точку x0, положить k = 0.

2. x4 = x1x2 + x3; F4 = f(x4).

Если F4 < F2, то если x2 < x4 то x1:= x4, перейти к 3.

Иначе: если x2 < x4, то x1:= x2; x2 := x4; F2 := F4, перейти к 3.

Иначе: x3:= x2; x2 := x4; F2 := F4 перейти к 3.

3. Тест на остановку: положить k := k + 1, если kN, то перейти к 2. Иначе: конец.

Г. Метод золотого сечения.

1. Выбрать интервал [A, B].

T1 := 0.38196600113; T2 := 1 – T1; x0 := A; x1 := A + T1(BA);

x2 := A + T2(BA); x3 := B; F1 := f(x1); F2 := f(x2).

2. Если F2 < F1, то выполнить

I := x3x1; x0 := x1; x1 := x2; x2 := x0 + T2I; F1 := F2; F2 := f(x2).

Идти к 3.

I := x2x0; x3 := x2; x2 := x1; F2 := F1; x1 := x0 + T1I; F1 := f(x1).

Идти к 3.

3. Тест на остановку: если выполнено, то конец. Иначе: положить k := k + 1 и вернуться к 2.

Д. Квадратичная интерполяция.

1. Выбрать первые три точки x1, x2, x3 и вычислить значение функции в этих точках F1, F2, F3. Выполнить квадратичную интерполяцию.

2. Вычислить точку минимума:

DN := (x2 ­– x3)F1;

DN := DN + (x3 ­– x1)F2 + (x1 ­– x2)F3;

NM := (x2x2x3x3)F1;

NM := NM + (x3x3x1x1)F2;

NM := NM + (x1x1x2x2)F3;

x4 = NM / (2 DN).

Вычислить значение функции F4 = f (x4).

Упорядочить точки и заменить три лучшие точки. Найти новый интервал.

3. Тест на остановку: если выполнено, то конец. Иначе: положить k := k + 1 и вернуться к 2.

Е. Метод дихотомии.

1. Выбрать интервал [a0, b0].

Вычислить с0 = (a0 + b0) / 2; d0 = (a0 + c0) / 2; e0 = (c0 + b0) / 2.

2. Исключить два из четырех подинтервалов, поскольку точка оптимума не может содержаться в них, и оставить только два смежных подинтервала [aK, cK] и [cK, bK] (отрезок [aK, bK] половинной длины).

Вычислить dK = (aK + cK) / 2 и eK = (cK + bK) / 2 и значение функции в двух этих точках.

3. Тест на остановку: если выполнено, то конец. Иначе: положить k := k + 1 и вернуться к 2.


Ё. Метод дихотомии с производными.

1. Определить начальный интервал [min, max], для которого g'(min) < 0, g'(max) > 0; k := 1.

2. На k-й итерации: вычислить ; вычислить g'(k). Если g'(k)>0, то max := k и перейти к 3. Иначе: min := k и перейти к 3.

3. Тест на остановку: если выполнено, то конец. Иначе: положить k := k + 1 и вернуться к 2.

Ж. Кубическая интерполяция.

1. Выбрать начальный интервал [a, b], содержащий точку минимума, при этом должно быть выполнено f '(x) < 0, f '(b) < 0.

2. Вычислить

.

Вычислить точку минимума .

3. Тест на остановку: если выполнено, то конец. Иначе: положить a = x, если f '(x) < 0, и b = x, если f '(x) > 0. Вернуться к 2.

З. Метод Голдстейна.

1. Определить min = 0, max = +. Найти g'(0) = f T(x)d и присвоить переменной  начальное значение (первую тестированную точку).

2. Вычислить g() = f(x + d). Если g()  g(0) + m1g'(0), то перейти к 3. Иначе: положить max =  и перейти к 3.

3. Вычислить g'() = f T(x + d)d, затем сравнить g'() и f(0) + m2g'(0). Если g'() ≥ g(0) + m2g'(0), то конец. Иначе: перейти к 4.

4. Положить min = .

5. Найти новое значение для  в интервале [min, max] и вернуться к 2.

И. Метод Вольфе–Пауэлла.

1. Определить min = 0, max = +. Найти g'(0) = f T(x)d и присвоить переменной  начальное значение (первую тестированную точку).

2. Вычислить g() = f(x + d). Если g()  g(0) + m1g'(0), то перейти к 3. Иначе: положить min =  и перейти к 3.

3. Вычислить g'() = f T(x + d)d, затем сравнить g'() и m3g'(0). Если g'()≥m3g'(0), то конец. Если g'() < m3g'(0), то перейти к 4.

4. Положить min = .

5. Найти новое значение для  в интервале [min, max] и вернуться к 2.


Наиболее употребительные критерии окончания

процесса вычислений


|xnxn–1| <  (метод Ньютона);

KN (метод Фибоначчи);

I  , I - длина нового интервала (метод золотого сечения);

|x1x2| <  (кубическая интерполяция);

|f | <  - (кубическая интерполяция), где  - заданная точность.


Контрольные вопросы и задания


1. Для каких функций метод Ньютона–Рафсона имеет конечную сходимость?

2. Какова скорость сходимости метода Ньютона вблизи точки минимума?

3. Приведите пример отсутствия глобальной сходимости метода Ньютона.

4. Какое преимущество имеет метод секущих по сравнению с методом Ньютона?

5. Получите формулу секущих из формулы Ньютона, приближая вторую производную.

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

7. Почему метод Фибоначчи приводит к наименьшему возможному интервалу для конечного числа N вычислений значений функций?

8. Какое условие обеспечивает независимость длины полученного интервала от результата теста?

9. Как относятся длины последовательных интервалов в методе золотого сечения?

10. Покажите асимптотическую сходимость метода золотого сечения к методу Фибоначчи.

11. Укажите преимущество метода квадратичной интерполяции по сравнению с методами Ньютона и секущих.

12. Для каких функций применима квадратичная интерполяция?

13. Когда применяется метод дихотомии без производных?

14. Насколько уменьшается длина интервала в методе дихотомии?

15. Выведите зависимость длины интервала от количества вычислений значения функции.

16. К каким функциям применим метод дихотомии с производной?

17. Обеспечена ли глобальная сходимость для метода дихотомии?

18. Для каких функций применяется кубическая интерполяция?

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

20. В каких алгоритмах применяются методы Голдстейна, а в каких метод Вольфе–Пауэлла?


  1. Задания к лабораторной работе



1. Найти минимум функции:

а) F(x) = 2N(xN)2 + 16(xN);

б) F(x) = 40 + 90(xN)2;

в)

с точностями EPS = 1E–3, 1E–10, 1E–15.

2. Построить график функции N = 3 на терминале вблизи точки минимума.


  1. Отчет о работе



1. Титульный лист.

2. Задания к лабораторной работе.

3. Алгоритмы численного нахождения минимума.

4. График зависимостей количества итерации от точности решения.

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

6. Вывод по работе.


Список методов


1. Метод Ньютона.

2. Метод секущих.

3. Метод Фибоначчи.

4. Метод золотого сечения.

5. Квадратичная интерполяция.

6. Метод дихотомии.

7. Метод дихотомии с производной.

8. Кубическая интерполяция.

9. Метод Голдстейна.

10. Метод Вольфе–Пауэлла.


  1. Выбор метода решения



1. Порядковый номер студента в журнале по модулю 10.

2. Номер метода +5 по модулю 10.


Список рекомендуемой литературы


1. Карманов В.Г. Математическое программирование. М.: Наука, 1960.

2. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.

  1   2   3

Похожие:

Методические указания к лабораторным работам iconМетодические указания по лабораторным работам Факультет: электроэнергетический
Моделирование: методические указания по лабораторным работам. Вологда: Вогту, 2003. 35 с
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам
Методические указания к лабораторным работам разработан на основании рабочей программы дисциплины
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам по курсу
Методические указания к лабораторным работам по курсу "Internet технологии" для студентов специальности Т. 10. 01. 00 "Автоматизированные...
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам «спектральный анализ»
Методические указания к лабораторным работам «спектральный анализ» по спецкурсу «оптические методы анализа» для студентов 4 курса...
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам Муром 2005
Середа С. Н. Представление знаний в информационных системах. Логическое программирование/ Методические указания к лабораторным работам....
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам. Большаков А. А., Саратов, 2006. Паскаль: модули, стандартный модуль crt // Методические указания к лабораторным работам. Большаков А. А., Саратов, 2006. Программа для построения графиков. По «Корпус»
...
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам Рязань 2004
Дискретная математика: Методические указания к лабораторным работам / Рязанская государственная радиотехническая академия; Сост....
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам по курсу «Материаловедение»
Основные свойства строительных материалов: Методические указания к лабораторным работам по курсу «Материаловедение», «Строительные...
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам по дисциплине «Управление проектами»
Методические указания к лабораторным работам по дисциплине «Управление проектами» для студентов и слушателей факультета «Инженерный...
Методические указания к лабораторным работам iconМетодические указания к лабораторным работам по курсу прикладной геодезии Для студентов V курса заочного отделения факультета дистанционных форм обучения. Специальности «Прикладная геодезия»
Методические указания к лабораторным работам по курсу прикладной геодезии. Изд. МиигаиК. Упп «Репрография», 2011 г., с. 38
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница