Метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Отличается от метода дихотомии тем что отрезок делится не на пополам, а на большую и меньшую часть. Таким образом поиск происходит быстрей.
Метод Ньютона
Метод Ньютона- это итерационный численный метод нахождения корня (нуля) заданной функции. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить.
Математическое описание заданного метода.
Метод дихотомии.
Рассмотрим простейший однопараметрический метод безусловной оптимизации – метод дихотомии. Этот метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.
Дана функция F(x). Необходимо найти , доставляющий минимум (или максимум) функции F(x) на интервале [a,b] с заданной точностью , т.е. найти
Запишем словесный алгоритм метода.
1) На каждом шаге процесса поиска делим отрезок [a,b] пополам, x=(a+b)/2 - координата середины отрезка [a,b].
2) Вычисляем значение функции F(x) в окрестности вычисленной точки x, т.е.
3) Сравниваем F1 и F2 и отбрасываем одну из половинок отрезка [a,b] (рис.1).
При поиске минимума:
Если F1<F2, то отбрасываем отрезок [x,b], тогда b=x. (рис.1.а)
Иначе отбрасываем отрезок [a,x], тогда a=x. (рис.1.б)
При поиске максимума:
Если F1<F2, то отбрасываем отрезок [a,x], тогда a=x.
Иначе отбрасываем отрезок [x,b], тогда b=x.
4) Деление отрезка [a,b] продолжается, пока его длина не станет меньше заданной точности , т.е.
Рис.1.