Методы поиска

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

Как показал исследования Д.Химмельблау [89], методы по­иска особенно эффективны в заключительной стадии минимизации, то есть тогда, когда градиентные методы „требуют повышенную точность вычисления производных и сходятся сравнительно мед­ленно.

Таблица 2.1.

Средние из 200 расхождений координат (линейная засечка)

Таблица 2.2.

Средние из 200 расхождений координат (прямая засечка)

Среди широкого класса методов прямого поиска наиболь­шее применение для решения систем нелинейных уравнений полу­чили методы покоординатной минимизации (Гаусса-Зейделя) [3], Хука и Дживса [37, 103], поиска по деформированному многогран­нику [103], метод Пауэлла [39, 86, 81, 83, 105] и др.

Самым трудоемким в вычислительном отношении является ме­тод слепого поиска, примененный для геодезических вычислений Г.М.Гринбергом [25].

При минимизации целевой функции слепым поиском используют регулярную сетку. Поместим центр этой сетки в точку с коорди­натами, равными среднему арифметическому из координат исход­ных пунктов. По ним также можно предсказать и шаг сетки l, но лучше его задавать заранее через S_ср./3, используя до­полнительную информацию о длинах сторон всей геодезической сети. Опыт показывает, что при двух определяемых пунктах l = S_ср./5, а для трех пунктов l = S_ср./3 при числе узлов 10 ´ 10 = 100. В этих случаях сеткой будут накрыты все возможные местоположения определяемых пунктов, а координаты будут найдены с точностью, позволяющей их дальнейшее уточнение другими методами нелинейного программирования, изложенными во второй главе. Для случая двух определяемых пунктов цель вычис­лений заключается в том, чтобы найти такие два узла сетки, для которых значение целевой функции будет минимальным. Для случая трех определяемых пунктов отыскиваются аналогично во всех воз­можных комбинациях три узла сетки. Для пространственной засечки двух пунктов сетка пространственная и будет содержать 10 ´ 10 ´ 10 = 1000 узлов.