admin

МАТРИЦЫ АДАМАРА

Этот форум посвящен матрицам Адамара в расширительном их толковании как ортогональных матриц с минимальным максимальным по абсолютной величине элементом (минимальной m-нормой). Форум, в отличие от статей, хорош тем, что отражает историю исследований – уникальная возможность проследить эволюцию темы. По итогам работы форума подготовлены статья (рекомендуется к просмотру) и постоянно корректируемый обзор.

Обзоры: Обзор П. Камеруна (копия) | (аннотация) | сайт | черновик | длинная статья | еще | новация

ИСТОРИЯ n=2^k-1 Числа Мерсенна | 2 | 3 | Числа Прота

Книжка Холла, Комбинаторика, 1970 | A course in combinatorics Авторы: Jacobus Hendricus van Lint, Richard Michael Wilson Симплексы и кубы | о том же | Design Theory | LAP-книга.

Список литературы есть в работе Мохана, можно почитать Стинсона, Себбери и Ко, Муда, Ли (комплексные C-матрицы) , каталоги комплексных H-матриц [2] и С-матриц

МОНИТОРИНГ

Hadamard Matrices: Калькулятор | Перечень (N. J. A. Sloane) | Библиотека | Еще.

Conference Matrices: Список C-матриц | Коды

Программы MatLab от MathWorks Inc. Программa PHP-BC (вычислений с повышенной разрядностью)..

Квантованные матрицы 8x8 с 8-ю значениями, [техника]

ФРАКТАЛЬНЫЕ СВОЙСТВА

Матричная алхимия: мир фракталов | вакуумное условие

НЕМНОГО ИСТОРИИ

В огромном саду геометрии каждый может подобрать себе букет по вку­су... И ныне наглядное понимание иг­рает первенствующую роль в геомет­рии.

Давид ГИЛЬБЕРТ

Особый класс систем ортогональных функций составляют системы кусочно-постоянных функций, таких как функции Уолша, Адамара и Хаара.

Впервые такую систему предложил Радемахер:

Rk(θ)=sign(sin(2kπθ))

где θ=t/T - безразмерное время. Система функций Радемахера ортонормирована на интервале [0,1], но неполна (синусы без косинусов). Дополнить ее для косинусов по аналогии не получается, условие ортогональности, в общем, противоречит периодичности выборки (см. след. стр.). Ниже рисунок дискретизации для косинусов.

В 1923 году американский ученый Уолш получил полную систему ортонормированных функций, которая дополняет систему функций Радемахера. Функции Уолша, образующие полную ортонормированную систему, можно определить так: W0=R0, W1=R1, W2=R2, W3=R1R2, и т.п. Их получают, в частности, систематизируя строки матриц Адамара.

ФУНКЦИИ УОЛША СИСТЕМАТИЗИРОВАНЫ ПО 'КОЛЕБАТЕЛЬНОСТИ'

Справка тут, еще.

Классическая система Хаара [2] есть система сжатий и сдвигов одной функции Радемахера R0. Существуют обобщения нечетных порядков для комплексных матриц Адамара. Эти системы имеют большое практическое значение, особенно для цифровых систем, поскольку они характеризуются высокоэффективными алгоритмами быстрых преобразований.

Быстрого там, собственно, то, что особый вид матрицы ортогонального преобразования позволяет сократить количество элементарных операций при вычислении результата умножения на нее вектора выборки сигнала.

Общеприняты следующие упорядочения (способы определения функций Уолша): упорядочение по частоте (по Уолшу с помощью функций Радемахера), упорядочение по Пэли (диадическое), упорядочение по Адамару, где под частотой функции понимается число пересечений нулевого уровня в единицу времени. Функции Радемахера перемножаются при использовании циклического кода Грея. Коды, у которых все следующие друг за другом кодовые слова различаются только одной цифрой в некотором разряде, называются циклическими. Двоичное представление числа может быть легко преобразовано в циклический код Грея с помощью полусумматоров. В любом таком случае генерируемые коды оказываются двухуровневыми, бинарными. Помимо того, им отвечает определенное четное количество точек аргумента во времени. Многоуровневые коды можно получить, обобщая матрицы Адамара.

На третьем (и прочих нечетных) порядке аналогом матрицы Адамара является не двух, а трехуровневая (и, в общем, многоуровневая) структура: М-матрица

M =
1
2
2
2
1
-2
2
-2
1

которая аппроксимирует все те же гармонические зависимости.

Связь с фракталами. В работе показано, что элементы матрицы Адамара можно получить возведением в p-степень -1, причем p=∑ ij, суммируются k-е разряды двоичного представления индексов элементов i и j. Матрица степеней образует треугольник Серпинского, если черным цветом закрашивать 0.

ДВУМЕРНЫЙ БАЗИС

График m-norm на текущий день

ТАИНСТВЕННАЯ ВЯЗЬ ИСТОРИИ

В разные эпохи один и тот же объект принимал образы символа Одина (Валькнута), колец Борромо, матриц Адамара. Так ему удалось пережить столетия.

КОЛЬЦА БОРРОМЕО

А теперь в качестве небольшого отступления рассмотрим известную топологическую структуру, которая называется "кольца Борромео". Это три кольца, попарно не сцепленные, но в совокупной целостности разъединить их не удается. Кольца соединены таким способом, при котором любые два кольца скрепляются посредством третьего. Такие кольца были изображены на фамильном гербе знаменитого в эпоху Возрождения итальянского семейства Борромео, откуда они и получили свое название.

В предположении, что все кольца плоские, такая фигура не может существовать. Для создания фигуры в трехмерном пространстве, необходимы трехмерные изгибы колец. Математические кольца Борромео определяются как три или больше топологических окружности, объединенных в соединении Брунниана таким образом, что при удалении из конструкции одной из них оставшиеся два оказываются разомкнутыми. Если подразумевать под кольцами физические подсистемы, то их характерной особенностью является то, что если одно кольцо убрать, то два оставшихся не будут связаны никакими корреляциями. Они станут сепарабельными (разделимыми), то есть их запутанность распадается с удалением любого кольца.

Международная группа физиков получила из трех обычных атомов новое состояние вещества, предсказанное советским ученым Виталием Ефимовым ещё в 1970 году. Он показал, что в квантовой системе из трех частиц наличие «резонансности» парных сил необходимо и достаточно для возникновения семейства связанных уровней, в отдельных случаях содержащее бесконечное их количество. Наиболее благоприятно этот эксперимент протекает в системе бесспиновых нейтральных бозонов. В новом эксперименте существование эффекта, предсказанного советским физиком, было подтверждено для системы из атомов цезия. Любые два из этих атомов отталкиваются при сближении. «Но если соединить вместе три атома, оказывается, что они притягиваются и переходят в новое состояние», - объясняет доктор Чэн Чин из Чикагского университета. Он и его коллеги из Инсбрукского университета в Австрии под руководством Рудольфа Грима получили новое состояние вещества в вакуумной камере при очень низких температурах, почти при абсолютном нуле. Атомы в новом состоянии ведут себя как «кольца Борромео» - узел из трех колец в котором любые два не связаны друг с другом, но все три вместе образуют единый узел.

Кольца Борромео как топологическая структура используются в качестве символа христианской Троицы. Ранее нередко встречались такие символы, как равносторонний треугольник, круг и некоторые другие, но сейчас все чаще Троицу изображают в виде колец Борромео. Одним из самых ранних источников, где было приведено такое символическое изображение Пресвятой Троицы, считается рукопись тринадцатого столетия, которая хранилась в муниципальной библиотеке г. Шартр (Chartres) во Франции. К сожалению, рукопись погибла в огне в 1944 году. Во все времена кольца Борромео служили символом «силы в единстве». Семьи Борромео и ныне владеет на севере Италии тремя островами на озере, где расположен впечатляющий дворец в стиле барокко, построенный в семнадцатом веке Витальяно Борромео. В самом дворце и в саду можно встретить много примеров знаменитой эмблемы дома Борромео. Невозможные объекты получили развитие в рисунках Эшера.

ССЫЛКА | НЕВОЗМОЖНЫЙ МИР

МАТРОИД ФАНО

Центральная часть колец Борромео проецируется на диаграмму или матроид Фано. Матроид (в дискретной математике и комбинаторике) — структура, которая схватывает сущность понятия «независимость», обобщающего линейную независимость в векторных пространствах. Классификация подмножеств некоторого множества, представляющая собой обобщение идеи независимости элементов, аналогично независимости элементов линейного пространства, на произвольное множество.

Возьмем треугольник с медианными линиями. Будем считать (одной) стороной (или блоком) совокупность трех точек пересечения, всего точек семь: (7,3,1).

Выделим все блоки по три точки: A = {123, 145, 167, 246, 257, 347, 356}. Это координаты (если считать верхний левый угол 0) 1 матрицы Адамара (матрицы инцидентности, то бишь, связей графа)

Диаграмма показывает 3-ранговый матроид, называемый матроидом Фано, пример, который появился в 1935 в статье Уитни (Whitney). Название возникло из того факта, что матроид Фано представляет собой проективную плоскость второго порядка, известная как плоскость Фано, чьё координатное поле — это двух-элементное поле. Это означает, что матроид Фано — это векторный матроид, связанный с семью ненулевыми векторами в трехмерном векторном пространстве над полем 2-х элементов. Из проективной геометрии известно, что матроид Фано непредставим произвольным множеством векторов в вещественном или комплексном векторном пространстве (или в любом векторном пространстве над полем, чьи характеристики отличаются от 2).

СИМВОЛ ОДИНА (ВАЛЬКНУТ)

Итак, кольца Борромео, матроид Фано и матрицы Адамара - три разные ипостаси объекта, трактуемого в разные века и у разных народов как святая Троица, символ Одина или Валькнут.

Валькнут часто встречается при археологических раскопках на древних рунических камнях (как правило, поминальных) рядом с изображениями Одина или павших воинов. Его иногда так и называют - Узел Павших или Узел Избранных. Три переплетенных треугольника символизируют три мира: мир богов (Асгард), мир людей (Мидгард) и мир мертвых (Хель). Как говорит А. Платов (Платов А., Дарт А. ван. Практический курс рунического искусства. К.: София, 2000): «Три мира переплетены в этом символе Отца Магии; следует видеть в этом знак того, что маг черпает Силу и мудрость изо всех трех миров, взаимопроникающих и пересекающихся чаще, чем об этом думают. Валькнут - своего рода Северная Мандала... Созерцание такого глубокого магического символа, как Валькнут, и размышление о его сути — возможно, это одна из тех многих тропок, что могут вести к самотрансформации...»

КАРТА КОСМОСА: МАНДАЛА

Мандала символизирует сферу обитания божеств, чистые земли будд. В принципе, мандала - это геометрический символ сложной структуры, который интерпретируется как модель вселенной, «карта космоса». Типичная форма - внешний круг, вписанный в него квадрат, в который вписан внутренний круг, который часто сегментирован или имеет форму лотоса. Нечто сходное с матрешками орбит Кеплера.

Внешний круг - Вселенная, внутренний круг - измерение божеств, бодхисаттв, будд. Квадрат между ними ориентирован по сторонам света.

Мандалы могут быть как двумерными, изображенными на плоскости, так и объёмными, рельефными. Их вышивают на ткани, рисуют на песке, выполняют цветными порошками и делают из металла, камня, дерева. Её даже могут вырезать из масла, которое окрашивают в соответствующие ритуальные цвета. Мандалы часто изображают на полах, стенах и потолках храмов. Мандала является настолько священной на Востоке, что рисуется под аккомпанемент особых ритуалов и сама может считаться объектом поклонения. Некоторые из мандал выполняют из цветных порошков для проведения определённой ритуальной практики (например, в посвящении Калачакры). К концу ритуала сделанную мандалу разрушают.

Для настроки сознания мадалу нужно созерцать

Карл Густав Юнг идентифицировал мандалу как архетипический символ человеческого совершенства - ныне она используется в психотерапии в качестве средства достижения полноты понимания собственного «я». В Индии сохраняется сходное искусство - ранголи, или альпона. До наших дней дошел Календарь древней цивилизации Майя, выполненный в форме мандалы.

При очевидной восточной вычурности эффект мандалы известен, впрочем, с детства едва ли не каждому, вспомните калейдоскоп

ТРЕУГОЛЬНИК ПАСКАЛЯ

Как же пройти мимо него. Уровни и количесво элементов на уровнях матриц нижних порядков - все находятся в вершине этой треугольной таблицы.

Существуют различные методы раскрашивания, выделяющие в нем фрактальные узоры. Этим качеством отличаются также матрицы Адамара.

Треугольник Паскаля mod 2

Раскраска показателями степенной функции (элементов матриц Адамара)

Оба построения ведут к треугольнику Серпинского, см. рисунки по матрицам Адамара.

И-Цзин. триграммы "Книги перемен"

СВЯЗКА С ЗАПИСЬЮ ЧИСЕЛ ПАЛОЧКАМИ

ТЕОРЕМА ФЕРМА (ЭЙЛЕРА) И ГИПОТЕЗЫ

Озвучим базовые гипотезы исследования, напомним, что гипотеза Адамара не доказана вот уже как 100 лет.

Гипотеза Адамара. Согласно этой гипотезе для всех порядков n=4*k ( кратных 4: 4, 8, 12, 16, 20, ..), существуют адамаровы матрицы.

Гипотеза Балонина. Согласно этой гипотезе для всех порядков n=3+4*k (3, 7, 11, 15, 19, ..), существуют матрицы типа Мерсенна (М-матрицы с уровнями 1, -b).

Гипотеза Балонина о приведенной норме. Приведенные m-нормы структурированных (уровневых) M-матриц типа Адамара, Белевича, Мерсенна с ростом n стремятся к 1, предположение (гипотеза) состоит в том, что для остальных минимаксных матриц это не так, есть иной предел b=9/8 (оптимистичная оценка, полочка).

m = min |M|.

У отдельных представителей матриц m может приближаться к 1, но с ростом порядка всегда найдутся "особо плохие", в этом смысле, матрицы. Не все матрицы приближаются к адамаровым, всегда будут отклонения, и первой такой неструктурируемой матрицей является M13.

Всего существует 4 типа M-матриц: A,B,C,D, где A - адамаровы, C - матрицы Белевича, B (и можно добавить D, учитывая отличие порядков по модулю 4, но тогда опускаются пропуски среди матриц Белевича) - остальные матрицы, деление пока весьма условное. Положение, высказанное Мироновским, подтвердилось – между матрицами порядков 3 (mod 4) и 1 (mod 4) существует такая же разница, как между матрицами Адамара и Белевича (C-матрицами).

Теорема Ферма (Эйлера) о простых числах. Все простые числа подразделяются на числа, представимые в виде 4k+1, и числа, представимые в виде 4k–1, где k - некоторое целое число. Так, число 13 принадлежит к первой группе (13 = 4·3+1), а число 19 - ко второй группе (19 = 4·5–1). Теорема Ферма о простых числах утверждает, что простые числа первой группы всегда представимы в виде суммы двух квадратов (13 = 4+9), в то время как простые числа второй группы никогда в виде суммы двух квадратов не представимы (19 =?+?). В 1749 году, после семи лет работы и почти через сто лет после смерти Ферма, Эйлеру удалось доказать эту теорему о простых числах.

C-матрица Белевича опираются в своем построении на символы Лежандра, как раз, для первого случая, когда q=n-1 простое число, представимое суммой квадратов - С6, например, q=n-1=5=1+22. C-матрицы, в отличие от матриц Адамара, существуют не для всех порядков, равных 2 (mod 4). В таком случае они отнесены к B-матрицам (или J-матрицам: найдена претендентная оптимальная 6-ти уровневая матрица J22 - замещающая первую "отсутствующую" C-матрицу Белевича для 22-го порядка, Juras-matrix, 2010).

С ростом порядка итогом численных алгоритмов поиска M-матриц являются "хаотические" матрицы с отмеченной выше пороговой приведенной нормой, если гипотеза верна, то они еще и оптимальные (B-матрицы). Первой матрицей в этом ряду является матрица 13-го порядка. Заметим, что для адамаровых и C-матриц это не так (барьер b общий для всех матриц, но оптимальные A и C лежат под, ниже). В теории детерминированного хаоса A и С-матрицам отвечают островки регулярности - фрактально повторяющиеся особенности первой и второй бифуркаций. В отличие от них B-матрицы могут быть положены в основу алгоритмов поиска спектров с качественно иным базисом (хаотическим).

Существуют алгоритмы пересчета матриц адамара по С-матрицам, кроме того, для базовых порядков 12 и 20 (те матрицы, которые нашел Адамар) найдены алгоритмы перехода от B матриц 3 и 5 порядков к C-матрицам 6 и 10 порядков, т.е. построена вся цепочка приведения от нижних порядков к старшим, аналогом которой является правило Сильвестра (Балонин, 2010).

КРИВАЯ МИРОНОВСКОГО

График m-нормы в зависимости от порядка матрицы будем называть для определенности кривой Мироновского.

Кривая Мироновского (над красным 1/√n)

Из рисунка видно, что кривая Мироновского аппроксимирует (нестрого) зависимость 1/√n и касается ее в точках n=2, 4, 8, и т.п., отвечающих обычным матрицам Адамара. Эта кривая, помимо первого изгиба Л, вычерчивает характерные буковки M. Средняя точка M (помимо 'странной' 22-й точки) описывается 1/√(n-1) и стремится к красной кривой. Это находимые аналитически C-матрицы порядков 2, 6, 10, 14 и т.п., но 22-я точка в этой последовательности отсутствует, так как 21=n-1 не есть сумма двух квадратов (признак, следующая такая матрица: 34-го порядка).

График приведенной умножением на √n нормы

Некоторое суждение о кривой Мироновского можно вынести и из графика приведенной умножением на √n нормы. Первые три (и даже четыре) буквы M убывают. Однако далее убывание сменяется вдруг неочевидным ростом, который может быть обусловлен погрешностью вычислений. Однако у C-матриц на данном интервале - первая особенность M22.

Программа, строящая все эти любопытные графики, основана на таблица вычисленных итерациями норм.

ПОСЛЕДОВАТЕЛЬНОСТЬ СИЛЬВЕСТРА

Обратим внимание на матрицу второго порядка. Если ее ортонормировать, то получим m-норму: величину максимального элемента 0.707.

A =
1
1
1
-1

Адамарова матрица четвертого порядка наследует ее структуру, замещая собой 1. Отсюда следует правило Сильвестра построения адамаровых матриц порядка 2k.

A =
A
A
A
-A

Эти матрицы стали именоваться адамаровыми после того, как Адамар в 1893 году построил промежуточные матрицы 12-го и 20-го порядков, он (или Палей, в статье 1933 г.) сформулировал 'гипотезу Адамара' о существовании всех остальных, кратных 4. Для порядков 1, 2, 4, 8, 12, 16, 20, 24 существует соответственно 1, 1, 1, 1, 2, 118, 6520, 43966313 эквивалентных классов нормализованных матриц Адамара по отношению эквивалентности перестановок строк и столбцов. Функциями Уолша назвывается семейство функций, образующих ортогональную систему, принимающих значения только 1 и −1 на всей области определения. Группа из 2k четных и нечетных функций Уолша (аналоги синусов и косинусов) образует матрицу Адамара, причем подсчет перемен знаков дает аналог частоты в разложениях Фурье.

изображения матриц Адамара

Существует еще неравенство Адамара: модуль определителя (объем n-мерного тела) ортогональной матрицы |nn/2| превалирует над всеми прочими определителями при вращении опорных вектор-столбцов. В 1933 тему продолжил англичанин Раймонд Пэли, указав алгоритм для части более сложных адамаровых матриц. В 1962 году 92-м порядком открыт счет адамаровым матрицам, находимым при помощи компьютера Baumert, Golomb и Hall. Ни порядок, ни гипотеза Адамара не исчерпаны.

Трудно обойти вниманием единичную матрицу, она ортогональна, перестановкой столбцов из нее получают ортогональную С-матрицу Пэли (Paley 1933) с нулями на диагонали. По m-норме она уступает адамаровой, но в отличие от нее существует при размерности 6. Ее еще называют conference-matrix.

С =
0
1
1
0

На третьем порядке единичная матрица уступает по m-норме ортогональной структуре, имеющей после нормирования столбцов целочисленные элементы (Мироновский)

M =
1
2
2
2
1
-2
2
-2
1

Эта матрица имеет различные эквивалентные реализации, среди них и такую

Свойства трехмерного пространства, таким образом, отличаются от пространства размерности 2, один из эйлеровых углов 'не довернут' до 45 градусов. Трехмерный чемодан, в который помещается такой недокрученный еж, получается самым компактным (пространственный феномен). Ранее едва ли отмечалось (третий порядок не соотносили с адамаровым построением), что C-матрица 6-го порядка составляется из блоков второго порядка на основе оптимальной трехмерной структуры (где матрица F=flip(A)=[1 1;-1 1])

C =
C
A
F
A
C
-F
F'
-F'
C

Минимальные по m-норме матрицы 5-го и 7-го порядков (простые числа) имеют трехуровневую и пятиуровневую структуры. Матрицы 9-го и 11-го порядков имеют четырехуровневую и шестиуровневую структуры (на единицу более 'прародителей'), следующие матрицы 13-го и 15-го порядков не разложились на уровни. Содержание гипотезы Адамара по отношению к такого сорта матрицам говорит о последовательностях матриц с нечетными порядками 5+4k, 7+4k, преемственных между собой по m-норме, стремящейся к B/√n (см. гипотезу ниже).

СУБОПТИМАЛЬНЫЕ МАТРИЦЫ

C-матрица Пэли 10-го порядка имеет норму 0.333. Опираясь на правило Сильвестра можно собрать матрицу того же порядка из оптимальных блоков 5-го порядка, при этом получим завышение нормы 0.3857. Матрицу 9-го порядка можно составить из матриц 3-го порядка

A
2A
2A
2A
A
-2A
2A
-2A
A

эта трехуровневая субоптимальная матрица имеет m-норму 0.4444. Матрица с заметно лучшей нормой 0.3943 имеет не 3, а 4-ре уровня. Таким образом, правило Сильвестра (и сходные) не всегда приводит к оптимальным матрицам.

ГИПОТЕЗА О МИНИМАЛЬНОЙ НОРМЕ ОРТОГОНАЛЬНЫХ МАТРИЦ

Мною высказано предположение (назовем так, гипотеза), что с повышением порядка кривая, в общем, не стремится к красной (адамаровой) линии 1. Существует иная полочка m/√n=b=1.14.., к которой стремятся вершины M хаотических матриц за исключением отдельных последовательностей.

Отдельно про 22-ю точку. Домик в 22-й точке указывает на то, что эту точку сложно прижать к единице! Это феномен, показывающий неординарность проблемы.

НОРМЫ ШИНТЯКОВА

Матрицы 1, 2, и 4 порядков являются одноуровневыми, матрица третьего порядка двууровневая. C-матрицы двууровневые c элементами 0 на диагонали и единичными вне (со знаками). Первая нетривиальная в этом смысле матрица, это матрица пятого порядка: трехуровневая, содержит (после нормирования) элементы 6, 3, 2. Затем идет пятиуровневая матрица седьмого порядка. Для этих двух матриц получены, в предположении, что структурирование по элементам произведено правильно, аналитические оценки норм 6/11 и (5+7√(7))/53 (Мироновский, Шинтяков, 2005).

 robots

ВЫЧИСЛИТЕЛЬНЫЙ АЛГОРИТМ

В разработанном варианте вычислительного алгоритма поиска m-матриц присутствует несколько важных деталей. Откоментирую их (поле открыто для новых предложений).

Фактор первый: начальное приближение. Сужение диапазона поиска резко сказывается на трудоемкости подхода, в чем легко убедиться, заменив рандомизированное случайное начальное приближение всего лишь суммой A+A'. Итерации замирают, не набрав силы. Симметричное представление, если оно есть, проще искать потом, перестановками.

Фактор второй: начальное сжатие. Поскольку цель итераций состоит в понижении m-нормы, формообразующую роль играет операция насыщения. Первое самое сильное сжатие, также, как и симметрирование, определяет последующий итерационный процесс. Профиль сжатия по мере итераций таже важен.

Фактор третий: перестановки. Периодические сжатия и восстановления формы матрицы, особенно простейшим ее QR-разложением, топчутся на месте. Перестановка наиболее изменяемых столбцов на первое место вызывает вращение ортогонального конструктива, так как сжатие заведомо меняет направление столбца, а ортогонализация не влияет на первый столбец, поворачивая все прочие оси.

Ниже профиль сжатия описывается разностным уравнением первого порядка (экспоненциальное сжатие). Для простоты демонстрации фокуса найдем адамарову матрицу четвертого порядка. При ортогонализации методом сингулярного разложения (устаревшее действие) основа смещается в силу сложности алгоритма, без перестановок. Выводятся параметр сжатия P и текущая m-норма, стремящаяся к 1/√4=0.5.

Исходный алгоритм без перестановок


if tick=0,
A=rands(4), norms(A), m=max(abs(A)),  
% СТАРТОВОЕ ПОНИЖЕНИЕ НОРМЫ,
P=0.9, A=sat(A P*m), A=SVD(A), m=max(abs(A)), g=m,  
end,

% ПРОФИЛЬ ПОНИЖЕНИЯ НОРМЫ,
P=0.995*P+0.005, A=sat(A P*m),
% ВОССТАНОВЛЕНИЕ ОРТОГОНАЛЬНОСТИ МАТРИЦЫ, 
A=SVD(A), m=max(abs(A)), mesh(A), P=?, m=?,
% ГРАФИК ПОНИЖЕНИЯ M-НОРМЫ, 
g={[g m]}, ball(g), ticker(1),

function: SVD(A),
var S U V, S={A'*A}, [V S]=eig(S), 
U={A*V}, U={U/S}, norms(U), norms(V), tr(V), A={U*V}, 
return A, 
end,

 admin

МАТРИЦЫ 5-го и 7-го ПОРЯДКОВ

Следить по внешнему виду матрицы за ходом итерационного процесса неудобно, он малоинформативен. Часть итераций можно не просматривать вовсе, это ускорит поиск. Информативным фактором является график распределения элементов матрицы по их абсолютным величинам. Процедура ортогонализации orth() дана здесь в первой ее редакции, далее будет еще оптимизирована.


if tick=0, i=0,
A=rands(5), norms(A), m=max(abs(A)), 
% СТАРТОВОЕ ПОНИЖЕНИЕ НОРМЫ,
P=0.9, A=sat(A P*m), A=SVD(A), 
m=max(abs(A)), u=columns(A),  
end,

% ПРОФИЛЬ ПОНИЖЕНИЯ НОРМЫ,
P=0.995*P+0.005, A=sat(A P*m),
% ВОССТАНОВЛЕНИЕ ОРТОГОНАЛЬНОСТИ МАТРИЦЫ, 
A=SVD(A), m=max(abs(A)), P=?, m=?,
% ПРОПУСКАЕМ ОТОБРАЖЕНИЕ,
if i<50, i=i+1, else, i=0,
% ГРАФИК НОРМ ЭЛЕМЕНТОВ,  
mesh(A), u=columns(A), ball(u), 
end, 
ticker(1),

function: SVD(A),
var S U V, S={A'*A}, [V S]=eig(S), 
U={A*V}, U={U/S}, norms(U), norms(V), 
tr(V), A={U*V}, return A, 
end,

function: columns(A),
var u uj, u=A[0],
for var i=1:colm(A), u=join(u A[i]), end, u={abs(u)},
for var i=0:size(u), for var j=i:size(u), 
if u[i]>u[j], uj=u[i], u[i]=u[j], u[j]=uj, 
end, end, end,
return u,
end,

Не каждый процесс с матрицей 5-го порядка завершается с нормой m=0.545, эту матрицу находить заметно сложнее. У нее три полочки элементов в пропорциях 6, 3, 2. Оптимальная матрица 7-го порядка имеет пять уровней, получить три четверки в m=0.444 для нее этим алгоритмом вполне реально. Существует 2-х уровневая структура с m=0.446 (21-н элемент на нижней полке). В некотором смысле это 3 полочки одинакового уровня по 7-м элементов. Матрица 7-го порядка, это первая матрица, у которой нерегулярная структура выигрывает, т.к. содержит 6+3+4+6=19-ть элементов внизу (на два меньше).

Трехуровневая и пятиуровневая матрицы 5-го и 7-го порядков
у матриц 3-го и 5-го порядков на полочках по n элементов (как и у 11-го)

Перестановки ведут к тому, что от итерации к итерации обрабатываются весьма различные между собой матрицы, принадлежащие некоторому классу эквивалентности. Это можно представить - как вращение базиса с периодическим возвращением его на уточненную позицию. Подкручиваемая матрица легче сходится по норме, однако сложно удержать во внимании одну структуру в ее развитии. Симметрирование мешает сходимости, его можно делать только для просмотра, вводя ловушки для желаемых быть увиденными конфигураций матрицы.

 admin

МНОГОУРОВНЕВЫЕ МАТРИЦЫ

Двухуровневая матрица шестого порядка находится тем же алгоритмом заметно проще. Это оптимальная С-матрица Палея, ее m-норма равна 1/√(n-1)=0.447.

Первое серьезное препятствие алгоритму представляет собой матрица 9-го порядка. Найден предел m-нормы четырехуровневой структуры (3+√3)/12 = 0.3943. Пора применить ортогонализацию Грама-Шмидта с перестановками, что гарантирует вращение базиса столбцов.


if tick=0, i=0,
P=0.95, A=rands(9), norms(A), m=max(abs(A)), 
end,

% СОРТИРОВКА,
A=sortm(A), 
% ПРОФИЛЬ ПОНИЖЕНИЯ НОРМЫ,
P=0.9995*P+0.0005, A=sat(A P*m), 
% ВОССТАНОВЛЕНИЕ ОРТОГОНАЛЬНОСТИ МАТРИЦЫ, 
A=orth(A), m=max(abs(A)), P=?, m=?,
% ПРОПУСКАЕМ ОТОБРАЖЕНИЕ,
if i<50, i=i+1, else, i=0,
% ГРАФИК НОРМ ЭЛЕМЕНТОВ,  
mesh(A), u=columns(A), ball(u),  
end, 
ticker(1),

function: orth(A),
var s a q qq Q, Q={A}, q={A[0]},  
a=norm(q), Q[0]={q/a},
for var i=1:colm(A), a={A[i]}, q={a},
for var j=0:i-1, qq={Q[j]}, 
s={a'*qq}, s={s*qq}, q={q-s}, end,
a=norm(q), Q[i]={q/a}, end,    
return Q,
end,

function: sortm(A),
var i j ix ii q qm Q, Q={A},
q=max(abs(A[0])),
for i=1:colm(A), qm=max(abs(A[i])), q={[q qm]}, end, ix=line(q), 
for i=0:size(q), 
for j=i:size(q), qm=q[i], ii=ix[i], 
if qm<q[j], q[i]=q[j], q[j]=qm, ix[i]=ix[j], ix[j]=ii, end, end, end, 
for i=0:size(ix), A[i]=Q[ix[i]], end,
return A,
end,

function: columns(A),
var u uj, u=A[0],
for var i=1:colm(A), u=join(u A[i]), end, u={abs(u)},
for var i=0:size(u), for var j=i:size(u), 
if u[i]>u[j], uj=u[i], u[i]=u[j], u[j]=uj, 
end, end, end,
return u,
end,

Итерациями находятся четырехуровневые и пятиуровневые матрицы с очень близкими между собой значениями норм 0.3943 и 0.3952. Пятиуровневая матрица регулярна в том смысле, что число элементов на ее полочках равно 9!!! Но нерегулярная матрица ее превосходит.

Матрицы с четырьмя и пятью уровнями.

 admin

Матрица порядка n=11 с m-нормой 0.343 имеет 6 уровней с абсолютными значениями 0.0454, 0.1567, 0.2440, 0.3089, 0.3357 (по 11 элементов) и с 0.3429 в остатке.


if tick=0, i=0,
P=0.95, A=rands(11), norms(A), m=max(abs(A)), 
end,

% СОРТИРОВКА,
A=sortm(A), 
% ПРОФИЛЬ ПОНИЖЕНИЯ НОРМЫ,
P=0.9995*P+0.0005, A=sat(A P*m), 
% ВОССТАНОВЛЕНИЕ ОРТОГОНАЛЬНОСТИ МАТРИЦЫ, 
A=orth(A), m=max(abs(A)), P=?, m=?,
% ПРОПУСКАЕМ ОТОБРАЖЕНИЕ,
if i<50, i=i+1, else, i=0,
% ГРАФИК НОРМ ЭЛЕМЕНТОВ,  
mesh(A), u=columns(A), ball(u),  
end, 
ticker(1),

function: orth(A),
var s a q qq Q, Q={A}, q={A[0]},  
a=norm(q), Q[0]={q/a},
for var i=1:colm(A), a={A[i]}, q={a},
for var j=0:i-1, qq={Q[j]}, 
s={a'*qq}, s={s*qq}, q={q-s}, end,
a=norm(q), Q[i]={q/a}, end,    
return Q,
end,

function: sortm(A),
var i j ix ii q qm Q, Q={A},
q=max(abs(A[0])),
for i=1:colm(A), qm=max(abs(A[i])), q={[q qm]}, end, ix=line(q), 
for i=0:size(q), 
for j=i:size(q), qm=q[i], ii=ix[i], 
if qm<q[j], q[i]=q[j], q[j]=qm, ix[i]=ix[j], ix[j]=ii, end, end, end, 
for i=0:size(ix), A[i]=Q[ix[i]], end,
return A,
end,

function: columns(A),
var u uj, u=A[0],
for var i=1:colm(A), u=join(u A[i]), end, u={abs(u)},
for var i=0:size(u), for var j=i:size(u), 
if u[i]>u[j], uj=u[i], u[i]=u[j], u[j]=uj, 
end, end, end,
return u,
end,

Разрешение по уровням становится трудным, тем не менее, вот, кажется, оно (и это найдено не на инструменте с удвоенной разрядной сеткой).

СОПОСТАВЛЕНИЕ

Сопоставим матрицы. Число уровней 'все более охотно' растет. Для первой пары 5-го и 9-го порядков отличие слоев состоит всего в одном элементе, но далее - элементов становится больше. Верхушка сглаживается, профиль становится выпуклым. Для матрицы 13-го порядка прогнозируется банальный четырехуровневый выпуклый же сэт, однако компьютерный расчет (у матриц есть своя драматургия) приводит к весьма неожиданной картине.

Сопоставление матриц 5-го и 7-го, 9-го и 11-го порядков



Rambler's Top100