|
||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Метод золотого сечения. Вметоде дихотомии при выполнении каждой итерации определяются две новые пробные точки: х[кхг Рассмотрим такое симметричное их расположение на отрезке [а\ Ь]В методе дихотомии при выполнении каждой итерации определяются две новые пробные точки: х[кхг Рассмотрим такое симметричное их расположение на отрезке [а\ Ь], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением значения функции /(х) только в одной точке, так как другое значение уже найдено на предыдущей итерации. Таким свойством обладают точки золотого сечения отрезка [а; Ь]. Золотым сечением отрезка называется такое деление отрезка на две неравные части, что отношение длины всего отрезка к ■ длине его большей части равно отношению длин большей и меньшей частей отрезка. Находятся две точки х, и х2 (х, < х2) (1.12) которые делят отрезок [а; Ь] в указанном отношении:
Ь-а-Ь 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, положить
/(х,) =/(л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) изу 6. Сформулировать вывод о сравнительной эффективности Задания для лабораторной работы 1. Минимизировать функцию f (х) = ху[х^Л ~ х1 на отрезке [-1; 2].
2. Минимизировать функцию /(х) = л--1п.т + 3. Минимизировать функцию /(*) = х" + е~v на отрезке [0; 2]. 4. Минимизировать функцию f(x) = x~\n(x+l) на отрез
5. Минимизировать функцию f(x) = — ке [0; 3]. 6. Минимизировать функцию /(л-) = л3 -3sinjc на отрез 7. Минимизировать функцию f(x) = е" + - на отрезке [0,5; 2]. 8. Минимизировать функцию /(.*) = х* + х2 + х + 1 на отрез Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.) |