Les maths c'est magique - Page 1

En matant les sources de la bibliothèque de FreePascal, j'ai appris que la racine carrée d'un nombre pouvait se calculer par un algorithme dit "de Newton".
J'en ai fait une implémentation en C :

unsigned short (unsigned long nombre)
{
  unsigned short racine= (nombre > 65535) ? 65535 : nombre;
  
  if (racine == 0) return 0;
  
  racine= (nombre/racine + racine) / 2;
  racine= (nombre/racine + racine) / 2;
  racine= (nombre/racine + racine) / 2;
  ... // on répète la ligne un dizaine de fois pour avoir un résultat très précis, en virgule flottante
  
  return  racine;
}

J'ai bien compris que lorsque racine tend vers la racine carrée de nombre, l'expression (nombre/racine + racine) / 2 tend également vers la racine, car (N/r + r)/2 = (r²/r + r)/2 = (r + r)/2 = r.

Mais par quelle magie le résultat après plusieurs répétitions tend-il irrémédiablement vers la racine du nombre, quelle que soit la valeur de racine au départ

D'une manière générale, quelles conditions faut-il respecter dans une telle expression pour qu'elle aboutisse toujours au résultat escompté ?

C'est ça qu'on appelle une "suite convergente" ?

oue c une suite convergente
plus precisement c la suite U(n+1)=1/2*( u(n)+nombre/u(n) ) avec u0=a.

on prouve (trivialement par récurrence ) que un>=sqrt(a) que un est décroissante.
u(n) décroissante minorée par sqrt(a) --> tend vers sqrt(a)

OK j'ai un peu simplifié , mais bon ... voila

Génial !! Merci beaucoup

Il y a juste le sens du verbe "minorer" que j'ai du mal à saisir, mais j'ai compris globalement ce que tu dis.


Sinon, "quelles conditions faut-il respecter dans une telle expression pour qu'elle aboutisse toujours au résultat escompté ?"

u(n) minorée par sqrt(a) <--> Pr tout n u(n)>=sqrt(a) c tout.
Je ne suis pas sur de comprendre ta question mais je vais essayer d'y répondre

Le raisonnement que j'ai fait plus haut est valable parceque la fonction
f(x)=1/2*(x+nombre/x) est une fonction continue (en effet x est tjs non nul car on suppose nombre!=0 donc la fonction est bien définie)

Remarque : il faut que "nombre" soit strictement positif (autrement ca retourne -sqrt(a) )

sinon l'algo marche tout les tps et la convergence est tres rapide

J'ai remarqué que la convergence n'était pas toujours rapide, par exemple si on travaille avec U(n)= (101*u(n-1) + 67*nombre / u(n-1)) / 2*(101+67) la fonction converge moins "facilement"


Je me suis mal exprimé pour la question 2. J'illustre pour que vous compreniez ce que je demande :
Tout comme U(n)= (u(n-1) + nombre/u(n-1)) / 2, la fonction U(n)= nombre/u(n-1) tend vers sqrt(nombre) quand u(n-1) tend vers sqrt(nombre)... et pourtant cette fonction ne converge pas du tout vers la racine de nombre !

Voilà ma question en d'autres termes : quelles "règles" faut-il respecter quand on invente une fonction, pour qu'elle converge ?

ça marche pas comme ça...
déjà c'est pas une fonction qui converge, mais une suite ou une série.

Merci d'avoir répondu précisément à la question

Là:

Thibaut a écrit :
J'ai bien compris que lorsque racine tend vers la racine carrée de nombre, l'expression (nombre/racine + racine) / 2 tend également vers la racine, car (N/r + r)/2 = (r²/r + r)/2 = (r + r)/2 = r.

tu as montré que si la suite converge, alors elle converge vers la racine carrée de nombre. Reste à montrer qu'elle converge.

Et TachMan montre ce fait là:

TachMan a écrit :
oue c une suite convergente
plus precisement c la suite U(n+1)=1/2*( u(n)+nombre/u(n) ) avec u0=a.

on prouve (trivialement par récurrence ) que un>=sqrt(a) que un est décroissante.
u(n) décroissante minorée par sqrt(a) --> tend vers sqrt(a)

OK j'ai un peu simplifié , mais bon ... voila

Vas-y Kevin offre lui un cours sur les DL et les séries entières

Plus généralement à un niveau pas trop élevé, tu peux montrer qu'une suite converge :
si elle est constante.
si c'est une suite facilement définissable pour un n donné, puis qu'elle ressemble à qqch de connu.
Si elle est croissante (décroissante) et majorée (minorée). Si elle est croissante (décroissante) avec une borne supérieure (inférieure), cette borne est sa limite.
Si tu peux montrer que son taux d'accroissement tend vers 0... Quoique, c pas toujours vrai... (exemple la série harmonique). Je crois qu'il faut aussi une autre condition.

Enfin, et c'est le cas qui nous intéresse, une suite définie par un+1=f(un), avec f une fonction quelconque, croissante (décroissante) et majorée (minorée) par un point fixe de f, tend vers ce point fixe. Un point fixe, c'est x0 tel que x0=f(x0).

Bon, y a surement d'autres méthodes...

Ici, f est la fonction qui a x associe (nombre/x+x)/2. Le point fixe de f est la racine carrée de nombre (tu l'as vu toi-même). La valeur en 0 de la suite est le nombre dont on calcule la racine, supérieur à la racine. Tu remarque que pour tout x supérieur à la racine du nombre, f(x) est inférieur à x (trivial), donc f(u(n))=u(n+1) est inférieur à u(n). La suite (u(n))n décroit. C'est fini, elle tend vers la racine du nombre.

Thibaut, et si tu allais te documenter directement sur l'algorithme général de Newton pour la recherche de racine ?

Soit l'équation f(x) = 0 à résoudre (dans ton cas, c'est x^2 - c = 0 car tu veux calculer sqrt(c)), tu obtiens la suite x(n+1) = x(n) - f(x(n)) / f'(x(n)) (dans ton cas : x(n+1) = x(n) - (x(n)^2 - c) / (2x(n)) = (x(n) + c / x(n)) / 2).

> si tu allais te documenter directement sur l'algorithme général de Newton pour la recherche de racine ?

Pas besoin, j'avais compris de moi-même le fonctionnement le soir où je l'ai découvert dans les sources de FP. Pour m'en assurer, j'avais essayé de construire une version pour extraire les racines cubiques. Ca marchait

Moumou : merci ! je lirai ton post quand j'aurai le temps