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

⇐ ПредыдущаяСтр 4 из 5Следующая ⇒

Все рассмотренные в предыдущих разделах методы поиска основываются на предположениях об унимодальности и в ряде случаев о непрерывности исследуемой целевой функции. Целесообразно предположить, что если в дополнение к условию непрерывности ввести требование дифференцируемости функции, то эффективность поисковых процедур можно существенно повысить. Напомним, что в разд. 2.2 установлено необходимое условие существования локального минимума функции в некоторой точке z, согласно которому первая производная функции в точке zдолжна обращаться в нуль, т. е. f '(z)=df/dx|_x₌₂=0.

Если функция f(x) содержит члены, включающие х в третьей и более высоких степенях, то непосредственное получение аналитического решения уравнения f'(x)=0может оказаться затруднительным. В таких случаях используются приближенные методы последовательного поиска стационарной точки функции f. Прежде всего опишем классическую поисковую схему, ориентированную на нахождение корня нелинейного уравнения. Эта схема была разработана Ньютоном и позднее уточнена Рафсоном [5].

Метод Ньютона — Рафсона

В рамках схемы Ньютона — Рафсона предполагается, что функция f дважды дифференцируема. Работа алгоритма начинается в точке x₁, которая представляет начальное приближение (или начальную оценку) координаты стационарной точки, или корня уравнения f '(x)=0Затем строится линейная аппроксимация функции f'(x) в точке x₁, и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего

приближения. Если точка x_k принята в качестве текущего приближения к стационарной точке, то линейная функция, аппроксимирующая функцию f '(x) в точке x_k, записывается в виде

Приравняв правую часть уравнения (2.7) нулю, получим следующее приближение:

Рис. 2.14 иллюстрирует основные шаги реализации метода Ньютона. К сожалению, в зависимости от выбора начальной точки и вида функции алгоритм может как сходиться к истинной стационарной точке, так и расходиться, что отражено на рис. 2.15. Если начальная точка расположена правее х₀, то получаемые в результате последовательных приближений точки удаляются от стационарной точки z.

Пример 2.10. Метод Ньютона — Рафсона

Рассмотрим следующую задачу:

минимизировать f(x)=2х²+(16/х).

Для того чтобы определить стационарную точку функции f(x), воспользуемся методом Ньютона — Рафсона, положив x₁=l:

Итерации продолжаются до тех пор, пока не будет выполняться неравенство |f'(x_k )| < e, где e — заранее установленная величина допустимого отклонения.

Метод средней точки

Если функция f(x) унимодальна в заданном интервале поиска, то точкой оптимума является точка, в которой f '(х)=0. Если при этом имеется возможность вычислять как значения функции, так и ее производной, то для нахождения корня уравнения f '(х)=0 можно воспользоваться эффективным алгоритмом исключения интервалов, на каждой итерации которого рассматривается лишь одна пробная точка. Например, если в точке z выполняется неравенство f '(z)< 0, то с учетом предположения об унимодальности естественно утверждать, что точка минимума не может находиться левее точки z. Другими словами, интервал х≤ z подлежит исключению. С другой стороны, если f '(z)> 0, то точка минимума не может находиться правее z и интервал x≥ z можно исключить. Приведенные рассуждения лежат в основе логической структуры метода средней точки, который иногда называют поиском Больцано.

Определим две точки L и R таким образом, что f '(L)< 0 и f '(R)> 0. Стационарная точка расположена между L и R. Вычислим значение производной функции в средней точке рассматриваемого интервала z=(L+R)/2. Если f '(z)> 0, то интервал (z, R)-можно исключить из интервала поиска. С другой стороны, если f '(z)< 0, то можно исключить интервал (L, z). Ниже дается формализованное описание шагов алгоритма.

Пусть имеется ограниченный интервал а≤ х≤ b и задан параметр сходимости e.

Шаг 1. Положить R=b, L=a; при этом f '(а)< 0 и f '(b)> 0.

Ш а г 2. Вычислить z=(R+L)/2и f '(z).

Ш а г 3. Если |f '(z)|≤ e, закончить поиск. В противном случае, если f '(z)< 0, положить L=z и перейти к шагу 2. Если f '(z)> 0, положить R=z и перейти к шагу 2.

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

Метод секущих

Метод секущих, являющийся комбинацией метода Ньютона и общей схемы исключения интервалов, ориентирован на нахождение корня уравнения f '(x)=0в интервале (а, b), если, разумеется, такой корень существует.

Предположим, что в процессе поиска стационарной точки функции f(x) в интервале (а, b) обнаружены две точки L и R, в которых знаки производной различны. В этом случае алгоритм метода секущих позволяет аппроксимировать функцию f '(x) «секущей прямой» (прямой линией, соединяющей две точки) и найти точку, в которой секущая графика f '(x) пересекает ось абсцисс (рис. 2.16). Таким образом, следующее приближение к стационарной точке х* определяется по формуле

Если |f(z)|≤ e, поиск следует закончить. В противном случае необходимо выбрать одну из точек L или R таким образом, чтобы знаки производной в этой точке и точке z были различны, а затем повторить основной шаг алгоритма. Например, в ситуации, изображенной на рис. 2.16, в качестве двух следующих точек должны быть выбраны точки z и R. Легко видеть, что в отличие от метода средней точки метод секущих основан на исследовании не только знака, но и значений производной в пробных точках и поэтому в ряде случаев позволяет исключить более половины интервала поиска (см. рис. 2.16).

Пример 2.11. Метод секущих

Опять рассмотрим задачу из примера 2.10:

минимизировать f(x)=2x²+(16/x) в интервале 1≤ х≤ 5.

Шаг 3. f '(z)=3, 51> 0; положить R = 1, 94. Итерации продолжаются до тех пор, пока не будет выполняться неравенство |f(z)|≤ e.

⇐ Предыдущая 1 2 345 Следующая ⇒