numerique2_2

8/14/2019 numerique2_2

1/71

Universite Mohammed V Agdal

Faculte des SciencesDepartement de Mathematiques et Informatique

Avenue Ibn Batota, B.P. 1014

Rabat, Maroc

Filiere :

Sciences Mathematiques et Informatique (SMI)

et

Sciences Mathematiques (SM)

Module Analyse Numerique I :

ANALYSE NUMERIQUE

Notes de Cours

Par

Pr . Souad El Bernoussi Pr . Sad El Hajji Pr . Awatef [email protected] [email protected]

htttp://www.fsr.ac.ma/ANO/

Annee 2005-2006


2/71

TABLE DES MATIERES

1 Reprsentation des nombres en machine 31.1 Arithmtique des calculateurs et Sources derreurs . . . . . . . 3

1.1.1 Evaluation de lerreur . . . . . . . . . . . . . . . . . . . 31.1.2 La mmoire de lordinateur : le stockage des nombres . 5

1.2 Les rgles de base du modle . . . . . . . . . . . . . . . . . . . 71.3 Propagation des erreurs. . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 Conditionnement et stabilit numrique. . . . . . . . . 9

2 Rsolution de f(x)=0 112.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Mthode de la bissection. . . . . . . . . . . . . . . . . . . . . . 132.3 Mthode de Newton-Raphson: . . . . . . . . . . . . . . . . . 142.4 Mthode de la scante . . . . . . . . . . . . . . . . . . . . . . 152.5 Mthode du point xe . . . . . . . . . . . . . . . . . . . . . . 162.6 Convergence et ordre de convergence. . . . . . . . . . . . . . . 18

2.6.1 Interprtation graphique. . . . . . . . . . . . . . . . . . 192.6.2 Ordre de convergence. . . . . . . . . . . . . . . . . . . 20

2.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Algbre linaire 223.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2 Rappels sur les systmes linaires . . . . . . . . . . . . . . . . 233.3 Mthode Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.4 FactorisationLU . . . . . . . . . . . . . . . . . . . . . . . . . 303.4.1 Appplications de la FactorisationLU . . . . . . . . . . 323.5 Mesure des erreurs . . . . . . . . . . . . . . . . . . . . . . . . 333.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

1


3/71

4 Interpolation polynmiale 37

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.2 Une mthode directe base sur la rsolution dun systmelinaire: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.3 Une mthode itrative : Mthode de Lagrange . . . . . . . . . 424.3.1 Interpolation Linaire : . . . . . . . . . . . . . . . . . . 424.3.2 Interpolation parabolique . . . . . . . . . . . . . . . . 444.3.3 Interpolation de Lagrange . . . . . . . . . . . . . . . . 45

4.4 Interpolation Itre de Newton-Ctes . . . . . . . . . . . . . . 474.5 Erreur dInterpolation polynomiale : . . . . . . . . . . . . . . 504.6 Exercices: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Integration et drivation numrique. 555.1 Introduction : . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.2 Drivation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.2.1 Drive premire. . . . . . . . . . . . . . . . . . . . . 565.2.2 Formule gnrale en trois points. . . . . . . . . . . . . 595.2.3 Drives dordre suprieur. . . . . . . . . . . . . . . . . 605.2.4 Etude de lerreur commise. . . . . . . . . . . . . . . . . 62

5.3 Mthodes numriques dintgration. . . . . . . . . . . . . . . . 625.3.1 Formules fermes. . . . . . . . . . . . . . . . . . . . . . 635.3.2 Etude gnrale de lerreur commise. . . . . . . . . . . . 645.3.3 Formules composes. . . . . . . . . . . . . . . . . . . . 66

5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

2


4/71

Chapitre 1

Reprsentation des nombres enmachine

1.1 Arithmtique des calculateurs et Sources

derreurs

Si sophistiqu quil soit , un calculateur ne peut fournir que des rponsesapproximatives. Les approximations utilises dpendent la fois des con-traintes physiques (espace mmoire, vitesse de lhorloge...) et du choix desmthodes retenues par le concepteur du programme . (pour plus de dtails

sur le fonctionnement dun ordinateur et la terminologie de base voir parexemple la page web htttp://www.commentcamarche.com

Le but de ce chapitre est de prendre connaissance de limpact de cescontraintes et de ces choix mthologiques. Dans certains cas il doit tre prisen compte dans lanalyse des rsultats dont une utilisation errone pourraittre coteuse.

La premire contrainte est que le systme numrique de lordinateur estdiscret, cest dire quil ne comporte quun nombre ni de nombres; Il endcoule que tous les calculs sont entachs derreurs.

1.1.1 Evaluation de lerreurRappelons dabord quelques notion de base ;

SiXest une quantit calculer et Xla valeur calcule, on dit que :

1. X Xest lerreur etj Ej=j X Xjest lerreur absolue.

3


5/71

Exemple :

SiX= 2:224et X= 2:223alors lerreur absolue

j Ej=j X Xj= 2:224 2:223 = 0:001

2. Er =XXXr

est lerreur relative,Xr6= 0: Xrest une valeur de rfrencepourX. En gnral ,on prend Xr =X.

Exemple :

SiX= 2:224etX= 2:223alors , si on prendXr =X, lerreur relative

Er=X X

Xr= j X X

jj Xj =0:001

2:224=4 : 496 104

Cependant, si Xest la valeur dune fonction F(t) avec a t b;onchoisira parfois une valeur de rfrence globale pour toutes les valeursdet.

Exemple :

SIX= sin(t)avec0 t 4 ;on pourra prendre

X=

p2

2 = sup

0t

4

sin(t):

En gnral , on ne connait pas le signe de lerreur de sorte que lonconsidre les erreurs absolues et les erreurs relatives absolues.

Les oprations lmentaires propagent des erreurs.Dans la pratique, on considre que :

1) Lerreur absolue sur une somme est la somme des erreurs absolues.2) Lerreur relative sur un produit ou un quotient est la somme des

ereurs relatives.On peut estimer leet dune erreur Esur largument x dune fonction

f(x)au moyen de la drive de f(x). En eet f(x+E)

'f(x) +Ef0(x)

Exemple :Calculer la valeur de (11111111)2

La valeur fournie par une petite calculatrice cinq chires est1; 2345x1014

Mais la rponse exacte est 123456787654321.

4


6/71

La machine a donc tronqu le rsultat 5 chires et lerreur absolue est

de 6 199

.Lerreur relative est de 0:0005% .Cet exemple montre quil faut tablir clairement lobjectif vis.

Cet objectif est double ;1) Nous voulons un bon ordre de grandeur (ici 1014) et avoir le maximum

de dcimales exactes,2) Ce maximum ne peut excder la longueur des mots permis par la

machine et dpend donc de la machine

1.1.2 La mmoire de lordinateur : le stockage desnombres

La mmoire dun ordinateur est forme dun certain nombre dunits adess-ables appeles OCTETS . Un ordinateur moderne contient des millions voirdes milliards doctets. Les nombres sont stocks dans un ordinateur commeENTIERS ou REELS.

Les nombres entiers :

Les nombres entiers sont ceux que lon utilise dhabitude sauf que le plus

grand nombre reprsentable dpend du nombre doctets utiliss:-avec deux (2) octets, on peut reprsenter les entiers compris entre

32768et 32767

-avec quatre (4) octets on peut reprsenterr les entiers compris entre

2147483648et 2147483647

Les nombres rels

Dans la mmoire dun ordinateur, les nombres rels sont reprsents en no-tation ottante.Cette notation a t introduite pour garder une erreur relative peu prs

constante; quelque soit lordre de gandeur du nombre quon manipule.En notation ottante, un nombre a la forme:

5


7/71

x= Y be

best la base du systme numrique utilisYest la mantisse : une suite de s entier y1y2:::ysavecy16= 0si x 6= 0et

0 yi (b 1)eest lexposant(un nombre entier relatif)La norme choisie est celle o la mantisse est comprise entre 0et1et o

le premier chire aprs la virgule est dirent de zro.Calcul de lerreurNous terminons ce chapitre en dnissant les notions de troncature et

darrondie.

Exemple :En base 10; x= 1=15 = 0:066666666::::::Dans le cas dune reprsentation tronque nous aurons, pour s = 5,

f l(x) = 0:66666 101:

Remarquez comment nous avons modi lexposant an de respecter largle qui veut que le premier chire de la mantisse ne soit pas nul .

Dans ce cas, lerreur absolueXf l(X)est de6 107:. Lerreur relativeest de lordre de 105

Dans une reprsentation tronque s chires, lerreur relative maximaleest de lordre de 10s

Dans une reprsentation arrondie, lorsque la premire dcimale ngligeest suprieure 5, on ajoute 1 la dernire dcimale conserve.

Exemple :x =1 =15 =0:066666666:Nous crirons f l(x) = 0:66667 101Lerreur absolue serait alors 3:333 107et lerreur relative serait 5

106

En gnral, lerreur relative dans une reprsentation arrondie s chiresest de5

10(s+1) soit la moiti de celle dune reprsentation tronque.

6


8/71

1.2 Les rgles de base du modle

Pour eectuer une opration sur deux nombres rels, on eectue loprationsur leurs reprsentations ottantes et on prend ensuite la reprsentation ot-tante du rsultat.

laddition ottante

x y= f l(f l(x) +f l(y))

la soustraction ottante

x y= f l((x) f l(y))

la multiplication ottante

x y= f l(f l(x) fl(y))

la division ottante

x y= f l(f l(x)=fl(y))

Chaque opration intermdiaire dans un calcul introduit une nouvelleerreur darrrondi ou de troncature.

Dans la pratique, il faudra se souvenir du fait que deux expressionsalgbriquement quivalentes peuvent fournir des rsultats dirents et quelordre des oprations peut changer les rsultats.

Pour laddition et la soustraction on ne peut eectuer ces 2 oprationsque si les exposants sont les mmes. On transforme le plus petit exposant etdonc on ne respecte plus la rgle voulant que le premier chire de la mantissene soit pas nul.

Quelques remarques sur ce modle:On constate une dviation importante par rapport aux lois habituelles de

larithmtique.x+ (y+z)peut tre dirent de (x+y) +z:

Exemple :Pour 4 chires signicatifs (s= 4) on a :

(1 +0:0005) +0:0005 =1 :000

7


9/71

car

0:1 101+0:5: 103=0:1 : 101+0:00005: 101=0:1 101+0:0000: 101=0:1 101

et

1 + (0:0005+0:0005) =1 :001

Ainsi, laddition ottante nest pas associative .(TD:Sommation dunesrie termes positifs)

On constate aussi que si y est trs petit par rapport x, laddition de x

et y donnera seulement x.

Exemple :Lquation 1 +x = x a x = 0 comme unique solution. Mais dans un

systme 10 chires signicatifs, elle aura une innit de solutions (il sutde prendrej x j 5 1011)

La distributivit de la multiplication par rapport laddition.

Exemple :Considrons lopration

122 (333+695) = (122 333) + (122 695) =125416

Si nous eectuons ces deux calculs en arithmtique 3 chires (s = 3)et arrondi, nous obtenons:

122 (333+695) =(122) (1028)=122 103 101=(125660) =126 103

(122 333) + (122 695) =(40626) +(84790)406 102+848 102=(406+848) 102=(1254 102) =125 103

Donc la distributivit de la multiplication par rapport laddition nestpas respecte en arithmtique ottante.

8


10/71

1.3 Propagation des erreurs.

Une tude de la propagation des erreurs darrondi permattra dexpliquer cephnomne.

Soit calculerex laide de son dveloppement en srie qui est convergentpour toutx :

ex = 1 + x

1!+

x2

2! +:::

Il est evident que dans la pratique il est impossible deectuer la somma-tion dune innit de termes. On arrtera donc lorsque le terme gnral x

k

k!

devient infrieur 10t(on a t digits):Pour x ngatif on sait que le reste dela serie est infrieur au premier terme nglig donc 10t(puisque la serie

est altrne).Les calculs suivant sont fait sur ordinateur pourt = 14:

x1015202530

ex

4:54:105

3:06:107

2:06:109

1:39:1011

9:36:1014

S4:54:105

3:05:107

1:55:1071:87:105

6:25:104

On voit que pour x 20 les rsultats obtenus sont dpourvus de sens.Lexplication de ce phnomne est la suivante: pour x =

30 les termes

de la serie vont en croissant jusqu x3030!

= 8:1011 puis ils dcroissent etx107

107! ~ 9:19:1015:Lerreur absolue sur le terme maximal est de8:1011:1015 = 8:104:Ainsi

le rsultat obtenu pour Sreprsente uniquement laccumulation des erreursdarrondi sur les termes de plus grand module de dveloppement en serie.

1.3.1 Conditionnement et stabilit numrique.

Le fait que certains nombres ne soient pas reprsents de faon exacte dansun ordinateur entraine que lintroduction mme de donne dun problme en

machine modie quelque peu le problme initial; Il se peut que cette petitevariation des donnes entraine une variation importante des rsultats. Cestla notion de conditionnement dun problme.

On dit quun problme est bien (ou mal) conditionn, si une petite varia-tion des donnes entraine une petite (une grande) variation sur les rsultats.

9


11/71

Cette notion de conditionnement est lie au problme mathmatique lui

mme et est indpendante de la mthode utilise pour le rsoudre.Une autre notion importante en pratique est celle de stabilit numrique.Un problme peut tre bien conditionn et la mthode utilise pour le r-soudre peut tre sujette une propagation importante des erreurs numriques.

Ces notions de conditionnement dun problme et de stabilit numriquedune mthode de rsolution sont fondamentales en analyse numrique. Si unproblme est mal conditionn alors la solution exacte du problmetronqu ouarrondi tdigits pourra tre trs dirente de la solution exacte du problmeinitial. Aucune methode ne pourra rien; il faudra essayer de donner une autreformulation au problme.

1

1 S. El Bernoussi, S. El Hajji et A. Sayah

10


12/71


13/71

54321

3.75

2.5

1.25

0

-1.25

-2.5

x

y

x

y

Figure 2.1: f(x) =x

ex

ex

2

On supposera donc dsormais avoir trouv un intervalle [a; b]o fadmetune unique racine simple et on supposera que f est dnie, continue, etautant de fois continument drivable que ncessaire.

Nous allons prsent dnir la notion dalgorithme.Dnition : Nous appellerons algoritnme toute mthode de rsolution

dun problme donn.Pour tout problme, nous avons des donnes et des rsultats. Les donnes

sont appeles paramtres dentre (input) et les rsultats paramtres de sortie(output). Ils constituent linterface de lalgorithme (ou encore la partie visiblede lalgorithme).

Dans ce chapitre, nous dsignerons par fpngune suite de nombres rels .Il y a plusieurs faons de gnrer les termes dune suite. En analyse

numrique, on construit les suites laide dun procd itratif appel algo-rithme.

Les algorithmes classiques que nous allons tudier sont les suivants:i) Mthode de la bissectionii) Mthode de Newton-Raphson

iii) Mthode de la scanteiv) Mthode du point xe.

Le but de ce chapitre est de trouver des approximations de la solution delquation (1) avec une prcision donne et un nombre ditrations maximum.

12


14/71

An de comparer ces direntes mthodes, nous allons introduire la no-

tion dordre de convergence.

2.2 Mthode de la bissection.

Considrons une fonction f(x) quelconque, continue et cherchons p tel quef(p) = 0:

Nous supposons quon a localis par tatonnement un intervalle[a; b]danslequel la fonction change de signe (c..d. f(a) f(b) 0) on posec = a+b2 ;sif(a) f(c) 0on remplacebparcsinon on remplaceaparc;et on continuecette operation jusqu ce quon trouve p avec la prcision demande.

Algorithme de bissection (ou de dichotomie)But : Donner une fonction continue f(x) et un intervalle [a; b] pour

lequel f(a) et f(b) sont de signes contraires, trouver une approximationde la solution de f(x) = 0 dans cet intervalle; en construisant une suitedintervalles([an; bn])ncontenant cette racine et tets que an oubnest le mi-lieu de lintervalle[an1; bn1].

Entres : a; bles extrmits de lintervalle la prcision dsireN0le nombre maximal ditrations

Sortie: la valeur approche de la solution de f(p) = 0Etape 0: Sif(a) = 0imprimer la solution est a, aller ltape 9

Sif(b) = 0imprimer la solution estb, aller ltape 9Etape 1:

sif(b) f(a)>0alors imprimer (il ny a pas de changement de signe)aller ltape 9

Etape 2: poserN= 1Etape 3:

Tant queN

N0;faire les tapes 4 7

Etape4: poser p = a+b2Etape 5:Sif(p) = 0ou ba

2

Alors imprimerpaller ltape 9

Etape 6: poserN=N+ 1

13


15/71

Etape 7: Sif(a) f(p)>0

alors posera =psinon poserb = pEtape 8: Imprimer aprsN0 itrations lapproximation obtenue est p et

lerreur maximale est ba2

Etape 9: Fin

2.3 Mthode de Newton-Raphson:

Le principe consiste construire une suite (xn)n; telle que xn+1 soitlintersection de la tangente la courbe de fau point (x

n; f(x

n))avec laxe

horizontal.

2.521.510.5

0.75

0.5

0.25

0

-0.25

-0.5

x

y

x

y

Figure 2.2: Mthode de Newton pour f(x) = log(x); x0 = 2:

On a: A= (x0; f(x0)); B= (x1; 0) 2 axe(Ox)

Aet B2 D: y = ax+bdonc

f(x0) =ax0+b0 =ax1+b ) ( a=f

0(x0)

x1= x0 f(x0)f0(x0)

Algorithme de Newton-Raphson.But: Trouver une solution de f(x) = 0

14


16/71

Entres: une approximation initiale p0

"(la prcision dsire)N0(le nombre maximum ditrations)Sortie: valeur approche de p ou un message dchec

Etape1 : N= 1Etape 2: Tant queN N0;faire les tapes 3 6.Etape 3: Poser p=p0 f(p0)f0(p0)Etape 4: Sij p p0j "alors imprimer p

aller ltape 8.Etape 5: Poser N=N+ 1:Etape 6: Poser p0= p:Etape 7: Imprimer la mthode a chou aprs N itrations.Etape 8: Fin.

2.4 Mthode de la scante

La mthode de Newton-Raphson suppose le calcul de f0(p) chaque tape.Il se peut quon ne dispose pas dun programme permettant de calculer sys-tmatiquement f0 .

Lalgorithme suivant peut tre considr comme une approximation de la

mthode de Newton.Le principe consiste construire une suite (xn)n laide de la formule

obtenue en remplaant dans la mthode de Newton f0(pn)par f(pn)f(pn1)

pnpn1 :Ainsi au lieu dutiliser la tangente au pointpnnous allons utiliser la scantepassant par les points dabscissespnetpn1pour en dduirepn+1. Ce dernierest obtenu comme intersection de la scante passant par les points dabscisse

pnetpn1 et de laxe des abscisses.Lquation de la scante scrit :s(x) =f(pn) + (x pn) f(pn)f(pn1)pnpn1Sis(pn+1) = 0, on en dduit:

pn+1= pn f(pn) pn

pn1

f(pn)f(pn1)Algorithme de la scante:

But:Trouver une solution de f(x) = 0Entres: deux approximations initialesp0 etp1

15


17/71

21.510.50

6

4

2

0

-2

x

y

x

y

Figure 2.3: f(x) =x3

1

"(la prcision dsire)N0(le nombre maximum ditrations)

Sortie:la valeur approche dep ou un message dchecEtape 1: poserN= 1

q0= f(p0)q1= f(p1)

Etape 2: Tant que N N0+ 1;faire les tapes 3 6Etape 3: poser p = p1 q1 (p1p0)q1q0Etape 4: Sijp p1j "alors imprimer paller ltape 8Etape 5: Poser N=N+ 1Etape 6: Poser p0= p1

q0= q1p1 = pq1= f(p)

Etape 7: Imprimer la mthode a chou aprsN0 itrationsEtape 8: Fin.

2.5 Mthode du point xe

Nous pouvons observer que la mthode de Newton peut sinterprter commepn+1= g(pn)o

16


18/71

g(x) =x ( f(x)f0(x)

):Maintenant , si la fonction g(x)est continue et si

lalgorithme converge (c..d. pn!p);on tire de pn+1= g(pn)que p satisfaitlquationp = g(p); on dit que p est un point xe de g.On peut toujours transformer un problme du typef(x) = 0en un prob-

lme de la forme x =g(x)et ce dune innit de faons.Par exemplex2 2 = 0oux = 2=xoux = x2 +x 2oux = (x2 2) +xIl faut toutefois noter que ce type de transformations introduisent des

solutions parasites.

Par exemple : rsoudre 1=x= a ou encore x = 2x ax2On voit que0est racine de la deuxime quation mais pas de la premire.

Algorithme du point xeBut: trouver une solution de g(x) =xEntres: une approximation initialep0

"(la prcision dsire)

N0le nombre maximale ditrationsSortie:valeur approche de p ou un message dchecEtape 1: poserN= 1Etape 2: Tant que N N0;faire les tapes 3 6

Etape 3: poser p = g(p0)Etape 4: Sij p p0j "

alors imprimer paller ltape 8

Etape 5: poser n =n+ 1Etape 6: poser p0= p

Etape 7: Imprimer (la mthode a chou aprrs N0 itrations)Etape 8 : Fin.

17


19/71

2.6 Convergence et ordre de convergence.

Dnition: SoitDune partie de Ret Fune application deD dansD:Ondit que la fonction Fest contractante si

8x; y2 D ; 9k2 [0; 1[ tel quej F(x) F(y) j k j x yj :

kest le cocient de contraction ou de Lipschitz de F:Thorme: Considrons le segment S = [p0 a; p0+a] D;si F est

contractante sur S et sij F(p0) p0j (1 k) a; alors litration pn+1 =F(pn)de point initialp0 ;converge vers lunique point xe p 2 SdeF:

Thorme: Convergence locale.Si F est direntiable au voisinage dun point xe p et sij F0(p)j< 1

alors :9Vvoisinage de p tels que p02 V etpn+1= F(pn)converge vers p:

18


20/71

2.6.1 Interprtation graphique.

0.750.6250.50.375

0.75

0.625

0.5

0.375

x

y

x

y

Figure 2.4: F(x) = x3 + 54

x; jF0(x)j 1;litration diverge.

Remarque: Un point xe rpulsif pour une mthode devient attractifpour une autre.

19


21/71

2.6.2 Ordre de convergence.

La convergence de litration pn+1 = F(pn) vers le point xe peut sefaire plus ou moins vite.

Dnition : Considrons une suitefpng convergeant vers p et posonsen = pn p:

On dit dans le cas on enen1

oconverge, que la suitepnconverge linaire-ment versp ou encore que la mthode est du premier ordre.

Si on an en(en1)k

oconverge, alors la convergence est dite dordre k:Exemple :La mthode de Newton pour rsoudre lquation f(x) = 0 est une mth-

ode de type point xe avec F(x) = x

f(x)

f0

(x)

: Si x est racine simple def(x) = 0;alorsf0(x) 6= 0 et il existe un voisinage V dextel que pour tout

p02 V; la suite (pn)nconverge versxet lordre de convergence est 2.(en eet F0(x) = 1 (f0(x))2f(x)f00(x)(f0(x))2 ) F0(x) = 0: Ainsi daprs

le thorme prcdent la mthode de Newton converge. Pour dterminerlordre de convergence on utilise la formule de Tylors enx: F(x) =F(x) +F0(x)(x x) +F00(x) (xx)2

2 ):

2.7 Exercices

20


22/71

Srief(x) = 0

Exercices 1Rsoudre laide de la mthode de bisectiontanxx= 0dans lintervalle

[4;4:7].

Exercice 2On considre lquation(1)ex 4x= 01) Dterminer le nombre et la position approximative des racines de (1)

situes dans .x 02) Utiliser lalgorithme de bissection pour dterminer la plus petite de

ces racines " prs.(par exemple 107

)3) Sans faire ditrations, dterminer combien vous devriez en faire pourcalculer la plus grande racine laide de la bissection avec une prcision de108, si lintervalle de dpart est [2; 2; 5]

Exercice 3crire un algorithme pour calculer par la mthode de Newton la racine

K-ime dun nombre.

Quelle est la valeur de s=q

2 +p

2 +p

2 +:::::?Suggestion: crire .pn+1=G(pn),p0=0 Quel est lordre de convergence ?

Exercice 4crire 3 mthodes itratives pour la rsolution de x3x1 =0 et vrier

exprimentalement leur convergence avec x0 = 1; 5. Trouver 106prs laracine comprise entre 1 et 2. Connaissant la valeur de cette racine, calculerlordre de convergence de vos 3 mthodes. Ce rsultat coincide-t-il aveclexprience?

Exercice 5Rsoudre x2-1=0 en utilisant la mthode de la scante avec x0 =3et

x1 = 5=3. Quarrivera-t-il si on choisit et x0 = 5=3et x1= 3? Expliquez.1

1 S. El Bernoussi, S. El Hajji et A. Sayah

21


23/71

Chapitre 3

Algbre linaire

3.1 Introduction

Un sytme linaire scrit sous la forme :

(1) Ax= b

oA est une matrice nxn coecients rels, b 2 Rn et x 2 Rn:La rsolution de grands systmes linaires (et non linaires) est pratique

courante de nos jours. Elle apparait dans tous les domaines o lon sintresse la rsolution numrique dquations aux drives partielles.

Il existe plusieurs packages (linpack, eispack, ..), logiciels (Maple et Mat-lab) et programmes (http://www.netlib.com, numerical recipes, NAG, IMSL,...) de base pour le rsoudre.

Le choix de la mthode dpend fortement du type (forme) de la matrice.Les mthodes de rsolution sont de deux types :

Les mthodes directes : Une mthode est dite directe si elle permet dobtenirla solution en un nombre ni doprations.

Les mthodes itratives : Une mthode est dite itrative si elle permet deconstruire une suite (xn)nqui converge vers la solution.

Dans ce chapitre nous allons :

1. Rapeler des notions et notations de base relatives aux systmes linaireset aux matrices

22


24/71

2. Etudier une mthode directe : la mthode de Gauss.

3. Etudier la dcomposition (factorisation)LU:

4. Etudier des applications : Inverse de matrices,...

3.2 Rappels sur les systmes linaires

Un systme denquations linaires ninconnues peut toujours scrire sousla forme :

(1) Ax= b

oA est une matrice(aij)et x et b sont des vecteurs colonnes de dimensionn.

Si la matrice A est inversible alors le systme linaire (1) admet uneunique solutionx = A1bo A1 est la matrice inverse deA:

Ainsi thoriquement le problme revient calculerA1?Mais en pratiquece calcul est dicile.

Il existe plusieurs mthodes classiques pour rsoudre (1) sans calculerA1:

Pour cela on va considerer le cas simple suivant :

(1)

x+ 2y= 52x+y= 4

i) La mthode de Cramer consiste calculer la solution en calculant desdterminants.

On a: x=

5 24 1

1 22 1

= 33 = 1et y =

1 52 4

1 22 1

= 63 = 2

ii) La mthode de substitution (ou dlimination) consiste transformerle systme(1):

(1)

x+ 2y= 52x+y= 4

)

x= 2y+ 52x+y = 4

)

x= 2y+ 52(2y+ 5) +y = 4

23


25/71

) x= 2y+ 5

3y= 6 ) x= 2y+ 5

y= 2 ) x= 1

y= 2Peut-on gnraliser ces mthodes pour un systme de n quations avecn 2 N?

Thoriquement OUI mais en pratique cela va ncessiter beaucoup de cal-culs et de techniques.

3.3 Mthode Gauss

La mthode de rsolution la plus tudie (et une des plus employes) sappellemthode dlimination de Gauss.

Lide de base de cette mthode consiste transformer le systme linaire(1)en un problme que lon sait rsoudre.

Si la matriceA = DavecD une matrice diagonale, alors on sait rsoudre(1):

Mais toute matrice nest pas diagonalisable.Si la matrice A = U (ou L) avec U (ou T) une matrice triangulaire

suprieure ( ou infrieure) alors on sait rsoudre(1):Problme : Comment tranformer une matrice en une matrice triangulaire

infrieure ou suprieure ?La mthode de substitution (dlimination) rpond cette question mais

elle nest pas automatique.

La mthode dlimination de Gauss a pour but de remplacer le sys-tme (1) par un systme triangulaire possdant la mme solution. Sonprincipe sapparente celui de la mthode de substitution (dlimination)mais (comme on le verra ci dessous), il est plus simple automatiser.

Regardons son fonctionnement sur lexemple suivant casn = 3:On pose A = (aij)i;j=1;3 X = (xi)i=1;3et b = (bi)i=1;3 de telle sorte que

AX=b scrit sous la forme :8>>:

x+y+ 3t= 42x+y z+t= 1

3x y z+ 2t= 3x+ 2y+ 3z t= 4

qui scrit encore:0BB@

1 1 0 32 1 1 13 1 1 2

1 2 3 1

1CCA0BB@

xyzt

1CCA =

0BB@

41

34

1CCA

Nous appliquons lalgorithme notre exemple en travaillant sur la matriceaugmente.

Nous obtenons

266664A b

1 1 0 3 : 42 1 1 1 : 13 1 1 2 : 3

1 2 3 1 : 4

377775

27


29/71

26641 1 0 3 : 40 1 1 5 : 70 4 1 7 : 150 3 3 2 : 8

37752664

1 1 0 3 : 40 1 1 5 : 70 0 3 13 : 130 0 0 13 : 13

3775

Que lon peut crire sous la forme :

8>>>:

x+y+ 3t= 4y z 5t= 7

3z+ 13t= 1313t= 13

,

Notons que ltape j = 3 nous donneraitl43= 0:Nous avons maintenant un systme triangulaire rsoudre.

Partie 2 : Remonte triangulaireEntre A; bavec A matrice triangulaire suprieureSortie x solution du sytme Ax = b

tape 1: xn= bnann tape 2: Pouri =n 1; n 2;:::; 1faire:

xi= 1

aii(bi

nXj=i+1

aijxj )

En appliquant cet algorithme notre exemple, nous obtenonsx= (1; 2; 0; 1).

Remarque:

1. Dans la pratique le test (3) de lalgorithme dlimination de Gauss neconduit pas larrt. En fait, si le pivot est nul, on cherche, dansla mme colonne, un lment dindice plus grand non nul, puis onchange les lignes correspondantes. Si ceci est impossible, le systmeest singulier.

28


30/71

2. On est parfois amen, pour des raisons de stabilit numrique, ef-

fectuer des changes de lignes mme si le test (3) est ngatif (cest dire que le pivot est non nul). Ceci conduit des stratgies dites depivot que nous ntudierons pas ici.

Exemple : Rsolution du systme suivant :8nX

j=1;j6=ijaijj

est vrie.

Remarque : Si la matrice est diagonale strictement dominante alors elleest inversible.

3.4.1 Appplications de la FactorisationLU

Si lon doit rsoudre souvent un systme o seul le membre de droite changeou son veut calculer linverse dune matrice, il y a intrt eectuer la r-duction la forme triangulaire une fois pour toutes.

En eet, si A = LU on peut rsoudre: Ax = b en rsolvant Lz = b etUx=z. On a :

(1)Ax =b , (2)Lz= b(3)U x= z

Dans ce casAx = LU x=L(Ux) =Lz = b .Les systmes(2) et (3) tant triangulaires, la rsolution ne ncessite que

lexcution dune remonte et dune descente triangulaire.

Exemple :

A=LU=

0BB@

1 0 0 02 1 0 03 4 1 0

1

3 0 1

1CCA

0BB@

1 1 0 30 1 1 50 0 3 130 0 0

13

1CCA

;on rsoud le sys-

tme Ax =

0BB@

41

34

1CCA :

32


34/71

Lz= b ) 8>>>:z1= 4

2z1+z2 = 13z1+ 4z2+z3= 3z1 3z2+z4= 4

) z = 0BB@4

71313

1CCA :

Ux= z)

8>>>:

13x4= 133x3+ 13x4= 13

x2 x3 5x4= 7x1+x2+ 3x4 = 4

) x=

0BB@

1201

1CCA :

3.5 Mesure des erreurs

Lutilisation dun calculateur pour implanter les algorithmes tudis conduirainvitablement des erreurs. Pour mesurer celles-ci, nous devons mesurer ladistance entre le vecteur reprsentant la solution exacte x = (x1;:::;xn)et levecteur x = (x1;:::;xn) reprsentant la solution approche. Nous pouvons,pour ce faire, utiliser la "longueur" usuelle de Rn i.e.:

kxk2 = fnX1

x2i g1

2

pourtant, dans la pratique on lui prfre souvent la longueur

kxk1

= max1in j

xij

Par exemple si x = (1; 7; 2; 4)alorskxk1= 7.

Exemple :

Six = (1; 1; 1; 1)alorskxk1= 1si x= (1:01; 1:1; 1; 1), on a

kx xk1= 0:1Considrons alors le systme

0BB@10 7 8 7

7 8 6 58 6 10 97 5 9 10

1CCA0BB@x1

x2x3x4

1CCA = 0BB@32

233331

1CCAdont la solution exacte est x = (1; 1; 1; 1).

33


35/71

Si dans le membre de droite nous remplaonsb par:

b= (32:06;22:87;33:07;30:89)

nons obtenonsx= (9:19; 12:59; 4:49; 1:09)

Cest--dire quune erreur relative de lordre de:

kb bk1kbk1 = 3 10

1

surb a entran une erreur relative de lordre de

kx xk1kxk1 = 13:52

sur la solution.Nous devons donc souponner que lapplication de larithmtique nie

la rsolution dun tel systme serait dsastreuse. Ltude de cette questiondpasse le cadre de ce programme.

3.6 Exercices

34


36/71

SrieAx= b

Exercice I -1) On considre le systme linaire :

(1)

1 5

1:0001 5

xy

=

6

6:0005

Dterminer la solution Xde ce systme.2) Dans le systme prcdent, on remplace 6:0005 par 6, dterminer la

solution X de ce nouveau systme note (2):3) Calculer les erreurs relatives sur les donnes et sur les rsultats.

4) Conclusion.Exercice II-

Rsoudre le systme linaire (1):

(1)

8

Documents

numerique2_2