Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Методы сопряженных направлений




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Как и метод Ньютона, методы сопряженных направлений основаны на свойствах квадратичных функций. В связи с этим говорят о сопряженных направлениях относительно квадратичной функции. Пусть дана матрица Н n´n. Направления d1, d2, ..., dk (k £ n) называются сопряженными или Н-сопряженными, если они линейно независимы и .

Эти векторы определяют сопряженные направления. Для квадратичной функции двух переменных сопряженные направления получаются следующим образом. Возьмем произвольное направление d1 и на нем найдем минимум, двигаясь из точки X1. Повторим поиск минимума на d1 из точки X2¹ X1 . Направление d2, определяемое прямой, проходящей через найденные минимумы, является сопряженным с направлением d1. При этом направление d2 проходит через искомый минимум функции f. Следовательно, при любой начальной точке минимум квадратичной функции двух переменных достигается за два одномерных поиска вдоль сопряженных направлений.

Пример: Используя сопряженные направления, найти минимум функции (точка минимума X*=(2,4)). Запишем матрицу Гессе . Возьмем . . Пусть а = 1, получаем

b = 2 и . Возьмем начальную точку X0=(-1;1). Найдем минимум на направлении d1. Для этого подставим в функцию X = X0+hd1, то есть x1= x10+h = -1+ h, x2=x20=1. Тогда f = h2-3h-3 и минимум по h будет при h*=1,5. Следовательно, минимум наd1 достигается в точке X1=(0,5;1). Приняв ее за начальную для поиска вдоль d2 и подставляя в функцию x1= 0,5+ h, x2=1+2h, получаем f = 3h2-9h-5,25. Находим h*=1,5 и соответствующую новую точку X2=(2;4). Как видим, второй одномерный поиск привел в точку искомого минимума f .

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

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

Методы Пауэла, Флетчера-Ривса, Девидона-Флетчера-Пауэла
43. Методы случайного поиска.

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

Случайный механизм выбора направления реализуется с помощью датчика случайных чисел b, равномерно распределенных на интервале [-b, b]. Направление задается случайным вектором X = (x1, x2, x3, ..., xn), компоненты которого вычисляются по формуле:

,где n случайных чисел bi генерируются датчиком. Такой случайный вектор имеет единичную длину и определяет только направление. При этом все направления равновероятны.

Приведем несколько простых алгоритмов случайного поиска.







Дата добавления: 2015-04-19; просмотров: 705. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.017 сек.) русская версия | украинская версия