§ 5. Матричный метод обобщенного представления быстрых ортогональных преобразований

А. Идеи обобщенного матричного представления БПФ, БПУ, БПХ и других быстрых дискретных ортогональных преобразований.

Исследования, результаты которых отражены в статье [165], в книге [99], в работах [124, 125] и [127], в книге [22] и в ряде других упоминаемых далее книг и статей, привели их авторов к выводу о возможности единообразного матричного описания различных ортогональных преобразований. При таком описании преобразуемая исходная последовательность представляется в виде вектора-столбца, заданное преобразование — в виде соответствующей ему матрицы. Умножая эту матрицу на указанный вектор-столбец, получаем вектор-столбец, содержащий результат преобразования, являющийся спектром заданной последовательности. О матрицах, векторах-столбцах как частном виде матриц, правилах матричной алгебры будет рассказано в разделе Б.

Используя эти правила, заменяют одномерное преобразование рядом более простых преобразований и приходят к многомерным преобразованиям, что позволяет уменьшить общий объем вычислений и ускорить их выполнение. В этом отношении данная процедура аналогична той, с которой мы познакомили читателя, описывая БПФ. Там исходная последовательность разделялась на части. Были приведены формулы, связывающие ДПФ частичных последовательностей и общей последовательности. Одномерный массив данных делился на части, образуя многомерный массив, вычисления сводились к ДПФ отдельных пар элементов последовательности. При матричном представлении информации исходная матрица заменяется вычисляемой по определенным правилам суммой слабозаполненных матриц, каждая из которых содержит лишь незначительное количество отличных от нуля элементов. При матричном выполнении БПФ, БПУ, БПХ и других быстрых ортогональных преобразований матрицы соответствующих преобразований оказываются различного вида. Однако во всех случаях в конечном счете матрица представляется в форме, при которой производятся относительно простые вычислительные операции.

Б. Краткие сведения о матричной алгебре.

Матрицей называют пред ставленную в виде таблицы совокупность вещественных или

комплексных чисел Для матрицы приняты обозначения или Или же каждую из матриц обозначают одной лишь буквой, например, это буквы . В общем случае в матрице имеется строк и столбцов (рис. 4.15, а). Числа являются элементами матрицы (выражение той же, что и на рис. 4.15, а матрицы при более кратком указании ее состава, дано на рис. 4.15, б). Если то матрицу называют векторомгстолбцом, если же то вектором-строкой. Применяются также следующие соответствующие им названия: матрица-столбец или просто столбец и матрица-строка или просто строка. Одномерный вектор называют скаляром.

При получаем квадратную матрицу порядка. Транспонированная матрица отличается от исходной матрицы А тем, что ее строки являются столбцами исходной матрицы, а ее столбцы — строками последней. Если матрицу называют симметрической. Приняты также следующие определения. Матрица, у которой все элементы называется нулевой матрицей. Диагональная матрица — это такая матрица, у которой равны нулю все элементы, кроме находящихся на главной диагонали элементов Если эти элементы одинаковые, матрицу называют скалярной, а при равенстве каждого из этих элементов единице — единичной матрицей. Для единичной матрицы приняты обозначения или [1] или .

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

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

Основные действия, выполняемые с матрицами: умножение матрицы на скаляр, сложение матриц, умножение матриц. При умножении матрицы А на скаляр а получается матрица, каждый элемент которой определяется как а

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

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

Умножение матриц возможно при условии, что число столбцов матрицы А равно числу строк матрицы В. Элемент результирующей

(см. скан)

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

Частным случаем произведения матрицы на матрицу является произведение содержащей столбцов матрицы на вектор-столбец с строками. В результате умножения получается вектор-столбец, в котором тоже имеется строк: Произведение матриц обладает следующими свойствами: Однако в общем случае Это иллюстрируется примером на рис. 4.15, г. Матрицы, для которых называются коммутативными. Коммутативны диагональные матрицы.

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

Кронекеровской суммой матриц называется клеточная матрица А, построенная так, как показано на рис. Для кронекеровской суммы матриц примем обозначение Кронекеровские суммы матриц обладают следующими свойствами:

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

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

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

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

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

Упомянем еще о некоторых других понятиях матричной алгебры (см. [64]), с которыми приходится встречаться при ознакомлении с литературой, посвященной рассматриваемым вопросам. Используется понятие ранга матрицы. Прежде чем пояснить его, приведем краткие сведения об определителях матриц и их минорах. Детерминантом или определителем квадратной матрицы размера называют алгебраическую сумму всех возможных произведений элементов матрицы, взятых по одному из каждой ее строки и из каждого ее столбца с учетом указываемого далее правила знаков.

Для определителя матрицы А приняты обозначения или Изображается определитель так, как показано на рис. 4.15, ж. Вычеркнув в определителе любые строк и столбцов и составив определитель из находящихся на их пересечении элементов, получим определитель 1-го порядка, называемый минором 1-го порядка исходного определителя. Определитель порядка, оставшийся в исходном определителе после вычеркивания указанных строк и столбцов, называется дополнительным к упомянутому выше минором. Под алгебраическим дополнением к элементу рассматриваемому как минор первого порядка исходного определителя, имеется в виду дополнительный минор к элементу который берется со знаком Всякий определитель может быть представлен в вице суммы произведений элементов какой-либо строки или какого-либо столбца на соответствующие этим элементам алгебраические дополнения. Это используется для раскрытия и вычисления определителей.

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

полинома называются собственными числами матрицы. Имеет место равенство Сумму обозначаемую как называют следом матрицы.

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