🗊Презентация Одномерная оптимизация. Метод деления интервала пополам

Категория: Математика
Нажмите для полного просмотра!
Одномерная оптимизация. Метод деления интервала пополам, слайд №1Одномерная оптимизация. Метод деления интервала пополам, слайд №2Одномерная оптимизация. Метод деления интервала пополам, слайд №3Одномерная оптимизация. Метод деления интервала пополам, слайд №4Одномерная оптимизация. Метод деления интервала пополам, слайд №5Одномерная оптимизация. Метод деления интервала пополам, слайд №6Одномерная оптимизация. Метод деления интервала пополам, слайд №7Одномерная оптимизация. Метод деления интервала пополам, слайд №8Одномерная оптимизация. Метод деления интервала пополам, слайд №9Одномерная оптимизация. Метод деления интервала пополам, слайд №10Одномерная оптимизация. Метод деления интервала пополам, слайд №11Одномерная оптимизация. Метод деления интервала пополам, слайд №12Одномерная оптимизация. Метод деления интервала пополам, слайд №13Одномерная оптимизация. Метод деления интервала пополам, слайд №14Одномерная оптимизация. Метод деления интервала пополам, слайд №15Одномерная оптимизация. Метод деления интервала пополам, слайд №16Одномерная оптимизация. Метод деления интервала пополам, слайд №17Одномерная оптимизация. Метод деления интервала пополам, слайд №18Одномерная оптимизация. Метод деления интервала пополам, слайд №19Одномерная оптимизация. Метод деления интервала пополам, слайд №20Одномерная оптимизация. Метод деления интервала пополам, слайд №21Одномерная оптимизация. Метод деления интервала пополам, слайд №22Одномерная оптимизация. Метод деления интервала пополам, слайд №23Одномерная оптимизация. Метод деления интервала пополам, слайд №24Одномерная оптимизация. Метод деления интервала пополам, слайд №25Одномерная оптимизация. Метод деления интервала пополам, слайд №26Одномерная оптимизация. Метод деления интервала пополам, слайд №27Одномерная оптимизация. Метод деления интервала пополам, слайд №28Одномерная оптимизация. Метод деления интервала пополам, слайд №29Одномерная оптимизация. Метод деления интервала пополам, слайд №30Одномерная оптимизация. Метод деления интервала пополам, слайд №31Одномерная оптимизация. Метод деления интервала пополам, слайд №32Одномерная оптимизация. Метод деления интервала пополам, слайд №33Одномерная оптимизация. Метод деления интервала пополам, слайд №34Одномерная оптимизация. Метод деления интервала пополам, слайд №35Одномерная оптимизация. Метод деления интервала пополам, слайд №36Одномерная оптимизация. Метод деления интервала пополам, слайд №37Одномерная оптимизация. Метод деления интервала пополам, слайд №38Одномерная оптимизация. Метод деления интервала пополам, слайд №39Одномерная оптимизация. Метод деления интервала пополам, слайд №40Одномерная оптимизация. Метод деления интервала пополам, слайд №41Одномерная оптимизация. Метод деления интервала пополам, слайд №42Одномерная оптимизация. Метод деления интервала пополам, слайд №43Одномерная оптимизация. Метод деления интервала пополам, слайд №44Одномерная оптимизация. Метод деления интервала пополам, слайд №45Одномерная оптимизация. Метод деления интервала пополам, слайд №46Одномерная оптимизация. Метод деления интервала пополам, слайд №47Одномерная оптимизация. Метод деления интервала пополам, слайд №48Одномерная оптимизация. Метод деления интервала пополам, слайд №49Одномерная оптимизация. Метод деления интервала пополам, слайд №50Одномерная оптимизация. Метод деления интервала пополам, слайд №51Одномерная оптимизация. Метод деления интервала пополам, слайд №52Одномерная оптимизация. Метод деления интервала пополам, слайд №53Одномерная оптимизация. Метод деления интервала пополам, слайд №54Одномерная оптимизация. Метод деления интервала пополам, слайд №55Одномерная оптимизация. Метод деления интервала пополам, слайд №56Одномерная оптимизация. Метод деления интервала пополам, слайд №57Одномерная оптимизация. Метод деления интервала пополам, слайд №58Одномерная оптимизация. Метод деления интервала пополам, слайд №59
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Одномерная оптимизация. Метод деления интервала пополам. Доклад-сообщение содержит 59 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


2.2.5. Метод деления интервала пополам Метод относится к последовательным стратегиям и позволяет исключить из дальнейшего рассмотрения на каждой итерации в точности половину текущего интервала. Задается начальный интервал неопределенности и требуемая точность поиска Реализация метода основана на выборе трех пробных точек, равномерно распределенных на текущем интервале ( делящем его на четыре равные части).
Описание слайда:
2.2.5. Метод деления интервала пополам Метод относится к последовательным стратегиям и позволяет исключить из дальнейшего рассмотрения на каждой итерации в точности половину текущего интервала. Задается начальный интервал неопределенности и требуемая точность поиска Реализация метода основана на выборе трех пробных точек, равномерно распределенных на текущем интервале ( делящем его на четыре равные части).

Слайд 2


Пусть длина интервала Пусть длина интервала Разделим интервал точками и на четыре равные части Вычисляются значения целевой функции Сравниваются полученные значения и находится новый интервал неопределенности следующим образом:
Описание слайда:
Пусть длина интервала Пусть длина интервала Разделим интервал точками и на четыре равные части Вычисляются значения целевой функции Сравниваются полученные значения и находится новый интервал неопределенности следующим образом:

Слайд 3


Одномерная оптимизация. Метод деления интервала пополам, слайд №3
Описание слайда:

Слайд 4


Одномерная оптимизация. Метод деления интервала пополам, слайд №4
Описание слайда:

Слайд 5


Одномерная оптимизация. Метод деления интервала пополам, слайд №5
Описание слайда:

Слайд 6


Затем снова вычисляются координаты и Затем снова вычисляются координаты и и продолжают поиск до выполнения условия За минимальное значение принимают
Описание слайда:
Затем снова вычисляются координаты и Затем снова вычисляются координаты и и продолжают поиск до выполнения условия За минимальное значение принимают

Слайд 7


Одномерная оптимизация. Метод деления интервала пополам, слайд №7
Описание слайда:

Слайд 8


2.2.6. Метод золотого сечения Метод относится к последовательным стратегиям. Задается начальный интервал неопределенности и требуемая точность поиска В качестве точек вычисления целевой функции выбираются точки золотого сечения. Тогда с учетом свойств золотого сечения на каждой итерации, кроме первой, требуется только одно новое вычисление целевой функции.
Описание слайда:
2.2.6. Метод золотого сечения Метод относится к последовательным стратегиям. Задается начальный интервал неопределенности и требуемая точность поиска В качестве точек вычисления целевой функции выбираются точки золотого сечения. Тогда с учетом свойств золотого сечения на каждой итерации, кроме первой, требуется только одно новое вычисление целевой функции.

Слайд 9


Рассмотрим способ размещения точек золотого Рассмотрим способ размещения точек золотого сечения на интервале Пусть длина интервала равна а точка делит его на две части и
Описание слайда:
Рассмотрим способ размещения точек золотого Рассмотрим способ размещения точек золотого сечения на интервале Пусть длина интервала равна а точка делит его на две части и

Слайд 10


Термин золотое сечение ввел Леонардо да Винчи. Термин золотое сечение ввел Леонардо да Винчи. Точка называется золотым сечением отрезка если имеет место соотношение Отсюда
Описание слайда:
Термин золотое сечение ввел Леонардо да Винчи. Термин золотое сечение ввел Леонардо да Винчи. Точка называется золотым сечением отрезка если имеет место соотношение Отсюда

Слайд 11


Так как нас интересует только положительное Так как нас интересует только положительное решение, то
Описание слайда:
Так как нас интересует только положительное Так как нас интересует только положительное решение, то

Слайд 12


Из этого соотношения имеем Из этого соотношения имеем
Описание слайда:
Из этого соотношения имеем Из этого соотношения имеем

Слайд 13


Поскольку заранее неизвестно, в какой Поскольку заранее неизвестно, в какой последовательности ( или ) делить интервал неопределенности, то рассматривают внутренние точки, соответствующие двум этим способам деления
Описание слайда:
Поскольку заранее неизвестно, в какой Поскольку заранее неизвестно, в какой последовательности ( или ) делить интервал неопределенности, то рассматривают внутренние точки, соответствующие двум этим способам деления

Слайд 14


Точки деления и с учетом полученных Точки деления и с учетом полученных значений Новый уменьшенный интервал неопределенности выбирается следующим образом.
Описание слайда:
Точки деления и с учетом полученных Точки деления и с учетом полученных значений Новый уменьшенный интервал неопределенности выбирается следующим образом.

Слайд 15


а) если то отрезком локализации точки а) если то отрезком локализации точки минимума становится отрезок
Описание слайда:
а) если то отрезком локализации точки а) если то отрезком локализации точки минимума становится отрезок

Слайд 16


Определим положение точки на интервале Определим положение точки на интервале Вычислим отношение Следовательно точка является второй точкой золотого сечения отрезка Положим
Описание слайда:
Определим положение точки на интервале Определим положение точки на интервале Вычислим отношение Следовательно точка является второй точкой золотого сечения отрезка Положим

Слайд 17


б) если то отрезком локализации точки б) если то отрезком локализации точки минимума становится отрезок
Описание слайда:
б) если то отрезком локализации точки б) если то отрезком локализации точки минимума становится отрезок

Слайд 18


Определим положение точки на интервале Определим положение точки на интервале Вычислим отношение Следовательно точка первая точка золотого сечения отрезка Положим
Описание слайда:
Определим положение точки на интервале Определим положение точки на интервале Вычислим отношение Следовательно точка первая точка золотого сечения отрезка Положим

Слайд 19


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

Слайд 20


Одномерная оптимизация. Метод деления интервала пополам, слайд №20
Описание слайда:

Слайд 21


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

Слайд 22


2.2.7. Метод Фибоначчи Метод Фибоначчи относится к последовательным стратегиям и обеспечивает максимальное сокращение интервала неопределенности при заданном количестве вычислений целевой функции. Алгоритм поиска по методу Фибоначчи определяется тем же правилом симметрии, что и алгоритм по методу золотого сечения: на первой итерации выбираются две точки, расположенные симметрично внутри интервала неопределенности ; на каждой последующей итерации точка очередного вычисления выбирается симметрично оставшейся точки. Разница заключается в выборе точек.
Описание слайда:
2.2.7. Метод Фибоначчи Метод Фибоначчи относится к последовательным стратегиям и обеспечивает максимальное сокращение интервала неопределенности при заданном количестве вычислений целевой функции. Алгоритм поиска по методу Фибоначчи определяется тем же правилом симметрии, что и алгоритм по методу золотого сечения: на первой итерации выбираются две точки, расположенные симметрично внутри интервала неопределенности ; на каждой последующей итерации точка очередного вычисления выбирается симметрично оставшейся точки. Разница заключается в выборе точек.

Слайд 23


Для простоты изложения алгоритма Для простоты изложения алгоритма рассмотрим интервал неопределенности Обозначим через - длину интервала
Описание слайда:
Для простоты изложения алгоритма Для простоты изложения алгоритма рассмотрим интервал неопределенности Обозначим через - длину интервала

Слайд 24


Одномерная оптимизация. Метод деления интервала пополам, слайд №24
Описание слайда:

Слайд 25


Одномерная оптимизация. Метод деления интервала пополам, слайд №25
Описание слайда:

Слайд 26


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

Слайд 27


Одномерная оптимизация. Метод деления интервала пополам, слайд №27
Описание слайда:

Слайд 28


Интервал неопределенности будет иметь Интервал неопределенности будет иметь длину следовательно На предыдущем этапе точки и должны быть помещены симметрично внутри интервала Следовательно Аналогично
Описание слайда:
Интервал неопределенности будет иметь Интервал неопределенности будет иметь длину следовательно На предыдущем этапе точки и должны быть помещены симметрично внутри интервала Следовательно Аналогично

Слайд 29


Таким образом, Таким образом, и так далее.
Описание слайда:
Таким образом, Таким образом, и так далее.

Слайд 30


Общее выражение для произвольного интервала Общее выражение для произвольного интервала неопределенности имеет вид где коэффициенты называются числами Фибоначчи и определяются следующим образом Последовательность чисел Фибоначчи имеет вид
Описание слайда:
Общее выражение для произвольного интервала Общее выражение для произвольного интервала неопределенности имеет вид где коэффициенты называются числами Фибоначчи и определяются следующим образом Последовательность чисел Фибоначчи имеет вид

Слайд 31


Пусть начальный интервал неопределенности имеет Пусть начальный интервал неопределенности имеет длину Через числа Фибоначчи выражение для определения можно получить из выражения (2.2), полагая Из последнего выражения найдем длину интервала неопределенности на -й итерации Далее, используя выражение (2.2), находим положение первой точки которая помещается на расстоянии от одного из концов начального интервала.
Описание слайда:
Пусть начальный интервал неопределенности имеет Пусть начальный интервал неопределенности имеет длину Через числа Фибоначчи выражение для определения можно получить из выражения (2.2), полагая Из последнего выражения найдем длину интервала неопределенности на -й итерации Далее, используя выражение (2.2), находим положение первой точки которая помещается на расстоянии от одного из концов начального интервала.

Слайд 32


При получим При получим
Описание слайда:
При получим При получим

Слайд 33


Используемое значение определяется Используемое значение определяется из условия После того как найдено положение первой точки, числа Фибоначчи больше не используются. Приведем дальнейшую схему вычисления интервала неопределенности. Вычислим
Описание слайда:
Используемое значение определяется Используемое значение определяется из условия После того как найдено положение первой точки, числа Фибоначчи больше не используются. Приведем дальнейшую схему вычисления интервала неопределенности. Вычислим

Слайд 34


Одномерная оптимизация. Метод деления интервала пополам, слайд №34
Описание слайда:

Слайд 35


Одномерная оптимизация. Метод деления интервала пополам, слайд №35
Описание слайда:

Слайд 36


Одномерная оптимизация. Метод деления интервала пополам, слайд №36
Описание слайда:

Слайд 37


Одномерная оптимизация. Метод деления интервала пополам, слайд №37
Описание слайда:

Слайд 38


Одномерная оптимизация. Метод деления интервала пополам, слайд №38
Описание слайда:

Слайд 39


Одномерная оптимизация. Метод деления интервала пополам, слайд №39
Описание слайда:

Слайд 40


Заметим, что при достаточно больших Заметим, что при достаточно больших значение стремится к 0.618, так что методы Фибоначчи и золотого сечения становятся асимптотически эквивалентными
Описание слайда:
Заметим, что при достаточно больших Заметим, что при достаточно больших значение стремится к 0.618, так что методы Фибоначчи и золотого сечения становятся асимптотически эквивалентными

Слайд 41


Сравнение методов уменьшения интервала неопределенности
Описание слайда:
Сравнение методов уменьшения интервала неопределенности

Слайд 42


2.2.8. Метод квадратичной аппроксимации Основная идея метода связана с возможностью аппроксимации гладкой функции полиномом и последующего использования аппроксимирующего полинома для оценивания координат точки минимума. Пусть известны значения целевой функции в трех различных точках равные соответственно Запишем интерполяционный многочлен в форме Лагранжа
Описание слайда:
2.2.8. Метод квадратичной аппроксимации Основная идея метода связана с возможностью аппроксимации гладкой функции полиномом и последующего использования аппроксимирующего полинома для оценивания координат точки минимума. Пусть известны значения целевой функции в трех различных точках равные соответственно Запишем интерполяционный многочлен в форме Лагранжа

Слайд 43


Вычислим значения в каждой из трех точек Вычислим значения в каждой из трех точек При при при
Описание слайда:
Вычислим значения в каждой из трех точек Вычислим значения в каждой из трех точек При при при

Слайд 44


Разрешая последнее уравнение относительно Разрешая последнее уравнение относительно получим Из уравнения (2.2)
Описание слайда:
Разрешая последнее уравнение относительно Разрешая последнее уравнение относительно получим Из уравнения (2.2)

Слайд 45


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

Слайд 46


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

Слайд 47


Одномерная оптимизация. Метод деления интервала пополам, слайд №47
Описание слайда:

Слайд 48


Вычислить Вычислить Найти По трем точкам вычислить используя формулу (2.6) и величину Если знаменатель в формуле (2.6) на некоторой итерации обращается в нуль, то результатом интерполяции будет прямая. В этом случае рекомендуется обозначить и перейти к пункту 1.
Описание слайда:
Вычислить Вычислить Найти По трем точкам вычислить используя формулу (2.6) и величину Если знаменатель в формуле (2.6) на некоторой итерации обращается в нуль, то результатом интерполяции будет прямая. В этом случае рекомендуется обозначить и перейти к пункту 1.

Слайд 49


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

Слайд 50


Выбор двух точек слева и справа от наилучшей точки Выбор двух точек слева и справа от наилучшей точки ( или ) осуществляется следующим образом: а) если точка находится между точками и то б) если точка находится между точками и то
Описание слайда:
Выбор двух точек слева и справа от наилучшей точки Выбор двух точек слева и справа от наилучшей точки ( или ) осуществляется следующим образом: а) если точка находится между точками и то б) если точка находится между точками и то

Слайд 51


Одномерная оптимизация. Метод деления интервала пополам, слайд №51
Описание слайда:

Слайд 52


Одномерная оптимизация. Метод деления интервала пополам, слайд №52
Описание слайда:

Слайд 53


Одномерная оптимизация. Метод деления интервала пополам, слайд №53
Описание слайда:

Слайд 54


Пример 2.3. Минимизировать функцию Пример 2.3. Минимизировать функцию методом Пауэлла с точностью Решение. Зададим начальную точку и величину шага Итерация 1. Вычислим и Так как то положим Вычислим Найдем По формулам (2.4) и (2.5) найдем По формуле (2.6) вычислим точку интерполяционного полинома и величину целевой функции
Описание слайда:
Пример 2.3. Минимизировать функцию Пример 2.3. Минимизировать функцию методом Пауэлла с точностью Решение. Зададим начальную точку и величину шага Итерация 1. Вычислим и Так как то положим Вычислим Найдем По формулам (2.4) и (2.5) найдем По формуле (2.6) вычислим точку интерполяционного полинома и величину целевой функции

Слайд 55


Проверим условие окончания поиска Проверим условие окончания поиска (не выполняется), следовательно продолжаем поиск. Учитывая, что выбираем как наилучшую точку. Слева от нее а справа Обозначим их в естественном порядке Этим точкам соответствуют значения целевой функции Итерация 2.
Описание слайда:
Проверим условие окончания поиска Проверим условие окончания поиска (не выполняется), следовательно продолжаем поиск. Учитывая, что выбираем как наилучшую точку. Слева от нее а справа Обозначим их в естественном порядке Этим точкам соответствуют значения целевой функции Итерация 2.

Слайд 56


По формулам (2.4) и (2.5) найдем По формулам (2.4) и (2.5) найдем По формуле (2.6) вычислим точку интерполяционного полинома и величину целевой функции Проверим условие окончания поиска - условие не выполняется. Выбираем как наилучшую точку. Слева от нее а справа Обозначим их в естественном порядке Этим точкам соответствуют значения целевой функции
Описание слайда:
По формулам (2.4) и (2.5) найдем По формулам (2.4) и (2.5) найдем По формуле (2.6) вычислим точку интерполяционного полинома и величину целевой функции Проверим условие окончания поиска - условие не выполняется. Выбираем как наилучшую точку. Слева от нее а справа Обозначим их в естественном порядке Этим точкам соответствуют значения целевой функции

Слайд 57


Итерация 3. Итерация 3. По формулам (2.4) и (2.5) найдем По формуле (2.6) вычислим точку интерполяционного полинома и величину целевой функции Проверим условие окончания поиска Следовательно, поиск закончен. Решение
Описание слайда:
Итерация 3. Итерация 3. По формулам (2.4) и (2.5) найдем По формуле (2.6) вычислим точку интерполяционного полинома и величину целевой функции Проверим условие окончания поиска Следовательно, поиск закончен. Решение

Слайд 58


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

Слайд 59


Одномерная оптимизация. Метод деления интервала пополам, слайд №59
Описание слайда:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию