8:52 PM

The Taylor series approximation of e^x converges rapidly for small positive values of x, but gives incorrect results for negative values, because computing the series requires subtracting large numbers from each other to get a small number, and on a computer this will introduce rounding errors.

The solution is to rewrite e^x as 1/e^−x when x<0. This can be computed without rounding errors reducing the accuracy of the final result. This solution is straightforward, but it was not obviously necessary in the original computation. The lesson, again, is to watch out for rounding errors.

The Taylor series approximation of e^x is accurate for larger positive values of x, but the number of terms that must be computed in order for the approximation to converge increases as x increases. This is a problem, because each term of the Taylor series has xⁿ in the numerator. If the number of required terms gets too large, xⁿ will become too large for the computer to represent and the computation will fail. My calculator gives e⁷⁹ as 2.038281066651×10³⁴. The Taylor series approximation returns infinity, because it requires more than 163 terms and 79¹⁶³ is greater than the computer can represent.

Once again, the solution is to rewrite the original function. x can be broken up into an integer part and a fractional part, and then e^x=e^{integer part}×e^{fractional part}. e^{fractional part} can be calculated as a Taylor series expansion. If e is stored as a constant, then e^{integer part} can be directly multiplied out, and this can be computed when a strict Taylor series approximation of e^x fails.

Taylor series can also be used to approximate sin(x) and cos(x). Like with e^x, the series require fewer terms to converge near 0, so the identities sin(x)=sin(x+2πn) and cos(x)=cos(x+2πn) for all positive and negative integer values of n should be used so the Taylor series is only computed for −π<x<π.

Finally, Taylor series can be used to approximate ln(x). The catch here is that e^x, sin(x), and cos(x) are all computed based the difference between x and 0, while ln(x) must be computed based on the difference between x and 1. This makes the math a little messier but isn't otherwise a big deal. However, the Taylor series for ln(x) does not converge for x>2. Since ln(x) = −ln(1/x), to compute ln(x) for x≥2, compute −ln(1/x) instead.

0 comments

6:47 PM

I have been considering resurrecting this blog to talk about my current interest, which is math. This fall I'm taking a course in Numerical Analysis, and I'm finding that in order to make sense of the class, I have to rethink through the lectures after each class. As long as I'm doing this thinking, I figured I should post it. Hopefully posting about math in a generic blogger blog won't turn into too much of a headache.

I'm going to go ahead and start with Lecture 1, which was last week's class. I likely don't know what I'm talking about. If anyone sees this and wants to leave a comment, please do.

The big picture on Numerical Analysis is that math gives us all kinds of tools for understanding the world. However, it's not always easy to go from a mathematical formula to a number, and often, we care about the number rather than the formula. Numerical Analysis is the techniques used to approximate the values of formulas and turn them into numbers.

Certain mathematical operations are easy. Addition, subtraction, multiplication, and division are all easy, and you can do a lot with them, such as evaluating polynomials. If f(x) is a polynomial, you can find the value of f(x) for any x just by a bunch of multiplications and additions. But there are lots of functions that are not polynomials, and these are hard to evaluate. For example, f(x)=e^x, f(x)=sin(x), and f(x)=∫_−∞^z (e^−t2/2)/(2π)^1/2 dt are common functions with many applications which cannot be directly evaluated at more than a few points.

Numerical analysis shows how to approximate the values of these functions. For example, we can look at how to approximate f(x)=e^x for values of x other than 0. Math tells us that lots of functions, including the exponential function, can be written as a Taylor series. The general form of a Taylor series is f(x) = f(a) + f′(a)(x−a)/1! + f″(a)(x−a)²/2! + f⁽³⁾(a)(x−a)³/3! + … . Written compactly, this is ∑_n=0→∞ f⁽ⁿ⁾(a)(x−a)ⁿ/n! .

The good news is that for f(x)=e^x, f′(x)=e^x=f(x), and therefore f⁽ⁿ⁾(x)=e^x for all integers n≥0. In combination with the fact that a⁰=1 for all a≠0, this gives the Taylor series for e^x=∑_n=0→∞ xⁿ/n! = 1 + x + x²/2 + … . This means that a Taylor series turns functions into polynomials, and since polynomials can be evaluated with addition, subtraction, multiplication, and division, we can evaluate functions other than polynomials, as long as they can be expressed as a Taylor series.

The bad news is that this is an infinite polynomial. We have turned e^x from a function that can't be evaluated at all into one that can be evaluated, but requires an infinite number of calculations. Fortunately, math tells us that if you take a finite number of terms of the Taylor series, that sum will approximate the true value of the function, and the approximation gets as close as you want as long as you take enough terms. Math tells us to figure out how many is "enough", so you can write a little computer program that does the calculations and spits out the value of e^x for any value of x. This value is an approximation, but it can be a good enough approximation for whatever purpose you're using it for.

Let's do a quick demonstration of this. The table below shows a sequence of approximations of f(1)=e¹=e. For each value of n, the table shows the sum of the first n terms of the Taylor series expansion of e^x, evaluated at x=1. For the record, my calculator says that e=2.71828182846.

The Taylor series reaches the same level of accuracy as my calculator in 14 steps, which is relatively quick. According to math, this calculation works for any value of x, although it may require more steps depending on the value of x to get the desired accuracy. In the real world, however, if x gets too large, then e^x can be bigger than the computer can represent. For example, if x=10²⁰, the resulting sequence of finite sums is:

Actually, much smaller values of x will return a value of ∞ on most computers. e⁷¹⁰ is larger that the computer can represent, although it takes many more steps to get there.

There's a much bigger problem with using computers to calculate e^x using a Taylor series expansion. Using the Taylor series expansion, calculating e⁻²⁰ requires 87 steps, but the result eventually settles on 4.1736374994×10⁻⁹. This looks reasonable, but my calculator says the answer is 2.06115362244×10⁻⁹. We can see the problem by looking at the individual sums in the expansion.

The problem is that the final result is a little tiny number, but early steps in the sum involve adding and subtracting really big numbers from each other. According to math, the Taylor series gives the correct result. On a computer, however, numbers are slightly rounded off. When a bunch of big numbers are added and subtracted from each other to get a small result, the rounding errors can make the final answer totally wrong.

This is kind of terrifying. You can write a program that math says will give the right answer, to the accuracy that you need it, but the computer program could introduce rounding errors that make the final answer totally wrong. By looking at the intermediate steps in this case, we could guess that there might be a problem with the final answer, but if you are handed a computer program that claims to evaluate e^x, or any other function, it's possible that the program will be mathematically correct but give incorrect answers for some inputs. These errors may only be detectable after the fact. The appropriate response is probably justifiable paranoia.

0 comments