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

Метод золотого сечения. Вметоде дихотомии при выполнении каждой итерации оп­ределяются две новые пробные точки: х[кхг Рассмотрим такое симметричное их расположение на отрезке [а\ Ь]

Читайте также:
  1. F. Метод, основанный на использовании свойства монотонности показательной функции .
  2. FAST (Методика быстрого анализа решения)
  3. I этап Подготовка к развитию грудобрюшного типа дыхания по традиционной методике
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. 3.2. Двойственный симплекс-метод.
  6. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  7. I. Метод рассмотрения остатков от деления.
  8. I. Методические основы
  9. I. Методические основы оценки эффективности инвестиционных проектов
  10. I. Организационно-методический раздел
  11. I. Предмет и метод теоретической экономики
  12. I. Что изучает экономика. Предмет и метод экономики.

В методе дихотомии при выполнении каждой итерации оп­ределяются две новые пробные точки: х[кхг Рассмотрим такое симметричное их расположение на отрезке [а\ Ь], при котором одна из них становится пробной точкой и на новом отрезке, получен­ном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением значения функции /(х) только в одной точке, так как другое значение уже найдено на предыдущей итерации. Таким свойством обладают точки золотого сечения отрезка [а; Ь].

Золотым сечением отрезка называется такое деление отрез­ка на две неравные части, что отношение длины всего отрезка к ■ длине его большей части равно отношению длин большей и мень­шей частей отрезка. Находятся две точки х, и х2 (х, < х2)

(1.12)

которые делят отрезок [а; Ь] в указанном отношении:


 


b~x

п > log
(1.11)

Ь-а-Ь

2е-6 Опишем алгоритм метода дихотомии.

ШагО. Задать параметр точности 8 > 0, параметр алгоритма 8е(0; 2s).

Шаг 1. Вычислить х] и х, по формулам (1.8) и значения функции/^,) и/(х2).


b-xt x,-a x2-a

Свойство золотого сечения как раз и замечательно тем, что точка хх также производит золотое сечение отрезка [я; х2], а точка х, в том же отношении делит отрезок [х,; Ь]. Это свойство и кла­дется в основу метода золотого сечения.


Отметим, что точки *, и х2 симметричны относительно сере­дины очередного отрезка:

х = а + Ъ - х; х = а+ Ъ - х.

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

В конце вычислений в качестве приближенного значения х" можно взять середину последнего из полученных отрезков. На каждой итерации отрезок поиска точки минимума уменьшается

в одном и том же отношении т = ( -1 ] 2, поэтому в результате

п итераций его длина становится равной hn = i"(b - а). Таким об­разом, точность ел определения точки х* после п итераций нахо­дится по формуле

e-=y = JT"(*-«). (1.15)

а условием окончания поиска х' с наперед заданной точностью s служит неравенство е t < e. Используя это условие и формулу (1.15), можно оценить число итераций, потребное для достижения за­данной точности е:

2±_ Ь-а

(1.16)

Опишем алгоритм метода золотого сечения. Шаг 0. Задать параметр точности е > 0, положить

(1.14)
2s

 


/(х,) =/(л2), хг = а + Ь - х{ и вычислить/(х(). Положить ел = тел и перейти к шагу 2.

ЩагАЗавершить поиск, положив х'»х =-------./' «/(xj.

1.3. Сравнительный анализ методов одномерного поиска

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

Поскольку при реализации методов одномерного поиска определение значений функции f{x) требует несравненно боль­ших затрат, чем выполнение таких вспомогательных операций, как вычисление точек перебора, сравнение значений функции и т.п., то объем вычислений можно оценить количеством N вычисле­ний значений функцииДх).

Метод считается тем эффективнее, чем меньше N, гаранти­рующее заданную точность определения точки х' минимума фун-кцииДх). Для сравнения рассматриваемых методов по этому при­знаку рекомендуется составить таблицу значений N(z) в зависи­мости от требуемой точности определения х'.

При сравнении методов по точности более эффективным счи­тается тот из рассматриваемых методов, который обеспечивает достижение меньшего значения e(N) при одинаковом объеме вы­числений. Для получения вывода о точности рекомендуется со­ставить таблицу значений достигнутой точности z(N) в зависи­мости от количества N найденных значений функции/(х)для ука­занных методов.

Порядок выполнения лабораторной работы

1. Кратко описать изучаемые методы одномерного поиска.

2. Решить задачу (1.1) классическим методом.

II


3. Выполнить программную реализацию каждого алг

4. Провести расчеты указанной в индивидуальном
задачи при различных значениях параметров алгоритмов с ц?
лью получения результатов, достаточных для сравнения изучае­
мых методов.

 

5. Выполнить сравнительный анализ (см. подразд. 1.3) изу­
чаемых методов, составив для этого таблицы значений /V(e) и е (М

6. Сформулировать вывод о сравнительной эффективности
изучаемых методов. Содержание работы отразить в отчете.

Задания для лабораторной работы

1. Минимизировать функцию f (х) = ху[х^Л ~ х1 на отрез­ке [-1; 2].

— на отрез-

2. Минимизировать функцию /(х) = л--1п.т +
ке [0,1; 3J.

3. Минимизировать функцию /(*) = х" + е~v на отрезке [0; 2].

4. Минимизировать функцию f(x) = x~\n(x+l) на отрез­
ке [-0,3; 2].

) --—-— на отрез-

5. Минимизировать функцию f(x) = —

ке [0; 3].

6. Минимизировать функцию /(л-) = л3 -3sinjc на отрез­
ке [0; 1].

7. Минимизировать функцию f(x) = е" + - на отрезке [0,5; 2].

8. Минимизировать функцию /(.*) = х* + х2 + х + 1 на отрез­
ке [-1;0].


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

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



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