автореферат диссертации по геодезии, 05.24.01, диссертация на тему:Сравнительный анализ различных методов решения систем нормальных уравнений при уравнивании больших астрономо-геодезических сетей

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА ИНСТИТУТ ИНЖЕНЕРОВ ГЕОДЕЗИИ, АЭРОФОТОСЪЕМКИ И КАРТОГРАФИИ

на нравах рукописи

РОДКН ИГОРЬ ИВАНОВИЧ

уда 528.

СРАВНИТЕЛЬНЫ!! АНШЗ РАЗЛИЧНЫХ МЕТОДОВ РЕШЕНИЯ састви НОРМАЛЬНЫХ УРАВНЕНИЙ ПРИ УРАВИИНМНИ БОЛЬШИХ ЛСТРОНО&О-ГЕОДВЗИЧЕСШХ СЕТЕЙ

Специальность 05.24.01 - Геодезия.

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических нал?

Москва, 1992

Работа выполнена в Центральном ордена "Знак почета" научно-исследовательском института геодезии, аэрофотосъемки и картографии имени Ф. Н. басовского /ЩШИГАиК/ и Московском ордена Трудового Красного Знамени аэрогеодезическом предприятии /МАГП/.

Научный руководитель - кандидат технических наук М. В. Цульмин

Официальные оппоненты:

доктор технических наук, профессор КХ И. Маркуэе

кандидат технических наук А. П. Герасимов

Ведутая органиэашя указана в решении специализированного совета.

Защита диссертации состоится а- 1992 г.

в чесов на заседании специализированного совета в

Московском институте инженеров геодезии, аэрофотосъемки и картографии по адресу; ^/мк^^г^ 4

С диссертацией можно ознакомиться в библиотеке МИИГАиК.

Автореферат разослан л^о^а. 5992 г.

Ученый согсретарь

специализированного

совета

к. т. н. В. А. Монахов

Ойдая характеристик работы.

Актуальность работу.

Современное развитие науки и техники неразрывно связано с производством. Широкое использование больших и малых ЭВМ делает все процессы работ автоматизированными, что позволяет широко применять новуя технологию, основанную на последних научных достижениях, иначе сокращаются сроки внедрения, результатов теоретических исследований и технических разработок в производство. С другой стороны, любой раздел науки, как фундаментальный, так и прикладной, при дальнейшем углублении требует обширной информационной базы, которую наиболее полно обеспечивает рассмотрение решения текущих производственных вадач. Эго в полной мере относится к такому крупному разделу вычислительной геодезии - уравнивания астрономо-геодезической сети (АТС) СССР, так как в этом случае нудно обрабатывать очень больной объем информации.

Б комплексе проблем, связанных с уравниванием АГС выделяются те, которые связаны с процессом решения систем нормальных уравнений. Порядок системы при уравнивании АГС СССР достигает более 300000 неизвестных. При атом приходится сталкиваться не только с большими денежными затрата«!, ко и с фактом наличия определенных расхождений меяду результатам!!, получаемыми после решения такой крупкой систему различными методами. Б этом контексте актуально то, что при современном

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

Цель работы.

Исследовать на реальном практическом материале возможные расхождения между результатами решения систем нормальных уравнений при уравнивании АТС с применением метода квадратного корня и метода сопряженных градиентов,как наиболее- оптимальных в использовании ресурсов ЭВМ.

Выполнить углубленный анализ характера течения процесса построения сопряженных градиентов при уравнивании АГС различной конфигурации.

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

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

Научная новизна.

Теоретически обосновано влияние степени ортогональности матрицы решаемой системы .на результат», получаемые по методу сопряжнных градиентов; показан процесс ззтухаяия ускорения по методу сопрялекных градиентов при накоплении ошйок округления пр.ч различной обусловленности решаемых систем, что привело 1: созданию методики, регламентирующей использование метода сопряй&ниых градиентов при уравнивании АТС.

Выполнено исследование с целью выбора оптимального вида нумерации системы и доказывается, что профильная нумерация в едином блоке обеспечиёает получение наиболее достоверных результатов при решения методом квадратного корпя:

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

Практическая ценность работы.

Экспериментально апробирована методика слежения за ходом решения системы по методу сопряженных градиентов с целью фиксирования отступления от нормального развития процесса.

Создан пакет программ, реализующий предлагаемую методику решения системы методом квадратного корня, который'совместим с комплексом программ уравнивания АГС, функционирую-

ним x¡ UAi'í] и применяется на производстве.

Выполнено полигональное уравнивание АТС СССР с использованием метода квадратного корня.

Реализация работы.

Все исследования в рамках диссертационной работы проводились в Московском аэрогеодезическом предприятии (ИАГП) Главного управления геодезии и картографии. Практические результаты были внедрены в производство а виде:

- рекомендаций по применению метода сопряяшньа градиентов;

- пакета программ уравнивания АТС с применением метода квадратного корня при решении систем в едином блоке.

Апробация работы.

Основнь» результаты работы докладывались isa научно-технической совете ЫАГП в 1990 и 1992 годах.

Публикации.

Результаты исследований опубликованы в двух статьях. Структура и обгви диссертации.

Диссертационная работа состоит из введения, трех глав, вакдючеиия, списка литературы, приложения и справки о внедре-

ник. Диссертация содержит 131 страницу машинописного текста, г .том числе 20 рисунков и 6 таблиц. Список литературы содержит 63 наименования. В приложении даны тексты пакета программ.

Основное содержание работы

Во введении обосновывается актуальность темы, сформули роваиы цели и направления исследования.

Первая глава " Исследование метода сопряженных градиентов при уравнивании ЛГС " описывает проблемы, вознигаше при решении больших систем нормальных уравнений с применением данного метода и даст оценку возможности зго использования.

Применение метода оопряяэнкьк градиентов (Си-метода) обусловлено его небольшим» потребностями к ресурсам памяти ЭВМ и простотой алгоритма, что отвечало имеющимся производственным мощностям на рубеж? гсоода 70-;; - начала 80-я годов. Основным его недостатком явилась зависимость скорости вычислений от обмена данныш меиду внешним запоминающим устройством и оперативной памятью ЭШ, но для решения систем до 20000 неизвестных б тех условчяХ это не имело особого вкачения, поэтому метод широко применялся на производстве.

Опыт использования СО-метода показал, что дл< различных сетей характерна разп&ч скорость сходимости. Если принять за основу теоретически [ 4 ] необходимое число шагоЕ, равное числу неизвестных, то изменение происходит от половины необходимого числа длп сплошных сетей до утроенного числа для разрешенных. Кроме того, при наличии в АГС конфигурации час-

гнчно отличной от оплошкой сети треугольников появляются расхождения мааду результатами решения системы по Ш-методу и методу квадратного корня. Оля составляют 2 см на 1000 пунктов; то есть на 2000 неизвестных и возрастают с увеличением порядка решаемой систеш. Так ке С8-иетод не отражает (сглаживает), локальные искажения в геометрии АТС; Встал вопрос углубленного исследования СО-метода.

Исходя из зависимости градиентных процессов релаксации от свойств матрицы А и от начального приближения I 2 1 а если рассматривать 03-метод как З-шаговый градиентный процесс, то юмко предположить, что он но является универсальнш в смысле полного и окончательного построения процесса итераций для широкого класса матриц, в случае уравнивания АТС - симметричных матриц. Налицо зависимость достижения решения не только от обусловленности матрицы, но и от ее специфических свойств, а конкретно от возможности построения системы ортогональных векторов в выбранной метрике. Представим формулы СЕ-метода [ 2,4. 3: Хо = 0 ; 30 = Ь ;

Ъ« = ъ - сц ;

а такмэ одно вытекающее из них соотношение:

Характер изменения коэффициентов "а", "Ь" выбран, кп-' критерий оценки специфических свойств матрицы решаемой систч мы,расхождение между скалярными произведениям и (ЗД) представляет исчерпывающую информацию о накоплении ошибок округления в ходе 08- процесса. Из многочисленной практики. выделятся три основные схемы хода решения в зависимости от поведения коэффициентов "а" и "Ь" и от связанного с этим рос та ошибок округления. Резкие изменения "а" и "Ь" соответствуют экстремальному случаю, равномерные, изменения - нормаль ному и незначителыше-затухавдему. Соответственно это происхо дит при уразииаашш сетей: несплошюй и сплошной конфигурации и сетей смешанной конфигурации, большого объема, при наличии олабсЬбусловленной матрицы системы нормальных уравнений. Та-цим обраоом, ' ход С(3-процесса -зависит от степени ортогональности матрицы. Статистика углов между строкам! матрицы показывает, что при нормальном течении решения, число углов, близких к прямы?! вдвое больше, чем при экстремальном'случае.

Показано, что резкие изменения коэффициентов "а" и "Ь" нр:шодят к росту ошибок округления и резкому увеличении количества необходимых итераций. Кроме того, подтверждается ияедувдее:

УСЛОБЖ: Степень ортогональности матрицы влияет т охотатгяьные результаты ¡зияния по кэтоду сопряженных градиентов.

Подтверждение строится на выводе взаимосвязи коэффициентов "а" и "Ь" на текущем гсаге решения,га чего вытекает,что возможна релаксация функции ошибок, независимо от уменьшения

ьектора невяакк. При этом значение коэффициента "а" после завершения решения характеризует полученные результата Если а < 1, то достигается точное решение, если а > 1, то имеется приближенное решение по принципу минимума квадратов невязок.

Рассмотрение случая затухающего хода решения основано на анализе накопления сшибок округления в СБ-методе,, который опирается па соблюдение равенства мевду скалярными произведениями (3,1.) и (1Л). Показано, что это условие зависит от обращения в ноль частных (^р^у Проведением взаимосвязи между п -мерным пространством, которое создается р. ходе СО-процесса, и построением ортогональных полиномов, доказивается, что накопление ошибок округления зависит от характера изменения коэффициента "а". Несоблюдение указанного условия приводит к неполной релаксации функции ошибок. Или, если ССЬ метод представить как соответствующее ускорение стационарного итерационного метода [ 3 ], то происходит затухание ускорения и решение ведется по-существу итерационным методом.

В таком случае модно говорить о неполной'универсальности эффективного и строгого применения СО-метода. Предполагаемые .процессы слежения за изменением коэффициентов "а" и "Ь", а также за соблюдением равенства (3,1.) и ) органи-вуюи методику, регламентирующую использовали» СО-метода, который позволяет в ходе и в конце решения планировать возможность постижения достоверных результатов и затраты на вычислительный процесс.

Основные недостатки С(3~метода: уменьшение скорости вычислений с увеличением объема матричной системы, неотраление локальных искажений геодезической сети и зависимость проц^с-

са решения от степени ортогональности матрицы, приводя-; к. необходимости обратиться к использованию прямых методов решения, так как увеличивающаяся мощность современных ЭВМ позволяет добиться эффективного их применения.

Вторая глава " К использованию метода кгадратного корня при уравнивании АТС " обосновывает требования к эффективному и строгому применению методов решения систем нормальных уравнений при уравнивании АТС, выдвигается метод квадратного корня, как наиболее эффективный в данном случае, и доказывается, что предлагаемый подход ь его реализации, обеспечивает получение наиболее достоверных результатов.

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

- метод долаен обеспечивать стабильный процесс решения, то есть, априорно долзгяа существовать уверенность в завершении процесса и надцый шаг решения долаен контролироваться-,

-.должен расходоваться минимум внешней памяти и алгоритм вычисления не должен зависеть от объемов доступной оперативной памяти ЭВМ;

- ход решения на долкэн накладывать «эстких ограничений на нумерацию АТС;

- обязательно применение определенных приемов масштабирования чисел, ка;: оредсгг.а борьбы с накоплением ошибок округления;

- методига применения выбранного метода должна характеризо-

ваться критерием, качественно определявшим процесс преобразования I хода решения), который служил бы теоретически или его соблюдение практически явилось Сы фактором достоверности получаемых результатов;

должна обеспечиваться строгая апостериорная оценка точности уравниваемых величин;

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

Исходя из приведенных требований, анализируется возмоя- . нссть применения оптимальных методов и делается вывод, что наиболее обоснованным является применение метода квадратного корня (ТТт -метод). При этом показывается полная строгость получения симметричной матричной системы при уравнивании реальных АТС параметрическим способом. Указывается, что уравнивание с применением ТТт-метода выгоднее проводить по углам ( в случае проведения такого уравнивания ) , так как сокращается наполненность матричной системы, в отличие от СО -метода, где требование наличия матриц*., близкой к ортогональной приводит к необходимости уравнивания по измеренным величинам, по направлениям. Выполнение требования насвтаби-

рования чисел в случае ТТт-метода сводится к применению од ной диагональной матрицы - масштабного мнолитзля. Таким образом, при использовании ТТт -метода необходимо хранение только одной преобразованной транспонированной треугольной матрицы (Т-матрицы), так как в хранении исходной матрицы нет необходимости. Это согласуется с оптимальным использованием рссурсоз в CG-мотоде,

При уравнивании ЛГС СССР параметрическим способом соз дастся разрешенная система уравнений, заполненность которой менее 1 %. В процессе факторизации происходит дальнейшее за лоляеиие системы, которое еависит от выбранной нумерации пунктов (неизвестных). Основным критерием при выборе систеш номеров является сведение к минимуму объема Т-матрицы. Наиболее приемлемы«« являются два подхода в нумерации: профильный (ркс. 1) и блочный С 1 Крис. 2), каздьЯ из которых дает свою методику реализации Т?т-метода.

Рис. 1

Рис. 2

В этом случае строгость применения Т1т-метода будет гави-ееть от выбора нумерации в системе. Для того, чтобы определить какой из двух подходов к нумерации наиболее строг с точки зрения получения достоверных результатов вводится определенный критерий, с помощью которого можно качественно охарактеризовать процесс преобразования в том и другом случае. Им является отступление от степени ортогональности б исходной матрице, связанное с появлением новых значащих коэффициентов в эквивалентной треугольной матрице в ходе преобразования. Подтверждается следугсщзе:

УСЛОВИЕ 1: Наиболее оптимальным является такое преобразование матричной сиотеш, при кото рои в эквивалентной патрице между строками (столбцами) степень ортогональности блинка той, которая оупрствовала к&хду аналогичными строками (столбцами) ясходюй матрицы. •

Подтверждение строятся на факте отклонения от известного' свойства нормальной системы п.

при получения преобразованной матрицы по Л-ТТ*» увеличении из-за неопгимальной нумерации числа вычитаемых в формулах

ТтУ - I, ТX - 7

Приводится практическое подтверядение условия 1.

УСЖВ'ьЖ 2 : В случае выполнения услссиъ/происходит иаиивнъшеч накопление ошибок округления.

Исходя из утверждения приведенного условия 1, доказывается что профильная методика нумерация в системе является наибо лее строгой с точки зрен;;я возможности получения достоверных результатов. Кроме этого, переход к профильной нумерации мс яет быть легга автоматизирован, а зто снимает ограничение нг. нукерациы АТС; при блочном подходе это труднсосущзствимо.

Третьи гжя& " Реализация иетода квадратного корня при решенкн систем в едином блоке " описывает приемы наиболее оптимальной практической реализации метода квадратного корни при профильной методит« нумерации в системе. Глава основан» ни рассмотрении пакета программ уравнивания АТС с применением метода квадратного корня в едином блоке, который создан по предлагаемой методике :: совместим с комплексом программ уравнивания АТС бодьвюй протяженности, функционирующим в МАГП. Глава состоит Из пяти разделов: перспективы создания пакета программ, алгоритм составлении и решения систем нормальных уравнения и оценка точности уравненных величин, описание программ, методика применения и сравнительный анализ.

Основные условия, обеспечивающие оптимальность подхода данной реализации П1 -метода:

1) нет необходимости задания определенных условий на исходную нумерацию АТС, переход от нумерации в сети к профильной нумерации в системе осуществляется автоматически по связям пунктов (Неизвестных);

<■) группирующиеся по профильной методике связи текущего неизвестного с другими адекватны аналогичным связям пунктов АГС, что дает возможность пересечь появлящиеся несоответствия в геометрии сети с получением особенной Т-матрицы, собственные числа которой■укажут на имевшиеся искажения;

3) факт необходимости для преобразования нормальных уравнений текущего пункта толь ¡со части Т-матрицы. позволяет исправлять ошибки в АГС без повторения решения.всей системы;

4) возможность размещения з оперативной памяти ЭВМ треугольника необходимой для преобразования информации позволяет поставить скорость решения системы в зависимость только от мощности процессора ЭВМ;

5) возможно хранение Т-матрицы в упакованной виде, что вдвое сократит потребности в ресурсах внешней памяти ЭВМ.

Алгоритм программы, выполняющей прямой ход решения, предполагает следующую последовательность операций. При обработке текущего пункта составляется пара нормальных уравнений, затем в ник производится переход к профильной нумерации, ооуааэствдлется шаг факторизации с разложением нормальные уравнений в пару столбцов и сбросом их на внешний носитель. Затем программа переходит к следующему пункту и так далее. Все операции выполняются с удвоенной точностью. Преобразование ведется по столбцам по формулам, вытекающим из уравнения А - ТТт. Как уле отмечалось, для преобразования уравнений текущего пункта необходима часть Т-матрицы, которая описывается треугольником с рис.1), условно отмечающим в профиле коэффициенты, относящиеся к разнице номеров на текущий пункт. Наиболзе оптимальным, очевидно, станет такой ре-

преобразовал, когда вся необходимая информация будет расположена в оперативной памяти ЭВМ. Для достижения этой цел! применены принципы кскусстьекной (внутрнпрограмшюй) виртуализации памяти и генерации индексов, которые позволяют исключить зависимость пакета программ от ширины профиля и от модели ЭВМ, объема ее оперативной памяти.

После завершения прямого хода решения, ~ помощью другой программы выполняются оледуюпую этапы: обратный ход, подстановка неизвестных в систему, оценка точности уравненных величин. возврат в исходную "Систему нумерации и метрику. Оценка точности производится вычислением весовых коэффициентов путем получения диагонали обратной матрицы. Обращзние матрицы распадается на два'этапа, а начале получается обратная треугольная матрица ив ТТ'« Е, а затем суммы квадратов коэффициентов по соответствующим строкам даот элементы диагонали матрицу А"'. При такой последовательности вычислений возможно получение одних весовых коэффициентов, независимо от других, иначе порядок проведения оценки точности мокет быть любым. Для того, чтобы в момент получения матрицы Г обеспечивалось последовательное считывание Т-матрицы, также применены виртуализация памяти и генерация индексов. Это дает возможность иметь в оперативной, памяти координаты каздого элемента вычисляемых текущих строк матрицы Т~' без хранения незначащих нулевых симметричных коэффициентов. 3 этом случае создается независимость программы от модели ЭВМ, объема ее оператигной памяти и скорость вычислений заьисит только от мощности процессора.

В основу методики применения пакета программ полотен

тот факт, что в процессе текущего преобразования при выполнении прямого хода решс-кия необходима только часть Т-матри-цы, которая считается активной, а остальная часть считается пассивной и может храниться в виде архива Применяемая метрика в системе делает - масштаб чисел по модулю не большим единицы и меньшим лишь на порядок. Тогда Т-матрица может храниться в архиве упакованной, в виде целых чисел, что сократит ее объем вдвое и никак не отразится на точности выполнения обратного хода и вычисления весовых коэффициентов. Кроме того, есть возможность выполнять обратный ход с имеющимся объемом Т-матрицы и продолжать решение далее. Контрольная точка создается через указываема промежуток временя. Таким образом, можно периодически получать промежуточные результаты уравнивания и исправлять ошибки в ходе ранения, не начиная все решение сначала Это характеризует приводимую методику, как самостоятельный подход к уравниванию ЛГС.

Шиболее эффективное применение пакета программ имело ыесто при полигональном уравнивании по измеренным элементам, которое объединило 31000 пунктов, то есть решалась система из 62000 нормальных уравнений. Были получены основные характеристики факторизация: обрабатывалось 5 пунктов в минуту на ЕС-1061 и на один пункт требовалось 7 КБ внешней памяти (без упаковки). В то рремя как применение метода сопряазнннх градиентов не дало окончательных результатов, так как решение развивалось по вегухаяизй схемэ хода реяанмп.

ЗАКЛЮЧЕНИЕ

Основные результаты диссертации заключаются в следующем:

1. Теоретически обоснована и экспериментально подтверждена зависимость метода солрпжшм: градиентов от степени ортогональности матрицы системы нормальных уравнений.

2. Разработана методика, регламентирующая применение ме ■года сопряженных градиентов при решении больших систем при уравнивании АГС.

3. Предложены основные требования к методу решения к его реализации при решении систем высокого порядка, Утверждается, что применение метода квадратного корня при уравнивании АГС является наиболее целесообразным.

4. Доказывается, что профильная нумерация в едином блоке обеспечивает получение неибо^ее достоверных результатов решения при уравнивании АГС.

5. Создан пакет программ и предложена методика его применения, основанные на реализации метода квадратного корня при профильной нумерации в едином блоке, что может быть охарактеризовано как самостоятельный подход к уравниванию АГС. Его применение обеспечивает получение достоверных результатов с наименьшими затратами.

Осиовниэ положения диссертации ощ'бхлкоааны в с ¿едущих работах:

1. Родик И. И. К использованию метода квадратного корня при уравнивании АТС. Геодезия и картографии, N 11, 1989.

2. Родин Л И. Исслодозание метода сопряженных градиентов при уравнивании ЛГС. Геодезия я картография, N 4, 1691.

ЛИТЕРАТУРА

1. Пранио-Щшевич И. Ю. Руководство по уравнительным вычис деииям триангуляции. Геодевиадат, М. ,1956.

2. Фаддеев Д. К. .Заддеева Е IL Вычислительные методы линейной алгебры. II -Л. , Яи8Матгив,19бЗ

3. Хейгман JL , Янг Д Накладные итерационное методы. М. .Мир, 1986.

4. Hestenes,M.R. , and Stiefel,EL. 119521. Mathods of conjugate gradients for solving linear systems. Nat. Bur. Std. J. Res. 49. 409-436

Ротапринт ЗШШэнергопрси

зак. Jf 477, тир. ПО экз.