§ 2. Метод отражений

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

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

Рассмотрим случай вещественной матрицы А. Если w — некоторый вектор-столбец единичной длины, , то матрицу

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

Непосредственной проверкой убеждаемся, что и

здесь мы воспользовались тем, что

Таким образом, матрица U — симметричная и ортогональная.

Напомним один факт из алгебры. Пусть U и В две матрицы порядка , В — многочлен от . Тогда можно переупорядочить их собственные значения так, что при .

Поскольку U симметрична и , а все собственные числа Е равны 1, то все собственные числа матрицы U удовлетворяют условию , т.е. равны или или —1.

Собственному значению —1 отвечает собственный вектор w. В самом деле,

Все векторы, ортогональные вектору w, являются собственными. Им соответствует собственное значение, равное . Действительно, пусть . Тогда имеем

Представим произвольный вектор у в виде , где Для этого следует взять в качестве z проекцию вектора у на вектор w, т. е. , и . Вследствие (2) и (3) имеем . Таким образом, есть зеркальное отражение вектора у относительно гиперплоскости, ортогональной вектору .

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

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

Рис. 6.2.1

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

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

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

Доказательство. Пусть дана квадратная матрица порядка . Будем Приводить ее к правой треугольной матрице путем последовательного Умножения слева на ортогональные матрицы. На первом шаге приведения рассмотрим в качестве вектора у из предыдущего рассуждения Первый столбец матрицы А:

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

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

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

Пусть мы уже осуществили шагов и пришли к матрице с элементами такими, что при . В пространстве векторов размерности рассмотрим вектор

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

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

имеющей правую треугольную форму.

Если обозначить , то из последнего равенства следует, что где — ортогональная, а — правая треугольная матрицы. Лемма доказана.

Вернемся к решению системы . С помощью указанных преобразований отражения последовательно приводим ее к эквивалентному

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

Задача 1. Получить асимптотику числа операций метода отражений при .

Рассмотрим случай системы уравнений с комплексными А и . Пусть

Исходная система уравнений равносильна системе

с вещественными :

Поэтому вместо непосредственного решения исходной задачи можно перейти к решению задачи (4) и применить для решения последней метод отражений.

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

Задача 2. Перенести метод отражений на случай комплексных матриц.

Задача 3. Исследовать метод отражений в случае его применения для решения систем уравнений с ленточной матрицей.