§ 28. Разложение на треугольные множители

Пусть матрица А удовлетворяет условиям теоремы 27.1. Так как в этом случае то по элементам первого столбца матрицы А можно построить матрицу вида (24.3) такую, что в произведении все поддиагональные элементы первого столбца будут нулевыми. При этом диагональный элемент останется без изменения и, следовательно, будет отличен от нуля.

Будем считать, что уже вычислены матрицы вида (24.3) для некоторого и построена последовательность матриц

для Обозначим элементы матрицы через и предположим, что

Это предположение заведомо выполняется при

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

Применяя формулу Бине — Коши [1], получаем

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

Левая часть этого соотношения отлична от нуля в силу условий на главные миноры матрицы элементы а отличны от нуля в силу предположений (28.2). Следовательно, Теперь мы можем по элементам столбца матрицы построить матрицу вида (24.3) и матрицу . В этой матрице по сравнению с не меняются элементы в первых столбцах и первых строках. По построению матрицы поддиагональные элементы в столбце матрицы будут нулевыми.

Таким образом, процесс (28.1) продолжен еще на один шаг и условия (28.2) выполняются при замене на Поэтому процесс (28.1) можно продолжить до Согласно (28.3) получаем, что

Как следует из (24.4), матрица левая треугольная с единичными диагональными элементами. Матрица правая треугольная. Условия, наложенные на матрицу гарантируют отличие от нуля всех диагональных элементов матрицы кроме, может быть, последнего.

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

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

где эквивалентное возмущение.

Процесс (28.1) в терминах преобразования столбцов был описан и исследован в § 24. Теперь вместо (24.6) имеем

формула (24.7) означает, что

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

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

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

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

если либо

Рассмотрим ошибки, возникающие при вычислении элементов второй группы. Имеем

Предположим, что . Это означает, что к элементу прибавляется нулевой элемент. Но тогда Из равенства следует неравенство , поэтому

Если же , то

где Отсюда вытекает, что

Принимая во внимание (28.7), получаем

Следовательно, в данном случае

Наконец, если то

что дает

Объединяя (28.6) — (28.8), заключаем, что

если

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

Но

следовательно,

Если то это означает, что

В случае, когда мы имеем

и тогда

Из (28.10), (28.11) вытекает, что в любом случае

если, конечно,

Полученнце оценки ошибок позволяют оценить элементы эквивалентного возмущения Принимая во внимание соотношение (28.4) и оценки (28.5), (28.9), (28.12), находим, что

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

и пренебречь членами с , то из (28.13) следует, что

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

то будем иметь

Оценки (28.13)-(28.15) получены без каких-либо предположений относительно величины главных миноров матрицы . Они еще раз подтвердили высказанное ранее мнение о том, что существенным источником неустойчивости в процессах типа (28.1) может быть лишь значительный рост элементов промежуточных матриц в процессе (28.1).

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

Выберем в исходной матрице А любой элемент который назовем ведущим или главным элементом 1-го шага, и рассмотрим матрицу . В этой матрице в позиции (1.1) находится ненулевой элемент Поэтому можно построить матрицу с нулевыми поддиагональными элементами в первом столбце. Предположим, что аналогично матрицам в (28.1) уже вычислены матрицы Среди элементов матрицы удовлетворяющих условиям выберем любой элемент

который назовем ведущим или главным элементом шага, и построим матрицу

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

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

Напомним, что для всех Если обозначить

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

где

Соотношения (28.18) — (28.20) показывают, что процесс (28.16) определяет разложение на треугольные множители матрицы которая согласно (28.20) получается из матрицы А путем перестановок ее строк и столбцов. Анализ ошибок, выполненный для матрицы А и процесса (28.1), уже без изменения переносится на матрицу А и процесс (28.16). Этот процесс получил название — метод Гаусса с перестановками для треугольного разложения матрицы.

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

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

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

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

Применение первой и третьей стратегий обеспечивает выполнение неравенств для элементов матриц

В этих случаях оценки (28.13) — (28.15) можно улучшить, но только лишь в 1,5 раза. По-прежнему главным фактором остается рост элементов матриц по сравнению с элементами исходной матрицы А.

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

Если перестановки не выполнялись, то очевидно, что

поэтому Перестановки не меняют этого соотношения, поэтому

К сожалению, при применении стратегии выбора ведущего элемента по столбцу оценка (28.21) может достигаться. Например, она достигается для матриц А вида

Значительно лучший результат известен для стратегии выбора ведущего элемента по всей матрице. Доказано [5], что если то

Правая часть (28.22) много меньше, чем 2-1. Однако оценка (28.22), по-видимому, сильно завышена, так как до сих пор не найдено ни одной матрицы, для которой

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

УПРАЖНЕНИЯ

(см. скан)