Обусловленность вычислительной задачи

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

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

Пример хорошо и плохо обусловленных вычислительных задач классической корректной задачи

, , , , , , и :

Т.е. при a = 1 имеем Dx*=1×Db, а при a = 0.001 имеем Dx*=10³×Db.

Пример Дж. Уилкинсона

Рассмотрим задачу о вычислении корней многочлена 20-й степени .

В качестве многочлена 20-й степени возьмем простой многочлен .

Очевидно, что решение задачи существует и единственно:x₁ = 1, x₂ = 2, …, x₂₀ = 20. Доказано, что эта задача устойчива относительно возмущения исходных данных (коэффициентов). Т.е. задача корректна.

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

Уилкинсон рассмотрел пример, когда коэффициент многочлена при , , содержит малую ошибку: .

Вычислим корни возмущенного многочлена высокоточным алгоритмом и посмотрим, как столь незначительная погрешность влияет на значения корней?

Т.е. если — решение задачиP(x)=0, a — решение задачиP*(x)=0, погрешность исходных и , то . Задача плохо обусловлена.

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

Пример Дж.Уилкинсона — классический пример плохо обусловленной вычислительной задачи. Степень рассмотренного многочлена довольно велика. Однако плохо обусловленной может быть и задача о вычислении корней многочленов невысоких степеней. Рассмотрим задачу о вычислении корней многочлена 4-й степени и соответствующую возмущенную задачу . (свободный член дан с относительной погрешностью . Корни возмущенного многочлена и , их относительная погрешность — задача плохо обусловлена.