Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  dexter04 Feb 1 '13 at 11:41
    
Hm... that's certainly a valid point. I guess you are right, sensitivity would indeed make more sense here. –  Johnny Westerling Feb 1 '13 at 11:58
add comment

1 Answer 1

up vote 2 down vote accepted

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?

share|improve this answer
    
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! –  Johnny Westerling Feb 1 '13 at 15:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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