Homework Question from Accuracy and Stability of Numerical Algorithms, 2nd Edition, by Nicholas J. Higham, page 33:enter image description here

So every time we store an number and do a operation, we introduce an error bounded by machine epsilon e, so for example, the computed sum of two number is fl($x_1+x_2$)=$[x_1(1+d_1)+x_2(1+d_2)](1+d_3)$, where $|d_i|<=e$. A complete example of subtraction is like this:enter image description here Hope this can express my question.

This is my try:enter image description here

I reckon, as the inequality we want has (n+3)u, and all higher terms are included in $O(u^2)$, I think we need only count how many first order terms left in the final multiplication result. However, the calculation already gets complicated and I am not sure whether I am on the right track, even if I am, it is easy to make mistake in this way, is there an easier and smart way to attack this question?

Any suggestion would be appreciated! Thanks in advance!

  • $\begingroup$ How do you get that very first equality in your attempt? It looks like you've just multiplied every term by additional factors, which generally doesn't provide equality. And since you've not explained what $u$ is, I have no real way of telling if you are on the right track or not. $\endgroup$ – Paul Sinclair Aug 23 '15 at 3:39
  • $\begingroup$ @PaulSinclair, thanks for your comments, I am using the definition (13.5) and (13.7) on page 99 books.google.com.au/…. $\endgroup$ – Bob Aug 23 '15 at 4:00
  • $\begingroup$ @PaulSinclair, and also, I should write fl(sum of $x_i's)=x_1(1+d_1)+x_2(1+d_2)$... $\endgroup$ – Bob Aug 23 '15 at 4:02
  • $\begingroup$ <s>Can't see the book</s>, and I understand what the sum is, but I don't see how it is equal to what you claim it is equal to. Edit - the first time visited the link, it told me I couldn't see the book. The second time, it showed it to me. $\endgroup$ – Paul Sinclair Aug 23 '15 at 4:07
  • $\begingroup$ Those definitions do not mention any $u$ either. What is $u$? $\endgroup$ – Paul Sinclair Aug 23 '15 at 4:14

Since its starting to complain about conversations in comments, I'll put this in a full post: I understand that you are not saying machine addition was the same as regular addition. What I finally realized was that before the first equal sign, you are using "+" to represent machine addition (for the main additions, the addition in the $(1 + \delta) factors is regular addition), but after the first equal sign, you are using it to represent regular addition, and that is why suddenly everything picks up additional factors.

Again, I suggest you try proving it inductively. First show it to be true for $n = 2$, then assume it is true for $n = k$ and use that to show that it is also true for $n = k + 1$. The mathematics shouldn't get as far out-of-hand that way.


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.