Методы одномерного поиска

Разобьем и вычислим значение функции в каждой точке.

искомый минимум

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

Интервал неопределенности — интервал, в котором заведомо находится точка минимума. Наиболее эффективное разбиение — двумя точками на 3 равных отрезка.

• 1)
• 2)

— после выполнения n шагов сокращение исходного интервала.

— точность с которой надо найти решение задачи.

N=2n, где n — число шагов, N — число вычислений (мера эффективности данного решения).

Метод золотого сечения Точки должны быть расположены на равном расстоянии.

;; ;

; - золотое сечение.

а.

— величина сокращения на каждом шаге.

число итераций растет как логарифм функции.

Одномерная оптимизация с использованием производных

. Пусть целевая функция дифференцируема .

точка локального минимума точка локального максимума Деление пополам Имеется хотя бы 1 корень. Выбираем любую точку и смотрим какой знак она имеет, такой знак нам и искать. Выбираем точку приблизительно в середине интервала, исследуя значения в 3-х можно отбросить половину интервала.

Метод Ньютона (метод касательной) В случае если известна производная, то выбираем — начальное приближение.

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

Для метода Ньютона необходимо:

• — функция должна иметь производную;
• — точка должна быть взята близко к корню;
• — функция изменяется близко к линейной функции.

;

— уравнение касательной;

.

Если, то вычисления можно прекратить и считать что нужный нам корень — условие прекращения поиска. (Е — значение корня с некоторой точностью).

В методе Ньютона каждя его итерация удваивает количество значащих цифр. Если все условия выполнены, то эти методы удваивают (ускоряют) количество значащих цифр:

;

Представим что линейная функция, то метод Ньютона позволяет найти ее корень за 1-у итерацию. Целевая функция представляет собой квадратичную зависимость следовательно метод Ньютона позволяет найти минимум или максимум квадратичной функции за 1-у итерацию.

Замена функции на касательную, называется — линейная аппроксимация, и ее применение к целевой функции парабола в точке приближения.

f (x)

Замена заданной зависимости квадратичной зависимостью, называется — квадратичной аппроксимацией. Метод Ньютона основан на замене заданной зависимости более простой зависимостью.