Исследование методов оптимизации

КурсоваяПомощь в написанииУзнать стоимостьмоей работы

Исследование методов оптимизации (реферат, курсовая, диплом, контрольная)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ХАРЬКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ»

Факультет информатики и управления Кафедра экономической кибернетики и маркетингового менеджмента КУРСОВАЯ РАБОТА По математическому программированию

Исследование методов оптимизации

Харьков 2009

РЕФЕРАТ

Данная курсовая работа содержит: 41 страницу, 16 таблиц, 6 графиков.

В курсовой работе рассмотрены теоретические основы двух методов оптимизации математического программирования :

— метод Нелдера-Мида ;

— градиентный метод с дроблением шага.

Произведена минимизация исследуемой функции указанными методами. Выявлена зависимость числа итераций от заданной точности. Сопоставлена трудоемкость и эффективность оптимизации заданной функции различными методами (градиентным и методом Нелдера-Мида).

Ключевые термины:

Градиент — вектор первых частных производных функции.

Линии уровня — множества точек, в которых функция принимает постоянные значения, т. е.

Методы нулевого порядка — методы, которые не предполагают вычисления производной для поиска оптимума.

Методы первого порядка — методы, в которых кроме вычисления функции в любой точке предлагается вычисление первых производных.

1. Введение

2. Математическое описание методов оптимизации

2.1 Метод Нелдера-Мида

2.2 Градиентный метод с дроблением шага

3. Решение задачи минимизации для каждого из методов

3.1 Метод Нелдера-Мида

3.2 Градиентный метод с дроблением шага

4. Графическая интерпретация решения задачи

5. Аналитическое исследование методов

6. Заключение

7. Приложение

8. Список литературы

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ

— точка

— длинна шага

— вектор градиент

E — точность

N — количество итераций Д — матрица координат симплекса

t — длинна ребра симплекса

1. ВВЕДЕНИЕ

Объектом исследования предмета математическое программирование являются задачи оптимизации.

Оптимизация подразумевает нахождение наилучшего варианта среди всех существующих. В любой практической оптимизационной задаче существует много совпадающих этапов. Наиболее важным этапом является моделирование рассматриваемой физической ситуации с целью получения математической функции, которую необходимо минимизировать, а также определения ограничений, если таковые существуют. Затем следует выбрать подходящую процедуру для осуществления минимизации. Эта процедура должна быть реализована на практике, что во многих реальных случаях вынуждает использовать ЭВМ для выполнения большого объема вычислений.

Универсальных методов, подходящих для поиска экстремума абсолютно любой функции не существует. Данная курсовая работа ставит себе целью исследовать метод оптимизации нулевого порядка — метод Нелдера-Мида, а также метод оптимизации первого порядка — градиентный метод с дроблением шага на примере конкретной функции. Таким образом, получив практические результаты, можно будет сравнить эффективность рассматриваемых методов, применяемых к исследуемой функции.

ПОСТАНОВКА ЗАДАЧИ (Вариант задания 1)

Исследовать функцию типа :

Используемые методы минимизации :

1. Метод: Нелдера-Мида.

2. Метод: Градиентный с дроблением шага.

Необходимо :

1. Решить задачу минимизации, начав итерации из выбранной начальной точки x0=(1;1) заданными по варианту методами, необходимая точность решения. Привести таблицу результатов расчета типа: Итерация: — точка: значение: критерий: .

2. Рассчитать 3 линии уровня функции и изобразить их на графике.

3. Отобразить на графиках линий уровня для каждого из заданных методов траекторию движения по итерациям (траекторию спуска).

4. Выявить зависимость числа итераций N от заданной точности E, значения точности:, ,, ,,. Привести таблицу результатов как в п. 1 для каждого значения E.

5. Сравнить эффективность рассмотренных в варианте методов по числу итераций N, построить графики N=F (E).

2. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ

2.1 Метод Нелдера-Мида

Вводится симплекс, координаты вершин которого заданы таблицей (одна из вершин в начале координат).

t — некоторое выбранное число.

Если n = 2, то при t = 1 имеем Расположение симплекса показано на рисунке 2.1

Рисунок 2.1- Начальное расположение симплекса

Легко убедиться в том, что если координаты вершин симплекса задать в соответствии с матрицей Д₀, то расстояние между двумя любыми вершинами симплекса всегда будет равно выбранной константе t независимо от размерности задачи n .

Действительно, расстояние между любой вершиной x_j, j= 2,3,., n+1, и вершиной x₁ равно С другой стороны, расстояние между любой парой вершин, ,, равно Зададим начальную точку процедуры поиска минимума вектором Перенесем исходный симплекс таким образом, чтобы вершина, находившаяся в начале координат, оказалась в точке. Получим матрицу Вычислим значения оптимизируемой функции в точках и переномеруем точки так, чтобы выполнялись неравенства :

Найдем координаты центра тяжести фигуры, получающейся в результате удаления вершины :

Осуществим отражение вершины относительно центра тяжести. Получим точку

Если a=1, то получим зеркальное отражение. В одномерном случае процедура отражения, обеспечивающая получение точки, симметричной точке относительно иллюстрируется рис. 2.2

Рисунок 2.2 — Построение точки

Сравним теперь между собой значения

Возможны следующие варианты а). В этом случае выполняется растяжение симплекса и отыскивается точка

Параметр обычно принимается равным 1,5.

Полученная точка заменяет, если. В противном случае для замены используется точка .

б). При этом реализуется отражение. Точка заменяет .

в). В этом случае осуществляется сжатие и отыскивается точка

Параметр обычно принимается равным 0,5. Точка заменяет .

г). При этом осуществляется редукция (уменьшение размера симплекса путем приближения всех его вершин к вершине). Координаты вершин нового симплекса рассчитываются по формулам Критерий останова вычислительной процедуры имеет вид :

Критерий останова J является составным. При этом его компоненты имеют различный вес в зависимости от того, каков характер поведения оптимизируемой функции в окрестности экстремума. Если в районе экстремума оптимизируемая функция изменяется по типу «глубокая впадина», то больший вклад в численное значение критерия J вносит первое слагаемое, а второе при этом быстро уменьшается. Напротив, если оптимизируемая функция изменяется по типу «пологое плато», то первое слагаемое быстро становится малым и поэтому второе слагаемое вносит больший вклад в величину критерия J.

Модификация метода

Описанный «классический» вариант построения алгоритма метода Нелдера-Мида обладает конструктивным недостатком, который состоит в следующем. Предположим, что оптимизируемая функция, для простоты, двух переменных имеет вид глубокого оврага с очень пологим дном. Тогда может случиться так, что симплекс, который в рассматриваемом случае представляет собой треугольник, в какой-то момент двумя вершинами ляжет на дно оврага, а третья окажется на его склоне. При этом на очередном шаге произойдет переброс этой вершины на другой склон, а затем редукция или сжатие симплекса. Если склон оврага крутой, то эта процедура повторится много раз, в результате чего симплекс сожмется и может сработать критерий останова, хотя до точки минимума еще может быть очень далеко. Естественное усовершенствование алгоритма состоит в следующем. После срабатывания критерия останова целесообразно построить над центром тяжести сжавшегося симплекса новый, размеры которого соответствуют исходному симплексу. Пусть координаты центра тяжести сжавшегося симплекса образуют вектор

Найдем теперь координаты точки такой, что центр тяжести симплекса с длиной ребра, равной t, использующего вершину в качестве начальной, совпадал бы с. Матрица координат указанного симплекса имеет вид

(2.1)

Координаты центра тяжести этого симплекса образуют вектор Теперь координаты точки найдем из равенства =, откуда где

Подставляя вычисленные значения в выражение (2.1), получим требуемый симплекс, используя который продолжим процедуру поиска минимума. С другой стороны, для продолжения процедуры в качестве начальной точки может быть использован центр тяжести «сжавшегося» симплекса. Возникающее при этом смещение нового симплекса относительно сжавшегося (точки предполагаемого останова) во многих случаях может даже оказаться полезным. Эту процедуру считаем законченной, если после очередного сжатия алгоритм приведет в точку, расстояние от которой до точки предыдущего сжатия не превосходит некоторого достаточно малого .

2.2 Градиентный метод с дроблением шага

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

(2.2)

Методы построения таких последовательностей называют методами спуска. Пусть Поставим задачу отыскания последовательности ., сходящейся к .

Выберем произвольным образом точку, направление и сконструируем луч

. (2.3)

Рассмотрим вопрос о выборе направления, обеспечивающего (2.2). Для этого изучим поведение вдоль луча. Имеем

Введем

(2.4)

Здесь

В соответствии с (2.3)

Тогда

Вычислим (2.5)

Теперь, чтобы для любого обеспечить отрицательность (2.5), достаточно положить, где произвольная положительно определенная матрица. Тогда При этом (2.6)

Выбрав каким-либо образом, получим Затем аналогично рассчитаем

Общее рекуррентное соотношение имеет вид :

(2.7)

Различные варианты градиентных процедур отличаются друг от друга способом выбора .

Полученное соотношение (2.7) обеспечивает построение последовательности точек, сходящейся к точке, минимизирующей. Понятно, что каждая из точек этой последовательности может рассматриваться как некоторое приближение к точке минимума, положение которого, вообще говоря, остается неизвестным в ходе всей процедуры спуска. Поэтому для всех таких процедур принципиальной остается проблема останова. В вычислительной практике часто используются следующие критерии останова:

(2.8)

(2.9)

где инекоторые достаточно малые числа .

Понятно, что критерий (2.8) хорош в тех случаях, когда функция в окрестности минимума, используя ранее введенную классификацию, имеет характер «глубокой» впадины. С другой стороны, если функция ведет себя как «пологое плато», то более предпочтительным является критерий (2.9). Аналогом критерия (2.8) является другое часто применяемое правило останова :

(2.10)

использующее необходимое условие экстремума функции. Очевидным недостатком критериев (2.8)-(2.10) является то, что их качество существенно зависит от абсолютных значений величины и компонентов векторов ,. Более универсальными являются относительные критерии :

(2.11)

(2.12)

(2.13)

Заметим, что очень часто на практике используются составные критерии, представляющие собой линейную комбинацию критериев (2.11)-(2.13), например, Иногда применяют другой вариант построения составного критерия :

При реализации градиентного метода с дроблением шага в качестве выбирают единичную матрицу, то есть

а длину шага определяют путем проверки некоторого неравенства. При этом основное рекуррентное соотношение (2.7) приобретает вид :

Ясно, то если, выбирать достаточно малым, то это обеспечит убывание, но потребуется весьма большое число шагов. Если же неосторожно выбрать большим, то можно проскочить минимум, а это опасно в связи с возможным осциллированием. Для выбора шага используется правило Голдстейна-Армийо :

а) (2.14)

б) (2.15)

Выполнение условия а) обеспечивает выбор не слишком большим. Выполнение условия б) не дает возможность выбрать слишком малым.

Практическая процедура строится следующим образом. Выбирается начальная точка и некоторое начальное значение, проверяется (2.14) и, если оно выполняется, то делается шаг в направлении В новой точке вычисляется градиент и вновь проверяется условие (2.14). В случае его удовлетворения продвижение к минимуму продолжается с тем же шагом. Если же оно не удовлетворяется, то параметр, определяющий длину шага, делят пополам до тех пор, пока это неравенство не будет выполнено. Затем выполняется очередной шаг. Процедура продолжается до выполнения критерия останова.

3. РЕШЕНИЕ ЗАДАЧИ МИНИМИЗАЦИИ ДЛЯ КАЖДОГО ИЗ МЕТОДОВ

3.1 Метод Нелдера-Мида

Построим симплекс состоящий из 3-х вершин. Длину ребра t возьмем равной 1 .

Начальные координаты симплекса :

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

Для осуществления оптимизации вычислим новую точку как отражение самой «плохой» вершины относительно центра тяжести симплекса. Формула для вычисления новой точки:

Затем, после сравнения значения функции в новой точке со значениями функции в остальных трех, а также после осуществления одного из четырех действий (замены, сжатия, растяжения и редукции), строится новый симплекс.

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

Замена происходит в случае, если новая точка лучше чем лучшая.

Если выполняется условие, то при этом реализуется отражение. Точка заменяет .

При выполнении условия осуществляется сжатие и отыскивается точка :

Параметр принимается равным 0,5. Точка заменяет. Таким образом полученная точка заменяет самую «плохую»

Если новая точка окажется самой «плохой», необходимо осуществить редукцию (уменьшение размера симплекса путем приближения всех его вершин к лучшей вершине) После выполнения указанных действий проверяется параметр останова. В случае, если он признан большим, чем выбранное значение точности, действия повторяются снова. Параметр останова рассчитывается по формуле :

Результат работы метода представлен в таблице 3.1

Таблица 3.1 — Решение задачи минимизации при помощи метода Нелдера-Мида


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,4 066 667	0,4 066 667	45,631 123 492 267	14,5 885 289
	0,4 433 333	0,2 683 333	29,870 063 661 634	2,8 471 538
	0,3 141 667	0,2 704 167	16,456 883 364 840	0,8 308 005
	0,2 495 833	0,2 714 583	13,667 862 520 021	0,3 301 516
	0,2 194 792	0,2 030 729	12,662 220 410 942	0,1 540 974
	0,1 796 615	0,1 864 974	12,281 326 901 893	0,870 517
	0,1 546 549	0,1 481 608	12,136 891 733 007	0,558 708
	0,1 284 945	0,1 302 889	12,72 845 463 097	0,394 655
	0,1 094 511	0,1 066 526	12,44 325 208 099	0,355 389
	0,380 868	0,472 725	12,32 057 545 239	0,204 381
	0,107 240	0,206 094	12,21 017 539 213	0,124 410
	0,217 244	0,287 886	12,11 093 940 034	0,130 068
	— 0,220 008	— 0,163 585	12,8 732 867 306	0,89 109
	— 0,274 319	— 0,235 556	12,5 248 404 276	0,53 110
	— 0,178 584	— 0,140 681	12,3 293 104 515	0,42 019
	— 0,191 470	— 0,189 750	12,2 069 416 305	0,30 794
	— 0,146 824	— 0,154 579	12,1 121 615 618	0,25 320
	— 0,132 441	— 0,133 520	12,655 246 493	0,26 725
	— 0,28 766	— 0,42 119	12,504 634 754	0,15 212
	0,4 344	— 0,8 739	12,339 347 268	0,9 248
	— 0,13 297	— 0,23 245	12,183 034 613	0,9 948
	0,35 282	0,29 010	12,137 117 579	0,7 582
	0,38 607	0,34 821	12,78 476 732	0,4 900
	0,27 293	0,23 210	12,50 320 679	0,4 156
	0,22 628	0,23 222	12,31 684 386	0,2 830
	0,15 804	0,17 419	12,17 894 979	0,2 411
	0,15 265	0,15 966	12,9 969 113	0,2 705
	0,1 079	0,2 907	12,8 036 464	0,1 594
	— 0,2 737	— 0,1 084	12,5 403 290	0,921

В результате решения задачи минимизации с помощью метода Нелдера-Мида получено следующее значение функции:. Данный оптимум достигается в точке. Этот метод позволяет найти минимум (при начальной точке Х (1; 1)) за 29 итераций при точности решения. При этом параметр останова равен 0,921.

3.2 Градиентный метод с дроблением шага

Для реализации процедуры необходимо вычислить градиент:

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

где E — заданная точность решения (в данной задаче E=).

Результат работы метода представлен в таблице 3.2

Вследствие того, что таблица содержит 1263 итерации, целесообразно предоставить первые и последние 25 итераций.

Таблица 3.2 — Решение задачи минимизации при помощи градиентного метода


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,992 187 500	0,976 562 500	14,872 248 322 711 100	5,725 771 436
	0,972 112 596	0,966 700 991	14,755 778 561 425 900	5,391 343 315
	0,960 252 606	0,949 298 075	14,647 453 457 158 200	5,170 831 157
	0,944 120 479	0,937 143 394	14,545 808 827 169 400	4,999 364 954
	0,931 250 704	0,922 455 245	14,450 015 755 630 300	4,851 038 521
	0,917 052 669	0,909 905 567	14,359 522 419 103 900	4,715 343 849
	0,904 265 341	0,896 648 294	14,273 894 939 963 900	4,588 117 156
	0,891 210 499	0,884 368 998	14,192 768 112 137 200	4,467 486 611
	0,878 869 537	0,872 030 350	14,115 817 843 495 700	4,352 565 782
	0,866 628 626	0,860 230 552	14,42 753 034 754 000	4,242 801 681
	0,854 831 609	0,848 589 700	13,973 308 662 686 200	4,137 814 211
	0,843 250 897	0,837 314 037	13,907 242 987 828 300	4,37 283 606
	0,832 001 542	0,826 261 206	13,844 334 505 896 600	3,940 936 337
	0,820 995 553	0,815 497 743	13,784 380 045 189 000	3,848 521 743
	0,810 266 979	0,804 966 957	13,727 192 808 899 800	3,759 812 059
	0,799 778 396	0,794 686 358	13,672 600 853 099 300	3,674 595 835
	0,789 535 800	0,784 630 345	13,620 445 636 362 400	3,592 677 880
	0,779 520 366	0,774 799 711	13,570 580 790 710 000	3,513 876 598
	0,769 728 817	0,765 180 416	13,522 870 992 857 600	3,438 023 378
	0,760 149 472	0,755 767 918	13,477 190 974 079 800	3,364 961 115
	0,750 776 352	0,746 552 749	13,433 424 623 226 000	3,294 543 452
	0,741 600 798	0,737 528 983	13,391 464 187 766 000	3,226 633 778
	0,732 616 368	0,728 689 198	13,351 209 552 529 500	3,161 104 506
	0,723 815 911	0,720 027 406	13,312 567 592 195 300	3,97 836 320
	0,715 193 248	0,711 537 292	13,275 451 586 431 100	3,36 717 546
	0,42 461	0,42 461	12,3 605 800	0,120 097
	0,42 129	0,42 129	12,3 549 700	0,119 159
	0,41 800	0,41 800	12,3 494 500	0,118 228
	0,41 473	0,41 473	12,3 440 100	0,117 304
	0,41 149	0,41 149	12,3 386 500	0,116 388
	0,40 828	0,40 828	12,3 333 800	0,115 479
	0,40 509	0,40 509	12,3 281 900	0,114 576
	0,40 192	0,40 192	12,3 230 900	0,113 681
	0,39 878	0,39 878	12,3 180 600	0,112 793
	0,39 567	0,39 567	12,3 131 100	0,111 912
	0,39 258	0,39 258	12,3 082 300	0,111 038
	0,38 951	0,38 951	12,3 034 400	0,110 170
	0,38 647	0,38 647	12,2 987 100	0,109 309
	0,38 345	0,38 345	12,2 940 600	0,108 455
	0,38 045	0,38 045	12,2 894 900	0,107 608
	0,37 748	0,37 748	12,2 849 800	0,106 767
	0,37 453	0,37 453	12,2 805 500	0,105 933
	0,37 161	0,37 161	12,2 761 800	0,105 106
	0,36 870	0,36 870	12,2 718 800	0,104 285
	0,36 582	0,36 582	12,2 676 500	0,103 470
	0,36 296	0,36 296	12,2 634 800	0,102 662
	0,36 013	0,36 013	12,2 593 800	0,101 860
	0,35 731	0,35 731	12,2 553 500	0,101 064
	0,35 452	0,35 452	12,2 513 700	0,100 274
	0,35 175	0,35 175	12,2 474 600	0,99 491

В результате реализации градиентного метода минимальное значение функции составляет. Данный оптимум достигнут в точке. Этот метод позволяет найти минимум (при начальной точке Х (1;1) за 1263 итерации при точности решения. При этом параметр останова равен 0,99 491.

4. ГРАФИЧЕСКАЯ ИНТЕРПРИТАЦИЯ РЕШЕНИЯ ЗАДАЧИ

График исследуемой функции имеет вид :

Рисунок 4.1 — График исследуемой функции Изобразим на рисунке (4.2) линии уровня функции Рисунок 4.2 — Линии уровня исследуемой функции Отобразим на графиках линий уровня для каждого из заданных методов траекторию спуска Рисунок 4.3 — траектория спуска (метод Нелдера-Мида) Рисунок 4.4 — траектория спуска (градиентный метод)

5. АНАЛИТИЧЕСКОЕ ИССЛЕДОВАНИЕ МЕТОДОВ

Для выявления зависимости числа итераций от заданной точности методы реализованы для каждого значения точности. Результаты представлены в таблицах (5.1−5.6, 5.8−5.13)

Реализация метода Нелдера-Мида :

Таблица 5.1 — Реализация метода Нелдера-Мида при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,4 066 667	0,4 066 667	45,631 123 492 267	14,5 885 289
	0,4 433 333	0,2 683 333	29,870 063 661 634	2,8 471 538
	0,3 141 667	0,2 704 167	16,456 883 364 840	0,8 308 005
	0,2 495 833	0,2 714 583	13,667 862 520 021	0,3 301 516
	0,2 194 792	0,2 030 729	12,662 220 410 942	0,1 540 974
	0,1 796 615	0,1 864 974	12,281 326 901 893	0,870 517

Таблица 5.2 — Реализация метода Нелдера-Мида при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,4 066 667	0,4 066 667	45,631 123 492 267	14,5 885 289
	0,4 433 333	0,2 683 333	29,870 063 661 634	2,8 471 538
	0,3 141 667	0,2 704 167	16,456 883 364 840	0,8 308 005
	0,2 495 833	0,2 714 583	13,667 862 520 021	0,3 301 516
	0,2 194 792	0,2 030 729	12,662 220 410 942	0,1 540 974
	0,1 796 615	0,1 864 974	12,281 326 901 893	0,870 517
	0,1 546 549	0,1 481 608	12,136 891 733 007	0,558 708
	0,1 284 945	0,1 302 889	12,72 845 463 097	0,394 655
	0,1 094 511	0,1 066 526	12,44 325 208 099	0,355 389
	0,380 868	0,472 725	12,32 057 545 239	0,204 381
	0,107 240	0,206 094	12,21 017 539 213	0,124 410
	0,217 244	0,287 886	12,11 093 940 034	0,130 068
	— 0,220 008	— 0,163 585	12,8 732 867 306	0,89 109

Таблица 5.3 — Реализация метода Нелдера-Мида при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,4 066 667	0,4 066 667	45,631 123 492 267	14,5 885 289
	0,4 433 333	0,2 683 333	29,870 063 661 634	2,8 471 538
	0,3 141 667	0,2 704 167	16,456 883 364 840	0,8 308 005
	0,2 495 833	0,2 714 583	13,667 862 520 021	0,3 301 516
	0,2 194 792	0,2 030 729	12,662 220 410 942	0,1 540 974
	0,1 796 615	0,1 864 974	12,281 326 901 893	0,870 517
	0,1 546 549	0,1 481 608	12,136 891 733 007	0,558 708
	0,1 284 945	0,1 302 889	12,72 845 463 097	0,394 655
	0,1 094 511	0,1 066 526	12,44 325 208 099	0,355 389
	0,380 868	0,472 725	12,32 057 545 239	0,204 381
	0,107 240	0,206 094	12,21 017 539 213	0,124 410
	0,217 244	0,287 886	12,11 093 940 034	0,130 068
	— 0,220 008	— 0,163 585	12,8 732 867 306	0,89 109
	— 0,274 319	— 0,235 556	12,5 248 404 276	0,53 110
	— 0,178 584	— 0,140 681	12,3 293 104 515	0,42 019
	— 0,191 470	— 0,189 750	12,2 069 416 305	0,30 794
	— 0,146 824	— 0,154 579	12,1 121 615 618	0,25 320
	— 0,132 441	— 0,133 520	12,655 246 493	0,26 725
	— 0,28 766	— 0,42 119	12,504 634 754	0,15 212
	0,4 344	— 0,8 739	12,339 347 268	0,9 248

Таблица 5.4 — Реализация метода Нелдера-Мида при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,4 066 667	0,4 066 667	45,631 123 492 267	14,5 885 289
	0,4 433 333	0,2 683 333	29,870 063 661 634	2,8 471 538
	0,3 141 667	0,2 704 167	16,456 883 364 840	0,8 308 005
	0,2 495 833	0,2 714 583	13,667 862 520 021	0,3 301 516
	0,2 194 792	0,2 030 729	12,662 220 410 942	0,1 540 974
	0,1 796 615	0,1 864 974	12,281 326 901 893	0,870 517
	0,1 546 549	0,1 481 608	12,136 891 733 007	0,558 708
	0,1 284 945	0,1 302 889	12,72 845 463 097	0,394 655
	0,1 094 511	0,1 066 526	12,44 325 208 099	0,355 389
	0,380 868	0,472 725	12,32 057 545 239	0,204 381
	0,107 240	0,206 094	12,21 017 539 213	0,124 410
	0,217 244	0,287 886	12,11 093 940 034	0,130 068
	— 0,220 008	— 0,163 585	12,8 732 867 306	0,89 109
	— 0,274 319	— 0,235 556	12,5 248 404 276	0,53 110
	— 0,178 584	— 0,140 681	12,3 293 104 515	0,42 019
	— 0,191 470	— 0,189 750	12,2 069 416 305	0,30 794
	— 0,146 824	— 0,154 579	12,1 121 615 618	0,25 320
	— 0,132 441	— 0,133 520	12,655 246 493	0,26 725
	— 0,28 766	— 0,42 119	12,504 634 754	0,15 212
	0,4 344	— 0,8 739	12,339 347 268	0,9 248
	— 0,13 297	— 0,23 245	12,183 034 613	0,9 948
	0,35 282	0,29 010	12,137 117 579	0,7 582
	0,38 607	0,34 821	12,78 476 732	0,4 900
	0,27 293	0,23 210	12,50 320 679	0,4 156
	0,22 628	0,23 222	12,31 684 386	0,2 830
	0,15 804	0,17 419	12,17 894 979	0,2 411
	0,15 265	0,15 966	12,9 969 113	0,2 705
	0,1 079	0,2 907	12,8 036 464	0,1 594
	— 0,2 737	— 0,1 084	12,5 403 290	0,921

Таблица 5.5 — Реализация метода Нелдера-Мида при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,4 066 667	0,4 066 667	45,631 123 492 267	14,5 885 289
	0,4 433 333	0,2 683 333	29,870 063 661 634	2,8 471 538
	0,3 141 667	0,2 704 167	16,456 883 364 840	0,8 308 005
	0,2 495 833	0,2 714 583	13,667 862 520 021	0,3 301 516
	0,2 194 792	0,2 030 729	12,662 220 410 942	0,1 540 974
	0,1 796 615	0,1 864 974	12,281 326 901 893	0,870 517
	0,1 546 549	0,1 481 608	12,136 891 733 007	0,558 708
	0,1 284 945	0,1 302 889	12,72 845 463 097	0,394 655
	0,1 094 511	0,1 066 526	12,44 325 208 099	0,355 389
	0,380 868	0,472 725	12,32 057 545 239	0,204 381
	0,107 240	0,206 094	12,21 017 539 213	0,124 410
	0,217 244	0,287 886	12,11 093 940 034	0,130 068
	— 0,220 008	— 0,163 585	12,8 732 867 306	0,89 109
	— 0,274 319	— 0,235 556	12,5 248 404 276	0,53 110
	— 0,178 584	— 0,140 681	12,3 293 104 515	0,42 019
	— 0,191 470	— 0,189 750	12,2 069 416 305	0,30 794
	— 0,146 824	— 0,154 579	12,1 121 615 618	0,25 320
	— 0,132 441	— 0,133 520	12,655 246 493	0,26 725
	— 0,28 766	— 0,42 119	12,504 634 754	0,15 212
	0,4 344	— 0,8 739	12,339 347 268	0,9 248
	— 0,13 297	— 0,23 245	12,183 034 613	0,9 948
	0,35 282	0,29 010	12,137 117 579	0,7 582
	0,38 607	0,34 821	12,78 476 732	0,4 900
	0,27 293	0,23 210	12,50 320 679	0,4 156
	0,22 628	0,23 222	12,31 684 386	0,2 830
	0,15 804	0,17 419	12,17 894 979	0,2 411
	0,15 265	0,15 966	12,9 969 113	0,2 705
	0,1 079	0,2 907	12,8 036 464	0,1 594
	— 0,2 737	— 0,1 084	12,5 403 290	0,921
	— 0,145	0,1 182	12,3 012 890	0,930
	— 0,5 185	— 0,4 534	12,2 135 678	0,765
	— 0,5 149	— 0,4 829	12,1 171 711	0,537
	— 0,3 880	— 0,3 474	12,755 753	0,486
	— 0,2 538	— 0,2 710	12,487 650	0,301
	— 0,1 568	— 0,1 842	12,290 103	0,249
	— 0,1 661	— 0,1 816	12,155 619	0,289
	0,186	— 0,52	12,128 281	0,180
	0,601	0,402	12,84 592	0,102
	0,243	0,74	12,49 029	0,94

Таблица 5.6 — Реализация метода Нелдера-Мида при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,4 066 667	0,4 066 667	45,631 123 492 267	14,5 885 289
	0,4 433 333	0,2 683 333	29,870 063 661 634	2,8 471 538
	0,3 141 667	0,2 704 167	16,456 883 364 840	0,8 308 005
	0,2 495 833	0,2 714 583	13,667 862 520 021	0,3 301 516
	0,2 194 792	0,2 030 729	12,662 220 410 942	0,1 540 974
	0,1 796 615	0,1 864 974	12,281 326 901 893	0,870 517
	0,1 546 549	0,1 481 608	12,136 891 733 007	0,558 708
	0,1 284 945	0,1 302 889	12,72 845 463 097	0,394 655
	0,1 094 511	0,1 066 526	12,44 325 208 099	0,355 389
	0,380 868	0,472 725	12,32 057 545 239	0,204 381
	0,107 240	0,206 094	12,21 017 539 213	0,124 410
	0,217 244	0,287 886	12,11 093 940 034	0,130 068
	— 0,220 008	— 0,163 585	12,8 732 867 306	0,89 109
	— 0,274 319	— 0,235 556	12,5 248 404 276	0,53 110
	— 0,178 584	— 0,140 681	12,3 293 104 515	0,42 019
	— 0,191 470	— 0,189 750	12,2 069 416 305	0,30 794
	— 0,146 824	— 0,154 579	12,1 121 615 618	0,25 320
	— 0,132 441	— 0,133 520	12,655 246 493	0,26 725
	— 0,28 766	— 0,42 119	12,504 634 754	0,15 212
	0,4 344	— 0,8 739	12,339 347 268	0,9 248
	— 0,13 297	— 0,23 245	12,183 034 613	0,9 948
	0,35 282	0,29 010	12,137 117 579	0,7 582
	0,38 607	0,34 821	12,78 476 732	0,4 900
	0,27 293	0,23 210	12,50 320 679	0,4 156
	0,22 628	0,23 222	12,31 684 386	0,2 830
	0,15 804	0,17 419	12,17 894 979	0,2 411
	0,15 265	0,15 966	12,9 969 113	0,2 705
	0,1 079	0,2 907	12,8 036 464	0,1 594
	— 0,2 737	— 0,1 084	12,5 403 290	0,921
	— 0,145	0,1 182	12,3 012 890	0,930
	— 0,5 185	— 0,4 534	12,2 135 678	0,765
	— 0,5 149	— 0,4 829	12,1 171 711	0,537
	— 0,3 880	— 0,3 474	12,755 753	0,486
	— 0,2 538	— 0,2 710	12,487 650	0,301
	— 0,1 568	— 0,1 842	12,290 103	0,249
	— 0,1 661	— 0,1 816	12,155 619	0,289
	0,186	— 0,52	12,128 281	0,180
	0,601	0,402	12,84 592	0,102
	0,243	0,74	12,49 029	0,94
	0,716	0,655	12,32 997	0,81
	0,655	0,636	12,17 601	0,61
	0,522	0,486	12,11 215	0,59
	0,267	0,299	12,7 565	0,34
	0,136	0,178	12,4 741	0,26
	0,167	0,194	12,2 493	0,31
	— 0,62	— 0,33	12,2 045	0,21
	— 0,104	— 0,81	12,1 302	0,12
	— 0,57	— 0,37	12,784	0,10
	— 0,94	— 0,89	12,507	0,9

Данные по количеству итераций и заданным точностям для метода Нелдера-Мида сведены в таблицу 5.7

Таблица 5.7 — Зависимость числа итераций от точности


Точность	Количество итераций
0,1
0,01
0,001
0,0001
0,1
0,1

Рисунок 5.1 — Графическое представление зависимости количества итераций N от точности E для метода Нелдера-Мида.

Для градиентного метода, принимая во внимание большое количество итераций, целесообразно приводить для каждой реализации первые и последние 25 итераций.

Реализация градиентного метода:

Таблица 5.8 — Реализация градиентного метода при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,992 187 500	0,976 562 500	14,872 248 322 711 100	5,725 771 436
	0,972 112 596	0,966 700 991	14,755 778 561 425 900	5,391 343 315
	0,960 252 606	0,949 298 075	14,647 453 457 158 200	5,170 831 157
	0,944 120 479	0,937 143 394	14,545 808 827 169 400	4,999 364 954
	0,931 250 704	0,922 455 245	14,450 015 755 630 300	4,851 038 521
	0,917 052 669	0,909 905 567	14,359 522 419 103 900	4,715 343 849
	0,904 265 341	0,896 648 294	14,273 894 939 963 900	4,588 117 156
	0,891 210 499	0,884 368 998	14,192 768 112 137 200	4,467 486 611
	0,878 869 537	0,872 030 350	14,115 817 843 495 700	4,352 565 782
	0,866 628 626	0,860 230 552	14,42 753 034 754 000	4,242 801 681
	0,854 831 609	0,848 589 700	13,973 308 662 686 200	4,137 814 211
	0,843 250 897	0,837 314 037	13,907 242 987 828 300	4,37 283 606
	0,832 001 542	0,826 261 206	13,844 334 505 896 600	3,940 936 337
	0,820 995 553	0,815 497 743	13,784 380 045 189 000	3,848 521 743
	0,810 266 979	0,804 966 957	13,727 192 808 899 800	3,759 812 059
	0,799 778 396	0,794 686 358	13,672 600 853 099 300	3,674 595 835
	0,789 535 800	0,784 630 345	13,620 445 636 362 400	3,592 677 880
	0,779 520 366	0,774 799 711	13,570 580 790 710 000	3,513 876 598
	0,769 728 817	0,765 180 416	13,522 870 992 857 600	3,438 023 378
	0,760 149 472	0,755 767 918	13,477 190 974 079 800	3,364 961 115
	0,750 776 352	0,746 552 749	13,433 424 623 226 000	3,294 543 452
	0,741 600 798	0,737 528 983	13,391 464 187 766 000	3,226 633 778
	0,732 616 368	0,728 689 198	13,351 209 552 529 500	3,161 104 506
	0,723 815 911	0,720 027 406	13,312 567 592 195 300	3,97 836 320
	0,715 193 248	0,711 537 292	13,275 451 586 431 100	3,36 717 546
	0,42 588 763	0,42 587 983	12,3 630 828 695 700	0,120 676 586
	0,42 255 429	0,42 254 667	12,3 574 166 022 100	0,119 728 711
	0,41 924 713	0,41 923 969	12,3 518 389 968 100	0,118 788 359
	0,41 596 595	0,41 595 868	12,3 463 486 588 100	0,117 855 470
	0,41 271 053	0,41 270 343	12,3 409 442 157 800	0,116 929 982
	0,40 948 069	0,40 947 375	12,3 356 243 171 100	0,116 011 835
	0,40 627 620	0,40 626 943	12,3 303 876 336 500	0,115 100 970
	0,40 309 688	0,40 309 026	12,3 252 328 573 200	0,114 197 326
	0,39 994 251	0,39 993 605	12,3 201 587 008 200	0,113 300 844
	0,39 681 292	0,39 680 660	12,3 151 638 972 600	0,112 411 467
	0,39 370 788	0,39 370 172	12,3 102 471 998 700	0,111 529 137
	0,39 062 723	0,39 062 121	12,3 054 073 816 300	0,110 653 795
	0,38 757 075	0,38 756 487	12,3 006 432 349 600	0,109 785 386
	0,38 453 826	0,38 453 252	12,2 959 535 714 300	0,108 923 853
	0,38 152 957	0,38 152 396	12,2 913 372 214 400	0,108 069 140
	0,37 854 448	0,37 853 901	12,2 867 930 339 100	0,107 221 192
	0,37 558 283	0,37 557 747	12,2 823 198 760 000	0,106 379 954
	0,37 264 440	0,37 263 918	12,2 779 166 327 700	0,105 545 371
	0,36 972 904	0,36 972 393	12,2 735 822 069 600	0,104 717 390
	0,36 683 654	0,36 683 156	12,2 693 155 186 500	0,103 895 956
	0,36 396 674	0,36 396 187	12,2 651 155 050 100	0,103 081 018
	0,36 111 944	0,36 111 468	12,2 609 811 200 200	0,102 272 522
	0,35 829 448	0,35 828 983	12,2 569 113 341 800	0,101 470 417
	0,35 549 167	0,35 548 714	12,2 529 051 343 000	0,100 674 650
	0,35 271 085	0,35 270 642	12,2 489 615 231 500	0,99 885 171

Таблица 5.9 — Реализация градиентного метода при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,992 187 500	0,976 562 500	14,872 248 322 711 100	5,725 771 436
	0,972 112 596	0,966 700 991	14,755 778 561 425 900	5,391 343 315
	0,960 252 606	0,949 298 075	14,647 453 457 158 200	5,170 831 157
	0,944 120 479	0,937 143 394	14,545 808 827 169 400	4,999 364 954
	0,931 250 704	0,922 455 245	14,450 015 755 630 300	4,851 038 521
	0,917 052 669	0,909 905 567	14,359 522 419 103 900	4,715 343 849
	0,904 265 341	0,896 648 294	14,273 894 939 963 900	4,588 117 156
	0,891 210 499	0,884 368 998	14,192 768 112 137 200	4,467 486 611
	0,878 869 537	0,872 030 350	14,115 817 843 495 700	4,352 565 782
	0,866 628 626	0,860 230 552	14,42 753 034 754 000	4,242 801 681
	0,854 831 609	0,848 589 700	13,973 308 662 686 200	4,137 814 211
	0,843 250 897	0,837 314 037	13,907 242 987 828 300	4,37 283 606
	0,832 001 542	0,826 261 206	13,844 334 505 896 600	3,940 936 337
	0,820 995 553	0,815 497 743	13,784 380 045 189 000	3,848 521 743
	0,810 266 979	0,804 966 957	13,727 192 808 899 800	3,759 812 059
	0,799 778 396	0,794 686 358	13,672 600 853 099 300	3,674 595 835
	0,789 535 800	0,784 630 345	13,620 445 636 362 400	3,592 677 880
	0,779 520 366	0,774 799 711	13,570 580 790 710 000	3,513 876 598
	0,769 728 817	0,765 180 416	13,522 870 992 857 600	3,438 023 378
	0,760 149 472	0,755 767 918	13,477 190 974 079 800	3,364 961 115
	0,750 776 352	0,746 552 749	13,433 424 623 226 000	3,294 543 452
	0,741 600 798	0,737 528 983	13,391 464 187 766 000	3,226 633 778
	0,732 616 368	0,728 689 198	13,351 209 552 529 500	3,161 104 506
	0,723 815 911	0,720 027 406	13,312 567 592 195 300	3,97 836 320
	0,715 193 248	0,711 537 292	13,275 451 586 431 100	3,36 717 546
	0,4 240 917	0,4 240 916	12,35 971 071 500	0,11 995 339
	0,4 207 784	0,4 207 784	12,35 411 204 000	0,11 901 621
	0,4 174 910	0,4 174 910	12,34 860 050 800	0,11 808 634
	0,4 142 293	0,4 142 293	12,34 317 476 100	0,11 716 375
	0,4 109 931	0,4 109 930	12,33 783 346 400	0,11 624 836
	0,4 077 822	0,4 077 821	12,33 257 530 400	0,11 534 012
	0,4 045 963	0,4 045 963	12,32 739 898 600	0,11 443 898
	0,4 014 354	0,4 014 353	12,32 230 323 500	0,11 354 489
	0,3 982 991	0,3 982 990	12,31 728 679 900	0,11 265 777
	0,3 951 873	0,3 951 873	12,31 234 844 100	0,11 177 759
	0,3 920 999	0,3 920 998	12,30 748 694 800	0,11 090 429
	0,3 890 366	0,3 890 365	12,30 270 112 300	0,11 003 781
	0,3 859 972	0,3 859 971	12,29 798 978 700	0,10 917 810
	0,3 829 815	0,3 829 815	12,29 335 178 200	0,10 832 511
	0,3 799 894	0,3 799 894	12,28 878 596 500	0,10 747 878
	0,3 770 207	0,3 770 207	12,28 429 121 400	0,10 663 907
	0,3 740 752	0,3 740 751	12,27 986 642 200	0,10 580 592
	0,3 711 527	0,3 711 526	12,27 551 050 000	0,10 497 927
	0,3 682 530	0,3 682 530	12,27 122 237 600	0,10 415 909
	0,3 653 760	0,3 653 760	12,26 700 099 600	0,10 334 531
	0,3 625 215	0,3 625 214	12,26 284 531 900	0,10 253 790
	0,3 596 892	0,3 596 892	12,25 875 432 400	0,10 173 679
	0,3 568 791	0,3 568 791	12,25 472 700 300	0,10 094 194
	0,3 540 910	0,3 540 909	12,25 076 236 600	0,10 015 330
	0,3 513 246	0,3 513 246	12,24 685 943 600	0,9 937 082

Таблица 5.10 — Реализация градиентного метода при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,992 187 500	0,976 562 500	14,872 248 322 711 100	5,725 771 436
	0,972 112 596	0,966 700 991	14,755 778 561 425 900	5,391 343 315
	0,960 252 606	0,949 298 075	14,647 453 457 158 200	5,170 831 157
	0,944 120 479	0,937 143 394	14,545 808 827 169 400	4,999 364 954
	0,931 250 704	0,922 455 245	14,450 015 755 630 300	4,851 038 521
	0,917 052 669	0,909 905 567	14,359 522 419 103 900	4,715 343 849
	0,904 265 341	0,896 648 294	14,273 894 939 963 900	4,588 117 156
	0,891 210 499	0,884 368 998	14,192 768 112 137 200	4,467 486 611
	0,878 869 537	0,872 030 350	14,115 817 843 495 700	4,352 565 782
	0,866 628 626	0,860 230 552	14,42 753 034 754 000	4,242 801 681
	0,854 831 609	0,848 589 700	13,973 308 662 686 200	4,137 814 211
	0,843 250 897	0,837 314 037	13,907 242 987 828 300	4,37 283 606
	0,832 001 542	0,826 261 206	13,844 334 505 896 600	3,940 936 337
	0,820 995 553	0,815 497 743	13,784 380 045 189 000	3,848 521 743
	0,810 266 979	0,804 966 957	13,727 192 808 899 800	3,759 812 059
	0,799 778 396	0,794 686 358	13,672 600 853 099 300	3,674 595 835
	0,789 535 800	0,784 630 345	13,620 445 636 362 400	3,592 677 880
	0,779 520 366	0,774 799 711	13,570 580 790 710 000	3,513 876 598
	0,769 728 817	0,765 180 416	13,522 870 992 857 600	3,438 023 378
	0,760 149 472	0,755 767 918	13,477 190 974 079 800	3,364 961 115
	0,750 776 352	0,746 552 749	13,433 424 623 226 000	3,294 543 452
	0,741 600 798	0,737 528 983	13,391 464 187 766 000	3,226 633 778
	0,732 616 368	0,728 689 198	13,351 209 552 529 500	3,161 104 506
	0,723 815 911	0,720 027 406	13,312 567 592 195 300	3,97 836 320
	0,715 193 248	0,711 537 292	13,275 451 586 431 100	3,36 717 546
	0,426 015	0,426 015	12,362 977 700	0,1 204 953
	0,422 687	0,422 687	12,357 328 300	0,1 195 539
	0,419 385	0,419 385	12,351 766 900	0,1 186 199
	0,416 108	0,416 108	12,346 292 000	0,1 176 932
	0,412 857	0,412 857	12,340 902 300	0,1 167 737
	0,409 632	0,409 632	12,335 596 500	0,1 158 614
	0,406 432	0,406 432	12,330 373 300	0,1 149 562
	0,403 256	0,403 256	12,325 231 400	0,1 140 581
	0,400 106	0,400 106	12,320 169 500	0,1 131 671
	0,396 980	0,396 980	12,315 186 400	0,1 122 829
	0,393 879	0,393 879	12,310 280 800	0,1 114 057
	0,390 801	0,390 801	12,305 451 600	0,1 105 354
	0,387 748	0,387 748	12,300 697 600	0,1 096 718
	0,384 719	0,384 719	12,296 017 600	0,1 088 150
	0,381 713	0,381 713	12,291 410 300	0,1 079 649
	0,378 731	0,378 731	12,286 874 800	0,1 071 214
	0,375 772	0,375 772	12,282 409 900	0,1 062 845
	0,372 837	0,372 837	12,278 014 500	0,1 054 542
	0,369 924	0,369 924	12,273 687 500	0,1 046 303
	0,367 034	0,367 034	12,269 427 800	0,1 038 129
	0,364 166	0,364 166	12,265 234 500	0,1 030 018
	0,361 321	0,361 321	12,261 106 400	0,1 021 971
	0,358 499	0,358 499	12,257 042 500	0,1 013 987
	0,355 698	0,355 698	12,253 041 900	0,1 006 066
	0,352 919	0,352 919	12,249 103 600	0,998 206

Таблица 5.11 — Реализация градиентного метода при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,992 187 500	0,976 562 500	14,872 248 322 711 100	5,725 771 436
	0,972 112 596	0,966 700 991	14,755 778 561 425 900	5,391 343 315
	0,960 252 606	0,949 298 075	14,647 453 457 158 200	5,170 831 157
	0,944 120 479	0,937 143 394	14,545 808 827 169 400	4,999 364 954
	0,931 250 704	0,922 455 245	14,450 015 755 630 300	4,851 038 521
	0,917 052 669	0,909 905 567	14,359 522 419 103 900	4,715 343 849
	0,904 265 341	0,896 648 294	14,273 894 939 963 900	4,588 117 156
	0,891 210 499	0,884 368 998	14,192 768 112 137 200	4,467 486 611
	0,878 869 537	0,872 030 350	14,115 817 843 495 700	4,352 565 782
	0,866 628 626	0,860 230 552	14,42 753 034 754 000	4,242 801 681
	0,854 831 609	0,848 589 700	13,973 308 662 686 200	4,137 814 211
	0,843 250 897	0,837 314 037	13,907 242 987 828 300	4,37 283 606
	0,832 001 542	0,826 261 206	13,844 334 505 896 600	3,940 936 337
	0,820 995 553	0,815 497 743	13,784 380 045 189 000	3,848 521 743
	0,810 266 979	0,804 966 957	13,727 192 808 899 800	3,759 812 059
	0,799 778 396	0,794 686 358	13,672 600 853 099 300	3,674 595 835
	0,789 535 800	0,784 630 345	13,620 445 636 362 400	3,592 677 880
	0,779 520 366	0,774 799 711	13,570 580 790 710 000	3,513 876 598
	0,769 728 817	0,765 180 416	13,522 870 992 857 600	3,438 023 378
	0,760 149 472	0,755 767 918	13,477 190 974 079 800	3,364 961 115
	0,750 776 352	0,746 552 749	13,433 424 623 226 000	3,294 543 452
	0,741 600 798	0,737 528 983	13,391 464 187 766 000	3,226 633 778
	0,732 616 368	0,728 689 198	13,351 209 552 529 500	3,161 104 506
	0,723 815 911	0,720 027 406	13,312 567 592 195 300	3,97 836 320
	0,715 193 248	0,711 537 292	13,275 451 586 431 100	3,36 717 546
	0,42 461	0,42 461	12,3 605 800	0,120 097
	0,42 129	0,42 129	12,3 549 700	0,119 159
	0,41 800	0,41 800	12,3 494 500	0,118 228
	0,41 473	0,41 473	12,3 440 100	0,117 304
	0,41 149	0,41 149	12,3 386 500	0,116 388
	0,40 828	0,40 828	12,3 333 800	0,115 479
	0,40 509	0,40 509	12,3 281 900	0,114 576
	0,40 192	0,40 192	12,3 230 900	0,113 681
	0,39 878	0,39 878	12,3 180 600	0,112 793
	0,39 567	0,39 567	12,3 131 100	0,111 912
	0,39 258	0,39 258	12,3 082 300	0,111 038
	0,38 951	0,38 951	12,3 034 400	0,110 170
	0,38 647	0,38 647	12,2 987 100	0,109 309
	0,38 345	0,38 345	12,2 940 600	0,108 455
	0,38 045	0,38 045	12,2 894 900	0,107 608
	0,37 748	0,37 748	12,2 849 800	0,106 767
	0,37 453	0,37 453	12,2 805 500	0,105 933
	0,37 161	0,37 161	12,2 761 800	0,105 106
	0,36 870	0,36 870	12,2 718 800	0,104 285
	0,36 582	0,36 582	12,2 676 500	0,103 470
	0,36 296	0,36 296	12,2 634 800	0,102 662
	0,36 013	0,36 013	12,2 593 800	0,101 860
	0,35 731	0,35 731	12,2 553 500	0,101 064
	0,35 452	0,35 452	12,2 513 700	0,100 274
	0,35 175	0,35 175	12,2 474 600	0,99 491

Таблица 5.12 — Реализация градиентного метода при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,992 187 500	0,976 562 500	14,872 248 322 711 100	5,725 771 436
	0,972 112 596	0,966 700 991	14,755 778 561 425 900	5,391 343 315
	0,960 252 606	0,949 298 075	14,647 453 457 158 200	5,170 831 157
	0,944 120 479	0,937 143 394	14,545 808 827 169 400	4,999 364 954
	0,931 250 704	0,922 455 245	14,450 015 755 630 300	4,851 038 521
	0,917 052 669	0,909 905 567	14,359 522 419 103 900	4,715 343 849
	0,904 265 341	0,896 648 294	14,273 894 939 963 900	4,588 117 156
	0,891 210 499	0,884 368 998	14,192 768 112 137 200	4,467 486 611
	0,878 869 537	0,872 030 350	14,115 817 843 495 700	4,352 565 782
	0,866 628 626	0,860 230 552	14,42 753 034 754 000	4,242 801 681
	0,854 831 609	0,848 589 700	13,973 308 662 686 200	4,137 814 211
	0,843 250 897	0,837 314 037	13,907 242 987 828 300	4,37 283 606
	0,832 001 542	0,826 261 206	13,844 334 505 896 600	3,940 936 337
	0,820 995 553	0,815 497 743	13,784 380 045 189 000	3,848 521 743
	0,810 266 979	0,804 966 957	13,727 192 808 899 800	3,759 812 059
	0,799 778 396	0,794 686 358	13,672 600 853 099 300	3,674 595 835
	0,789 535 800	0,784 630 345	13,620 445 636 362 400	3,592 677 880
	0,779 520 366	0,774 799 711	13,570 580 790 710 000	3,513 876 598
	0,769 728 817	0,765 180 416	13,522 870 992 857 600	3,438 023 378
	0,760 149 472	0,755 767 918	13,477 190 974 079 800	3,364 961 115
	0,750 776 352	0,746 552 749	13,433 424 623 226 000	3,294 543 452
	0,741 600 798	0,737 528 983	13,391 464 187 766 000	3,226 633 778
	0,732 616 368	0,728 689 198	13,351 209 552 529 500	3,161 104 506
	0,723 815 911	0,720 027 406	13,312 567 592 195 300	3,97 836 320
	0,715 193 248	0,711 537 292	13,275 451 586 431 100	3,36 717 546
	0,4 265	0,4 265	12,36 400	0,12 064
	0,4 232	0,4 232	12,35 800	0,11 970
	0,4 199	0,4 199	12,35 300	0,11 877
	0,4 166	0,4 166	12,34 700	0,11 784
	0,4 134	0,4 134	12,34 200	0,11 692
	0,4 101	0,4 101	12,33 600	0,11 600
	0,4 069	0,4 069	12,33 100	0,11 510
	0,4 038	0,4 038	12,32 600	0,11 420
	0,4 006	0,4 006	12,32 100	0,11 331
	0,3 975	0,3 975	12,31 600	0,11 242
	0,3 944	0,3 944	12,31 100	0,11 154
	0,3 913	0,3 913	12,30 600	0,11 067
	0,3 882	0,3 882	12,30 100	0,10 981
	0,3 852	0,3 852	12,29 700	0,10 895
	0,3 822	0,3 822	12,29 200	0,10 810
	0,3 792	0,3 792	12,28 800	0,10 725
	0,3 762	0,3 762	12,28 300	0,10 641
	0,3 733	0,3 733	12,27 900	0,10 558
	0,3 704	0,3 704	12,27 400	0,10 476
	0,3 675	0,3 675	12,27 000	0,10 394
	0,3 646	0,3 646	12,26 600	0,10 313
	0,3 618	0,3 618	12,26 200	0,10 232
	0,3 589	0,3 589	12,25 800	0,10 152
	0,3 561	0,3 561	12,25 400	0,10 073
	0,3 534	0,3 534	12,25 000	0,9 994

Таблица 5.13- Реализация градиентного метода при


Номер итерации	Х1	Х2	Функция	Параметр останова
	0,992 187 500	0,976 562 500	14,872 248 322 711 100	5,725 771 436
	0,972 112 596	0,966 700 991	14,755 778 561 425 900	5,391 343 315
	0,960 252 606	0,949 298 075	14,647 453 457 158 200	5,170 831 157
	0,944 120 479	0,937 143 394	14,545 808 827 169 400	4,999 364 954
	0,931 250 704	0,922 455 245	14,450 015 755 630 300	4,851 038 521
	0,917 052 669	0,909 905 567	14,359 522 419 103 900	4,715 343 849
	0,904 265 341	0,896 648 294	14,273 894 939 963 900	4,588 117 156
	0,891 210 499	0,884 368 998	14,192 768 112 137 200	4,467 486 611
	0,878 869 537	0,872 030 350	14,115 817 843 495 700	4,352 565 782
	0,866 628 626	0,860 230 552	14,42 753 034 754 000	4,242 801 681
	0,854 831 609	0,848 589 700	13,973 308 662 686 200	4,137 814 211
	0,843 250 897	0,837 314 037	13,907 242 987 828 300	4,37 283 606
	0,832 001 542	0,826 261 206	13,844 334 505 896 600	3,940 936 337
	0,820 995 553	0,815 497 743	13,784 380 045 189 000	3,848 521 743
	0,810 266 979	0,804 966 957	13,727 192 808 899 800	3,759 812 059
	0,799 778 396	0,794 686 358	13,672 600 853 099 300	3,674 595 835
	0,789 535 800	0,784 630 345	13,620 445 636 362 400	3,592 677 880
	0,779 520 366	0,774 799 711	13,570 580 790 710 000	3,513 876 598
	0,769 728 817	0,765 180 416	13,522 870 992 857 600	3,438 023 378
	0,760 149 472	0,755 767 918	13,477 190 974 079 800	3,364 961 115
	0,750 776 352	0,746 552 749	13,433 424 623 226 000	3,294 543 452
	0,741 600 798	0,737 528 983	13,391 464 187 766 000	3,226 633 778
	0,732 616 368	0,728 689 198	13,351 209 552 529 500	3,161 104 506
	0,723 815 911	0,720 027 406	13,312 567 592 195 300	3,97 836 320
	0,715 193 248	0,711 537 292	13,275 451 586 431 100	3,36 717 546
	0,425	0,425	12,400	0,1 202
	0,422	0,422	12,400	0,1 193
	0,419	0,419	12,400	0,1 184
	0,415	0,415	12,300	0,1 174
	0,412	0,412	12,300	0,1 165
	0,409	0,409	12,300	0,1 156
	0,406	0,406	12,300	0,1 147
	0,402	0,402	12,300	0,1 138
	0,399	0,399	12,300	0,1 129
	0,396	0,396	12,300	0,1 120
	0,393	0,393	12,300	0,1 112
	0,390	0,390	12,300	0,1 103
	0,387	0,387	12,300	0,1 094
	0,384	0,384	12,300	0,1 086
	0,381	0,381	12,300	0,1 077
	0,378	0,378	12,300	0,1 069
	0,375	0,375	12,300	0,1 061
	0,372	0,372	12,300	0,1 052
	0,369	0,369	12,300	0,1 044
	0,366	0,366	12,300	0,1 036
	0,363	0,363	12,300	0,1 028
	0,361	0,361	12,300	0,1 020
	0,358	0,358	12,300	0,1 012
	0,355	0,355	12,300	0,1 004
	0,352	0,352	12,200	0,996

Данные по количеству итераций и заданным точностям для градиентного метода сведены в таблицу 5.14

Таблица 5.14 — Зависимость числа итераций от точности


Точность	Количество итераций
0,1
0,01
0,001
0,0001
0,1
0,1

Рисунок 5.2 — Графическое представление зависимости количества итераций N от точности E для градиентного метода.

Таким образом, анализируя полученные зависимости можно сделать вывод о том, что метод Нелдера-Мида является более эффективным. Так же следует отметить, что градиентный метод быстро приближается к экстремуму, когда текущая точка находится далеко от него, и резко замедляется вблизи экстремума.

Следует заметить, что эффективность применения методов оптимизации прежде всего обусловлена видом функции.

6. ЗАКЛЮЧЕНИЕ

В курсовой работе произведена минимизации функции с помощью метода оптимизации нулевого порядка — метода Нелдера-Мида и метода оптимизации первого порядка — градиентного метода с дроблением шага.

В результате реализации градиентного метода минимальное значение функции составляет. Данный оптимум достигнут в точке. Этот метод позволяет найти минимум (при начальной точке Х (1;1)) за 1263 итерации при точности решения. При этом параметр останова равен 0,99 491.

Для каждого из методов была установлена зависимость числа итераций от заданной точности. Анализируя полученные результаты, можно сделать вывод о том, что по числу итераций более эффективным является метод Нелдера-Мида. Однако следует отметить, что эффективность этих методов может изменяться в зависимости от выбора начального приближения и вида функции. Следует также учесть, что градиентный метод может быть непригоден в тех случаях, если расчет производных вызывает затруднение.

7. ПРИЛОЖЕНИЕ

В таблицах представлены координаты точек, образующих линии уровня

В настоящем приложении представлена реализация программного кода для каждого из методов оптимизации. Используемый язык программирования — Visual Studio C# 2005.

Градиентный метод с дроблением шага

namespace GradientL

{public partial class Form1: Form

{public Form1()

{InitializeComponent ();}

public static string[] str = new string[100 000];

struct Tk

{public double x1, x2;

public Tk (double X, double Y)

{x1 = X;

x2 = Y;}

public static Tk operator /(Tk v1, double q)

{return new Tk (v1.x1 / q, v1. x2 / q);}

public static Tk operator *(Tk v, double d)

{return new Tk (v.x1 * d, v. x2 * d);}

public static Tk operator *(Tk v1, Tk v2)

{return new Tk (v1.x1 * v2. x1, v1. x2 * v2. x2);}

public static Tk operator -(Tk v1, Tk v2)

{return new Tk (v1.x1 — v2. x1, v1. x2 — v2. x2);}

public static Tk operator +(Tk v1, Tk v2)

{return new Tk (v1.x1 + v2. x1, v1. x2 + v2. x2);}

public static double Dist (Tk v1, Tk v2)

{return Math. Sqrt ((v1.x1 — v2. x1) * (v1.x1 — v2. x1) + (v1.x2 — v2. x2) * (v1.x2 — v2. x2));}

public override string ToString ()

{return «(«+ this. x1.ToString («f5») + «;» + this. x2.ToString («f5») + «)» ;}}

class Pr

{public static double f (Tk c)

{return 12 + c. x1 * c. x1 + (1 + c. x2 * c. x2) * c. x2 * c. x2 + (c.x1 * c. x1 * c. x2 * c. x2 + 100) * (c.x1 — c. x2) * (c.x1 — c. x2);}

static Tk gradient (Tk c)

{Tk N = new Tk (2 * c. x1 + 2 * c. x1 * c. x2 * c. x2 *

(c.x1 — c. x2)*(c.x1 — c. x2) + 2 * (c.x1 * c. x1 * c. x2 * c. x2 + 100) * (c.x1 — c. x2),

2 * c. x2*c.x2*c.x2+2*c.x2*(1+c.x2*c.x2)+

2*c.x2*c.x1*c.x1*(c.x1-c.x2)*(c.x1-c.x2)-2*(c.x1-c.x2)*

(c.x1*c.x1*c.x2*c.x2+100));

return N;}

public static double Dl (Tk c)

{return Math. Sqrt (c.x1 * c. x1 + c. x2 * c. x2);}

public static void Tr (double eps, ref Tk ca, out double fn, out int i)

{Tk cb = new Tk (1, 1), st = new Tk (0.5, 0.5);

Tk step = new Tk (1, 1), eq; i = 0;

{while (true)

{cb = ca — step * gradient (ca);

eq = st * step * gradient (cb) * gradient (cb);

if (f (cb — step * gradient (cb)) >= (f (cb) — Dl (eq)))

{ step. x1 /= 2;

step.x2 /= 2;}

else break;}

fn = f (ca);

i++;

str[i] = String. Format («{0}» + «) «+ «{1}» + «; «+

" {2}" + «; «+ «{3}» + «.», i. ToString (), ca. ToString (), fn. ToString («f6»), Dl (gradient (cb)).ToString («f6»));

ca = cb;}

while (Dl (gradient (cb)) >= eps);

fn = f (cb);}}

private void button1_Click (object sender, EventArgs e)

{listBox1.Items.Clear ();

double Et = Convert. ToDouble (textBox3.Text);

double fn;

int j;

Tk mas = new Tk (Convert.ToDouble (textBox1.Text), Convert. ToDouble (textBox2.Text));

Pr.Tr (Et, ref mas, out fn, out j);

Min.Visible = true;

Min.Text = String. Format («{0}» + «; «+ «{1}» + «; «+

" {2}", mas. ToString (), fn. ToString (), j. ToString ());

for (int i = 1; i < j; i++)

listBox1.Items.Add (str[i]);}

private void Form1_Load (object sender, EventArgs e){}}}

Метод Нелдера-Мида

namespace Nelder_Method