36
1 APPROXIMATION. MOINDRES CARRES

1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

Embed Size (px)

Citation preview

Page 1: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

1

APPROXIMATION.

MOINDRES CARRES

Page 2: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

2

 Approcher le graphe de la fonction sur [0,1] par une droite.

cos(πt)

0 0.2 0.4 0.6 0.8 1-1.5

-1

-0.5

0

0.5

1

1.5

cos t

Page 3: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

3

problème d’approximation avec contrainte.

Approcher » sur [0,1] le graphe de la fonction par

une parabole dont la tangente en 0 est égal à

πsin t

2

2

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

1

1.2

1.4

πsin t

2

Page 4: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

4

Ajuster un ensemble de points à l’aide d’une droite.

xk

yk

Page 5: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

5

I-Approximation dans un espace préhilbertien I-1 Théorème de la projection

Soit H espace vectoriel muni d’une norme et V une partie de H. Pour u donné dans H, on considère le problème (Q)

Trouver u* V

(Q)u u * Min u v / v V

Si u* existe et est unique, il est dit meilleure approximation de u dans V ou projection de u sur V.

Page 6: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

6

Dans la suite on se place dans le cas particulier où

H est un espace préhilbertien

V est le translaté d’un espace vectoriel de dimension finie

est la norme associée au produit scalaire

On verra que la résolution du problème (Q) peut se ramener alors à celle d’un système linéaire.

Page 7: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

7

Théorème 1 Soit V une partie de H ,translatée d’un sous-espace vectoriel V0 de dimension finie de H.

1°) , il existe un unique élément de V noté u* tel que

2°) L’élément est caractérisé par

u u * Min u v / v V

0u* V et u-u*,w 0 w V

u H

Soit H un espace préhilbertien sur muni du produit scalaire et de la norme associée

IR,

Page 8: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

8

Remarque: V translaté de V0 signifie:

v H tel que v+ 0 0V wV /w+ Vv

V n’est pas un espace vectoriel sauf si v=0 soit V=V0

u u* w

u

Illustration du théorème:

33

i ii 1

H IR x, y x y

V

V0

w

o

u*

Page 9: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

9

I-2 Applications

On note {vi}, i=1 à n une famille finie d’éléments de H.

On s’intéresse au problème de minimisation dans :

nIR

n n

n

i ii=1

Trouver * IR tel que q( *)=Min q( )/ IR

(P)où q( )= u- v

a) Problème sans contrainte

En posant V=espace engendré par la famille {vi}, i=1 à n, le problème (P) se met sous la forme du problème (Q)

avec n

*i i

i 1

u* v

Soit u un élément de H.

Page 10: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

10

Théorème 2 1°) 2°) est solution si et seulement s ’il vérifie le système linéaire où G est la matrice (n,n) et b le vecteur de définis respectivement par:

3°)

u H,le problème(P) admet au moins une solution α * .*

Gα* = b

ij i j i iG = v , v pour i, j = 1 à n b = u, v pour i = 1 à n

i i=1 à n

u H, * est unique si et seulement si la famille

v est libre.

nIR

Page 11: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

11

Démonstration:

Théorème 1 ! V avec où est solution de (P). n

*i i

i=1

u* u* = α v α *

i i 1 à nunique unique si et seulement si v est une famille libre u * α *

u* projection de u sur V V et u- ,v 0 v V u* u*

u ,v 0 v V n

*i i

i=1

α v

n*

j i i ji 1

u, v v , v j=1 à n

j u ,v 0 j=1 à n n

*i i

i=1

α v

Page 12: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

12

Remarques:a) La matrice G est dite matrice de GRAM.

b) G est symétrique par propriété du produit scalaire ,

c) G est semi-définie positive.n n

ti ij j i i j j

i, j 1 i, j 1

G G v ,v

2

n n nt

i i j j j ji 1 j 1 j 1

G v , v v 0

d) G est symétrique définie positive si la

famille est libre. i i=1 à nv

Page 13: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

13

b) Problème avec contraintesSoit M une matrice (p,n) « surjective » (donc de rang p)

Pour , on note Xc la partie non vide de définie par

pc IR nIR

ncX = α IR /Mα = c

On s’intéresse au problème de minimisation dans Xc:

nc

i ii=1

Trouver * tel que q( *)=Min q( )/

(P )où q( )= u- v

c cX X

Le problème (Pc) se met sous la forme du problème (Q) en posant

n

i i ci=1

V = v = α v /α X

Soit u un élément de H.

Page 14: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

14

Soit v V et

n

0 i ii=1

V = v = α v /Mα = 0

0 car v v (v v) avec v-v V 0V = v + V

V0 est un espace vectoriel de dimension finie.

c cThéorème 1 existence de * X solution de (P ).

De façon similaire au théorème 2, on peut donner une CNS d’unicité de la solution et montrer que s’obtient en résolvant un système linéaire de dimension (n+p,n+p).

*

V est un translaté d’espace vectoriel:

Page 15: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

15

Théorème 3 1°)

2°) est solution si et seulement s’il vérifie le système

où , G est la matrice (n,n) et b le vecteur de définis dans le théorème 2

3°)

pcc IR , u H,le problème(P )

admet

au moins une solution α * .

n* IR

pc IR , u H, * est unique si et seulement

Ker(M) Ker(G)= 0 .

tGα * +M λ = b

Mα* = cpIR nIR

Page 16: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

16

Remarque: Si la famille {vi} est libre alors Ker(G)={0}. Il y a a donc unicité de la solution.

Exemple:n=2 p=1 M=[1 2] de rang 1

Le problème (Pc) admet au moins une solution qui vérifie le système:

*11 1 1 2 1*

2 1 2 2 2 2

v ,v v ,v 1 u,v

v ,v v ,v 2 u,v

1 2 0 c

Page 17: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

17

On se pose le problème « d’approcher » le graphe de la fonction sur [0,1] par une droite. cos(πt)

II-Application aux moindres carrés II-1 Moindres carrés continus

a) sans contrainte

Une méthode naturelle consiste à l ’approcher au sens des des moindres carrés dit « continus ».

0 0.2 0.4 0.6 0.8 1-1.5

-1

-0.5

0

0.5

1

1.5

cos t

Page 18: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

18

b

a

(f ,g) f (t)g(t)dt de norme associée

1/2b2

2a

f = f(t) dt

On cherche la meilleure approximation au sens de la norme d ’une fonction par une fonction

2 2f L (]a,b[)

Soit un sous-espace de dimension finie n.

L2(]a,b[) espace des classes [f] de fonctions définies sur

]a,b[ de carré intégrable est un espace de Hilbert quand il est muni du produit salaire:

IR

Page 19: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

19

Soit i 1 à n une base de i

Le problème se met sous la forme du problème (P) avec

n

ii= 2

i1

αq( ) f

Théorème 2 q( ) atteint son minimum en * unique.

La meilleure approximation s’obtient en résolvant le système

(t) n

*i i

i=1

* (t) = α

Gα* = bb b

i, j i j i ia a

G (t) (t)dt b f (t) (t)dt i,j=1 à n

Page 20: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

20

k kb b i 1 j 1ij i j ka a

b k=i

aG t +t j-1

k

Dans ce cas

cas particulier de l’approximation par un polynôme espace des polynômes de degré muni de la

base des monômes n 1

i 1(t ),i 1 à n.

1 2 n

2 n 1

n n 1 2n 1

matrice de Hilbert si a=0 b=1G

Attention! Cette matrice est très mal conditionnée. Pour n grand, on choisira plutôt une base de polynômes orthogonaux qui rend la matrice G diagonale.

Page 21: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

21

Illustration numérique: retour à l’exemple

1

0

12

0

0cos t dtG b= 2

tcos t dt

1 1/2

1/2 1/3

2 2

112 12α* = * (t) = (1- 2t)

-2π π

Page 22: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

22

b) avec contraintes

C’est un problème d’approximation similaire au précédent auquel on a rajouté une contrainte.

On se pose le problème « d’approcher » sur [0,1] le

graphe de la fonction par une parabole dont la

tangente en 0 est égal à

πsin t

2

2

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

1

1.2

1.4

πsin t

2

Page 23: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

23

Ce problème peut s ’écrire comme un problème d ’approximation dans L2(]a,b[) :

c ic il ( ) c i=1 à / p

est une partie d’un sous-espace de dimension finie n définie par .

ii est une forme linéaire: IR et c unl réel

1 1soit al ( ) l (vec '(0)2

)

Dans l’exemple précédent est l ’espace des polynômes de degré

2

'(0)2

Il y a une contrainte (donc p=1) qui s ’écrit

l1 est bien une forme linéaire.

c c2 2Trouver * tel que f- * Min f- /

Page 24: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

24

j

i i

jc

n

j 1

l ( ) c i=1 à p

Ce problème d’approximation peut se mettre sous la forme du problème (Pc) en introduisant une base i i 1 à n , de .

n

j i j ij=1

i il ( ) c i= l ( ) c i=1 à p1 à p

ij i jM c avec M matrice (p,n) définie par M l ( )

Si M est surjective , on peut alors appliquer le théorème 3.

Page 25: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

25

Illustration numérique: retour à l’exemplei 1

i (t) t i=1 à 3 1l ( ) ' 0 M = 0 1 0

1 1

2 2

3 3

b

b

b

0 / 2

0

1

0

G

0

1 0

1 i 1i 0

t b t sin dt

2

ij1

G =i + j - 1

2*(t) 0.0333 t 0.5463t2

Page 26: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

26

II-2 Résolution d ’un système linéaire au sens des moindres carrés

Par mesure, on obtient pour les angles d’un triangle.On voudrait en déduire 3 valeurs vérifiant exactement

1 2 3θ ,θ ,θ

1 2 3α ,α ,α1 2 3α + α + α

On peut écrire ce problème comme un système à 2 inconnues

1 2α ,α

1

2

1

1 2 3

2

α

α

α + θα

θ

θ

Ce système ne possède pas en général de solution.

Page 27: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

27

On dit que l’on « résout » le système au sens des moindres carrés si on résout le problème

Trouver qui minimise sur n* IR

2N

k kk 1

q( ) w ( )

Aα - y

nIR

wk , k=1 à N sont des réels >0 (poids).

Si le système admet une solution au sens habituel, alors . Le minimum est donc atteint pour cette valeur.

*q( *) 0

Soit le système où une matrice rectangulaire A (N,n) et . (N=3 et n=2 dans l ’exemple précédent).

Aα = yNy IR

Page 28: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

28

NN 2

k kwk 1

Nk

Pour z IR ,on note z w z

qui définit une norme sur IR car w 0 k=1 à N

Le problème de minimisation s’écrit encore

n n

w

Trouver * IR tel que q( *)=Min q( )/ IR (P)

où q( )= A -y

Page 29: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

29

N3 ) y IR , * est unique si et seulement si Ker(A)=0.

est solution si et seulement s’il vérifie

le système

où DW est la matrice diagonale (N,N) définie par

n2 ) * IR t t

w wA D Aα = A D y

w kkD w pour k=1 à N

le problème aux moindres carrés

admet au moins une solution

N1 ) y IR (P)

*.

Proposition 1

Page 30: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

30

Remarques:

a) Ker(A)={0}

nj j

jj 1

A 0 0 (A colonnes de A)

les colonnes Aj sont linéairement indépendantes

est une condition nécessaire d’unicité de la solution (plus d’équations que d’inconnues).

N n

b) Pour retenir le résultat:

tw

On multiplie le système rectangulaire (N,n): A y

par la matrice (n,N) A D pour obtenir le système carré (n,n):

t tw w A D Ay A D y

c) On pourrait traiter un problème avec contraintes en utilisant le théorème 3.

Page 31: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

31

Illustration numérique: retour à l’exemple1 0

A 0 1 y=

1 1

1

2

3

θ

θ

θ

Ker(A)={0} unicité

t t2 1A A A y

1 2

2 3θ - θ

t t 3A A A y avec = -( )

3

1

2

3

2

1

1 2

θθ θ

α

θ

θ

α

( )3

3 1 2 3α α + α θ

Page 32: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

32

II-3 Moindres carrés discrets

On se pose le problème  d ’ajuster un ensemble de points à l ’aide d ’une droite.

2k k(x ,y ) IR ,k 1 à N

xk

yk

N=8

Page 33: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

33

Résoudre ce problème au sens des moindres carrés discrets consiste à déterminer une fonction espace de fonctions de dimension finie telle que soient «  petits ».

2k k[y - * (x )]

*

xk

yk

y = *(x)

k*(x )

Page 34: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

34

Une base étant donnée, cela revient à résoudre le problème

de i , i = 1 à n

n n

2N

i k kk 1

Trouver * IR tel que q( *)=Min q( )/ IR

Poù q( ) (x ) y

n

ii=1

kw

wk>0 k=1 à N sont des poids.

Il peut s’écrire sous la forme du problème (voir TD 6)

(P).

De la proposition 1, on tire alors le corollaire suivant:

Page 35: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

35

nIR

n3 ) y IR , *

N

ij k i k j kk=1

N

i k i k kk=1

G = w (x ) (x ) i, j = 1 à n

b = w (x )y i = 1 à n

Corollaire 1°) Le problème aux moindres carrés discrets admet au moins une solution 2°) est solution si et seulement s ’il vérifie le système linéaire où G est la matrice (n,n) et b le vecteur de définis respectivement par :

(P)*

n* IR G * b

est unique si et seulement si l’espace vérifie la propriété:

k (x ) 0 pour k 1 à N 0.

Page 36: 1 APPROXIMATION. MOINDRES CARRES. 2 Approcher le graphe de la fonction sur [0,1] par une droite. 00.20.40.60.81 -1.5 -0.5 0 0.5 1 1.5 cos t

36

Application : droite aux moindres carrés

1 2(x) 1 (x) x n=2 base des monômes:

N N N

k k k k kk 1 k 1 k 1

N N N2

k k k k k k kk 1 k 1 k 1

G

w w x w y

w x w x

b=

w x y