Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Suite convergente vers log

Posté par
lonico
25-06-15 à 21:44

Bonjour,
Existe il une suite (défini par recurence) qui converge vers une valeur d'un logarithmique quelconque ?
Merci d'avance

Posté par
Taik
re : Suite convergente vers log 25-06-15 à 23:13

Bonjour,

En fait je comprends pas ta question. C'est simple de définir une telle suite qui converge vers log(2) par exemple.
La suite u_n = log(2) + \frac{1}{n} converge bien vers log(2).

Désolé pour la trivialité de ma réponse, je sais pas trop quoi dire

Posté par
lake
re : Suite convergente vers log 25-06-15 à 23:15

Bonjour,

Soit x>0

La suite (w_n) est définie par:

\begin{cases}w_0=x\\w_{n+1}=\sqrt{w_n}\end{cases}

Puis la suite (t_n):

t_n=2^n(w_n-1)

(t_n) converge vers \ln\,x

Posté par
lonico
re : Suite convergente vers log 29-06-15 à 18:47

Effectivement, excusez moi de ma question imprécise, mais la réponse que lake me donne est l'information que j'attendais.
Si maintenant vous avez d'autre suites tendant vers un logarithme,du moins sans l'utilisé directement, je suis preneur.
En tout cas merci beaucoup pour cette réponse

Posté par
lake
re : Suite convergente vers log 30-06-15 à 15:04

De rien pour moi lonico

Posté par
luzak
re : Suite convergente vers log 30-06-15 à 15:45

Bonjour !
Je sors un peu du cadre fixé : je ne donne pas une suite mais je te propose un algorithme (facile d'en déduire une suite) permettant de calculer la valeur approchée à \varepsilon près de \log_a(x).

Conditions imposées : (A) a>1 (base des logarithmes à calculer), 1\leqslant x\leqslant a,\;\varepsilon>0.
variables auxiliaires : s,u initialisées par s\gets1,\;u\gets 0.
boucle : TANTQUE s>\varepsilon
                 s\gets s/2;\;x\gets x^2
                  SI x>a ALORS x\gets x/a;\;u\gets u+1 FINSI
         FIN TANTQUE
valeur retournée : z=s*u+s/2.
Il est facile de voir que l'algorithme (mis sur une machine non virtuelle) est fini et il suffit de faire une boucle infinie sur une machine virtuelle (je veux dire connaissant TOUS les réels) pour avoir une suite définie sur \N.
La condition  1\leqslant x\leqslant a reste vraie dans la boucle et l'expression s*(\log_a(x)+u) invariante le long de la boucle.
En notant y cette valeur constante, comme s=1,\;u=0 au départ, on a y=\log_a(x).
Alors \log_a(x)-z=s*(\log_a(x)+u)-s*u-s/2=\dfrac s{2}\Bigl(2\log_a(x)-1\Bigr) et on en déduit facilement que |\log_a(x)-z|\leqslant s/2\leqslant\varepsilon.

A noter qu'après n itérations on a s=2^{-n} ce qui confirme la convergence (si tu mets en place la suite associée à l'algorithme).


Pour calculer des logarithmes quand les conditions (A) ne sont pas vérifiées : (x>0,\;a\neq1,\;a>0 bien entendu) :
Si a>1, chercher p\in\Z tel que 1\leqslant x*a^p\leqslant a et prendre \log_a(x)=\log_a(x*a^p)-p.
Enfin, si 0<a<1 il suffit d'utiliser \log_a(x)=-\log_{1/a}(x)

Posté par
luzak
re : Suite convergente vers log 30-06-15 à 15:50

J'ai oublié (honte sur moi) une instruction. Lire, juste avant le SI : s\gets s/2;\;x\gets x^2;\;u\gets 2*u

Posté par
lonico
re : Suite convergente vers log 02-07-15 à 21:36

Et bien vous avez très bien fait de sortir du cadre car cela m'intéresse beaucoup

Cependant j'ai du mal à comprendre la logique de cette algorithme,


Si j'ai bien compris (sn) et (un) valide les formules :
sn*(y+un)= sn+1*(y+ un+1)  
et
|y-z| = s/2 *(2y-1) |y-z|

or ces deux formules sont toujours vrai tant que y< 1

Comment l'algorithme fait-il pour trouver s et u tel que y = loga(x) ?
Utilise t-il l'une des identités logarithmique ?
Quel est l'objectif du SI et notamment du u u+1 ?

Posté par
luzak
re : Suite convergente vers log 03-07-15 à 13:27

Bonjour !
Je comprends ton embarras. Il faut corriger : dans \log_a(x)-z=s*(\log_a(x)+u)-s*u-s/2=\dfrac s{2}\Bigl(2\log_a(x)-1\Bigr) il faut lire \log_a(x_0)-z=.... J'ai un peu (!) abusé de l'utilisation du x initial en variable de programme, x_0 désigne alors la valeur initiale de cette variable.
On a donc \log_a(x_0)-z=s*(\log_a(x)+u)-s*u-s/2=\dfrac s{2}\Bigl(2\log_a(x)-1\Bigr) et puisque 1\leqslant x\leqslant a on a toujours 0\leqslant\log_a(x)\leqslant1 puis |2\log_a(x)-1|<1.

Les valeurs s,u sont celles de ces variables quand la boucle s'arrête.

Le "SI" corrige les valeurs de x,u pour avoir toujours 1\leqslant x\leqslant a,\;s*(\log_a(x)+u)=1*(\log_a(x_0)+0).

Si tu préfères le point de vue "suite de limite \log_a(x)" voici une présentation différente :
a,x sont des réels tels que a>1,\;1\leqslant x\leqslant a.
On définit les suites réelles n\mapsto x_n,\;n\mapsto u_n par les relations :
      \bullet x_0=x,\;u_0=0
      \bullet en supposant connus x_n,u_n :
                  si x_n^2\leqslant a on prend x_{n+1}=x_n^2,\;u_{n+1}=2u_n et           si x_n^2>a on prend x_{n+1}=\dfrac{x_n^2}a,\;u_{n+1}=2u_n+1
Alors, par récurrence sur n, on a 1\leqslant x_n\leqslant a :
     C'est vrai pour n=0 et si 1\leqslant x_n\leqslant a on a aussi 1\leqslant x_n^2\leqslant a^2 donc
     (x_n^2\leqslant a\implies 1\leqslant x_n^2=x_{n+1}\leqslant a) et (x_n^2>a\implies 1< \dfrac{x_n^2}a=x_{n+1}\leqslant\dfrac{a^2}a= a)

La suite n\mapsto y_n telle que y_n=\log_a(x_n)+u_n est une suite géométrique de raison 2. Même raisonnement :
(x_n^2\leqslant a\implies y_{n+1}=\log_a(x_n^2)+2u_n=2y_n) et (x_n^2>a\implies y_{n+1}=\log_a\dfrac{x_n^2}a+2u_n+1=2y_n ).

Il en résulte y_n=2^ny_0=2^n(\log_a(x_0)+u_0)=2^n\log_a(x) puis, \log_a(x)-2^{-n}u_n=2^{-n}(y_n-u_n)=2^{-n}\log_a(x_n) et enfin, puisque 0\leqslant x_n\leqslant a, 0\leqslant \log_a(x)-2^{-n}u_n\leqslant2^{-n}.
La suite n\mapsto2^{-n}u_n converge vers \log_a(x) et la valeur en n est valeur par défaut, à moins de 2^{-n} près, de la limite.

Posté par
luzak
re : Suite convergente vers log 03-07-15 à 13:55

Encore une bêtise : au bout de la dernière grande ligne c'est 1\leqslant x_n\leqslant a...

Quelques remarques :
A propos du "SI" de l'algorithme : en fait, comme tu peux le voir sur l'explication théorique, on prend le premier cas par défaut et on corrige si nécessaire. Cette façon de faire évite de calculer plusieurs fois le termex^2 : si tu veux imiter de manière stricte le passage d'un x au suivant (calcul de x_{n+1} à partir de x_n) tu devrais calculer 4 fois le carré de x.

Ne pas confondre les y_n de la partie théorique avec l'invariant y utilisé dans le premier message.

La variable s n'est utilisée dans la partie "programme" que pour assurer une fin de boucle et la correction s/2 pour la valeur retournée sert à "centrer" la valeur approchée calculée : le côté "valeur par défaut" est sans grand intérêt informatique.

Posté par
lonico
re : Suite convergente vers log 10-07-15 à 23:00

Bien merci je pense avoir compris. (J'avoue je suis plus à l'aise avec les suites)

Cette méthode repose donc (en gros) sur la ligne yn+1 = log(xn2) + 2un = 2yn et donc la propriété du logarithme log(xr) = r*log(x) et de la factorisation de l'addition.

Merci encore pour cette algorithme (et pour le temps que vous avez du passez pour l'écrire) x).
cordialement
Lonico  

Posté par
luzak
re : Suite convergente vers log 11-07-15 à 14:06

Bonjour !
A ta disposition si nécessaire, bonne fin de semaine !

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !