deutsch     english    français     Print

 

8.5 SEQUENCES, CONVERGENCE

 

 

INTRODUCTION

 

Sequences of numbers have fascinated people for a long time. Already in ancient times around 200 B.C. Archimedes had approximated the number of Pi through a sequence of numbers that he found by calculating the perimeters of regular polygons with increasingly many vertices that fit into a circle. It was already clear to him then that the circle could be regarded as a border-line case of a regular polygon with infinitely many vertices. Therefore, he found that the perimeters of the polygons had to strive towards the circumference of the circle.

A sequence of numbers consists of the numbers a0, a1, a2, etc., thus of the terms an with index n = 0, 1, 2, etc. (sometimes it begins with n = 1). A formation rule clearly determines how big each number is. If ak is defined for any natural number, however large it may be, we speak of an infinite sequence of numbers. The principle can be specified as an explicit expression of n. However, a term may also be calculated from previous terms of the series (recursive rule). In this case, the start values must also be known.

A convergent sequence has a very descriptive property: there is a unique number g called a limit that the terms gradually approach, which means that you can choose any arbitrarily small neighborhood interval of g so that none of the following terms fall outside of the chosen interval starting at a definite n. You can imagine the neighborhood as a house around the limit: before that, the sequence may leap around wildly, however after a certain n all terms of the sequence end up in the house no matter how small it may be.

Number sequences can be studied experimentally using the computer. In order to illustrate them, you use various graphical representations: You can, for instance, similar to the above illustration, draw all terms as points or lines and analyze whether there is a limit point. However, you can also investigate how the sequence behaves for large values of n by representing it as a two dimensional graph where the n are on the x-axis and the an on the y-axis.

PROGRAMMING CONCEPTS: Limit point, convergence, Feigenbaum bifurcation, chaos

 

 

THE HUNTER AND HIS DOG

 

A hunter walks with his dog with the velocity u = 1 m/s to their hunting lodge d = 1000 m away. However, since the hunter walks too slowly for the dog, the dog proceeds as follows: It runs alone at its own velocity u = 20 m/s to the hunting lodge, turns around, and then runs back to its owner. As soon as it reaches its owner, it turns around again and runs back to the hunting lodge, and then continues this behavior.

You would like to simulate this procedure with a program. With every press of the button in your program, you draw the next meeting point of the hunter and the dog and write out the position next to it. The successive values form a sequence of numbers whose behavior you want to study.  Since the same amount of time passes for the hunter and the dog between each of their meetings, the increase in position of the hunter can be described as follows:

  (da)/ u = (2 * (d - a) - da)/          v
 

From this, you can deduce the following relationship with little knowledge of Algebra:

  da = c * (d - x) mit
c = (2 * u)/ u + v

As you might have expected, the numbers an pile up against the limit number 1000.

from gpanel import *

u = 1 # m/s
v = 20 # m/s
d = 1000  # m
a = 0     # hunter
h = 0     # dog
c = 2 * u / (u + v)
it = 0

makeGPanel(-50, 50, -100, 1100)
title("Hunter-Dog problem")
line(0, 0, 0, 1000)
line(-5, 1000, 5, 1000)
line(-5, 1050, 5, 1050)
line(-5, 1000, -5, 1050)
line(5, 1000, 5, 1050)

while not isDisposed():
    move(0, a)
    fillCircle(1)
    text(5, a, str(int(a)))
    getKeyWait()
    da = c * (d - a)
    dh = 2 * (d  - a) - da
    h += dh
    a += da 
    it += 1
    title("it = " + str(it) + "; hunter = " + str(a) +
          " m; dog = " + str(h) + " m")
Highlight program code (Ctrl+C to copy, Ctrl+V to paste)

 

 

MEMO

 

One says that the number sequence an converges and that its limit value is 1000.

Think about why this problem is of a theoretical nature. It corresponds to the ancient anecdote where Achilles was invited to race with a turtle. Since he was ten times faster than the turtle, the turtle would have gotten a head start of 10 meters. Achilles refused to compete because in his opinion, he had no chance to catch up with the turtle. So, he argued: In the time that he needed for the first 10 meters, the turtle would have already advanced 1 meter. In the time that he needed for this one meter, the turtle would already be 10 cm further. In the time that he then needed for these 10 cm, the turtle would already be another 1 cm further, and so forth. What do you think about this?

 

 

BIFURCATION DIAGRAM (FEIGENBAUM BIFURCATION)

 

You got to know the logistic growth in the context of population dynamics. The population size  xnew in the next generation is calculated from its current size x from a quadratic relationship. The relationship is simplified in the following (parameter r can be arbitrarily chosen) :

xnew = r * x * (1 - x)

an+1 = r * an * (1 - an)

You wonder whether the resulting recursively defined sequence  with a0 = 0.5 converges and what the limit value is in this case.

You examine the behavior with an extremely simple program where you plot the first 1,000 terms of the sequence as points for 1,000 equidistant values of r in an area from 0 to 4.

With a fixed r, you should always begin with the same starting value a0 = 0.5 and draw the terms only from n = 500, since you are only interested in finding out if the sequence is convergent or divergent.
 
from gpanel import *

def f(x, r):
     return r * x * (1 - x)

makeGPanel(-0.6, 4.4, -0.1, 1.1)
title("Tree Diagram")
drawGrid(0, 4.0, 0, 1.0, "gray")
for z in range(1001):
    r = 4 * z / 1000
    a = 0.5
    for i in range(1001):
        a = f(a, r)
        if i > 500:
            point(r, a)
Highlight program code (Ctrl+C to copy, Ctrl+V to paste)

 

 

MEMO

 

In the experiment, you detect the limit points of the sequence for a certain r. Based on a computer simulation, you can establish the following assumptions: For r < 1 there is a limit point at 0 and so the sequence converges to 0. The sequence likewise converges in the area between 1 and 3. There are initially two and later more limit points for an even larger r, but the sequence no longer converges. For even larger values of r the sequence chaotically jumps back and forth.

 

 

THE EULER NUMBER

 

One of the most famous sequences are the numbers defined by the formation rule:

  an = (1 + (1)/ n )n    mit n = 1, 2, 3, ...

It is not clear what this sequence does with an increasing n, since on the one hand 1 + 1/n increasingly approaches the number 1, and on the other hand, this number is exponentiated with an increasing exponent. You can try to solve this mystery with a simple computer experiment.

 
from gpanel import *

def a(n):
     return (1 + 1/n)**n

makeGPanel(-10, 110, 1.9, 3.1)
title("Euler Number")
drawGrid(0, 100, 2.0, 3.0, "gray")
for n in range(1, 101):
    move(n, a(n))
    fillCircle(0.5)
Highlight program code (Ctrl+C to copy, Ctrl+V to paste)

 

 

MEMO

 
an = (1 + (1)/ n )n
The sequence converges to a number in the order of 2.7.

This is a case of the Euler number e, arguably one of the most famous numbers ever.

 

 

QUICK CONVERGING SEQUENCES FOR THE CALCULATION OF PI

 

The calculation of πfor as many digits as possible poses a challenge since ancient times. A sum formula was discovered only in 1995 by the mathematicians Bailey, Borwein and Plouffe called the BBP formula. They proved that you can get exactly π as the limit value of a sequence whose n-th term is the sum from k = 0 to k = n of:

   1 )/ 16k (    4   )/ 8k + 1 -      2   )/ 8k + 4    1   )/ 8k + 5    1   )/ 8k + 6 )       .  

Your program uses the Python modulle decimal which provides the decimal numbers with a high level of accuracy. The constructor creates such a number from an integer or a float where common mathematical operation signs can be used directly.

You can set the accuray with getcontext().prec. This roughly corresponds to the number of decimal places used.

Each time a button is pressed, your program calculates the next term of the sequence and represents the value in a EntryDialog.

from entrydialog import *
from decimal import *
getcontext().prec = 50

def a(k):
    return 1/16**Decimal(k) * (4 / (8 * Decimal(k) + 1) - 2 
    / (8 * Decimal(k) + 4) - 1
    / (8 * Decimal(k) + 5) - 1 / (8 * Decimal(k) + 6))

inp = IntEntry("n", 0)
out = StringEntry("Pi")
pane0 = EntryPane(inp, out)
btn = ButtonEntry("Next")
pane1 = EntryPane(btn)
dlg = EntryDialog(pane0, pane1) 
dlg.setTitle("BBP Series - Click Next")
n = 0
s = a(0)
out.setValue(str(s))
while not dlg.isDisposed():
    if btn.isTouched():
       n = inp.getValue()
       if n == None:
           out.setValue("Illegal entry")
       else:
           n += 1
           s += a(n)
           inp.setValue(n)
           out.setValue(str(s))
Highlight program code (Ctrl+C to copy, Ctrl+V to paste)

 

 

MEMO

 

At just 40 iterations the displayed number for π no longer changes.

The program ends when you close the display window, since isDisposed() is True.

 

 

EXERCISES

 

1.


The Fibonacci sequence is defined such that a term is equal to the sum of its two predecessors, with the first and second terms being 1. Calculate the first 30 terms of the sequence and display them on a x-y graph.

2.

The Fibonacci sequence diverges, whereas the sequence of quotients of two consecutive terms converges. Similar to exercise 1, display this sequence of quotients graphically and determine the approximate value of the limit.

3.

Consider the following sequence with the start value a0 = 1:

  an+1 = (1)/ 2 * ( an (2)/ an )n

Draw the terms as points on a number line and write their value in an output window. As you can see, the sequence converges. You can calculate the limit value x somewhat generously as follows: For large n subsequent terms may not be easily distinguishable, so in the border line case we get:

  x =   (1)/ 2 *  ( x  +  (2)/ x )   und aufgelöst   x = √ 2  

Formulate this result as a guide on how you can approximately determine the square root of 2 using the 4 basic arithmetic operations. How does the algorithm need to be changed for the determination of the square root of any given number z?


 

 

 

ADDITIONAL MATERIAL


 

ITERATIVE SOLUTION OF AN EQUATION

 
Wie du in Aufgabe 3 gesehen hast,  ist x = √ 2 die Lösung der Gleichung
  x =  f(x)    mit    f(x) = (1)/ 2 * ( x +   (2)/ x )  

It is illustrative to display the procedure of solving this equation graphically. To do this, draw both the function graph y = f(x)  and the angle bisector y = x  in the same coordinate system. The solution is at the intersection of the two curves.

The iterative solution corresponds to the successive pass of a point on the function graph horizontally towards the bisecting angle and vertically down towards the nearest point of the function graph.

.

 
from gpanel import *

def f(x):
    return 1 / 2 * (x + 2 / x)

makeGPanel(-1, 11, -1, 11)
title("Iterative square root begins at x = 10. Press a  key...")
drawGrid(0, 10, 0, 10, "gray")

for i in range(10, 1001):
    x = 10 / 1000 * i
    if i == 10:
        move(x, f(x))
    else:
        draw(x, f(x))
        
line(0, 0, 10, 10)

x = 10
move(x, f(x))
fillCircle(0.1)
it = 0
while not isDisposed():
    getKeyWait()
    it += 1
    xnew = f(x)
    line(x, f(x), xnew, f(x))
    line(xnew, f(x), xnew, f(xnew))
    x = xnew
    move(x, f(x))
    fillCircle(0.1)
    title("Iteration " + str(it) + ": x = " + str(x))
Highlight program code (Ctrl+C to copy, Ctrl+V to paste)

 

 

MEMO

 

You can clearly see that with each press of the key the points move quickly towards the point of intersection. Just a few iterations results in a solution with 10 digits of accuracy.