§ 41. Тактика решения систем общего вида

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

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

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

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

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

и при этом известны оценки вида

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

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

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

Следующий этап связан с проверкой матриц на полноту их ранга. Согласно (37.19), (41.3), (41.4) они имеют полный ранг, если имеет полный ранг матрица и выполняется хотя бы одно из условий:

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

Основная трудность в проверке (41.5) связана с вычислением нормы матрицы Если то

где — квадратная двухдиагональная матрица порядка Но тогда

Если же , то

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

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

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

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

Тогда

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

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

Определяем вектор

находим нормальное псевдорешение системы

и вычисляем вектор

Он будет служить приближением к нормальному псевдорешению точной системы (41.1). Все вычислительные операции были подробно рассмотрены ранее. Решение системы (41.7) сводится к решению системы с двухдиагональной невырожденной матрицей, преобразования (41.6), (41.8) осуществляются по алгорифмам, исследованным в §§ 20, 21.

Выполнение любого из условий (41.5) позволяет дать асимптотически правильные оценки точности. Если то в соответствии с (10.10), (36.15),

Если те согласно (16.6), (36.15) и аналогично (37.9)

В случае в соответствии с (16.7), (37.12),

В последней оценке есть вектор, содержащий первые координат вектора есть вектор, содержащий последние координат

Процесс получения оценок (41.9) — (41.11) почти не отличается от процесса получения других аналогичных оценок, поэтому мы не будем останавливаться на нем подробно. Во всех оценках есть наименьшая из величин вычисленных при проверке выполнения условий (41.5).

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

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

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

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

Выполним несколько шагов процесса (40.1), (40.2), взяв в качестве начальной матрицу Это означает, что будут получены матрицы и двухдиагональная матрица для которых

Матрицы представлены как произведения матриц вращения, а эквивалентное возмущение удовлетворяет соотношению

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

В соответствии с преобразованием (41.12) запишем систему (41.7) в следующем виде:

и рассмотрим близкую к ней систему

Для матрицы легко находится псевдообратная матрица причем невелика. Поэтому нормальное псевдорешение системы (41.13) можно вычислить с высокой точностью. Определяем вектор

и затем вектор согласно (41.8). Этот вектор берем в качестве приближения к нормальному псевдорешению точной системы (41.1).

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

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

При практической реализации описанного этапа тактики действий процесс (40.1), (40.2) следует проводить до тех пор, пока матрицу нельзя расщепить на сумму

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

(40.1), (40.2) можно ограничиться выполнением небольшого числа шагов, тем более, что все оценки точности, связанные с вектором наиболее эффективны именно при оторванности малых сингулярных чисел. Если расщепление (41.14) не наступило после 8—10 шагов, то, скорее всего, это говорит о том, что сингулярные числа матрицы не имеют достаточного разделения.

В этом случае переходим к последнему этапу. Будем решать систему (41.2) с помощью процесса минимизации регуляризирующего функционала

Преобразование, выполненное на первом этапе, сводит эту задачу к минимизации более простого функционала

причем сохраняются соотношения (41.6) — (41.8). Но минимизация функционала (41.15) приводит к решению систем вида

с трехдиагональными положительно определенными матрицами.

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

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

Количественные оценки этой близости снова невозможны без привлечения дополнительной информации о точной задаче.

УПРАЖНЕНИЯ

(см. скан)