6.4. НВП-РАЗЛОЖЕНИЕ МАТРИЦЫ

Один из эффективных методов решения системы линейных уравнений состоит в применении так называемого НВП-разложения.

Определение. НВ-разложением -матрицы А, , называется представление ее в виде где нормированная нижняя треугольная -матрица, a U - верхняя треугольная -матрица.

Уравнение где А — это -матрица, -мерный вектор-столбец неизвестных, -мерный вектор-столбец, можно решить, сначала НВ-разложив А в произведение в предположении, что это возможно. Затем представим в виде Чтобы получить решение х, решим сначала относительно у, а затем относительно х.

Трудность применения этого метода заключается в том, что у матрицы А может не быть НВ-разложения, даже если она невырож-денна. Например, матрица

невырожденна, нее нет НВ-разложения. Однако если матрица А невырожденна, то найдется такая матрица перестановки что имеет НВ-разложение. Изложим алгоритм, который по любой невырожденной матрице А находит такие матрицы что Матрицы образуют НВП-разложение 2) матрицы

Алгоритм 6.1. НВП-разложение

Вход. Невырожденная -матрица степень числа 2.

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

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

Каждый рекурсивный вызов процедуры МНОЖИТЕЛЬ происходит на -подматрице А -матрицы При каждом вызове есть степень числа 2 и Выходом этой процедуры являются три матрицы показанные на рис. 6.1.

Пример 6.3. Найдем НВП-разложение матрицы

(кликните для просмотра скана)

Рис. 6.3. Завершение процедуры а — построение матрицы ; б - разложение матриц в — разложение матрицы А.

Начнем с вызова процедуры ), которая сразу же вызывает

Взяв в качестве матрицы А первый аргумент этого иылива, вызываем МНОЖИТЕЛЬ результате получаем

последняя матрица переставляет столбцы 1 и 4.

(см. скан)

Рис. 6.4. (см. скан) Процедура

В строке 7 вычисляем

ГО

В строке 8 имеем , так что после выполнения строки Строка 10 дает ; следовательно, после строки 11 будет

В строке 12

а в строке 13

Таким образом, МНОЖИТЕЛЬ выдает

Теперь возвращаемся к вызову в строке 6, причем роль играют соответственно В строке 7 вычисляем

в строке 8

так что после выполнения строки 9

и в строке 10

Предлагаем читателю проверить, что ) выдает

Таким образом, в строке а в строке 13

Следовательно, в строках 14—16 вычисляем

Теперь приступим к доказательству корректности алгоритма 6.1.

Теорема 6.3. Для любой невырожденной матрицы А алгоритм 6.1 вычисляет такие матрицы что

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

1) в строке 2 процедуры МНОЖИТЕЛЬ всегда можно найти ненулевой столбец и

2) в строке 9 всегда существует

Пусть А будет -матрицей. Покажем индукцией по где степень числа 2, что если А имеет ранг то МНОЖИТЕЛЬ вычислит такие что нижняя треугольная матрица, верхняя треугольная матрица и матрица перестановки рангов соответственно. Кроме того, первые столбцов матрицы образуют подматрицу ранга Если то в А должен быть ненулевой элемент, так что базис индукции выполняется. Допустим, что Так как А имеет столбцов и ранг то каждая из матриц появляющихся в строке 5, имеет столбцов и ранг По предположению индукции вызов процедуры МНОЖИТЕЛЬ в строке 6 выдает требуемые матрицы причем первые столбцов матрицы образуют матрицу ранга Поэтому матрица необходимая в строке 9, существует.

Из рис. 6.2,г видно, что матрица А равна произведению трех матриц, у одной из которых в верхней части стоит а в нижней Ранг этой матрицы должен быть ибо матрица А имеет ранг Поэтому имеет ранг Поскольку первые столбцов матрицы состоят из нулей, получается из вычеркиванием ее первых столбцов, то ранг матрицы также равен Следовательно, по предположению индукции вызов процедуры МНОЖИТЕЛЬ в строке 11 дает нужные Отсюда непосредственно вытекает доказываемое утверждение.

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

Теорема 6.4. Пусть для каждого можно умножить две -матрицы за такое время что при некотором неравенство

выполняется для всех Тогда найдется такая постоянная что алгоритм 6.1 тратит не более времени для любой невырожденной матрицы.

Доказательство. Применим алгоритм 6.1 к -матрице. Пусть время, требуемое для выполнения процедуры где А — это -матрица, В силу строк 1—4 этой процедуры для некоторой постоянной Рекурсивные вызовы в строках 6 и 11 занимают времени каждый. В каждой из строк 7 и 13 вычисляется матрица, обратная к матрице перестановки (что занимает времени), и произвольная матрица умножается на матрицу перестановки. Это умножение просто переставляет столбцы первой матрицы. Представляя матрицу перестановки в виде массива видим, что столбец первой матрицы становится столбцом произведения. Таким образом, произведение можно найти за время и тем самым строки 7 и 13 выполняются за время

Строка 9 тратит времени на вычисление (в силу теоремы 6.2); такое же время требуется для вычисления Так как матрица имеет не более строк и не более столбцов, то произведение можно вычислить за время

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

где постоянные.

В силу условия теоремы и равенствам справедливо неравенство Поэтому можно объединить второе и третье слагаемые в (6.5). Для некоторой постоянной

Из (6.6) выводим

Из условия теоремы вытекает, что Поэтому

Так как сумма в правой части сходится и существует такая постоянная что Для алгоритма значит,

Следствие. НВП-разложение любой невырожденной -мат-рицы можно найти за шагов.

Доказательство. В силу теорем 6.1, 6.3 и