§ 39. Особенности решения неустойчивых систем

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

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

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

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

Известно [1], что в этом случае

где — псевдообратная матрица для матрицы А.

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

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

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

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

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

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

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

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

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

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

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

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

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

Возмущение на элемент

в позиции делает эту матрицу вырожденной. Но при больших (

и снова величина элементов строк и столбцов матрицы (39.3) не отражает степени ее близости к матрице не полного ранга.

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

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

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

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

достоверного приближения к нужному решению исходной задачи будет заключаться в многократном решении параметризованной задачи с целью подбора совокупности параметров согласно дополнительной информации. Два вида такой параметризации рассмотрены во второй главе. В § 16 исследована дискретная параметризация, связанная с аппроксимацией матрицы исходной системы близкими матрицами меньшего ранга, в § 17 — непрерывная параметризация, связанная с минимизацией регуляризирующего функционала.

Исследования, выполненные в §§ 16, 17, составляют теоретическую основу решения неустойчивых систем линейных алгебраических уравнений. Теперь необходимо построить такие вычислительные алгорифмы, которые сохраняли бы свою устойчивость в условиях влияния ошибок округления и позволяли бы решать параметризованные задачи достаточно быстро.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)