§ 36. Решение систем с невырожденными матрицами

Значительная часть наиболее известных численных методов решения систем линейных алгебраических уравнений

основана на разложении матрицы А на множители. В зависимости от того, как связаны сомножители с матрицей различают две схемы построения методов.

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

Решение системы (36.1) сводится к последовательному решению таких систем:

Во второй схеме предполагается, что найдены матрицы для которых выполняется соотношение

Тогда

где и есть решение системы

с матрицей из (36.4) и правой частью

Решение системы (36.1) сводится теперь к вычислению вектора согласно (36.7), решению системы (36.6) и определению искомого вектора по формуле (36.5). В данной схеме матрицы обычно бывают представлены в виде произведения элементарных матриц.

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

Эти методы в отношении скорости и объема требуемой памяти ЭВМ будут обладать такими же характеристиками, как и соответствующие разложения матрицы. Главный член числа арифметических операций остается без изменения, так как для решения систем (36.1) при наличии разложений (36.2), (36.4) нужно выполнить на порядок меньше вычислительной работы, чем для получения самих разложений. При этом, по существу, не требуется никакой дополнительной памяти ЭВМ по сравнению с той, которая уже была использована при разложении матрицы. Поэтому выбор вида разложения матрицы для построения численного метода решения систем линейных алгебраических уравнений, обладающего нужными характеристиками скорости и объема памяти ЭВМ, можно осуществлять, используя табл. 34.1.

Связь точности решения систем с точностью разложения гораздо сложнее. В общем случае удается лишь показать, что реально вычисленное решение X близко к

некоторому вектору который является точным решением возмущенной системы

с относительно малыми возмущениями Во многих случаях при этом оказывается возможным получить и Ьценки вида

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

Точность разложения матрицы на множители является одной из важнейших характеристик, определяющих общую погрешность решения системы (36.1). Как вытекает из формулы (10.10), (36.8), справедливо соотношение —

где — точное решение системы (36.1), a - спектральное или евклидово число обусловленности матрицы А. Отсюда следует, что точность решения системы, по существу, зависит лишь от максимальной из функций в (36.8). Но заведомо не может быть меньше, чем Поэтому разложение, для которого максимальная из функций не слишком сильно превосходит мы будем считать эффективным, по точности. Как будет показано ниже, все разложения из табл. 34.1 являются таковыми.

По-видимому, нет никакой необходимости исследовать всевозможные комбинации допустимых видов матриц в разложениях (36.2), (36.4). Численные методы, использующие разложения любого типа, не могут обеспечить решение систем (36.1) с меньшими затратами времени и памяти ЭВМ, чем методы, основанные на разложениях из табл. 34.1. К тому же не известно ни одного разложения, более точного, чем эти. Сказанное выше позволяет нам ограничиться в дальнейшем исследованием точности тех

методов решения систем уравнений, которые основаны на использовании разложений из табл. 34.1.

Из всех разложений в табл. 34.1 лишь разложение на треугольные множители, выполненное по компактной схеме, имеет вид (36.2). Построим соответствующие численные методы решения систем линейных алгебраических уравнений (36.1). Тогда, решая вспомогательные системы (36.3) с помощью обратной подстановки, описанной в § 35, мы будем вносить дополнительные эквивалентные возмущения в диагональные элементы матриц Но ошибки такого порядка уже могли появиться во всех элементах матриц при их вычислении. Поэтому для методов этой группы имеем

Рассмотрим теперь разложения вида (36.4) из табл. 34.1. Пусть матрица О — треугольная и получена с помощью умножения матрицы слева на последовательность матриц вращения, отражения или матриц типа (24.3). При решении системы (36.6) снова будут вноситься дополнительные эквивалентные возмущения в диагональные элементы матрицы но значительно большие ошибки уже могли появиться во всех элементах этой матрицы при ее вычислении. Эквивалентное возмущение в векторе при вычислении правой части образуется по тому же закону, как и при преобразовании матрицы Следовательно, для методов, основанных на этих разложениях,

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

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

Предположим теперь, что мы используем разложения (36.4), основанные на двухсторонних унитарных преобразованиях матрицы Матрица может не быть треугольной. Однако в § 35 было показано, что какой бы вид она не имела, решение системы (36.6) дает эквивалентные возмущения в зависящие от существенно слабее,

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

Наконец, рассмотрим использование процесса ортогонализации. Матрица в разложении (36.4) представлена в виде произведения матриц типа (24.9) и диагональных матриц, у которых не более одного элемента отлично от единицы. Если при вычислении вектора I согласно (36.7) применять операции накопления, то реально вычисленный вектор будет иметь в каждой своей координате такие же ошибки, как и при правильном округлении этих координат. Но матрица близка к унитарной. Следовательно, евклидова норма вектора ошибок в I может быть с таким же весом перенесена в решение и. Мы уже отмечали, что система (36.6) с матрицей близкой к унитарной, может быть решена настолько точно, что эквивалентное возмущение войдет лишь в правую часть и согласно (35.8) будет весьма малым. Принимая во внимание значение функции для процесса ортогонализации, заключаем, что теперь

Полученные оценки для функций (36.8) позволяют сделать общий вывод о величине отклонения реально вычисленного вектора от точного решения системы (36.1). Для этого воспользуемся неравенством (36.9) и заметим, что всегда Из соотношений (36.9)- (36.14) вытекает, что для численных методов решения систем линейных алгебраических уравнений, основанных на рассмотренных разложениях из табл. 34.1, асимптотически будем иметь

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

Отметим некоторые из известных методов, характеристики которых определяются табл. 34.1 и формулой (36.15).

Метод Гаусса [6]. Основан на разложении (36.4). Матрица — правая треугольная, матрица представлена как произведение матриц типа (24.3). Если используется одна из стратегий выбора ведущего элемента, связанная с изменением порядка просмотра столбцов, то матрица будет матрицей перестановок. При изменении порядка просмотра строк матрица будет представлена как произведение матриц (24.3) и матриц перестановок.

Компактная схема метода Гаусса [6]. Основана на разложении (36.2). Матрица В — левая треугольная, матрица С — правая треугольная.

Метод квадратного корня [2]. Основан на разложении (36.2) для положительно определенной матрицы А. Матрица С — правая треугольная,

Метод отражений [2]. Основан на разложении (36.4). Матрица — правая треугольная, матрица представлена как произведение матриц отражения.

Нормализованный метод отражений [7]. Основан на разложении (36.4). Матрица нормализованная левая (правая) треугольная, матрица представлена как произведение матриц отражения; матрица является матрицей перестановок.

Двухсторонний метод отражений [3]. Основан на разложений (36.4). Матрица — двухдиагональная, матрицы и 5 представлены как произведения матриц отражения.

Симметричный метод отражений [7]. Основан на разложении (36.4) и применяется для эрмитовых матриц А. Матрица — эрмитова трехдиагональная, матрица представлена как произведение матриц отражения и совпадает с матрицей

Метод ортогонализации [2]. Основан на разложении (36.4). Матрица унитарная, матрица представлена как произведение матриц типа (24.9) и диагональных матриц, у которых не более одного элемента отлично от единицы. Матрица 5 совпадает с единичной.

Все рассмотренные методы особенно удобны для решения систем линейных алгебраических уравнений с многими

правыми частями и одной и той же матрицей. В этом случае соответствующие разложения (36.2), (36.4) находятся лишь один раз. Многократно приходится решать только простые системы (36.3), (36.6) и выполнять преобразования (36.5), (36.7).

Согласно формуле (36.15) точность любого метода полностью определяется точностью разложения матрицы на множители. Но как видно из табл. 34.1, в этом отношении различные разложения отличаются друг от друга не так уж сильно. Поэтому, если какой-либо из методов не обеспечивает нужной точности решения системы линейных алгебраических уравнений, то нет никаких оснований надеяться на то, что другой метод будет давать для этой же системы существенно лучшие результаты. Скорее всего, такую систему следует рассматривать как неустойчивую и решать ее одним из тех способов, которые обсуждаются в §§ 39, 41.

УПРАЖНЕНИЯ

(см. скан)