Поваляев А.А. Спутниковые радионавигационные системы (2008) (1151867), страница 48
Текст из файла (страница 48)
Как только найдена ТЦК внутри эллипсоида (0.12) , т.е. вычислено значение х, < Х, можно уменьшить размер эллипсоида Х, приняв его равным значению квадратичной формы в найдешюй точке, т.е. Е = а, . В результате дальнейший поиск будет осуществляться в эллипсоиде меньшего размера. Такое уменьшение размера эллипсоида можно продолжать до тех пор, пока внутри него не окажется ни одной ТЦК. Тогда последняя найденная ТЦК является целочисленным минимумом квадратичной формы. Если требуется найти несколько ТЦК, являющихся последовательно нарастающими минимумами квадратичной формы (О.1), то уменьшение размера эллипсоида следует начинать только после того, как внутри него уже найдено желаемое число ТЦК. В кодах языка МАТ(.АВ вышеописанный алгоритм поиска имеет вид: Ропе![оп [КК,ЛЯГ) = зеагс!з(10!с, )сит, и) ;4 вычисление и последовательно нарастающих целочисленных ;4 минимумов квадратичной формы (К-!ггт) Рпп ()г-)сит) о Вход: ' 1О1! — матрица размера с~*д, содержащая матрицы 1., О, 1.т ЫН.т ',4 разложения матрицы квадратичной формы Рос в упакованной ' форме (см.
Приложение Е) ' )гхт — ц-мерный вектор координат центра эллипсоида ' и — число точек с целочисленными а4 координатами, которое необходимо найти ' Выход: ;4 КК матрица размера ц'п, столбцы которой являются а целочисленными координатами и последовательно ' нарастающих минимумов квадратичной формы о ЛЯà — и-размерный вектор значений квадратичной формы для и О последовательно нарастающих минимумов [ч, ш) = з(ке(!01!). 1!ц-= гп дЬР('Входная матрица в функции зеагс!з не является квадратной'); ге!игл; епг! 1(цс! о(зр('Размерность входной матрицы в функции зеагсЬ меньше, чем 1'); гвв Снутнссконын раднонненгосСнннные со<тены гетпгп; епд % Определение структуры веагсЬ веагсЬ = ввгисС('1еч', ввгпсС(Чс Ьей', П, Чс', (), Чс П', (), 'ис)Г, (), ...
'раг аппп', (),'0', (),'сс овс', (),'дсг', ()),'101с',101с, '!сыч', ... 1сич, 'сГ, сс, 'гевк', весов(сс,о), 'гевх', [1:о], 'про!асс', п, ... 'проппд', О, 'ОР, 0.0); % Вычисление определителя матрицы квадратичной формы десепп = 1.0; Гогс = 0:0-1 хч = 1О!с((в(0+1)+1); сГхч < 0.0 дсвр('Матрица квадратичной формы в функции веагсЬ не является положительно определенной'); геспгп; епд десепп = десепп'хч; веагсЬ.!еч(с+!).Р = хч; % распределение диагональных % элементов входной 1011 % матрицы % по уровням поиска % веагсЬ.!еч(с+!).раг впш(с(-1) = 0.0; % обнуление сумм для % вычисления Ь Й на всех уровнях епд веагсЬ.!еч(с!+1).ицГ = 0.0; % вычислени размера эллипсоида [веагсЩР] = вса!е(с), п+1, десепп); % начало основного алгоритма 11 = 0; с2 = 0; пЫ!е 11 < = сс % начало внешнего бесконечного цикла веагсЬ.!еч(сс)Лс Й = веагсЬ.1сич(с(); [веагсЬ] = асссч(сС,веагсЬ); % активация сс-го уровня 1еч ппш = сб и Ь11е с2 < = сс % начало внутреннего бесконечного цикла !Г веагсЬ.!еч(! еч пшп).гцГ < веагсЬ.ОР % первая открывающая % операторная скобка 1Г 1еч пшп = = ! % вторая открывающая операторная скобка [веагсЬ] = ваче роспс(веагсЬ); [веагсЬ] = рагс асйч(!еч пшп, веагсЬ);% частичная % активация % !еч пшп-го уровня Прил оасепам е)зе % вычисление сумм для !г Г! на уровнях от !еч пшп-1 до 1 хч = зеагсЬ.!еч(1еч ппв).1г-зеагсЬ.йяч(1еч ппв); Гог т = 1еч пшп-1:-1:1 зеагсЬ.!еч(!).раг зпв(1еч ппв-1) = ...
зеагсЬЛеч(т).раг янп(1еч пшп-!+1)+ Ю!т(!Леч пшп)"хч; епт! !еч пов = 1еч ппв-1; % вычисление)г Л на уровне с номером 1еч пшп зеагсЬ.!еч(1еч пшп)Лс П = зеагсЬЛсхч(!еч ппв)-... зеагсЬЛеч(!еч пшп).раг зпв(1); [зеагсЬ) = асбч(!еч пшп, зеагсЬ); % активация уровня %1еч ппв епт! % вторая закрывающая операторная скобка е)зе 1Г 1еч пцв = = т! % вторая открывающая операторная скобка % проверка условия что найдено не менее чем п точек !ГзеагсЬ.пропит! > = зеагсЬ.пРо(пгз; Гог)= 1:п ХгЛР(1) = зеагс!т.гезг.(1); Кй(:, 1) = зеагсЬ.гезК(:, 1); епт! ге!игл; епт) % увеличение размера эллипсоида в случае пропив' < пРошм зеагсЩР = 2Л)*зеагсЩР; зеагсЬ.пропит! = 0; Ьгеа)ц) епт! % вторая закрывающая операторная скобка !еч ппв = 1еч пшп+1; (зеагсЬ] = рагт асйч(1еч пшп,зеагсЬ);%частичная активация % 1еч пшп-го уровня; епт! % первая закрывающая операторная скобка епй % конец внутреннего бесконечного цикла епд % конец внешнего бесконечного цикла Гппсбоп (зеагсЬ) = асйч(Ь зеагсЬ) % начальная активация Ьго % уровня % вычисление начального целого наг-м уровне путем округления % до ближайшего целого зеагсЬ.!еч(1)Лг = гоппп(зеагсЬ.!еч(1)Лс й); зеагсЬЛеч(1)Лг Ьея = зеагсЬ.1еч(1)йн Снутникоеи~е раднонаеигаяионные си<тены % Вычисление начального целочисленного шага для колебаний на % Ьм уровне зеагсЬЛен(1)Лг озс = О; % Вычисление начального направления целочисленных колебаний зеагсЬЛен(1)А)1г = 1; !г зеагсЬ.!еи(!).1с () < зеагсЬ.!еч(!)Лс Ъек зеагсЬ.1еи(!).г(!г = -1; епг! % вычисление частичной суммы на Ьм уровне ггпр = зеагсЬ.!еи(!)Лс-зеагсЬЛеу(1)Лг (); зеагсЬЛен(!).2с!!' = зеагсЬ.1ен(1+1).хг!(+...
зеагсЬ.!ен(1).0'напр'гшр; рапсйоп [зеагсЬ] = рагс асг!н(1, зеагсЬ) '/ю частичная активация Ьго % уровня % Перевычисленне шага целочисленных колебаний зеагсййен(г).1с озс = зеагсЬ.1ен(!)Лг озс+... зеагсЬ.!ен(!).г(!г; % изменение направления целочисленных колебаний на ;4 противоположное хн =-1; 1г зеагсЬ.1ен(1).б!г < О хи=1; епг! зеагсЬ.1еи(!)хйг = хн-зеагсЬ.1ен(1).г(!г; % вычисление нового целого на 1-м уровне зеагсЬ.!ен(!)Лс = зеагсЬ.!еи(1)Лс Ьея+...
зеагсЬ.!еи(!)Лс озс; % Вычисление новой частичной суммы на 1-м уровне Нпр = зеагсЬ.!ен(!).!с - зеагсЬ.!еи(!),1с Й; зеагсЬ.1ен(!).2г!Г = зеагсЬ.!ен(!+!).хо(+... зеагсЬ.!ен(1).Рапир'гшр; рапсйоп [зеагсЬ) = каче ро!пг(зеагсЬ) % определение места для сохранения информации об очередной '/ найденной целочисленной точке и сохранение этой % информации на найденном месте % вычисление местоположения новой найденной точки среди н4 ранее найденных 1=1; 1ог ш = 1зеагсЬ.пгоопд; !г зеагсЬ.!еи(1) хг!Г < зеагсЬ.гезХ(ш) Ьгеай; епг! 288 Приложения 1= 1+1; епп % До тех пор, пока проппд < пРо)пш, 1 < = проппа+1, потому % что всегда проппа' < = пРогппс %Кактолькопроппд = = пРо(пгз,(неможетбыть больше, чем % пРошгз.
Следовательно, всегда г < = прогпцс % сохранение информации о вновь найденной точке 1Г1<= зеагсЬ.процпг(сс г- = зеагсЬшрошгз [зеагсЬ) = шзегг ро!пг(1, зеагсЬ); е!зе'/ случай! = = пЕоцпдили г = = проппд+1 [зеагсЬ) = сору ропп(Ь зеагс)г); епй % Увеличение числа найденных точек на 1, если процпг! < пРогпгз 1Г зеагсйшроппд < зеагсЬ.пРошгз зеагсЬ.пЕоппг) = зеагсЬ.проппй+1; епп % эадагие нового размера эллипсоида при пЕоцпд = = пРо!пгз 1ГзеагсЬ.процпд = = зеагсЬ.пРогпгз зеагсЩР = зеагсЬ.ген(зеагсЬ.пРо!пгз); епп Гвпсйоп [зеагсЬ) = шзегг ро[пг([, зеагсЬ) % раэдвижение информации о ранее найденных точках на)-м месте и % помещение на это место информации о вновь найденной точке % сдвиг информации о точках с номерами от)-го до процпд на % одну позицию Гогг = зеагсЬ.проппд:-1:) !Г) < зеагсЬ.пРошгз зеагсЬ.ген(1+1) = зеагсЬ.ген(!); зеагсЬ.гезК(:, !+1) = зеагсЬ.гезК(:, 1); епг) епг) % копирование информации о вновь найденной целочисленной % точке на )-е место [зеагсЬ) = сору ро)пг([, зеагсЬ); Гппсйоп [зеагсЬ) = сору ро)пг([, зеагсЬ) % Копирование информации о вновь найденной точке на)хе место % копирование значения квадратичной формы зеагсЬ.ген([) = зеагсЬ.!еч(1).гоГ; % копирование целых со всех уровней Гог( = 1зеагсЬх) Саун>никоеые уадионаеигаяиониые енотеиы зеагсй.геаК(1,)) = зеагсЬ.!еи(1) к; епп' В результате работы функции зеагс1з вычисляется массив КВ, в котором последовательно представлены целочисленные векторы, минимизирующие квадратичную форму, и массив у44г, в котором последовательно представлены значения квадратичной формы, соответствующие векторам из массива Кй.
П р и м е р . Для матрицы 1О1! (Е.1), вектора йят (С.14) и и = 1О имеем 9 10 10 1О 9 9 8 9 !1 10 ! 0 0 1 0 0 1 ! 0 1 ! 0 1 1 1 0 1 0 0 0 (О.16) Уфг =1!4,06893175026263 20,44588513772041 20,79727978399100 21,07021448587864 24,860!6558266340 27,3503602!972637 40,605661318681!3 42,98489554207729 47,07942235974896 47,! 445889943598 1] Умножение матрицы Кй (О.! 6) слева на матрицу !) (С.!3) дает следую- щую совокупность из 10 последовательно нарастающих целочисленных минимумов исходной квадратичной формы с матрицей Ог!г( (В.!): ! 0 1 1 ! 0 ! 0 0 0 к ы=бхКВ= 7 0 6 7 6 0 7 1 0 1 .
(О.!8) 80 10 70 81 69 9 79 20 !! 2! 270 Массив (О.17) значений квадратичной формы при этом, очевидно, не меняется В основе описанного выше алгоритма лежит перебор координат !гр, ТЦК колебаниями вокруг координат 8р; центра эллипсоида, вычисление значений частичных сумм х; (О.10) и сравнение их на каждом уровне поиска 1 с размером эллипсоида 2. Если при этом на каком либо уровне оказывается, что х, .>2, то поиск со значением кр, .на данном уровне прекращается и алгоритм переходит па предыдущий, более высокий уровень для очередной смены значения Еры, .
При этом не производится явного вычисления границ, между которыми происходит перебор целочисленных координат кр, ТЦК в процессе поиска. Определение таких границ, так как это делается, например, в (27, 28, 721, требует Приложения выполнения операции извлечения квадратного корня и, следовательно, повышенного объема вычислений. Приложение Е Алгоритм ЕОЕ разложения положительно определенной матрицы Для реализации алгоритма вычисления последовательно нарастающих целочисленных минимумов квадратичной формы (см. Приложение О) необходимо осуществление специального преобразования матрицы Р„этой квадратичной формы.
Симметричную положительно определенную матрицу Р размерности Ч можно представить аналогично разложению Холецкого в виде произведения трех матриц: Рн — (ОЙ, (Е.1) где Š— нижнетреугольная матрица с единичными элементами по главной диагонали; 0 — диагональная матрица, диагональные элементы которой больше нуля. Разложения (Е.1) называют 1.О1." разложением [41, 70] Его можно так же рассматривать как разновидность разложения Холецкого [41], либо же как разложение матрицы квадратичной формы для представления ее в виде суммы квадратов по Лагранжу [7! ].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
