Let us define $\alpha=x^{2}-y^{2}$ and $\beta=2xy$ for $x,y\in\mathbb{R}$. In order to calculate the $\alpha$ and $\beta$, we use the following algorithm:

$$p:=x-y;\quad q:=x+y;\quad \alpha=p\cdot q;\quad \beta=2\cdot x\cdot y$$

I wanted to prove that the above algorithm is numerically stable. I understand that numerical stability means that an error in the input will not significantly shift the produced output. Thus, intutively, I believe I should insert an $\varepsilon$ error term in the input and see how the algorithm behaves with it. However, I do not see how this could be properly done. I would be grateful for ideas.

  • $\begingroup$ Stability doe not make a lot of sense here as the procedure is not iterative. So, there is no blow-up or divergence. Are you asking for sensitivity w.r.t parameters x and y? $\endgroup$ – dexter04 Feb 1 '13 at 11:41
  • $\begingroup$ Hm... that's certainly a valid point. I guess you are right, sensitivity would indeed make more sense here. $\endgroup$ – Johnny Westerling Feb 1 '13 at 11:58

What you can try to show, is how your algorithm behaves, if you have a certain error in your input.

Therefore, let $\tilde x = x +\epsilon$ and $\tilde y = y +\delta$ be your perturbed input. From that we get

$$ \tilde p = \tilde x - \tilde y ,\quad \tilde q = \tilde x + \tilde y $$ And with that \begin{align} \tilde \alpha &= \tilde p \cdot \tilde q = ((x+\epsilon)-(y+\delta))\cdot ((x+\epsilon)+(y+\delta)) \\& = ...= x^2-y^2+2\epsilon x-2 \delta y + \epsilon^2-\delta^2 \\&= \alpha +2\epsilon x-2 \delta y + \epsilon^2-\delta^2 \end{align} So you can see, that your algorithm for $\alpha$ is stable, in the sense that $\tilde \alpha \rightarrow \alpha$ if $\delta,\epsilon \rightarrow 0$. For $\beta$ you obtain $\tilde \beta = \beta+ 2(\epsilon y +\delta x +\epsilon \delta) $, which is also stable in the sense above. Maybe instead of stability you mean well-conditioned?

  • $\begingroup$ Nope, it was about stability, but it seems to me that your answer makes a good enough argument (especially in the light of dexter04's comment). Thanks! $\endgroup$ – Johnny Westerling Feb 1 '13 at 15:01

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.