AOP_Tom2 (1021737), страница 21
Текст из файла (страница 21)
Переменная йг избыточна в этом представлении Е, потому что можно менять (х, йы йг,..., Йс) на (х+ кгт, О, Йг — акы..., Йс — а' кг), доводя (с~ до нуля без потери общности. Поэтому получим сравнительно простую Формулу: Е, = (Уе+ угУг + угУг + . + уЛ! целые ум уз,,ус), (7) где У~ — — (1, а, аг,, аг г); 1 (8) Уг = (О, 1, О,..., 0), Уг = (О, О, 1,..., 0), ..., Ъг = (О, О, Оы .., 1). (9) Точки (хмхг,...,хг) Ь, удовлетворяющие неравенству О < х, с 1 для всех у, являются именно т точкями исходного множества (2). Заметим, что приращение с появляется только в ге и влияние Уе заключается в сдвиге всех элементов Е без изменения их относительных расстояний.
Следовательно, с никоим образом не влияет иа спектральный критерий и в качестве хорошего предположения можно взять Ус — — (0,0,...,0) при вычислении яо Когда Уе— нулевой вектор, имеем точечную струюпуру Ее = (угУ +угУг+. +уЛ ! целые умуг,...,уг) (10) и нашей целью является изучение расстояний между смежными (1 — 1)-мерными гнперплоскостями в семействе параллельных гиперплоскостей, покрывающих все точки Ее.
Семейство параллельных (1 — 1)-мерных гиперплоскостей можно определить следующим образом. Пусть ненулевой вектор (7 = (им...,пс) перпендикулярен всем гиперплоскостям; тогда множеством точек на определенной гиперплоскости является множество ((хм..., хг) ( хгиг + + хспг = у) где у — различные константы для каждой гиперплоскости семейства, Другими словами, каждая гнперплоскость — это множество всех векторов Х, для которых скалярное провгеедетгае Х. 17 имеет данное значение д. В нашем случае все гиперплоскости разделяются фиксированными расстояниями и в одной из иих содержится (О, О,..., О).
Следовательно, можно так установить значение У, что множество всех целых значений д даст все гиперплоскости в семействе. Тогда расстояние между соседними гиперплоскостями будет равно минимальному расстоянию от (О, О,..., 0) до гиперплоскости с д = 1,а именно: Ь 1чЯ~ тг гь;.. ';г»=1). (1Е леествлтельлме то...,т~ Г В соответствии с неравенством Коши (см. упр.
1.2.3-30) имеем (хгиг+ ..+хгщ) <(х, + +х,)(и,+.. +и,), (13) следовательно, минимум в (12) достигается, когда каждое хг = иугг(ог + .. + и,). Это означает, что расстояние между соседними гиперплоскостями равно (14) Другими словами, искомая величина гтг точна равна длине кратчайшего вектора сг, определяющего семейство гиперплоскостей (Х У = е ~ целое д), в которых содержатся все элементы Ье. Такой вектор У = (иг,..., иг) должен быть ненулевым и удовлетворять требоваиию И (1 = целое для всех И в Ее, В частности, так как все точки (1,0,..., 0), (0,1,...,0), ..., (0,0,...,1) принадлежат Ее, все и должны бьггь целыми.
Кроме того, так как Ъ~ принадлежит Ье, получим, что — '(иг + аиг + .. + а' г пг) — целые, т. е. иг+ аиг+ + а' 'и, = 0 (по модулю пг). (15) И наоборот, любой ненулевой целый вектор ЕУ = (иы, .., иг), удрвлетворяющий (15), определяет семейство гиперплоскостей с необходимыми свойствами, так как будут покрыты все Бе. скалярное произведение (у111 + " + ргъг) У будет целым для всех целых рг, ..., Во Мы доказали, что и~ = ппп (игг+ +иг ~ иг+аиг+ . +а~ ~юг = 0 (по модулю пг)) (ьь...,ьОЯ1е,...,а1 (16) г тг г г,г,гг гп!и ((тхг — ахг — а хг — — а х,) +хг+хг+ +х,) . 1т " ' 1гь1е " *е) С.
Обоснование вычислительных методов. Сведем спектральный критерий к задаче иахождения минимального значения (16). Но как можно найти минимальное значение за разумный отрезок времени? Грубое силовое исследование ие входит в наши планы, так как пг — очень большое в случаях, представляющих практический интерес. Будет интересно и, возможио, более полезно разработать вычислительные методы решений даже более общей проблемы: лапти минимальное значение величины У(х,,х,) =(и~ х, + . +ьцхг) + +(игсхг+ +ипхс) (17) по всем ненулевым целым векторам (хы..., хг) для любой невырождениой матрицы с коэффициентами с7 = (и; ).
Выражение (17) назовем положительно определенной квадратичной формой от г переменных. Так как У - — иевырождеииая матрица, (17) ие может быть нулем, если не все хг равны нулю. Запишем как Ь'и ..., Ц все строки Г Тогда (17) можно записать как У(хы °,хс) =(х11~1+ . +х~Ц) (х~П1+ +х~У,), (18) квадрат длины вектора х1П1+ . +х~Пь Невырожденная матрица Г имеет обратную матрицу, а это означает, что можно найти единственным образом определенные векторы К~,...,Ъм такие, что П, $1=б„, 1<1,2<6 (19) Например, в частном случае (16), возникающем в связи со спектральным критерием, получим Ъ"~ = — (1,а,ат,...,а ), И = (О, 1, О,..., О), 1з = (О, О, 1,..., О), П1 — — ( гп, О, О,..., 0), Пг = ( — а,1,0,...,0), Пз = ( -аэ, Р, 1,..., О), (20) Пс = (-а~ 1,0,0,..., 1), Р~ —— (0,0, О,..., 1). Эти Ъ; точно равны векторам (8) и (9), которые использовались для определения начальной решетки Ье.
Как и подозревает читатель, здесь нет совпадения: действительно, мы начинали с произвольной решетки Те, определенной любым множеством линейно независимых векторов Уы..., И. Доводы, используемые нами выше, могут быть обобщены, чтобы показать, что максимальное расстояние между гиперплоскостями в покрывающем все точки семействе равно минимуму (17), где коэффициенты и, определены в (19) (см. упр. 2).
Первый шаг в минимизации (18) — ее сведение к конечной задаче: необходимо показать, что лдя нахождения минимума нет необходимости в бесконечном множестве векторов (хы..., х~). Удобно выразить хь через векторы (м., ., Ъм а именно х, = (х,П, + "+х,(7) („ и из неравенства Коши получить неравенство ((х1П1 + ' '+ хЮг) )гь) < 1(х1 х~)Я ' 1гь). Итак, получена удобная верхняя граница каждой координаты хь. Лемма А. Пусть (хм..., х,) — ненулевой вектор, минимизирующий (18), и пусть (уы..., уэ) — любой ненулевой целочисленный вектор.
Тогда хь < ауы..., У1)(1гь Ъ'ь) для 1 < й < к (21) В частности, полагая у; = б; для всех 1, получим х,' <% Пу)(Ъи $гь) длл 1<1,lс <й 1 (22) Лемма А сводит задачу к нахождению минимума по конечному множеству, но правая часть (21) обычно является слишком большой для того, чтобы можно было перебрать все значения (по крайней мере, нужна еще одна добавочная идея).
В таком случае помогает старый афоризм: "Если вы не можете решить задачу в том виде, в каком она сформулирована, упростите ее, чтобы получить х', = х, — о ху, Ц = Г; для 1 ~ у; (23) х,' = х„П,' = (?1 + Еказ дД Ъ? = 'г', — д,~', Г'=Г, 1' Легко видеть, что новые векторы У,',..., Ц определяют квадратичную форму У', для которой У'(х'„..., х',) = Дх„..., х,). Кроме того, основное условие ортогональности (19) сохраняется, так как легко проверить, что У 1" = 311 Когда(яы.,.,х~) пробегает множество всех не равных нулю целочисленных векторов, то (х'„..., х',) пробегает зто же множество; следовательно, новая форма ?' имеет тот же минимум, что и У.
Нашей целью является использование преобразования (23) и замена Ц на У,' и 1с на Ъ? для всех 1, чтобы сделать правую часть (22) малой (правая часть (22) будет малой, когда У ° У. и Р~, 1ь будут малы). Следовательно, вполне естественно задать два следующих вопроса о~носитсльпо преобразования (23), а) Какие значения д; делают 'г',? 'г'1 настолько малыми, насколько это возможно? Ь) Какие значения дм ..., дз ы о ч,, ..., д, делают П' У настолько малыми, насколько зто возможно? Легче всего ответить на зти вопросы сначала для дейсшвишельних значений щ.
Вопрос (а) совершенно простой, так как Я вЂ” ч |'~) Я вЂ” ЬЦ) = $', 1'( — 29; ~~ Ъ'+93 1' Ъ' (1,, 1, )( (1, 1, (Р ~,'))з+Р Р (1; 1, )2~1, 1; и минимум достигается, когда (24) 9; = Р; 1 (11.1',. С геометрической точки зрения мы спрашиваем, сколько раз можно вычесть гу из 1;, чтобы получить вектор минимальной длины $~', и отвечаем: нужно выбрать такое до чтобы Ъ было перпендикулярно г', (т. е. сделать так, чтобы выполнялось такой же ответ".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
