Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Градиентные методыСтр 1 из 6Следующая ⇒ ГЛАВА 2 ВЫЧИСЛЕНИЕ ПРЕДВАРИТЕЛЬНЫХ КООРДИНАТ ПУНКТОВ МЕТОДАМИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Методы нелинейного программирования, Используемые в геодезических вычислениях
Градиентные методы
При решении задач оптимизации применяют различные итерационные методы, обеспечивающие процесс минимизации целевой функции согласно неравенству , где j - номер приближения. Большой класс задач оптимизации успешно решается градиентными методами спуска, предусматривающими итерационный процесс
, lj > 0, (2.1) где lj - шаг минимизации в направлении, противоположном градиенту
, (2.2) Из-за сложной формы гиперповерхностей Ф(Х) = const направление, противоположное градиенту, в общем случае не ориентировано на точку минимума. Поэтому необходим итерационный прогресс. Градиентные методы поиска экстремума различаются в основном способом выбора шага lj, что предопределяет объем вычислений на каждой итерации. Требования к выбору шага минимизации имеют некоторые противоречия. Во-первых, шаги lj должны быть достаточно малыми, чтобы выполнялось неравенство (2.1) и вместо спуска не начался подъем. Во-вторых, если шаги окажутся слишком малыми, то резко возрастет объем вычислений и снизится эффективность используемого алгоритма. Поиск минимума с малым постоянным шагом выполняется градиентным методом, в котором после каждого шага заново определяется направление градиента и осуществляется следующий малый шаг. Графическая интерпретация метода градиента для двух переменных х1 и х2 дана на рис. 2.1, где изображены изолинии целевой функции и траектория спуска от начальной точки Р к точке минимума М. Рис. 2.1. Траектория минимизации методом градиента Минимизация целевой функции с использованием наибольшего возможного шага в направлении, противоположном градиенту, осуществляется методом скорейшего спуска. В зависимости от способа вычисления длины шага минимизации применяются различные модификации метода наискорейшего спуска. Классическим, но редко применяемым на практике, является способ, основанный на определений шага lj из уравнения
с использованием разложений целевой функции в ряд Тейлора. Наибольшее распространение на практике получили различные модификации метода наискорейшего спуска, основанные на одномерной минимизации критериальной функции в направлении скорейшего ее уменьшения. При этом применяются различные однопараметрические алгоритмы минимизации: метод золотого сечения, поиск Фибоначчи, метод квадратичных приближений и др. [103]. Последовательность минимизации целевой функции для случая двух переменных модифицированным методом спуска состоит в следующем. 1. Вычислим значение критериальной функции в начальной точке, которое обозначим . 2. Найдем частные производные и . 3. Вычислим длину шага минимизации по формуле , где квадрат евклидовой нормы градиента найдем из выражения
. 4. Определим координаты двух вспомогательных точек ;
и вычислим в этих точках значения целевой функции, обозначая их соответственно и 5. По величинам , , выполним квадратичную интерполяцию. В результате получим коэффициент
. Если , l удваивают, и повторяют вычисления с п.4, чтобы не допустить экстраполяции. Если , то находят новую длину шага . 6. Вычислим координаты точки для следующего приближения
; , и найдем в ней значение целевой функции. 7. Если , где e ¾ некоторое малое заранее заданное положительное число, то приближения прекращают. В противном случае, продолжают вычисления с п.1. Наиболее существенные осложнения при применении метода скорейшего спуска возникают тогда, когда процесс приближений выполняется в окрестности минимума. Здесь траектория минимизации начинает изменяться скачками, как показано на рис.2.2, что для достижения необходимой точности приводит к большому числу приближений. Рис. 2.2. Траектория минимизации по методу скорейшего спуска
Поэтому в ряде случаев целесообразно применять методы прямого поиска. Важным вопросом при использовании метода градиента является вычисление частных производных входящих в (2.2). Для этого применяют аналитические и численные методы. Первые из них более точные, но используются они при простом виде целевой функции. Так, в методе наименьших квадратов имеем [76] ; , где Р - веса результатов измерений; a и b коэффициенты уравнений поправок; l -свободные члены параметрических уравнений. Для более сложных целевых функций применяют следующие виды формул: ; (2.3) ; (2.4) ; (2.5)
где ; ; ; , а d ¾ малое приращение аргументу. Выбор правильного значения d входящего в формулы (2.3) - (2.5) зависит от следующих факторов: 1) от числа значащих цифр в разрядной сетке ЭВМ (n); 2) от числа целых чисел в переменной xi (Sср.); 3) от вида геодезических построений. Учитывая эти факторы, найдем эмпирическую формулу для вычисления d, входящего в (2.4) и (2.5). С этой целью применим метод статистических испытаний, сравнивая сгенерированные координаты с полученными их значениями при различных d, Среднее из 200 расхождений координат дня однократной линейной засечки представлены в табл.2.1, а для однократной прямой засечки ¾ в табл.2.2. По результатам вычислений получим формулу . (2.6) Величины расхождений для d, найденного по этой формуле, подчеркнуты в табл. 2.1 и 2.2.
|