§ 37. Системы с матрицами полного ранга

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

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

имеет наименьшую евклидову норму.

Инвариантность евклидовой нормы к унитарным преобразованиям позволяет свести задачу отыскания нормального псевдорешения системы общего вида к более простой задаче. Действительно, выполним какое-нибудь преобразование (36.4) с унитарными матрицами Тогда легко проверить, что в обозначениях (36.5) — (36.7)

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

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

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

с квадратной невырожденной матрицей А А порядка путем простого преобразования

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

Формально соотношения легко заменить другими. Рассмотрим решение переопределенной системы. Если точное псевдорешение, то невязка

сбгласно (37.1) удовлетворяет соотношению

Поэтому вместо системы (37.1) можно решать систему

Вместо соотношений (37.2), (37.3) получаем аналогичную систему:

Здесь — совпадает с решением системы (37.2). Матрицы систем (37.5), (37.6) эрмитовы невырожденные порядка

Итак, численные методы решения систем с прямоугольными матрицами полного ранга можно строить тремя различными способами. Первый способ связан с унитарным преобразованием матрицы и минимизацией функционала невязки, второй с решением систем (37.1), (37.2), третий —с решением систем (37.5), (37.6). Какому из способов отдать предпочтение — не очевидно. Тем более, что все они требуют примерно одинаковых затрат как по времени решения, так и по объему используемой памяти ЭВМ. Необходимо их сравнение по точности. Мы начнем исследования с первого способа.

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

где невырожденная левая треугольная матрица

порядка Если нормальное решение системы (36.6) представить в виде

где размерность вектора равна то для векторов будем иметь

Решение системы в (37.8) осуществляется по одному из тех алгорифмов, которые были исследованы ранее, например, с помощью обратной подстановки.

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

где или, что то же самое,

Предположим, далее, что система переопределенная. Приведем матрицу А с помощью умножения слева на унитарную матрицу к правой треугольной матрице Ясно, что можно представить в виде

где невырожденная правая треугольная матрица. Пусть

где размерность вектора V равна Тогда единственное псевдорешение системы (36.6) удовлетворяет уравнению Снова в этом процессе наиболее целесообразным является использование преобразований отражения.

Анализ ошибок показывает, что в соответствии с оценкой (16.7) реально вычисленный вектор удовлетворяет соотношению

Теперь вместо (37.10) имеем

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

то оценка (37.12), по существу, совпадает с (37.9) при замене, конечно, на Если же

то оценка (37.12) в целом становится такой:

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

Будем вычислять матрицу и правую часть системы (37.1), используя операцию накопления. Тогда в действительности придется иметь дело с системой

где

Решая систему (37.16) одним из исследованных ранее

методов, мы получим некоторый вектор для которого согласно (36.15), (37.17) выполняется соотношение

Для евклидовой нормы для спектральной нормы это неравенство обращается в равенство. Поэтому, используя, например, метод квадратного корня для решения системы (37.16), получим, что

При выполнении условия (37.14) оценка (37.18) значительно лучше оценки (37.15). Если в условии (37.14) знак «много больше» заменить знаком «больше», то и тогда оценка (37.18) остается более предпочтительной.

Таким образом; сравнивая первые два способа, можно сделать следующий вывод в отношении точности решения переопределенной системы линейных алгебраических уравнений. Если правая часть системы достаточно хорошо согласована с матрицей, то такую систему целесообразно решать с помощью унитарного преобразования матрицы без перехода к системе (37.1). При плохом согласовании более точные результаты дает прямое решение системы (37.1). Условием хорошего согласования является выполнение неравенства (37.13).

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

Оценка (37.9) настолько хороша, что при решении недоопределенной системы линейных алгебраических уравнений (36.1) нет никаких оснований для перехода к системе (37.2). Если все же находить нормальное решение такой системы согласно (37.2), (37.3) и для решения системы (37.2) использовать метод квадратного корня, то мы получим некоторый вектор для которого снова выполняется оценка (37.18). Но мы не будем останавливаться на ее выводе.

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)