4

Let be $f(x) = x_1 - 2x_2 +x_3, x_1 \approx x_2 \approx x_3 $

Find out (by using forward stability analysis) which of those following algorithms is the most stabil one:

a) $ \tilde{f} (x) := ( x_1 \ominus 2x_2) \oplus x_3$

b) $ \tilde{g} (x) := ( x_1 \ominus x_2) \ominus (x_2 \ominus x_3) $

c) $ \tilde{h} (x) := ( x_1 \oplus x_3) \ominus 2x_2$

The forward stability analysis we defined as $ \frac{ || \tilde{f} (x) - f(x) ||} {||f(x) ||} \leq \sigma k_{rel} (f, x) \epsilon + o( \epsilon), ( \epsilon \rightarrow 0) $

Hello dearest people, I struggle already with the first algorithm. My attempt:

$ \frac{ || \tilde{f} (x) - f(x) ||} {||f(x) ||} = |\frac{(x_1 \ominus 2x_2) \oplus x_3 - ((x_1 -2x_2)+x_3)} {((x_1 -2x_2)+x_3)} | = | \frac{ ((x_1 -2x_2)(1+ \delta) + x_3)) (1+\delta) -((x_1-2x_2)+x_3}{(x_1 - 2 x_2) +x_3} |$

From here on I am not sure how to estimate right..

(Oh and by the way $ \o (x) = x(1+ \delta) $ and those circles are actually supposed to be squares, I apologize)

Would appreciate any help, because I couldn't find any good examples which could help me solving this task.

wondering1123
  • 1,079

1 Answers1

4

Stability analysis is always a very ugly task. I will try to explain it for the first algorithm, and I hope that this will give a some ideas how to start. You can find your approach in this answer as well. I just wrote it a bit more systematic.
For a single operator one can relate machine and exact operation by:

$$x_1 \ominus x_2 = \text{rd}(x_1-x_2) = (x_1-x_2)(1+ε)$$ with $|ε|≤\text{eps}$, the machine precision, and $\text{rd}$ the "rounding" of the machine.

The first algorithm is given by: $$\tilde{f} (x) := ( x_1 \ominus 2x_2) \oplus x_3$$ And we can rewrite that to \begin{align*} u&:= x_1 \ominus 2x_2 \\ y&:= u\oplus x_3 \end{align*}

Using the definition above we get: $$ u = (x_1-2x_2)(1+ε_1)$$ and therefore $$y = [(x_1-2x_2)(1+ε_1)]\oplus x_3 = ((x_1-2x_2)(1+ε_1)+x_3)(1+ε_2)$$

Simplifying that expression leads to: \begin{align*} y&= [(x_1 -2x_2) + (x_1-2x_2)ε_1 + x_3](1+ε_2)\\ &= (x_1-2x_2)+x_3+ (x_1-2x_2)ε_1 + (x_1-2x_2)ε_2 + (x_1 - 2x_2)ε_1ε_2 + x_3ε_2\\ &= \underbrace{(x_1-2x_2)+x_3}_{y} + (x_1-2x_2)(ε_1+ε_2) + x_3 ε_2 + \mathcal{O}(\text{eps}^2) \end{align*}

This leads to : $$\left|\frac{Δy}{y}\right| \overset{.}{≤} \frac{|(x_1-2x_2)(2\text{eps})+x_3\text{eps}|}{|x_1-2x_2+x_3|}=\text{eps}\frac{|2(x_1-2x_2)+x_3|}{|x_1-2x_2+x_3|}$$

The $\overset{.}{≤}$ means first order approximation.

Now it get's a bit tricky, as this depends on the results of the other algorithms. If all results are close you might need to work a little bit more to compare them. Otherwise I would do this: \begin{align*}\left|\frac{Δy}{y}\right| &\overset{.}{≤} \text{eps}\frac{|2(x_1-2x_2)+x_3|}{|x_1-2x_2+x_3|} ≤ \text{eps}\frac{|x_1-2x_2+x_3| + |x_1-2x_2|}{|x_1-2x_2+x_3|} \\ &= \text{eps}(1+\frac{|x_1-2x_2|}{|x_1-2x_2+x_3|}) =\text{eps}(1+\frac{1}{|1+\frac{x_3}{x_1-2x_2}|}) \end{align*} So if $\frac{x_3}{x_1-2x_2}\approx -1$ this influence of the round-off error will be large.

In your case you wrote $x_1\approx x_2\approx x_3$, so this condition is true.

P. Siehr
  • 3,672