ГЛАВА V. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

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

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

§ 35. Системы специального вида

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

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

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

Согласно общей идее обратного анализа ошибок постараемся показать, что реально вычисленное решение и системы (35.1) будет точным решением некоторой возмущенной системы

Для каждого из численных методов мы проведем исследование соответствующих эквивалентных возмущений

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

Ясно, что Предположим, что уже вычислены им из последних уравнений (35.3). Из уравнения находим

Таким образом последовательно определяем все координаты вектора .

Полученные формулы удобны для применения операции накоплений. Пусть реально вычисленные величины; тогда

где принимает обычные для ошибок значения. Если то

где

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

и тогда

где

Итак, реально вычисленное решение и системы (35.1) с треугольной матрицей является точным решением возмущенной системы (35.2). При этом матрица эквивалентного возмущения А диагональная, а ее элементы удовлетворяют неравенствам (35.4). Элементы эквивалентного возмущения в правой части системы удовлетворяют неравенствам (35.5). Отметим, что всегда

Система с ортогональной матрицей. Если матрица системы (35.1) ортогональная, то решение и находится весьма просто. Именно,

откуда следует, что для Эти формулы можно использовать и для численного определения решения. Вычисляем

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

Вектор будет точным решением системы вида (35.2), если положить Так как матрица ортогональная, то

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

Следовательно, вектор а, координаты которого определяются по формулам (35.7), будет точным решением возмущенной системы (35.2). При этом эквивалентное возмущение в правой части удовлетворяет неравенству (35.8), а эквивалентное возмущение матрицы системы — неравенству

Как мы покажем в § 38, процесс решения системы с матрицей, близкой к ортогональной, можно организовать так, что возмущение не будет влиять на точность. Для этого вычисления по формулам типа (35.7) придется проводить не один раз, а несколько.

Система с двухдиагональной матрицей. Рассмотрим, для определенности, систему с правой двухдиагональной матрицей. Имеем

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

принимают обычные для ошибок значения.

Если ошибки отличны от —1, то определяет эквивалентное возмущение элемента

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

Элементы эквивалентного возмущения удовлетворяют неравенствам

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

то нетрудно показать, что реально вычисленное решение будет точным решением возмущенной системы (35.2); при этом

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

одинарной точностью, то в предположении (35.12) вместо (35.13) будем иметь

УПРАЖНЕНИЯ

(см. скан)