03.11.2017 admin

1.1. Общие понятия и определения


Основной объект этой книги, как следует из ее названия, – ортогональные матрицы.

Определение 1. Ортогональная матрица A, это квадратная матрица некоторого порядка n, удовлетворяющая квадратичному уравнению связи

A'A=I,


где I – единичная матрица.

Ортогональная матрица, иначе, – это матрица координат некоторого ортонормированного базиса. Вместе с тем, нормирование столбцов или строк матриц Адамара H, например, и сходных им нарушает условие простого вида их элементов, которые по определению принадлежат множеству {1, –1}. Для их нахождения используется итерационный алгоритм, предложенный еще Сильвестром.

Алгоритм Сильвестра. Алгоритм удвоения порядка описывается формулой [A,A;A,–A]. Его инвариантом является свойство ортогональности столбцов или строк матрицы.

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

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

Мы исходим из того, что нормированная по строкам или столбцам матрица Адамара не перестает, по существу, ею быть. Меняется только интерпретация элементов, их модули перестают быть равными единице и становятся равными другому числу a.

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

Прежде всего на первое место выдвигаются понятия уровень матрицы и ее уровневость. Давайте уточним их определениями, чтобы быть точными.

Определение 2. Уровнями матрицы будем называть численные значения, которым равны ее элементы.

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

Например, ортогональная матрица Адамара – матрица с элементами {a, –a}, a=1/n1/2.

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

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

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

Определение 3. Матрица называется k-уровневой, если все элементы ее принадлежат k уровням соответственно.

Введение уровней позволяет формировать матрицу в числовом, символьном и графическом видах, в последнем случае возникает понятие цветности. Понятие цветности не широко, но применяется в математике, его использовал, например, Эйлер. Существует его теорема о красках []. Для характеристики математических объектов это не лишнее понятие.

Например, матрица Адамара – двухцветная, а Белевича со значениями элементов {1, –1, 0} – трехцветная матрица.

Среди двухуровневых матриц можно указать также матрицы с диагональным преобладанием: единичную матрицу I и D-матрицу, элементы которой равны 2 за вычетом диагонали с числами 2–n, т.е. в нотации языка матричных вычислений D=(2I–nI), см. рис. 1.



Рисунок 1. Двухцветная матрица с диагональным преобладанием



Легко заметить, что столбцы матриц D ортогональны. Уровневость, это важнейший инвариант матриц. Он может рассчитываться применительно к элементам или применительно к модулям (нормам, абсолютным значениям) элементов. Матрица Адамара – это, в общем, однуровневая по модулям элементов матрица.

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

Определение 4. Максимум m абсолютных значений элементов ортогональной матрицы назовем ее m-нормой.

Для подсчета m-нормы более широкого класса матриц с ортогональными столбцами (строками) их предварительно нормируют, переводя в ортогональные. Этот показатель достигает своего верхнего амплитудного значения m=1 у единичных матриц. Для всех остальных матриц m<1.

У ортогональных матриц Адамара с элементами {a, –a} норма m=a=1/n1/2.

Для того, чтобы вычислить инвариант, отличающий матрицу Адамара от всех остальных ортогональных матриц, достаточно число m умножить на n1/2.

Определение 5. Адамаровой нормой (h-нормой, приведенной m-нормой) матрицы порядка n называется число h = m n1/2.

Норма Адамара – инвариант преобразования Сильвестра.

Приведенная норма для всех матриц Адамара h = 1. Для других матриц она больше единицы. Таким образом, матрица Адамара H – это минимаксная ортогональная матрица.

Для оценивания эффективности работы итерационных алгоритмов поиска М-матриц полезна метрика, вводимая следующими четырьмя определениями.

Определение 5.1. Энтропией ортогональной матрицы будем называть логарифм нормы Адамара (логарифм приведенной нормы) lg(h).

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

Определение 5.2. Константой Балонина будем называть норму Адамара М-матрицы тринадцатого порядка, она отличается от нормы h=1 матриц Адамара аддитивной добавкой

B=h13=m131/2=1+δ=1.117136,


аппроксимирующее добавку значение δ≅21/2/12. Это не столько показатель этой именно матрицы, сколько интегральный параметр слоя хаотических матриц, к которому матрица тринадцатого порядка принадлежит. Игрою вездесущего случая для этой М-матрицы m≅0.31, так что B≅0.31⋅131/2.

Определение 5.3. Информативность матрицы (в отличие от ее энтропии) будем оценивать по показателю i=lg(h–δ)/lg(1–δ).

Низкая информативность М-матрицы тринадцатого порядка принята за эталон, у всех таких матриц она в точности или приближенно равна нулю. Единичные и D-матрицы – у них h>>B, показатель имеет отрицательное значение. У матриц Адамара этот показатель положителен и достигает своей амплитуды – единицы.

Определение 5.4. Информационный барьер – понятие, характеризующее сходимость алгоритмов – область адамаровых норм матриц хаотических аттракторов, порождаемых итерационными алгоритмами, лежащая вблизи B.

Обратим внимание, что относительно легко находимые начальные М-матрицы до двенадцатого порядка включительно, имеют приведенную норму выше константы B. Далее начинаются серьезные проблемы поиска таких матриц.

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

Понятие минимаксной ортогональной матрицы шире, в общем, понятий матриц Адамара и Белевича. Оно охватывает эти матрицы и другие матрицы нечетных и четных порядков. Именно к ним будет направлен наш интерес.

Приведенная норма D-матриц резко растет с увеличением порядка. Приведенная норма трехуровневых матриц Белевича, напротив, стремится к единице. Это минимаксная ортогональная матрица для порядков, на которых двухуровневых матриц Адамара не существует.

Заметим, вкратце, что приведенную норму для матриц Белевича выгоднее считать по иной формуле ν = m (n–1)1/2. Именно это число будет инвариантом ν=1 матриц Белевича, т.е. инвариантом того преобразования, которое связывает эти ортогональные матрицы.

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

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

Определение 7. М-матрица в узком смысле этого слова, это минимаксная ортогональная матрица.

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

Определение 8. М-матрица в широком смысле этого слова, это ортогональная матрица, локально-оптимальная по m-норме.

Зажав количество уровней ортогональной матрицы в узком диапазоне, мы получаем, как правило, только локально-оптимальные матрицы.

Варьируя значения элементов, т.е. расширяя уровневость, приобретаем возможность получить более оптимальный по интересующему нас показателю (m-норме) вариант, который может оказаться, в итоге, абсолютным экстремумом.

Матрицы Адамара H, это тот редкий случай, когда оба важных инварианта, различающих ортогональные матрицы между собой, приведенная m-норма и уровневость, минимальны.

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

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


Литература.

Дынкин Е.Б., Успенский В.А. Математические беседы. – 2-е изд. – М.: ФИЗМАТЛИТ, 2004. 240 с. – (Школьная библиотека физико-математической литературы) – ISBN 5-9221-0369-5.

Hide

Rambler's Top100