Методы оптимизации и вычислительная геометрия
Заказать уникальную курсовую работу- 33 33 страницы
- 5 + 5 источников
- Добавлена 29.12.2014
- Содержание
- Часть работы
- Список литературы
- Вопросы/Ответы
1. Цель, задачи и этапы выполнения курсовой работы 4
2. Метод ломаных 6
2.1 Описание метода ломаных 6
2.2 Описание программы, реализующей метод ломаных 8
3. Метод наискорейшего спуска 12
3.1 Общая схема методов спуска 12
3.2 Описание метода градиентного спуска 14
3.3 Описание метод наискорейшего спуска 17
3.4 Описание метода наискорейшего спуска для квадратичных функций 18
3.5 Описание программы, реализующей метод наискорейшего спуска 20
ЗАКЛЮЧЕНИЕ 25
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 26
ПРИЛОЖЕНИЕ А. Блок-схема к программе, реализующей метод ломаных 27
ПРИЛОЖЕНИЕ Б. Листинг программы, реализующей метод ломаных 30
ПРИЛОЖЕНИЕ В. Блок-схема программы, реализующей метод наискорейшего спуска 32
ПРИЛОЖЕНИЕ Г. Листинг программы, реализующей метод наискорейшего спуска 33
Метод наискорейшего спуска по сравнению с обычным градиентным методом дает некоторое ускорение, метод хорошо "работает" при минимизации гладких функций и если начальное приближение выбрано достаточно далеко от оптимума. Если же очередная точка окажется в окрестности оптимума, то уменьшение целевой функции будет очень медленным. Это происходит из-за того, что для получения оптимума с высокой точностью необходимо выполнить большое число мелких шагов.Метод наискорейшего спуска хотя не дает особенного ускорения сходимости он свободен от параметров и на практике может дать некоторый выигрыш, особенно на начальных итерациях.В связи с этим в программе был реализован более точный метод градиентного спуска.В качестве условия окончания поиска задаётся требуемая малость модуля градиента функции, т.е. должно выполнятся условие(в области оптимума градиент равен 0, но достичь этого значения практически не возможно, поэтому задаётся требуемая малость близкая к 0).Программа написана на языке программирования VBA в среде MicrosoftOfficeExcel.Программа имеет понятный интуитивный графический интерфейс (рисунок3.1).Рисунок 3.1 Главное окно программыПосле запуска необходимо ввести требуемую точность вычислений (рисунок3.2).Рисунок 3.2 Ввод входных значенийЗатем программа рассчитывает точки приближения и находит для данных ограничений точку минимума (рисунок3.3).Рисунок 3.3 Вывод результатов расчетаТаблица расчетов приведена в таблице 3.1.Таблица 3.1 Расчет поиска минимума по методу наискорейшего спуска0,013868-0,298630,6609110,072739-0,308160,6116090,116095-0,313540,5851910,147855-0,316320,5711460,170995-0,317580,5637370,187777-0,317970,5598530,199903-0,317920,5578290,208643-0,317680,5567770,214929-0,317380,5562320,219445-0,317080,5559510,222686-0,316820,5558050,225011-0,316610,555730,226678-0,316430,5556920,227873-0,31630,5556720,22873-0,31620,5556620,229344-0,316120,5556560,229784-0,316060,5556540,230099-0,316020,5556520,230326-0,315990,5556520,230488-0,315970,5556510,230604-0,315950,5556510,230687-0,315940,555651График поверхности представлен на рисунке 3.4.Рисунок 3.4 График поверхности Таким образом в результате применения метода наискорейшего спуска и реализации этого метода программным образом был найден минимум функции с заданной точностью ЗАКЛЮЧЕНИЕВ результате выполнения данной курсовой работы:Проанализированы теоретические основы методов оптимизации и вычислительной геометрии.Освоены основные этапы процесса постановки задачи оптимизации.Произведено построение и анализ математической модели, осуществлен выбор адекватного метода ее исследования.Применены на практике теоретические знания из разделов данного курса.СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВПиявский С. А. Один алгоритм отыскания абсолютного экстремума функций // Журнал вычислительной математики и математической физики, т.12, № 4 (1972), стр. 885—896.Норкин В. И. О методе Пиявского для решения общей задачи глобальной оптимизации // Журнал вычислительной математики и математической физики, т.32, № 7 (1992), стр. 992—1006.Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986. — С. 298-311.Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.ПРИЛОЖЕНИЕ А. Блок-схема к программе, реализующей метод ломаныхПРИЛОЖЕНИЕ Б. Листинг программы, реализующей метод ломаныхPrivate Sub CommandButton1_Click()Dim a, b, e, L, x1, x2, fx1, fx2a = Val(TextBox1.Value)b = Val(TextBox2.Value)e = Val(TextBox3.Value)L = Abs((a * Sin(a) + 2 * Cos(a)) / (a * a * a))For i = a To b Step 0.01 If Abs((i * Sin(i) + 2 * Cos(i)) / (i * i * i)) > L Then L = Abs((i * Sin(i) + 2 * Cos(i)) / (i * i * i)) End IfNext iCells(5, 11) = Lx0 = (a + b) / 2 + (Cos(a) / (a * a) - Cos(b) / (b * b)) / (2 * L)Cells(2, 11) = x0k = 0For i = 0 To 100 Cells(2 + i, 12) = "" Cells(2 + i, 13) = "" Cells(2 + i, 14) = "" Cells(2 + i, 15) = ""Next iDo While Abs(a - b) >= e x1 = (a + x0) / 2 + (Cos(a) / (a * a) - Cos(x0) / (x0 * x0)) / (2 * L) x2 = (x0 + b) / 2 + (Cos(x0) / (x0 * x0) - Cos(b) / (b * b)) / (2 * L) fx1 = Cos(x1) / (x1 * x1) fx2 = Cos(x2) / (x2 * x2) Cells(2 + k, 12) = x1 Cells(2 + k, 13) = x2 Cells(2 + k, 14) = fx1 Cells(2 + k, 15) = fx2 If fx1 < fx2 Then a = x1 x0 = x2 Else b = x2 x0 = x1 End If k = k + 1LoopIf (Cos(x1) / (x1 * x1)) < (Cos(x2) / (x2 * x2)) Then TextBox5.Value = Round(x1, 4) TextBox4.Value = Round(Cos(x1) / (x1 * x1), 5)Else TextBox5.Value = Round(x2, 4) TextBox4.Value = Round(Cos(x2) / (x2 * x2), 5)End IfCells(18, 7) = TextBox5.ValueCells(18, 8) = TextBox4.ValueEnd SubПРИЛОЖЕНИЕ В. Блок-схема программы, реализующей метод наискорейшего спускаПРИЛОЖЕНИЕГ. Листинг программы, реализующей метод наискорейшего спускаPrivate Sub CommandButton1_Click()Dim e, L, x(1000), y(1000), f(1000) As Double, modgrade = Val(TextBox3.Value)x(0) = 1y(0) = 1h = 1f(0) = x(0) ^ 2 + 2 * y(0) ^ 2 + Exp(x(0) ^ 2 + y(0) ^ 2) - x(0) + 2 * y(0)For i = 0 To 100 Cells(2 + i, 12) = "" Cells(2 + i, 13) = "" Cells(2 + i, 14) = ""Next ii = 11: x(i) = x(i - 1) - h * (2 * x(i - 1) + 2 * x(i - 1) * Exp(x(i - 1) ^ 2 + y(i - 1) ^ 2) - 1) y(i) = y(i - 1) - h * (4 * y(i - 1) + 2 * y(i - 1) * Exp(x(i - 1) ^ 2 + y(i - 1) ^ 2) + 2) f(i) = x(i) ^ 2 + 2 * y(i) ^ 2 + Exp(x(i) ^ 2 + y(i) ^ 2) - x(i) + 2 * y(i) Cells(1 + i, 12) = x(i) Cells(1 + i, 13) = y(i) Cells(1 + i, 14) = f(i) R = f(i) - f(i - 1) If R > 0 Then h = h / 2 GoTo 1 End If modgrad = Sqr((2 * x(i) + 2 * x(i) * Exp(x(i) ^ 2 + y(i) ^ 2) - 1) ^ 2 + (4 * y(i) + 2 * y(i) * Exp(x(i) ^ 2 + y(i) ^ 2) + 2) ^ 2) If modgrad > e Then i = i + 1 GoTo 1 End If TextBox5.Value = Round(x(i), 4) TextBox6.Value = Round(y(i), 4) TextBox4.Value = Round(f(i), 4)Cells(18, 7) = TextBox5.ValueCells(18, 8) = TextBox6.ValueCells(18, 9) = TextBox4.ValueEnd Sub
2. Норкин В. И. О методе Пиявского для решения общей задачи глобальной оптимизации // Журнал вычислительной математики и математической физики, т.32, № 7 (1992), стр. 992—1006.
3. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986. — С. 298-311.
4. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
Вопрос-ответ:
Какая цель задачи и какие этапы выполнения курсовой работы?
Целью задачи является изучение методов оптимизации и вычислительной геометрии. Этапы выполнения курсовой работы включают ознакомление с основными методами оптимизации, разработку программы, реализующей метод ломаных, а также проведение численных экспериментов и анализ результатов.
Что такое метод ломаных и как он работает?
Метод ломаных - это численный метод оптимизации, используемый для нахождения минимума функции. Он основан на аппроксимации функции ломаной линией и последовательном уточнении этой аппроксимации. Метод ломаных является итерационным методом, который на каждом шагу перебирает определенные точки и выбирает лучшую из них.
Как работает программа, реализующая метод ломаных?
Программа, реализующая метод ломаных, состоит из нескольких этапов. На первом этапе задается исходная функция и начальное приближение точки минимума. Затем происходит итерационный процесс, включающий аппроксимацию функции ломаной линией, выбор наилучшей точки и переход к следующему шагу. Итерации продолжаются до достижения заданной точности или удовлетворения другому критерию остановки.
Что такое метод наискорейшего спуска и как он работает?
Метод наискорейшего спуска - это численный метод оптимизации, который использует градиент функции для поиска ее минимума. Он основан на идее движения в направлении, противоположном градиенту функции, для нахождения точки минимума. Метод наискорейшего спуска является итерационным методом, который на каждом шагу пересчитывает направление спуска и величину шага.
Что включает в себя программа, реализующая метод наискорейшего спуска?
Программа, реализующая метод наискорейшего спуска, включает несколько этапов. На первом этапе задается исходная функция и начальное приближение точки минимума. Затем происходит итерационный процесс, включающий вычисление градиента функции, определение направления спуска, выбор оптимального размера шага и переход к следующему шагу. Итерации продолжаются до достижения заданной точности или удовлетворения другому критерию остановки.
Какова цель выполнения курсовой работы?
Целью выполнения курсовой работы по методам оптимизации и вычислительной геометрии является изучение различных методов оптимизации и их программной реализации, а также применение этих методов для решения конкретных задач.
Какой метод используется в данной статье?
В данной статье рассматривается метод ломаных и метод наискорейшего спуска как методы оптимизации.
Как описывается метод ломаных?
Метод ломаных представляет собой метод оптимизации, в котором происходит аппроксимация целевой функции ломаными линиями. В каждом шаге происходит построение ломаной линии и нахождение пересечения с целевой функцией, затем выбирается точка с наименьшим значением функции и движение продолжается в этом направлении.
Как описывается метод наискорейшего спуска?
Метод наискорейшего спуска является методом оптимизации, при котором на каждом шаге происходит движение в направлении, противоположном направлению градиента целевой функции. Таким образом, на каждом шаге происходит поиск оптимальной точки спуска.
Как реализована программа для метода наискорейшего спуска?
Программа для метода наискорейшего спуска реализует алгоритм движения в сторону, противоположную градиенту целевой функции. Выполняется поиск оптимальной точки спуска с использованием метода линейного поиска.
Что такое методы оптимизации и вычислительная геометрия?
Методы оптимизации и вычислительная геометрия - это разделы математики, которые занимаются разработкой алгоритмов и методов для решения задач оптимизации функций и применения геометрических методов для решения вычислительных задач.
Какова цель задачи и этапы выполнения курсовой работы в методах оптимизации и вычислительной геометрии?
Целью задачи курсовой работы в методах оптимизации и вычислительной геометрии является разработка и реализация алгоритма оптимизации функции с использованием геометрических методов, а также проведение исследования и сравнение полученных результатов. Этапы выполнения курсовой работы включают изучение литературы по теме, формулировку постановки задачи, выбор метода оптимизации, программную реализацию метода, проведение экспериментов на тестовых функциях и анализ результатов.