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