§ 40. Системы с двухдиагональными матрицами

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

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

В случае нечетного

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

всех исключаются подряд, начиная с первого. Из процесса исключения сразу же вытекает следующее:

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

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

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

Обозначим диагональные элементы матрицы через внедиагональные — через Преобразование (40.1) унитарное, поэтому у матриц из (40.1) совпадают квадраты евклидовых норм векторов-столбцов. Следовательно,

У матриц из (40.2) совпадают квадраты евклидовых норм векторов-строк, что также приводит к -Итак, соотношения (40.3) выполняются для всех Отсюда получаем:

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

для всех Но тогда для всех

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

Исследуем скорость сходимости последовательности . В силу унитарности преобразования (40.1) скалярные произведения соседних векторов-столбцов матриц совпадают. Для матриц из (40.2) совпадают скалярные произведения соседних векторов-строк. Это приводит к соотношениям

для из которых вытекает, что

Но для всех поэтому

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

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

они «оторваны» от остальных. В этом случае отношение будет достаточно малым и уже после нескольких преобразований (40.1), (40.2) последние строк и столбцов всех матриц будут состоять только из малых элементов. Так, например, матрица (39.2) при имеет лишь одно малое сингулярное число. Но легко проверить, что выполнение только одного преобразования приводит к тому, что последний диагональный элемент матрицы становится меньше, чем . В матрице последняя строка и последний столбец будут состоять только из малых элементов.

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

Процесс преобразований (40.1), (40.2) численно устойчив. Если выполняется таких преобразований, то при использовании вычислений с одинарной точностью реально полученная матрица будет ючно унитарно эквивалентна матрице при этом

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

целесообразно использовать процессы минимизации

регуляризирующего функционала типа (17.1), что приводит к необходимости решать системы

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

УПРАЖНЕНИЯ

(см. скан)