Основные ограничения t-разрядных вычислений

12. В главе 2 мы уже отмечали, что если матрица А требует для своего представления больше чем разрядов, то мы не можем ее представить в вычислительной машине, имеющей t-разрядное слово. Мы должны с самого начала ограничиться -разрядной аппроксимацией матрицы».

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

то увидим, что

где

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

Нетрудно построить примеры, для которых эти границы почти достижимы.

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

где нормированные левые и правые собственные векторы А. Из (12.4) имеем

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

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

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

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

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

13. (i). Мы не предполагаем, что если некоторая матрица имеет большое значение какого-нибудь из чисел 1 то соответствующее собственное значение должно обязательно иметь потерю точности порядка величины, даваемой оценками в (12.5) и (12.6), при любом используемом методе. Рассмотрим, например, плохо обусловленную матрицу, определенную в § 33 гл. 2; она принадлежит классу матриц, которые называются трехдиагональными. Матрица А является трехдиагональной, если

Теперь будем развивать методы, предназначенные специально для трехдиагональных матриц, и покажем, что ошибки округления, сделанные в этих методах, эквивалентны возмущениям в ненулевых элементах А. Хотя матрица в § 33 имеет плохо обусловленные собственные значения, они не очень чувствительны к возмущениям элементов в трех центральных линиях по диагонали, и, следовательно, используя эти методы, мы

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

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

(iii) В обсуждении предыдущего раздела мы ссылались на возможность того, что некоторые преобразования могли быть «неустойчивыми», и подразумевали, что тогда ошибки могли бы быть существенно больше. Мы можем проиллюстрировать эту идею неустойчивости очень простым способом. Пусть матрица о определена так:

Используя -разрядную плавающую арифметику, умножим справа на матрицу типа (гл. 1, § 40), выбирая ее так, чтобы сделать элемент нулем. Мы имеем

(где в качестве элемента матрицы написан ). Далее

ЛГА

Так как след вычисленной матрицы равен 0,5000, а исходной матрицы равен 0,5502, то не может быть точно подобной любой для которой

Очень большой элемент в привел к имеющей много большие элементы, чем А о, и ошибки округления не эквивалентны «малым» возмущениям в элементах . В действительности пагубный эффект преобразования более сильный, чем может быть замечен просто из рассмотрения ошибки в следе. Собственные значения с четырьмя десятичными знаками суть 0,7621 и —0,2119, в то время как они равны . В общем случае мы убедимся в том, что при использовании матриц преобразования с большими элементами ошибки округления эквивалентны большим возмущениям в исходной матрице.