CCINP Mathématiques 2 TSI 2005Sujet et corrigé

Pas encore noté

Explorer les annales

BanqueCCINP Année2005 FilièreTSI MatièreMathématiques

Annales CCINP TSI Mathématiques CCINP TSI 2005 TSI Mathématiques Mathématiques 2005

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Corrigé 2

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

Les calculatrices sont autorisées

N.B. :Le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction.

Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il la signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.

Ce sujet présente la méthode des traces, algorithme de calcul itératif du polynôme caractéristique d'une matrice. Cette méthode fut utilisée par l'astronome français Urbain Le Verrier pour découvrir la planète Neptune en 1845.

Le principe de la méthode est expliqué en partie I. Le programme informatique qui s'en déduit est analysé en partie II. Trois exemples et une application concluent le problème, partie III. Les parties II et III sont indépendantes et pourront être traitées dans un ordre arbitraire.

Dans tout le problème, ndésigne un entier naturel supérieur ou égal à 2 , et

M_n(ℂ)

est l'ensemble des matrices carrées à n lignes et n colonnes. On notera I la matrice identité.

I. La méthode des traces

Soit une matrice

A \in M_n(ℂ)

. On souhaite en calculer de façon systématique le polynôme caractéristique

χ_A

défini sur

ℂ

par :

χ_A(λ), = det(A - λI); = a_0 λ^n + a_1 λ^(n - 1) + \dots + a_(n - 1)λ + a_n

où les coefficients

a_0, \dots, a_n \in ℂ

ont volontairement été indexés à rebours pour faciliter l'issue de la question I.6 . Dans le cas général, deux difficultés se posent :

Le développement du déterminant, qui doit être réalisé avec une complexité raisonnable.
La collecte des coefficients à l'issue du développement.

Nous verrons en question II. 4 d/ que ces deux contraintes excluent d'office toute méthode de calcul récursif. Des méthodes plus appropriées ont donc été mises au point, dont la méthode des traces expliquée ci-après.

$a/$ Que vaut $a_0$ ?
b/ Quelle hypothèse du problème et quel théorème du cours vous permettent - au moins d'un point de vue théorique - de factoriser $χ_A(λ)$ sous la forme :

χ_A(λ) = a_0 \cdot (λ - λ_1)(λ - λ_2)\dots(λ - λ_n)

où les complexes

λ_1, λ_2, \dots, λ_n

sont les valeurs propres (non nécessairement distinctes) de A .
c/ Lorsque ces valeurs propres sont connues, elles permettent de remonter aux coefficients de

χ_A

. Expliquer comment pour les coefficients

a_1

a_n

Malheureusement, les valeurs propres ne sont pas toujours connues avant le calcul du polynôme caractéristique. Plutôt que de relier les coefficients aux racines, on peut relier les coefficients à des sommes de puissances de valeurs propres, grâce à des formules de Newton (question I. 7 ): c'est la méthode des traces.
2. Le polynôme caractéristique

χ_A

étant scindé, on rappelle qu'il est possible de trigonaliser A. Il existe une matrice T triangulaire semblable à A dont les coefficients diagonaux sont précisément

λ_1, λ_2, \dots, λ_n

. Exprimer en fonction de

λ_1, λ_2\dots, λ_n

les traces de

T^p

puis de

A^p

pour tout entier naturel p .
3. On note

χ_A^'

la dérivée de

χ_A

. Établir l'identité :

(χ_A^'(λ))/(χ_A(λ)) = \sum_(k = 1)^n 1/(λ - λ_k)

En déduire que, pour $λ$ assez grand en module :

(χ_A^'(λ))/(χ_A(λ)) = 1/λ\sum_(k = 1)^n\sum_(p = 0)^(+ \infty)((λ_k)/λ)^p

On fournira un minorant strict m de

|λ|

le plus précis possible.
5. En conclure que, pour

|λ| > m

(χ_A^'(λ))/(χ_A(λ)) = 1/λ\sum_(p = 0)^(+ \infty)(tr(A^p))/(λ^p)

Démontrer alors que, pour $λ$ assez petit en module, on a :

n \cdot a_0 + (n - 1) \cdot a_1 \cdot λ + \dots + 1 \cdot a_(n - 1)λ^(n - 1) = (a_0 + a_1 \cdot λ + \dots + a_n \cdot λ^n)\sum_(p = 0)^(+ \infty)tr(A^p)λ^p

On traitera le cas

λ = 0

à part, et on fournira un majorant strict M de

|λ|

le plus précis possible.
7. En déduire les relations de Newton, valables pour tout

k, 1 \leq k \leq n

- ka_k = a_0 \cdot tr(A^k) + a_1 \cdot tr(A^(k - 1)) + \dots + a_(k - 1)tr(A)

Expliquer sommairement en quoi ces relations permettent d'obtenir le polynôme caractéristique $χ_A$ . Restent-elles valables lorsque $A \in M_n(ℝ)$ ?

II. Mise en place de l'algorithme

Dans cette partie, on s'intéresse à la mise en œuvre pratique de l'algorithme des traces et on en évalue les performances en termes de complexité. Cette partie en appelle à l'expérience du candidat en matière de calcul formel : Maple, Mathematica, ou tout simplement le logiciel de sa calculatrice programmable. Dans tous les cas, indiquez sur la copie le langage utilisé.

Dire qu'un programme a une complexité de l'ordre de

n^k

(

n

k

entiers naturels non nuls) signifie que le nombre d'additions, de multiplications et de divisions élémentaires à réaliser est équivalent à

αn^k(α > 0)

lorsque n tend vers

+ \infty

. Par exemple, un programme réalisant le produit de n complexes est d'une complexité de l'ordre de n . En revanche, un programme réalisant n fois un produit de

n

complexes est d'une complexité de l'ordre de

n^2

Les logiciels de calcul formel sont souvent livrés avec une fonction permettant de multiplier deux matrices de $M_n(ℂ)$ . Sans reprogrammer cette fonction, indiquer sa complexité.
Les logiciels de calcul formel sont souvent livrés avec une fonction permettant de calculer la trace d'une matrice de $M_n(ℂ)$ . Sans reprogrammer cette fonction, indiquer sa complexité.
a/ On suppose la matrice A et l'entier n connus du logiciel. Rédiger la partie de programme réalisant le stockage des traces $tr(A^1), tr(A^2), \dots, tr(A^n)$ dans un tableau $t$ , de sorte que $t[k]$ contienne $tr(A^k)$ pour k variant de 1 à n .
b/ En général, la complexité d'un tel programme peut varier de $n^4$ à $n^5$ selon la manière dont on s'y prend. Quelle est la complexité du programme conçu en réponse au a/ (justifier) ?

a/ On suppose désormais la matrice A, l'entier n et le tableau t connus du logiciel. Rédiger la partie du programme réalisant le stockage des coefficients

a_0, a_1, \dotsa_n

, dans un tableau

a

, de sorte que

a[k]

contienne

a_k

pour k variant de 0 à n .
b/ Que renseigne le dernier coefficient :

a_n

?
c/ Quelle est la complexité totale de l'algorithme des traces (justifier) ?
d/ On revient maintenant à la méthode naïve évoquée au début du problème. Celle-ci consisterait en un développement récursif du déterminant caractéristique : développement du déterminant

n \times n

par rapport à la première colonne, puis développement des sous-déterminants

(n - 1) \times (n - 1)

par rapport à leur première colonne, etc. Quelle est la complexité de cette méthode (justifier) ? En quoi la collecte des coefficients pose-t-elle difficulté ? Conclure.

III. Trois exemples et une application

La validation d'un algorithme s'accompagne toujours de tests. On fait tourner le programme sur des exemples dont on connaît les résultats intermédiaires ou finaux. Puis on compare ce qui est attendu à ce qui est effectivement retourné. Les questions 1,2 et

3

de cette partie permettent d'élaborer de tels tests. La question 4 validera encore davantage cette étude, mais pour d'autres raisons.

Dans les trois premières questions de cette partie, on rapporte l'espace vectoriel

ℝ^n

à sa base canonique

B = (e_1\to, e_2\to, \dots, e_n^(\to-))

. Dans la dernière question, on revient sur

ℂ

1. Exemple 1.

On définit l'endomorphisme f de

ℝ^n

vérifiant les conditions :

f(e_1\to) = e_2\to, f(e_2\to) = e_3\to, \dots, f(e_(n - 1)^(\to-)) = e_n^(\to-) et f(e_n^(\to-)) = 0\to.

a/ Pourquoi ces conditions définissent-elles f sans ambiguïté ? Déterminer la matrice A de f dans la base B, puis l'image, le rang et le noyau de f.
b/ Sans utiliser la méthode des traces, déterminer directement le polynôme caractéristique de f.
c/ Retrouver ce résultat en simulant la méthode des traces.

2. Exemple 2.

On définit l'endomorphisme f de

ℝ^n

vérifiant les conditions :

f(e_1^(\to-)) = e_2^(\to-), f(e_2^(\to-)) = e_3^(\to-), \dots, f(e_(n - 1)^(\to-)) = e_n^(\to-) et f(e_n^(\to-)) = e_1^(\to-).

Déterminer la matrice A de f dans la base B, puis l'image, le rang et le noyau de f. Sans utiliser la méthode des traces, déterminer directement le polynôme caractéristique de f. Retrouver ce résultat en simulant la méthode des traces.

3. Exemple 3.

On munit dans cette question

ℝ^n

de son produit scalaire canonique.
a/ Soit

u\to = (u_1, u_2, \dots, u_n)

un vecteur unitaire de

ℝ^n

. On définit l'endomorphisme f de

ℝ^n

comme étant la projection orthogonale sur la droite

D

engendrée par

u⃗

. Déterminer son image, son rang et son noyau. Sans utiliser la méthode des traces, déterminer directement le polynôme caractéristique de f (on choisira une base adaptée au problème).
b/ Déterminer la matrice

A

f

dans la base

B

en fonction des coefficients

u_1, u_2, \dots, u_n

. Justifier que

A^2 = A

. Retrouver le polynôme caractéristique de f en simulant la méthode des traces sur la matrice A .
4. Une application. On rétablit dans cette question un résultat classique de l'algèbre linéaire grâce - entre autres - à la méthode des traces.
a/ Soit A une matrice de

M_n(ℂ)

telle que

tr(A) = tr(A^2) = \dots = tr(A^n) = 0

. Déterminer

χ_A

. En déduire que 0 est la seule valeur propre de

A

. Démontrer alors que

A^n = [0]

.
b/ Soit maintenant une matrice

A

M_n(ℂ)

vérifiant

A^n = [0]

. Prouver que 0 est valeur propre de A et qu'il n'y en a pas d'autre.
c/ En déduire l'équivalence, valable pour tout A de

M_n(ℂ)

A^n = [0] \Leftrightarrow tr(A) = tr(A^2) = \dots = tr(A^n) = 0

Fin de l'énoncé.

Pas de description pour le moment

Commentaires• CCINP Mathématiques 2 TSI 2005

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...