Maths 1

# Mathématiques 1

TSI

4 heures Calculatrice autorisée

La méthode des moindres carrés

Ce problème comporte 5 parties. Les parties A, B, C et D sont indépendantes entre elles. L’objet de ce sujet est l’étude d’une méthode très utile en intelligence artificielle : la méthode des moindres carrés. Les parties A et C présentent des domaines des mathématiques que l’on peut reformuler en termes de problème des moindres carrés. La partie D amène à résoudre des systèmes d’équations linéaires au sens des moindres carrés à l’aide de la notion de décomposition en valeurs singulières. La partie B introduit la notion de limites de suites de matrices, que l’on utilise dans la partie E pour résoudre le problème étudié dans la partie D.

Rappels et notations

– Si k et l sont deux entiers tels que k ≤l, on note Jk, lK l’ensemble des entiers i tels que k ≤i ≤l.

– L’espace vectoriel des polynômes à coefficients dans R est noté R[X]. Pour n ∈N, on note Rn[X] l’espace

vectoriel des polynômes à coefficients dans R de degré inférieur ou égal à n.

– Pour n ∈N∗et p ∈N∗, on note Mn,p(R) l’espace vectoriel des matrices à n lignes et p colonnes.

On note aussi Mn(R) = Mn,n(R) l’espace vectoriel des matrices carrées de taille n.

– La transposée d’une matrice A = (ai,j) 1 ≤i ≤n 1 ≤j ≤p ∈Mn,p(R) est notée AT .

Elle est définie par AT = (aj,i) 1 ≤i ≤n 1 ≤j ≤p ∈Mp,n(R).

n X

– La trace d’une matrice A = (ai,j)1≤i,j≤n ∈Mn(R) est notée Tr(A). Elle est définie par Tr(A) =

ai,i.

i=1

– Le produit scalaire canonique sur l’espace vectoriel Mn,1(R) des vecteurs colonnes à n lignes est noté ⟨., .⟩et sa

norme associée est notée ∥.∥2. Ce produit scalaire est défini par :









a1

b1

v u u t

n X

n X

... an

... bn

 , ⟨A, B⟩= AT B =

a2

∀A =

 , ∀B =

aibi et ∥A∥2 =

i .

 

 

i=1

i=1

– Le produit scalaire canonique sur l’espace vectoriel Mn(R) des matrices carrées est aussi noté ⟨., .⟩et sa norme

associée est notée ∥.∥2. Ce produit scalaire est défini par :

v u u t

n X

n X

n X

n X

AT B






a2

∀A = (ai,j)1≤i,j≤n , ∀B = (bi,j)1≤i,j≤n , ⟨A, B⟩= Tr

=

ai,jbi,j et ∥A∥2 =

i,j.

i=1

j=1

i=1

j=1

– L’ensemble des valeurs propres complexes d’une matrice A ∈Mn(R) s’appelle le spectre de A et se note Sp(A).

Partie A – Quelques problèmes de minimisation et de convergence

I – Distance entre un vecteur et un sous-espace vectoriel

On munit M4,1(R) de son produit scalaire canonique. Soit F = Vect(e1, e2, e3) avec













1 −2

1 1 1 0

1 0 −1

  

   e2 =

  

   e3 =

  

  .

e1 =

1 0

Q1. Justifier que (e1, e2, e3) est une base orthogonale de F. Proposer une base orthonormée de F.





x y z

  ∈M4,1(R).

  

Q2. Calculer le projeté orthogonal sur F d’un vecteur colonne

t





1 1 1 1

  

  . Calculer min

Q3. On note v =

u∈F ∥v −u∥2.

II – Séries de Fourier

2π(R, R) l’espace vectoriel des fonctions continues 2π-périodiques. On munit E du produit scalaire défini par

Soit E = C0

Z 2π

∀(f, g) ∈E2, φ (f, g) = 1

0 f(t)g(t) dt.

2π

2π(R, C) sont définis (pour n ≥1) par

On note ∥.∥la norme associée. Les coefficients de Fourier d’une fonction f ∈C0

Z 2π

Z 2π

Z 2π

a0(f) = 1

0 f(t) dt an(f) = 1

0 f(t) cos(nt) dt bn(f) = 1

0 f(t) sin(nt) dt

2π

π

π

Pour tout n ∈N, nous introduisons les fonctions en : x 7−→cos(nx) et fn : x 7−→sin(nx).

Les sommes partielles de la série de Fourier d’une fonction f ∈E sont les fonctions définies par

N X

∀N ∈N∗, SN(f) = a0(f) +

(an(f)en + bn(f)fn).

n=1

Q4. Soient α ∈R \ Z et f la fonction 2π-périodique telle que f(x) = cos(αx) pour tout x ∈] −π, π].

απ et an(f) = (−1)n

Montrer que pour tout n ≥1, on a bn(f) = 0 et a0(f) = sin(απ)

2α sin(απ) α2 −n2 .

π

+∞ X

+∞ X

1 n2 −α2 et

1 (n2 −α2)2 convergent, et calculer

1 n2 −α2 et

1 (n2 −α2)2 .

X

X

Q5. Montrer que les séries

n≥1

n≥1

n=1

n=1

+∞ X

Q6. Montrer que pour tout t ∈R \ πZ, on a cos(t)

sin(t) = 1

2t t2 −(nπ)2 .

t +

n=1

Soit f : R −→C une fonction 2π-périodique de classe C2 qui est solution de l’équation différentielle

f ′′ + eixf = 0. (E)

Z 2π

Z 2π

Pour tout n ∈Z, on pose cn(f) = 1

0 f(t)e−int dt et cn(f ′′) = 1

0 f ′′(t)e−int dt.

2π

2π

Q7. Montrer que pour tout n ∈N∗on a cn(f) = an(f) −ibn(f)

2 et c−n(f) = an(f) + ibn(f)

2 .

Montrer que pour tout n ∈N∗on a an(f) = cn(f) + c−n(f) et bn(f) = i(cn(f) −c−n(f)).

Q8. Soit n ∈Z. Montrer que cn(f ′′) = −n2cn(f), puis que cn−1(f) = n2cn(f).

 

c0(f)

(n!)2 si n ≥0

En déduire que cn(f) =

.

0 si n < 0



+∞ X

+∞ X

einx

cn(f)einx + c−n(f)e−inx


Q9. Montrer que pour tout x ∈R, on a f(x) = c0(f) +



= c0(f)

(n!)2 .

n=1

n=0

+∞ X

einx

On admet que la fonction définie par x 7−→

(n!)2 est bien une solution de l’équation (E).

n=0

Q10. On rappelle que l’ensemble des solutions de l’équation (E) est un sous-espace vectoriel de C∞(R, C).

Quelle est sa dimension ? Justifier. L’équation (E) admet-elle une solution qui n’est pas 2π-périodique ?

Q11. Montrer que, pour tout N ∈N∗, la famille (e0, . . . eN, f1, . . . , fN) est orthogonale pour φ. Est-elle orthonormale ?

Q12. Soient g ∈E et N ∈N∗. On note VN = Vect(e0, . . . , eN, f1, . . . , fN).

Quelle est la projection orthogonale de g sur VN ? En déduire une fonction h ∈E telle que ∥g−h∥= min

v∈VN ∥g−v∥.

Partie B – Limites de suites de Matrices





mk,1,1 . . . mk,1,p ... ... mk,n,1 . . . mk,n,p

Soit (Mk)k∈N une suite de matrices de Mn,p(R), avec Mk =

 (pour tout k ∈N).

 

On dit que la suite (Mk)k∈N converge si pour tout (i, j) ∈J1, nK × J1, pK la suite (mk,i,j)k∈N converge. On note alors

lim k→+∞(mk,1,1) . . . lim k→+∞(mk,1,p)





... ... lim k→+∞(mk,n,1) . . . lim k→+∞(mk,n,p)

  

  .

lim k→+∞Mk =

Lorsque la suite (Mk)k∈N ne converge pas, on dit que la suite (Mk)k∈N diverge.

On admettra sans preuve que, si (Mk)k∈N converge, alors, pour tout (q, r) ∈N∗× N∗, toute matrice P ∈Mq,n(R) et





toute matrice Q ∈Mp,r(R) la suite (PMkQ)k∈N converge et lim k→+∞(PMkQ) = P

lim k→+∞Mk

Q.

√

 0 1 1 0

 −1/2 −





3/2 √

Ak


Bk






Q13. Soient A =

et B =

. Montrer que les suites

k∈N et

k∈N divergent.

3/2 −1/2

Q14. Soit A une matrice diagonalisable sur R. Montrer que la suite



Ak


k∈N converge si et seulement si Sp(A) ⊂]−1, 1].





0 1 1 1 0 1 1 1 0

Q15. Soit A = 1

. Montrer que A est diagonalisable sur R, et que la suite de matrices

Ak




k∈N converge.











0 1 0 0 0 1 1 1 −1

1 0 0 0 −1 1 0 0 −1

Q16. Montrer que les matrices A =

et T =

sont semblables.





Ak


La suite de matrices



k∈N converge-t-elle ?

Dans la suite de l’énoncé, on pourra utiliser sans preuve le résultat suivant :

si M ∈Mn,p(R) est une matrice et si (Mk)k∈N est une suite de matrices de Mn,p(R), alors

lim k→+∞Mk = M si et seulement si lim k→+∞∥Mk −M∥2 = 0.

Partie C – Interpolation polynômiale et moindres carrés

Soient n ∈N∗et (x0, . . . , xn) ∈Rn+1 une famille de nombres réels deux à deux distincts. Pour chaque i ∈J0, nK, on note

X −xj xi −xj

Y

Li(X) =

.

0≤j≤n, j̸=i

 1 si k = i 0 sinon

Q17. Montrer que pour tout (i, k) ∈J0, nK2, on a Li(xk) =

n X

Q18. Montrer que l’on peut munir Rn[X] d’un produit scalaire ⟨., .⟩en posant ⟨P, Q⟩=

P(xk)Q(xk).

k=0

Q19. Montrer que (L0, . . . , Ln) est une base orthonormée de Rn[X] muni du produit scalaire ⟨., .⟩.

n X

Q20. Montrer que pour tout P ∈Rn[X] et tout i ∈J0, nK, on a ⟨Li, P⟩= P(xi), puis que P =

P(xi)Li.

i=0

n X

Soit (a, b) ∈R2 tel que pour tout i ∈J0, nK on ait a < xi < b. Soit f ∈Cn+1([a, b], R). On note Pf =

f(xi)Li.

i=0

Q21. Soient m ≤n. En calculant ⟨Pf −Q, Pf −Q⟩, montrer l’existence et l’unicité d’un polynôme R ∈Rm[X] tel que

n X

n X

!

(f(xi) −R(xi))2 = min Q∈Rm[X]

(f(xi) −Q(xi))2

.

i=0

i=0

Q22. Soit g ∈Cn+1([a, b], R). On suppose que g possède au moins n+2 zéros deux à deux distincts dans [a, b]. Montrer

par récurrence sur n que g(n+1) a au moins un zéro dans [a, b]. On pourra utiliser le théorème de Rolle.

Q23. Soit x ∈[a, b] avec x̸ = xi pour tout i ∈J0, nK. Soit K = f(x) −Pf(x)

.

n Y

(x −xi)

i=0

n Y

Montrer que W : t 7−→f(t) −Pf(t) −K

(t −xi) s’annule en n + 2 points distincts de [a, b].

i=0

n Y

(x −xi)

i=0

(n + 1)! f (n+1)(ξx).

En déduire l’existence de ξx ∈[a, b] tel que f(x) −Pf(x) =

Partie D – Régression linéaire et moindres carrés

I – Le cas particulier de la dimension 2

Soit n ≥2 un entier. Considérons n points du plan réel (x1, y1), . . . , (xn, yn) avec x1, . . . , xn deux à deux distincts tels que (x1, . . . , xn) ne soit pas colinéaire au vecteur (1, . . . , 1).

En dimension 2, la régression linéaire consiste à trouver une relation affine entre deux grandeurs physiques, c’est-à-dire à chercher une droite affine s’approchant le plus possible des points (x1, y1), . . . , (xn, yn) (au sens des moindres carrés).

Pour formuler ce problème de manière précise et rigoureuse, nous notons









1 x1 1 x2 ... ... 1 xn

y1 y2

n X

   

    et Y =

   

   .

(yi −a −bxi)2 et A =

E(a, b) =

... yn

i=1

Le problème est alors de trouver les valeurs de a et b qui minimisent la fonction E.

 a

A



Q24. Montrer que E admet un minimum m sur R2 (qu’on ne demande pas de calculer) et que m = min (a,b)∈R2

−Y

2 .

b

!2

n X

n X

!

AT A

AT A

x2

Q25. Montrer que det






= n

−

xk

, puis justifier l’affirmation det






> 0.

k

k=1

k=1

Indication : On pourra utiliser l’inégalité de Cauchy-Schwarz

Q26. Calculer le gradient de E : (a, b) 7−→E(a, b).

 a0



Soit (a0, b0) un point critique de E. Montrer que l’on a AT A

= AT Y .

b0

En déduire qu’il existe un unique couple (c, d) ∈R2 tel que E(c, d) = min (a,b)∈R2 E(a, b).

II – Les moindres carrés : le cas général

Nous allons maintenant généraliser les idées de la sous-section précédente au cas de la dimension quelconque.

Soit A ∈Mn,p(R). Notons Col(A) = Vect(C1, . . . , Cp) avec C1, . . . Cp les colonnes de A. Soit y ∈Mn,1(R).

Q27. Soit x ∈Mp,1(R) tel que AT Ax = 0. Montrer que ∥Ax∥2 = 0.

AT A

= Ker (A), puis que rg(AT A) = rg(A).






Q28. Montrer que Ker

Q29. Montrer l’existence d’un unique couple (u, d) ∈Mp,1(R) × (Col(A))⊥tel que y = Au + d.

Q30. Montrer que pour tout x ∈Mp,1(R), on a ∥Ax −y∥2 ≥∥d∥2 avec égalité si et seulement si x −u ∈Ker(A).

Q31. Montrer que AT y = AT Au.

Q32. Soit x0 ∈Mp,1(R). Montrer que : ∥Ax0 −y∥2 = min x∈Mp,1(R) ∥Ax −y∥2 ⇐⇒ AT Ax0 = AT y.

Q33. Supposons n > p et que la matrice A est de rang maximal, c’est-à-dire que le rang de A est égal à p.

Montrer que AT A est inversible. En déduire que l’équation ∥Ab −y∥2 = min x∈Mp,1(R) ∥Ax −y∥2 a une unique solution donnée par b = (AT A)−1AT y.

III – La décomposition en valeurs singulières

Soient A ∈Mn,p(R) non nulle et y ∈Mn,1(R). Nous allons généraliser le résultat de la question Q33.

Dans la suite, nous notons Diagk,l(α1, . . . , αmin(k,l)) la matrice de taille k × l dont le coefficient en ligne i et colonne i est αi (pour tout indice i ≤min(k, l)), et dont tous les autres coefficients sont nuls.

Q34. Montrer que pour tout vecteur colonne X ∈Mp,1(R), les nombres XT AT AX et XT X sont positifs ou nuls.

Q35. Montrer que les valeurs propres de la matrice AT A sont toutes positives ou nulles.

AT A






Q36. Notons r = rg

= rg (A) (égalité prouvée à la question Q28). Montrer qu’il existe des nombres réels λ1 ≥· · · ≥λr > 0 et une matrice orthogonale V ∈Op(R) tels que AT A = V Diagp,p(λ1, . . . , λr, 0, . . . 0)V T .

Q37. Notons vi la i-ème colonne de V .

Montrer que la famille (Av1, . . . , Avr) est orthogonale pour le produit scalaire canonique de Mn,1(R), et que,

 p

λi si i ≤r 0 si i ≥r + 1 .

pour tout i ∈J1, pK, on a ∥Avi∥2 =

Montrer l’existence d’une base orthonormée (u1, . . . , un) de Mn,1(R) telle que ui = 1 √λi

Avi pour tout i ≤r.

p



p

∈Mn,p(R).

Q38. Notons U la matrice dont la i-ème colonne est ui et D = Diagn,p

λ1, . . . ,

λr, 0 : . . . , 0

Vérifier que U ∈On(R) et que AV = UD.

En particulier, on a A = UDV T . Cette écriture s’appelle une décomposition en valeur singulière de A. Posons

 1 √λ1

, . . . , 1 √λr



∈Mp,n(R) et eA = V ∆U T ∈Mp,n(R)

∆= Diagp,n

, 0, . . . , 0

Q39. Montrer que A eA est la matrice de la projection orthogonale sur Im(A).

Q40. Soit y ∈Mn,1(R). Soit b = eAy ∈Mp,1(R). Vérifier que ∥Ab −y∥2 = min x∈Mp,1(R) ∥Ax −y∥2.

Soit x0 ∈Mp,1(R) un autre vecteur qui vérifie ∥Ax0−y∥2 = min x∈Mp,1(R) ∥Ax−y∥2. Nous allons montrer que ∥x0∥2 ≥∥b∥2.

Q41. Montrer que Ab −y ∈Im(A)⊥. En déduire que x0 −b ∈Ker(A)

Q42. Montrer que b ∈Ker(A)⊥.





Indication : on pourra exprimer Im

eA

et Ker(A) en fonction des vecteurs colonnes vi.

Q43. Montrer que ∥x0∥2 ≥∥b∥2 avec égalité si et seulement si x0 = b.

Partie E – La méthode du gradient

Soit A ∈Mn,p(R) et y ∈Mn,1(R). Nous avons vu à la question Q35 que les valeurs propres λ1 ≤· · · ≤λp de AT A sont des nombres réels positifs ou nuls. Dans cette partie, nous supposons en plus que pour tout i, on a λi > 0.

Nous reformulons notre problème des moindres carrés en remarquant (par le calcul) que

2 = ⟨AT Ax, x⟩−2⟨x, AT y⟩+ ⟨y, y⟩.

∀x ∈Mp,1(R), ∥Ax −y∥2

Nous allons étudier une suite de matrices convergente dont la limite sera un minimum de la fonction

 Mp,1(R) −→ R x 7−→ ⟨AT Ax, x⟩−2⟨x, AT y⟩.

f :

Soit (e1, , . . . , ep) une base orthonormale de Mp,1(R) telle que pour tout i ∈J1, pK on ait AT Aei = λiei.

Q44. Montrer que la matrice AT A est inversible, et justifier que Ker(A) = { 0 }.

 Mp,1(R) × Mp,1(R) −→ R (x, y) 7−→

Q45. Montrer que l’application

est un produit scalaire.

AT Ax, y

p X

Soient (v1, . . . , vp) ∈Rp et v =

viei.

i=1

Q46. Montrer que pour tout (α, β) ∈R2 on a : αβ ≤1

4(α + β)2.

 λi

!2

p X

≤1

4 λ1 λp

+ λp



AT Av, v

(AT A)−1v, v

v2

Montrer que

.

i

λ1

λi

i=1

Q47. Soit ψ : t 7−→t

+ λp

t . Calculer le maximum de ψ sur [λ1, λp].

λ1

≤(c(A) + 1)2

Q48. On note c(A) = λp

AT Av, v

(AT A)−1v, v

4c(A) ∥v∥4

. Montrer l’inégalité de Kantorovich :

2.

λ1

Nous souhaitons maintenant déterminer une approximation de l’unique solution ℓà l’équation AT Aℓ= AT y.

Nous définissons une suite par récurrence en choisissant un vecteur x0 ∈Mp,1(R) et en posant pour tout k ∈N :

dk = AT Axk −AT y tk = ∥dk∥2

2 ⟨AT Adk, dk⟩ xk+1 = xk −tkdk.

Pour que cette définition ait un sens, nous supposons que le vecteur dk est non nul pour tout k ∈N. Cette hypothèse n’est pas restrictive : s’il existe k tel que dk = 0 alors xk = ℓet nous avons ainsi la valeur exacte de ℓ.

Soit ℓ= (AT A)−1AT y ∈Mp,1(R).

Q49. Vérifier que pour tout x ∈Mp,1(R), on a f(x) −f(ℓ) = ⟨AT A(x −ℓ), x −ℓ⟩.

1 − ∥dk∥4





Q50. Montrer que pour tout k ∈N, on a f(xk+1) −f(ℓ) = (f(xk) −f(ℓ))

2 ⟨AT Adk, dk⟩⟨(AT A)−1dk, dk⟩

.

2k

2 ≤f(xk) −f(ℓ) ≤(f(x0) −f(ℓ)) c(A) −1

Q51. Montrer que pour tout k ∈N, on a λ1∥xk −ℓ∥2

.

c(A) + 1

M085 - 24 février 2026 - 15:26:54 c b e a

Q52. Montrer que la suite (xk)k∈N converge vers ℓ, et que ∥Aℓ−y∥2 = min x∈Mp,1(R) ∥Ax −y∥2.

⋄ Fin ⋄