§ 32. Унитарно подобное разложение

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

Отсюда следует, что

Итак, любое подобное преобразование матрицы по существу, приводит к разложению ее на множители.

Известно [1] существование преобразований подобия, при которых матрица В в (32.1) является треугольной, квазидиагональной или имеет вид канонической формы Жордана. Однако все эти преобразования косвенным образом связаны с отысканием корней алгебраических многочленов и поэтому не могут быть получены в общем случае за конечное число арифметических операций. Тем не менее можно построить подобное преобразование (32.1) с матрицей В, существенно более простой, чем исходная матрица

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

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

Предположим, что уже построены матрицы отражения такие, что первые строк, матрицы

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

унитарно подобную матрице А.

Конечно, для реализации преобразования (32.3) можно использовать не только матрицы отражения, но и матрицы вращения. Анализ ошибок округления, возникающих в реальных вычислительных процессах, полностью охватывается анализом, проведенным в § 23, с заменой в формулах (23.8), (23.10) числа на

Остановимся более подробно на одном частном, но очень важном случае. Пусть матрица А эрмитова; тогда будут эрмитовы все матрицы из (32.2) и матрица В из (32.3). Но почти треугольная эрмитова матрица в действительности является эрмитовой трехдиагональной. Следовательно, в случае эрмитовой матрицы А процесс подобного преобразования (32.2), (32.3) становится особенно эффективным.

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

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

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

Необходимая модификация вычислительной схемы осуществляется довольно просто. Принимая во внимание вид (20.4) матрицы отражения, будем иметь

Далее,

Если обозначить

то согласно (32.4)

Задание матрицы половиной ее элементов позволяет теперь вычислить аналогичную половину элементов

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

Пусть — элементы вычисленной матрицы отражения Через обозначим векторы, точно вычисленные согласно (32.5), но исходя из величин Тогда, в соответствии с (32.6),

При вычислении правой части появятся ошибки. Поэтому в действительности мы будем иметь

где матрица суммарных ошибок.

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

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

Здесь

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

где

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

УПРАЖНЕНИЯ

(см. скан)