Uwarunkowanie zadania | Wojciech Myszka

Numeryczne uwarunkowanie zadania, to parametr pozwalający ocenić wpływ drobnych zmian parametrów wejściowych na wynik działania. Zainteresowani jesteśmy taką sytuacją, w której niewielkie zmiany (błędy) parametrów wejściowych będą powodowały niewielkie jedynie fluktuacje wyników obliczeń.

Okazuje się, że nawet w całkiem prostych przypadkach nie można liczyć na dobre uwarunkowanie problemu obliczeniowego. Co gorsza może ono zależeć od danych wejściowych.

Do oszacowania uwarunkowania obliczeniowego używa się metod bardzo podobnych do tych używanych przy określaniu stabilności układów. Po szczegóły odsyłam do [1].

Tu będą tylko przykłady.

Rozpatrzmy wielomian o postaci [1] :

\begin{aligned} w (x) & = \prod_{i = 1}^{20} (x - i) = \sum_{i = 0}^{20} a_{i} x^{i} = x^{20} - 210 x^{19} + 20615 x^{18} - 1256850 x^{17} \\ + 53327946 x^{16} - 1672280820 x^{15} + 40171771630 x^{14} - 756111184500 x^{13} \\ + 11310276995381 x^{12} - 135585182899530 x^{11} + 1307535010540395 x^{10} \\ - 10142299865511450 x^{9} + 63030812099294896 x^{8} - 311333643161390640 x^{7} \\ + 1206647803780373360 x^{6} - 3599979517947607200 x^{5} \\ + 8037811822645051776 x^{4} - 12870931245150988800 x^{3} + 13803759753640704000 x^{2} \\ - 8752948036761600000 x + 2432902008176640000 \end{aligned}

Pierwiastkami tego wielomianu są liczby $1, 2, \dots, 20$ .

Zaburzmy jeden ze współczynników (patrz również [1]). Normalnie wartość współczynnika $a_{19}$ wynosi $- 210$ . Zastąpimy go współczynnikiem o wartości $- (210 + 2^{- 23})$ . Można to symbolicznie zapisać tak: $a_{19} (ε) = a_{19} (1 - ε)$ , gdzie $ε = (2^{23} * 210)^{- 1} < 2^{- 30}$ . Tak niewielka zmiana jednego tylko parametru powoduje, że wielomian ma zespolone miejsc zerowe.

Gdy niewielkie względne zmiany danych zadania powodują duże względne zmiany jego rozwiązania, to zadanie takie nazywamy źle uwarunkowanym .

Kolejnym problemem, który może być źle uwarunkowany jest zadanie liczenia iloczynu skalarnego dwu wektorów :

$S = \sum_{i = 1}^{n} a_{i} b_{i} \neq 0.$

Aby oszacować uwarunkowanie zadania zastąpimy dokładne wartości parametrów $a = (a_{1}, a_{2}, \dots, a_{n})$ i $b = (b_{1}, b_{2}, \dots, b_{n})$ przez wartości przemnożone przez $1 + α_{i}$ i $1 + β_{i}$ odpowiednio. Założymy przy tym, że iloczyny $α_{i} β_{i}$ są zaniedbywalnie małe. Aby oszacować zmienną zmianę wyniku liczymy iloraz

\begin{aligned} | \frac{\sum_{i = 1}^{n} a_{i} (1 + α_{i}) b_{i} (1 + β_{i}) - \sum_{i = 1}^{n} a_{i} b_{i}}{\sum_{i = 1}^{n} a_{i} b_{i}} | & \approx | \frac{\sum_{i = 1}^{n} a_{i} b_{i} (α_{i} + β_{i})}{\sum_{i = 1}^{n} a_{i} b_{i}} | \\ \leq max_{i} | α_{i} + β_{i} | \frac{\sum_{i = 1}^{n} | a_{i} b_{i} |}{| \sum_{i = 1}^{n} a_{i} b_{i} |} \end{aligned}

Jeżeli określimy $cond (a, b) = \sum_{i = 1}^{n} | a_{i} b_{i} | / | \sum_{i = 1}^{n} a_{i} b_{i} |$ wskaźnikiem uwarunkowania (największy błąd przenosi się na wynik z takim mnożnikiem) to gdy wszystkie współczynniki mają taki sam znak — niewielki błąd ma bardzo niewielki wpływ na wynik. Gdy $\sum_{i = 1}^{n} a_{i} b_{i}$ jest bliskie zeru — sytuacja jest znacznie gorsza.

Literatura

J. Jankowscy, Przegląd metod i algorytmów numerycznych. Cz. 1. Wydawnictwa Naukowo-Techniczne, 1988.