[PDF] MT09-Analyse numérique élémentaire

View - Download MT09-Analyse numérique élémentaire

Previous PDF

Next PDF

MT09-Analyse numérique élémentaireChapitre 3 : Résolution des problèmes de moindres carrés

Équipe de Mathématiques AppliquéesUTCJuin 20075

SommaireConceptsExemplesExercicesDocumentssuivantI2Chapitre IIIRésolution des problèmes de moindres carrésIII.1 Formulation générale des problèmes de moindres carrés. . . . . . . . . . . . .3III.2 Approche algébrique du problème de moindres carrés. . . . . . . . . . . . . . .10III.3 Résolution des problèmes de moindres carrés par "QR".. . . . . . . . . . . . . .17Documents du chapitre III. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24Exercices du chapitre III. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31

SommaireConceptsExemplesExercicesDocumentschapitreNsection suivanteI3III.1 Formulation générale des problèmes de moindrescarrésIII.1.1 Un exemple : un problème de lissage.. . . . . . . . . . . . . . . . . . .4III.1.2 Formulation matricielle. . . . . . . . . . . . . . . . . . . . . . . . . . .6III.1.3 Les équations normales. . . . . . . . . . . . . . . . . . . . . . . . . . .8

SommaireConceptsExemplesExercicesDocumentssectionNsuivantI4IIIII.1.1 Un exemple : un problème de lissage.Exercices :Exercice III.1Si on se donne une famille de points du plan(ti;bi)1im(lestiétant distincts) alors il existe

un unique polynômeP(t)de degré inférieur ou égal àm1tel que

P(ti) =bi; i= 1;:::;m;

qui est le polynôme d"interpolation des points(ti;bi). Si le nombre de pointsmest trop grand,

ou si les ordonnées sont bruitées, on préfère en général chercher une fonctionf(t)qui, dans unettii

f(t)bFIG. III.1.1: un problème de lissageclasse donnée (polynômes, fractions rationnelles, polynômes trigonométriques, exponentielles

SommaireConceptsExemplesExercicesDocumentssectionNsuivantIJJ5Un exemple : un problème

de lissage....), approche "au mieux" les points(ti;bi), on parle alors d"approximation, de lissage ou bien de

régression(voir la figureIII.1.1).

Soit donc une famille de fonctions

f

1(t);f2(t);:::;fn(t); nm;

linéairement indépendantes. Etant donnénnombres réelsx1;x2;:::;xnon peut introduire le nombreE(x)

E(x) =mX

i=1[f(ti)bi]2; avecf(t) =Pn k=1xkfk(t). La quantitéE(x)représente la somme des erreurs quadratiques entre les valeurs données et celles prises parfaux pointsti. Le problème d"approximation se formule alors de la façon suivante :Trouverbx2IRn, tel queE(bx)E(x);8x2IRn.

Par exemple si l"on désire faire de la régression polynômiale, c"est-à-dire prendre pourf(t)un

polynôme de degrén1, on a f k(t) =tk1; k= 1;:::;n; f(t) =x1+x2t+:::+xntn1: L"écriture inhabituelle du polynôme avecxkcomme coefficients permet de mettre en évidence que les inconnues du problème de moindres carrés sont ces coefficients.

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNsuivantI6IIIII.1.2 Formulation matricielleExercices :Exercice III.2Cours :LissageOn suppose que l"on a à résoudre un système linéaireAx=b(A2 Mmn), avec un second

membrebnon nul et on suppose que le nombre d"équations est supérieur strictement au nombre d"inconnues (m > n). Dans la plupart des cas, ce système n"a pas de solution. On cherche alors une approximation de la solution qui réduise la différenceAxb. Un des choix possible est de minimiser la norme euclidienne de cette différence. Dans tout ce chapitre, nous n"utiliserons

que la norme euclidienne.Définition III.1.1.SoitA2Mmn(IR)etb2IRmdonnés. On appelle problème de moindres carrés

le problème minx2IRnkAxbk2

2:(III.1.1)

On noterabxla solution de ce problème. On montrera dans la suite qu"elle existe, et qu"elle est unique sous l"hypothèse fondamentale suivante : Les colonnes de A sont linéairement indépendantes:(III.1.2) ou, de façon équivalente rangA=n: Un cas particulier est le casm=netAinversible, alorsbxest la solution unique deAx=b, mais ce n"est pas ce cas particulier qui nous intéresse dans ce chapitre.

matricielleUn autre exemple, pour le problème de lissage, est introduit dans le paragraphe référencé.

Il n"est pas possible en général de faire passer une fonctionf(t)dépendant deninconnues (par

exemple un polynôme de degrén1) parmpoints (m > n). Il n"existe donc sans doute pas de x2IRnqui annule les quantités n X k=1x kfk(ti)bi;1im:

Cette expression s"écrit bienAxboù

a ij=fj(ti);1im;1jn; et l"on a bien à minimiser

E(x) =mX

i=1" nX k=1x kfk(ti)bi# 2

Cette fois-ci le minimum ne sera pas nul.

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionN8IIIII.1.3 Les équations normalesExercices :Exercice III.3Documents :Document III.2Nous ferons plus tard une résolution purement algébrique du problème des moindres carrés.

Cependant nous allons en donner une approche analytique qui permet de voir ce problème sous un angle différent. Tout d"abord, explicitons la fonction à minimiser. On a

E(x) =kAxbk2

2= (Axb)T(Axb) =xTATAxbTAxxTATb+kbk22

=xTATAx2(ATb)Tx+kbk22: Le problème de moindres carrés peut donc se reformuler en min x2IRnJ(x) =xTGx2hTx;

oùG=ATAest symétrique eth=ATbest un vecteur donné.Définition III.1.2.On appellefonction quadratiqueune fonctionJ: IRn!IR, de la forme

J(x) =xTGx2hTx;

oùGest une matricennsymétrique ethest un vecteur donné deIRn. Rappelons que siJ: IR!IR, continûment dérivable, admet un minimumbx2IR, alors J

0(bx) = 0. De même soitJ: IRn!IRcontinûment dérivable, alors

J(bx)J(x)8x2IRn) rJ(bx) = 0;ropérateur gradient: SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNJJ9Les équations normalesIci le calcul du gradient deJdonne (voir le document référencé) rJ(x) = 2(Gxh) et la solutionbxdu problème de moindre carrés vérifie donc nécessairement

Gbx=h;soit

A

TAbx=ATb:

Ces relations sont appeléeséquations normalesdu problème, ce sont des conditions nécessaires

pour quebxsoit minimum, on montre de plus que ces conditions sont suffisantes d"où le théorème.Théorème III.1.1.SoitA2Mmn(IR)etb2IRmdonnés, si l"on suppose que la matriceAest de

rangn, le problème de moindres carrésminx2IRnkAxbk2

2, admet une solution uniquebxdonnée

par A

TAbx=ATb:(III.1.3)Démonstration

SommaireConceptsExemplesExercicesDocumentsJsection précédentechapitreNsection suivanteI10III.2 Approche algébrique du problème de moindrescarrésIII.2.1 Idée intuitive de l"approche algébrique. . . . . . . . . . . . . . . . . .11III.2.2 Espaces orthogonaux - Rappels. . . . . . . . . . . . . . . . . . . . . . .12III.2.3 Problèmes de projection. . . . . . . . . . . . . . . . . . . . . . . . . . .14III.2.4 Utilisation de l"orthogonalisation de Schmidt pour résoudre les équa-

tions normales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16

SommaireConceptsExemplesExercicesDocumentssectionNsuivantI11III.2.1 Idée intuitive de l"approche algébrique

Soit Im(A) =fy2IRmj 9x2IRn; y=Axg. Alors le problème de moindres carrés min x2IRnkAxbk2 2; signifie que l"on cherche dans l"image de A l"élément le plus "proche" deb. Il se formule donc comme un problème de projection orthogonale debsur le sous-espace vectoriel Im(A)(voir la

figureIII.2.2). Si on appellebxla solution de ce problème, on s"attend donc à ce que lerésidu

r=bAbxsoit orthogonal à Im(A)(ceci sera évidemment revu dans la suite de ce cours).S=Im(A)b ^r

bFIG. III.2.2: projection debsur Im(A)Quel est le lien avec les équations normales? Pour le retrouver nous allons rappeler quelques

résultats sur les espaces euclidiens.

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNsuivantI12IIIII.2.2 Espaces orthogonaux - RappelsExercices :Exercice III.4Exercice III.5Documents :Document III.3Définition III.2.1.On rappelle la définition du produit scalaire usuel surIRn:

x;y2IRn;hx;yi=xTy=yTx:

Cette définition généralise le produit scalaire usuel que vous connaissez dansIR2ouIR3.Définition III.2.2.SoitSun sous-espace vectoriel deIRn, on appelleorthogonaldeSle sous

espace vectoriel deIRnnotéS?défini par : x2S?, 8y2S;hx;yi= 0:Proposition III.2.3.SoitSun sous-espace vectoriel deIRn,S?l" orthogonal deSalors

S\S?=f0g;IRn=SS?:

Démonstration-

x2S\S?) hx;xi= 0)nX i=1x

2i= 0)x= 0:

Pour montrer la somme directe, on utilise l"orthogonalisation de Schmidt (voir le document référencé) pour montrer que tout sous-espace vectorielSadmet une base orthogonaleB. On orthogonaux -

Rappelsrappelle qu"une famille libre, par exempleB, deEpeut être complétée par une familleCtelle

queB [ Csoit une base deE(théorème de la base incomplète). On continue alors le processus d"orthogonalisation de Schmidt surCet on obtient ainsi une base orthogonale de la formeB[B0.

Alors il est clair, par construction, queB0engendre un sous espace vectoriel qui estS?.Corollaire III.2.1.Soity2IRnalors il existe un uniqueby2Stel que

yby2S?; le vecteurbyétant appeléprojection orthogonaledeysurS.

Démonstration- D"après le théorème précédent, tout vecteurys"écrit de manière unique sous

la forme :y=by+z, oùby2Setz2S?.Proposition III.2.4.SoitA2 Mmn (ImA)?=Ker(AT):

Démonstration-

x2Im(A)?,xTy= 0;8y2Im(A); ,xT(Az) = 0;8z2IRn; ,(ATx)Tz= 0;8z2IRn; ,ATx= 0: Pour la démonstration du dernier point voir l"exerciceIII.4

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNsuivantI14IIIII.2.3 Problèmes de projectionProposition III.2.5.Etant donnésSun sous-espace vectoriel deEety2E, le problème

min z2Skzyk2 admet pour solution uniqueby2Sprojection orthogonale deysurS. Démonstration- Soitzun élément quelconque deS, alors kzyk22=kzby(yby)k22; =kzbyk22+kybyk222;hzby;ybyi; =kzbyk22+kybyk22; puisque(zby)2Set(yby)2S?. Alors kzyk22>kbyyk228z6=by

ce qui montre queminz2Skzyk2=kbyyk2.Corollaire III.2.2.SoitA2Mmn(IR)etb2IRmdonnés, le problème :

trouverbx2IRntel que kAbxbk2 kAxbk28x2IRn; est équivalent à : trouverbx2IRntel que : A

TAbx=ATb:

Démonstration-

On noterabbla projection orthogonale debsur ImA, on a donc par définition b b2ImA; bbb2(ImA)?: SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNsuivantIJJ15Problèmes de projection-On utilise la proposition précédente avecE= IRm;S=Im(A);y=b. kAbxbk2 kAxbk28x2IRn, kAbxbk2 kzbk28z2ImA,Abx=bb:-Montrons que

Abx=bb,ATAbx=ATbb:

l"implication de gauche à droite est évidente. montrons la réciproque : A

TAbx=ATbb,AT(Abxbb) = 0,Abxbb2KerAT= (ImA)?

or bb2ImA, doncAbxbb2ImA, donc

Abxbb2ImA\(ImA)?)Abxbb= 0)Abx=bb:

Ce qui termine de montrer l"équivalence.-Montrons maintenant que A

TAbx=ATbb,ATAbx=ATb:

Par définition de

bb, on abbb2(ImA)?=KerAT, doncAT(bbb) = 0doncATb=ATbb. Ce qui termine de démontrer cette dernière équivalence. On retrouve donc par un raisonnement faisant intervenir les projections que les équations

normales sont des conditions nécessaires et suffisantes d"optimalité pour le problème de mini-

misation.

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionN16III.2.4 Utilisation de l"orthogonalisation de Schmidt pour résoudre les

équations normalesExercices :Exercice III.7Exercice III.6A l"aide de l"orthogonalisation de Schmidt, on calcule une base orthogonalefE1;E2;:::;Eng

de Im(A), on obtient (démontré en exercice)

A=ET;oùE= [E1E2:::En];

E2 Mmnest une matrice rectangulaire etT2 Mnnest une matrice triangulaire supérieure inversible. Puisque les colonnes deEsont des vecteurs orthonormés, on aETE=I, montrer ce résultat en exercice.

On obtientATA=TTETET=TTT,ATb=TTETb.

En reprenant les équations normales, on a donc : A

TA^x=ATb,TTT^x=TTETb,T^x=ETb:

En effet la matriceTdonc la matriceTTest inversible, on peut donc simplifier la deuxième

équation, il n"était évidemment pas possible de simplifier la première équation parATpuisque

la matriceATn"est pas carrée donc pas inversible.

Il s"avère que le systèmeT^x=ETbest mieux conditionné que celui donné par les équations

normales. Cependant l"orthogonalisation de Schmidt est très sujette à l"accumulation des er-

reurs d"arrondi. C"est pourquoi on lui préfère une factorisation deAdu même type, basée cette

fois sur la transformation deHouseholder, qui fait l"objet du paragraphe suivant.

SommaireConceptsExemplesExercicesDocumentsJsection précédentechapitreNsection suivanteI17III.3 Résolution des problèmes de moindres carrés par"QR".III.3.1 La transformation deHouseholder. . . . . . . . . . . . . . . . . . . . .18III.3.2 La factorisation "QR". . . . . . . . . . . . . . . . . . . . . . . . . . . . .20III.3.3 Application à la résolution du problème de moindres carrés. . . . . .22

SommaireConceptsExemplesExercicesDocumentssectionNsuivantI18IIIII.3.1 La transformation deHouseholder

Dans l"espace euclidienIRn, les transformations orthogonales (c"est à dire les applications

linéaires représentées par des matrices orthogonales) conservent la norme euclidiennek:k2. En

effet siHest orthogonale on aHT=H1et donc kHxk22= (Hx)THx=xTHTHx=xTx=kxk22: Le but de ce paragraphe est d"introduire une transformation orthogonale particulière : la trans-

formation deHouseholder, qui est une symétrie plane.Définition III.3.1.On appelletransformation de Householder, une transformation dont la ma-

trice est de la forme

H=I2yyT;

oùy2IRnetkyk2= 1. Il est clair queHest symétrique et on vérifie sans difficulté queHest orthogonale : HH

T=HH= (I2yyT)(I2yyT) =I2yyT2yyT+ 4yyT=I:Remarque III.3.2.La transformation de Householder conserve donc la norme. Par d"ailleurs

on a :

Hy=y2yyTy=y

et sizest orthogonal àyalors

Hz=z2yyTz=z

ce qui montre queHcorrespond à une symétrie par rapport au "plan" perpendiculaire ày.Théorème III.3.3.Soitx2IRn, aveckxk2= 1etx6=e= ( 1 0:::0 )T. Alors il existe une

transformation de HouseholderHtelle queHx=e: SommaireConceptsExemplesExercicesDocumentssectionNsuivantIJJ19La transfor- mation de HouseholderDémonstration- Posonsy=(xe)avec= (kxek2)1, alors la matrice

H=I2yyTrépond à la question. En effet

Hx= [I22(xe)(xe)T]x=x22(xe)Tx(xe):

En effet(xe)Txest un scalaire, on peut donc commuter. On a de plus2=kxek22= (xe)T(xe) =kxk222eTx+ 1 = 2(1eTx) et(xe)Tx= 1eTx, d"où22(xe)Tx= 1:

Ce qui donne :Hx=x(xe) =e:

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNsuivantI20IIIII.3.2 La factorisation "QR"Exercices :Exercice III.8Définition III.3.1.SoitQune matrice carrée, on dit queQest orthogonale si :

Q T=Q1,QTQ=I:Théorème III.3.4.SoitA2 Mmn(IR)avecmn, alors il existe une matrice orthogonale Q2 Mmm(IR)et une matrice triangulaire supérieureeR2 Mnn(IR)telles que

A=QeR0

:(III.3.1)DémonstrationOn noteR=eR 0 On peut remarquer que la formule (III.3.1) correspond à une orthogonalisation des colonnes deA. En effet, lajèmecolonne deA, soitAj, est donnée par A j=QRj=jX i=1r ijQi; factorisation "QR"ceci compte tenu de la structure deR. Ceci signifie que8k= 1:::n, les colonnes[Qj]j=1:::k (qui constituent une famille orthonormée) et[Aj]j=1:::kengendrent le même sous-espace. La factorisationQRest donc une façon d"orthogonaliser une famille de vecteurs, au même titre que l"orthogonalisation de Schmidt. En fait on utilise toujours la factorisationQRcar elle est moins sujette aux erreurs d"arrondi que l"orthogonalisation de Schmidt.

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionN22IIIII.3.3 Application à la résolution du problème de moindres carrésExercices :Exercice III.9Exercice III.10On part donc de la factorisationQRprécédente, ce qui permet d"écrireAsous la forme

A=QeR 0 où eR2 Mnn(IR)est triangulaire supérieure. Notons que pour tout vecteurydeIRmon a kQTyk22=kyk22; puisqueQT, commeQ, est orthogonale. On a donc, en particulier : kAxbk22=kQT(Axb)k22=kQTAxQTbk22:

Définissonsc2IRnetd2IRmnpar

Q Tb=c d Alors Q

TAxQTb=eR

0 xQTb=eRxc d et donc kAxbk22=keRxck22+kdk22: SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNJJ23Application à la résolution du problème de moindres carrésLe vecteurbxminimisant la norme dekAxbk2est donné par e

Rbx=c;(III.3.2)

puisquekdk22est une constante qui ne joue aucun rôle dans la minimisation. Le vecteurbxest unique si eRest inversible, ce qui est le cas si rang(A) =n. Remarquons que la factorisationQRest présente dans tous les logiciels d"analyse numé- rique, comme par exemple MATLAB ou SCILAB.

SommaireConceptsExemplesExercicesDocumentsJsection précédentechapitreNsection suivanteI24Documents du chapitre IIIIII.1 Démonstration du théorème III.1.1. . . . . . . . . . . . . . . . . . . .25III.2 Le gradient d"une forme quadratique. . . . . . . . . . . . . . . . . . .26III.3 L"orthogonalisation de Schmidt. . . . . . . . . . . . . . . . . . . . . . .27III.4 Démonstration du théorème III.3.4. . . . . . . . . . . . . . . . . . . .29

SommaireConceptsExemplesExercicesDocumentssectionNsuivantI25Document III.1Démonstration du théorème III.1.1

On remarque tout d"abord que siAest de rangn, alorsG=ATAest définie positive en effet : x

TGx=kAxk2

208x2IRn;

d"autre part puisque le rang deAvautn, alors la dimension de KerAest nulle donc x

TGx= 0, kAxk2

2= 0,Ax= 0,x= 0:

La matriceGétant définie positive, elle est inversible, donc il existe une unique solutionbx vérifiantATAbx=ATb,Gbx=h.

Montrons maintenant que

8x2IRn;x6=bx)J(x)> J(bx):

Posonsy=xbx, on a doncy6= 0.

J(bx+y) = (bx+y)TG(bx+y)2hT(bx+y);

=bxTGbx+yTGy+ 2bxTGy2hTy2hTbx; =bxTGbx+yTGy+ 2(Gbxh)Ty2hTbx; =yTGy+bxTGbx2hTbx; puisqueGbx=h. d"où

J(bx+y) =J(bx) +yTGy:

PuisqueGest une matrice définie positive, et quey6= 0, on ayTGy >0, et donc

J(bx+y)> J(bx);8y2IRn; y6= 0;

ce qui montre quebxréalise le minimum deJ.Retour au théorème III.1.1N

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNsuivantI26Document III.2Le gradient d"une forme quadratique

Soit la fonction quadratique

J(x) =xTGx2hTx;

oùGest une matrice symétrique. On veut calculer son gradient, soit rJ(x) =@J@x1;@J@x2;:::;@J@xn

Développons la fonctionJ

J(x) =nX

i=1x i(Gx)i2nX i=1h ixi: Alors @J@xk= (Gx)k+nX i=1x i@@xk(Gx)i2hk; et @@xk(Gx)i=@@xk0 nX j=1g ijxj1 A =gik=gki: Donc @J@xk= (Gx)k+nX i=1x igki2hk= (Gx)k+ (Gx)k2hk= 2(Gx)k2hk; d"où le résultat rJ(x) = 2(Gxh):retour au cours

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNsuivantI27IIDocument III.3L"orthogonalisation de SchmidtThéorème III.3.5 (Orthogonalisation deSchmidt).Dans tout espace euclidien de dimen-

sion finie il existe des bases orthonormées. Démonstration- Elle est constructive : on part d"une base quelconque deEsoitfB1;B2;:::;Bng

et on construit par récurrence une base orhonorméefE1;E2;:::;Eng. Première étape, on pose

E

1=B1kB1k2;

en effetkB1k26= 0car la famillefB1;B2;:::;Bngest libre.

Deuxième étape, on poseeE2=B2 hB2;E1iE1;

où on a notéh;ile produit scalaire dansE.

On a bienDeE2;E1E

=hB2 hB2;E1iE1;E1i=hB2;E1i hB2;E1ihE1;E1i= 0: k eE2k26= 0car sinonB2serait proportionnel àE1donc àB1ce qui est impossible car la famille fB1;B2;:::;Bngest libre.

On peut donc définir

E

2=eE2keE2k2:

Etapek: supposons que les vecteursfE1;E2;:::;Ek1gsont construits et orthogonaux deux

à deux. On définit alors

eEkpar e

Ek=Bkk1X

j=1hBk;EjiEj; III.3

L"orthogonalisation

de SchmidtVérifions que le vecteureEkest orthogonal aux vecteursE1;E2;:::;Ek1 D eEk;EiE B kk1X j=1hBk;EjiEj;Ei+ =hBk;Eii k1X j=1hBk;EjihEj;Eii; =hBk;Eii hBk;EiihEi;Eii; =hBk;Eii hBk;Eii= 0: k eEkk26= 0car sinonBkserait une combinaison linéaire deE1;E2;:::;Ek1, donc une combi- naison linéaire deB1;B2;:::;Bk1ce qui est impossible car la famillefB1;B2;:::;Bngest libre.

On peut donc définir

E k=eEkkeEkk2: Il faut remarquer que, à chaque étapekde la méthode, l"espace engendré parfE1;E2;:::;Ekg est le même que celui engendré parfB1;B2;:::;Bkg.retour au cours

SommaireConceptsExemplesExercicesDocumentsJprécédentsectionN29IIDocument III.4Démonstration du théorème III.3.4

Il est important de donner ici la démonstration complète de ce théorème, car elle estconstruc-

tive. C"est à dire qu"elle donne l"algorithme pour obtenir la factorisation. On va chercher à obte-

nir la matriceRcomme le résultat dentransformations orthogonales successivesU(k), soit eR 0 =A(n+1)=U(n)U(n1):::U(1)A les matricesU(k)étant construites à l"aide de transformations de Householder.

Si la première colonne deAs"écrit(10:::0)T, il n"y a rien à faire et on pose doncU(1)=I. Si-

non on sait qu"il existe une transformation de HouseholderH(1)qui transformeA1en(10:::0)T, avec1=kA1k2. En posantU(1)=H(1)on a donc : A (2)=U(1)A=0 B BB@ 1::: 0::: 0:::1 C CCA: Soitv(2)2IRm1le vecteur dont les éléments sont[a(2) i2]i=2:::m; il s"agit de la partie de la

deuxième colonne deA(2)qui commence à l"élément diagonal. On sait qu"il existe une trans-

formation de HouseholderH(2)qui transformev(2)en(20:::0)T2IRm1, avec2=kv(2)k2.

On définit alorsU(2)comme

U (2)=1 0 0H(2) III.4

Démonstration

du théorème

III.3.4et on obtient

A (3)=U(2)A(2)=0 B BBBB@ 1 ::: 02:::

0 0:::

0 0:::1

C

CCCCA:

On peut remarquer que, par définition deU(2), la première colonne deA(2)n"a pas été modifiée.

On peut aisément généraliser ce procédé : supposons que l"on a obtenuA(k)dont lesk1pre-

mières colonnes forment une matrice trapézoïdale supérieure (les éléments en dessous de la dia-

gonale sont nuls). Si on notev(k)2IRmk+1le vecteur dont les éléments sont[a(k) ik]i=k:::m, alors il existe aussi une transformation de HouseholderH(k)qui transformev(k)en[k0:::0]T2 IR mk+1, aveck=kv(k)k2. On définit alorsU(k)comme U (k)=Ik10 0H(k) et on obtientA(k+1)=U(k)A(k). On continue ce procédé jusqu"à obtenir une matriceA(n+1) A (n+1)=U(n)A(n)=U(n)U(n1):::U(1)A; qui, par construction, a la structure désirée. On a donc bien eR 0 =UA; avecU=U(n)U(n1):::U(1). On obtient la factorisationQRen remarquant que le produit de

matrices orthogonales reste une matrice orthogonale et en posantQ=UT.Retour au théorème III.3.4N

SommaireConceptsExemplesExercicesDocumentsJsection précédentechapitreN31Exercices du chapitre IIIIII.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32III.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33III.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34III.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35III.5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36III.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37III.7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38III.8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39III.9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40III.10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41

SommaireConceptsExemplesExercicesDocumentssectionNsuivantI32Exercice III.11.Ecrire le problème de la régression linéaire comme un problème de moindres carrés : plus

précisément on se donne une famille de points(ti;bi)1im(lestiétant distincts) et on

cherche à faire passer une droite le plus près possible de ces points.2.La question précédente conduit à une fonction de deux variables à minimiser. On admet

que ce minimum est donné en annulant les deux dérivées partielles. Donner le système linéaire de deux équations à deux inconnues ainsi obtenu.retour au coursSolution SommaireConceptsExemplesExercicesDocumentsJprécédentsectionNsuivantI33Exercice III.2

On cherche à approcher les données(ti;bi)1im(lestiétant distincts) à l"aide d"un polynôme

de degré inférieur ou égal àn1, on supposemn, on note p(t) =1+2t+:::+ntn1; et on cherche les coefficients1;2;:::;nqui minimisent

E(1;2;:::;n) =mX

i=1(p(ti)bi)2:quotesdbs_dbs23.pdfusesText_29

[PDF] approximation polynomiale moindres carrés

[PDF] approximation polynomiale taylor

[PDF] approximation des fonctions analyse numérique

[PDF] approximation linéaire d'une fonction

[PDF] approximation de pi par la méthode de monte carlo

[PDF] méthode de monte carlo algorithme

[PDF] méthode de la sécante

[PDF] méthode du point fixe

[PDF] methode de newton pdf

[PDF] méthode de héron dm

[PDF] developpement decimal

[PDF] développement décimal d un réel

[PDF] loi de poisson exemple

[PDF] approximation dans un calcul synonyme

[PDF] approximation linéaire excel