Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 31
Текст из файла (страница 31)
С другой стороны, значения и~ при 1 > 10, кажется, не имеют практического значения. (И это хорошо, поскольку было бы очень трудно вычислить точность «м когда 1 > 10,) Существует не вполне ясная зависимость между спектральным критерием и критерием серий. Например, частный случай критерия серий для целого периода, рассмотренный в упр.
3.3.3 — 19, подсчитывает число ячеек в каждом из 64 подквадратов (см. рис. 8, (а)). Основная разница состоит в том, что спектральный критерий вращает точки до тех пор, пока не определит наименее благоприятную ориентацию. Ниже в этом разделе мы еще возвратимся к критерию серий. Может показаться, что достаточно применить спектральный критерий только для одного довольно большого значения г. Если генератор пройдет проверку критерием с тремя измерениями, то кажется правдоподобным, что он пройдет проверку и 2-П-критерием; следовательно, зту проверку можно не делать. Такие рассуждения ошибочны, поскольку не учтено то, что мы требуем более жестких ограничений при более низких размерностях.
Подобная ситуация наблюдается при использовании критерия серий. Рассмотрим генератор, у которого почти то же количество точек попадает в каждый подкуб единичного куба, когда единичный куб разделен на 64 подкуба размера -' х -' х -'. Тот же генератор нижет дать полностью писптоп подкввдрат единичного квадрата, когда единичный квадрат делится на 64 подквадрата размера -' х -'. Таким образом, средние значения при низких измерениях увеличиваются и для каждого измерения требуется отдельная проверка.
Не вгегда выполняется неравенство и~ < гп1 ч, хотя гп'д будет верхней гранью для прямоугольной решетки. Например, оказывается, что иэ = чг274 > ~/об на. рнс. 8, поскольку приблизительно шестиугольная структура объединяет т точек так, что возможно строго прямоугольное упорядочение. Чтобы построить алгоритм, который эффективно подсчитывает им следует более глубоко разобраться в необходимой для этого математической теории. Поэтому читатель, которого не интересуют математические обоснования, может перейти сразу к части П этого раздела, в которой спектральный критерий будет представлен как "общий" метод, сопровождаемый некоторыми примерами.
Однако для математического обоснования спектрального критерия необходимо знать только элементарные преобразования векторов. Некоторые авторы предлагают использовать минимальное число Ф~ параллельных линий или гиперплоскостей, проходящих через все точки, вместо максимального расстояния 1/и~ между ними. Однако число М~ не кажется таким важным, как понятие точности, определенное выше, поскольку оно имеет смещение, зависящее от величины отклонения этих линий или гиперплоскостей от координатных осей куба. Например, приблизительно 20 вертикальных линий, проходящих через все точки на рис.
8, (а), дают действительно 1/~/328 единиц в соответствии с формулой (14), которая приводилась ниже: (иы пэ) = (18, — 2). Поэтому можно ошибочно принять„ что точность равна ~/328 или, возможно, даже 20. Истиннан точность, равная ~/2~4, реализуется только для большого семейства из 21 линии с наклоном 7/15; другое семейство из 24 линий с наклоном -11/13 также имеет ббльшне расстояния между линиями, чем семейство из 20 линий, поскольку 1/~/290 > 1/1/328.
Способ, с помощью которого семейства линий располагаются относительно границ единичного гиперкуба, кажется, не является каким-либо особенно "чистым" или значащим критерием. Однако те, кто предпочитают считать гиперплоскости, могут подсчитывать Жь используя метод, весьма похожий на тот„с помощью которого мы будем подсчитывать и, (см. упр. 16), ЯВ.
Дальнейшее исследование критерия. Анализ основного множества (2) начнем с наблюдения 1 О) азх+(1+а+".+аз ')с (б) От "модуля 1" можно избавиться, выполнив операцию, с помощью которой множество удлиняется периодически, н сделав бесконечное множество копий исходного г-размерного гиперкуба во всех направлениях. Это дает множество Е = (~ — +йм — +йт, „— +й~) ~ целое х,й~,йт,...,Ц~ х э(х) э(* '~(х) = )(1о+ ~ — + йм — +йт,...,— +(ь) ~ целое х,й1„йт,...,йг~, 1о = — (О, с, (1+ а)с, ..., (1 + а + ° ° + а' ~)с) (б) является вектором констант. Переменная й1 избыточна в этом представлении Ь, потомУ что можно менать (х, йм Лз,..., йс) на (х+ багги, О, Лт — айм..., Ир — аг 'Л1), доводя,)г~ до нуля без потери общности.
Поэтому получим сравнительно простую формулу: Е =Я+1пЪ'1+ртЪт+" +у~'К~целыермрз" 1л) (7) где 1 ~4г = — (1, а, а,..., а" ~ ); (8) Ъ'р = (0,1,0,..., 0), Ъз = (О, О, 1,..., 0), ..., Ъ'~ = (0,0,0,..., 1), (9) Точки (х~,хт,..., х~) Е, удовлетворяющие неравенству 0 < х1 < 1 лчя всех у, являются именно т точяямя исходного множества (2). Заметим, что приращение с появляется только в 1'е и влияние 1'е заключается в сдвиге всех элементов Е без изменения их относительных расстояний. Следовательно, с никоим образом не влияет яа спектральный критерий и в качестве хорошего предположения можно взять Ц = (0,0...,,0) при вычислении но Когда 1е— нулевой вектор, имеем точечную сятррятлррр Хо = (рг1'1+Ыз+ +у~1з ~ целыеумрз„...,уД (10) и нашей целью является изучение расстояний между смежными (à — 1)-мерными гиперплоскостями в семействе параллельных гиперплоскостей, покрывающих все точки Хо.
Семейство параллельных (1 — 1)-мерных гиперплоскостей можно определить следующим образом. Пусть ненулевой вектор У = (нм...,и~) перпендикулярен всем гиперплоскостям; тогда множеством точек на определенной гиперплоскости является множество ((хм",х~) ~х1и~+" +яраг=4, где а — - различные константы для каждой гиперплоскости семейства.
Другими словами, каждая гиперплоскость — это множество всех векторов Х, для которых скалярное произведение Х У имеет данное значение д. В нашем случае все гиперплоскости разделяются фиксированными расстояниями и в одной из них содержится (О, О,..., О). Следовательно, можно так установить значение У, что множество всех целых значений о даст все гиперплоскости в семействе. Тогда расстояние между соседними гиперплоскостями будет равно минимальному расстоянию от (О, О,..., О) до гиперплоскости с и = 1, а именно: ( '*Г+" *(~* ° +"+* = ).
(12) деястентельнме ть...л, ( В соответствии с неравенством Коши (см. упр. 1.2.3-30) имеем (х(и)+ ° ° +х~ис) <(х, + ° ° +х,)(и, + ° ° +и,), (13) следовательно, минимум в (12) достигаетгя, когда каждое ху = и~/(и1 + + и,). Это означает, что расстояние между соседними гиперплоскостямн равно 1(~Я+ '+') =1~а -(г).
(14) Другими словами, искомая величина и~ точно равна длине кратчайшего вектора (), определяющего семейство гиперплоскостей (Л' () = Е ( целое д), в которых содержатся все элементы Ее, Такой вектор У ы (н),..., иг) должен быть ненулевым н удовлетворять требованию $'У = целое для всех У в Ьо. В частности, так как все точки (1,0,...,0), (0,1,...,0)...
(0,0....,1) принадлежат Ье, все и) должны быть целыми. Кроме того, так как 1 ) пРинадлежит Ао, получим, что -'(и~ + аиз + . ° + а' (сч) — целые, т. е. и) + аиэ + " + а' 1и, ьз О (по модулю и)). (16) И наоборот, любой ненулевой целый вектор (7 = (им..., н~), удрвлетворяющий (15), определяет семейство гнперплоскостей с необходимыми свойствами, так как будут покрыты все Ьо. Скалярное произведение (р) 1') + °" + р(р() У будет целым для всех целых ры ..'., рь Мы доказали, что и~ = шш (ит1+ . +и~ ~ и)+пот+ +а' (и, пи о (по модулю го)) (ко „ы)ф(0,...,6) (16) ппп ((тх)-ахэ-а хэ- .-а' х,) +хт+хэ+ . +х,) . (ю,., л~)я(о,...,о) С.
Обоснование вычислительных методов. Сведем спектральный критерий к задаче нахождения минимального значения (16). Но как можно найти минимальное значение за разумный отрезок времени? Грубое силовое исследование не входит в наши планы, так квк гп — очень большое в случаях, представляющих практический интерес. Будет интересно и, возможно, более полезно разработать вычислительные методы решений даже более общей проблемы: найти минимальное значение величины ,7(х),...,хд = (имх(+ ° ° .
+ ипх1)~ + ° ° + (пмх) + ° ° + и~ хдт (17) по всем ненулевым целым векторам (хм..., х,) для любой невырожденной матрицы с коэффициентами У = (и(.). Выражение (17) назовем положительно определенной квадратичной формой от ( переменных. Так как (7 — невырожденная матрица, (17) не может быть нулем, если не все х равны нулю. Запишем как П>, ..., Пз все строки Г Тогда (17) можно запксать как У(хз ° ° ° >хй = (х1П1 + +хеПа) (х1б'1 +" . +х>Ю> (18) квадрат длины вектора х з П~+ ° .+хз Пь Невырожденная матрица П имеет обратную матрицу, а это означает, что можно найти единственным образом определенные векторы 3~ы.... 14, такие, что (19) Пз Ъ; =80, 1<11<1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
