sharadsinha

Numerical Stability in Calculations

In Design Methodologies, Embedded Systems, Engineering Principles, Mathematics on January 24, 2013 at 11:44 PM

I did not have any course on algorithms in my undergraduate education. I studied about them (their properties, design etc.) during my research work. I now realize why their study is important for anyone who wants to be really good at designing algorithms or implementing them. After all, algorithms solve problems. I recently came across the subject of numerical stability of algorithms, numerical algorithms to be precise. While algorithms help solve problems, they need to be implemented on a digital machine (a computer for example) which has limited precision. Whatever number system we use, they cannot cover all the numbers present in exact  mathematics. This leads to approximations as well as upper and lower bounds on the numbers that can be represented. Also, approximations can be the source of errors and deviations from the exact numerical answer. For instance, on a machine with only 3 digit precision, numbers like 22, 2.22, 0.110, 100, 177 can be represented. Now if you try to add 2 and 1000 instances of 0.11 , your sum would be 112 on this machine and this matches with the exact answer. Similarly, if you try to add 9 and 9 instances of 0.11, the answer on this machine would be 9.99, which matches with the exact answer. However, if you try to add 10 and 9 instances of 0.11 in that order i.e 10+0.11+0.11…., the machine would return 10 as answer because the moment you try to add 0.11 to 10, you are going to exceed the precision of the machine. Now imagine doing the same calculation in the reverse order i.e adding all the nine 0.11’s first and then 10 i.e. 0.11+0.11+….+10, the machine would return an answer of 0.99 which is far off from the actual answer 10.99 and far worse than the previous approximation of 10 (for the other order of addition). This means that the way you arrange your numbers( in memory, for instance an array) to be added also may influence the sum!! I wish that embedded systems engineers read more on this subject so that the numerical errors that we see cropping up in such systems get reduced. A nice introduction is at wikipedia.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: