[PDF] Algorithme de Horner compensé en précision finie et applications

View - Download Algorithme de Horner compensé en précision finie et applications

Previous PDF

Next PDF

Algorithme de Horner compensé en précision finie et applicationsStef Graillat LIP6/PEQUAN - Université Pierre et Marie Curie (Paris 6)

Séminaire SPIRAl/SALSA

1 juin 2007, Paris

S. Graillat (Univ. Paris 6)Algorithme de Horner compensé1 / 40

Plan de l"exposé

1Motivations

2Évaluation précise de polynômes

3Applications

S. Graillat (Univ. Paris 6)Algorithme de Horner compensé2 / 40

Plan de l"exposé

1Motivations

2Évaluation précise de polynômes

3Applications

S. Graillat (Univ. Paris 6)Algorithme de Horner compensé3 / 40

Motivations générales

Proposer des algorithmes et des logiciels :

plus précisque ceux utilisant les précisions de la norme IEEE 754 ?on veut que la précision vérifie une "version améliorée» de l"estimation empirique classiqueefficace en terme de performancesans sacrifier la portabilité ?on utilise seulement la précision IEEE 754 simple ou double avec uneborne d"erreurpour contrôler la précision du résultat ?borne d"erreur dynamique et certifiée calculable en précision finie Un exemple : le schéma de Horner pour l"évaluation polynomiale →leschéma de Horner compensé1

1SG, N. Louvet, Ph. Langlois. Compensated Horner Scheme. Research Report, 2005

S. Graillat (Univ. Paris 6)Algorithme de Horner compensé4 / 40

Imprécision dans l"évaluation polynomiale

Évaluation du polynômep(x) = (x-2)3=x3-6x2+12x-8 pour

environ 200 points au voisinage dex=2 ensimpleetdoubleprécision1.991.9921.9941.9961.99822.0022.0042.0062.0082.01-2

-1.5 -1 -0.5 0 0.5 1 1.5

2x 106

évaluation en simple précision

évaluation en double précisionS. Graillat (Univ. Paris 6)Algorithme de Horner compensé5 / 40

Problématique en précision finie (1/2)

But :Résoudre des problèmes numériques en étantprécisetfiable Comprendrel"influence de la précision finie sur la qualité numérique du logiciel scientifique pourcontrôler et limiter ses effets néfastes résultat imprécis; instabilité numérique.

Améliorerla précision des résultats

Comment être plus précis à faible coût S. Graillat (Univ. Paris 6)Algorithme de Horner compensé6 / 40

Problématique en précision finie (2/2)

Comprendre l"influence de la précision finie sur la qualité numérique du

logiciel scientifique pour contrôler et limiter ses effets néfastes :Contrôler les effets de la précision finie :

Comment mesurer ladifficulté de résolutiond"un problème? Comment apprécier lafiabilité de l"algorithmede résolution? Comment estimer laprécision de la solutioncalculée?

Limiter les effets de la précision finie

Commentaméliorer la précision de la solution? S. Graillat (Univ. Paris 6)Algorithme de Horner compensé7 / 40

Analyse d"erreur

x=?G(y)x=G(y)Espace de donnéesDyGEspace des résultatsR?

GErreur directe

Analyse directe

Analyse inverse

consiste à identifier ?xà la solution d"un problème perturbé : x=G(y+ Δy).S. Graillat (Univ. Paris 6)Algorithme de Horner compensé8 / 40

Analyse d"erreur

x=?G(y)x=G(y)Espace de donnéesDy+ Δyy

Erreur inverse

GGEspace des résultatsR?

GErreur directe

Analyse directe

Analyse inverse

consiste à identifier ?xà la solution d"un problème perturbé : x=G(y+ Δy).S. Graillat (Univ. Paris 6)Algorithme de Horner compensé8 / 40

Intérêt de l"analyse inverse

Comment estimer la précision de la solution calculée?

Au premier ordre, on a l"estimation empirique :erreur directe?conditionnement×erreur inverse.Comment mesurer la difficulté de résolution d"un problème?

Le conditionnement caractérise la sensibilité de la solution d"un problème à des perturbations sur les données.Conditionnement:K(P,y) :=limε→0sup

Δy?P(ε)?

?Δx?R?Δy?D?Comment apprécier la fiabilité de l"algorithme de résolution? L"erreur inverse mesure la distance entre le problème que l"on a

effectivement résolu et le problème initial.Erreur inverse:η(?x) =minΔy?D{?Δy?D:?x=G(y+ Δy)}S. Graillat (Univ. Paris 6)Algorithme de Horner compensé9 / 40

Intérêt de l"analyse inverse

Comment estimer la précision de la solution calculée?

Au premier ordre, on a l"estimation empirique :erreur directe?conditionnement×erreur inverse.Comment mesurer la difficulté de résolution d"un problème?

Le conditionnement caractérise la sensibilité de la solution d"un problème à des perturbations sur les données.Conditionnement:K(P,y) :=limε→0sup

Δy?P(ε)?

?Δx?R?Δy?D?Comment apprécier la fiabilité de l"algorithme de résolution? L"erreur inverse mesure la distance entre le problème que l"on a

effectivement résolu et le problème initial.Erreur inverse:η(?x) =minΔy?D{?Δy?D:?x=G(y+ Δy)}S. Graillat (Univ. Paris 6)Algorithme de Horner compensé9 / 40

Intérêt de l"analyse inverse

Comment estimer la précision de la solution calculée?

Au premier ordre, on a l"estimation empirique :erreur directe?conditionnement×erreur inverse.Comment mesurer la difficulté de résolution d"un problème?

Le conditionnement caractérise la sensibilité de la solution d"un problème à des perturbations sur les données.Conditionnement:K(P,y) :=limε→0sup

Δy?P(ε)?

?Δx?R?Δy?D?Comment apprécier la fiabilité de l"algorithme de résolution? L"erreur inverse mesure la distance entre le problème que l"on a

effectivement résolu et le problème initial.Erreur inverse:η(?x) =minΔy?D{?Δy?D:?x=G(y+ Δy)}S. Graillat (Univ. Paris 6)Algorithme de Horner compensé9 / 40

Plan de l"exposé

1Motivations

2Évaluation précise de polynômes

3Applications

S. Graillat (Univ. Paris 6)Algorithme de Horner compensé10 / 40

Nombres à virgule flottante

Un nombre flottant normaliséx?Fest un nombre qui s"écrit sous la forme x=±x0.x1...xp-1???? Modèle standard de l"arithmétique à virgule flottante TypeTailleMantisseExposantUnité d"arrondiIntervalle Simple32 bits23+1 bits8 bitsu=2-24≈5,96×10-8≈10±38

Double64 bits52+1 bits11 bitsu=2-53≈1,11×10-16≈10±308S. Graillat (Univ. Paris 6)Algorithme de Horner compensé12 / 40

Pour une évaluation plus précise

Évaluation dep(x)plus précise : leschéma de Horner compenséet l"estimation empirique compensée Une borne améliorée etcertifiéede l"erreur Les résultats théoriques et expérimentaux montrent que précision : identique à celle obtenue si les calculs avaient été effectués avecdeux fois la précision courante, vitesse :deux fois plus rapideque l"implémentation double-double de référence S. Graillat (Univ. Paris 6)Algorithme de Horner compensé13 / 40

Plus de précision, comment?

Augmenter la précision interne des calculs :

de façon matérielle précision étendue sur l"architecture x86 de façon logicielle expansions de longueur finie :double-double(Briggs, Bailey, Hida, Li), quad-double (Bailey, Hida, Li)expansions de longueur variable : Priest, Shewchuk précision arbitraire : MP, MPFUN/ARPREC, MPFR

Corriger les erreurs d"arrondis :

sommation compensée (Kahan,1965) et doublement compensée (Priest,1991), etc.sommation et produit scalaire : Ogita, Rump et Oishi (2005) →résultat avec une précision identique à celle obtenue si on faisait les calculs avec 2 fois la précision courante S. Graillat (Univ. Paris 6)Algorithme de Horner compensé14 / 40

Plus de précision, comment?

Augmenter la précision interne des calculs :

de façon matérielle précision étendue sur l"architecture x86 de façon logicielle expansions de longueur finie :double-double(Briggs, Bailey, Hida, Li), quad-double (Bailey, Hida, Li)expansions de longueur variable : Priest, Shewchuk précision arbitraire : MP, MPFUN/ARPREC, MPFR

Corriger les erreurs d"arrondis :

sommation compensée (Kahan,1965) et doublement compensée (Priest,1991), etc.sommation et produit scalaire : Ogita, Rump et Oishi (2005) →résultat avec une précision identique à celle obtenue si on faisait les calculs avec 2 fois la précision courante S. Graillat (Univ. Paris 6)Algorithme de Horner compensé14 / 40

À précision courante ...

Estimation empirique pour les algorithmes inverses-stables :

précision du résultat≈conditionnement×précision de calcul1précision IEEE-754 : double (u=2-53≈10-16)2Conditionnement pour l"évaluation dep(x) =?n

i=0aixi:cond(p,x) =? n i=0|ai||x|i| ?n i=0aixi|=?p(|x|)|p(x)|,toujours≥1.3Précision de la solution

Que signifie doubler la précision courante?

Estimation empirique compensée :

précision du résultat?précision + conditionnement×précision2Trois régimes pour la précision de l"évaluation de

10-18 10-16 10-14 10-12 10-10 10-8 10-6 10-4quotesdbs_dbs3.pdfusesText_6

[PDF] horner method

[PDF] méthode de horner exercice corrigé

[PDF] schema de horner

[PDF] algorithme de horner python

[PDF] seuil de rentabilité cours pdf

[PDF] méthode des couts variables exercices corrigés

[PDF] exercice seuil de rentabilité corrigé pdf

[PDF] levier opérationnel calcul

[PDF] représentation graphique du seuil de rentabilité

[PDF] calcul du seuil de rentabilité avec plusieurs produits

[PDF] indice de sécurité calcul

[PDF] exercice seuil de rentabilité bts

[PDF] choix d'investissement exercices

[PDF] rentabilité des investissements cours

[PDF] calcul drci+formule