Специальные матрицы. Представление матриц

 

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

Первое, как правило, труда не представляет и часто используется в формировании схем итерационных методов решения СЛАУ. Здесь, как правило, матрица представляется в виде суммы двух или трех матриц. Например, , – лево треугольная матрица, состоящая из элементов квадратной матрицы , находящихся под главной диагональю, – право треугольная матрица, состоящая из элементов квадратной матрицы , находящихся над главной диагональю, а – диагональная матрица, состоящая из элементов главной диагонали матрицы . Остальные элементы матриц , и полагают равными нулю.

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

4.3.1. -представление

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

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

Разложение единственно с точностью до диагональных элементов.

(по индукции)

Для утверждение очевидно: , где один из множителей может быть взят произвольно.

Пусть утверждение теоремы верно для матриц порядка . Покажем, что она верна для матриц порядка . Разобьем матрицу на клетки: , где и – векторы. Искомые матрицы и представим аналогично матрице в клетчатом виде: , .

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

Осталось определить лишь диагональные элементы и , воспользовавшись равенством или . Это всегда возможно, если значение одного из чисел или зафиксировать отличным от нуля, тогда второе однозначно определиться. Теорема доказана. ■

Выведем формулы разложения. Рассмотрим для этого матричное равенство , которое в поэлементном виде дается формулой

, (4.3.1)

которая является произведением вектора-строки матрицы на вектор-столбец матрицы .

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

Поскольку , при и , при , то равенство (4.3.1) разбивается на два:

(4.3.2)

и

(4.3.3)

Из (4.3.2) имеем , (4.3.4)

из которой определяются элементы матрицы .

Из формулы (4.3.3) получаем , (4.3.5)

которая определяет элементы матрицы .

При вычислении по формулам (4.3.4) и (4.3.5) неопределенности не наступает, если счет вести по строкам обеих матриц сразу – с помощью пар индексов : , , ..., , , , ..., , ..., , , ..., .

Часто фиксируют диагональные элементы матрицы , полагая их равными единице. Это позволяет делать разложение не вводя дополнительных матриц в программу и хранить полученные матрицы на месте исходной матрицы . В формулах (4.3.4) и (4.3.5) при этом следует заменить символы и на .

Пример: Осуществить -разложение матрицы .

Решение: Зафиксируем в матрице элементы главной диагонали, положив их равными 1. Матрицы и будут иметь вид: , . Найдем неизвестные элементы в следующем порядке (по строкам обеих матриц): , , , , применяя формулы (4.3.4) и (4.3.5).

; ; ; .

В итоге: , . Проверка умножением подтверждает правильность разложения: .

Замечание: Появление в ходе разложения нулевого значения элемента главной диагонали матрицы говорит о вырожденности главного минора -го порядка матрицы и невозможности ее LU-разложения. Следовательно, нет необходимости проверять условие отличия от нуля главных миноров матрицы (задачи весьма трудоемкой) до начала процедуры разложения.

Замечание: Условие отличия от нуля главных миноров матрицы – достаточно жесткое. Разложение не может быть осуществлено даже для такой «хорошей» матрицы, как , получаемой из единичной матрицы перестановкой строк. Для разложимости невырожденной матрицы , следует использовать матрицы перестановок, умножая их слева на матрицу для перестановки строк и(или) справа – для перестановки столбцов.

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

Будем говорить, что матрица имеет нижнюю ширину ленты , если для , и верхнюю ширину ленты , если для . Ширина ленты матрицы – есть число .

Например, матрица размерности имеет нижнюю ширину ленты =1, верхнюю ширину ленты = 2 и ширину ленты матрицы =4. Крестиками отмечены ненулевые, в общем случае, элементы.

Квадратная ленточная матрица с нижней и верхней шириной ленты равной называется -диагональной.

При имеем трехдиагональную, а при – пятидиагональную матрицу.

Формулы (4.3.4) и (4.3.5) для -диагональной матрицы приобретают вид:

, (4.3.6)

. (4.3.7)

В случае трехдиагональной матрицы для элементов -ой строки имеем:

; ; ; . (4.3.8)

Все остальные элементы равны нулю. В первой строке не следует пользоваться первой формулой, а в последней строке – последней.

Пример: Осуществить - разложение трехдиагональной матрицы .

Решение:

При : ; ; .

При : ; ; ; .

При : ; .

Т.о. , .

Проверим умножением.

. Разложение верно.

 

4.3.2. -представление эрмитовых матриц
(метод квадратного корня)

 

Важный в приложениях класс матриц – эрмитовы матрицы.

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

Очевидно, что эрмитова матрица на главной диагонали содержит лишь действительные числа.

Замечание: Если все элементы матрицы – действительные числа, то условие эквивалентно условию . Матрица в этом случае называется симметричной.

-разложение эрмитовой матрицы – это представление квадратной матрицы в виде произведения право-треугольной матрицы , диагональной матрицы и матрицы , которая является лево-треугольной (как транспонированная право-треугольной матрицы ).

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

при ; (4.3.8)

или

при (4.3.9)

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

при из (4.3.9) получим откуда определим диагональные элементы первой строки матриц и :

и ;

из (4.3.8) имеем и, следовательно, определяются все остальные элементы строки матрицы :

, .

Рассмотрим . Формула (4.3.9) имеет вид , откуда определим диагональные элементы второй строки:

и .

Из (4.3.8), при , имеем , откуда

, .

В общем случае, будем иметь следующие рабочие формулы:

, , (4.3.10)

, . (4.3.11)

В случае вещественной симметричной матрицы в -разложении и матрица представима в виде . Формулы (4.3.10) и (4.3.11) упрощаются (схема разложения Холецкого):

, (4.3.12)

, . (4.3.13)

Вещественность и положительность элементов здесь будет лишь в случае положительно определенной матрицы . Напомним

Матрица называется положительно определенной, если .

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

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

Пример: Разложить положительно определенную симметричную матрицу методом квадратного корня (по схеме Холецкого).

Решение.

Используем формулы (4.3.12), (4.3.13).

При : ; ; .

При :

; .

При : .

Таким образом, , и

.

Проверьте разложение умножением.

 

4.3.3. Представление через ортогональные и унитарные
матрицы

 

Вещественная матрица называется ортогональной, если .

Ортогональная матрица состоит из векторов столбцов, ортогональных между собой: , т.е. . Здесь – -й и -й столбцы соответственно, – символ Кронекера.

Из определения следует, что:

1) Единичная матрица ортогональна;

2) Если ортогональна, то и тоже ортогональна;

3) Произведение ортогональных матриц – матрица ортогональная;

4) Определитель ортогональной матрицы = ;

5) Преобразование с ортогональной матрицей сохраняет скалярное произведение и, следовательно, длину вектора .

Упражнение: Пусть и - ортогональная матрица, покажите, что матрицы и коммутативны.

 

4.3.3.1. Матрицы вращения (Гивенса)

 

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

.

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

Нетрудно проверить, что определитель .

Упражнение: Покажите, что .

 

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

Умножим квадратную матрицу слева на матрицу , . Очевидно, меняется только -я и -я строки матрицы по правилам ( ):

,

, .

Если хотя бы один из элементов или отличен от нуля, то выбирая

и , можно получить:

и , т.е. можно так построить матрицу вращения, чтобы обнулился элемент .

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

.

Элемент при этом будет положительным.

Если , то достаточно начать с умножения на матрицу , где – наименьший номер строки, в которой на первом месте стоит ненулевой элемент, т.е. . Т.к. матрица не вырождена, то такой элемент, и, следовательно, номер строки, существует.

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

.

При этом элемент станет положительным.

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

,

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

Замечание_1: Умножение матрицы на матрицу вращения не меняет евклидовой нормы векторов-столбцов матрицы.

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

.

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

Замечание_2: Преобразование вращения позволяет избирательно обнулять ту или иную компоненту вектора (матрицы). Этой способностью преобразования часто пользуются на практике.

Следствие_1: Всякая невырожденная матрица представима в виде произведения ортогональной матрицы , с определителем равным +1, на правую треугольную , т.е. .

Доказательство. По теореме матрица приводится к право-треугольному виду , где – есть ортогональная матрица (как произведение ортогональных), . Обратная к матрице – есть ее транспонированная матрица, которая тоже ортогональна и . Следовательно – есть произведение ортогональной матрицы с определителем равным 1, на правую треугольную: . Здесь , . ■

Пример: Представить матрицу в виде произведения ортогональных матриц вращения и право-треугольной матрицы.

Решение: Построим последовательно ортогональные матрицы вращения , и , левые произведения на которые обнулят поддиагональные элементы матрицы .

Матрица имеет вид , где ; . .

Умножим слева на , получим:

Матрица имеет вид , где

; . .

Умножим слева на , получим:

.

 

Матрица имеет вид , где

; . .

Умножим слева на , получим право-треугольную матрицу:

.

 

.

Следовательно , где .

Откуда искомое разложение имеет вид

.

Следствие_2: Всякая ортогональная матрица с определителем равным +1 представима в виде произведения ортогональных матриц вращения.

И класс симметричных и класс ортогональных матриц входят в более общий класс нормальных матриц.

Вещественная матрица называется нормальной, если .

 

4.3.3.2. Матрицы отражения (Хаусхолдера)

 

В предыдущем параграфе рассматривалась матрица вращения вектора на угол :

.

Рассмотрим матрицу вида . Преобразование отражает вектор относительно прямой с образующим вектором или с нормальным вектором .

Пусть – ненулевой вектор. Матрица

(4.3.14)

называется матрицей отражения Хаусхолдера. Вектор называется вектором Хаусхолдера.

Преобразование отражает вектор относительно гиперплоскости, ортогональной вектору .

Т.к. , то формулу (4.3.14) можно записать в следующем виде .

Следовательно, в дальнейшем можно считать, что вектор Хаусхолдера нормирован, т.е. имеет длину, равную единице, а матрица Хаусхолдера, при , строится по правилу:

. (4.3.15)

Видно, что матрица Хаусхолдера симметрична. Она ортогональна.

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

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

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

Учитывая, что , где

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

Построим вектор Хаусхолдера по вектору так, чтобы преобразование Хаусхолдера обнуляло все компоненты вектора кроме -й, т.е., чтобы вектор был коллинеарен базисному вектору . Вектор – есть линейная комбинация вектора и , следовательно, он представим в виде: , где – искомая константа.

По формуле (4.3.14)

.

Т.к.