§ 9. Неустранимая погрешность при численном решении систем линейных алгебраических уравнений

Пусть требуется решить систему линейных алгебраических уравнений

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

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

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

Тогда

или

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

Тогда согласованная с ней норма матрицы А будет равна

где через обозначено наибольшее собственное значение симметрической матрицы Из равенства (2) получаем

Но

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

Тогда из (9) и (10) получаем:

Обозначим минимальное из через Из (11) следует:

Таким образом,

Из (8) и (13) находим:

или

Поэтому второе слагаемое правой части неравенства (5) может быть оценено следующим образом:

Очевидно,

Уменьшаемое в правой части неравенства (17) оценивается так же, как мы оценивали (8). При этом получим:

Вычитаемое в правой части (17) может быть оценено так:

Таким образом,

Если то (5) и (20) дают

Это и есть искомая оценка.

Приведем пример на применение полученной формулы. Пусть дана система:

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

В этом случае вектор будет выглядеть так:

Итак, Матрица в нашем случае нулевая. Поэтому

Так как матрица А симметрическая, то получить грубую оценку Таким образом,

Возьмем теперь в качестве нормы вектора величину

Тогда согласованная с ней норма матрицы А с элементами а будет равна

Перепишем равенство (4) в виде

где Отсюда следует:

Будем предполагать, что погрешности ей настолько малы, что Тогда

Последнее справедливо в том случае, если Далее, заметим, что

где через обозначено

и через обозначены элементы матрицы

Здесь алгебраическое дополнение элемента матрицы определитель матрицы А. Таким образом, оценка для при примет вид

Такая же оценка справедлива и для каждой компоненты вектора Однако для компонент можно получить и более точную оценку. По (24) имеем:

Отсюда

Подставляя сюда вместо выражение (30) и используя (29), получим:

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

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

велика, так что будет близко к единице, то правая часть (30) или (33) будет велика. В связи с этим вводилось ряд характеристик, аналогичных (34), так называемой «обусловленности» систем. При этом система считалась хорошо обусловленной, если небольшие изменения в коэффициентах и правой части мало изменяют решение системы, и плохо обусловленной, если небольшие изменения в коэффициентах и правой части вызывают большие изменения в решении системы. Пока эти вопросы еще не исследованы до конца.

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

ЛИТЕРАТУРА

(см. скан)