Методы Флетчера-Ривса, Дэвидона-Флетчера-Пауэлла, Кубической интерполяции

Сентябрь 13, 2022

Главная
Математика
Методы Флетчера-Ривса, Дэвидона-Флетчера-Пауэлла, Кубической интерполяции

Содержание

2. СОДЕРЖАНИЕ Метод Флетчера-Ривза Алгоритм Дэвидона - Флетчера - Пауэлла Метод кубической интерполяции
3. МЕТОД ФЛЕТЧЕРА-РИВЗА
4. МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ Формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Определение. Два n-мерных
5. СТРАТЕГИЯ МЕТОДА ФЛЕТЧЕРА-РИВСА Состоит в построении последовательности точек {xk}, k=0, 1, 2, ... таких, что f(xk+1)
6. СХОДИМОСТЬ МЕТОДА Теорема 1. Если квадратичная функция f(x) = (х, Нх) + (b, х) + а
7. Теорема 2 гарантирует сходимость последовательности {xk} к стационарной точке x*, где ▽f(x*)=0. Поэтому найденная точка x*
8. АЛГОРИТМ ДЭВИДОНА - ФЛЕТЧЕРА - ПАУЭЛЛА Рассмотрим алгоритм Дэвидона - Флетчера - Пауэлла минимизации дифференцируемой функции
9. РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ ПО МЕТОДУ ДЭВИДОНА - ФЛЕТЧЕРА – ПАУЭЛЛА Рассмотрим следующую задачу : минимизировать (x1 -
10. МЕТОД ДЭВИДОНА - ФЛЕТЧЕРА – ПАУЭЛЛА
11. МЕТОД КУБИЧЕСКОЙ ИНТЕРПОЛЯЦИИ При решении реальных задач редко приходится иметь дело с функциями одной переменной. Однако
12. КУБИЧЕСКАЯ ИНТЕРПОЛЯЦИЯ (МЕТОД ДЭВИДОНА) ЛОКАЛЬНАЯ ЗАМЕНА МИНИМИЗИРУЕМОЙ ФУНКЦИИ МНОГОЧЛЕНОМ ТРЕТЬЕЙ СТЕПЕНИ (ТРИ ЧЛЕНА В РАЗЛОЖЕНИИ ТЕЙЛОРА)
13. ЗАКЛЮЧЕНИЕ Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Первоначально метод
15. Скачать презентацию

Слайд 2

СОДЕРЖАНИЕ
Метод Флетчера-Ривза
Алгоритм Дэвидона - Флетчера - Пауэлла
Метод кубической интерполяции

Слайд 3

МЕТОД ФЛЕТЧЕРА-РИВЗА

Слайд 4

МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ
Формирует направления поиска, в большей мере соответствующие геометрии минимизируемой

функции.
Определение.
Два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н- симметрическая положительно определенная матрица размером nхn.

Слайд 5

СТРАТЕГИЯ МЕТОДА ФЛЕТЧЕРА-РИВСА
Состоит в построении последовательности точек {xk}, k=0, 1, 2,

... таких, что
f(xk+1) < f(xk), k=0, 1, 2, ...
Точки последовательности {xk} вычисляются по правилу: xk+1=xk-tkdk, k = 0, 1, 2,… dk = ▽f(xk) + bk-1▽f(xk-1)

Слайд 6

СХОДИМОСТЬ МЕТОДА
Теорема 1. Если квадратичная функция f(x) = (х, Нх) +

(b, х) + а с неотрицательно определенной матрицей Н достигает своего минимального значения на Rn, то метод Флетчера-Ривса обеспечивает отыскание точки минимума не более чем за n шагов. Теорема 2. Пусть функция f(x) дифференцируема и ограничена снизу на Rm, а ее градиент удовлетворяет условию
Липшица
Тогда при произвольной начальной точке для метода Полака-Рибьера имеем

Слайд 7

Теорема 2 гарантирует сходимость последовательности {xk} к стационарной точке x*, где

▽f(x*)=0. Поэтому найденная точка x* нуждается в дополнительном исследовании для ее классификации. Метод Полака-Рибьера гарантирует сходимость последовательности {xk} к точке минимума только для сильно выпуклых функций.
Оценка скорости сходимости получена только для сильно выпуклых функций, в этом случае последовательность {xk} сходится к точке минимума функции f(x) со скоростью: |xk+n – x*| ≤ C|xk – x*|, k = {0, n, 2, …}

Слайд 8

АЛГОРИТМ ДЭВИДОНА - ФЛЕТЧЕРА - ПАУЭЛЛА
Рассмотрим алгоритм Дэвидона - Флетчера -

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

Слайд 9

РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ ПО МЕТОДУ ДЭВИДОНА - ФЛЕТЧЕРА – ПАУЭЛЛА Рассмотрим следующую задачу

: минимизировать (x1 - 2)4 + (x1 - 2x2)2.

Слайд 10

МЕТОД ДЭВИДОНА - ФЛЕТЧЕРА – ПАУЭЛЛА

Слайд 11

МЕТОД КУБИЧЕСКОЙ ИНТЕРПОЛЯЦИИ
При решении реальных задач редко приходится иметь дело с

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

Слайд 12

КУБИЧЕСКАЯ ИНТЕРПОЛЯЦИЯ (МЕТОД ДЭВИДОНА) ЛОКАЛЬНАЯ ЗАМЕНА МИНИМИЗИРУЕМОЙ ФУНКЦИИ МНОГОЧЛЕНОМ ТРЕТЬЕЙ СТЕПЕНИ (ТРИ

ЧЛЕНА В РАЗЛОЖЕНИИ ТЕЙЛОРА) ИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН СТРОИТСЯ ПО ЗНАЧЕНИЯМ ФУНКЦИИ И ЕЕ ПРОИЗВОДНОЙ В ДВУХ ТОЧКАХ + ТРЕБУЕТСЯ ЗАДАНИЕ ПРИБЛИЗИТЕЛЬНОГО ЗНАЧЕНИЯ FMIN

Слайд 13

ЗАКЛЮЧЕНИЕ
Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии

минимизируемой функции.
Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj*grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj, где Dj - положительно определенная симметрическая матрица порядка n×n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.

Методы Флетчера-Ривса, Дэвидона-Флетчера-Пауэлла, Кубической интерполяции

Содержание

СОДЕРЖАНИЕМетод Флетчера-РивзаАлгоритм Дэвидона - Флетчера - ПауэллаМетод кубической интерполяции

МЕТОД ФЛЕТЧЕРА-РИВЗА

МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВФормирует направления поиска, в большей мере соответствующие геометрии минимизируемой

СТРАТЕГИЯ МЕТОДА ФЛЕТЧЕРА-РИВСА Состоит в построении последовательности точек {xk}, k=0, 1, 2,

СХОДИМОСТЬ МЕТОДАТеорема 1. Если квадратичная функция f(x) = (х, Нх) +