Влияние ошибок округления

5. Прежде чем рассматривать более сложные способы ускорения сходимости, важно оценить влияние ошибок округления. Можно было бы подумать, что если мы работаем прямо с матрицей А, то достижимая точность будет высока, даже если матрица плохо обусловлена в смысле проблемы собственных векторов; но это не так. Если мы учтем влияние ошибок округления в процессе § 3, то, обозначая получим

где, вообще говоря, это «малый» ненулевой вектор. Поэтому весьма возможно, что станет равным хотя еще будет далек от точного собственного вектора.

Рассмотрим, например, матрицу

для которой

Если мы возьмем то точные вычисления дадут

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

6. Если наибольшей по модулю компонентой вектора является то (5.1) может быть записано в виде

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

Если, например, вычислен с использованием стандартной арифметики с плавающей запятой, то мы имеем из гл. 3, § 6 (v)

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

хотя обычно ошибка в векторе предельной точности значительно меньше, чем максимум, который может вызвать возмущение, удовлетворяющее (6.2). Заметим, что граница для каждой компоненты в (6.2) равна и так как она прямо пропорциональна то ясно, что так же, как и в гл. 7, § 15, точность, достижимая при вычислении доминирующего собственного значения итерациями с любая диагональная матрица), такая же, как и при итерировании с А.

В примере и предельной точности является хорошим приближением к несмотря на неточность вектора, из которого оно было определено. Это вызвано тем, что матрица имеет хорошо обусловленные собственные значения, но плохо обусловленные собственные векторы, так как собственные значения близки. Если — плохо обусловленное собственное значение, т. е. если мало (гл. 2, § 31), то предельная точность, достижимая в собственном значении, также мала.

Рассмотрим, например, матрицу

собственные значения которой и 1. Если мы возьмем

так что при использовании арифметики с плавающей запятой и восьмизначной мантиссой, процесс стационарен и дает в качестве собственного значения

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

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

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

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

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

Изменение р

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

и мы имеем некоторую оценку величины Взяв получим

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

Для иллюстрации предположим, что матрица четвертого порядка имеет собственные значения 1,0, 0,9, 0,2, 0,1. Если мы итерируем без сдвига, то компоненты по и по будут быстро уменьшаться, но ошибки округления не дадут им исчезнуть. Предположим, что. работая с 10 десятичными знаками, мы достигли вида

и что на этом шаге имеем для оценку 0.901. Если мы применим итераций с то получим

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

т. е.

Дальнейшие итерации с не будут уменьшать компоненты но а компоненты по и по будут расти. Если мы теперь вернемся к то компоненты по и по будут снова быстро уменьшаться, и

после пяти или шести итераций получим

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

Специальный выбор р

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

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

и, взяв текущее значение в качестве получим

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

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

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