ГЛАВА II. ТЕОРИЯ ВОЗМУЩЕНИЙ В ЛИНЕЙНОЙ АЛГЕБРЕ

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

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

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

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

§ 9. Сведение к простым матрицам

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

Пусть для матрицы А находится сингулярное разложение. Это означает, что необходимо определить

ненулевые векторы х, у и неотрицательные числа связанные с матрицей такими соотношениями:

Известно [1], что векторы х, у, удовлетворяющие (9.1), не только существуют, но и образуют ортонормированные системы. Эти векторы называются соответственно правыми и левыми сингулярными векторами, числа — сингулярными числами.

Предположим, что векторы образуют столбцы унитарной матрицы X, векторы у — столбцы унитарной матрицы числа диагональную матрицу Будем считать, что соответствующие (9.1) векторы х, у и числа расположены в столбцах матриц с одинаковыми номерами. Тогда уравнения (9.1) эквивалентны двум матричным равенствам:

или одному матричному разложению

Оно и называется сингулярным разложением матрицы А.

Рассмотрим возмущенную матрицу и напишем для нее систему уравнений, аналогичную (9.1). Имеем

Подставив вместо ее сингулярное разложение (9.2) и сделав замену

получим, что

где . В случае точной матрицы мы имели бы такую систему:

если, конечно,

Очевидно, что точные векторы являются единичными. Поэтому есть некоторое основание предполагать, что при достаточно малом возмущении векторы могут быть взяты близкими к единичным. Если используется евклидова норма векторов, то в силу ее инвариантности к унитарным преобразованиям из (9.3), (9.4) вытекает, что

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

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

и возмущенная система

Система (9.6) может быть совместной либо несовместной. Однако известно [1], что отыскание ее решения или нормального псевдорешения сводится к нахождению наименьшего по длине вектора минимизирующего функционал невязки

Подставив вместо матрицы А ее сингулярное разложение (9.2) и сделав замену

мы приходим к задаче минимизации функционала невязки

с диагональной матрицей Евклидовы нормы векторов

совпадают, поэтому решение системы (9.6) однозначно определяется решением системы

Аналогичные рассуждения показывают, что возмущенная система (9.7) будет эквивалентна системе

если положить

При этом снова имеет место (9.5) и, конечно,

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

Подставив вместо матрицы ее сингулярное разложение (9.2) и сделав замену

мы приходим к системам

Очевидно, что

Из диагонального вида матрицы заключаем, что системы (9.9), а следовательно, и системы (9.8) всегда совместны. Отношение норм их нормальных решений к норме нормального псевдорешения системы (9.6) говорит о степени согласованности матрицы и правой части в (9.6).

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

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

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

относительно чисел X и векторов при целых положительных не превосходящих кратности к как корня характеристического многочлена. В возмущенном уравнении

мы допускаем отличие от так как могут быть различными размерности циклических подпространств матриц

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

Подставив это разложение в (9.10), (9.11) и сделав замену

приходим к таким уравнениям:

где

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

нормальной матрицы это снова имеет место. Нормальная матрица имеет полную систему ортонормированных собственных векторов [1], поэтому можно считать, что матрица унитарная и

Если матрица А нормальная, то 1. Предположим, что возмущение таково, что будет нормальной и матрица тогда Следовательно, вместо уравнений (9.12) можно рассматривать уравнения

С подобной ситуацией мы заведомо встретимся, изучая влияние эрмитова возмущения эрмитовой матрицы.

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

УПРАЖНЕНИЯ

(см. скан)