Презентация Одномерная оптимизация. Метод деления интервала пополам онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Одномерная оптимизация. Метод деления интервала пополам абсолютно бесплатно. Урок-презентация на эту тему содержит всего 59 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:59 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.56 MB
- Просмотров:84
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: 2.2.5. Метод деления интервала пополам
Метод относится к последовательным стратегиям и
позволяет исключить из дальнейшего рассмотрения на
каждой итерации в точности половину текущего
интервала.
Задается начальный интервал неопределенности
и требуемая точность поиска
Реализация метода основана на выборе трех пробных
точек, равномерно распределенных на текущем
интервале ( делящем его на четыре равные части).
№2 слайд
Содержание слайда: Пусть длина интервала
Пусть длина интервала
Разделим интервал точками и на четыре равные части
Вычисляются значения целевой функции
Сравниваются полученные значения и находится новый
интервал неопределенности следующим образом:
№3 слайд
Содержание слайда:
№4 слайд
Содержание слайда:
№5 слайд
Содержание слайда:
№6 слайд
Содержание слайда: Затем снова вычисляются координаты и
Затем снова вычисляются координаты и
и продолжают поиск до выполнения условия
За минимальное значение принимают
№7 слайд
Содержание слайда:
№8 слайд
Содержание слайда: 2.2.6. Метод золотого сечения
Метод относится к последовательным стратегиям.
Задается начальный интервал неопределенности
и требуемая точность поиска
В качестве точек вычисления целевой функции
выбираются точки золотого сечения. Тогда с учетом
свойств золотого сечения на каждой итерации, кроме
первой, требуется только одно новое вычисление
целевой функции.
№9 слайд
Содержание слайда: Рассмотрим способ размещения точек золотого
Рассмотрим способ размещения точек золотого
сечения на интервале
Пусть длина интервала равна а точка делит его на
две части и
№10 слайд
Содержание слайда: Термин золотое сечение ввел Леонардо да Винчи.
Термин золотое сечение ввел Леонардо да Винчи.
Точка называется золотым сечением отрезка
если имеет место соотношение
Отсюда
№11 слайд
Содержание слайда: Так как нас интересует только положительное
Так как нас интересует только положительное
решение, то
№12 слайд
Содержание слайда: Из этого соотношения имеем
Из этого соотношения имеем
№13 слайд
Содержание слайда: Поскольку заранее неизвестно, в какой
Поскольку заранее неизвестно, в какой
последовательности ( или ) делить
интервал неопределенности, то рассматривают
внутренние точки, соответствующие двум этим
способам деления
№14 слайд
Содержание слайда: Точки деления и с учетом полученных
Точки деления и с учетом полученных
значений
Новый уменьшенный интервал неопределенности
выбирается следующим образом.
№15 слайд
Содержание слайда: а) если то отрезком локализации точки
а) если то отрезком локализации точки
минимума становится отрезок
№16 слайд
Содержание слайда: Определим положение точки на интервале
Определим положение точки на интервале
Вычислим отношение
Следовательно точка является второй точкой
золотого сечения отрезка
Положим
№17 слайд
Содержание слайда: б) если то отрезком локализации точки
б) если то отрезком локализации точки
минимума становится отрезок
№18 слайд
Содержание слайда: Определим положение точки на интервале
Определим положение точки на интервале
Вычислим отношение
Следовательно точка первая точка
золотого сечения отрезка
Положим
№19 слайд
Содержание слайда: Процесс оптимизации заканчивается при выполнении
Процесс оптимизации заканчивается при выполнении
условия
В качестве минимального значения берется середина
последнего интервала
№20 слайд
Содержание слайда:
№21 слайд
Содержание слайда: При эффективность метода золотого сечения
При эффективность метода золотого сечения
выше, чем у метода дихотомии, так как при каждом
последующем вычислении целевой функции интервал
неопределенности уменьшается в раза.
За итераций длина интервала будет равна
Точность на шаге вычислений можно оценить
неравенством
Отсюда следует, что для достижения требуемой точности
требуется
итераций.
№22 слайд
Содержание слайда: 2.2.7. Метод Фибоначчи
Метод Фибоначчи относится к последовательным
стратегиям и обеспечивает максимальное
сокращение интервала неопределенности при
заданном количестве вычислений целевой функции.
Алгоритм поиска по методу Фибоначчи
определяется тем же правилом симметрии, что и
алгоритм по методу золотого сечения: на первой
итерации выбираются две точки, расположенные
симметрично внутри интервала неопределенности ;
на каждой последующей итерации точка очередного
вычисления выбирается симметрично оставшейся
точки. Разница заключается в выборе точек.
№23 слайд
Содержание слайда: Для простоты изложения алгоритма
Для простоты изложения алгоритма
рассмотрим интервал неопределенности
Обозначим через - длину
интервала
№24 слайд
Содержание слайда:
№25 слайд
Содержание слайда:
№26 слайд
Содержание слайда: Определим величину Для этого
Определим величину Для этого
рассмотрим - ю итерацию.
Для того, чтобы получить наибольшее
уменьшение интервала неопределенности,
расположим точки и на расстоянии
по обе стороны от середины отрезка (см.
рисунок).
№27 слайд
Содержание слайда:
№28 слайд
Содержание слайда: Интервал неопределенности будет иметь
Интервал неопределенности будет иметь
длину следовательно
На предыдущем этапе точки и
должны быть помещены симметрично
внутри интервала Следовательно
Аналогично
№29 слайд
Содержание слайда: Таким образом,
Таким образом,
и так далее.
№30 слайд
Содержание слайда: Общее выражение для произвольного интервала
Общее выражение для произвольного интервала
неопределенности имеет вид
где коэффициенты называются числами Фибоначчи
и определяются следующим образом
Последовательность чисел Фибоначчи имеет вид
№31 слайд
Содержание слайда: Пусть начальный интервал неопределенности имеет
Пусть начальный интервал неопределенности имеет
длину Через числа Фибоначчи
выражение для определения можно получить из
выражения (2.2), полагая
Из последнего выражения найдем длину
интервала неопределенности на -й итерации
Далее, используя выражение (2.2), находим положение
первой точки которая помещается на расстоянии
от одного из концов начального интервала.
№32 слайд
Содержание слайда: При получим
При получим
№33 слайд
Содержание слайда: Используемое значение определяется
Используемое значение определяется
из условия
После того как найдено положение первой
точки, числа Фибоначчи больше не
используются.
Приведем дальнейшую схему вычисления
интервала неопределенности.
Вычислим
№34 слайд
Содержание слайда:
№35 слайд
Содержание слайда:
№36 слайд
Содержание слайда:
№37 слайд
Содержание слайда:
№38 слайд
Содержание слайда:
№39 слайд
Содержание слайда:
№40 слайд
Содержание слайда: Заметим, что при достаточно больших
Заметим, что при достаточно больших
значение
стремится к 0.618, так что методы Фибоначчи и
золотого сечения становятся асимптотически
эквивалентными
№41 слайд
Содержание слайда: Сравнение методов уменьшения интервала неопределенности
№42 слайд
Содержание слайда: 2.2.8. Метод квадратичной аппроксимации
Основная идея метода связана с возможностью
аппроксимации гладкой функции полиномом и
последующего использования аппроксимирующего
полинома для оценивания координат точки минимума.
Пусть известны значения целевой функции в
трех различных точках равные
соответственно
Запишем интерполяционный многочлен в форме
Лагранжа
№43 слайд
Содержание слайда: Вычислим значения в каждой из трех точек
Вычислим значения в каждой из трех точек
При
при
при
№44 слайд
Содержание слайда: Разрешая последнее уравнение относительно
Разрешая последнее уравнение относительно
получим
Из уравнения (2.2)
№45 слайд
Содержание слайда: находим точку
находим точку
Поскольку аппроксимирующий квадратичный полином
является унимодальной функцией, то коэффициент
при старшем члене будет положителен.
Следовательно, в точке полином
имеет локальный минимум.
№46 слайд
Содержание слайда: Рассмотрим алгоритм квадратичной интерполяции, называемый методом Пауэлла.
Рассмотрим алгоритм квадратичной интерполяции, называемый методом Пауэлла.
Пусть начальная точка, - величина шага
по оси и числа, характеризующие точность
поиска.
Вычислить точку
Вычислить значения целевой функции в точках
Сравнить значения и найти точку
так, чтобы точки были как можно ближе к
искомой точке минимума.
№47 слайд
Содержание слайда:
№48 слайд
Содержание слайда: Вычислить
Вычислить
Найти
По трем точкам вычислить используя
формулу (2.6) и величину
Если знаменатель в формуле (2.6) на некоторой
итерации обращается в нуль, то результатом
интерполяции будет прямая. В этом случае
рекомендуется обозначить и перейти
к пункту 1.
№49 слайд
Содержание слайда: Проверить условие окончания процесса вычислений
Проверить условие окончания процесса вычислений
Если оба условия выполнены, то поиск закончен и
В противном случае выбрать наилучшую точку ( или ) и две точки по обе стороны от нее. Обозначить их в естественном порядке и перейти к пункту 5.
№50 слайд
Содержание слайда: Выбор двух точек слева и справа от наилучшей точки
Выбор двух точек слева и справа от наилучшей точки
( или ) осуществляется следующим образом:
а) если точка находится между точками и
то
б) если точка находится между точками и
то
№51 слайд
Содержание слайда:
№52 слайд
Содержание слайда:
№53 слайд
Содержание слайда:
№54 слайд
Содержание слайда: Пример 2.3. Минимизировать функцию
Пример 2.3. Минимизировать функцию
методом Пауэлла с точностью
Решение. Зададим начальную точку и величину шага
Итерация 1. Вычислим и
Так как то положим
Вычислим
Найдем
По формулам (2.4) и (2.5) найдем
По формуле (2.6) вычислим точку интерполяционного полинома
и величину целевой функции
№55 слайд
Содержание слайда: Проверим условие окончания поиска
Проверим условие окончания поиска
(не выполняется),
следовательно продолжаем поиск. Учитывая, что
выбираем как наилучшую точку. Слева от нее
а справа
Обозначим их в естественном порядке
Этим точкам соответствуют значения целевой функции
Итерация 2.
№56 слайд
Содержание слайда: По формулам (2.4) и (2.5) найдем
По формулам (2.4) и (2.5) найдем
По формуле (2.6) вычислим точку интерполяционного полинома
и величину целевой функции
Проверим условие окончания поиска
- условие не выполняется.
Выбираем как наилучшую точку. Слева от нее
а справа
Обозначим их в естественном порядке
Этим точкам соответствуют значения целевой функции
№57 слайд
Содержание слайда: Итерация 3.
Итерация 3.
По формулам (2.4) и (2.5) найдем
По формуле (2.6) вычислим точку интерполяционного полинома
и величину целевой функции
Проверим условие окончания поиска
Следовательно, поиск закончен. Решение
№58 слайд
Содержание слайда: Найдем аналитически координату точки минимума
Найдем аналитически координату точки минимума
Проверим выполнение достаточного условия экстремума
В точке выполняется условие
- следовательно целевая функция в данной точке имеет минимум.
№59 слайд
Содержание слайда:
Скачать все slide презентации Одномерная оптимизация. Метод деления интервала пополам одним архивом:
