Повышение устойчивости к ошибкам округления достигается путем выбора на каждом шаге в качестве ведущего элемента Ь)У максимального по модулю, и перемещения его в главную

диагональ посредством перестановок строк и столбцов Уменьшение заполнения преобразуемой матрицы также связано с оп--гимизацией перестановок Достаточно подробное изложение ЭТИХ вопросов имеется в работах [45, 46]

Отметим, что в случае эрмитовых (симметричных) матриц сохранение симметрии в процессе преобразования весьма жела-

хх« .«хххх

X X • •

• X X X X

Рис 3 1 Пример преобразования матрицы, которое упрощает последующую триангуляризацию

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

Для иллюстрации эффективности предварительной переста-

новки строк и столбцов разреженных матриц Бпш на рис 3 1 представлены матрицы, которые могут быть получены одна из другой с помощью перестановок Однако для триангуляризации первой матрицы потребуется 2/С/З арифметических операций, а поскольку в процессе разложения произойдет заполнение треугольных сомножителей, то для хранения потребуется /С ячеек памяти Для триангуляризации второй матрицы следует выполнить только 2/( операций и использовать 3/< ячеек памяти В общем виде задача оптимизации перестановок для эрмитовых разреженных Матриц является минимаксной [46] Требуется отыскать матрицу перестановок Р, такую, чтобы преобразованная матрица PBinnP~ =-*пш имела минимальную ширину ленты для максимальных индексов элементов Ьг)

Существует несколько практических методов построения матрицы Р, близкой к оптимальной [46] На рис 3 2 иллюстрирован эффект приведения к ленточному виду матрицы (IOX ХЮ)

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

с X X X Х X

; X X

XX X

: X X XX : X Хх X X д X

Рис 3 2 Пример приведения разреженной матрицы к ленточному виду

Рнс 3 3 Упорядоченные структуры разреженных матриц, удобные для триангулярнзации

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

Vol = 4" К" + И" + 4) + 2] ~ 4"

(3 23)

где (2т + I) -ширина ленты, т е 6,j=0npH \i - />т 7* 99

Обратный ход вычислительного процесса можно исключить,

если для преобразования Впш вместо элементарных матриц Lr использовать матрицы Гг, которые в соответствии с (3 10) определяются выражением

(3 24)

Очередной шаг процедуры записывается в виде

Q(r + i)jQ(r) (3 25)

где BW = Впш - исходная матрица ковариаций

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

I! = TjTk- Т.тХш (3 26)

Этот метод называется исключением Гаусса-Жордана Из (3 26) получаем мультипликативную форму обратной матрицы

Впш=ТкТк- TJ, (3 27)

Соответственно решение уравнения (3 8) получается применением последовательности преобразований Тг к обеим частям

W = r,r, . r.r.Vo (3 28)

Мультипликативная форма обратной матрицы (3 27) обладает теми же преимуществами, что и элиминативная (3 22), но имеет меньшую разреженность

3 2.2. Триангуляризация методом квадратного корня (разложение Холецкого)

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