Поваляев А.А. Спутниковые радионавигационные системы (2008) (1151867), страница 46
Текст из файла (страница 46)
Вычисляются координаты минимумов исходной квадратичной формы (5.19) с матрнцей 0 по формуле 1с = 13 щ;, 1=1, и. (А.4) Приложение В Алгоритм разложения Холецкого симметрической положительно определенной матрицы Для данной симметрической положительно определенной матрицы 0еКн"н следующий алгоритм в кодах языка МАТ(.АВ вычисляет верхнюю треугольную матрицу ВКт е К""", такую что 0 = ВК ВКт.
На выходе алгоритма для всех ) >1 элементы ВК~(1,1) замещают соответствующие элементы 0(1,1): 252 Описанная трехэтапная процедура минимизации в целых числах квадратичной формы вида КЧР(к) (5.19) позволяет значительно сократить расходы машинного времени. (Автору известны примеры успешной минимизации квадратичной формы в целых числах с числом переменных 9 = 200 за время порядка нескольких секунд.) Можно с уверенностью утверждать, что без перехода к более ортогональным базисным векторам решетки решение задачи минимизации квадратичной формы в целых числах при столь большом числе переменных было бы невозможным.
77риложелия Гппсйоп (Р) = С1ю! гп(Р) ;4 Вычисление множителя Холецкого положительно определенной ;4 симметрической матрицы Р. Функция Спо! ш вычисляет ;4 всрхнетреугольную матрицу бт, такую, что Р = бабт. 54 На выходе входная матрица Р замешается на бт. (ц,п) = з(хе(Р); 1Гц»= и п(зр('Входная матрица в функции Озо! ш не является квадратной'); е(зе Гог! = 1х( 1Г! >! Р(! 1:ч) = Р(! ':Ч) - Р(16-1 1) "Р(16-1 йц)! епй (Г Р(1, !) < = 0.0 о(зр('Входная матрица в функции Спо! пз не является...
положительно определенной'); ге(пгп; спи Р(! ВЧ) = Р(! ВЧ)узцг1(Р(1 '))! епй Гог! = 29 Гог! = 16-1 Р(1,!) = 0.0; епг! епп епд П р и м е р . Для матрицы 1 769,95389611312 -960,302974544202 68,842325950905 ГИ!ц = -960,302974544202 1944,51339220187 -178,926983405045 .(В.1) 68,842325950905 -178,926983405045 !6,7690061520!73 соответствуюшая матрица бт будет иметь вид 42,07082000761479 -22,82586777178073 1,6363438!1!8420 бт = 0,0 37,72920821680535 -3,75242478263094 .(В.2) 0,0 0,0 0,10340857949693 Алгоритм вычисления верхнетреугольного мгюжителя Холецкого в данном приложении получен путем небольшой модификации алгоритма, заимствованного из [70).
Модификация заключалась в том, что 263 Сн»тникиеые роднонавнгопнонные еиетюгы вместо нижней треугольной матрицы ВВ, вычисляемой в [70], в предлагаемом алгоритме вычисляется верхняя треугольная матрица ВВ», столбцы которой являются исходными базисными векторами решетки. Результат вычислений помещается в верхней треугольной части матрицы О.
Часть этой матрицы, расположенная под нижней диагональю, обнуляется. Готовая процедура на языке С вычисления нижнетрсугольной матрицы ВВ разложения Холецкого может быть заимствована из [61]. Приложение С Ш алгоритм Рассмотрим способ диагоналнзации матрицы исходной квадратичной формы Кргр(к) (5.!9) па основе мсгодов математической теории решетчатых упаковок [59, 60].
Матрица () называется целочисленной унимодулярной, если ее элементы целочисленные и модуль определителя () равен 1: 1) н Уи"", г)е1() =Ы. (С.1) Поскольку элементы обратной матрицы есть отношения миноров исходной матрицы к се определителю, а определитель обратной матрицы есть величина обратная к определителю исходной матрицы, то обращение унимодулярной матрицы дает так жс унимодулярную матрицу. Все множество целочисленных векторов У," размера ц можно рассматривать как целочисленную решетку в о-мерном пространстве. В силу унимодулярности матрицы (), линейное преобразование у = ()х хнг.' является взаимно однозначным отображением целочисленной решетки Е" на себя.
Пусть А — произвольная вещественная невырождснная матрица размера окц. Тогда множество Т(А) вещественных векторов вида Т(А)=(у=Ах: хнуч) (С.2) называется действительной решеткой, порожденной матрицсй А. Другими словами, действительная решетка Т(А) есть образ цслочислешюй решетки Е" при отображении линейным преобразованием А. Пусть В— другая вещественная невырожденная матрица н Т(В) порождаемая ею действительная решетка. Тогда совпадение множеств Т(А) и Т(В) (т.е. совпадение действительных решеток) возможно только в том слу- чае, если В=А(/, (С.З) с$е1Т(А)~)а,на,! .... (а,), (С.4) где а1, 1=1, о, — вектор-столбцы матрица А; 11 — операция вычисления модуля вектора.
Будем далее использовать вектор-столбцы матрицы В=А(1 для обозначения произвольного базиса решетки Т(А) и введем в рассмотрение функцию Е(В) произвольного базиса, определяемую как произведение модулей всех его векторов: Р(В)=(Ь,НЬ,~ .... (Ь,), где Ь;, 1 = 1, ц, — вектор-столбцы матрицы В. В соответствии с (С.4) минимум функции Р(В) на множестве базисов решетки Т(А) будет всегда больше или равен определителю де1Т(А) этой решетки.
Равенство будет достигаться только в случае, когда среди всех возможных базисов решетки найдется ортогональный базис, или иными словами найдется матрица В = АВ с ортогональными столбцами. Тогда произведение модулей вектор-столбцов этой матрицы 255 где 1) — унимодулярная матрица. Из (С.З), с учетом того, что де1 1) =~1, получаем ое1 А =~де1В. Таким образом одна и та же действительная решетка может порождаться множеством матриц, связанных между собою соотношением (С.З), в котором  — произвольная унимодулярная матрица. Модули определителей этих матриц одинаковы.
Это позволяет ввести понятие не зависяшего от матрицы 13 определителя действительной решетки, который равен ~де1(А)~ и обозначается как ое1Т(А). Какова бы ни была унимодулярная матрица 1), столбцы каждой из матриц А() образуют разные базисы одной и той же действительной решетки Т(А) . Из обших свойств определителей матриц следует (41), что объем параллелепипеда, натянутого на векторы каждого из этих базисов, одинаков и равен определителю решетки де1 Т(А) = ~бе1 А~ . Объем прямоугольного параллелепипеда, построенного на произвольных векторах, всегда больше или равен объему любого другого параллелепипеда, построенного на тех же векторах. Отсюда вытекает неравенство Сиутникивые ридиииавигиниинные енетюни будет равно де1Т(А).
Однако не всякая решетка имеет среди всех своих возможных базисов ортогоналльный базис, поскольку ис всякую матрицу А можно привести к виду с ортогональными столбцами при помощи целочисленного унимодулярного преобразования А(). Поэтому в теории решеток [59, 60) ставится задача о наилучшем приведении не- вырожденной матрицы А к виду с «почти» ортогональными столбцами при помощи унимодулярных преобразований.
Эту же задачу можно понимать как задачу выбора в действительной решетке Т(А) базиса, наиболее приближенного к ортогональному. Нетрудно видеть, что эта же задача может быть сформулирована как задача поиска минимума функции Р(В) (С.5) на множестве всех базисов решетки Т(А), т.е. как задача поиска базиса с наиболее коротки- ми векторами. В случае рассмотрения целочисленной решетки Е" такая задача формулируется так же, как задача поиска так называемого М-сторонника Эрмита [66). Рассмотрим один из наиболее эффективных алгоритмов решения задачи приведения [64). Для любой невырожденной матрицы А существует такая верхняя треугольная матрица р(А) с единицами по главной диагонали, что А = А"р(А) и столбцы матрицы А" ортогональны.
Наддиагональные элементы матрицы р(А)могут быть вычислены с помощью метода ортогонализации Грамма — Шмидта [4!): нч а,'=а; — ~Гид(А)а,", 1 (а, а,") (а; а,") (а,' а,") ) в~' где а;, а,.", 1=1, 9, — столбцы матриц А и А" соответственно; ()— операция скалярного произведения векторов.
Первый столбец матрицы А" в методе Грамма — Шмидта принимается равным первому столбцу матрицы А. Каждый следующий йй столбец матрицы А" вычисляется как проекция 1-го вектор-столбца матрицы А на(9-1)-плоскость, ортогональную ранее найденным вектор- столбцам матрицы А" . Таким образом, модули вектор-столбцов матрицы А" не превышают модулей соответствующих им вектор-столбцов матрицы А. ПРипожелая Если исходная матрица А такова, что ее столбцы ортогональны, то наддиагональные элементы матрицы р(А), вычисленные в соответствии с (С.б), будут равны О. Поэтому в качестве меры близости столбцов матрицы А к ортогональным можно использовать максимум модуля ~ря(А)~, найденный среди всех 1=2, Ч, 1=1, Р1, В алгоритме приведения (64) базис решетки считается почти ортогональным, если выполняется условие ~ря (А)~ < —, 1 = 2, Ч, 3 = 1, 1-1.
2 В противном случае в 164] пытаются найти такое унимодулярное преобразование (), что элементы матрицы р(А()) удовлетворяют ограничению (С.7). Вернемся к задаче диагонализацни матрицы исходной квадратичной формы КЧг(к) (5.19). Представим матрицу 0 исходной квадратичной формы (5.19) в виде разложения Холецкого: (С.8) где матрица В — нижнетреугольная. Полагая, что вектор-столбцы матрицы Вм~ задают вещественную решетку, применим к ней процедуру приведения. В результате найдем матрицу унимодулярного преобразования 1) такую, что столбцы матрицы Ч = Вй~() будут образовывать базис с наиболее короткими векторами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
