Quelle condition d'arrêt pour algorithme permettant d'approcher la limite d'une suite convergente ?

Lol_a · September 2022

Bonjour,
Comment trouver à l'aide d'un algorithme une valeur aussi proche que l'on veut (précision passée en paramètre) de la limite d'une suite qu'on sait convergente ?
Par exemple, je sais (enfin plutôt, j'ai admis) que la suite de terme général $S_n = \sum^n_{k=1} 1/n^2$ (pour $n \geq 1$) est convergente et a pour limite $\frac{\pi^2}{6}$. Je pourrais donc utiliser cette suite pour calculer une valeur approchée au millième de $\frac{\pi^2}{6}$ par exemple. Or, comment faire pour savoir combien de terme il me faudra calculer ?

Avec un algorithme comme ce qui suit, on triche puisqu'on utilise la valeur "exacte" de la limite alors qu'on ne sait pas toujours la calculer :

Image: https://les-mathematiques.net/vanilla/uploads/editor/w8/il3mqovl5pc7.png

J'ai essayé cette autre méthode ci-dessous mais l'algorithme s'arrête sur $S_{32} \approx 1.6141672628279242$ alors que $\frac{\pi^2}{6} \approx 1.6449340668482264$.

Même en demandant à ce que la distance entre $S_n$ et $S_{n-1}$ soit plus petite, on est loin du compte. Par exemple, si je demande à l'algorithme de s'arrêter quand celle-ci est inférieur à $10**{-6}$, il s'arrête à $S_{1000} \approx 1.6439345666815615$. On a bien une valeur approchée au millième mais je ne trouve pas ça satisfaisant. D'une part, on pourrait certainement obtenir une valeur approchée au millième avant le rang 1000, deuxièmement, et d'autre part j'ai trouvé le "-6" par tâtonnement. Or finalement, je trouve qu'au millième on est encore assez loin de la valeur exacte. Comment / peut-on

trouver une condition d'arrêt qui permette de calculer une valeur de la limite aussi proche qu'on le souhaite ?

Bibix · September 2022

C'est toute une théorie (estimation d'erreurs) qui répond à cette question dans le cas général ! Mais par exemple, dans ton cas, on calcule généralement le reste qui vaut dans ton exemple environ $1/n$ et $S_{n} - S_{n-1} \approx 1/n^2$. Donc on retrouve ce que tu as trouvé en tatônnant.

Alban_ · September 2022

Le souci dans ta condition "$u_{n+1}-u_n$ est petit", c'est que dans ce cas, ton algo va dire que la suite $(ln(n))$ converge...

À mon avis, il y a deux façons de faire cela :

- on fait des majorations d'erreur en prouvant par exemple que $|u_n-\ell|\leq 1/n$ et on dit qu'il suffit que $1/n$ soit inférieur à epsilon. La défaut, c'est que c'est compliqué, que la majoration de l'erreur dépend de chaque suite, etc

- on utilise la condition $u_{n+1}-u_n$ est petit en sachant que c'est un peu bancal

Fin de partie · September 2022

Pour tout $n\geq 1$, $\ \displaystyle Q_n:=\dfrac{\pi^2}{6}-\sum_{k=1}^n \frac{1}{k^2}$. On a $Q_n>0$.

\begin{align}Q_{n+1}-Q_n=\sum_{k=1}^{n} \frac{1}{k^2}-\sum_{k=1}^{n+1} \frac{1}{k^2}=-\frac{1}{(n+1)^2}\end{align}

La suite $(Q_n)$ est décroissante (et elle tend vers $0$)

Fin de partie · September 2022

Pour voir que $\displaystyle \sum_{k=1}^\infty \frac{1}{k^2}$ est convergente, on utilise que $n\geq 2,\dfrac{1}{n^2}\leq \dfrac{1}{n(n-1)}$.

On sait calculer $\displaystyle \sum_{k=2}^\infty \frac{1}{k(k-1)}$

Il me semble que ton algorithme précédent permet de déterminer le nombre de termes qu'il faut calculer pour que $Q_n$ soit inférieur à une valeur donnée.

Cette série converge lentement. Il faut accélérer la convergence de cette série. C'est ce qu'a fait Euler pour avoir une valeur assez précise qu'il lui a permis de deviner la valeur de cette constante.

Lol_a · September 2022

Merci pour les réponses. Effectivement @Alban, si la suite ne convergeais pas je n'aurais pas utilisé un tel algorithme, je garde le contre-exemple sous le coude, ça pourra me servir.

Je me rends compte que je ne maîtrise pas totalement les séries de Riemann (i.e. je connais mais je ne saurais pas bien redémontrer le critère de convergence en 2 minutes), je vais aller réviser ça.

Si j'ai bien compris il n'y a pas d'algorithme qui marcherait pour n'importe quelle suite convergente. En revanche, il y a une méthode générale qui consisterait à majorer le reste le plus finement possible puis à adapter la condition d'arrêt à la majoration trouvée. C'est bien ça ?

@Fin de partie Oui, il faut que je me penche sur la question de l'accélération de la convergence. C'est d'ailleurs pour essayer de mieux appréhender ce qu'est la vitesse de convergence que j'en suis venu à m'intéresser à un tel algorithme.

Heuristique · September 2022

Bonjour,

Pour les séries de Riemann leur nature convergente ou divergente vient du théorème de comparaison série/intégrale.

C'est dans ce genre d'algorithme d'estimation de limite que tu vois une différence entre l'existence mathématique et l'existence explicite (la seconde est plus forte que la première). Tu as une preuve que pour tout $\varepsilon$, il existe $n_0$ tel que $\forall n \geqslant n_0,\ \vert S_n - \ell \vert \leqslant \varepsilon$ mais tu n'as pas de formule explicite pour exprimer ce $n_0$ en fonction de $\varepsilon$.

Il faut donc que tu puisses trouver explicitement $n_0$ afin d'avoir la condition d'arrêt sur ton algorithme. Pour majorer le reste de la série, tu peux utiliser le reste intégrale qui, lui, est facilement calculable !

Fin de partie · September 2022

$ \displaystyle n\geq 1,Q_n:=\dfrac{\pi^2}{6}-\sum_{k=1}^n \frac{1}{k^2}=\sum_{k=n+1}^{\infty}\frac{1}{k^2}\leq \sum_{k=n+1}^{\infty}\frac{1}{k(k-1)}=\frac{1}{n}$ Cela permet, sauf erreur, d'avoir une borne pour le nombre de termes à calculer pour avoir une précision donnée.

PS.
Mais la précision souhaitée peut être atteinte probablement en calculant moins de termes que cette borne.

PS2.
Il me semble qu'on peut montrer que $\displaystyle Q_n\geq \frac{1}{n+1}$

Fin de partie · September 2022

$\zeta(2)$ est relié à l'intégrale $\displaystyle \int_0^1 \frac{\ln x}{1-x}dx$ et on peut calculer l'intégrale $\displaystyle \int_0^{\frac{1}{2}} \frac{\ln x}{1-x}dx$ en fonction de la précédente, et cette dernière intégrale est égale à une série qui converge beaucoup plus vite que la série qui définit $\zeta(2)$.

PS.
On en a plusieurs fois parlé sur le forum mais je n'ai pas été capable de retrouver un message.

Médiat_Suprème · September 2022

Lol_a a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/2331580/quelle-condition-darret-pour-algorithme-permettant-dapprocher-la-limite-dune-suite-convergente

Comment trouver à l'aide d'un algorithme une valeur aussi proche que l'on veut (précision passée en paramètre) de la limite d'une suite qu'on sait convergente ?

Je reprends à partir de la question initiale : trouver un algorithme (basé sur le calcul) capable de trouver la limite (avec un test d'arrêt pas trop idiot) de n'importe quelle suite convergente, sans indication supplémentaire, me paraît impossible, on peut toujours imaginer une suite dont les mille milliards de premiers termes tendent vers 1 puis qui se met à tendre vers 2.

Bibix · September 2022

Sinon, un cas intéressant pour $\zeta(2)$ serait la formule :

$$\sum_{k = 1}^{+\infty} \frac{1}{k^2} = \sum_{k = 1}^n \frac{1}{k^2} + \sum_{k = 1}^{+\infty} \frac{1}{k^2 \binom{k + n}{k}}$$

C'est typiquement le genre de formule qui a l'air belle et fonctionnelle (on a l'impression qu'augmenter $n$ va permettre de converger super vite), mais qui ne marche pas en pratique (si on l'implémente naïvement sans faire attention) à cause des approximations numériques... . C'est bien pour cela que c'est toute une théorie !

Fin de partie · September 2022

\begin{align}\int_0^{\frac{1}{2}}\frac{\ln x}{1-x}dx&\overset{u=1-x}=\int_{\frac{1}{2}}^1\frac{\ln(1-u)}{u}du\\
&=\int_0^1\frac{\ln(1-u)}{u}du-\int_0^{\frac{1}{2}}\frac{\ln(1-u)}{u}du\\
&\overset{\text{IPP}}=\underbrace{\Big[\ln u\ln(1-u)\Big]_0^1}_{=0}+\int_0^1 \frac{\ln u}{1-u}du-\underbrace{\Big[\ln u\ln(1-u)\Big]_0^{\frac{1}{2}}}_{=\ln^2 2}-\int_0^{\frac{1}{2}}\frac{\ln u}{1-u}du
\end{align}
Donc
\begin{align}-\int_0^1\frac{\ln x}{1-x}dx=-2\int_0^{\frac{1}{2}}\frac{\ln x}{1-x}dx-\ln^2 2.\end{align}
Or, on démontre que
\begin{align}-\int_0^1\frac{\ln x}{1-x}dx&=\zeta(2)\\
\int_0^{\frac{1}{2}}\frac{\ln x}{1-x}dx&=-\ln^2 2-\sum_{n=1}^\infty\frac{1}{n^22^n}\\
\end{align}
donc,
\begin{align}\boxed{\zeta(2)=\ln^2 2+2\sum_{n=1}^\infty\frac{1}{n^22^n}.}\end{align}
Cette dernière série converge rapidement.

Lol_a · September 2022

@Médiat_Suprème Effectivement, vu comme ça.. La méthode à laquelle j'ai pensé n'a vraiment aucun sens si on n'a fait l'effort de réfléchir un peu aux mathématiques qu'il y a derrière avant.
@Bibix Je me méfie du $\binom {k +n} n$, j'ai l'impression que c'est plus couteux à calculer que ça n'en à l'air et surtout j'avais bien constaté sur calculatrice qu'en calculant naïvement $(k+n)!$ (pour ensuite diviser) on dépassait rapidement la capacité de la calculatrice.

@Fin de partie Intéressant. Je vais regarder ça à tête reposée. En fait, je ne connait pas du tout la fonction $\zeta$.

Fin de partie · September 2022

@Lol_a: la fonction $\zeta$ est définie pour tout réel $s>1$ par $\displaystyle \zeta(s):=\sum_{n=1}^\infty \frac{1}{n^s}$

On peut prolonger* cette fonction à tout $\mathbb{R}$ privé du réel $1$. **

*: on étend son domaine de définition mais en conservant ses bonnes propriétés de dérivabilité (ce qui restreint le choix de fonctions candidates à être le prolongement de la série ci-dessus, il n'y a qu'un seul tel prolongement).

** Hors de l'intervalle $]1,\infty[$ on n'a plus l'égalité ci-dessus. Ce qui rend acrobatique le calcul de $\zeta(s)$ pour $s$ n'appartenant pas à $[1,\infty[$ (pour $s=1$ elle n'est pas définie)

PS.
Riemann a étendu cette fonction à tout $\mathbb{C}$ privé toujours du réel $1$.

Cette fonction s'annule pour les réels qui sont des nombres entiers pairs strictement négatifs.

L'hypothèse de Riemann est que les zéros qui sont dans la "bande critique" ont tous leur partie réelle qui vaut $1/2$

(la "bande critique" est l'ensemble des nombres complexes dont la partie réelle est comprise entre $0$ et $1$.

Hélas sur cette bande, la fonction $\zeta$ ne peut pas s'exprimer par la série ci-dessus. Cette série converge seulement pour les nombres complexes $s$ de partie réelle strictement plus grande que $1$ (et sur cet ensemble elle coïncide avec $\zeta(s)$)

Fin de partie · September 2022

$m>n$ des entiers naturels.

\begin{align}\frac{1}{(n+1)\binom{m+1}{n+1}}=\int_0^1 x^n(1-y)^{m-n}dx\end{align}

alors,
\begin{align}\frac{1}{k\binom{k+n}{k}}=\int_0^1 x^{k-1}(1-x)^n dx\end{align}
\begin{align}\sum_{k=1}^\infty\frac{1}{k^2\binom{k+n}{k}}&=\sum_{k=1}^\infty\frac{1}{k}\int_0^1 x^{k-1}(1-x)^n dx\\
&=\int_0^1 \frac{(1-x)^n}{x}\left(\underbrace{\sum_{k=1}^\infty \frac{x^{k}}{k}}_{=-\ln(1-x)}\right)dx\\
&=-\int_0^1 \frac{(1-x)^n\ln(1-x)}{x}dx\\
&\overset{u=1-x}=-\int_0^1 \frac{x^n\ln u}{1-u}du\\
\end{align}
Et, on montre aisément que
\begin{align}-\int_0^1 \frac{x^n\ln u}{1-u}du=\sum_{k=n+1}^\infty \frac{1}{k^2}\end{align}

Saturne · September 2022

Pour le cas général, en informatique on utilise souvent un critère du genre $|u_{n+1} - u_n| < \epsilon u_n$. Cela donne une précision relative à l'ordre de grandeur de $u_n$.

Saturne · September 2022

Voilà la fonction que j'utilise en Julia.

function areclose(z1::S, z2::S) where {T <: Real, S <: Union{T, Complex{T}}}
	z1 == z2 && (return true)
	eps2 = eps(T)^2
	mod2_z2 = abs2(z2)
	maxmod2 = (mod2_z2 < eps2) ? 1.0 : max(abs2(z1), mod2_z2)
	return abs2(z1 - z2) < 4.0 * eps2 * maxmod2
	end

**eps(T)** est la "précision machine" du type T. Pour le type "double", c'est en général un truc de l'ordre de $10^{-16}$. Tout langage fournit une précision machine.

Math Coss · September 2022

La balise "code" est sous l'onglet « paragraphe ».

Image: https://les-mathematiques.net/vanilla/uploads/editor/rd/ca8rx3jk7m4g.png

Fin de partie · September 2022

On peut considérer que la formule suivante est une façon d'accélérer la convergence de la série qui définit $\zeta(2)$:
\begin{align}\sum_{n=1}^\infty \frac{1}{n^2\binom{2n}{n}}=\frac{1}{3}\zeta(2)=\frac{\pi^2}{18}\end{align}
Preuve. Pour $n\geq 1$, \begin{align} \frac{1}{n\binom{2n}{n}}=\int_0^1 x^{n-1}(1-x)^{n}dx \end{align}
Donc,
\begin{align}\sum_{n=1}^\infty \frac{1}{n^2\binom{2n}{n}}&=\sum_{n=1}^\infty \frac{1}{n}\int_0^1 x^{n-1}(1-x)^{n}dx\\ &=\int_0^1 \frac{1}{x}\left(\sum_{n=1}^\infty \frac{x^n(1-x)^n}{n}\right)dx\\ &=-\int_0^1 \frac{\ln\Big(1-x(1-x)\Big)}{x}dx\\ &=-\int_0^1 \frac{\ln\left(\frac{1+x^3}{1+x}\right)}{x}dx\\ &=\int_0^1 \frac{\ln\left(1+x\right)}{x}dx-\underbrace{\int_0^1 \frac{\ln\left(1+x^3\right)}{x}dx}_{u=x^3}\\ &=\frac{2}{3}\int_0^1 \frac{\ln\left(1+x\right)}{x}dx\\ &=\frac{2}{3}\underbrace{\int_0^1 \frac{\ln\left(1-x^2\right)}{x}dx}_{u=x^2}-\frac{2}{3}\int_0^1 \frac{\ln\left(1-x\right)}{x}dx\\ &=-\frac{1}{3}\int_0^1 \frac{\ln\left(1-x\right)}{x}dx\\ &=-\frac{1}{3}\times -\zeta(2)\\ &=-\frac{1}{3}\times -\frac{\pi^2}{6}\\ &=\boxed{\frac{\pi^2}{18}} \end{align}
PS. La sommation de dix termes de cette série (multipliée par trois) donne déjà sept décimales exactes pour le calcul de $\zeta(2)$ tandis que la série originale ne donne même pas une décimale exacte.

S1(n)={sum(k=1,n,1.0/k^2)}
S2(n)={3*sum(k=1,n,1.0/(k^2*binomial(2*k,k)))}
print(S1(10)," ",S2(10)," ",Pi^2/6)
1.549767731166540690350214160 1.644934021798102956882258076 1.644934066848226436472415167

Bibix · September 2022

Je reviens sur ce fil juste pour ajouter que ce genre de formules ne sert pas qu'à converger vite. En particulier, il existe la formule similaire suivante pour $\zeta(3)$ qui a été redémontrée et utilisée par Apéry dans sa preuve de l'irrationnalité de $\zeta(3)$ :

$$\zeta(3) = \frac{5}{2} \sum_{k = 1}^{\infty} \frac{(-1)^{k-1}}{k^3 \binom{2 k}{k}}$$

Fin de partie · September 2022

@Bibix: C'est parce que cette formule converge vite que $\zeta(3)$ est irrationnel me semble-t-il.

La démonstration de la formule que tu mentionnes se fait de la même manière que celle donnée plus haut.

ManuTLS · September 2022

Juste une petite video sur la formule de Machin et le calcul des décimales de pi et les problèmes de rapidité de convergence associés:

Fin de partie · September 2022

ManuTLS.
Plus personne n'utilise ce genre de formules pour battre des records d'obtention de décimales de $\pi$*.
Il existe des séries (plus compliquées) qui convergent très vite vers $\pi$.
On a aussi la formule de Brent-Salamin.

*: Ce type de formules avait été utilisé en 1974 pour calculer 500 000 décimales de $\pi$. Mais depuis on a fait beaucoup mieux et ce n'est pas uniquement grâce à la puissance croissante des calculateurs.

Fin de partie · September 2022

Avec la technique utilisée plus haut, on montre que:
\begin{align}\sum_{k = 1}^{\infty} \frac{(-1)^{k-1}}{k^3 \binom{2 k}{k}}=-\int_0^1 \frac{\text{Li}_2\Big(-\frac{x}{(1+x)^2}\Big)}{x}dx\end{align} Le reste du calcul est sportif.
PS.
On peut calculer ce genre de séries par creative telescoping.

Quelle condition d'arrêt pour algorithme permettant d'approcher la limite d'une suite convergente ?

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 11