§ 38. Уточнение решения

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

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

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

Подставляя это выражение в (36.1), получим

где

Будем считать, что способ вычисления невязки (38.3) и численный метод решения системы (38.2) таковы, что реальная поправка удовлетворяет соотношению

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

1. Вычисляем невязку в режиме накопления.

2. Нормируем невязку.

3. Решаем систему (38.2) одним из методов, удовлетворяющих условию (36.15).

4. Умножаем вычисленную поправку на обратную величину нормирующего множителя.

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

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

Процесс решения системы (38.2) заканчивается вычислением следующего приближения точному решению Находим

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

Далее из (38.1), (38.6) следует

откуда, учитывая (38.4), (38.7), получаем, что

Согласно описанному процессу построим последовательность векторов исходя из любого вектора например, нулевого. Из (38.8) заключаем, что

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

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

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

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

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

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

где

Поэтому поправку До можно находить из условия минимизации функционала невязки для системы

Может показаться, что, вычисляя с высокой относительной точностью невязку (38.9), мы найдем с высокой относительной точностью поправку как единственное псевдорешение системы (38.10). Однако в действительности попытка «уточнить» псевдорешение переопределенной системы приводит к следующей ситуации. Чем лучше взято приближение к псевдорешению, тем хуже его невязка будет согласована с матрицей и тем хуже будет относительная точность поправки, полученной по первому способу решения системы (38.10).

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

случае здесь можно надеяться на хорошую близость к какому-нибудь решению. При этом отклонение от нормального решения может быть значительным.

Эффективные процессы уточнения для систем с прямоугольными матрицами полного ранга можно построить на основе второго и третьего способов их решения. Напомним, что эти способы связаны с решением систем (37.1), (37.2) или (37.5), (37.6), матрицы которых невырожденные.

Рассмотрим применение второго способа к решению переопределенной системы. Теперь для поправки мы получаем систему

где

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

Предположим далее, что вторым способом решается недоопределенная система. Пусть некоторое приближение к решению системы (37.2). Если

то для поправки получаем систему

где

Снова при вычислении вектора все арифметические операции надо выполнять с удвоенной точностью. С удвоенной точностью следует сохранить последнее приближение и выполнить преобразование (37.3).

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

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

Тогда для поправок получаем систему

где

Для вычисления этих векторов с высокой относительной точностью вполне достаточно использования операций накопления.

Многократность решения систем не приводит к заметному увеличению времени счета. Если для систем (37.1), (37.2) применяется метод квадратного корня, то разложения матриц и полученные на первом шаге, используются и на всех остальных шагах. При решении систем (37.5), (37.6) и в процессах уточнения, связанных с ними, целесообразно выполнить предварительно унитарное преобразование матрицы А к матрице простого вида. Если

где — унитарные матрицы, то это определяет и разложения матриц в (37.5), (37.6). Именно,

Разложения (38.9) используются на всех шагах процесса уточнения. Полезно иметь в виду и такие соотношения:

Скорость сходимости процессов уточнения определяется соответствующими значениями в (38.4). Если использовать рассмотренные выше алгорифмы решения систем

линейных алгебраических уравнений с матрицами полного ранга, то для систем (37.1), (37.2)

для систем (37.5), (37.6)

Здесь

Различие оценок (38.10), (38.11) связано прежде всего с принципиальным различием свойств систем (37.1), (37.2) и (37.5), (37.6). Пусть, например, матрица и правая часть исходной системы умножаются на одно и то же число а. Тогда ее псевдорешения не изменяются, а решение вспомогательной системы (37.2) является однородной функцией а. Поэтому все полученные ранее оценки точности псевдорешений, включая оценку (38.10), инвариантны к такому умножению. Составные же решения систем (37.5), (37.6) не будут однородными функциями а, что и приводит к появлению неоднородной зависимости в правой части (38.11).

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

Рассмотрим один из распространенных способов построения итерационных методов. Пусть матрица системы (36.1) представлена в виде

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

Из (38.12), (38.13) вытекает, что

Следовательно,

Если выполняется условие

то последовательность векторов

будет сходиться к точному решению

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

связывающее два последовательных приближения. Это соотношение может быть получено непосредственно из (38.13), (38.15).

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)