Поваляев А.А. Спутниковые радионавигационные системы (2008) (1151867), страница 47
Текст из файла (страница 47)
Та же матрица Ч, будучи представлена в виде Ч = Ч"р(Ч) (где Ч" — матрица с ортогональными столбцами), будет содержать множитель р(Ч), удовлетворяющий ограничению (С.7). Введем замену переменных к=(/в, 1с'=1)в' в исходной квадратичной форме (5.19). Тогда для новых целочисленных переменных в квадратичная форма КЧг(к) (5.19) примет внд ((с — к ) 0в(й — )с*)=(1)в — $/в ) 0еч(()в — ив )= =(в-в') Ю~ВВ ВВ~(3(в-в*)=(в-в') ЧтЧ (в-в')= =( -в') и(Ч) (Ч') Ч"р(Ч) и(в- '). (С,9) Учитывая ортогональность столбцов матрицы Ч", получаем (Ч') Ч" =Йай(чо...,ч )=ч и 257 Си1 чниииовые роди оиавигалиоииые еноте и ы (" "') ~чч 11й й') =(ш — ш')" р(Ч) т П(Ч) (вп- ю'), (С.10) где элементы и,, 1= 1, о, диагональной матрицы т равны модулям век- тор-столбцов матрицы Ч" .
Из [С.10), с учетом того, что вектор столбцы матрицы Ч = ВВЪ образуют базис с наиболее короткими векторами; модули вектор- столбцов матрицы Ч" не превышают модулей соответствующих вектор-столбцов матрицы Ч; для любого наддиагонального элемента мат- 1 рицы п(ч) выполняется ограничение ~ри(ч)~< —, видим, что в новых 2 целочисленных переменных матрица р(Ч) е р(Ч) квадратичной формы будет более близкой к диагональному виду по сравнению с исходной матрицей В, .
Разумеется, что использование критерия (С.7) не может гарантировать отыскания абсолютного минимума функции Е(В) (С.5). Однако, как показывает моделирование, приведение в соответствии с [С.7) значительно улучшает обусловленность матрицы минимизируемой в целых числах квадратичной формы. Кроме того, достижение строгого минимума функции Г(В) не является абсолютно необходимым. Описанный в приложении О алгоритм минимизации квадратичной формы в целых числах успешно работает и в условиях, когда используемый базис решетки состоит из достаточно коротких векторов, не все из которых являются предельно короткими. ЬЬЬ алгоритм приведения, описанный в данном приложении, получен путем небольшой модификации алгоритма, опнсапного в [б4). Модификация заключалась в записи алгоритма без использования оператора яо 1о, как это принято в современном программировании.
Помимо этого, представление векторов в виде строк матриц, использованное в [64], заменено на более распространенное представление векторов в виде столбцов тех же матриц. Алгоритм является итерационным. На каждой итерации совершаются операции перестановки столбцов матриц, умножение столбца матрицы на -1, сложение либо вычитание одного столбца, умноженного на целое число г, с другим столбцом.
Каждая из этих операций может быть описана в виде умножения на унимодулярную матрицу. Следовательно, итог всех итераций можно рассматривать как результат унимодулярного преобразования. Приводимый ниже Ш. алгоритм вычисляет следующие величины; матрицу Р квадратичной формы, соответствующую решетке с гораздо более короткими базисными векторами; 258 Приягоячяил унимодулярную матрицу (), необходимую для преобразования решения по формуле (А.4); векторы ю,, 1=!,и, пересчитанных координат центров эллипсоидов (для алгоритма, рассмотренного в Приложении А, требуется пересчет координат только одного центра). Для упрощения обозначений в процессе описания (ЛЛ. алгоритма введены следующие обозначения: О=ВЫ'; Р=Р; п- векторов к,.', 1= 1,и, координат центров исходных эллипсоидов представлены столбцами входной матрицы 1сгч размера Чхи. С учетом введенных обозначений, Ш.
алгоритм в кодах языка МАТ(.АВ имеет следующий вид: Гппс1)оп [РЧЧ, $3, пзхч[ = Ш.(О, кхч) о Ш. алгоритм. 94 Вход: ;4 Π— верхняя треугольная матрица, столбцы которой задают я исходные базисные векторы решетки о )ггч — матрица размера Чхи, столбцы которой являются ' векторами координат центров и о исходных эллипсоидов ' Выход: Я4 Р— матрица квадратичной формы, соответствующая решетке я с гораздо более короткими базисными векторами Я4 $3 — матрица обратного унимодулярного преобразования я щхч — матрица размера Чхи, столбцы которой являются Я4 векторами координат центров и преобразованных эллипсоидов [Ч,Ц = а[хе(О); 1ГЧ дЬр (' Входная матрица в функции Ш.
не является квадратной'); гезигп; епй 0 = еуе(Ч); [1, и) = я)хе(харч); щхч = 1ил; ;4 Ортогонализация Грама — Шмидта Гог1 = 1:Ч йаих(:, 1) = О(:,1); Гог)= 1: 1-1 щи([, 1) = О(:, 1) Яяаих(:,))/ч([); йаих(:,1) = йаих(:,1)-що([, 1)Яйацх(:,)); епп 259 Сп/пнпиновыв/гадионавиголионныв гастоны ч(1) = дацх(:, 1) впацх(:, 1); епй '.4 Основной алгоритм Ь=2; эчЬ!1е Ь < = и 5=1п!; (пш, О, 13, щгч) = Аагег(ак(5, !Ь щц, О,(/, п, шхч); !Г ч(1з) < (0.75ыпц(1п1, Ь)"2)*ч(Ь-1) гш = пш(1м!,Ь); с = ч(Ь)+ по 2вч(1п1); пш(Ь-1,Ь) = пц*ч(1м1)/с; ч(Ь) = ч(1м1)вч(1з)/с; ч(1п1) = с; вйв перестановка 1пго и (!м1)-го столбцов матрицы О ацх = О(:,Ь-1); О(:,!п!) = О(:, 1з); О(:, 1з) = ацх; ',4 перестановка Ь-го и (Ь-1)-го столбцов матрицы ~3 уиимодулярного вг4 преобразования ацх = Щ:,Ь-1); Щ, Ь-1) = 13(:, Ь); Щ:,1з) = ацх; Гй перестановка Ь-й и (Ь-1)-й компоисит векторов тхч Гог(= 1:и ацх = гпгч(1м1, 1); пзхч(Ь-!, 1) = тгч(Ь, 1); щхч(Ь, 1) = ацх; епй '4в перестановка первых Ь-2 элементов в 1пм и (1м1)-м '/о столбцах матрицы пш ацх = пш(1: Ь-2, Ь-1); пш(1: Ь-2, 1и1) = шц(1: Ь-2, Ь); пш(1: Ь-2, 1з) = ацх; ;4 осуществление векторно-матричного улщожсиия Гог! = Ь+!х) пш2 = (1 пш(Ь-1, 1з);0 1)в(0 1;! -пц)в[шц(Ь-1, 1); пш(Ь, 1)).
пш(Ь-1,1) = пш2(1); пш(Ь,1) = тц2(2); епп' 1Г)з > 2 260 Прнлозкелая Ь = Ь-1; еаза е1ве Гога = Ь-2: -1: 1 [тп,б, Цтгч] = Авгег!вЕ(в, Ь, шн,б,(),п,шгч); еаза 1ГЬ= =Ч РЧЧ = П «П' ге!пгп; еаза Ь = Ь+1; еаза епв( Гппсйоп [пш, 6, (), шгч] = Аввепв1с(в, Ь, пш, б, (), п, пач) % процедура Авгег!й длл Ш. алгоритма 1в аЬв(шн(в, Ь)) > 0.5 г = гоппд(шн(в, Ь)); % округление до ближайшего целого П(;, Ь) = П(;, Ь)-г«б(;, в); ()(:, Ь) = Б(:, Ь) - г«Ц:, в); Гог] = 1:и швч(в,]) = шач(в,]) е г«шач(!и)); ецио Гог] = 1з-! шн(], Ь) = пш(1, Ь) - г«шн(], в); епд шн(в, Ь) = па(в, Ь)-г; епв) 1,420794641 66677 -13,2!288457737586 50,87553058794973 !6,7690061520!726 5,53208426714422 5,532084267!4422 37,16950168495617 1,42079464166677 -13,21288457737586 (С.!2) 0 0 1 0 ! 6 1 !1 60 (С.13) швч =[9,50939974400!04 0,435454!7599785 0,62334411599636) .
(С.14) 261 П р и м е р. Для матрицы С(В.2) и вектора бич Ьвч =[0,623344115996358 4,!75518871976 51,7000426397589] (С.!1) матрицы РЧЧ, 1) и вектор шач имеют аид Сауттканые род нов авнгои нонны е сиате вы Легко проверяются равенства; де!(Р) = де!(Рир!) = = 26942,04028079618, где Рр(р( матрица (В,!), де!(()) =-1, шгн = () ' кгт, Р = ()~0р(р! (! . Приложение 0 Описание алгоритма вычисления п последовательно нарастающих целочисленных минимумов квадратичной формы Ставиться задача минимизации преобразованной квадратичной формы: ,т кн((ш) = (ш — ш') Р (ш - ш'), (РЛ) размерности о в целых числах. Алгоритм вычисления матрицы Р преобразованной квадратичной формы описан в Приложении С.
Разложим матрицу Р квадратичной формы (О.!) на произведе- ние трех матриц Р = 00!., (0.2) х=кр-ир . (0.3) С учетом (Р.2) и (Р.З), представим квадратичную форму (0.1) в виде х Р х=х !.РЬ х=у Ру, (0.4) где 1п 1н "' 1~ рр О 1 !23 " 12 р„ 1за, О О О " О ! х, хз у=!. х= (0.5) хз 262 где !. — нижнетреугольная матрица с единицами по главной диагонали; 0 — диагональная матрица, диагональные элементы которой больше нуля. Преобразование матрицы Р„„к виду (0.2) называют ЕР1~ разложением [41, 70). Алгоритм вычисления этого разложения описан в Приложении Е. Введем обозначение Првцожецая Матричное выражение ут0у может быть запнса1ю также в форме у"Оу =,),~„у,', (0.6) >ы где для каждой компоненты у; справедливы выражения у; = х; + ~ 1„х1 = х, + ~ 18 ()цр! — йр, ), 1 = 1, о -1, (0.7) уц = хц = 1црц 1грц (0.8) ~ йьУзйг, (0.9) где Л вЂ” пока что некоторая произвольная положительная константа, необходимо, чтобы все члены дьу,' суммы (0.9) были бы меньше Е и все частичные суммы г; =~6-у, ~~, 1=9,1.
(0.10) Частичные суммы г; (0.10) обладают следуюшими свойствами: если удовлетворяется неравенство (0.9), то а < гц, «." а, < Е; значение х зависит только от уц и, следовательно, согласно (0.8), только от кр,; значение а,, зависит только от у , уц, и, следовательно, согласно (0.7), (0.8), только от )цр,, кр , и т.д. Значение г, зависит от всех компонент вектора у и, следовательно, от всех компонент целочисленного вектора кр.
Частичные суммы г; (0.10) могут вычисляться рекуррентно, а именнйч (О.!! ) Если теперь квадратичную форму (Р.б) приравнять константе У,: Нетрудно видеть, что (0.6) есть представление квадратичной формы (0.1) в виде суммы квадратов по Лагранжу !71]. Поэтому ЕОь~ разложение можно рассматривать так же, как способ вычисления коэффициентов д,, 11 1=1,9, )=1+1,9, используемых для представления квадратичной формы в виде суммы квадратов по Лагранжу. Все слагаемые в сумме (0.6) больше нуля. Поэтому для того, чтобы выполнялось условие Сп»тонконме раднооаенгапноппые енететм у'Ру=',) дну,'=2, (0.12) то получим уравнение эллипсоида. Точки с целочисленными координатами (ТЦК), лежащие внутри этого эллипсоида, будут порождать значение квадратичной формы (0.6) меньше, чем 2.
ТЦК, лежащие вне эллипсоида (0.12), будут порождать значение квадратичной формы больше, чем 2 (способ задания начального значения Е описан в Приложении Е). Поэтому надо искать ТЦК, расположенные внутри эллипсоида (Р.12). При этом желательно выбирать каждый раз такие координаты 1ср, .ТЦК, при которых достигается возможно меньшее значение квадратичной формы. Из (0.7) и (0.8) следует, что для этого необходимо выбирать такие значения координат йр; ТЦК, при которых модули 1у;~ принимают минимальные значения. Отсюда, с учетом того, что х; = 1срн - йр;, полу- чаем ч ( !у ~= хг ь ~ 1вх! = !чр;-~!чр; — ~1;;(кр1-кр,) -+ш(п, (013) 1 ~+! гл» или в другой форме: ч 1ср, = ближайшее целое к !чр — ) 18.
х; Нд (О.! 4) Нетрудно видеть, что вычисление сумм в (Р.14) для каждого уровня ! =9-1,1 также может осуществляться рекуррентно. Из (0.14) видим, что выбор координат !чр, ТЦК на каждом уровне поиска 1 необходимо проводить в следующем порядке. Сначала в качестве кр; следует выбрать ближайшее целое к середине интервала, т.е. к значению !ерзал 1ср1 Х 1вх! ' (0.15) Затем следует последовательно перебирать координаты слева и справа от начального целого, отходя от него на ч-1, затем на ч-2 и т.д.
При таком переборе величины у,' растут монотонно. Поэтому для проверки того, что ТЦК с координатой 1ср; лежит внутри эллипсоида (0.9) достаточно рекуррентно вычислять значение частичной квадратичной формы х, и сравнить его с 2. Если х; < 2, то выбранная координата кр; ТЦК на 1-м Првяожеаая уровне принимается. Если же г; > Х, то выбранная координата 1~, .ТЦК на 1-м уровне отвергается и поиск переходит на уровень с большим индексом Е Если на и-м уровне достигается условие г„ > Е, то поиск внутри эллипсоида (0.9) заданного размера Х прекращается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
