29. Обусловленность систем уравнений. Коэффициент обусловленности.

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

Как количественно характеризовать степень обусловленности вычислительной задачи. Пусть B – вектор, составленный из точных исходных данных задачи; x – ее решение. Пусть, далее B характеризует ошибки, внесенные в исходные данные, а вектор x – изменение решения, вызванное этими ошибками. Предположим, что ошибки, вносимые в исходные данные, малы:

||δB||<.

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

||δx||≤K·||δB||,

то это число K и можно принять за меру обусловленности задачи.

Для системы линейных уравнений исходные данные – это n² коэффициентов исходной матрицы и n элементов вектора свободных членов; искомое решение – n-мерный вектор x. В матричном виде система записывается

Ax=b, (1)

где A – невырожденная (Δ=detA≠0) квадратная матрица n-го порядка; b - n-мерный вектор свободных членов; x - n-мерный вектор неизвестных.

Пусть вектор правых частей изменился на величину δb, т.е. вместо истинного вектора b используется вектор b+δb. Реакцией решения x на возмущение δb будет вектор поправок δx, т.е. если x – решение системы (1), то x+δx – решение системы:

A(x+δx)=b+δb. (2)

Такую систему называют возмущенной системой, а ее решение – возмущенным решением. Понимая под абсолютной погрешностью приближенного вектора норму разности между точным и приближенным векторами, а под относительной погрешностью – отношение абсолютной погрешности к норме вектора, выясним связь между погрешностями вектора свободных членов и вектора-решения. Раскроем скобки в (2): Ax+Aδx=b+δb. Так как Ax=b, то Aδx=δx. Для невырожденной матрицы существует A^-1 и δx=A^-1δb. Пронормируем последнее равенство:

||δx||=||A^-1+δb||≤||δx||≤||A^-1||·||δb||,

а также равенство (1), записанное в обратном порядке - b=Ax:

||b||=||Ax||≤||A||·||x||.

Эти два числовых неравенства одинакового смысла можно перемножить

||δx||·|b|≤||A||·||A^-1||·||δb||·||x||.

Из последнего делением на ||b||·||x|| получаем искомую связь

(||δx||/||x||)≤||A||·||A^-1||·(||δb||/||b||). (3)

Положительное число ||A||·||A^-1|| - коэффициент этой связи – называют числом обусловленности матрицы A и обозначают cond(A) (от английского слова conditioned – «обусловленный»). Легко показать, что то же самое число служит коэффициентом роста относительных погрешностей при неточном задании элементов матрицы A в (1). А именно, если матрица получила возмущение δA и x+δx – решение возмущенной системы

(A+δA)(x+δx)=b,

то справедливо неравенство

(||δx||/||x+δx||)≤cond(A)·(||δA||/||A||). (4)

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

Рассмотрим числовой пример плохообусловленной системы:

x₁+0.99x₂=1.99

0.99x₁+0.98x₂=1.97

То есть, имеем

A= b= точное решение: x=