66
Calcul Formel et Numérique INFO-F-205 G. Bontempi Département d’Informatique Boulevard de Triomphe - CP 212 http://www.ulb.ac.be/di Cours de calcul numérique – p. 1/??

Calcul Formel et Numérique

Embed Size (px)

Citation preview

Page 1: Calcul Formel et Numérique

Calcul Formel et NumériqueINFO-F-205

G. Bontempi

Département d’Informatique

Boulevard de Triomphe - CP 212

http://www.ulb.ac.be/di

Cours de calcul numérique – p. 1/??

Page 2: Calcul Formel et Numérique

COMMUNICATIONS• Premier TP: mercredi 16 février, salle A2.120

• Pas de cours lundi 7 mars.

Cours de calcul numérique – p. 2/??

Page 3: Calcul Formel et Numérique

Ressources• Syllabus (PUB).

• Livre: A. Quarteroni, R. Sacco, F. Saleri Méthodes numériques pour lecalcul scientifique, Springer. Disponible à la bibliothèque DI.

• Page web du courshttp://www.ulb.ac.be/di/map/gbonte/InfoF205.html

• transparents du cours (vendredi avant le cours),• valves: horaires, salles, accès web,• table des matières,• livres de références,• sites web de références,• code Matlab,• énoncés des projets,• énoncés et corrigés des écrits de l’année précédente.

Cours de calcul numérique – p. 3/??

Page 4: Calcul Formel et Numérique

Ressources (II)• rendez-vous:

• fixer par email ([email protected]) en spécifiant nom, raison etdurée prévue,

• au moins 2 jours ouvrables à l’avance.

• Délégué étudiant.

Cours de calcul numérique – p. 4/??

Page 5: Calcul Formel et Numérique

Répartition points examen1. projet obligatoire (2/20)

2. écrit (15/20)

3. oral facultatif (3/20)

Cours de calcul numérique – p. 5/??

Page 6: Calcul Formel et Numérique

Table de matières du cours• Introduction au calcul numérique.

• Analyse d’erreurs

• Résolution des systèmes linéaires.

• Résolution numérique des équations différentielles ordinaires.

• Interpolation.

• Curve fitting.

• Résolution des équations non linéaires.

Cours de calcul numérique – p. 6/??

Page 7: Calcul Formel et Numérique

Table de matières• Définition du calcul numérique.

• Des phénomènes réels aux modèles.

• Résolution analytique et numérique.

• Problèmes bien posés et mal posés.

• Définition d’algorithme.

• Propriétés des algorithmes

• Calcul numérique sur l’ordinateur• Programmes• Archives• Outils

Cours de calcul numérique – p. 7/??

Page 8: Calcul Formel et Numérique

Préjugés sur la matière• Discipline non attrayante.

• Trop théorique.

• A quoi cela sert-il?

• Est-elle vraiment utile pour un informaticien?

Cours de calcul numérique – p. 8/??

Page 9: Calcul Formel et Numérique

Désastres et calcul numériqueAvez vous porté suffisamment d’attention à votre cours de calcul numérique?Si ce n’est pas le cas, ceci pourrait avoir des conséquences effroyables...Voici quelques exemples de désastres qui ont eu pour cause une mauvaisecompréhension et utilisation des algorithmes de calcul numerique. (extrait dela page web http://www.ima.umn.edu/∼arnold/disasters/)

• L’erreur de fonctionnement du missile Patriot à Dharan, Arabie Saudite,le 25 février 1991 qui a causé la mort de 28 soldats américains était laconséquence d’une erreur numérique.

• L’explosion de la roquette Ariane 5 juste après son décollage enGuyane, le 4 juin 1996, fut la conséquence d’une erreur d’overflow.

• L’échouement de la plate-forme pétrolière Sleipner A à Gandsfjorden enNorvège le 23 août 1991, qui eut pour conséquence une perte d’unmilliard de dollars, fut le résultat d’une simulation numérique imprécise.

Cours de calcul numérique – p. 9/??

Page 10: Calcul Formel et Numérique

Définition de calcul numérique• Nous proposons une définition formelle de calcul numérique basée sur

la définition de Nick Trefethen (Oxford University):

• Le calcul numérique est une discipline qui traite de la conception,l’analyse et l’implémentation d’algorithmes pour la résolution numériquedes problèmes mathématiques continus qui proviennent de lamodélisation des phénomènes réels.

• Cette définition s’appuie sur plusieurs notions, comme celle de modèle,de problème et d’algorithme, que nous allons présenter dans la suite.

Cours de calcul numérique – p. 10/??

Page 11: Calcul Formel et Numérique

Du modèle au problème mathématiqueL’utilisation d’un modèle pour la résolution d’un problème pratique passe àtravers la résolution d’un problème mathématique.

PROBLEME MATHEMATIQUEPROBLEME APPLICATIF

SOLUTION DU PROBLEME SOLUTION MATHEMATIQUE

interpretation

construction du modèle

numériqueresolutionanalytique

resolution

Les modèles mathématiques continus prennent typiquement la forme d’unensemble d’équations (algébriques ou différentielles) et/ou inéquations avecparamètres (connus et/ou inconnus).

Cours de calcul numérique – p. 11/??

Page 12: Calcul Formel et Numérique

Problème mathématique• Un problème mathématique continu est une relation fonctionnelle F

entre un ensemble de données d et une solution x.

• On peut distinguer entre deux formes de problème:

Forme explicite:

x = F (d)

Forme implicite:

F (x, d) = 0

• Selon la nature du problème, la solution x et les données d peuvent êtrereprésentées par des matrices, des nombres réels ou des fonctions.

Cours de calcul numérique – p. 12/??

Page 13: Calcul Formel et Numérique

Un exemple: Page Rank• Page Rank est le nom de l’algorithme proposé par L. Page and S. Brin,

à l’époque étudiants à Stanford et plus tard les fondateurs de

• Cet algorithme est à la base des rankings renvoyés par Google.

• L’algorithme originaire était basé entièrement sur la connectivité du Webet n’utilisait aucune information sur le contenu des pages Web.

• Une fois qu’une requête est émise, GOOGLE cherche les pages surInternet qui satisfont la requête et les ordonne sur la base du rangrenvoyé par Page Rank.

Cours de calcul numérique – p. 13/??

Page 14: Calcul Formel et Numérique

Formulation mathématique• Considérons l’ensemble de n pages Web qui peuvent être atteintes

suivant les hyperliens.

• Soit G une matrice de taille [n, n] telle que G[i, j] = 1 si il existe un lienj → i, autrement G[i, j] = 0.

• Soit deg(j) =∑n

i=1 gij le degré de sortie de la jème page, c.-à-d. lenombre de pages pointées par j.

• Construisons la matrice A telle que

A[i, j] =

{

G[i, j]/deg(j), si deg(j) > 0

1/n, si deg(j) = 0

• L’idée de Page Rank est que le rang d’une page i est la combinaisonlinéaire des degrés des pages qui pointent vers elle, pondérée parl’inverse du degré de sortie des pages d’origine

xi =

n∑

j=1

A[i, j]xj =∑

j→i

xj/deg(j)

Cours de calcul numérique – p. 14/??

Page 15: Calcul Formel et Numérique

Formulation mathématique• Le rang x est donc la solution non nulle du problème en forme implicite

(I − A)x = 0

où I est la matrice identité de taille n.

• Ceci est un problème très complexe en calcul numérique pour lesraisons suivantes:• les données d sont représentées par une matrice A de taille n où n

est énorme,• la matrice A est creuse.

• Un algorithme itératif pour la résolution du problème x = Ax est

x(k) = Ax(k−1)

où la condition initiale est le vecteur colonne x(0) = [1/n, . . . , 1/n] detaille n.

Cours de calcul numérique – p. 15/??

Page 16: Calcul Formel et Numérique

Page rank: exemple

3

P1

P2

P

Puisque n = 3, le vecteur solution est x = [x1, x2, x3]

G =

0 0 1

1 0 1

0 0 0

, A =

0 1/3 1/2

1 1/3 1/2

0 1/3 0

, I − A =

1 −1/3 −1/2

−1 2/3 −1/2

0 −1/3 1

En utilisant l’algorithme nous obtenons

x(0) = [1/3, 1/3, 1/3]T ⇒ x(100) = [0.27, 0.54, 0.19]T

Cours de calcul numérique – p. 16/??

Page 17: Calcul Formel et Numérique

Exemple: le penduleLe pendule est un système physique composé par une masse suspendue àun fil tendu de longueur l et soumise à l’action de la pesanteur

ϕ

Un modèle mathématique continu qui est souvent utilisé pour décrire lesystème physique est

ϕ′′(t) = −ω2sin(ϕ(t)) ϕ(0) = ϕ0, ϕ′(0) = 0

où ϕ est le déplacement angulaire, ω2 = g/l, et g est l’accélération de lagravité.

Cours de calcul numérique – p. 17/??

Page 18: Calcul Formel et Numérique

Trouver la valeur de l’angle ϕ(t) pour t = 10 qui satisfait l’équationdifférentielle

ϕ′′(t) = −ω2sin(ϕ(t)) ϕ(0) = π/2, ϕ′(0) = 0

qui décrit l’évolution de la position du pendule.

Le problème, dont la solution est x = ϕ(10) et les données sontd = [ϕ(0), ϕ′(0)], est en forme implicite.

Cours de calcul numérique – p. 18/??

Page 19: Calcul Formel et Numérique

Exemples de problèmes1. Trouver la racine carrée de d: x =

√d. Ceci est un problème sous forme

explicite.

2. Trouver la plus grande racine x de l’équation algébrique

ax2 + bx + c = 0

où les données sont représentées par le vecteur d = [a, b, c]. Ceci est unproblème sous forme implicite.

Cours de calcul numérique – p. 19/??

Page 20: Calcul Formel et Numérique

Exemples de problèmes (II)Trouver la solution x = [x1, x2, x3] du système

2x1 + 4x2 − 6x3 = −4

x1 + 5x2 + 3x3 = 10

x1 + 3x2 + 2x3 = 5

où les données sont représentées par la matrice

d =

2 4 −6 −4

1 5 3 10

1 3 2 5

Cours de calcul numérique – p. 20/??

Page 21: Calcul Formel et Numérique

Problèmes bien/mal posésLa notion de problème bien/mal posé a été introduite pour la première foispar Hadamard en 1923.

Définition (Problème bien posé). Le problème mathématique x = F (d) est bien posé si la

solution x

• existe,

• est unique,

• dépend continûment des données d.

Autrement le problème est dit mal posé.

Nous ne considérerons dans le cours que des problèmes bien posés.

Cours de calcul numérique – p. 21/??

Page 22: Calcul Formel et Numérique

Problèmes inverses• On retrouve des exemples de problèmes mal posés aussi dans le cas de

problèmes inverses, qui consistent à trouver d étant donné x.

• Considérons un problème direct où deux valeurs différentes de d

produisent le même x:

d x

d

d

1

2

• Le problème inverse d = F−1(x) est par conséquent mal posé.

Cours de calcul numérique – p. 22/??

Page 23: Calcul Formel et Numérique

Problèmes inverses (II)Des exemples de problèmes inverses mal posés mais très importants dansles sciences sont les suivants:

• trouver la cause d’un certain effet;

• trouver la position d’un obstacle à partir de l’information radar;

• mesurer l’épicentre d’un phénomène sismique;

• trouver une information sur une scène 3D à partir d’une image 2D (parexemple dans le procédé de la tomographie);

• trouver sur une barre métallique la valeur de la température en sachantla température en une autre position;

• estimer la température d’un objet à l’instant initial en sachant latempérature à l’instant final;

• trouver la solution d’équations différentielles partielles.

Cours de calcul numérique – p. 23/??

Page 24: Calcul Formel et Numérique

Exemples de problèmes mal posés1. Un cas simple de problème mal posé est x = (d > 0.5) où d est un

nombre réel et x ∈ {0, 1}.

2. Un autre exemple de problème mal posé est le suivant: Trouver lenombre x de racines réelles distinctes d’un polynôme.• Considérons le polynôme

p(z, d) = d + z − 2z2 + z3

• Le nombre de racines réelles x varie de façon discontinue pour d

autour du zéro

x = 1 si d > 0

x = 2 si d = 0

x = 3 si d < 0

Cours de calcul numérique – p. 24/??

Page 25: Calcul Formel et Numérique

−1 −0.5 0 0.5 1 1.5 2−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1d=0.09

−1 −0.5 0 0.5 1 1.5 2−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1d=0

−1 −0.5 0 0.5 1 1.5 2−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1d=−0.07

Les figures représentent différents polynômes p(z, d) pour différentes valeursde d prés du zéro.

Cours de calcul numérique – p. 25/??

Page 26: Calcul Formel et Numérique

Conditionnement d’un problème• Le conditionnement d’un problème bien posé de la forme x = F (d)

mesure la sensibilité de la solution x du problème aux changements desdonnées d.

• Soient δd une perturbation admissible des données et δx la modificationinduite sur la solution du problème x = F (d).

• On appelle conditionnement relatif de ce problème la quantité

κ(d) = supδd∈D

‖δx‖/‖x‖‖δd‖/‖d‖

où sup dénote la borne supérieure, D est un voisinage de l’origine, lesymbole ‖ · ‖ désigne la norme matricielle.

• Quand d = 0 ou x = 0, il est nécessaire d’introduire le conditionnementabsolu

κabs(d) = supδd∈D

‖δx‖‖δd‖

Cours de calcul numérique – p. 26/??

Page 27: Calcul Formel et Numérique

Conditionnement d’un problème (II)Si

1. le problème est en forme explicite x = F (d),

2. F (·) est différentiable en d et

3. si nous notons par F ′(d) ≈ δxδd

sa dérivée,

le conditionnement relatif peut être écrit de la manière suivante

κ(d) =

‖δx‖‖x‖

‖δd‖‖d‖

=‖δx‖‖δd‖

‖d‖‖x‖ ≈ ‖F ′(d)‖‖d‖‖x‖ = ‖F ′(d)‖ ‖d‖

‖F (d)‖

Cours de calcul numérique – p. 27/??

Page 28: Calcul Formel et Numérique

Considérations• Un problème peut avoir un petit conditionnement κ(d) pour certaines

valeurs de d et un grand conditionnement pour d’autres valeurs.

• Si κ(d) est grand pour toute donnée admissible d, le problème est ditmal conditionné.

• Le conditionnement associé à un problème est une mesure de ladifficulté de résolution numérique du problème.

En outre, il est important de remarquer que

• un problème mal posé est forcément aussi un problème mal conditionné,mais que mal conditionné ne signifie pas forcement mal posé;

• le fait d’être bien conditionné est une propriété du problème qui estindépendante de la méthode choisie pour le résoudre.

Cours de calcul numérique – p. 28/??

Page 29: Calcul Formel et Numérique

ExemplesConsiderons la série logistique

s(k + 1) = 4s(k)(1 − s(k)), 0 ≤ s(k) ≤ 1

Definissons le problème où d = s(0) et x = s(20). En faisant varier d onremarque qu’une très légère variation suffit à donner après quelquesitérations des résultats x très différents.Notons que ce problème est mal conditionné:

d = 0.2 ⇒ x = 0.82

d = 0.2001 ⇒ x = 0.8116

d = 0.201 ⇒ x = 0.9877

d = 0.21 ⇒ x = 0.3143

Cet exemple est souvent cité pour montrer comment un comportementcomplexe peut émerger d’une équation dynamique non-linéaire (plus dedétails dans INFO-F-305).

Cours de calcul numérique – p. 29/??

Page 30: Calcul Formel et Numérique

ExempleConsidérons les deux problèmes implicites

F1(x, d) = g1(x) − d = 0, F2(x, d) = g2(x) − d = 0

où g1(x) et g2(x) sont

x

d d

g (x)1

g (x)2

x

Lequel des deux est le mieux conditionné?

Cours de calcul numérique – p. 30/??

Page 31: Calcul Formel et Numérique

ExempleConsidérons les deux problèmes explicites

x = F1(d), x = F2(d)

où F1(d) et F2(d) sont

d

x x

F (d)1

F (d)2

d

Lequel des deux est le mieux conditionné?

Cours de calcul numérique – p. 31/??

Page 32: Calcul Formel et Numérique

Exemples• Considérons le problème x = F (d) = d − 1.

Le conditionnement relatif du problème est

κ(d) ≈ ‖F ′(d)‖ ‖d‖‖F (d)‖ =

‖d‖‖d − 1‖

Il en résulte que κ(d) > 100 pour 0.999 < d < 1.001. Donc, le problèmeest mal conditionné pour les valeurs de d autour de 1.

• Considérons le problème x = F (d) = d1000. Alors

κ(d) ≈ ‖F ′(d)‖ ‖d‖‖F (d)‖ = 1000‖d999‖ ‖d‖

‖d1000‖ = 1000

Le problème est mal conditionné pour toute valeur de d.

Cours de calcul numérique – p. 32/??

Page 33: Calcul Formel et Numérique

La résolution d’un problèmeDeux approches peuvent être envisagées:

Résolution symbolique: ceci utilise les propriétés analytiques etmathématiques du problème pour en dériver la solution x.Malheureusement une solution analytique n’est pas calculable pour tousles problèmes.

Résolution numérique: ceci utilise une méthode numérique pour déterminer lasolution x pour une valeur d donnée.

Cours de calcul numérique – p. 33/??

Page 34: Calcul Formel et Numérique

Exemple• Considérons le problème élémentaire de la recherche des racines d’une

équation du second ordre

d1x2 + d2x + d3 = 0,

où d = [d1, d2, d3].

• La solution analytique est

x =−d2 ±

d22 − 4d1d3

2d1.

• La solution numérique pour d = [0.1, 1.2, 0.3] est x = −11.74.

Cours de calcul numérique – p. 34/??

Page 35: Calcul Formel et Numérique

Pour/contre une approche numériqueUne méthode numérique présente des bénéfices aussi bien que desinconvénients par rapport à une solution analytique.Les avantages tiennent au fait

1. qu’une solution numérique peut être obtenue aussi lorsqu’aucunesolution analytique n’est disponible,

2. que la décomposition d’une méthode numérique en une longue séried’opérations arithmétiques élémentaires s’avère être facilement gérablepar un ordinateur.

A son détriment, il faut mentionner que l’analyse et l’étude d’une solutionnumérique sont typiquement plus coûteuses.

Cours de calcul numérique – p. 35/??

Page 36: Calcul Formel et Numérique

Définition qualitative d’algorithme

Définition. Un algorithme est un texte fini qui spécifie l’exécution d’une série finie

d’opérations élémentaires, conçue pour résoudre des problèmes d’une classe ou d’un type

particulier.

Cours de calcul numérique – p. 36/??

Page 37: Calcul Formel et Numérique

Propriétés d’un algorithme• un algorithme décrit la résolution d’un problème en utilisant un niveau

d’abstraction qui dépend du type et du nombre d’opérationsélémentaires;

• un algorithme est destiné à résoudre une classe de problèmes et passimplement une occurrence isolée d’un problème;

• un algorithme est exécuté par un processeur. Le processeur peut êtreun être humain, une mécanique ou plus généralement par un ordinateur;

• l’exécution d’un algorithme procède par étapes;

• un algorithme peut être décomposé en plusieurs sous-algorithmes;

• la description d’un algorithme est nécessairement de longueur finie;

Cours de calcul numérique – p. 37/??

Page 38: Calcul Formel et Numérique

Propriétés d’un algorithme (II)• on dit qu’un algorithme se termine s’il s’achève après un nombre fini

d’étapes et s’il renvoie un résultat à chaque exécution;

• un algorithme est dit déterministe si à chaque moment de l’exécution, laprochaine étape est déterminée de façon unique.

• Si plusieurs alternatives existent, l’algorithme est dit non-déterministe.

• Un algorithme non-déterministe est dit stochastique si la probabilité desdifférentes alternatives est décrite par une distribution de probabilité.

Cours de calcul numérique – p. 38/??

Page 39: Calcul Formel et Numérique

Complexité d’un algorithme• Plusieurs mesures peuvent être adoptées pour caractériser la

complexité d’un algorithme: le nombre d’étapes, le temps d’exécution,l’occupation de la mémoire ou des mesures dépendantes del’architecture du processeur.

• Dans certains cas l’utilisateur de l’algorithme est intéressé à avoir uneidée qualitative du comportement de l’algorithme plutôt que le nombreexact d’opérations.

• Pour ce faire, la notion d’ordre de complexité (ou complexitéasymptotique) à été introduite.

• Cette notion consiste à définir une mesure de complexité ( par exemplele nombre d’operations arithmetiques) comme une fonction de la tailledes données du problème.

Cours de calcul numérique – p. 39/??

Page 40: Calcul Formel et Numérique

Ordre de complexité• Si la complexité d’un algorithme dépend d’un paramètre p (représentant

la taille des données du problème), la complexité C(p) d’un algorithmeest dite d’ordre f(p) s’il existe deux constantes a et b telles que

C(p) ≤ bf(p) pour tout p ≥ a.

• Ceci est indiqué par la notation conventionnelle "grand O"

C(p) = O(f(p)).

Cours de calcul numérique – p. 40/??

Page 41: Calcul Formel et Numérique

Classes de complexitéOrdre Classe de complexité exemple de C(p)

O(1) constante c ∈ R+

O(log p) logarithmique c log p

O(p) linéaire c1p + c0

O(p2) quadratique c2p2 + c1p + c0

O(p3) cubique c3p3 + c2p

2 + . . ....

......

O(pm), m ∈ N polynomiale cmpm + cm−1pm−1 + . . .

O(cp) exponentielle cdp+polynôme(p)

O(p!) factorielle cp!

Si la complexité est définie en termes d’opérations arithmétiques, quelle estla complexité de

• la somme de deux vecteurs d1 et d2 de taille n

• la somme de deux matrices carrées A1 et A2 de taille n

• le produit de deux matrices carrées A1 et A2 de taille n

Cours de calcul numérique – p. 41/??

Page 42: Calcul Formel et Numérique

Complexité d’un problème• Notons que même si nous pouvons définir la complexité d’un algorithme,

la notion de complexité d’un problème reste floue, car plusieursalgorithmes de complexité différente peuvent être utilisés pour résoudrele même problème.

• En général, nous définissons la complexité d’un problème comme étantla complexité de l’algorithme qui a la complexité la plus petite parmiceux qui résolvent le problème.

Cours de calcul numérique – p. 42/??

Page 43: Calcul Formel et Numérique

Algorithmes numériques•

Définition (Algorithme numérique). Étant donné un problème bien posé F (x, d) = 0,

nous définissons l’algorithme numérique pour la résolution du problème F par la suite

de problèmes approchés F1(x(1), d(1)), F2(x

(2), d(2)), . . . , Fn(x(n), d(n))

dépendant d’un paramètre n.

• L’idée sous-jacente à la décomposition en sous-problèmes est que larésolution des Fn est plus simple que la résolution de F . Ceci rendpossible l’exécution d’un algorithme par une machine.

• Différents algorithmes peuvent résoudre le même problème numérique.

• Il est alors nécessaire de choisir l’algorithme qui présente les meilleurspropriétés numériques et de complexité.

Cours de calcul numérique – p. 43/??

Page 44: Calcul Formel et Numérique

Propriétés d’un algorithme numériqueUn algorithme numérique transforme un problème en une série desous-problèmes.Les propriétés souhaitées d’un algorithme numérique sont

• la consistance: ceci concerne la capacité d’un algorithme dedécomposer le problème original en une série de sous-problèmes quiont parmi leurs solutions aussi la solution originale.

• la stabilité: ceci concerne la robustesse de la solution d’un algorithme àdes perturbations possibles.

• la convergence: ceci concerne la convergence de la solution del’algorithme vers la solution du problème.

Cours de calcul numérique – p. 44/??

Page 45: Calcul Formel et Numérique

Consistance• Rappelons nous que Fn(x(n), d(n)) = 0 signifie que x(n) est la solution

produite par l’exécution de la nème étape de l’algorithme.

Définition. Un algorithme Fn(x(n), d(n)) est dit consistant si

limn→∞

Fn(x, d(n)) = F (x, d) = 0,

c.-à-d., si la solution exacte x du problème est parmi les solutions de

Fn(x(n), d(n)) = 0 pour n → ∞.

•Un algorithme itératif x(n+1) = f(x(n)) est donc consistant si

x(n) = x ⇒ x(n+1) = x

• Attention: être consistant ne signifie pas que x(n) converge vers x maisseulement que l’algorithme a été conçu de manière à avoir la solution x

parmi les solutions de ses sous-problèmes pour n → ∞.

Cours de calcul numérique – p. 45/??

Page 46: Calcul Formel et Numérique

Consistance forteDéfinition. Un algorithme Fn(x(n), d(n)) est dit fortement consistant si Fn(x, d(n)) = 0

pour tout n.

Ceci signifie que tous les sous-problèmes Fn ont x parmi leurs solutions.

Cours de calcul numérique – p. 46/??

Page 47: Calcul Formel et Numérique

Exemple: algo consistantSupposons de connaitre la forme analytique de la fonction univariée g(t) etde vouloir calculer l’integral

x =

∫ b

a

g(t)dt

g(t)

1 t2 t3 t4 t5 t =bna=t

t

L’algorithme, dit du point milieu, est basé sur la suite de problèmesapprochés suivante

x(n) =b − a

n

n∑

k=1

g

(

tk + tk+1

2

)

L’algorithme est consistant mais pas fortement.

Cours de calcul numérique – p. 47/??

Page 48: Calcul Formel et Numérique

Exemple: algo fort. consistConsidérons le problème mathématique F (x, d) = 0 qui correspond à larésolution d’un système linéaire d’ordre 3:

2x1 + 4x2 − 6x3 = −4

x1 + 5x2 + 3x3 = 10

x1 + 3x2 + 2x3 = 5

Les données sont représentées par

d =

2 4 −6 −4

1 5 3 10

1 3 2 5

et la solution est x = [−3, 2, 1].

Cours de calcul numérique – p. 48/??

Page 49: Calcul Formel et Numérique

Considérons un algorithme de résolution numérique en 2 étapes où lapremière étape est représentée par le problème implicite

F1(x(1), d(1)) = 0 ⇔

2x1 + 4x2 − 6x3 = −4

3x2 + 6x3 = 12

x2 + 5x3 = 7

d(1) =

2 4 −6 −4

0 3 6 12

0 1 5 7

et x(1) = x = [−3, 2, 1].NB: ne pas confondre la solution x(n) (vecteur) de la nème étape del’algorithme et le nème composant (scalaire) de la solution x du problème.

Cours de calcul numérique – p. 49/??

Page 50: Calcul Formel et Numérique

Soit la deuxième étape représentée par le problème implicite

F2(x(2), d(2)) = 0 ⇔

2x1 + 4x2 − 6x3 = −4

3x2 + 6x3 = 12

3x3 = 3

avec

d(2) =

2 4 −6 −4

0 3 6 12

0 0 3 3

et x(2) = x = [−3, 2, 1].Pour toute valeur de n (n = 1, 2), Fn(x, d(n)) = 0. Donc cet algorithme estfortement consistant.

Cours de calcul numérique – p. 50/??

Page 51: Calcul Formel et Numérique

Stabilité d’un algorithmeSoit x(n) la suite des solutions approchées produite par l’algorithme pour lesdonnées d(n) et x̄(n) = x(n) + δx(n) la suite des solutions approchées produitepar l’algorithme suite aux perturbations {δd(i)}, i = 1, . . . , n des données.

Définition (Stabilité). Un algorithme numérique est dit stable (ou bien posé) si

1. il existe pour tout n une solution unique x(n)

2. pour chaque ǫ > 0 il existe un η > 0 et un n0 tel que

‖δd(i)‖ ≤ η ⇒ ‖x̄(n) − x(n)‖ ≤ ǫ pour tout n > n0

Cours de calcul numérique – p. 51/??

Page 52: Calcul Formel et Numérique

Stabilité d’un algorithme

(0)

x2

ε

x (n)

x(n)

η

x 1

x(0)x

Cours de calcul numérique – p. 52/??

Page 53: Calcul Formel et Numérique

Conditionnement asymptotique relatif• Nous appelons conditionnement asymptotique relatif de la méthode

numérique la quantité

κnum(d(n)) = limk→∞

supn≥k

κn(d(n)),

κn(d(n)) = supδd(n)∈Dn

‖δx(n)‖/‖x(n)‖‖δd(n)‖/‖d(n)‖ .

• L’algorithme numérique est dit bien conditionné si κnum est “petit” pourtoutes données d(n) et mal conditionné sinon.

Cours de calcul numérique – p. 53/??

Page 54: Calcul Formel et Numérique

Exemple• Considérons le problème mathématique

2x = 1

• et les deux algorithmes itératives suivants, où x(0) = 1/2 + δ

1.

x(n) = d(n)x(n−1) +1

4, d(n) =

1

2

2.

x(n) = d(n)x(n−1) − 1

2, d(n) = 2

• Tous les deux sont consistants mais uniquement le premier algorithmeest stable.

• Dans le premier cas uniquement, un petit changement δd(n) desdonnées entraîne un changement borné de la solution x(n) pour tous n

(script MATLAB s_stable2.m et s_unstable2.m).

Cours de calcul numérique – p. 54/??

Page 55: Calcul Formel et Numérique

Convergence d’un algorithmeSoit x̄(n) = x(n) + δx(n) la suite des solutions approchées produite parl’algorithme suite aux perturbations {δd(i)}, i = 1, . . . , n des données.

Définition (Convergence). Un algorithme est convergent si

limn→∞,δd(i)→0

x̄(n) = limn→∞,δd(i)→0

x(n) + δx(n) = x

ou, en d’autres termes, si pour chaque ǫ > 0 il existe η > 0 et un n0 tels que pour tous

n > n0

‖δd(i)‖ ≤ η ⇒ ‖x̄(n) − x‖ ≤ ǫ

• Les concepts de stabilité et convergence sont fortement liés.

• Les méthodes numériques que nous allons considérer satisfons lesconditions du théorème de Lax-Richtmyer (ou théorème d’équivalence)selon lequel pour un algorithme numérique consistant, la stabilité estéquivalente à la convergence.

Cours de calcul numérique – p. 55/??

Page 56: Calcul Formel et Numérique

Calcul numérique en pratique• Tout calcul numérique est exécuté sur un ordinateur.

• Trois options:

1. Programmer les algorithmes.

2. Utiliser des librairies existantes.

3. Utiliser des outils numériques.

Cours de calcul numérique – p. 56/??

Page 57: Calcul Formel et Numérique

Programmation scientifique• Tout programme comporte trois types d’opérations:

1. entrées

2. calculs

3. sorties

• Pour les programmes scientifiques, les opérations liées auxentrées-sorties sont généralement peu volumineuses alors que lescalculs représentent l’essentiel du programme.

• La performance du calcul est strictement liée à

1. la complexité de l’algorithme

2. la façon dont on stocke et on accède en mémoire aux données (applications multimédia (codage, décodage, filtrage))

3. l’architecture hardware (séquentielle, parallèle)

4. langage utilisé pour le calcul numérique (Fortran, C, C++,Java)

Cours de calcul numérique – p. 57/??

Page 58: Calcul Formel et Numérique

Exemple: code numériqueDéfinition formelle de la variance statistique

var(x) =N−1∑

i=0

(x[i] − x̄)2 où x̄ =

1

N

N−1∑

i=0

x[i]

Code 1 pour calculer la variancefloat Var1 (int x[])

{

int x_sum=0;

for (i=0; i<N; i++)

x_sum+=x[i];

float x_avg=x_sum/N;

float var=0;

for (i=0;i<N;i++)

var+=(x[i]-x_avg)^2;

return var;

}

2N accès aux cases mémoire de x.

Cours de calcul numérique – p. 58/??

Page 59: Calcul Formel et Numérique

Exemple: code optimiséÉcriture alternative de la formule de la variance

var(x) =1

N

N−1∑

i=0

x[i]2 −(

∑N−1i=0 x[i]

N

)2

Code 2 pour calculer la variancefloat Var2 (int x[])

{

int x_sum=0, x_square=0;

for (i=0; i<N; i++)

{

x_tmp=x[i];

x_sum+=x_tmp;

x_square += x_tmp^2;

}

return x_square/N-(x_sum/N)^2;

}

N accès aux cases mémoire de x. Ceci entraîne un temps d’exécutioninférieur et une dissipation d’énergie moindre.

Cours de calcul numérique – p. 59/??

Page 60: Calcul Formel et Numérique

Fortran (FORmula TRANslation)• version originelle date de 1954

• le premier compilateur FORTRAN a été conçu par une équipe dechercheurs IBM guidée par John W. Backus. un des premiers exemplesde langage de haut niveau.

• avec le nouveau langage, les programmes pour calculer les paramètresdes réacteurs nucléaires exigeaient seulement des heures et non plusdes semaines!

• Fortran II, IV, 66 (1972): compilation séparée des modules.

• Fortran 77 (1980): DO loops, IF ... THEN ...ELSE.

• Fortran 90 (1991) CASE, DO, WHILE,Record, Array, allocationdynamique

• HPF (High Performance Fortran)

• Fortran 95 (1997)

• Fortran 2008

Cours de calcul numérique – p. 60/??

Page 61: Calcul Formel et Numérique

Archives numériquesA partir des années 70 un grand nombre de projets financés par legouvernement américain ont concerné le développement de logiciel pourl’analyse numérique.

• Archives Netlib (à partir du 1985)• LAPACK, EISPACK, LINPACK, FFTPACK• Fortran, C, C++

• National HPCC (High Performance Computing and Communications)Software Exchange• calcul parallèle• analyse des données et visualisation

• GAMS (Guide to Available Mathematical Software)• un projet du NIST (National Institute of Standards and Technology-http://math.nist.gov/)

• index des archives sur le Net

Cours de calcul numérique – p. 61/??

Page 62: Calcul Formel et Numérique

Outils commerciaux: MATLAB• Première version en 1984

• http:// www.mathworks.com

• actuellement version 7.9

• fonctionnalités de base et langage de programmation

• basé sur le routines LAPACK

• inclut des outils pour :• le calcul numérique et statistique• l’acquisition de données• l’analyse et l’exploration de données• la visualisation et le traitement d’images• le prototypage et le développement d’algorithmes• la modélisation et la simulation• la programmation et le développement d’applications

Cours de calcul numérique – p. 62/??

Page 63: Calcul Formel et Numérique

Outils commerciaux: Mathematica• http:// www.wolfram.com

• puissant en calcul symbolique. Il peut• effectuer de produits de facteurs,• factoriser des expressions plus ou moins complexes.• intégrer analytiquement,• dériver une expression,• rendre une expression moins compliquée.• résoudre des équations, numériquement ou exactement.

• aussi fonctionnalités numériques et graphiques

• permet d’éditer des textes mathématiques complexes

• langage de programmation

Cours de calcul numérique – p. 63/??

Page 64: Calcul Formel et Numérique

Outils public-domain• Octave

• http://www.octave.org/

• outil GNU d’analyse numérique libre similaire à Matlab.• Version stable (2.0.17 date du 2002).

• R

• http://www.r-project.org/

• outil GNU d’analyse statistique libre similaire à S.• langage et environnement pour le calcul statistique• aussi fonctionnalités numériques et graphiques.• R core team.• mon cours Méthodes stochastiques pour l’apprentissage

automatique.

Cours de calcul numérique – p. 64/??

Page 65: Calcul Formel et Numérique

Sujets récurrents en calcul numérique• La solution numérique d’un problème mathématique ne peut être plus

significative que le modèle même.

• Problèmes qui ne peuvent être résolus directement sont approchés pardes problèmes plus simples.

• Usage fréquente des résultats de l’algèbre linéaire.

• Souci pour les phénomènes d’amplitude des erreurs (numériques etd’approximation).

• Souci pour la stabilité des algorithmes.

• Souci pour la complexité et la performance du calcul.

• Tendance à surestimer les logiciels numériques: L’utilisateur estintelligent; le logiciel ne l’est pas.

Cours de calcul numérique – p. 65/??

Page 66: Calcul Formel et Numérique

Calcul numérique et réalité industriel• Avec les progrès foudroyants des performances des ordinateurs, le

calcul numérique devient de plus en plus réalisable et souple.

• Plusieurs applications:• recherche et développement• modélisation• simulation• organisation de la production• optimisation et planification (scheduling)• prévisions ( à longue et courte durée)• fiabilité.

Cours de calcul numérique – p. 66/??