§ 48. Особенности вычислений

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

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

при некотором числе а, где

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

иначе

Если равны нулю одновременно, то

Предположим, что уже вычислены числа Находим

В случае положим

иначе

Если равны нулю одновременно, считаем . В качестве и берем вектор с координатами

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

где все величины имеют порядок Это предположение заведомо выполняется на первом шаге, причем

Определяем

Если имеет место (48.2), то находим

Поэтому новые величины можно считать точно полученными из возмущенных данных:

В случае, когда имеет место (48.3), находим

Теперь новые величины можно считать точно получен, ными из данных:

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

Здесь а совпадает с а для возмущений справедливы оценки

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

где величины имеют порядок а величины порядок со. Снова выполняется равенство (48.5), но теперь а совпадает с не всегда. Если но все диагональные элементы матрицы с отличны от нуля, то это означает, что равенство (48.5) выполняется при таком а, которое по модулю меньше со.

Не ограничивая общности, можно считать, что матрица а системы (47.5) правая почти треугольная. Аналогичный вид будет иметь матрица А — Поэтому систему (47.5) целесообразно решать следующим образом. Сначала приводим ее с помощью умножения слева на подходящим образом выбранную последовательность матриц вращения к системе с правой треугольной матрицей. Затем решение полученной системы находим с помощью описанного выше процесса. Реально вычисленный вектор удовлетворяет (47.6). Принимая во внимание неравенство а также оценки (35.13), (48.6), получаем

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

Обратные итерации особенно эффективны, когда матрица а симметричная. В этом случае без ограничения

общности можно считать, что матрица А трехдиагональная и тогда, в соответствии с (35.14),

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

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

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

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

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

Более целесообразно выполнять обратные итерации несколько иначе. Будем определять векторы из прямой суммы! корневых подпространств матрицы соответствующих Рассмотрим вещественную матрицу

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

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

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

порядка Если координаты корневого вектора матрицы соответствующего Я, равны то корневой вектор матрицы соответствующий , будет таким:

Заметим, что в случае простого собственного значения матрица (48.9) имеет второй порядок.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)