Поваляев А.А. Спутниковые радионавигационные системы (2008) (1151867), страница 45
Текст из файла (страница 45)
Для точек, лежащих внутри эллипсоида, значение квадратичной формы будет меньшее д, а для точек вне эллипсоида ее значение будет большее д. Если нас интересует только один целочисленный минимум квадратичной формы КЧР(к) (5.19), то геометрически такая задача формулируется как нахождение эллипсоида минимального размера (с минимальным значением константы д в уравнении (А.1)), на поверхности которого будет располагаться единственная точка с целочисленными координатами (ТЦК) при отсутствии таковых внутри эллипсоида. В примере на 24В Приложения рис. А.! эта точка имеет координаты Е, = О, й, = 2. При необходимости найти несколько например, и последовательно нарастающих целочисленных минимумов квадратичной формы КЧР(к) (5.19), необходимо найти эллипсоид минимального размера, внутри либо на поверхности которого располагается и ТЦК.
Рассортировав эти ТЦК в порядке нарастания соответствующих им значений квадратичной формы КЧР(к) (5.19), получим список последовательно нарастающих минимумов квадратичной формы КЧГ(й) (5.19). При всей геометрической простоте задачи, ее реализация наталкивается на огромные вычислительные трудности. Дело в том, что в практически интересных случаях матрица !3 квадратичной формы КЧР(к) (5.19) обычно является очень плохо обусловленной. Отношение ее минимального и максимального собственных чисел может доходить до нескольких десятков тысяч.
Зто порождает сильную вытянутость (или сплюснутость) эллипсоида (А.1). В результате поиск ТЦК, находящихся внутри либо па поверхности эллипсоида (А.1), при размерностях ц> -5 превращается в задачу, непосильную даже для современных мощных компьютеров. Вычислительная нагрузка может быть резко уменьшена при использовании так называемого линейного целочисленного унимодулярного преобразования (ЦУМП).
Идея этого преобразования заключается в таком взаимно-однозначном отображении исходной целочисленной решетки в другую, так же целочисленную, решетку, при котором эллипсоид (А,! ) преобразуется в фигуру, близкую к шару. Пример такого преобразования эллипсоида, показанного на рис. А.1, представлен на рис. А.2. Действительные координаты (г,, )г, центра эллипса, показан- ного на рнс.
А.1, преобразуются в действительные координаты ш',, ш~ центра эллипса, показанного на рис. А.2: ТЦК к, = О, )с, = 2 переходит в ТЦК пй =4, пз, =3; ТЦК (с, =9, (г, =3 переходит в ТЦК ш, =5, ш, = 4; ТЦК и, =1, (с, = 2 переходит в ТЦК ш, = 5, ш, = 3. Преобразование исходного эллипсоида в фигуру, близкую к шару, означает, что матрица преобразованного эллипсоида должна быть близка к диагональной, при этом сами диагональные элементы должны быть близкими друг к другу. Изменение формы эллипсоида приводит к резкому сокращению вычислительных расходов на поиск ТЦК, расположенных внутри и на его границе. При необходимости найти только один минимум квадратичной формы такой поиск часто может быть осуществлен при помощи простого округления координат центра преобразован- 249 Спупишкааые радиаиааигалиаииые системы ного эллипсоида до ближайших целых чисел. После нахождения ТЦК, лежащих внутри преобразованного эллипсоида, над векторами их координат осуществляется обратное ЦУМП, в результате чего находятся ТЦК, лежащие внутри исходного эллипсоида.
Рис. А.2. Унимодулярное преобразование эллипсоида, представленною парис. А.! Для использования изложенного выше подхода необходимо иметь способ вычисления матрицы ЦУМП. Задача вычисления матрицы этого преобразования может быть сформулирована в терминах математической теории решетчатых упаковок !59, 60) как задача приведения решетки к совокупности ее базисных векторов наиболее близких к ортогональным.
При этом исходными базисными векторами решетки принимаются столбцы верхней треугольной матрицы ВВ~ разложения Холецкого матрицы О, входящей в (А.1): (А.2) 0 =ВВ ВВ Алгоритм вычисления разложения Холецкого описан в Приложении В. Готовая процедура на языке С вычисления нижнетреугольной матрицы этого разложения может быть заимствована из 1611. Вектор-столбцы матрицы ВВ' задают решетку, которая получается как линейная комбинация этих векторов при произвольных целочисленных коэффициентах. Рассматриваемая решетка может задаваться множеством наборов других базисных векторов.
Все наборы связаны между собою преобразованием ВК~13, где 1) — матрица унимодулярного преобразования с целочисленными элементами и определителем, равным 1! . Смысл задачи приведения заключается в нахождении возможно более ортогональиых базисных векторов решетки, порождаемых матрицей ВВ~, и вычислении унимодулярной матрицы 1), связывающей исходные и наиболее ортогональные базисные вектора. 250 Приложеяия Строгое решение задачи приведения в теории решетчатых упаковок не найдено.
Однако в настоящее время известны три итерационных алгоритма [62 — 64], использование которых позволяет найти базисные векторы, достаточно близкие к наиболее ортогональным. Исследования, проведенные в [65], показали, что лучшим из них является Ш. алгоритм [64].
Его описание приведено в приложении С. Впервые использование ЦУМП для разрешении неоднозначности было описано в кандидатской диссертации автора данной монографии (!972 г.). Столбцы матрицы обратного ЦУМП образовывались как векторы так называемого Х-сторонника Эрмита [66]. Геометрически этот Х-сторонник представляет собою совокупность Х ненулевых линейно-независимых векторов и, с цело- численными элементами, доставляющих последовательно нарастающие значения минимумов квадратичной форме К~В,„й„. Вычислительные расходы для поиска Х-сторонника Эрмита были огромными. Так, например, вычисление этого Х-сторонника для мерности й = !5 занимало примерно двое суток счета на лучшей для того времени вычислительной машине БЭСМ-б. Столь огромные вычислительные расходы являлись вполне оправданными, поскольку результат использовался для разрешения неоднозначности измерений фазового пеленгатора, взаимное расположение антенн которого было фиксированным.
Поэтому, осуществив одни раз вычисление лзатрицы ЦУМП, можно было далее без изменений использовать ее многократно для эффективного разрешения неоднозначности. В СРНС, где взаимное положение приемника и спутников постоянно изменяется, такой подход, очевидно, неприемлем. Применение Ш. алгоритма для вычисления матрицы ЦУМП впервые было описано в [28]. Там же была продемонстрирована высокая эффективгюсть использования матрицы ЦУМП для разрешения неоднозначности, а также возможность вычисления этой матрицы в реальном масштабе времени.
Идея использования ЦУМП для разрешения неоднозначности была, по всей видимости, независимо, предложена так же в [67]. Несколько позже появилось описание способов вычисления матрицы ЦУМП на основе Ш. алгоритма [68, 69]. Автор работы [67] назвал метод разрешения неоднозначности, основанный на использовании ЦУМП, ЕАМВРА-методом (Ееаз! Боцагез АшЬ!Бц!!у Ресогге!айоп Аг!]аз!ше!з!). Это название получило в настоящее время широкое распространение за рубежом.
Из всего ранее сказанного следует, что общий алгоритм вычисления одного либо нескольких последовательно нарастающих целочис.,т ленных минимумов квадратичной формы КЧЕ(й) = [й - к ) х хР,„(й — й') (5.19) состоит из трех этапов. Э т а п 1 . Осуществляется разложение Холецкого Р„= ВК ВВ~ матрицы исходной квадратичной формы и решается за- 261 Снттоининые родионаеигочионные системы дача приведения исходных базисных векторов решетки, порождаемой матрицей ВКт, к наиболее ортогональным базисным векторам той же решетки. Задача приведения решается с помощью (.11.
алгоритма, описанного в Приложении С. В процессе ее решения находится матрица Рм преобразованной квадратичной формы, соответствующей наиболее ортогональным базисным векторам, вычисляются вектор ш' пересчитанных координат центра эллипсоида и целочисленная унимодулярная матрица 13 для возврата к исходным базисным векторам. Э т а л 2 . Осуществляется поиск заданного числа и целочисленных векторов ш; 1 = 1, и, доставляющих последовательно нарастающие значения минимумов квадратичной форме: ( -щ') Р,„(щ- ). (А.З) Алгоритм вычисления и последовательно нарастающих целочисленных минимумов положительно определенной квадратичной формы описан в Приложении О. Э т а п 3 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
