Матриц адамара нечетного порядка balonin N. A., Myronovskiy L. A

ИНТЕРАКТИВНОЕ ВЫЧИСЛЕНИЕ
МАТРИЦ АДАМАРА НЕЧЕТНОГО ПОРЯДКА*



Balonin N.A., Myronovskiy L.A.


Рассматриваются классические матрицы Адамара. Вводятся
M-матрицы как возможное обобщение матриц Адамара на случай n нечетного порядка. Описываются компьютерные алгоритмы их нахождения.
Classical Hadamard matrices are considered. M-matrices as a possible generalization of Hadamard matrices in the case of odd order n introduced. A computer algorithm for finding such matrices is described.

Введение.

Матрицы Адамара находят широкое применение в теории кодирования (коды, исправляющие ошибки), теории планирования многофакторных экспериментов (ортогональные блок-схемы) и прочих областях.
Отыскание их для больших четных и особенно нечетных n сопряжено со значительными трудностями, в связи с чем текущая информация по ним публикуется в сетевых справочниках, например, в Wolfram Research http://mathworld.wolfram.com/HadamardMatrix.html
Средства для знакомства с соответствующей тематикой помещены на ресурсе, оснащенном сетевой версией системы MatLab, которая позволяет осуществлять интерактивные вычисления с пользовательской вариацией алгоритма http://artspb.com/books/hadamard/index.php
Как известно, матрицы Адамара существуют далеко не при всех четных порядках n, а при нечетных n вообще не существуют. В работе [1] введено обобщение матриц Адамара на случай нечетных порядков и найден ряд таких матриц для n<16.
Сложность поиска матриц при больших n резко возрастает, что позволяет использовать эту задачу как тестовую для проверки производительности суперкомпьютеров в интерактивном режиме.
Ниже приводятся необходимые сведения для постановки такого вычислительного эксперимента.

* Работа выполнена при поддержке РФФИ, грант 08-08-00228

Известные результаты.

Напомним, что матрицей Адамара порядка n называется такая nn – матрица А с элементами 1, что ААТ = nE, где Е – единичная матрица [2].
Простейшая матрица Адамара имеет вид
она ортогональна ААТ=2E и симметрична.
Для существования матриц Адамара порядка n>2 необходимо, чтобы n делилось на 4. Гипотеза о том, что это условие является и достаточным, пока не доказана. Для практического получения матриц Адамара можно использовать команду

hadamard

пакета MATLAB, она позволяет строить матрицы Адамара для случаев, если n, n/12 или n/20 являются степенями двойки. К сожалению, сюда не входят такие n, кратные четырем, как 28, 36, 44, 52, 56, 60 и другие, хотя для них уже давно найдены матрицы Адамара.
У матриц Адамара максимальный по модулю элемент минимален на классе ортогональных матриц. Будем далее обозначать максимальный по модулю элемент ортогональной матрицы через α. Величина этого элемента для матриц Адамара с /, где константа с=1.
Для нечетных n известно лишь несколько оптимальных (ортогональных, с минимальным по модулю максимальным элементом) матриц для небольших значений n. Информация о них приводится ниже.

Оптимальные матрицы нечетного порядка (М-матрицы).

В работе [1] матрицы, доставляющие решение задачи о поиске ортогональных матриц с минимальным по модулю элементом для нечетных n, названы М-матрицами. Для них можно выделить три задачи.
Задача 1. Поиск конкретных М-матриц для различных значений n.
Задача 2. Определение точной нижней границы α* для величины максимальных по модулю элементов М-матриц α в зависимости от n:
Задача 3. Определение числа L уровней элементов в М-матрице при разных n.
Следует ожидать, что решение всех трех поставленных задач будет зависеть от того, какой остаток при делении на 4 дает нечетное число n (1 или 3). Соответственно, множество М-матриц распадается на два подмножества, отличающихся нижними границами, числом уровней L и типом матриц.

Алгоритм численного поиска адамаровых матриц.

Чисто аналитическое решение рассматриваемой задачи найти затруднительно, поэтому целесообразно использовать интерактивные сетевые ресурсы. Опишем разработанный авторами вычислительный алгоритм. Он строится на основе итераций, в которых на каждом шаге максимальный по модулю элемент α матрицы уменьшают по правилу
α ­k +1= α k k/(k+p) для ее элементов, где k – номер итерации, p>0 – некоторое число. Так как после этого матрица перестает быть ортогональной, ее снова ортогонализируют путем вычисления полярного разложения. Полярное разложение представляет данную матрицу в виде произведения ортогональной и симметричной матриц. В дальнейшем используется первая из них. Итерационный процесс сходится к некоторой ортогональной матрице, далее его многократно повторяют.
Он может быть записан в виде следующего алгоритма:
1. В качестве начального приближения берется квадратная невырожденная матрица.
2. Матрица заменяется ортогональным сомножителем ее полярного разложения.
3. Уменьшается максимальный по модулю элемент матрицы.
4. Производится возврат к пункту 2 до тех пор, пока процесс не сойдется к определенной матрице.
Этот алгоритм был реализован в сетевом MATLAB
A=rands(4), norms(A), R=0.8, a=max(abs(A)), g=zero(1),
for i=0:40, g[i]=a, if i=10, R=0.8, end,
R=0.99*R+0.01, A=sat(A R*a), call A=SVD(A), a=max(abs(A)),
end, mesh(A), ball(g), a=?,
function: SVD(A),
var S U V, S=calc(A'*A), [V S]=eig(S),
U=calc(A*V), U=calc(U/S), norms(U), norms(V),
tr(V), A=calc(U*V), return A,
end,

Гипотеза о максимальном элементе

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

Структура

оптимальных матриц.

К настоящему времени найдены М-матрицы для n = 3, 5, 7, 9, 11.
Для случая n = 3 оптимальная матрица имеет вид
.
Отношение максимального элемента к минимальному k=2.
Она ортогональна и симметрична, величина ее максимального элемента равна α=2/3. Матрица содержит два типа элементов, т.е. является двухуровневой. Она связана с геометрической задачей о вписывании данного правильного октаэдра в куб минимального размера [3].
Для случая n = 5 оптимальная матрица оказалась трехуровневой:
. (3)
Отношение максимального элемента к минимальному k=3.
Она также ортогональна и симметрична, величина ее максимального элемента α=6/11. Из 25 ее элементов 15 равны 6/11, т.е. находятся на верхнем уровне и по пять элементов на двух других. Таким образом, элементы верхнего уровня составляют 60% от общего числа (у матрицы М3 – 67%, а у матриц Адамара – 100%).
Для случая n = 7 оптимальная матрица оказалась пятиуровневой со значением :
Элементы матрицы иррациональны, они содержат :
, при нормировке все их надо разделить на .
В случае n=9 лучшая из найденных матриц имеет 4 уровня и показатель В ней уже встречается иррациональность типа «корень из корня», возникающая при решении биквадратного уравнения. Распределение модулей элементов матрицы M9 по уровням весьма неравномерно. Так, на нижнем уровне находится один элемент, на двух следующих – 24 и 16 элементов соответственно. На верхнем уровне находится 40 элементов, что составляет около 49% от общего числа.
Для n=11 лучшая ортогональная матрица, найденная в MATLAB, имеет шестиуровневую структуру, см. рис. 1. Отношение максимального элемента к минимальному k =7.5599

Рис.1. Распределение числа элементов матрицы M11 по уровням
Распределение абсолютных величин элементов матрицы M11 по уровням показано на рис. 1. Верхний уровень содержит 66 элементов, остальные – по 11 элементов, всего 66+55=121 элемент.
Распределение количества уровней в матрицах в зависимости от их порядка показано на рис. 2.

Рис.2. Распределение количества уровней

Заключение.

Как видно, с ростом размерности матрицы происходит нерегулярное расслоение элементов, притом, что более половины от их количества совпадает по модулю с максимальным элементом – у матриц Адамара 100%. Количество уровней матрицы M13 находится под вопросом, ответ на который требует более мощных вычислительных ресурсов. Кроме оптимальных вариантов наблюдаются интересные субоптимальные с заметно меньшим количеством уровней – отсюда возникает предположение, что и такие задачи, связанные с оптимизацией не только норм элементов, но и структуры – можно решать.

Литература:


1. Балонин Н.А., Мироновский Л.А. Матрицы Адамара нечетного порядка. //Информационно-управляющие системы. 2006, №3. С.46-50.
2. Hadamard J. Resolution d’une question relative aux determinants// Bull. sci. math., 1893, v.2. Pp. 240-248
3. Голуб Дж., Ван Лоун Ч.Матричные вычисления. М: Мир,1999. - 549 с.
4. Медяник А.И. Вписанный в куб правильный симплекс и матрицы Адамара полуциркулянтного типа // Матем. Физика, анализ, геометрия, 1997, т.4., N4, с. 458-471.
5. Шинтяков Д.В. Алгоритм поиска матриц Адамара нечетного порядка. Девятая научная сессия ГУАП: Сб. докл. //ГУАП. СПб., 2006
prakticheskaya-rabota-1-sozdanie-bazi-dannih-v-microsoft-access-2010.html
prakticheskaya-rabota-1-sozdanie-web-stranici-na-html.html
prakticheskaya-rabota-1-stranica-3.html
prakticheskaya-rabota-1-stranica-4.html
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат