Лекция: Алгоритм метода наискорейшего спуска

1) Задаются координаты начальной точки .

2) В точке, k = 0, 1, 2,…, вычисляется значение градиента .

3) Определяется величина шага путем одномерной минимизации по функции .

4) Определяются координаты точки :

i = 1,..., n .

5) Проверяются условия остановки итерационного процесса. В качестве критерия остановки итерационного процесса используются либо выполнениие условия малости приращения координат, либо выполнение условия малости градиента. Если они выполняются, то вычисления прекращаем. В противном случае осуществляем переход к п. 2.

Пример. 3.4.Найти минимума целевой функции

(3.39)

с начальными координатами поиска x1 = 2, x2 = 2 и значением функции y = 16.

Решение. Направление градиента определим по значениям частных производных:

;. (3.40)

В начальной точке значения частных производных соответственно равны: ¶y / ¶x1 = 2 (2) + 2= 6; ¶y / ¶x2 = 4 (2) + 2 = 10.

Обе частные производные положительны, поэтому значения целевой функции изменяются в том же направлении, что и. Если необходимо минимизировать функцию, то нужно уменьшать значения и в отношении: ¶y / ¶x1:¶y / ¶x2 = 6:10 = 0.6.

Шаг изменения по переменной x2 примем равным 0,5, соответственно по переменной x1 он будет равным 0,6 × 0,5 = 0,3. Изменения переменных с этими шагами проводится до достижения минимума целевой функции. Результаты пошагового движения к оптимуму приведены в табл. 3.14.

Таблица 3.14

x1	x2	y
1,7	1,5	9,94
1,4	1,0	5,36
1,1	0,5	2,26
0,8	0,64
0,5	— 0,5	0,5
0,2	— 1	1,84

В точке с наименьшим значением функции вычислим новое направление градиента: ¶y / ¶x1 = 2 (0,5)-0,5 = 0,5; ¶y / ¶x2 = 4(-0,5) + 0,5 = -1,5. В соответствии со значениями производных отношение шагов движения к оптимуму по переменным должно быть равным 1:3. Отрицательный знак производной по переменной x2 означает, что для уменьшения целевой функции необходимо эту переменную увеличивать. Если принять шаг движения к оптимуму по второй переменной Dx2 = 0,3, получим Dx1 = 0,1. Движение к оптимуму по новому направлению будет иметь следующие результаты (табл. 3.15).

Таблица 3.15

x1	x2	y
0,5	— 0,5	0,5
0,4	— 0,2	0,16
0,3	0,1	0,14
0,2	0,3	0,44

Точку с наилучшим выходом можно использовать для нового направления движения к оптимуму, пока не будет достигнута оптимальная точка с погрешностью 0.1.

3.5.8. Упражнения для самостоятельной работы

к теме «Задачи многомерной оптимизации»

Минимизировать функцию:

1. ,

2. ,

3. ,

4. ,

5. ,

6. ,

7. ,

8. ,

9. ,

10. ,

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

1. В чем состоит свойство унимодальности функции и в чем заключается важное значение этого свойства при решении задач оптимизации с одной переменной?

2. Опишите алгоритм метода сканирования и метода дихотомии.

3. Опишите алгоритм метода золотого сечения.

4. Дайте общие характеристики методам прямой и косвенной многомерной оптимизации.

5. Что является критерием для прекращения итерационного процесса в методе Гаусса-Зейделя?

6. Опишите алгоритм метода Гаусса-Зейделя.

7. На каком свойстве градиента основаны все градиентные методы поиска экстремума функции?

8. Опишите алгоритм метода градиента.

9. Охарактеризуйте метод наискорейшего спуска.

10. Проведите сравнительный анализ рассмотренных методов.

Библиографический список

1. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986.

2. Андреев В.В., Филимонова Т.К. Лабораторные работы по курсу «Математическое моделирование». Казань: КГЭИ, 1999.

3. Андреев В.В., Филимонова Т.К. Лабораторный практикум по курсу «Математические методы в экономике». Казань: КГЭУ, 2001.

4. Андреев В.В. Табличный процессор Excel в экономических расчетах. Учебное пособие по курсу „Технологическая обработка экономической информации”. Казань: КГЭУ, 2002.

5. Аоки М. Введение в методы оптимизации. М.: Наука, 1977.

6. Балашевич В.А. Основы математического программирования. Минск: Вышэйшая школа, 1985.

7. Банди Б. Основы линейного программирования. М.: Радио и связь, 1989.

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

9. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987.

10. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учебное пособие. М.: Финансы и статистика, 2001.

11. Боглаев П.Ю. Вычислительная математика и программирование. М.: Высшая школа, 1990.

12. Боглов В.А, Демидович Б.П., Ефимов А.В. и др.: Сборник задач по математике для вузов. Ч.1. Линейная алгебра и основы математического анализа. Учебное пособие для втузов. М.: Наука. 1986.

13. Браверман Э.М. Математические модели планирования и управления в экономических системах. М.: Наука, 1976.

14. Васильков Ю.В., Василькова Н.Н. Компьютерные технологии вычислений в математическом моделировании. М.: Финансы и статистика, 2002.

15. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979.

16. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Наука, 2000.

17. Вержбицкий В.М. Численные методы. Математический анализ и обыкновенные дифференциальные уравнения. М: Высшая школа, 2001.

18. Волков Е.А. Численные методы. М.: Наука, 1982.

19. Воробьева Г.Н., Данилова А.Н. Практикум по вычислительной математике. М.: Высшая школа, 1990.

20. Гарнаев А. Использование MS Excel и VBA в экономике и финансах. СПб.: БХВ – Санкт-Петербург, 2000.

21. Гершгорн А.С. Математическое программирование и его применение в экономических расчетах. М.: Экономика, 1968.

22. Грешилов А.А. Как принять наилучшее решение в реальных условиях. М.: Радио и связь, 1991.

23. Демидович Б.П.: Марон И.А. Основы вычислительной математики. М.: Наука, 1979.

24. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. Приближение функций, дифференциальные и интегральные уравнения. М.: Наука, 1967.

25. Дьяконов В.П. Справочник по Mathcad PLUS 6.0. М.: “СК Пресс”, 1997.

26. Дьяконов В.П. Справочник по алгоритмам и программам на языке Бейсик для персональных ЭВМ. М.: Наука, 1987.

27. Дьяконов В.П. Справочник по Mathcad 7.0. PRO. М.: “СК Пресс”, 1998.

28. Дьяконов В.П., Абраменкова И.В. Mathcad 7.0 в математике, физике и в Internet. М.: “Нолидж”, 1999.

29. Ефимова М.Р., Петрова Е.В., Румянцева В.Н. Общая теория статистики. М.: ИНФРА-М, 2000.

30. Каганов В.И. Компьютерные вычисления в средах Excel и MathCad. М.: Горячая линия Телеком, 2003.

31. Калиткин Н.Н. Численные методы. М.: Наука,1978.

32. Каранчук В.П., Сваровский И.Н., Суздальницкий И.Д. Основы применения ЭВМ. М.: Радио и связь, 1988.

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

34. Коллатц Л… Численные методы решения дифференциальных уравнений. М.: Издательство иностранной литературы, 1953.

35. Кофман А. Методы и модели исследования операций. Т. 1. М.: Мир, 1966.

36. Кудрявцев Е.М. MATHCAD 2000 Pro. М.: ДМК Пресс, 2001.

37. Кузнецов Ю.Н., Кузубов В.И, Волощенко А.Б… Математическое программирование. М.: Высшая школа, 1980.

38. Лавренов С.М. Excel: Сборник примеров и задач. М.: Финансы и статистика, 2002.

39. Лаврентьев М.М., Романов В.Г., Шишатский С.П. Некорректные задачи математической физики и анализа. М.: Наука, 1980.

40. Ларсен Р.У. Инженерные расчеты в Excel. М.: Издательский дом «Вильямс», 2002.

41. Левшиц В.М., Литвин Б.Ф. Приближенные вычисления и программирование на ЭВМ «Наири-2».: Машиностроение, 1977.

42. Львовский Е.Н… Статистические методы построения эмпирических формул. М.: Высшая школа, 1988.

43. Ляшенко И.Н., Карагодова Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. Киев: Вища школа, 1975.

44. Малыхин В.И. Математика в экономике. Учебное пособие. М.: ИНФРА-М, 2001.

45. Метьюз Д.Г., Финк К.Д… Численные методы. Использование MATLAB. М.: Издательский дом «Вильямс», 2001.

46. Mathcad 6.0 PLUS. Финансовые, инженерные и научные расчеты в среде Windows 95 / Перевод с англ. М.: Информационно-издательский дом “Филинь”, 1996.

47. Норкин С.Б. и др. Элементы вычислительной математики. М.: Высшая школа, 1966.

48. Орлова И.В. Экономико-математические методы и модели. Выполнение расчетов в среде Excel. Практикум: Учебное пособие для вузов. М.: ЗАО „Финстатинформ”, 2000.

49. Очков В.Т. Mathcad PLUS 6.0 для студентов и инженеров. М.: “Компьютер-Пресс”, 1996.

50. Очков В.Т. Mathcad 8.0 PRO для студентов и инженеров. М.: “Компьютер-Пресс”, 1999.

51. Покровский Г.Б., Ананьева М.П… Программирование на языке Бейсик. Казань: Издательство Казанского университета, 1987.

52. Попов А.А. Excel: Практическое руководство. М.: ДЕСС КОМ, 2001.

53. Попов Ю.П., Самарский А.А. Вычислительный эксперимент. Компьютеры, модели, вычислительный эксперимент. Ведение в информатику с позиций математического моделирования. М.: Наука, 1988.

54. Рахимов Л.И. Численные методы математического моделирования. Учебное пособие Казань: Издательство КГЭУ, 2001.

55. Реклейстер Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. В 2-х тт. М.: Мир, 1986.

56. Самарский А.А. Предисловие в кн. Компьютеры, модели, вычислительный эксперимент. Ведение в информатику с позиций математического моделирования. М.: Наука, 1988.

57. Самарский А.А., Гулин А.В. Численные методы. М.: Наука, 1989.

58. Самарский А.А., Курдюков С.П. Парадоксы многовариантного нелинейного мира – мира вокруг нас. В кн. Гипотезы. Прогнозы. (Будущее науки): Международный ежегодник. Вып. 22. М.: Знание, 1989.

59. Смирнова Л.И., Шарифуллин В.Н. Статистический пакет Statgraphics в инженерных расчетах. Казань: КФ МЭИ, 1996.

60. Солодовников А.С., Бабайцев Б.А., Браилов А.В. Математика в экономике: Учебник. Ч.1. М.: Финансы и статистика, 2001.

61. Солодовников А.С., Бабайцев Б.А., Браилов А.В. Математика в экономике: Учебник. Ч.2. М.: Финансы и статистика, 2001.

62. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1974.

63. Тихонов А.Н., Костомаров Д.П. Вводные лекции по прикладной математике. М.: Наука, 1984.

64. Турчак Л.И. Основы численных методов. М.: Наука, 2002.

65. Филимонова Т.К., Шарифуллин В.Н… Математический пакет Mathcad в технико-экономических расчетах. Казань: КФ МЭИ, 1997.

66. Филиппов А.Ф. Сборник задач по дифференциальным уравнениям: Учебное пособие для вузов. М.: Наука, 1985.

67. Фурунжиев Р.И., Бабушкин Ф.М., Варавко В.В. Применение математических методов и ЭВМ. Минск: Вышэйшая школа, 1988.

68. Хемминг Р.В. Численные методы для научных работников и инженеров. М.: Наука, 1972.

69. Шарифуллин В.Н. Задачи линейного программирования. Методические указания по курсу „Математические методы в экономике”. Казань: КФ МЭИ, 1996.

70. Шарифуллин В.Н. Математический пакет Eureka в инженерных задачах. Методические указания по курсу „Численные методы моделирования”. Казань: КФ МЭИ, 1996.

71. Шелобаев С.И. Математические методы и модели в экономике, финансах и бизнесе. Учебное пособие. М.: Юнити, 2000.

72. Шуп Т. Прикладные численные методы в физике и технике. М.: Высшая школа, 1990.

73. Шуп Т. Решение инженерных задач на ЭВМ. М.: Мир, 1982.

74. Юдин Д.Б., Гольдштейн Е.Г. Линейное программирование. Теория, методы, приложения. М.: Наука, 1969.

СОДЕРЖАНИЕ

Введение........................................................
ГЛАВА 1. Численные методы решения нелинейных уравнений и систем нелинейных и линейных уравнений..........................
1.1. Численное решение нелинейных уравнений.......................	‑
1.1.1. Общие положения............................................	‑
1.1.2. Метод простой итерации......................................
1.1.3. Метод половинного деления (дихотомии, бисекции)...............
1.1.4. Метод касательных (метод Ньютона)............................
1.1.5. Решение нелинейных уравнений в среде пакета Excel..............
1.1.6. Решение уравнений в пакете Mathcad............................
1.1.7. Упражнения для самостоятельной работы по теме «Численное решение нелинейных уравнений».........................
1.2. Численные методы решения систем нелинейных уравнений..........
1.2.1. Метод Ньютона для системы нелинейных уравнений..............	‑
1.2.2. Решение систем нелинейных уравнений в среде пакета Excel.......
1.2.3. Решение систем нелинейных уравнений в пакете Mathcad..........
1.2.4. Упражнения для самостоятельной работы по теме «Решение систем нелинейных уравнений».............................
1.3. Решение систем линейных уравнений…...........................	‑
1.3.1. Общие положения...........................................	‑
1.3.2. Метод Гаусса решения систем линейных уравнений...............
1.3.3. Метод Зейделя..............................................
1.3.4. Решение систем линейных уравнений в среде пакета Excel..........
1.3.5. Решение систем линейных уравнений в пакете Mathcad............
1.3.6. Упражнения для самостоятельной работы к теме «Решение систем линейных уравнений»..............................
Глава 2. Численное дифференцирование и интегрирование...............
2.1. Численное дифференцирование..................................	‑
2.1.1. Общие положения............................................	‑
2.1.2. Применение интерполяционного многочлена Лагранжа для численного дифференцирования.................................
2.1.3. Применение интерполяционного многочлена Ньютона.............
2.1.4. Численное дифференцирование в среде пакета Excel...............
2.1.5. Нахождение производной в пакете Mathcad и в пакете Eureka..................................................
2.1.6. Упражнения для самостоятельной работы по теме «Численное дифференцирование»....................................
2.2. Численное интегрирование......................................
2.2.1. Постановка задачи численного интегрирования...................	‑
2.2.2. Формула прямоугольников.....................................
2.2.3. Метод трапеций..............................................
2.2.4. Метод Симпсона (метод парабол)...............................
2.2.5. Численное интегрирование в среде пакета Excel...................
2.2.6. Вычисление определенного интеграла в пакете Mathcad и в пакете Eureka..................................................
2.2.7. Упражнения для самостоятельной работы по теме «Численное интегрирование».......................................	‑
2.3. Численные методы решения обыкновенных дифференциальных уравнений......................................
2.3.1. Основные понятия............................................	‑
2.3.2. Задача Коши.................................................
2.3.3.Метод Эйлера................................................
2.3.4. Метод Рунге-Кутта...........................................
2.3.5. Системы дифференциальных уравнений.........................
2.3.6. Краевые задачи..............................................
2.3.7. Численные методы решения обыкновенных дифференциальных уравнений в среде пакета Excel......................................
2.3.8. Решение дифференциальных уравнений в пакете Mathcad..........
2.3.9. Упражнения для самостоятельной работы по теме «Численные методы решения дифференциальных уравнений»............
Глава 3. Задачи оптимизации........................................
3.1. Постановка задачи оптимизации.................................	‑
3.1.1. Выбор критерия оптимальности................................	‑
3.1.2. Управляющие параметры и ограничения на их изменение..........
3.1.3. Составление целевой функции и математического описания задачи оптимизации...............................................	‑
3.1.4. Выбора метода оптимизации...................................
3.2. Задачи линейного программирования.............................
3.2.1. Задача оптимального планирования производства.................	‑
3.2.2. Задача приготовления оптимальных смесей и рационов............
3.2.3. Задача оптимального раскроя материала.........................
3.3. Решение задачи линейного программирования симплекс-методом.....
3.4. Оптимизация в среде пакета Excel................................
3.5. Решение задачи линейного программирования в пакете Mathcad и в пакете Eureka..................................................
3.6. Упражнения для самостоятельной работы к теме «Задачи линейного программирования»...............................
3.5. Методы нелинейного программирования..........................
3.5.1. Методы одномерного поиска...................................	‑
3.5.2. Метод сканирования..........................................
3.5.3. Метод дихотомии (метод деления отрезка пополам)...............
3.5.4. Решение задачи одномерной оптимизации в пакете Mathcad........
3.5.5. Упражнения для самостоятельной работы к теме «Задачи одномерной оптимизации»..................................	‑
3.5.6. Методы многомерной оптимизации.............................
3.5.7. Метод наискорейшего спуска..................................	‑
3.5.8. Упражнения для самостоятельной работы к теме «Задачи многомерной оптимизации».................................
Библиографический список.........................................