0
$\begingroup$

I could never quite grasp the precise concept. For starters, some books seem to use absolute error to find the number of correct digits the aproximation shares with the exact value whereas others use relative error. To me, it makes more intuitive sense to use the former, but even so, if you take, for example the numbers 2.97 an 3.01, the abs error is 0.04 which is less than $$0.5*10^{-1}$$ which means they share at least one digit, but I don't see it. What digit is that? It's even more confusing to me when it comes to iterative methods since you don't have access to the exact value. I tried running this code to see if things would get a little more clear:

def eulers_number():
    n = 2
    k = [2,2.25]
    while abs(k[1]-k[0]) >= 0.5 * 10**(-12):
        n = n * 2
        k.append((1 + 1/n)**n)
        k = k[1:]
    print(k)
    return k[1]

The output is [2.7182818284584274 , 2.718281828458736], the last two iterations, so I should have 12 correct decimal places and yet my calculator gives me 2.718281828459045.... so my 12th digit is actually wrong(8 instead of 9). Why is that? I'm sorry if it all seems pretty basic, but it bugs me a lot and I would deeply appreciate any help. Thanks in advance!

$\endgroup$

1 Answer 1

1
$\begingroup$

Digits and Distance

In your leading example, you get the same digits in the number $3.0$ if you round to one digit after the dot.

In general it is not that easy to connect the digit sequence and the rounding error, one can always construct some counter-examples. However, in designing algorithms it is more natural to measure the convergence in terms of distance than of digits, so one uses that in most cases when two numbers are less than $0.5\cdot 10^{-k}$ apart, they share the same $k$ digits after the dot after rounding to these $k$ digits. In about half the cases (like $1.04$ and $1.06$ with $k=1$) the last digit may differ by 1. This is a good enough compromise, so that the digit-to-error correspondence is very often understood this way.

Increment and Limit

In the second part you make the wrong claim that the increment of a sequence is indicative of the distance to the limit of the sequence. Take as example the harmonic series. Its terms or increments $\frac1n$ fall below every threshold, however the series itself diverges to infinity.


However, it is correct that in efficient numerical methods, where the convergence is at least linear, then indeed the distance to the limit is proportional to the last increment. As one can see from the remainder formula of the geometric series. For quadratic or higher order convergence, the factor of this proportionality is close to $1$. See for example the Newton-Kantorovich theorem.


For the given case $a_n=(1+\frac1n)^n$ using the sub-sequence with $n=2^m$, one gets indeed linear convergence. It is known that $$ a_n=\exp(n\ln(1+\tfrac1n))=\exp(1-\tfrac1{2n}+\tfrac1{3n^2}+...) =e\cdot (1-\tfrac1{2n}+\tfrac7{12n^2}+...) $$ Thus the increment is $a_{2n}-a_n=\frac{e}{4n}+O(n^{-2})$ while the distance to the limit $e-a_{2n}=\frac{e}{4n}+O(n^{-2})$ is of the same size. This distance pattern is quite faithfully represented in your calculated values, using the digits after the 10th, $a_n=...5842..., a_{2n}=...5873..., e=...5904...$ where the difference is both times $...0031...$ Thus rounding of $e$ and $a_{2n}$ to 12 digits is expected to have the same digit sequence. However, the distance of $e$ and $a_n$ is twice as large and thus can have a different last digit in the rounded number.

$\endgroup$
1
  • $\begingroup$ Thank you so much for your answer. Do you have any good books to recommend that go into detail about this stuff rather than using the usual "this is how things are" approach? $\endgroup$
    – cabutchei
    May 31, 2020 at 23:09

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.