Discussion :

[j.p.mignot]

supprimé.

[Le Furet]

A première vue, cette suite est assez proche de celle obtenue par méthode de Newton :

u_{n+1}=1/2*(u_n+a/u_n)

qui converge vers sqrt(a) quadratiquement (on double le nombre de décimales justes à chaque itération).

u_n est une valeur par défaut, on obtient une valeur par excès en regardant a/u_n, cela doit répondre, en adaptant, à ta première question.

Pour la deuxième, j'avoue que je ne sais pas. Un ami procédait par un algorithme plus lent maisdonnant vite de bonnes approximations pour déterminer u_0 (en l'occurence, la "méthode de la potence", voir : http://membres.lycos.fr/ericmer/Racines/racines.htm ), je ne sais pas s'il y a plus iintelligent.

[j.p.mignot]

1- J'ai enlevé mon mail qui comportait une ENORME erreur désolé!
2- La série que j'utilise est effectivement la série de Newton et la réponse reste par contre tout à fait valable: Merci.
3- Le méthode de la potence qui a fait mon emerveillement quand j'étais encore gamin car elle me semblait magique à cette époque donne bien une approximation de U0 mais le temps nécessaire pour extraire 1 valeur raisonnable de U0 me semble + élevé que celui nécessaire pour converger avec la méthode de la tangente en partant d'1 point comme a/2. On peut donc se poser la question de l'interet d'implementer cette autre technique ici. A voir!
4- J'aurais souhaité trouver un majorant du reste afin de fixer n de façon sure pour garentir une erreur donnée sur sqrt(x). La série converge quadratiquement de façon très rapide OK, mais cela ne fixe pas pour autant n. Quand on doit implémenter ce genre de calcul sur des processeurs embarqués (très) lents pour des questions de consomation, ce genre de question reprend tout son interet.
J'ai essayé - mais encore sans succès c.a.d. sans démonstration formelle - d'utiliser l'évolution de la dérivée des résultats. J'avais dans l'idée d'essayer d'utiliser l'évolution de la courbure de la parabole - idée probablement farfelue- .

[Le Furet]

Tu voudrais pouvoir évaluer n a priori ? Pourquoi ne pas sortir de ta boucle dès que |u_n - a/u_n| < epsilon ?

Pour l'histoire de la potence, je suis moi aussi dubitatif, mais il est possible que ça soit pas si bête : le pb des convergences quadratiques, c'est leur initialisation, ça peut converger très lentement au début (typiquement, dans ton cas, j'ai le sentiment que a/2 n'est pas une très bonne approximation pour a grand - je peux me planter, j'y ai pas trop réfléchi). Du coup, un algorithme linéaire mais sûr pour démarrer, pourquoi pas (j'avoue ne pas avoir essayé).

J'ai regardé dans les Numerical Recipe l'algorithme pour une racine carrée dans les fonctions de calculs en grande précision, ils utilisent une suite de type Newton mais plus facile à calculer, qu'ils initalisent... avec le résultat de fsqrt(a) ! Donc aucun intérêt...

[j.p.mignot]

si je 'stoppe' avec le critère |Un - a/Un| = Un - a/Un < Eps ( || innutile dès n=2 ) alors
Un^2 - Eps Un - a < 0

soit Un dans [ 0.5*(Eps +- sqrt(Eps^2+4a)) ]
Un > sqrt(a) ( des n > 2 ) donc

Un dans [ sqrt(a), 0.5*(Eps + sqrt(Eps^2 + 4a)) ]


Un < 0.5*(Eps + sqrt(Eps^2 + 4a)) =
sqrt(a) * ( Eps/4a + sqrt(1 + Eps'2/(4a)) )

Un-sqrt(a) < sqrt(a)*( Eps/4a + sqrt(1+Eps^2/4a) - 1 ]
~ sqrt(a)*( Eps/4a + Eps^2/8a ] ~ sqrt(a)* Eps/4a

si on souhaite Un - sqrt(a) < Eps0, Eps0 etant donné, alors Eps0 = Eps/4/sqrt(a) soit Eps = 4. sqrt(a). Eps0 - Ici je suis déjà inquiet car la relation x < a ~B n'implique pas x < B !!

Il faut donc connaitre sqrt(a) pour fixer Eps depuis Eps0.


A moins qu'1 majoration + fine m'ai échappée!

On peu "peut-être" ??? admettre que l'on fixe Eps suivant le critère proposé, calculer B = sqrt(a) avec ce critère de convergeance le reportrer alors B dans Eps0 = Eps / 4 /B pour estimer l'erreur.

On doit + ou - arriver à un majorant honete mais je ne suis pas convaincu - du tout - de la solidité de l'approche.

Bien entendu on peut calculer n ainsi ajouter 1 ou 2 à titre de "sécurité" rt esperer que le risque de planté d'1 algo du à un vice du test soit assez faible pour qu'il surbiennent quant on est "hors garanties".

Cela est tout de même peu satisfaisant.

[Le Furet]

Je ne comprends pas ce que tu cherches. Je suppose que epsilon est la précision à laquelle tu veux calculer sqrt(a), autrement dit tu veux que |u_n-a|<epsilon.

Mais dans ce cas, si tu appelles v_n la suite v_n = a/u_n, alors on a toujours : v_n < sqrt(a) < u_n (ou le contraire, à creuser), donc |u_n - sqrt(a)| < u_n - v_n.

Donc si tu t'arrêtes dès que u_n - v_n < epsilon, tu as nécessairement |u_n - sqrt(a)| < epsilon.

J'ai oublié de préciser que v_n aussi converge vers sqrt(a), quadratiquement, donc cette condition est très vite réalisée.

Ou alors, je n'ai pas compris ce que tu cherches à faire (c'est quand même dur à lire, faut dire aux admins qu'ils installent un mode LaTeX sur le forum ).

[j.p.mignot]

OK!
à prioris sans faille. Un decroit vers sqrt(a), Vn croit vers sqrt(a).

MERCI !!!

En ce qui concerne U0 y a-t-ill quelquechose à gagner si on fait


n=0; while a < 1 { n--; a=100*a;} while a>100 [ n++; a=a/100;}
maintenant a= 1..100 => srqrt(a) = 1..10 => partir de 3 puis mutiplier le résulltat par 10 ^n