Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 32
Текст из файла (страница 32)
Например, в частном случае (16), возникающем в связи со спектральным критерием, получим Р— 1 (1, а, аз,, аз-1) (О, 1, О,..., О), Рз = (0* 0 1,..., 0), (20) Пь = ( т, О, О,... „0), Пз = ( -а,1,0,...,0), Пз = ( -аз, О, 1,, О), Пз =(-а' ',0,0,...,1), хь = (х1П~ + +х~Пз) 1'в, и из неравенства Коши получить неравенство ((х1 6 з + . + хам~) .
)гь) < У(х1 ., ха) ()гь " Ю. Итак, получена удобная верхняя граница каждой координаты хь. Лемма А. Пусть (хз,..., хз) — ненулевой вектор, минимизирующий (18), н пусть (йы..., рз) — любой ненулевой целочисленный вектор. Тогда хь э< Дум...,р,)Я, ° 34ь) для 1 < Й <Ф. (21) В частности, полагал 9; = бз для всех з, получим хьз < Щ Пт)(Ъ~ )гь) для 1 <,~', А < г. (22) Лемма А сводит задачу к нахождению минимума по конечному множеству, но правая часть (21) обычно является слишком большой для того„чтобы можно было перебрать все значения (по крайней мере, нужна еще одна добавочная идея).
В таком случае помогает старый афоризм: "Если вы не можете решить задачу в том виде, в каком оиа сформулирована, упростите ее, чтобы получить Эти Р) точно равны векторам (8) и (9), которые использовались для определения начальной решетки Ее. Как и подозревает читатель, здесь нет совпадения: действительно, мы начинали с произвольной решетки Ее, определенной любым множеством линейно независимых векторов Ъы..., Ъь Доводы, используемые нами выше, могут быть обобщены, чтобы показать, что максимальное расстояние между гиперплоскостями в покрывающем все точки семействе равно минимуму (17), где коэффициенты иц определены в (19) (см.
упр. 2). Первый шаг в минимизации (18) — ее сведение к конечной задаче: необходимо показать, что для нахождения минимума иет необходимости в бесконечном множестве векторов (хм..., хз). Удобно выразить хь через векторы 1 ы..., 1м а именно такой же ответ". Например, алгоритм Евклида имеет такой вид, что если наибольший общий делитель чисел на входе неизвестен, придется выбирать его среди меньших чисел, имеющих тот же наибольший общий делитель. (На самом деле в основе открытия всех подобных алгоритмов, возможно, лежит несколько более общий подход: "Если вы не можете непосредственно решить задачу, сведите ее к одной из более простых задач, решив которые, вы сможете справиться с исходной задачей'.) В рассматриваемом здесь случае более простой проблемой является проблема, требующая меньшего количества проверок, потому что правая часть в (22) уменьшилась.
Ключевой используемой идеей является возможность заменить одну квадратичную форму другой, которая представляет собой эквивалент лля достижения всех практических целей. Пусть з — любой фиксированный индекс, 1 < з < 1, н пусть (чм ° ",чз-мФ+м...,9) — любая последовательность 1 — 1 целых чисел. Рассмотрим следующее преобразование векторов: $",=У; — д,-Уч х'; =х,- з;х„(Г =б;. для1~1; 17=Уз, хз =ху, Н1 =уз+к;ВЗчро Легко видеть, что новые векторы (1,',..., Ц определяют квадратичную форму у', ,зля которой ~'(х1,..., я',) = У(ям..., х,). Кроме того, основное условие ортогональности (19) сохраняется, так как легко проверить, что Ц У.' = 4».
Когда (хм..., яг) пРобегает множество всех не равных нулю целочисленных векторов, то (х(,..., я',) пробегает это же множество; следовательно, новая форма ~' имеет тот же минимум, что н у. Нашей целью является использование преобразования (23) и замена У; нв Ц и У; на ~ для всех 1, чтобы сделать правую часть (22) малой (правая часть (22) будет малой, когда Пу (11 н Уь . Уь будут малы). Следовательно, вполне естественно задать два следующих вопроса огноипсльно преобразования (23). а) Какие значения д~ делают Уг У„' настолько малымн, насколько зто возможно? Ь) Какие значения ом ..., о~ ы ву+м ..., ц делают Ц ° У' настолько малыми, насколько это возможно? Легче всего ответить на эти вопросы сначала для дейстеншельимя значений оь Вопрос (а) совершенно простой, так' как (1)-д;У) (У,-о,.У1) =У,.У)-2д;У; Уз+дйУ1 У =(Уз У) (~,-(УмУ;)Уз-Уз))'+У; У,-(У,"Ут)'~У1.У, и минимум достигается, когда (24) о; = К Уз./У1.У,.
С геометрической точки зрения мы спрашиваем, сколько раз можно вычесть 11 нз Усо чтобы получить вектор минимальной длины У,.', и отвечаем: нужно выбрать такое в„чтобы У было перпендикулярно Уз (т. е. сделать так, чтобы выполнялось равенство Ъ . $' = О), Это изображено на следующем графике. (25) Обратимся к воп1хлсу (Ь). Необходимо выбрать такое ао чтобы Уу + ~,.~ 4;Ул имели минимальную длину. С геометрической точки зрения следует начать с Уу и прибавить некоторый вектор в (г — Ц-мерной гиперплоскостн, равный сумме кратных (Ц ~ л 1~ Я. Снова лучшим решением является такой выбор, при котором У' является перпендикулярным к гиперплоскости, т. е. У' ° Ул —— 0 для всех Й ~ у: иу"(1,+'сйад и,) =О, 1<3<1, (26) оь1 (В упр.
12 приводится строгое доказательство того, что решение (Ь) должно удовлетворять этим 1 — 1 уравнениям.) Ответив на вопросы (а) и (Ь), мы оказались в двойном затруднении: можно ли выбрать щ соответственно (24) так, чтобы Ъ",' ° Ъ было минимальным, или согласно (26) так, чтобы б'" ° У' было минимальным? Каждая из этих альтернатив приводит к уменьшению части (22), поэтому сразу не ясно, какому выбору отдать предпочтение. К счастью, существует очень простое решение этой дилеммы: уеловия (24) и (26) те же самые! (См, упр. 7,) Следовательно, ответы на вопросы (а) и (Ь) совпадают.
Получается, что длину обоих векторов Ц и 11 можно уменьшить одновременно. На самом деле мы только что снова открыли процесс ортогоиалиаации Грача-Шмидта ~0гат-$сйтлй) (см. Сге11е 94 (1883), 41-73). Нашу радость омрачает понимание того, что вопросы (а) и (Ь) рассматривались только для действительных значений йь Для решения поставленной задачи следует ограничиться целыми значениями, в связи с чем провести Ъ1 точно перпендикулярно 1' нельзя. Лучшее, что можно сделать в (а), — это положить 4; наиболее близким целим к )гл. Р) 1 1) 1" (см.
(25)). Оказывается, что зто ие всегда лучшее решение вопроса (Ь); на самом деле У~ иногда может быть длиннее У . Однако граница (21) никогда не растет, поэтому мы можем запомнить наименьшее значение Дум °, Р~), найденное до сих пор. Этот выбор д;, основанный исключительно на вопргхя (а), является совершенно удовлетворительным. Если преобразование (23) повторно применить таким образом, чтобы ни один из векторов 1; не стал длиннее и по крайней мере один стал короче, мы никогда не попадем в петлю, т.
е. мы никогда не будем рассматривать ту же квадратичную форму асиле ряда нетривиальных преобразований подобного вида, В конце концов, мы застрянем: ни одно из преобразований (23) для 1 < 1 < 1 не будет в состоянии укоротить любой нз векторов $'ы ..., Ъь В этой точке можно возвращаться к исчерпывающему исследованию, используя границы леммы А, которые будут вполне малы в болыпинстве случаев.
Изредка этих границ (21) недостаточно, и другой вид преобразования обычно дает алгоритм выхода из положения, в котором мы застряли, и уменьшения границы (см. упр. 18). Тем не менее доказано, что преобра- 1 < с' < С; иа протяжении этого этапа вычислений.) В2. [Шаг Евклида.[ Присвоить д с- (Ь'~Ь), и +- Ь'-ф,, и +- р'-сср. Если из+се < з, присвоить з с — из + из, Ь' +- Ь, Ь +- и, р' с- р, р +- и и повторить шаг 82.
БЗ. [Вычислеиие из.) Присвоить и +- и — Ь, и +- и — р, а если и~+из < з, присвоить з +- из + из, Ь' с- и, р' с- и. Затем выход ~/з = из. (Справедливость этих вычислеиий для двумерного случая доказана в упр. 5. Подготовим матрицы У и Р, удовлетворяющие соответственно (28) и (29), для вычисчеиий в больших размерностях.) Присвоить У с- Ь, , $' с в к зоваиие (23) в самого себя вполне отвечает требованиям спектрального критерия; к тому же доказаио, что оио поразительно мощное, когда вычисления осуществляются твк, как в алгоритме, обсуждаемом ниже.
е11. Квк выполнить спектральный критерий. В этом разделе будет приведеиа эффективная вычислительная процедура. Госпер (Соврет) и Дитер (Всесег) заметили, что можио использовать результаты для более низкой размериости, чтобы зиачительио быстрее получить спектральиый критерий в высокой размерности. Это усовершеиствоваиие включено в следующий алгоритм вместе с упрощением Гаусса (Саизз) для двумерного случая (упр.
5). Алгоритм Б (Спектральимсс критерий). Этот алгоритм определяет значение '(чЯ~" +4[* ~ е~-" ~ '' — о( ее )) ОО для 2 < с < Т, заданных а, т и Т, где О < а < т и а и т — взаимно простые числа. (Мииимум взят по всем ненулевым целочисленным векторам (хм..., хс), а число ю является С-меркой точностью генератора случайных чисел, как обсуждалось выше.) Вся арифметика в пределах алгоритма дана в целых числах, размеры которых редко либо никогда ие превышают т~, исключая шаг 87.
К тому же почти все целые перемеииые будут меиьше т по абсолютной величине иа протяжеиии вычислеиий. Когда ис вычисляется для С > 3, алгоритм работает с двумя С х С-матрицами Сс и 1», векторы-строки которых обозначены через Ц = (ип,..., ии) и рс = (шс,..., ии) для 1 < с < С. Эти векторы удовлетворяют условиям ип+ аип+ ° ° +а' сии аз О (по моДУлю т), (28) Пс 1»у = тАО, 1 < с,у < с. (29) (Таким образом, $~с из предыдущих обсуждеиий умножаются иа т, чтобы их компоиеиты бьши целыми числами.) Существует три дополнительных вектора: Х = (хсм .~хс)с 1» (ус,... ус) и Я (зс ... хс).
В алгоритме г будет обозневаеь ас с шос( пс, а з — иаимеиьшУю веРхнюю гРвиь исз, котоРаа была найдена Ранее. В1. [Ииицивлизация,[ Присвоить С с- 2, Ь +- а, Ь' +- т, р с- 1, р' +- О, г с — а, з е- 1+ а . (Первые шаги алгоритма — это специальный метод, примененный к случаю С = 2, который очень похож иа алгоритм Евклида.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
