4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Or does someone has a good example? :) $\endgroup$ Nov 7 '17 at 9:51
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you So much :) made this hole thing a lot more clearer! Thank you for your time. $\endgroup$ Nov 8 '17 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.