Université d’Orléans Outils numériquesL3 groupe 2 2ème semestre 2006/2007

Corrigé du partiel

—————————————————

Question de cours : Problème des moindres carrésL’origine de ce problème est la recherche de solutions pour un système linéaire Ax = b où la matrice A estnon inversible ou non carrée. Le problème des moindres carrés consiste alors à chercher la ou les solutions duproblème de minimisation

minx∈Rp

‖Ax− b‖22,

où A ∈Mn,p(R) et b ∈ Rn.Il existe toujours au moins une solution de l’équation normale A∗Ax = A∗b. Cette solution est unique si et

seulement si ker A = {0}, et on a alors x = A†b = (A∗A)−1A∗b (pseudo-inverse).

Méthodes de résolution numérique.

1. Méthode de Cholesky : lorsque ker A = {0}, on peut résoudre l’équation normale A∗Ax = A∗b par laméthode de Cholesky, la matrice A∗A étant alors symétrique définie positive.

2. Méthode QR : la décomposition QR de la matrice A conduit à écrire A = QR où Q ∈ Mn(R) est unematrice orthogonale et R ∈ Mn,p(R) est une matrice triangulaire supérieure. Le problème des moindrescarrés est alors équivalent à

minx∈Rp

‖Rx−Q∗b‖22.

Si n > p (cas le plus répandu en pratique ; les autres cas se traitent similairement) et si ker A = {0},l’unique solution est alors

x = (R16i,j6p)−1(Q∗b)16i6p.

3. Méthode SVD et pseudo-inverse : la décomposition SVD de la matrice A conduit à écrire A = V ΣU∗,où U ∈ Mp(R) et V ∈ Mn(R) sont des matrices orthogonales et Σ ∈ Mn,p(R) est une matrice donttous les coefficients sont nuls sauf les r premiers coefficients diagonaux qui sont les r valeurs singulièresµ1 > · · · > µr > 0 de A. Le problème des moindres carrés est alors équivalent à

minx∈Rp

‖V ΣU∗x− b‖22 = minx∈Rp

‖ΣU∗x− V ∗b‖22,

dont toutes les solutions sont x = Uy avec y ∈ Rp un vecteur quelconque dont les r premières composantess’écrivent yi = (V ∗b)i/µi.

Notons que le pseudo-inverse de A est alors A† = UΣ†V ∗ où Σ† ∈Mp,n(R) est une matrice dont tous lescoefficients sont nuls sauf les r premiers coefficients diagonaux qui sont 1/µ1, . . . , 1/µr.

Remarque. Notons que le vecteur x = A†b est toujours une solution du problème des moindres carrés, etest la solution de norme Euclidienne minimale lorsque ce problème admet plusieurs solutions.

1

Application : le problème de l’approximation aux moindres carrés. C’est un problème d’analyse dedonnées. Etant donnés n valeurs (ti)16i6n d’un paramètre, et n valeurs (bi)16i6n d’une grandeur mesurée, oncherche à déterminer un polynôme P de degré p− 1 qui minimise

E =n∑

i=1

|bi − P (ti)|2 .

Lorsque n 6 p − 1, on peut choisir un polynôme d’interpolation de Lagrange, et alors E = 0. Le cas le pluscourant est bien sûr n > p− 1.

En écrivant P (t) =p−1∑j=0

ajφj(t) dans une base (φj) de l’espace des polynômes, on se ramène à min-

imiser une fonction E(a0, . . . , ap−1). Soient les vecteurs x = (ai)06i6p−1, b = (bi)06i6p−1, et la matriceA = (φj(ti))16i6n,06j6p−1. Avec ces notations, E = ‖Ax − b‖22, et donc, on s’est ramené au problème desmoindres carrés pour le couple (A, b).

—————————————————

Problème :

1. (a) En prenant y = 0 dans l’inégalité, on obtient xf(x) > cx2, pour tout x ∈ IR. On en déduit quef(x) → +∞ lorsque x → +∞, et f(x) → −∞ lorsque x → −∞.

(b) On prend y = x + h, on divise par h2, et on obtient f ′(x) > c.(c) La fonction f est strictement croissante, et va de −∞ à +∞ sur IR. C’est donc une bijection de IR

dans IR. Donc l’équation (1) admet une solution unique α.(d) Puisque f est strictement croissante, et f(0) = 0, et a > 0, on a α > 0. Par ailleurs, αf(α) > cα2

d’après 1.a, donc α 6 ac .

2. (a) f ′ est croissante sur l’intervalle considéré (car f ′′ > 0), donc f ′(x) 6 f ′(α) et f ′(y) > f ′(α), et parailleurs f ′(α) > c. Donc,

0 6f ′(x)f ′(y)2

61

f ′(α)6

1c.

(b) Notons que a− f(x) = f(α)− f(x) > 0 puisque f est croissante. D’après le théorème des accroisse-ments finis, a− f(x) 6 sup[x,α](|f ′|)(α− x) = f ′(α)(α− x) car f ′ est croissante, d’où

f ′(x)f ′(y)2

(a− f(x)) 61

f ′(α)(a− f(x)) 6 α− x,

même chose pour la deuxième inégalité avec changement de signe puisque a− f(y) 6 0.

3. (a) Par récurrence: c’est vrai pour n = 0. Supposons que c’est vrai au rang n. Alors f(xn) − a =f(xn)− f(α) 6 0, et d’après 2.b, 0 6 ρn(a− f(xn)) 6 α− xn, d’où xn+1 6 α. De même pour yn+1.

(b) Puisque 0 6 ρn(a− f(xn)), on a clairement xn+1 > xn. De même pour yn.(c) La suite (xn)n∈IN est croissante et majorée par α, et la suite (yn)n∈IN est décroissante et minorée par

α, donc ces suites convergent, respectivement vers α1 et α2. En passant à la limite dans la définitionpar récurrence de ces suites (on voit facilement que ρn converge vers une valeur non nulle), on trouveque f(α1) = f(α2) = a, et puisque f est bijective, α1 = α2 = α.

4. (a) D’après le théorème des accroissements finis, 0 6 f ′(yn)− f ′(xn) 6 K(yn − xn), et par ailleurs, on a1

f ′(yn) 6 1c puisque f ′ > c, donc

f ′(yn)− f ′(xn)f ′(yn)

6K

c(yn − xn).

2

(b) En appliquant la formule de Taylor-Lagrange, il existe θn ∈]xn, yn[ tel que f(xn) = f(yn)+f ′(yn)(xn−yn) + 1

2f ′′(θn)(xn − yn)2, d’où

|xn+1 − yn+1| =∣∣∣∣xn − yn −

f ′(xn)f ′(yn)2

(f(xn)− f(yn))∣∣∣∣

=∣∣∣∣xn − yn −

f ′(xn)f ′(yn)2

(f ′(yn)(xn − yn) +12f ′′(θn)(xn − yn)2)

∣∣∣∣6 |xn − yn|

∣∣∣∣f ′(yn)− f ′(xn)f ′(yn)

∣∣∣∣ +K

2c|xn − yn|2 car | f

′(xn)f ′(yn)2

| 6 1c

d’après 2.a

6K

c|xn − yn|2 +

K

2c|xn − yn|2 d’après 4.a

6 M |xn − yn|2 avec M =3K

2c.

(c) Par récurrence immédiate, |xn − α| 6(M1− 1

2n ac

)2n

6(

Mac

)2n

. Convergence quadratique (ordre 2).

5. La méthode n’est pas plus rapide que la méthode de Newton.

6. Fichier script, avec un exemple de fonction qui vérifie les hypothèses du problème:

clc ;

deff(’y=f(x)’,’y=x+atan(x)’) ;deff(’y=fp(x)’,’y=1+1/(1+x^2)’) ;a=3 ; c=1 ;

x=0 ; y=a/c ; eps=1e-6 ;

while abs(x-y)>epsrho=fp(x)/fp(y)^2 ;x=x-rho*(f(x)-a) ;y=y-rho*(f(y)-a) ;

end

x

3