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

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

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

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

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

, , , , , ,  и :

Т.е. при 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-й степени  и соответствующую возмущенную задачу . (свободный член дан с относительной погрешностью . Корни возмущенного многочлена  и , их относительная погрешность  — задача плохо обусловлена.