Mathématiques avec Python et Ruby/Suites en Ruby

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche


Une suite de nombres (éventuellement complexes) ne peut se représenter en machine parce qu'elle comprend une infinité de termes. Alors on n'en représente qu'une partie sous forme de liste de nombres. Et Ruby manipule très bien ce genre d'objets.

Définition de suites[modifier | modifier le wikicode]

Par fonction[modifier | modifier le wikicode]

Une suite est une fonction de dans (ou ...). On peut donc facilement calculer les premiers termes de celle-ci en utilisant la méthode collect d'une liste d'entiers (approximation finie de ). Par exemple pour vérifier que la suite tend vers 0, on peut essayer

(1..50).collect{|n| puts(1/n.to_f)}

Suites récurrentes[modifier | modifier le wikicode]

Pour une suite récurrente, chaque terme est défini à partir du précédent.

Suite logistique[modifier | modifier le wikicode]

La suite logistique est chaotique sur [0;1]. Pour le vérifier, on peut faire

u=0.1
50.times do
    u=4*u*(1-u)
    puts(u)
end

En constatant que , on peut vérifier que, quoique chaotique, cette suite est formée de fractions:

require 'mathn'
u=1/10
10.times do
    u=4*u*(1-u)
    puts(u)
end

Quoique chaotique, cette suite ne fait pas un bon générateur pseudo-aléatoire, parce que les nombres proches de 0 et 1 sont trop souvent visités. Pour le vérifier graphiquement, on peut dessiner un histogramme des 4000 premières valeurs de la suite, avec l'algorithme suivant:

  1. On fait comme ci-dessus, mais au lieu d'afficher u, on incrémente l'entrée d'un tableau des effectifs indexée par sa troncature. C'est ce tableau qui va être représenté graphiquement.
  2. Ensuite, on représente chaque effectif par un rectangle de largeur 4 pixels et de hauteur l'effectif correspondant. Les rectangles sont bleus, remplis de vert.

Le tout est fait en écrivant les instructions dans le langage svg, engendrées par Ruby, dans un fichier HistogramRuby1.svg visible ci-dessous. Voici le script au complet:

figure=File.open("HistogramRuby1.svg","w")
figure.puts('<?xml version="1.0" encoding="utf-8"?>')
figure.puts('<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"')
figure.puts('"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">')
figure.puts('<svg xmlns="http://www.w3.org/2000/svg" width="500" height="360">')

effectifs=[0]*100
u=0.1

4000.times do
    u=4*u*(1-u)
    effectifs[(100*u).to_i]+=1
end

(0..99).collect{|n| figure.puts('<rect x="'+(4*n+50).to_s+'" y="'+(320-effectifs[n]).to_s+'" width="4" height="'+effectifs[n].to_s+'" fill="green" stroke="blue" stroke-width="1" />')}

figure.puts('</svg>')
figure.close

Et voici le fichier produit par le script:

HistogramRuby1.svg


Suites arithmétiques et géométriques[modifier | modifier le wikicode]

Les suites arithmétiques et géométriques sont aussi des suites récurrentes.

Suites arithmétiques[modifier | modifier le wikicode]

Une suite est arithmétique de raison r si . Cette définition est récurrente.

Par exemple, si on place 2000 € avec des intérêts (simples) correspondant à 3 % du capital de départ, soit 60 €, on peut calculer les valeurs successives du capital pendant 20 ans avec

capital=2000.00
interet=capital*3/100.0
20.times do
    capital+=interet
    puts(capital)
end

Suites géométriques[modifier | modifier le wikicode]

Une suite est géométrique de raison r si . Les suites géométriques sont donc aussi récurrentes.

Si on place 2000 € à intérêts composés au taux de 2 % par an, l'affichage des valeurs successives du capital (arrondies à l'eurocent près) peut se faire avec

capital=2000.00
20.times do
    capital*=1.02
    puts(capital.round(2))
end

Sachant que chaque humain a deux parents et que chacun d'entre eux a aussi deux parents, etc. on peut dire que le nombre d'ancêtres à la génération n est géométrique de raison 2. Le nombre total d'ancêtres jusqu'à la génération n s'obtient par

(0..20).inject{|ancetres,generation| ancetres+=2**generation}

puts(ancetres)
puts(2**21)

On a presque autant d'ancêtres à la génération 21 qu'à toutes les générations précédentes cumulées!

Ce qui donne envie de vérifier si c'est pareil pour toutes les générations ou si c'est une spécificité de la génération 21:

genealogie=[1]*20
(1..20).collect{|i| genealogie[i]=(0..i).inject{|a,g| a+=2**g }}
generations=[1]*20
(1..20).collect{|i| generations[i]=2**i}
test=(1..20).reject{|i| generations[i]==genealogie[i-1]+2}
puts(test.size)

On crée une liste des ancêtres jusqu'à la génération n comprise (genealogie) et une liste (generations) des nombres d'ancêtres à la génération n seulement. La lise test est constituée des entiers n pour lesquels le nombre d'ancêtres à la génération n n'est pas égal au total d'ancêtres jusqu'à la génération n-1 augmenté de 2 (avec reject, on a enlevé les positifs). La longueur de ce test est très petite !

Sous Ruby on peut aussi calculer des suites géométriques de raison complexe. La somme des termes est alors particulièrement intéressante à étudier (par exemple si la raison vaut i).

Suites d'entiers[modifier | modifier le wikicode]

Suite de Fibonacci[modifier | modifier le wikicode]

Calcul des termes[modifier | modifier le wikicode]

La récurrence de la suite de Fibonacci est double, avec . Son calcul pose donc un problème algorithmique, puisqu'il faut trois variables (les deux termes à calculer et une variable tampon pour stocker temporairement l'un des deux termes, afin qu'il ne soit pas écrasé par la somme). Ce problème n'existe pas en Ruby qui permet les affectations simultanées:

a=1
b=1
for n in 1..20 do
    a,b=b,a+b
    puts(b)
end

On peut aussi le faire de manière plus Ruby:

a=1
b=1
(1..20).collect{
    a,b=b,a+b
    puts(b)
}

Nombre d'Or[modifier | modifier le wikicode]

Pour étudier le quotient de deux termes successifs de la suite:

a,b=1,1
(1..20).collect{
    a,b=b,a+b
    puts(b.to_f/a.to_f)
}

puts((5**0.5+1)/2)

Mais en fait, les nombres de Fibonacci étant entiers, leurs quotients sont des fractions, et cette variante le montre:

require 'mathn'

a,b=1,1
(1..20).collect{
    a,b=b,a+b
    puts(b/a)
}

On a donc une suite d'approximations rationnelles du nombre d'Or.

Suite de Collatz[modifier | modifier le wikicode]

Algorithmiquement, la suite de Collatz est intéressante parce que son calcul est basé sur un test de parité, et qu'elle utilise une boucle à condition de sortie:

def Collatz(x)
    if x%2==0
        return x/2
    else
        return 3*x+1
    end
end

u=65
while(u>1) do
    u=Collatz(u)
    puts(u)
end

Multiples communs[modifier | modifier le wikicode]

La suite des multiples de 5 et la suite des multiples de 7 sont arithmétiques de raisons respectives 5 et 7. On peut les construire en choisissant les nombres entiers qui sont divisibles respectivement par 5 et par 7:

a5=(1..1000).select{|n| n%5==0}
a7=(1..1000).select{|n| n%7==0}
puts(a5&a7)

Les multiples communs à 5 et 7 sont les multiples de 35, qui est le ppcm de 5 et 7. Cette construction est à l'origine de la théorie des idéaux par Kummer.

Suites et séries[modifier | modifier le wikicode]

Une série est une suite dont le terme général est défini par une somme.

Premier exemple[modifier | modifier le wikicode]

La suite définie par tend vers 1, il est relativement aisé de le démontrer, et encore plus facile de le vérifier avec Ruby:

suite=(1..50).collect{|n|
    (1..n).inject(0){|somme,k|
        somme+=1.0/(k*k.succ)
    }
}

puts(suite)

Cette suite est une suite de rationnels:

require 'mathn'

suite=(1..20).collect{|n|
    (1..n).inject(0){|somme,k|
        somme+=1/(k*k.succ)
    }
}

puts(suite)

Cette variante suggère d'ailleurs une démonstration de la convergence, grâce à l'émission d'une conjecture sur le terme général de la suite...

Deuxième exemple[modifier | modifier le wikicode]

La suite converge aussi, bien que ce ne soit pas évident en voyant son expression algébrique.

suite=(1..20).collect{|n|
    (1..n).inject(0){|somme,k|
        somme+=n.to_f/(n**2+k)
    }
}

puts(suite)

Là encore, la suite est rationnelle:

require 'mathn'

suite=(1..20).collect{|n|
    (1..n).inject(0){|somme,k|
        somme+=n/(n**2+k)
    }
}

puts(suite)


Constante d'Euler[modifier | modifier le wikicode]

On peut la calculer (et vérifier la lenteur de la convergence) avec

suite=(1..50).collect{|n|
    (1..n).inject(0){|s,k| s+=1.0/k}-Math.log(n)
}

puts(suite)

Applications[modifier | modifier le wikicode]

Méthode de Heron[modifier | modifier le wikicode]

Pour calculer avec la méthode de Heron, on utilise la suite itérée :

u=1.0
50.times do
    u=(u+5.0/u)/2.0
    puts(u)
end

Mais encore une fois, cette suite qui converge vers est formée de fractions. On a donc une suite d'approximations rationnelles de :

require 'mathn'

u=1
50.times do
    u=(u+5/u)/2
    puts(u)
end

On en déduit des approximations rationnelles du nombre d'Or :

require 'mathn'

u=1
10.times do
    u=(u+5/u)/2
    puts((u+1)/2)
end

En comparant avec les quotients de nombres de Fibonacci successifs, on voit que la méthode de Heron converge beaucoup plus vite. Cette convergence peut se montrer en représentant graphiquement la suite, ce qu'on peut faire en plaçant des points dans un fichier svg:

figure=File.open("SuiteRuby01.svg","w")
figure.puts('<?xml version="1.0" encoding="utf-8"?>')
figure.puts('<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"')
figure.puts('"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">')
figure.puts('<svg xmlns="http://www.w3.org/2000/svg" width="640" height="480">')

figure.puts('<line x1="20.0" y1="460.0" x2="540.0" y2="460.0" style="stroke:rgb(0,0,64);stroke-width:1"/>')
((0..400).select {|x| x%10==0}).collect { |x| figure.print('<text x="'+(x+20).to_s+'" y="475.0" style="font-size:6;fill:rgb(0,0,64);font-weight:normal">'+(x/10).to_s+'</text>\n'+'<line x1="'+(x+20).to_s+'" y1="455" x2="'+(x+20).to_s+'" y2="465" style="stroke:rgb(0,0,64);stroke-width:1"/>\n')}
figure.puts('<line x1="20.0" y1="460.0" x2="20.0" y2="60.0" style="stroke:rgb(0,40,0);stroke-width:1"/>')
((0..300).select {|x| x%10==0}).collect { |x| figure.print('<text x="0" y="'+(460-x).to_s+'" style="font-size:6;fill:rgb(0,40,0);font-weight:normal">'+(x/100.0).to_s+'</text>\n'+'<line x1="18" y1="'+(460-x).to_s+'" x2="22" y2="'+(460-x).to_s+'" style="stroke:rgb(0,40,0);stroke-width:1"/>\n')}

u=1.0
n=0
40.times do
    n+=1
    u=(u+5.0/u)/2.0
    figure.puts('<circle cx="'+(20+10*n).to_s+'" cy="'+(460-100*u).to_s+'" r="2" fill="white" stroke="red" stroke-width="1" />')
end

figure.puts('</svg>')
figure.close

Le fichier produit par ce script s'appelle SuiteRuby01.svg. Le voici:

SuiteRuby01.svg

Formule de l'arc tangente[modifier | modifier le wikicode]

p=(1..100).collect{|n|
    4*(0..n).inject(0){|s,k|
        s+=(-1)**k/(2*k+1.0)
    }
}

puts(p)

Comme on le voit, la suite converge très lentement.

Encore une fois, les termes de la suite sont rationnels, ce qui donne une suite de fractions approchant :

require 'mathn'

p=(1..10).collect{|n|
    4*(0..n).inject(0){|s,k|
        s+=(-1)**k/(2*k+1)
    }
}

puts(p)