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

1

APPROXIMATION.

MOINDRES CARRES

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

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

4

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

xk

yk

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.

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.

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,

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*

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.

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

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

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

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.

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:

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

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

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

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

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

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.

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π π

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

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- /

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.

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

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.

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

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

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

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.

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α α + α θ

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

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 )

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:

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.

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