We look at the challenges of numerical algorithms i.e we show that there are limitations of algorithmic power.
Numerical algorithms are those for computations of problems in a continuous mathematical world.
Therefore the first obstacle is that we have finite approximations of what is really infinite objects.
This results in truncation erros.
The second class of errors we get from round off errors. Real numbers cannot be used accurately because we cannot represent the real answers so we put them in a range.
To overcome the first limitation, we use what is called the Taylor's expansion.
e ^ x = 1 + x + x ^ 2 / 2! + x ^ 3 / 3! + ... x ^ n / n! + ...
we stop the expansion at a definite n. Anything beyond that fixed n is the truncation error.
The second class is evident from when we take a graph of the curve and want to compute the area under it. In this case, we slice up the area into geometrical shapes, trapezoidals to be precise and this is called the trapezoidal rule by which we approximately compute the area under the curve.
One way to get an upper bound on the truncations error is
to use the equation:
e ^ x - ( 1 + x + x ^ 2/ 2! + ... x ^n / n! ) <= M/(n+1)! |x| ^ n+1 where M = max e ^ y for 0 <y <x
i.e by choosing an upper bound M for any y that can be between 0 and x, we are able to establish an upper bound on the truncation error.
We can take an example to show how we come up with M
Let's say we target e ^ 0.5 with an error of 0.0001
Since 0< y < x and e ^ y is increasing , this has to be less than e ^ 0.5. Since e is between 2 and 3, we can take value of M as 4 ^ 0.5 = 2
Now the truncation error is M / (n + 1)! |x| ^ n + 1 and this is determined to be upper bounded by ( as per our chosen values) as 2 / (n + 1) ! | 0.5 | ^ n + 1 which should be less than 0.0001 and this lets us find out n. In this case, we may find n = 5.
We can similarly write a formula to find the upper bound on the error of the trapezoidal rule. Here the problem is defined as how thin and how many trapezoidals can be put between lower and upper limit of the curve.
Numerical algorithms are those for computations of problems in a continuous mathematical world.
Therefore the first obstacle is that we have finite approximations of what is really infinite objects.
This results in truncation erros.
The second class of errors we get from round off errors. Real numbers cannot be used accurately because we cannot represent the real answers so we put them in a range.
To overcome the first limitation, we use what is called the Taylor's expansion.
e ^ x = 1 + x + x ^ 2 / 2! + x ^ 3 / 3! + ... x ^ n / n! + ...
we stop the expansion at a definite n. Anything beyond that fixed n is the truncation error.
The second class is evident from when we take a graph of the curve and want to compute the area under it. In this case, we slice up the area into geometrical shapes, trapezoidals to be precise and this is called the trapezoidal rule by which we approximately compute the area under the curve.
One way to get an upper bound on the truncations error is
to use the equation:
e ^ x - ( 1 + x + x ^ 2/ 2! + ... x ^n / n! ) <= M/(n+1)! |x| ^ n+1 where M = max e ^ y for 0 <y <x
i.e by choosing an upper bound M for any y that can be between 0 and x, we are able to establish an upper bound on the truncation error.
We can take an example to show how we come up with M
Let's say we target e ^ 0.5 with an error of 0.0001
Since 0< y < x and e ^ y is increasing , this has to be less than e ^ 0.5. Since e is between 2 and 3, we can take value of M as 4 ^ 0.5 = 2
Now the truncation error is M / (n + 1)! |x| ^ n + 1 and this is determined to be upper bounded by ( as per our chosen values) as 2 / (n + 1) ! | 0.5 | ^ n + 1 which should be less than 0.0001 and this lets us find out n. In this case, we may find n = 5.
We can similarly write a formula to find the upper bound on the error of the trapezoidal rule. Here the problem is defined as how thin and how many trapezoidals can be put between lower and upper limit of the curve.
No comments:
Post a Comment