Методы оценки погрешностей. Нормы векторов и матриц

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

Постановка задачи

Пусть дана система n линейных уравнений с n неизвестными :

(5.1)

где коэффициенты

В матричной форме записи система (5.2) имеет вид:

, (5.2)

где

.

Матрица А в этом случае называется матрицей коэффициентов, матрица b - столбцом свободных членов, матрица х – столбцом неизвестных.

Из курса линейной алгебры ([13]) известно, что если , то существует единственное решение систем (5.1) – (5.2), которое (с теоретической точки зрения) определить не составит труда:

а) в случае (5.1) можно воспользоваться формулами Крамера:

, (5.3)

где - матрица, получающаяся из матрицы А заменой её i- го столбца столбцом свободных членов;

б) в случае (5.2) можно воспользоваться существованием, в данном случае, матрицы , являющейся обратной к матрице коэффициентов А:

. (5.4)

Как правило, при проведении исследования данной задачи на устойчивость, в качестве входных параметров рассматривают столбец свободных членов b. Известно, что в случае невырожденности матрицы А, решение системы (5.1) - (5.2) устойчиво по входным данным ([3], стр. 129).

Таким образом, поставленная задача является корректной.

Рассмотренные выше способы (5.3) и (5.4) построения решений являются весьма трудоемкими, особенно формулы Крамера, приводящие к необходимости расчета n + 1 определит ел я n-го порядка.

Поэтому на практике, как правило, применяют другие методы, которые условно разбивают на две группы: точные и приближенные.

Точными методами называются такие методы, которые в предположении, что вычисления ведутся точно (без округлений), приводят к точным значениям неизвестных , . Так как на практике все вычисления ведутся с округлениями, то и значения неизвестных, полученные точным методом, неизбежно будут содержать погрешности ([14], стр. 44).

Приближенными методами называются такие методы, которые даже в предположении, что вычисления ведутся без округлений, позволяют получить решение системы лишь с заданной точностью. Точное решение системы в этих случаях может быть получено теоретически как результат бесконечного процесса ([14], 44).

В связи с этим возникает потребность оценки погрешностей.

Методы оценки погрешностей. Нормы векторов и матриц

Пусть - приближенное решение системы (5.1) – (5.2).

Для оценки погрешностей используют следующие векторы:

, (5.5)

которой называют погрешностью, и

, (5.6)

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

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

Нетрудно заметить, что

,

и следовательно, в случае невырожденной матрицы А:

. (5.7)

Условие (5.7) позволяет вместо требования малости погрешности е использовать критерий малости невязки r.

Для количественной оценки погрешностей в вычислительной математике используется понятие нормы, поскольку решение системы (5.1), являющее вектором, можно рассматривать как элемент линейного пространства .

Говорят, что в пространстве задана норма ([3], стр. 130), если каждому вектору поставлено в соответствие действительное число , называемое нормой вектора х и обладающее следующими свойствами:

1) , причем ; (5.8)

2) ; (5.9)

3) . (5.10)

В вычислительной математике наиболее употребительными являются следующие нормы ([3], стр. 130):

, (5.11)

, (5.12)

. (5.13)

. (5.14)

Нетрудно заметить, что нормы (5.11) и (5.12) – частные случаи нормы (5.14), а норма (5.13) может быть рассмотрена как результат предельного перехода при . Норма (5.12) является естественным обобщением на случай n -мерного пространства понятия длины вектора в двух и трехмерном пространстве, поэтому её называют евклидовой нормой ([3], стр. 130).

Известно ([3], стр. 130), что

. (5.15)

Неравенство (5.15) означает, что в определенном смысле нормы (5.11), (5.12) и (5.13) – эквивалентны: каждая из них оценивается любой из двух других с точностью до множителя, зависящего от n ([3], стр. 130).

Учитывая способ задания в Rⁿ скалярного произведения, можно записать следующее соотношение:

. (5.16)

Понятие абсолютной и относительной погрешности приближенного решения х * системы (5.1) – (5.2)в этом случае вводится так ([3], стр. 131):

(5.17)

- абсолютная погрешность вектора х *;

(5.18)

- относительная погрешность.

Выбор той или иной нормы в практических задачах, определяется тем, какие требования предъявляются к точности решения ([3], стр. 131):

· отвечает случаю, когда малой должна быть суммарная абсолютная погрешность в компонентах решения;

· соответствует критерию малости среднеквадратичной погрешности;

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

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

Говорят, что последовательность векторов сходится к вектору х при , если при ([3], стр. 131).

Обозначается: при .

Известно, что в конечномерных пространствах факт наличия или отсутствия сходимости последовательности векторов к вектору х не зависит от выбора нормы, так из сходимости последовательности по одной норме следует её сходимость по любой другой норме. Для норм (5.11) – (5.13) это следует из неравенства (5.15). Более того, при , тогда и только тогда, когда при для всех . Это означает, что в Rⁿ сходимость по норме эквивалентна покомпонентной (покоординатной) сходимости ([3], стр. 132).

Пусть А – квадратные матрицы, порядка n. Как известно, множество всех таких матриц – конечномерное линейное пространство ([13]).

Нормой матрицы А, подчиненной норме векторов, введенной в Rⁿ, называется величина ([3], стр. 132)

. (5.19)

Для введенной по (5.19) нормы, остаются справедливыми свойства, аналогичные свойствам (5.8) – (5.10) для нормы вектора ([3], стр. 132):

1) ; причем ; (5.20)

2) и любого числа a; (5.21)

3) . (5.22)

Кроме того, дополнительно к ним, верны свойства ([3], стр. 132):

4) ; (5.23)

5) . (5.24)

Нормам рассмотренным выше, подчинены нормы, соответственно, нормы , определяемые по формулам ([3], стр. 132):

; (5.25)

, (5.26)

где - собственные числа матрицы ;

. (5.27)

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

Вычисление нормы (5.26), как правило, вызывает затруднения, так как необходимо определять собственные векторы матрицы . Для оценки нормы (5.27) используется неравенство ([3], стр. 133):

, (5.28)

где

(5.29)

- величина, называемая евклидовой нормой матрицы А.

Норма (5.19) имеет простую геометрическую интерпретацию ([3], стр. 133). Операцию умножения вектора х на матрицу А можно рассматривать как преобразование, которое вектор х переводит в новый вектор у = Ах. Если значение интерпретируется как длина вектора х, то величина есть коэффициент растяжения вектора х под действием матрицы А. Таким образом, величина

(5.31)

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

Известно ([3], стр. 133), что для невырожденной матрицы минимальный коэффициент растяжения отвечает норме обратной матрицы и вычисляется по формуле:

. (5.32)

Справедливость этого факта легко подтверждается с помощью свойства (5.24) и возможностью, в данном случае, представления вектора х в виде

, (5.33)

с помощью следующих несложных преобразований:

.

Из равенства (5.7) связи погрешности е = х – х* и невязки r = b – Ax*, используя свойство (5) нормы матрицы, легко получить оценку:

. (5.34)

С помощью которой несложно доказать следующую теорему.

Теорема 5.1 ([3], стр. 138) Пусть х * -точное решение системы Ах *=b*, где b* является приближением к b. Тогда верны следующие оценки абсолютной и относительной погрешностей:

; (5.35)

. (5.36)

Доказательство. Из (5.34) следует, что

, т.е. оценка

(5.35) верна и .

Разделив неравенство (5.35) на , получим:

, откуда следует, что оценка (5.36) верна и .

Величина для задачи (5.1) и (5.2) играет роль абсолютного числа обусловленности, а величина называется естественным числом обусловленности ([3], стр. 138).

Величина зависит от конкретного решения х и характеризует коэффициент возможного возрастания относительной погрешности этого решения, вызванного погрешностью задания правой части. Это означает, что для задачи вычисления решения х системы (5.2) играет роль относительного числа обусловленности ([3], стр. 138).

Используя понятие нормы матрицы (5.19) можно вычислить максимальное значение естественного числа обусловленности:

. (5.37)

Полученную величину называют стандартным числом обусловленности (или просто числом обусловленности) матрицы А и обозначают: или ([3], стр. 139). Таким образом,

. (5.38)

Используя введенную величину, можно получить следствие к теореме 5.1.

Следствие 5.1 ([3], стр. 139) В условиях теоремы 5.1 справедлива оценка

. (5.39)

Величина cond (A) является широко используемой количественной мерой обусловленности системы (5.2). В частности, систему и матрицу А принято называть плохо обусловленными, если cond (A) >> 1. Для таких систем существуют решения, обладающие чрезвычайно высокой чувствительностью к малым погрешностям задания входного данного b. Тем не менее следует заметить, что не для всякого решения х коэффициент роста относительной погрешности достигает значений, близких к максимально возможному значению cond (A).

Число обусловленности обладает следующими свойствами.

Теорема 5.2

1) (5.40)

2) . (5.41)

3) . (5.42)

Доказательство.

1) Ex = x, , , следовательно, , таким образом, .

2) , следовательно, , так как , получаем:

.

3) .

Опираясь на геометрическую интерпретацию норм матриц, рассмотренную выше, число обусловленности можно интерпретировать как отношение максимального коэффициента растяжения векторов под действием матрицы А к минимальному коэффициенту ([3], стр. 140):

. (5.43)

Величина cond (A) зависит от выбора нормы векторов в пространстве Rⁿ. Фактически это есть зависимость максимального коэффициента роста погрешности от способа измерения величины входных данных и решения.

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

Теорема 5.3. Пусть х * - точное решение системы A * x *= b, где A * - приближенно заданная матрица А. Тогда имеет место следующая оценка относительной погрешности:

. (5.44)

Доказательство.

;

; следовательно,

;

.

Из данной теоремы следует приближенное равенство.

Следствие ([3], стр. 142) При выполнении условий теоремы 5.3 имеет место приближенное неравенство:

. (5.45)

Если с погрешностью заданны как правая часть системы, так и матрица (т.е. х * является решением системы А * x * = b *), причем , можно доказать справедливость неравенства ([3], стр. 142):

. (5.46)

На практике для вычисления и cond (A) формулы (5.36) и (5.38) практически не используются, так как их применение требует предварительного вычисления обратной матрицы. Существуют другие алгоритмы, дающие оценки этих величин ([3], стр. 143).

Чаще всего чувствительность решения к погрешностям проверяют экспериментально. Для этого задачу решают несколько раз с близкими к b правыми частями . Затем вычисляют

, (5.47)

что позволяет получить оценку снизу:

. (5.48)

Поиск по сайту: