Modélisation Mathématique et Méthodes d’Optimisation

Cours

Dr. Ali SAADA

Enseignant-Chercheur à Sup’Com
[email protected]
1
 l
A la mémoire de Patrick Lascaux
1943-2010

2
Table des matières :
Avant-propos 5
Partie I : Modélisation mathématique et résolution numérique de systèmes linéaires 6
I- Modèles mathématiques pour des problèmes de la physique, équations et 7
discrétisation :
I.1- Introduction : 7
I.2- Modèles mathématiques pour des problèmes de la physique : 7
I.2.a- Problèmes elliptiques : 8
I.2.b- Problèmes paraboliques : 8
I.2.c- Problèmes hyperboliques : 9
I.3- Discrétisation d’un modèle mathématique, cas d’un problème elliptique : 9
II- Méthodes de résolution des systèmes linéaires : 12
II.1- Quelques outils pour l’analyse d’une solution numérique des systèmes 12
linéaires :
II.1.a- Notations: 12
II.1.b- Rappels : 12
II.1.c- Normes matricielles : 13
II.1.d- Conditionnement : 16
II.1.e- Majorations des erreurs de résolution d’un système linéaire : 16
II.2- Méthodes numériques pour la résolution des systèmes linéaires : 18
II.2.a- Méthodes directes pour la résolution des systèmes linéaires : 18
i- Opérations élémentaires : 18
ii- Méthode de Gauss : 19
iii- Méthode LU : 20
iv- Méthode Crout : 20
v- Méthode Cholesky : 21
II.2.b- Méthodes itératives pour la résolution des systèmes linéaires : 21
i- Principe des méthodes itératives : 21
ii- Condition nécessaire et suffisante de convergence : 22
iii- Convergence d’une méthode itérative : 22
iv- Vitesse de convergence : 22
v- Méthodes itératives connues : 23

- Méthode de Jacobi : 23
- Méthode de Gauss-Seidel : 23
- Méthode de relaxation : 23
Partie II : Méthodes d’optimisation : 25
I- Introduction : 26
II- Optimisation sans contraintes : 29
II-1 Résultats d’existence et d’unicité du problème d’optimisation : 29
II-2 Recherche du minimum pour 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ). Algorithmes du gradient : 30
II.2.a Introduction : 30
II.2.b Eléments pour la construction des algorithmes du gradient : 30
II.2.c Algorithmes du gradient : 31
i- Introduction : 31
ii- Algorithme du gradient à pas fixe : 31

3
 iii- Algorithme du gradient à pas optimal : 32
iv- Algorithme du gradient conjugué : 33
v- Application : Etude et recherche du minimum de la
𝑓: ℝ𝑛 ⟶ ℝ
fonction 1 avec 𝐴 symétrique
𝑥 ⟼ ⟨𝐴𝑥|𝑥⟩ − ⟨𝑏|𝑥⟩
2
33
définie positive :
- Application de la méthode du gradient à pas fixe
pour la recherche de x̅ : 33
- Application de la méthode du gradient à pas optimal
pour la recherche de 𝑥̅ : 34
- Application de la méthode du gradient conjugué
pour la recherche de 𝑥̅ : 34
II-3 Algorithmes de recherche du minimum pour 𝑓 ∈ 𝒞 2 (ℝ𝑛 , ℝ): 35
II.3.a : Méthode de Newton : 35
II.3.b Méthodes de quasi-Newton : 36
i- Méthode de Broyden1 : 36
ii- Méthode de BFGS (Broyden2, Fletcher, Goldfarb et Shanno) : 37
III- Optimisation sous contraintes 37
III-1 Résultats d’existence et d’unicité: 37
III-2 Conditions d’optimalité simple: 38
III-3 Conditions d’optimalité en cas de contraintes d’égalité : 38
III-4 Conditions d’optimalité en cas de contraintes d’inégalité : 39
Bibliographie 40

1
https://en.wikipedia.org/wiki/Charles_George_Broyden
2
https://en.wikipedia.org/wiki/Charles_George_Broyden

4
Avant-Propos :
L'art de l'ingénieur a dans sa noble t\^ache le principe de trouver des solutions aux problèmes concrets
de l'humanité, d'innover les machines et d'en inventer, d'améliorer les procédures de fabrication et le
confort de la vie et d'apporter des réponses à certaines énigmes et questions existentielles. Il nécessite
un esprit éveillé, critique, au courant des hypothèses et de l'acheminement de la science ainsi que des
évolutions technologiques. Paradoxalement, bien qu'il soit l'art du concret, il ne trouve ses innovations
les plus fortes que dans les esprits à grande capacité d'abstraction, à l'image de celui d'un Newton et
d'un Einstein. Un des rôles des mathématiques est le développement de cet instinct d'abstraction qui
permet de remettre en cause des phénomènes qui paraissent établis depuis l'éternité d'une manière
rigoureuse. Le dialogue qu'elles instaurent entre la science et la technologie fertilise l'imagination de
l'ingénieur aussi bien dans le premier domaine que dans le second. En outre, les mathématiques offrent
par les modèles qu'elles traitent d'excellents outils pédagogiques et d'aide à la prise de décision pour
les phénomènes qu'elles mettent en équation qu'ils soient technologiques, économiques, financiers ou
sociaux.

Il est donc très important que les mathématiques "appliquées" soient enseignées en première année
des écoles d'ingénieurs avec un volume horaire conséquent et un contenu adéquat. Elles permettent
aux élèves d'avoir un regard critique et profond sur la science dispensées lors des cours de spécialité.

Ce document est partagé en deux parties. La première s’intéresse à la modélisation mathématique et

de certains problèmes algébriques qui lui sont liés, et la seconde à l’optimisation non linéaire. J'ai pris
plaisir de l’étoffer par des pauses ou des stations sur les rues d'autres arts en marge de l'art
mathématique. Il est en effet important à mes yeux que l'ingénieur fasse plus ample connaissance de
tout ce qui peut émouvoir l'humanité comme musique, peinture, poésie, danse, l'histoire, géographie
et j’en passe, pour que ses inventions ou ses innovations ne soient que causes de bien-être et de
bonheur pour lui à travers ce qu'il peut en procurer à autrui.

5
Partie I : Modélisation mathématique et résolution numérique de
systèmes linéaires

6
I- Modèles mathématiques pour des problèmes de la physique,
équations et discrétisation :
I.1- Introduction :
Beaucoup de problématiques théoriques et pratiques se traduisent par une représentation matricielle
et vectorielle issus de mesures ou de modèles mathématiques. En communication, nous pouvons citer
les matrices de corrélations qui sont issus des problèmes d’émission-réception pour détecter un signal
utile [1],[2]. Aussi, nous pouvons évoquer les systèmes algébriques obtenus par la considération des lois
de3 Kirchhoff4 relatives aux nœuds et aux mailles d’un filtre. D’autres problèmes se modélisent par des
équations différentielles ordinaires, telle que la dynamique des espèces, ou par des équations aux
dérivées partielles comme la propagation des ondes. La discrétisation de ces dernières équations, dites
de Maxwell5, qui n’ont de solutions analytiques que dans très peu de cas collégiens et académiques,
aboutit dans tous les cas à la résolution de systèmes linéaires qui peuvent être de tailles très
importantes. Le problème de résolution de ces équations est transféré alors dans le traitement du
système algébrique. Ne faut-il pas réussir à le résoudre convenablement ? Les algorithmes pour mener
cette action sont nombreux et sont de nos jours préprogrammés dans les codes numériques tel que
Matlab ou Scilab, mais faut-il que l’ingénieur saisisse leurs tenants et aboutissants pour qu’il finisse par
évaluer la qualité de la solution qu’ils proposent. Il peut paraitre utopique pour un non averti de
remettre en cause les calculs menés par l’ordinateur mais de simples exemples peuvent montrer que
l’alternative que l’ordinateur puisse donner de faux résultats sont là. Vous pouvez par exemple vérifier
sur Matlab ce que l’ordinateur donne comme solution pour le système algébrique 𝐴𝑥 = 𝑏, avec 𝐴 =
2 6 8 1 ∗
[ −𝑛 ] et 𝑏 = [ −𝑛 ]. La solution théorique 𝑥 = [ ] pour tout 𝑛 ∈ ℕ est loin d’être
2 6 + 10 8 + 10 1
obtenue pour tous les entiers naturels !!! Par ailleurs, pour le système équivalent avec 𝐴 =
2 6 8
[ −𝑛 ] et 𝑏 = [ ] le résultat est vérifié même pour des entiers « assez grands ». Pourquoi ?
0 10 10−𝑛
C’est une des questions à laquelle l’analyse numérique matricielle tente de répondre pour les différents
systèmes soumis à la résolution, sachant que l’origine de ces erreurs vient de cet ordinateur qui n’arrive
pas à représenter tous les nombres, les irrationnels à fortiori, et qui utilise la troncature pour évaluer
les valeurs numériques des variables.

I.2- Modèles mathématiques pour des problèmes de la physique :

Les modèles mathématiques pour les phénomènes physiques sont nombreux et se présentent sous
formes d’équations reliant, d’une manière empirique ou via des opérateurs mathématiques, différents
paramètres. Ce paragraphe est consacré à la présentation des trois classes connues des équations aux
dérivées partielles à savoir les équations elliptiques qui modélisent par exemple le phénomène de
fléchissement d’une poutre soumise à une charge, les équations paraboliques qui peuvent prendre en
considération les phénomènes transitoires pour un problème de propagation de la chaleur et les
problèmes hyperboliques tels que le problème de transport ou celui de la propagation d’une onde6.

3
https://fr.wikipedia.org/wiki/Lois_de_Kirchhoff
4
https://fr.wikipedia.org/wiki/Gustav_Kirchhoff
5
https://fr.wikipedia.org/wiki/James_Clerk_Maxwell
6
Les applications technologiques sont souvent un mixage de problèmes de différentes natures. Un élève
ingénieur, en télécommunication par exemple, doit tenir compte des phénomènes qui peuvent interagir avec
une onde ou modifier le comportement d’un composant électronique…. Un des buts du club Sup’Aire à Sup’Com
est justement d’améliorer cette culture indispensable pour compléter la formation académique

7
I.2.a- Problèmes elliptiques :
̅ = Ω ∪ 𝜕Ω. Soit x un point de
Soit Ω un domaine polygonal dans le plan de frontière 𝜕Ω et soit Ω
coordonnées (x1 , 𝑥2 ) ∈ Ω.. Soit aussi quatre fonctions de x, (𝑎𝑖𝑗 (𝑥)) que nous supposons
1≤𝑖,𝑗≤2
̅ → ℝ une fonction
continues et une fois continument dérivables par rapport à x1 et x2 . Soit encore 𝑓: Ω
continue donnée. Nous posons le problème de trouver 𝑢: Ω ̅ → ℝ satisfaisant les relations :

𝜕 𝜕
− ∑2𝑖,𝑗=1 𝜕𝑥 (𝑎𝑖𝑗 (𝑥) 𝜕𝑥 𝑢(𝑥)) = 𝑓(𝑥) ∀𝑥 ∈ Ω
{ 𝑖 𝑗 (1)
𝑢(𝑥) = 0 ∀𝑥 ∈ 𝜕Ω
𝜕
Où la notation 𝜕𝑥 désigne l’opération de dérivation partielle par rapport à la variable 𝑥𝑖 , 𝑖 = 1,2. Nous
𝑖
dirons que le problème (1) est un problème différentiel aux limites d’ordre 2. La condition limite étant
la seconde équation du système.

Le problème (1) est dit fortement elliptique si les fonctions (𝑎𝑖𝑗 (𝑥)) sont telles qu’il existe un
1≤𝑖,𝑗≤2
nombre positif α tel que ∀x ∈ Ω et ∀ξ = (𝜉1 , 𝜉2 ) ∈ ℝ2 , ∑2𝑖,𝑗=1 𝑎𝑖𝑗 (𝑥)𝜉𝑖 𝜉𝑗 ≥ 𝛼(𝜉1 2 + 𝜉2 2 ).

Remarquons que si le problème (1) est fortement elliptique pour tout x ∈ Ω, l’équation
en 𝜉1 , 𝜉2 donnée par 𝑎11 (𝑥)𝜉1 2 + (𝑎12 (𝑥) + 𝑎21 (𝑥))𝜉1 𝜉2 + 𝑎22 (𝑥)𝜉2 2 = 1 est l’équation d’une
ellipse, d’où la terminologie problème elliptique.

I.2.b- Problèmes paraboliques :

̅ = Ω ∪ 𝜕Ω. Soit aussi quatre
Soit Ω un domaine polygonal dans le plan, de frontière 𝜕Ω et soit Ω
̅ ×ℝ+ , (𝑎𝑖𝑗 (𝑥, 𝑡))
fonctions de (𝑥, 𝑡) ∈ Ω ̅ ×ℝ+ → ℝ et 𝑤: Ω
. Soient encore 𝑓: Ω ̅ → ℝ deux
1≤𝑖,𝑗≤2
̅ ×ℝ+ → ℝ satisfaisant les
autres fonctions données. Nous posons le problème de trouver 𝑢: Ω
relations suivantes :

𝜕𝑢 𝜕 𝜕
(𝑥, 𝑡) − ∑2𝑖,𝑗=1 (𝑎𝑖𝑗 (𝑥, 𝑡) 𝜕𝑥 𝑢(𝑥, 𝑡)) = 𝑓(𝑥, 𝑡) ∀𝑥 ∈ Ω, ∀𝑡 ∈ ℝ+
𝜕𝑡 𝜕𝑥𝑖 𝑗
(2)
𝑢(𝑥, 𝑡) = 0 ∀𝑥 ∈ 𝜕Ω, ∀𝑡 ∈ ℝ+
{ 𝑢(𝑥, 0) = 𝑤(𝑥) ∀𝑥 ∈ Ω

La deuxième équation de (2) est appelée condition aux limites alors que la troisième est appelée
condition initiale.

Nous dirons que le problème (2) est parabolique si les fonctions (𝑎𝑖𝑗 (𝑥, 𝑡)) sont telles qu’il
1≤𝑖,𝑗≤2
existe un nombre positif 𝛼 qui satisfasse, pour tout 𝑥 ∈ Ω, pour tout 𝑡 > 0 et pour tout couple de
réels (𝜉1 , 𝜉2 ) , la relation ∑2𝑖,𝑗=1 𝑎𝑖𝑗 (𝑥, 𝑡)𝜉𝑖 𝜉𝑗 ≥ 𝛼(𝜉1 2 + 𝜉2 2 )

Remarquons que si le problème (2) est parabolique pour tout x ∈ Ω et pour tout 𝑡 > 0, l’équation
en 𝜉1 , 𝜉2 , 𝜉3 donnée par 𝜉3 = 𝑎11 (𝑥, 𝑡)𝜉1 2 + (𝑎12 (𝑥, 𝑡) + 𝑎21 (𝑥, 𝑡))𝜉1 𝜉2 + 𝑎22 (𝑥, 𝑡)𝜉2 2 est l’équation
d’un paraboloïde d’axe 𝑂𝜉3 , d’où la terminologie problème parabolique.

8
I.2.c- Problèmes hyperboliques :
̅ = Ω ∪ 𝜕Ω. Soient :
Soit Ω un domaine polygonal dans le plan, de frontière 𝜕Ω et soit Ω

- ̅ ×ℝ+ → ℝ
𝑓: Ω
- ̅ → ℝ et
𝑤: Ω
- ̅→ℝ
𝑣: Ω

̅ ×ℝ+ → ℝ tel que :

Si 𝑐 est un nombre positif donné, nous posons le problème de 𝑢: Ω

𝜕2 𝑢
(𝑥, 𝑡) − 𝑐 2 ∆𝑢(𝑥, 𝑡) = 𝑓(𝑥, 𝑡) ∀𝑥 ∈ Ω, ∀𝑡 ∈ ℝ+
𝜕𝑡 2
𝑢(𝑥, 𝑡) = 0 ∀𝑥 ∈ 𝜕Ω, ∀𝑡 ∈ ℝ+ (3)
𝜕
{ 𝑢(𝑥, 0) = 𝑤(𝑥) 𝑒𝑡 𝑢(𝑥, 0) = 𝑣(𝑥) ∀𝑥 ∈ Ω
𝜕𝑡

Le problème (3) est appelé problème hyperbolique d’ordre deux. La première équation est une
équation aux dérivées partielles d’ordre deux en temps et en espace. La seconde équation est la
condition aux limites tandis que les deux dernières sont les conditions initiales.

𝜕2 𝑢 𝜕2 𝑢 𝜕2 𝑢
Remarquons que si nous remplaçons symboliquement 𝜕𝑡 2 par 𝑡 2 , 𝜕𝑥12
par 𝑥12 et 𝜕𝑥22
par 𝑥22 , alors la
première équation se réduit à , 𝑡 2 − 𝑐 2 𝑥12 − 𝑐 2 𝑥22 = 1 qui est l’équation d’une hyperboloïde, d’où le
nom de problème hyperbolique. Ces équations modélisent par exemple les vibrations d’une membrane
élastique ou d’un champ électrique.

I.3- Discrétisation d’un modèle mathématique, cas d’un problème

elliptique :
Dans ce qui suit, on considère l’équation de Poisson sur un intervalle ouvert et borné de ℝ. Elle modélise
de nombreux problèmes. Dans son expression la plus simple, dans un domaine unidimensionnel qui
représente une barre homogène et isotrope soumise à une source de chaleur 𝑓 et à qui on a imposé
aux bords des valeurs de températures données 𝑢(𝑎) et 𝑢(𝑏). Cette équation s’écrit :

−𝑢"(𝑥) = 𝑓(𝑥) dans ]𝑎, 𝑏[

{ 𝑢(𝑎) = 𝛼 (4)
𝑢(𝑏) = 𝛽

Les techniques de résolutions analytiques d’une telle équation sont connues et peuvent, même dans ce
cas simple, être compliquées, selon les propriétés de 𝑓. Numériquement, il existe plusieurs méthodes
pour trouver une bonne approximation de la solution. Les plus connues sont la méthode des différences
finies, la méthode des éléments finis et la méthode des volumes finis. La discrétisation de (4) par la
méthode des différences finies consiste à faire un développement de Taylor-Young de 𝑢, supposée être
un élément de 𝒞 2 ]𝑎, 𝑏[, au voisinage d’un ensemble de points (𝑥𝑖 )1≤𝑖≤𝑛 de ]𝑎, 𝑏[ .

Pour un ℎ « assez petit », les deux développements de Taylor-Young suivants de 𝑢 au voisinage de 𝑥 ∈

]𝑎, 𝑏[ donnent :

ℎ2
′ (𝑥)
𝑢(𝑥 + ℎ) = 𝑢(𝑥) + ℎ𝑢 + 𝑢"(𝑥) + ℎ2 𝜖𝑥 (ℎ) (5.1)
2
2
′ (𝑥)
ℎ
{𝑢(𝑥 − ℎ) = 𝑢(𝑥) − ℎ𝑢 + 𝑢"(𝑥) + ℎ2 𝜖̃𝑥 (ℎ) (5.2)
2

9
En les additionnant et en faisant les manipulations nécessaires, on obtient :

−𝑢(𝑥 − ℎ) + 2𝑢(𝑥) − 𝑢(𝑥 + ℎ)

−𝑢"(𝑥) = + 𝜖̌𝑥 (ℎ) (5.3)
ℎ2

où 𝜖̌ est une fonction telle que lim 𝜖̌𝑥 (ℎ) = 0.

ℎ→0

𝑏−𝑎
Par ailleurs, soit 𝑛 ∈ ℕ∗ , ℎ = 𝑛+1 et 𝑥𝑖 = 𝑎 + 𝑖ℎ pour 0 ≤ 𝑖 ≤ 𝑛 + 1. La formule (5.3) appliquée aux
éléments de la suite ( 𝑥𝑖 )1≤𝑖≤𝑛 aboutit, quand on néglige 𝜖̌𝑥𝑖 (ℎ), à l’écriture matricielle :

𝐴𝑢̅ = 𝑏 , avec

2 -1 0 … … … 0

-1 2 -1 0 ⋮

0 -1 2 -1 0 ⋮

1 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋮ ∈ 𝑀𝑛 (ℝ),
𝐴=
ℎ2

⋮ 0 -1 2 -1 0

⋮ 0 -1 2 -1

0 … … … 0 -1 2

𝛼 𝑢1
𝑓(𝑥1 ) +
ℎ2

𝑓(𝑥2 ) 𝑢2

⋮ ⋮

𝑏= ⋮ ∈ ℝ𝑛 et 𝑢̅ = ⋮ ∈ ℝ𝑛 ,

⋮ ⋮

𝑓(𝑥𝑛−1 ) 𝑢𝑛−1

𝛽 𝑢𝑛
𝑓(𝑥𝑛 ) +
ℎ2

où (𝑢𝑖 )1≤𝑖≤𝑛 est une approximation de (𝑢(𝑥𝑖 ))1≤𝑖≤𝑛 , vu que nous avons négligé 𝜖̌𝑥𝑖 (ℎ) dans (5.3).

10
Différentes techniques permettent de résoudre ce système linéaire. Certaines d’entre elles font l’objet
du prochain chapitre.

11
II- Méthodes de résolution des systèmes linéaires :
II.1- Quelques outils pour l’analyse d’une solution numérique des systèmes
linéaires :
Les algorithmes pour la résolution des systèmes linéaires arrivent à donner théoriquement la solution
du système linéaire 𝐴𝑢 = 𝑏 quand la matrice 𝐴 est inversible. Dans la pratique et à cause des erreurs
d’arrondi et de troncature de l’ordinateur, ces méthodes peuvent ne pas donner cette bonne solution.
Dans ce qui suit nous allons construire des outils qui nous permettent de majorer l’erreur obtenue pour
un système quelconque avec une matrice A inversible.

Dans toute la suite, 𝑛 est considéré comme étant un entier naturel strictement positif.

II.1.a- Notations:
Soit ( 𝑒𝑖 )1≤𝑖≤𝑛 la base canonique de ℝ𝑛 . Pour un vecteur 𝑥 = ∑𝑛𝑖=1 𝑥𝑖 𝑒𝑖 ∈ ℝ𝑛 , nous écrivons :

𝑥1

𝑥2

𝑥= ⋮ et 𝑥 𝑇 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) le transposé de 𝑥.

𝑥𝑛−1

𝑥𝑛

Pour 𝑀 = (𝑚𝑖𝑗 ) ∈ ℳ𝑛 (ℝ) une matrice carrée d’ordre 𝑛, nous désignons par 𝑀𝑇 =
1≤𝑖≤,𝑗≤𝑛
𝑇
(𝑚𝑖𝑗 ) = (𝑚𝑗𝑖 )1≤𝑖≤,𝑗≤𝑛 , la transposée de 𝑀,
1≤𝑖≤,𝑗≤𝑛

II.1.b- Rappels :
Nous notons le produit scalaire de deux vecteurs de ℝ𝑛 par 〈𝑥, 𝑦〉 = ∑𝑛𝑖=1 𝑥𝑖 𝑦𝑖 = 𝑥 𝑇 𝑦 et nous rappelons
que ∀𝜆 ∈ ℝ et ∀(𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛 , on a 〈𝜆𝑥, 𝑦〉 = 〈𝑥, 𝜆𝑦〉 = 𝜆〈𝑥, 𝑦〉.

Nous rappelons encore que la norme « vectorielle » est une application de ℝ𝑛 vers ℝ+ que nous notons
généralement ‖∙‖ et qui vérifie les trois propriétés suivantes :

- ∀𝑥 ∈ ℝ𝑛 , ‖𝑥‖ = 0 ⟺ 𝑥 = 0,
- ∀𝜆 ∈ ℝ, ∀𝑥 ∈ ℝ𝑛 , ‖𝜆𝑥‖ = |𝜆|‖𝑥‖ et
- ∀𝑥, 𝑦 ∈ ℝ𝑛 , ‖𝑥 + 𝑦‖ ≤ ‖𝑥‖ + ‖𝑦‖

Aussi, les normes usuelles sont :

- La norme indice 1, ‖𝑥‖1 = ∑𝑛𝑖=1|𝑥𝑖 |,

- La norme indice 2, ‖𝑥‖2 = √∑𝑛𝑖=1|𝑥𝑖 |2 , et
- La norme infinie, ‖𝑥‖∞ = max |𝑥𝑖 |.
1≤𝑖≤𝑛

12
Une matrice 𝑀 ∈ ℳ𝑛 (ℝ) est inversible, s’il existe 𝑁 ∈ ℳ𝑛 (ℝ) telle que 𝑀𝑁 = 𝑁𝑀 = 𝐼𝑛 . On
note 𝑁 = 𝑀−1 .

Nous rappelons que 𝑀 ∈ ℳ𝑛 (ℝ) inversible⟺ 𝑑𝑒𝑡(𝑀) ≠ 0 . Nous rappelons aussi qu’une matrice 𝑂 ∈
ℳ𝑛 (ℝ) est dite orthogonale si et seulement si 𝑂−1 = 𝑂𝑇 , autrement dit 𝑂𝑂𝑇 = 𝑂𝑇 𝑂 = 𝐼𝑛

𝜆 ∈ ℂ est une valeur propre de 𝑀 ∈ ℳ𝑛 (ℝ) si et seulement s’il existe 𝑥 ∈ ℂ𝑛 ∖ {0} tel que 𝑀𝑥 = 𝜆𝑥.
La plus grande valeur propre en module s’appelle rayon spectrale de 𝑀. L’ensemble des valeurs propres
d’une matrice 𝑀 ∈ ℳ𝑛 (ℝ) est noté 𝑠𝑝(𝑀). Le plus grand élément en module de 𝑠𝑝(𝑀) est appelé le
rayon spectral de 𝑀 et est noté 𝜌(𝑀) = max |𝜆𝑖 |.
𝜆𝑖 ∈𝑠𝑝(𝑀)

Nous appelons polynôme caractéristique d’une matrice 𝑀 ∈ ℳ𝑛 (ℝ) le polynôme de degré 𝑛,

𝜒𝑀 (𝜆) = 𝑑𝑒𝑡(𝑀 − 𝜆𝐼𝑛 ). Nous montrons que 𝜆 ∈ ℂ est une valeur propre de 𝑀 ∈ ℳ𝑛 (ℝ) si et
seulement si 𝜆 annule 𝜒𝑀 . En particulier, toute valeur de la diagonale d’une matrice triangulaire est une
valeur propre de cette matrice.

Nous disons qu’une valeur propre est d’ordre de multiplicité 1 si elle est racine simple du polynôme
caractéristique, nous disons qu’elle est d’ordre 𝑛 si c’est une racine de multiplicité 𝑛 en tant que zéro
du polynôme caractéristique.

Le déterminant d’une matrice 𝑀 ∈ ℳ𝑛 (ℝ) est le produit de ses valeurs propres en tenant compte de
leur ordre de multiplicité dans le polynôme caractéristique 𝑑𝑒𝑡(𝑀) = (∏𝑛𝑖=1 𝜆𝑖 ). En particulier, le
déterminant d’une matrice triangulaire est le produit des éléments de sa diagonale.

II.1.c- Normes matricielles :

La norme matricielle est une application de ℳ𝑛 (ℝ) dans ℝ+ que nous notons généralement |‖. ‖|. Elle
vérifie les quatre propriétés suivantes :

- ∀𝑀 ∈ ℳ𝑛 (ℝ), ‖𝑀‖ = 0 ⟺ 𝑀 = 0,
- ∀𝜆 ∈ ℝ, ∀𝑀 ∈ ℳ𝑛 (ℝ), ‖|𝜆𝑀|‖ = |𝜆|‖|𝑀|‖
- ∀𝑀, 𝑁 ∈ ℳ𝑛 (ℝ), ‖|𝑀 + 𝑁|‖ ≤ ‖|𝑀|‖ + ‖|𝑁|‖ et
- ∀𝑀, 𝑁 ∈ ℳ𝑛 (ℝ), ‖|𝑀𝑁|‖ ≤ ‖|𝑀|‖ ‖|𝑁|‖

Nous pouvons montrer que si ‖. ‖ est une norme vectorielle sur ℝ𝑛 , alors l’application |‖. ‖| définit sur
‖𝑀𝑥‖
ℳ𝑛 (ℝ) par ‖|𝑀|‖ = sup ‖𝑥‖
est une norme matricielle dite norme matricielle subordonnée à la
𝑥∈ ℝ𝑛 ,𝑥≠0
norme vectorielle ‖. ‖.

Remarques :

- Soit 𝐼𝑛 étant la matrice identité de ℳ𝑛 (ℝ). Pour toute norme subordonnée |‖. ‖|,
|‖𝐼𝑛 ‖| = 1.
- Soit 𝐴 une matrice de ℳ𝑛 (ℝ) et 𝑢 un vecteur de ℝ𝑛 . Pour toute norme subordonnée
|‖. ‖| associée à la norme vectorielle ‖. ‖, ‖𝐴𝑢‖ ≤ |‖𝐴‖| ‖𝑢‖.
1⁄
- L’application définit sur ℳ𝑛 (ℝ) par |‖𝑀‖| = (∑𝑛𝑖,𝑗=1 𝑚𝑖𝑗
2
) 2
, où 𝑀 = (𝑚𝑖𝑗 )1≤𝑖,𝑗≤𝑛 est une
norme, appelée norme de Schur, qui n’est subordonnée à aucune norme vectorielle.

13
Théorème :

- Soit |‖. ‖| est une norme matricielle quelconque, alors on a ∀𝑀 ∈ ℳ𝑛 (ℝ), 𝜌(𝑀) ≤
|‖𝑀‖|, 𝜌(𝑀) étant le rayon spectral de 𝑀.
- Soit 𝑀 ∈ ℳ𝑛 (ℝ). Pour tout 𝜀 > 0 il existe une norme subordonnée qu’on note |‖. ‖|𝑀,𝜀
telle que |‖𝑀‖|𝑀,𝜀 ≤ 𝜌(𝑀) + 𝜀

Preuve :

- Soient 𝑛 ∈ ℕ∗ , 𝑀 ∈ ℳ𝑛 (ℝ) et soit 𝜆 une valeur propre de 𝑀 telle que 𝜌(𝑀) = |𝜆| et soit
𝑢 ∈ ℝ𝑛 ∖ {0} un vecteur propre associé à 𝜆 (𝑀𝑢 = 𝜆𝑢). Soit 𝑣 ∈ ℝ𝑛 tel que 𝑢𝑣 𝑇 ≠ 0, on
a alors : 𝜌(𝑀)|‖ 𝑢𝑣 𝑇 ‖| = |‖ λ𝑢𝑣 𝑇 ‖| = |‖ A𝑢𝑣 𝑇 ‖| ≤ |‖ 𝐴‖| |‖ 𝑢𝑣 𝑇 ‖|.
- Je laisse au lecteur le soin de faire la preuve du second point.

Théorème :

Soient |‖. ‖| une norme matricielle et 𝐵 ∈ ℳ𝑛 (ℝ) telle que |‖𝐵‖| < 1, alors 𝐼𝑛 − 𝐵 est inversible et
vérifie :

- ( 𝐼𝑛 − 𝐵)−1 = ∑+∞ 𝑘
𝑘=0 𝐵 , et
1
- |‖( 𝐼𝑛 − 𝐵)−1 ‖| ≤ .
1−|‖𝐵‖|
- Réciproquement, si une matrice de la forme 𝐼𝑛 − 𝐵 est non inversible alors pour toute
norme matricielle |‖. ‖| on a |‖𝐵‖| ≥ 1.

Preuve :

- On pose 𝑆𝑛 = ∑𝑛𝑘=0 𝐵𝑘 . Montrons que (𝑆𝑛 )𝑛∈ℕ est une suite de Cauchy, donc
convergeante. On a : ∀(𝑀, 𝑁) ∈ ℕ×ℕ avec 𝑁 > 𝑀, |‖𝑆𝑁 − 𝑆𝑀 ‖|= |‖∑𝑁 𝑘
𝑘=𝑀+1 𝐵 ‖| ≤
∑𝑁 𝑘
𝑘=𝑀+1|‖𝐵‖| → 0. Donc (𝑆𝑛 )𝑛∈ℕ est convergeante. Notons 𝑠 sa limite. On a :
𝑀⟶+∞
𝑆(𝐼𝑛 − 𝐵) = (𝐼𝑛 − 𝐵)𝑆 = 𝐼 ⟹ 𝑆 = ∑+∞ 𝑘 −1
𝑘=0 𝐵 = (𝐼𝑛 − 𝐵) .
1−|‖𝐵‖|𝑁+1 1
- |‖𝑆𝑁 ‖|=|‖∑𝑁 𝑘 𝑁 𝑘
𝑘=0 𝐵 ‖| ≤ ∑𝑘=0|‖𝐵‖| = → .
1−|‖𝐵‖| 𝑁⟶+∞ 1−|‖𝐵‖|
- Si 𝐼𝑛 − 𝐵 est non inversible, alors 1 est valeur propre de 𝐵, alors |‖𝐵‖| ≥ 𝜌(𝐵) ≥ 1
∎

Corollaire :

1
Soient |‖. ‖| une norme matricielle et 𝐴 ∈ ℳ𝑛 (ℝ) inversible, alors la boule ouverte ℬ (𝐴, |‖𝐴−1 ‖|) =
1
{𝑀 ∈ ℳ𝑛 (ℝ), |‖𝑀 − 𝐴‖| < |‖𝐴−1 ‖|} est contenue dans l’ensemble des matrices inversibles.

Preuve :

1 1
Soit 𝑀 ∈ ℬ (𝐴, |‖𝐴−1 ‖|) = |‖𝑀 − 𝐴‖| < |‖𝐴−1 ‖| ⟹ |‖𝐼 − 𝐴−1 𝑀‖| ≤ |‖𝐴−1 ‖| |‖𝑀 −
𝐴‖| < 1 ⟹ 𝐴−1 𝑀 inversible ⟹ 𝑀 inversible.
∎

14
Théorème :

Soit 𝑀 ∈ ℳ𝑛 (ℝ). Les quatre propriétés suivantes sont équivalentes :

i- Il existe une norme subordonnée |‖ ‖| telle que |‖𝑀‖| < 1,

ii- lim |‖𝑀𝑘 ‖| = 0,
𝑘→+∞
iii- Pour tout 𝑦 ∈ ℝ𝑛 , lim ‖𝑀𝑘 𝑦‖ = 0,
𝑘→+∞
iv- Le rayon spectral 𝜚(𝑀) < 1l

Preuve :
𝑘
𝑖 ⇒ 𝑖𝑖 |‖𝑀𝑘 ‖| ≤ |‖𝑀‖|
⏟ ⟶ 0
𝑘→+∞
<1

𝑖𝑖 ⟹ 𝑖𝑖𝑖 ‖𝑀𝑘 𝑦‖ ≤ |‖𝑀𝑘 ‖| ‖𝑦‖ ⟶ 0,

𝑘→+∞

𝑖𝑖𝑖 ⟹ 𝑖𝑣 Soit 𝜆 ∈ ℂ/|𝜆| = 𝜚(𝑀), et soit 𝑦̅ ∈ ℂ𝑛 ∖ {0} tel que 𝑀𝑦 = 𝜆𝑦 alors ‖𝑀𝑘 𝑦‖ =
|𝜆|𝑘 ‖𝑦‖ ⟶ 0 ⟹ |𝜆| < 1.
𝑘→+∞

𝑖𝑣 ⟹ 𝑖 Nous avons vu que pour tout 𝜀 > 0 il existe une norme subordonnée qu’on note |‖. ‖|𝑀,𝜀 telle
1− 𝜌(𝑀)
que |‖𝑀‖|𝑀,𝜀 ≤ 𝜌(𝑀) + 𝜀, en particulier, pour 𝜀 = 2
il existe une norme subordonnée telle que
1− 𝜌(𝑀) 𝜌(𝑀)+1
|‖𝑀‖|𝑀,𝜀 ≤ 𝜌(𝑀) + = <1
2 2

Proposition :

Soit |‖. ‖| est une norme matricielle subordonnée. Pour tout 𝑀 ∈ ℳ𝑛 (ℝ), on a

1⁄𝑘
lim |‖𝑀𝑘 ‖| = 𝜌(𝑀)
𝑘→+∞

où 𝜌(𝑀) est le rayon spectral de 𝑀.

Preuve :

- Soit 𝜆 une valeur propre de 𝑀 telle que 𝜌(𝑀) = |𝜆| et soit 𝑢 ∈ ℝ𝑛 ∖ {0} un vecteur propre
associé à 𝜆 (𝑀𝑢 = 𝜆𝑢). On a :
1⁄𝑘
‖𝑀𝑘 𝑢‖ = ‖𝜆𝑘 𝑢‖ = |𝜆|𝑘 ‖𝑢‖ = 𝜌(𝑀)𝑘 ‖𝑢‖ ≤ |‖𝑀𝑘 ‖|‖𝑢‖ ⟹ 𝜌(𝑀) ≤ |‖𝑀𝑘 ‖|
𝑀 𝜌(𝑀) 𝑀 𝑘
- Réciproquement, pour 𝜀 > 0, 𝜌 (𝜀+𝜌(𝑀)) = 𝜀+𝜌(𝑀) < 1 ⟹ lim |‖(𝜀+𝜌(𝑀)) ‖| = 0 ⟹
𝑘→+∞
𝑀 𝑘 1⁄𝑘
(∃𝑁𝜀 ∕ 𝑘 > 𝑁𝜀 ⟹ |‖(𝜀+𝜌(𝑀)) ‖| < 1) ou encore que |‖𝑀𝑘 ‖| < 𝜀 + 𝜌(𝑀).

Donc

1⁄𝑘
∀𝜀 > 0, ∃𝑁𝜀 > 0 ∕ 𝑘 > 𝑁𝜀 ⟹ 𝜌(𝑀) ≤ |‖𝑀𝑘 ‖| < 𝜀 + 𝜌(𝑀)

15
II.1.d- Conditionnement :
Définition :

Soient |‖. ‖| une norme matricielle subordonnée et 𝑀 ∈ ℳ𝑛 (ℝ) inversible. Le nombre 𝑐𝑜𝑛𝑑(𝑀) =
|‖𝑀‖| |‖𝑀−1 ‖| est appelé le conditionnement de 𝑀 relativement à la norme |‖. ‖|.

Propriétés :

- 𝑐𝑜𝑛𝑑(𝑀) ≥ 1,
- ∀𝛼 ∈ ℝ∗ , 𝑐𝑜𝑛𝑑(𝛼𝑀) = 𝑐𝑜𝑛𝑑(𝑀)
- 𝑐𝑜𝑛𝑑(𝑀) = 𝑐𝑜𝑛𝑑(𝑀−1 ) ,
- Soit 𝑂 une matrice orthogonale, alors 𝑐𝑜𝑛𝑑2 (𝑂) = 1 et 𝑐𝑜𝑛𝑑2 (𝑂𝑀) = 𝑐𝑜𝑛𝑑2 (𝑀), avec
𝑐𝑜𝑛𝑑2 (𝑀) = |‖𝑀‖|2 |‖𝑀−1 ‖|2

Preuve :

- 1 = |‖𝐼‖| = |‖𝑀𝑀−1 ‖| ≤ |‖𝑀‖| |‖𝑀−1 ‖|,

1
- 𝑐𝑜𝑛𝑑(𝛼𝑀) == |‖𝛼𝑀‖| |‖(𝛼𝑀)−1 ‖| = |𝛼| |‖𝑀‖| |𝛼|
|‖𝑀−1 ‖| = 𝑐𝑜𝑛𝑑(𝑀),
- Evident,

‖𝑂𝑥‖2 √⟨𝑂𝑥 |𝑂𝑥 ⟩

- Soit 𝑂 une matrice orthogonale. On a : |‖𝑂‖|2 = sup = sup = 1. Comme
𝑥≠0 ‖𝑥‖2 𝑥≠0 √⟨𝑥 |𝑥 ⟩
𝑂−1 est orthogonale, alors nous avons aussi −1
|‖𝑂 ‖|2 = 1 .

‖𝑂𝑀𝑥‖2 √⟨𝑂𝑀𝑥 |𝑂𝑀𝑥 ⟩ √⟨𝑀𝑥 |𝑀𝑥 ⟩

|‖𝑂𝑀‖|2 = sup = sup = sup = |‖𝑀‖|2 et
𝑥≠0 ‖𝑥‖2 𝑥≠0 √⟨𝑥 |𝑥 ⟩ 𝑥≠0 √⟨𝑥 |𝑥 ⟩
|‖(𝑂𝑀)−1 ‖|2 = |‖𝑀−1 𝑂−1 ‖|2 = |‖𝑀−1 ‖|2.

II.1.e- Majorations des erreurs de résolution d’un système linéaire :

Exemple :

10 78 7 32 0.1
Soit 𝐴 = [ 7 56 5 ], 𝑏 = [23] et 𝛿𝑏 = [ −0.1 ]. Les solutions des systèmes linéaires 𝐴𝑥 = 𝑏
1
8 6
10 9 33 0.1
7 59 10 31 −0.1
1 9.2
et 𝐴𝑥2 = 𝑏 + 𝛿𝑏 sont 𝑥1 = [1] et 𝑥2 = [−12.6]. Ainsi une petite perturbation dans le second membre
1 4.5
1 −1.1
‖𝛿𝑏‖
peut générer une grande perturbation dans la solution. Dans ce cas précis, On a ‖𝑏‖ ∞ ≃ 0,00303 et
∞
‖𝛿𝑥‖∞
‖𝑥‖∞
= 13,6. Il est donc important de savoir l’impact du aux erreurs de troncature sur la solution d’un
système.

16
Théorème :

Soient |‖. ‖| une norme matricielle subordonnée à une norme vectorielle ‖∙‖, 𝐴 ∈ ℳ𝑛 (ℝ) inversible
et 𝑏 et 𝛿𝑏 deux vecteurs de ℝ𝑛 avec 𝑏 ≠ 0. On considère 𝑥 et 𝛿𝑥 tels que 𝐴𝑥 = 𝑏 (6) et
𝐴(𝑥 + 𝛿𝑥) = 𝑏 + 𝛿𝑏 (7), alors on a :

‖𝛿𝑥‖ ‖𝛿𝑏‖
≤ 𝑐𝑜𝑛𝑑(𝐴)
‖𝑥‖ ‖𝑏‖

Preuve :

𝐴𝑥 = 𝑏 ⟹ ‖𝑏‖ ≤ |‖𝐴‖| ‖𝑥‖ (∗)

Par ailleurs, (7) − (6) ⟹ 𝐴 𝛿𝑥 = 𝛿𝑏 ⟹ 𝛿𝑥 = 𝐴−1 𝛿𝑏 ⟹ ‖ 𝛿𝑥‖ ≤ |‖𝐴−1 ‖| ‖𝛿𝑏‖ (∗∗).

(∗)×(∗∗) ⟹ le résultat.

Théorème :

Soient |‖. ‖| une norme matricielle subordonnée à une norme vectorielle ‖∙‖, 𝐴 ∈ ℳ𝑛 (ℝ) inversible,
𝛿𝐴 ∈ ℳ𝑛 (ℝ) et 𝑏 ∈ ℝ𝑛 . On considère 𝑥 et 𝛿𝑥 tels que 𝐴𝑥 = 𝑏 (8) et (𝐴 + 𝛿𝐴)(𝑥 + 𝛿𝑥) = 𝑏 (9).
On a alors:

‖ 𝛿𝑥‖ |‖𝛿𝐴‖|
≤ 𝑐𝑜𝑛𝑑(𝐴)
‖𝑥 + 𝛿𝑥‖ |‖𝐴‖|

Preuve :

(9) − (8) ⟹ 𝐴𝛿𝑥 + 𝛿𝐴(𝑥 + 𝛿𝑥) = 0 ⟹ 𝛿𝑥 = −𝐴−1 𝛿𝐴(𝑥 + 𝛿𝑥)

⟹ ‖ 𝛿𝑥‖ ≤ |‖𝐴−1 ‖| |‖𝛿𝐴‖| ‖𝑥 + 𝛿𝑥‖

‖ 𝛿𝑥‖ |‖𝛿𝐴‖|
⟹ ≤ 𝑐𝑜𝑛𝑑(𝐴)
‖𝑥 + 𝛿𝑥‖ |‖𝐴‖|

Théorème :

Soient |‖. ‖| une norme matricielle subordonnée à une norme vectorielle ‖∙‖, 𝐴 ∈ ℳ𝑛 (ℝ) inversible,
1
𝛿𝐴 ∈ ℳ𝑛 (ℝ) telle que |‖𝛿𝐴‖| < et (𝑏, 𝛿𝑏) ∈ ℝ𝑛 ∗ × ℝ𝑛 . On considère 𝑥 et 𝛿𝑥 tels
|‖𝐴−1 ‖|
que 𝐴𝑥 = 𝑏 (10) et (𝐴 + 𝛿𝐴)(𝑥 + 𝛿𝑥) = 𝑏 + 𝛿𝑏 (11). On a alors :

‖ 𝛿𝑥‖ 1 ‖𝛿𝑏‖ |‖𝛿𝐴‖|

≤ 𝑐𝑜𝑛𝑑(𝐴) −1 ( + )
‖𝑥‖ 1 − |‖𝛿𝐴‖||‖𝐴 ‖| ‖𝑏‖ |‖𝐴‖|

Preuve :

(11) − (10) ⟹ (𝐴 + 𝛿𝐴) 𝛿𝑥 + 𝛿𝐴 𝑥 = 𝛿𝑏

17
 ⟹ 𝐴(𝐼 + 𝐴−1 𝛿𝐴) 𝛿𝑥 + 𝛿𝐴 𝑥 = 𝛿𝑏
−1
⟹ 𝛿𝑥 = −(𝐴(𝐼 + 𝐴𝛿𝐴)) (𝛿𝐴 𝑥 + 𝛿𝑏)

⟹ ‖ 𝛿𝑥‖ ≤ |‖(𝐼 + 𝐴𝛿𝐴)−1 ‖| |‖𝐴−1 ‖|(|‖𝛿𝐴‖|‖𝑥‖ + ‖𝛿𝑏‖)

‖ 𝛿𝑥‖ ‖𝛿𝑏‖
⟹ ≤ |‖(𝐼 + 𝐴𝛿𝐴)−1 ‖| |‖𝐴−1 ‖| (|‖𝛿𝐴‖| + )
‖𝑥‖ ‖𝑥‖

‖ 𝛿𝑥‖ 1 |‖𝛿𝐴‖| ‖𝛿𝑏‖

⟹ ≤ 𝑐𝑜𝑛𝑑(𝐴) −1 ( + )
‖𝑥‖ 1 − |‖𝛿𝐴‖||‖𝐴 ‖| |‖𝐴‖| |‖𝐴‖|‖𝑥‖

Le résultat est alors obtenu en remarquant que (10) ⟹ ‖𝑏‖ ≤ |‖𝐴‖|‖𝑥‖

II.2- Méthodes numériques pour la résolution des systèmes linéaires :

Il existe deux classes de méthodes pour la résolution d’un système linéaire 𝐴𝑥 = 𝑏 avec 𝐴 inversible. La
première classe est la classe des méthodes directes qui consiste à transformer le système en un autre
qui lui est équivalent et facile à résoudre, et l’autre est la classe des méthodes itératives qui consiste à
construire une suite de vecteurs (𝑥 (𝑖) )𝑖∈ℕ convergente vers la solution 𝑥 du système. Dans toute la
suite, la matrice 𝐴 du système linéaire est considérée inversible.

II.2.a- Méthodes directes pour la résolution des systèmes linéaires :

Pour les méthodes directes, la méthode de base pour la résolution des système linéaires est celle de
Gauss. Son but est de transformer le système linéaire 𝐴𝑢 = 𝑏 en un autre équivalent 𝑇𝑢 = 𝑐 où 𝑇 est
une matrice triangulaire supérieur. La résolution de ce dernier système est facile à traiter par
l’algorithme de la remontée qui consiste à calculer d’une manière itérative les composantes de 𝑢 en
commençant par 𝑢𝑛 . Cet algorithme s’obtient en exprimant l’égalité entre les composantes du
vecteur 𝑇𝑢 et du vecteur 𝑐, (𝑇𝑢)𝑖 = 𝑐𝑖 , pour 𝑖 = 1, … , 𝑛, ⟺ ∑𝑛𝑗=1 𝑇𝑖𝑗 𝑢𝑗 = 𝑐𝑖 pour 𝑖 = 1, … , 𝑛 ou
encore en tenant compte de la forme triangulaire de 𝑇, ∑𝑛𝑗=𝑖 𝑇𝑖𝑗 𝑢𝑗 = 𝑐𝑖 pour 𝑖 = 1, … , 𝑛, c’est à dire
𝑐 𝑐𝑛−1 −𝑇𝑛−1,𝑛 𝑢𝑛
𝑢𝑛 = 𝑇 𝑛 , 𝑢𝑛−1 = 𝑇𝑛−1,𝑛−1
,… Par ailleurs, (𝐴𝑢 = 𝑏 ⟺ 𝑇𝑢 = 𝑐) ⟺ ∃𝐿 ∈ ℳ𝑛 (ℝ) inversible, telle
𝑛𝑛

que 𝐿𝐴 = 𝑇 et 𝐿𝑏 = 𝑐. La construction d’une telle matrice se fait par opérations successives dont les
détails font l’objet du paragraphe qui suit.

- Opérations élémentaires :
Soient 𝛼 ∈ ℝ, (𝑖0 , 𝑗0 ) ∈ ℕ2 et 𝐴 ∈ ℳ𝑛 (ℝ).

- Pour 𝑗0 < 𝑖0 , on définit 𝐸𝛼,𝑖0 ,𝑗0 = 𝐼𝑛 + 𝐵𝛼,𝑖0 ,𝑗0 ∈ ℳ𝑛 (ℝ) avec (𝑏𝛼,𝑖0 ,𝑗0 ) =
𝑖𝑗
𝛼 si (𝑖, 𝑗) = (𝑖0 , 𝑗0 )
{ , alors la matrice 𝐴̃ = 𝐸𝛼,𝑖0 ,𝑗0 𝐴 est telle que 𝑎̃𝑖𝑗 =
0 sinon
𝛼𝑎𝑗 ,𝑗 + 𝑎𝑖0 ,𝑗 si 𝑖 = 𝑖0
{ 0 , autrement dit les lignes de la matrice produit ̃ 𝐴 sont
𝑎𝑖𝑗 si 𝑖 ≠ 𝑖0
exception faite pour la ligne 𝑖0 les mêmes lignes que 𝐴. 𝐿𝑖0 ( ̃ 𝐴 ) = 𝛼𝐿𝑗0 (𝐴) + 𝐿𝑖0 (𝐴), où
𝐿𝑖 ( ̃
0
𝐴 ) est la 𝑖0 −ème ligne de ̃ 𝐴 , 𝐿𝑗 (𝐴) est la 𝑗0 −ème ligne de 𝐴 et 𝐿𝑖 (𝐴) est la
0 0
𝑖0 −ème ligne de 𝐴.

18
 Remarque :
𝑑𝑒𝑡(𝐸𝛼,𝑖0 ,𝑗0 ) = 1 ≠ 0 ⟹ 𝐸𝛼,𝑖0 ,𝑗0 inversible
𝛿𝑖𝑗 si 𝑖 ≠ 𝑖0 et 𝑖 ≠ 𝑗0
- Soit 𝑃𝑖0 𝑗0 ∈ ℳ𝑛 (ℝ), telle que 𝑝𝑖𝑗 = { 𝑗𝑗0 si
𝛿 𝑖 = 𝑖0 , alors la matrice 𝐴̃ =
𝛿𝑖𝑖0 si 𝑖 = 𝑗0
𝑎𝑖𝑗 si 𝑖 ≠ 𝑖0 et 𝑖 ≠ 𝑗0
𝑃𝑖𝑗 𝐴 est telle que 𝑎̃𝑖𝑗 = {𝑎𝑗0 𝑗 si 𝑖 = 𝑖0
𝑎𝑖0𝑗 si 𝑖 = 𝑗0
Remarque :
𝑑𝑒𝑡(𝑃𝑖𝑗 ) = (−1)|𝑖−𝑗| ≠ 0 ⟹ 𝑃𝑖𝑗 inversible

- Méthode de Gauss :
(𝑛)
Soit 𝐴 = 𝑀(𝑛) ∈ ℳ𝑛 (ℝ) inversible, il existe alors 𝑖0 ∈ ⟦1, 𝑛⟧/𝑚𝑖0 1 ≠ 0 ⟹ le coefficient
̃
𝑚(𝑛)11 = 𝑚𝑖0 1 de la matrice ̃
(𝑛)
𝑀(𝑛) = 𝑃1𝑖0 𝑀(𝑛) est donc non nul. Ceci entraîne que La famille de

matrices (𝐸 ̃
(𝑛) ) existe et la matrice 𝐴(1) = (∏𝑛𝑖=2 𝐸 𝑚
(𝑛) )̃
𝑀(𝑛) est égale
𝑚11
(− ̃ ),𝑖,1 (− 11
(𝑛) ),𝑖,1
(𝑛) 𝑚
𝑚𝑖1 𝑖1
2≤𝑖≤𝑛
̃
𝑚(1)11 ̃
𝑚(1)12 … ̃
𝑚(1)1𝑛
à 0 avec 𝑀(𝑛−1) ∈ ℳ𝑛−1 (ℝ) inversible car 0 ≠ 𝑑𝑒𝑡( 𝐴(1) ) =
⋮ [ (𝑛−1) ]
𝑀
[ 0 ]

𝑑𝑒𝑡 (∏𝑛𝑖=2 𝐸 ̃
(𝑛) )̃
𝑀(𝑛) = ∏𝑛𝑖=2 𝑑𝑒𝑡 (𝐸 ̃
(𝑛) ) 𝑑𝑒𝑡 ̃
𝑀(𝑛) = ±𝑑𝑒𝑡(𝑀(𝑛) ) =
𝑚11 𝑚11
(− ̃ ),𝑖,1 (− ̃ ),𝑖,1
(𝑛) (𝑛)
𝑚𝑖1 𝑚𝑖1
( )
̃
𝑚(1)11 𝑑𝑒𝑡( 𝑀(𝑛−1) ). Ceci implique qu’un des éléments de la première colonne de 𝑀(𝑛−1) est non
nul et nous pouvons alors réitérer la démarche précédente, autrement dit, il existe une famille de
matrices triangulaires inférieures telles que leur produit avec 𝑀(𝑛−1) donne une matrice dont les
éléments sous diagonaux de la première colonne sont nuls.

Illustration :

5 6 −3 2 16
Soit à résoudre le système linéaire 𝐴𝑢 = 𝑏 avec 𝐴 = [ 1 1.2 6 −4 ] et 𝑏 = [ 5.4]
−1 −1 2 0 3
3 1 2 −5 −9

1 0 0 0
− 1⁄5 1 0 0
Soit 𝐿1 = 𝐸−3⁄5,4,1 𝐸1⁄5,3,1 𝐸−1⁄5,2,1 =[ ] On a alors 𝐿1 𝐴𝑢 = 𝐿1 𝑏 qui s’écrit :
1⁄5 0 1 0
− 3⁄5 0 0 1

19
 5 6 −3 2 𝑢1 16
𝑢
6.6 −4.4] [ 2 ] = [ 2.2] ⇔
[ 0 0
0 0.2 1.4 0.4 𝑢3 6.2
0 −2.6 3.8 −6.2 𝑢 4 −18.6
1 0 0 0 5 6 −3 2 𝑢1 1 0 0 0 16
[0 0 0 1][ 0 0 6.6 −4.4] [𝑢2 ] = [0 0 0 1 ] [ 2.2] ⇔
0 0 1 0 0 0.2 1.4 0.4 𝑢3 0 0 1 0 6.2
0 1 0 0 0 −2.6 3.8 −6.2 𝑢4 0 1 0 0 −18.6
5 6 −3 2 𝑢1 16
0 −2.6 𝑢
3.8 −6.2] [ 2 ] = [−18.6] ⇔
[
0 0.2 1.4 0.4 𝑢3 6.2
0 0 6.6 −4.4 𝑢4 2.2

1 0 0 0 5 6 −3 2 𝑢1
0 1 0 0 ] [ 0 −2.6 𝑢
3.8 −6.2] [ 2 ]
[
0 0.2⁄2.6 1 0 0 0.2 1.4 0.4 𝑢3
0 0 0 1 0 0 6.6 −4.4 𝑢4
1 0 0 0 16
=[ 0 1 0 0 ] [−18.6] ⇔
0 0.2⁄2.6 1 0 6.2
0 0 0 1 2.2

5 6 −3 2 𝑢1 16
3.8 −6.2 𝑢 −18.6
[0 −2.6 ] [ 2] = [ ]⇔
0 0 1.6923 −0.0769 𝑢3 4.7892
0 0 6.6 −4.4 𝑢4 2.2
5 6 −3 2 𝑢1 16
3.8 −6.2 𝑢 −18.6
[0 −2.6 ] [ 2] = [ ]
0 0 1.6923 −0.0769 𝑢3 4.7892
0 0 0 −4.1 𝑢4 −16.4

Et avec la remontée nous obtenons 𝑢4 = 4, 𝑢3 = 3, 𝑢2 = 2 et 𝑢1 = 1.

- Méthode LU
Nous avons vu ci-dessus, que nous pouvons transformer un système linéaire 𝐴𝑢 = 𝑏, en un
système 𝑈𝑢 = 𝑐, avec 𝑈 triangulaire supérieure. On a : 𝑈 = ∏ 𝐿̃𝑖 𝑃𝑖 𝐴 où les matrices 𝐿̃𝑖 sont
triangulaires inférieures et les 𝑃𝑖 des matrices de permutation. Nous pouvons montrer que le produit
∏ 𝐿̃𝑖 𝑃𝑖 peut s’écrire ∏ 𝐿̃𝑖 𝑃𝑖 = 𝐿̅𝑃 avec 𝐿̅ une matrice triangulaire inférieure à diagonale unité et 𝑃 une
matrice de permutation. Ainsi, nous pouvons écrire 𝑈 = 𝐿̅𝑃𝐴 ou encore 𝐿𝑈 = 𝑃𝐴 avec 𝐿 = 𝐿̅ est une
matrice triangulaire inférieure à diagonale unité. Ainsi 𝐴𝑢 = 𝑏 ⇔ 𝑃𝐴𝑢 = 𝑃𝑏 = 𝑐 ⇔ 𝐿𝑈𝑢 = 𝑐. On
résout après par une descente 𝐿𝑣 = 𝑐, avant de déterminer 𝑢 par la résolution de 𝑈𝑢 = 𝑣.

Remarques :

- 𝑑𝑒𝑡(𝐿) = 1 et 𝑑𝑒𝑡(𝑈) = ±𝑑𝑒𝑡(𝐴) ≠ 0

- Nous pouvons écrire 𝑈 = 𝐷𝑉 où 𝐷 est une matrice diagonale formée par les éléments
diagonaux de 𝑈 et 𝑉 une matrice triangulaire supérieure à diagonale unité.

- Méthode Crout
Soit 𝐴 une matrice inversible symétrique. Supposons qu’il existe une matrice de permutation
𝑃 telle que 𝑃𝐴 = 𝐿𝑈. Supposons que nous pouvons écrire 𝐿𝑈 = 𝐿𝐷𝑉, où 𝐷 est une matrice diagonale

20
dont les éléments sont les éléments diagonaux de 𝑈 , et 𝑉 est une matrice triangulaire supérieure où
les lignes sont les lignes de 𝑈 divisées par leurs coefficients diagonaux. Supposons que 𝐴 admette une
décomposition 𝐿𝑈 sans avoir recourt à une permutation. Autrement dit que 𝐴 = 𝐿𝑈 = 𝐿𝐷𝑉 . Cette
décomposition est unique. Si 𝐴 est symétrique alors 𝐴 = 𝐴𝑇 ⟹ 𝐿𝐷𝑉 = 𝑉 𝑇 𝐷𝐿𝑇 ⇒ 𝑉 = 𝐿𝑇 ⇒ 𝐴 =
𝐿𝐷𝐿𝑇 . C’est la décomposition de Croût.

- Méthode Cholesky
Proposition : Soit 𝐴 symétrique définie positive, alors les éléments diagonaux de 𝐷 dans la
décomposition de Croût sont positifs.

Preuve :

On a ∀𝑥 ∈ ℝ𝑛 ∖ {0}, 〈𝐴𝑥, 𝑥〉 > 0 ⟹ 〈 𝐿𝐷𝐿𝑇 𝑥, 𝑥〉 = 〈 𝐷𝐿𝑇 𝑥, 𝐿𝑇 𝑥〉 > 0. En posant 𝑦 = 𝐿𝑇 𝑥, on a ∀𝑦 ∈

ℝ𝑛 ∖ {0}, 〈 𝐷𝑦, 𝑦〉 > 0 ⇒ ∑𝑛𝑖=1 𝑑𝑖𝑖 𝑦𝑖2 > 0, d’où le résultat.

Ceci implique que si 𝐴 est symétrique définie positive, alors 𝐴 = 𝐿𝐷𝐿𝑇 = 𝐿√𝐷√𝐷𝐿𝑇 = 𝐵𝐵𝑇 , avec
𝐵 matrice triangulaire inférieure à diagonale positive. C’est la décomposition de Cholesky.

Illustration :

2 −1 0
Soit 𝐴 = [−1 2 −1].
0 −1 2
𝑥1 2𝑥1 − 𝑥2 𝑥1
𝐴 est définie positive. En effet, pour tout 𝑥 = [𝑥2 ] ∈ ℝ𝑛 ∖ {0}, 〈𝐴𝑥, 𝑥〉 = 〈[−𝑥1 + 2𝑥2 − 𝑥3 ] , [𝑥2 ]〉 =
𝑥3 −𝑥2 + 2𝑥3 𝑥3
𝑥12 + 𝑥12 − 2𝑥1 𝑥2 + 𝑥22 + 𝑥22 − 2𝑥2 𝑥3 + 𝑥32 + 𝑥32 > 0. Ceci implique qu’il existe 𝐵 triangulaire
inférieure à diagonale positive telle que 𝐴 = 𝐵𝐵𝑇 .

𝑚𝑖𝑛(𝑖,𝑗)
𝑇
𝐴 = 𝐵𝐵 ⇒ 𝑎𝑖𝑗 = ∑ 𝑏𝑖𝑘 𝑏𝑗𝑘
𝑘=1

2 −1
Ceci implique que 𝑎11 = 𝑏11 ⇒ 𝑏11 = √2 et on a 𝑎21 = 𝑏21 𝑏11 ⇒ 𝑏21 = et 𝑎31 = 𝑏31 𝑏11 ⇒ 𝑏31 =
√2
0.

2 2 1 √3 2
𝑎22 = 𝑏21 + 𝑏22 ⇒ 𝑏22 = √2 − 2 = 2
et 𝑎32 = 𝑏31 𝑏12 + 𝑏32 𝑏22 ⇒ 𝑏32 = − et enfin,
√3

2 2 2 4 2
𝑎33 = 𝑏31 + 𝑏32 + 𝑏33 ⟹ 𝑏33 = √2 − 3 = √3.

II.2.b- Méthodes itératives pour la résolution des systèmes linéaires :

Les méthodes itératives pour la résolution des systèmes linéaires sont des méthodes de construction
de suites de vecteurs susceptibles de converger vers la solution du problème.

21
Principe des méthodes itératives :
Soit à résoudre le système linéaire 𝐴𝑥 = 𝑏 avec 𝐴 ∈ ℳ𝑛 (ℝ) inversible. Soient 𝑀 ∈ ℳ𝑛 (ℝ) facilement
inversible et 𝑁 ∈ ℳ𝑛 (ℝ) telles que 𝐴 = 𝑀 − 𝑁. Le principe des méthodes itératives est de construire
une suite de vecteurs (𝑥 (𝑘) )𝑘∈ℕ de ℝ𝑛 selon l’algorithme :

(0)
∈ ℝ𝑛
{ 𝑥 (𝑘+1) donné
𝑀𝑥 = 𝑁𝑥 (𝑘) + 𝑏

Condition nécessaire et suffisante de convergence :

Nous pouvons remarquer que si l’algorithme précédent converge, alors il converge vers la solution du
système. En effet, si lim 𝑥 (𝑘) = 𝑥̅ , alors lim (𝑀𝑥 (𝑘+1) = 𝑁𝑥 (𝑘) + 𝑏) ⇒ 𝑀𝑥̅ = 𝑁𝑥̅ + 𝑏 ⇒ 𝐴𝑥̅ = 𝑏.
𝑘→+∞ 𝑘→+∞

Convergence d’une méthode itérative :

Théorème :

Soient 𝐴, ∈ ℳ𝑛 (ℝ) inversible et 𝑏 ∈ ℝ𝑛 . La méthode itérative relative à la décomposition 𝐴 = 𝑀 − 𝑁

pour la résolution du système linéaire 𝐴𝑥 = 𝑏 converge si et seulement si 𝜌(𝑀−1 𝑁) < 1 .

Preuve :
(0)
- Supposons que la suite générée par l’algorithme { 𝑥 (𝑘+1) ∈ ℝ𝑛 donné converge
𝑀𝑥 = 𝑁𝑥 (𝑘) + 𝑏
vers un vecteur 𝑥̃ ∈ ℝ𝑛 . Alors on a 𝑀𝑥̃ = 𝑁𝑥̃ + 𝑏 . Ainsi 𝑀(𝑥̃ − 𝑥 (𝑘+1) ) = 𝑁(𝑥̃ − 𝑥 (𝑘) ) ou
encore 𝑥̃ − 𝑥 (𝑘+1) = 𝑀−1 𝑁(𝑥̃ − 𝑥 (𝑘) ). En posant 𝑀−1 𝑁 = 𝐵, on a :
𝑥̃ − 𝑥 (𝑘+1) = 𝐵(𝑥̃ − 𝑥 (𝑘) ) = 𝐵2 (𝑥̃ − 𝑥 (𝑘−1) ) = ⋯ = 𝐵𝑘−1 (𝑥̃ − 𝑥 (0) ).
lim 𝑥̃ − 𝑥 (𝑘+1) = 0 = lim 𝐵𝑘−1 (𝑥̃ − 𝑥 (0) ) , ∀𝑥 (0) ∈ ℝ𝑛 , alors, d’après le théorème
𝑘→+∞ 𝑘→+∞
précédent, 𝜌(𝐵) < 1.
- Réciproquement, posons encore une fois 𝐵 = 𝑀−1 𝑁 et supposons que 𝜌(𝐵) < 1.
𝜌(𝐵) < 1 implique qu’il existe une norme subordonnée |‖ ‖| telle que |‖𝐵‖| < 1 ⟹ 𝐼 −
𝐵 est inversible. Considérons maintenant 𝑥̅ ∈ ℝ𝑛 solution du système (𝐼 − 𝐵)𝑥̅ = 𝑀−1 𝑏.
On a donc 𝑥̅ = 𝐵𝑥̅ + 𝑀−1 𝑏 = 𝑀−1 𝑁𝑥̅ + 𝑀−1 𝑏 ⇒ 𝑀𝑥̅ = 𝑁𝑥̅ + 𝑏 ⇒ 𝑥̅ − 𝑥 (𝑘+1) =
𝑀−1 𝑁(𝑥̅ − 𝑥 (𝑘) ), où encore 𝑥̅ − 𝑥 (𝑘+1) = 𝐵𝑘−1 (𝑥̅ − 𝑥 (0) ) qui tend vers zéro quand 𝑘
tend vers l’infini. Donc la suite converge vers 𝑥̅

Remarque :

La matrice 𝐵 = 𝑀−1 𝑁 est dite matrice d’itération de la méthode itérative.

‖𝐵𝑘 𝑢‖
Soit 𝜆 ∈ ℂ⁄𝜌(𝐵) = |𝜆| et soit 𝑢 ∈ ℂ𝑛 ∖ {0}⁄𝐵𝑢 = 𝜆𝑢 ⟹ ‖𝐵𝑘 𝑢‖ = ‖𝜆𝑘 𝑢‖ = 𝜌(𝐵)𝑘 ‖𝑢‖ ⟹ ‖𝑢‖
=
𝜌(𝐵)𝑘 ≤ ‖|𝐵|‖𝑘 .

Vitesse de convergence :
La méthode itérative construit une suite ( 𝑥 (𝑘) ) 𝑘∈ℕ , telle que 𝑥 (𝑘) = (𝑀−1 𝑁)𝑥 (𝑘−1) + (𝑀−1 𝑏) . En
posant 𝐵 = 𝑀−1 𝑁 et 𝑐 = 𝑀−1 𝑏, on a :

𝑥 (𝑘) = 𝐵𝑥 (𝑘−1) + 𝑐

22
Et en cas de convergence, on a :

𝑥̅ = 𝐵𝑥̅ + 𝑐

Ceci implique que 𝑥̅ − 𝑥 (𝑘) = 𝐵(𝑥̅ − 𝑥 (𝑘−1) ) = 𝐵 (𝐵(𝑥̅ − 𝑥 (𝑘−2) )) = ⋯ = 𝐵𝑘 (𝑥̅ − 𝑥 (0) ) ou
encore en considérant une norme subordonnée |‖∙‖| associée à une norme vectorielle ‖∙‖, on a :

∀𝜀 > 0, ‖ 𝑥̅ − 𝑥 (𝑘) ‖ = ‖𝐵𝑘 (𝑥̅ − 𝑥 (0) )‖ ≤ |‖𝐵𝑘 ‖|‖𝑥̅ − 𝑥 (0) ‖ ≤ (𝜌(𝐵) + 𝜀)𝑘 ‖𝑥̅ − 𝑥 (0) ‖

Ce qui indique que plus 𝜌(𝐵) est petit plus la convergence est rapide.

Méthodes itératives connues :

Soit 𝐴 = 𝐷 − 𝐸 − 𝐹 où :

- 𝐷 est la matrice diagonale issue de 𝐴,

- 𝐸 la matrice opposée de la matrice triangulaire inférieure stricte issue de 𝐴, et
- 𝐹 la matrice opposée de la matrice triangulaire supérieure stricte issue de 𝐴.

Méthode de Jacobi :
La matrice d’itération de la méthode de Jacobi est 𝐽 = 𝐷 −1 (𝐸 + 𝐹). Cela suppose qu’aucun élément de
la diagonale de 𝐴 n’est nul.

Méthode de Gauss-Seidel :
La matrice d’itération de la méthode de Jacobi est ℒ1 = (𝐷 − 𝐸)−1 𝐹. Cela suppose aussi qu’aucun
élément de la diagonale de 𝐴 n’est nul.

Méthode de Relaxation :
1 −1 1−𝜔
Soit 𝜔 ∈ ℝ∗. La matrice d’itération de la méthode de Jacobi est 𝐵 = (𝜔 𝐷 − 𝐸) ( 𝜔 𝐷 + 𝐹). Cela
suppose encore qu’aucun élément de la diagonale de 𝐴 n’est nul.

23
Partie II : Méthodes d’optimisation

24
 I- Introduction :
Un problème d’optimisation est un problème qui s’exprime sous la forme :

Chercher 𝑥̅ ∈ ℝ𝑛 tel que:

{𝑓(𝑥̅ ) = inf 𝑓(𝑥) (1)
𝑥∈ℝ𝑛

Quand il s’agit d’un problème sans contraintes, et sous la forme :

Chercher 𝑥̅ ∈ 𝐾 tel que:

{𝑓(𝑥̅ ) = inf 𝑓(𝑥) (2)
𝑥∈𝐾

Quand il s’agit d’un problème avec contraintes, avec 𝑓 est une application de ℝ𝑛 dans ℝ et 𝐾 ⊂ ℝ𝑛
l’ensemble qui exprime les contraintes sur la solution.

Si 𝑥̅ est solution de (1) ou de (2), on dit que 𝑥̅ ∈ argmin 𝑓.

𝑥∈ℝ𝑛

Nous rencontrons ces problèmes dans tous les domaines sans exception. L’amélioration d’un service,
d’un rendement, d’une qualité, passe obligatoirement par l’optimisation. Je cite ci-dessous deux
problèmes liés au filtrage adaptatif : l’égalisation et l’identification. Le premier consiste à estimer les
données à partir d’observations perturbées par un bruit blanc additif, de variance connue, de la sortie
d’un filtre. Il est traité par la minimisation de la puissance de l’erreur entre les données transmises et la
sortie du filtre égaliseur. Le second, quant à lui, consiste à identifier un filtre linéaire à partir des signaux
d’entrée et de sortie bruités. Sa solution se formalise en termes d’optimisation d’un critère de coût qui
est l’erreur quadratique moyenne minimale.

Commençons par faire ces rappels:

Définitions :

- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un minimum local si et seulement si, il existe 𝛼 ∈ ℝ∗+
tel que 𝑓(𝑥̅ ) ≤ 𝑓(𝑥) ∀𝑥 ∈ 𝐵̇(𝑥̅ , ∝),
- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un minimum local strict si et seulement si, il existe
𝛼 ∈ ℝ∗+ tel que 𝑓(𝑥̅ ) < 𝑓(𝑥) ∀𝑥 ∈ 𝐵̇(𝑥̅ , ∝) ∖ {̅
𝑥},
𝑛 𝑛
- Soit 𝑓 ∈ 𝒞(ℝ , ℝ). On dit que 𝑥̅ ∈ ℝ est un minimum global si et seulement si, il existe 𝑓(𝑥̅ ) ≤
𝑓(𝑥) ∀𝑥 ∈ ℝ𝑛 ,
- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un minimum global strict si et seulement si, il existe
𝑓(𝑥̅ ) < 𝑓(𝑥) ∀𝑥 ∈ ℝ𝑛 ∖ {𝑥 ̅}.

Définitions :

- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un maximum local si et seulement si, il existe 𝛼 ∈
ℝ∗+ tel que 𝑓(𝑥̅ ) ≥ 𝑓(𝑥) ∀𝑥 ∈ 𝐵̇(𝑥̅ , ∝),
- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un maximum local strict si et seulement si, il existe
𝛼 ∈ ℝ∗+ tel que 𝑓(𝑥̅ ) > 𝑓(𝑥) ∀𝑥 ∈ 𝐵̇(𝑥̅ , ∝) ∖ {𝑥
̅},
𝑛 𝑛
- Soit 𝑓 ∈ 𝒞(ℝ , ℝ). On dit que 𝑥̅ ∈ ℝ est un maximum global si et seulement si, il existe 𝑓(𝑥̅ ) ≥
𝑓(𝑥) ∀𝑥 ∈ ℝ𝑛 ,
- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un maximum global strict si et seulement si, il existe
𝑓(𝑥̅ ) > 𝑓(𝑥) ∀𝑥 ∈ ℝ𝑛 ∖ {𝑥 ̅}.

25
Définitions :

- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un optimum local si et seulement si 𝑥̅ est un minimum
ou un maximum local,
- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un optimum local strict si et seulement si 𝑥̅ est un
minimum ou un maximum local strict,
- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un optimum global si et seulement si 𝑥̅ est un
minimum ou un maximum global,
- Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑥̅ ∈ ℝ𝑛 est un optimum global strict si et seulement si 𝑥̅ est un
minimum ou un maximum global strict.

Définitions :

- Minimiser une fonction 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) c’est chercher un minimum,

- Maximiser une fonction 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) c’est chercher un maximum,
- Optimiser une fonction 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) c’est chercher un minimum ou un maximum.

Définitions :

Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ).

- On dit que 𝑓 est convexe si et seulement si :

𝑓(𝑡𝑥 + (1 − 𝑡)𝑦) ≤ 𝑡𝑓(𝑥) + (1 − 𝑡)𝑓(𝑦), ∀(𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛 et 𝑡 ∈ [0,1].
- On dit que 𝑓 est strictement convexe si et seulement si :
𝑓(𝑡𝑥 + (1 − 𝑡)𝑦) < 𝑡𝑓(𝑥) + (1 − 𝑡)𝑓(𝑦), ∀(𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛 et 𝑡 ∈ ]0,1[.

Définition (dérivabilité dans ℝ)

Soit 𝑓 ∈ 𝒞(ℝ, ℝ). On dit que 𝑓 est dérivable en 𝑥 ∈ ℝ si et seulement si, il existe 𝑑 ∈ ℝ telle que

𝑓(𝑥 + 𝑡) − 𝑓(𝑥)
lim =𝑑
𝑡→0 𝑡

𝑑 est appelée la dérivée de 𝑓 en 𝑥 et est notée 𝑓′(𝑥).

Définition :
Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) et 𝑧 ∈ ℝ𝑛 ∖ {0}. On dit que 𝑓 est dérivable en 𝑥 ∈ ℝ𝑛 dans la direction 𝑧 si et
seulement si, il existe 𝑑 ∈ ℝ telle que

𝑓(𝑥 + 𝑡𝑧) − 𝑓(𝑥)

lim =𝑑
𝑡→0 𝑡

𝑑 est appelée la dérivée de 𝑓 en 𝑥 dans la direction 𝑧.

Soit (𝑒𝑖 )1≤𝑖≤𝑛 est la base canonique de ℝ𝑛 . On appelle la 𝑖-ème dérivée partielle de 𝑓 en 𝑥, la dérivée
𝜕𝑓
de 𝑓 en 𝑥 dans la direction 𝑒𝑖 quand elle existe. Cette 𝑖-ème dérivée partielle en 𝑥 est notée 𝜕𝑥 (𝑥), ou
𝑖
encore 𝜕𝑖 𝑓(𝑥).

Définitions (différentielle d’une fonction):

Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). On dit que 𝑓 est différentiable en 𝑥 ∈ ℝ𝑛 si et seulement si, il existe une application
linéaire de ℝ𝑛 dans ℝ telle que telle que :

26
 𝑓(𝑥 + ℎ) = 𝑓(𝑥) + 𝐿(ℎ) + ‖ℎ‖𝜖(ℎ)

Où 𝜖 ∈ 𝒞(ℝ𝑛 , ℝ) vérifie lim 𝜖(ℎ) = 0.

‖ℎ‖⟶0

𝐿 est appelée la différentielle de 𝑓 en 𝑥 et est notée 𝐷𝑓𝑥 .

L’isomorphisme qui existe entre l’ensemble des applications linéaires de ℝ𝑛 dans ℝ et l’ensemble des
matrices à une ligne et 𝑛 colonnes implique que si 𝑓 est différentiable en 𝑥 ∈ ℝ𝑛 , alors il existe 𝑢 =
𝐷𝑓𝑥 𝑇 ∈ ℝ𝑛 , tel que :

𝑓(𝑥 + ℎ) = 𝑓(𝑥) + ⟨u|ℎ⟩ + ‖ℎ‖𝜖(ℎ)

𝑢 est appelé le gradient de 𝑓 en 𝑥 et est noté ∇𝑓(𝑥).

Proposition :
Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). Si 𝑓 est différentiable en 𝑥 ∈ ℝ𝑛 , alors la matrice de 𝐷𝑓𝑥 relativement à la base
𝜕𝑓 𝜕𝑓 𝜕𝑓
canonique de ℝ𝑛 est [𝜕𝑥 (𝑥) 𝜕𝑥2
(𝑥) …
𝜕𝑥𝑛
(𝑥)].
1

Preuve :

𝑓 est différentiable en 𝑥 ∈ ℝ𝑛 ⟹
𝑓(𝑥 + ℎ) = 𝑓(𝑥) + 𝐷𝑓𝑥 (ℎ) + ‖ℎ‖𝜖(ℎ)

avec lim 𝜖(ℎ) = 0

‖ℎ‖⟶0

ou encore
𝑛

𝑓(𝑥 + ℎ) = 𝑓(𝑥) + ∑ 𝑑𝑖 ℎ𝑖 + ‖ℎ‖𝜖(ℎ)

𝑖=1

Où ℎ𝑖 est la 𝑖-ème coordonnée de ℎ, et 𝑑𝑖 le 𝑖-ème coefficient de la matrice de 𝐷𝑓𝑥 .

Pour ℎ = 𝑡𝑒𝑖 ,

𝑓(𝑥 + 𝑡𝑒𝑖 ) = 𝑓(𝑥) + 𝑡𝑑𝑖 + |𝑡|𝜖(𝑡𝑒𝑖 )

𝑓(𝑥 + 𝑡𝑒𝑖 ) − 𝑓(𝑥) 𝜕𝑓

⇒ 𝑑𝑖 = lim = (𝑥)
𝑡→0 𝑡 𝜕𝑥𝑖

Et donc
𝑛
𝜕𝑓
𝑓(𝑥 + ℎ) = 𝑓(𝑥) + ∑ ℎ𝑖 (𝑥) + ‖ℎ‖𝜖(ℎ)
𝜕𝑥𝑖
𝑖=1

Corollaire :

27
 𝜕𝑓
(𝑥)
𝜕𝑥1
𝜕𝑓
(𝑥)
Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). Si 𝑓 est différentiable en 𝑥 ∈ ℝ𝑛 alors ∇𝑓(𝑥) = 𝜕𝑥2
⋮
𝜕𝑓
(𝜕𝑥𝑛 (𝑥))

II- Optimisation sans contraintes

Un problème d’optimisation sans contraintes est un problème qui s’exprime sous la forme :

Chercher 𝑥̅ ∈ ℝ𝑛 tel que:

{𝑓(𝑥̅ ) = inf 𝑓(𝑥) (1)
𝑥∈ℝ 𝑛

où 𝑓 est une application de ℝ𝑛 dans ℝ.

II-1 Résultats d’existence et d’unicité du problème d’optimisation :

Proposition (Existence):

Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). Si lim 𝑓(𝑥) = ∞, alors il existe 𝑥 ∈ ℝ𝑛 tel que 𝑓(𝑥) ≤ 𝑓(𝑦), ∀𝑦 ∈ ℝ𝑛 .
‖𝑥‖→+∞

Preuve :

lim 𝑓(𝑥) = ∞ ⟹ (∀𝐴 > 0, ∃𝑅 > 0 ∕ ‖𝑥‖ > 𝑅 ⟹ 𝑓(𝑥) > 𝐴)

‖𝑥‖→+∞

Prenons 𝐴 = 𝑓(0) ⟹ ∃𝑅 > 0 ∕ ‖𝑥‖ > 𝑅 ⟹ 𝑓(𝑥) > 𝑓(0) ⟹ inf

𝑛
𝑓(𝑥) ∈ 𝐵(0, 𝑅). Comme 𝑓 est
ℝ
continue et que 𝐵(0, 𝑅) est fermée, alors ce minimum est atteint

Proposition (Condition suffisante d’ unicité):

Soit 𝑓 de ℝ𝑛 dans ℝ strictement convexe, alors il existe au plus un 𝑥̅ ∈ ℝ𝑛 tel que 𝑓(𝑥̅ ) ≤ 𝑓(𝑦), ∀𝑦 ∈
ℝ𝑛

Preuve :

Supposons qu’il existe deux vecteurs différents 𝑥1 et 𝑥2 qui vérifient (𝑃) 𝑓(𝑥1 ) = 𝑓(𝑥2 ) ≤
1 1 1 1
𝑓(𝑦), ∀𝑦 ∈ ℝ𝑛 . Comme 𝑓 est strictement convexe alors 𝑓 (2 𝑥1 + 𝑥 )
2 2
< 2
𝑓(𝑥1 ) + 2 𝑓(𝑥2 ), ce qui
contredit l’hypothèse (𝑃)

Proposition (existence et unicité):

Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ). Si :

28
 1- lim 𝑓(𝑥) = ∞,
‖𝑥‖→+∞
2- 𝑓 strictement convexe

alors il existe un unique 𝑥̅ ∈ ℝ𝑛 tel que 𝑓(𝑥̅ ) ≤ 𝑓(𝑦), ∀𝑦 ∈ ℝ𝑛 .

Preuve :

La preuve est obtenue par combinaison des épreuves des deux dernières proposition.

II-2 Recherche du minimum pour 𝒇 ∈ 𝓒𝟏 (ℝ𝒏 , ℝ). Algorithmes du gradient :

Introduction :
Les méthodes du gradient pour la recherche d’un minimum d’une fonction 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ), s’inscrivent
dans la classe de méthodes dites de descentes pour la recherche de ce minimum. Ces méthodes
construisent à partir d’un vecteur 𝑥 (0) ∈ ℝ𝑛 , selon un algorithme bien précis qui fait l’objet de la
prochaine section, une suite (𝑥 (𝑘) )𝑘∈ℕde ℝ𝑛 telle que 𝑓(𝑥 (𝑘+1) ) ≤ 𝑓(𝑥 (𝑘) ).

Eléments pour la construction des algorithmes du gradient :

Proposition :.

Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) et 𝑥̅ ∈ ℝ𝑛 donné. On suppose que 𝑓 est différentiable en 𝑥̅ . Si 𝑥̅ est un minimum

local, alors ∇𝑓(𝑥̅ ) = 0.

Preuve :

- 𝑓 est différentiable en 𝑥̅ ⇒ 𝑓(𝑥̅ + ℎ) = 𝑓(𝑥̅ ) + ⟨∇𝑓(𝑥̅ )|ℎ⟩ + ‖ℎ‖𝜖(ℎ).

- 𝑥̅ est un minimum local⇒ ⟨∇𝑓(𝑥̅ )|ℎ⟩ + ‖ℎ‖𝜖(ℎ) ≥ 0 pour ℎ assez petit.

Si ∇𝑓(𝑥̅ ) ≠ 0 ⇒ ∃ 𝑧 ∈ ℝ𝑛 ∖ {0} tel que 〈∇𝑓(𝑥̅ ), 𝑧〉 ≠ 0 ⟹ pour 𝑡 strictement positif assez petit
〈∇𝑓(𝑥̅ ), 𝑡𝑧〉 + 𝑡‖𝑧‖𝜖(𝑡𝑧) ≥ 0 ⟨∇𝑓(𝑥̅ )|𝑧⟩ + ‖𝑧‖𝜖(𝑡𝑧) ≥ 0
{ ⟹{ ⟹ en faisant tendre 𝑡 vers 0 que
〈∇𝑓(𝑥̅ ), −𝑡𝑧〉 + 𝑡‖𝑧‖𝜖(𝑡𝑧) ≥ 0 ⟨∇𝑓(𝑥̅ )|−𝑧⟩ + ‖𝑧‖𝜖(𝑡𝑧) ≥ 0
⟨∇𝑓(𝑥̅ )|𝑧⟩ ≥ 0
{ .
−⟨∇𝑓(𝑥̅ )|𝑧⟩ ≥ 0

Proposition :.

Soit 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ).

- 𝑓 convexe ⟺ 𝑓(𝑦) ≥ 𝑓(𝑥) + 𝐷𝑓𝑥 (𝑦 − 𝑥) ∀(𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛

- 𝑓 strictement convexe ⟺ 𝑓(𝑦) > 𝑓(𝑥) + 𝐷𝑓𝑥 (𝑦 − 𝑥) ∀(𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛 ; 𝑥 ≠ 𝑦

Preuve :

- ⇒) Soit (𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛 et 𝑡 ∈ ]0,1[.

𝑓 convexe ⟺
𝑓(𝑡𝑦 + (1 − 𝑡)𝑥) = 𝑓(𝑥 + 𝑡(𝑦 − 𝑥)) ≤ 𝑡𝑓(𝑦) + (1 − 𝑡)𝑓(𝑥) = 𝑓(𝑥) + 𝑡(𝑓(𝑦) − 𝑓(𝑥)) ⟺

29
 𝑓(𝑥) + 𝑡𝐷𝑓𝑥 (𝑦 − 𝑥) + 𝑡‖𝑦 − 𝑥‖𝜖(𝑡(𝑦 − 𝑥)) ≤ 𝑓(𝑥) + 𝑡(𝑓(𝑦) − 𝑓(𝑥)) ⟺
𝐷𝑓𝑥 (𝑦 − 𝑥) + ‖𝑦 − 𝑥‖𝜖(𝑡(𝑦 − 𝑥)) ≤ (𝑓(𝑦) − 𝑓(𝑥)) ⇒

En faisant tendre 𝑡 vers 0 que 𝑓(𝑦) ≥ 𝑓(𝑥) + 𝐷𝑓𝑥 (𝑦 − 𝑥)

⇐) Soit (𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛 . ∀𝑧 ∈ ℝ𝑛 On a :

𝑓(𝑥) ≥ 𝑓(𝑧) + 𝐷𝑓𝑧 (𝑥 − 𝑧)

{ ⇒
𝑓(𝑦) ≥ 𝑓(𝑧) + 𝐷𝑓𝑧 (𝑦 − 𝑧)

Pour 𝑡 ∈ [0,1], en multipliant la première inégalité par 𝑡, la seconde par 𝑡 − 1 puis en sommant,
on obtient :
𝑡 𝑓(𝑥) + (1 − 𝑡)𝑓(𝑥) ≥ 𝑓(𝑧) + 𝐷𝑓𝑧 (𝑡𝑥 + (1 − 𝑡)𝑦 − 𝑧)

En particulier, pour 𝑧 = 𝑡𝑥 + (1 − 𝑡)𝑦, on obtient :

𝑓(𝑡𝑥 + (1 − 𝑡)𝑦) ≤ 𝑡𝑓(𝑥) + (1 − 𝑡)𝑓(𝑦)

- La démonstration est la même à peu de choses près.

∎

Proposition :.

Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) convexe et 𝑥̅ ∈ ℝ𝑛 donné. On suppose 𝑓 différentiable en 𝑥̅ .

𝑥̅ minimum local ⟺ ∇𝑓(𝑥̅ ) = 0

Preuve :

⇒) démontré ci-dessus.

⇐) 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) convexe et 𝑓 différentiable en 𝑥̅ ⇒ ∀𝑦 ∈ ℝ𝑛 , 𝑓(𝑦) ≥ 𝑓(𝑥̅ ) + 𝐷𝑓𝑧 (𝑦 − 𝑥̅ )

et ∇𝑓(𝑥̅ ) = 0 ⇒ ∀𝑦 ∈ ℝ𝑛 , 𝑓(𝑦) ≥ 𝑓(𝑥̅ )

Définition :

Soient 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) et 𝑥 ∈ ℝ𝑛 .

- On dit que 𝑑 ∈ ℝ𝑛 ∖ {0} est une direction de descente pour 𝑓 en 𝑥 s’il existe 𝑝𝑚𝑎𝑥 ∈ ℝ∗+ tel
que 𝑓(𝑥 + 𝑝𝑑) ≤ 𝑓(𝑥) ∀𝑝 ∈ [0, 𝑝𝑚𝑎𝑥 [
- On dit que 𝑑 ∈ ℝ𝑛 ∖ {0} est une direction de descente stricte pour 𝑓 en 𝑥 s’il existe 𝑝𝑚𝑎𝑥 ∈
ℝ∗+ tel que 𝑓(𝑥 + 𝑝𝑑) < 𝑓(𝑥) ∀𝑝 ∈ ]0, 𝑝𝑚𝑎𝑥 [

Proposition :

Soit 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ) et soit 𝑥 ∈ ℝ𝑛 . Si 𝑑 ∈ ℝ𝑛 ∖ {0} est tel que ⟨∇𝑓(𝑥)|𝑑⟩ < 0 alors 𝑑 est une direction
de descente stricte. En particulier, pour toute matrice 𝑆 ∈ ℳ𝑛 (ℝ) symétrique définie positive, si
∇𝑓(𝑥) ≠ 0 alors −𝑆∇𝑓(𝑥) est une direction de descente stricte.

Preuve :

30
On a 𝑓(𝑥 − 𝑝𝑑) = 𝑓(𝑥) − 𝑝⟨∇𝑓(𝑥)|𝑑⟩ + 𝑝‖𝑑‖𝜖(𝑝𝑑) ⇒il existe 𝑝𝑚𝑎𝑥 ∈ ℝ∗+ tel que

𝑓(𝑥−𝑝𝑑)−𝑓(𝑥)
= −⟨∇𝑓(𝑥)|𝑑⟩ + ‖𝑑‖𝜖(𝑝𝑑) = −‖∇𝑓(𝑥)‖22 + ‖𝑑‖𝜖(𝑝𝑑) < 0 ∀𝑝 ∕ |𝑝| < 𝑝𝑚𝑎𝑥 ⟹
𝑝
pour 0 < 𝑝 < 𝑝𝑚𝑎𝑥 on a : 𝑓(𝑥 − 𝑝𝑑) − 𝑓(𝑥) < 0.

Algorithmes du gradient :
Introduction :
Nous venons de voir que lorsque 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ) la direction opposée du gradient est une direction de
descente. Elle n’est d’ailleurs pas l’unique. Pour s’en convaincre, il suffit de considérer quand 𝑛 > 1 et
dans le cas où le gradient n’est pas nul, la direction 𝑑 = −𝑆∇𝑓(𝑥), où 𝑆 ∈ ℳ𝑛 (ℝ) est symétrique
définie positive. Pour 𝑓 plus régulières, d’autres méthodes ont été développées utilisant les propriétés
supplémentaires par rapport aux fonctions une fois régulières.

D’une manière générale, les méthodes du gradient pour 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ), se basent sur des algorithmes
de la forme

𝑥 (0) ∈ ℝ𝑛
{
𝑥 (𝑘) = 𝑥 (𝑘−1) + 𝑝𝑘−1 𝑑(𝑘−1)

où 𝑝𝑘−1 est un réel positif appelé le pas et 𝑑(𝑘−1) est une direction de descente fonction du gradient.

Les algorithmes présentés ci-dessous supposent que la fonction 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ) à traiter possède au
moins un minimum et ne se soucient pas vers lequel de ces minimums ils vont converger ou pas.

Algorithme du gradient à pas fixe

Soit 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ). La méthode du gradient à pas fixe consiste à prendre la direction de descente
𝑑(𝑘−1) = −∇𝑓(𝑥 (𝑘−1) ) et un pas 𝑝𝑘−1 = 𝑝0 fixé. L’algorithme s’écrit :

𝑥 (0) ∈ ℝ𝑛 et 𝑝0 ∈ ℝ∗+ donnés

Pour 𝑘 = 0,1, …
𝑑(𝑘) = −∇𝑓(𝑥 (𝑘) )
Alg (1)
si 𝑑(𝑘) = 0 Stop
𝑥 (𝑘+1) = 𝑥 (𝑘) + 𝑝0 𝑑(𝑘)
{ fin de pour

De tels algorithmes peuvent converger avec un bon choix de pas. Ils divergent pour un choix de pas
assez grand.

Théorème :

Soit 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ). On suppose qu’il :

a- Existe ∝> 0 ; ⟨∇𝑓(𝑥) − ∇𝑓(𝑦)|𝑥 − 𝑦⟩ ≥ 𝛼‖𝑥 − 𝑦‖2, ∀(𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛

b- Existe 𝑀 > 0 ; ‖∇𝑓(𝑥) − ∇𝑓(𝑦)‖ ≤ 𝑀‖𝑥 − 𝑦‖, ∀(𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛

Alors :

- 𝑓 admet un minimum unique 𝑥̅ ∈ ℝ𝑛 ,

31
 2𝛼
- Si 0 < 𝑝0 < 𝑀2, alors la suite (𝑥 (𝑘) )𝑘∈ℕ de l’algorithme Alg (1) est convergente vers 𝑥̅

Preuve :

Remarquons d’abord que ∀(𝑥, 𝑦) ∈ ℝ𝑛 ×ℝ𝑛 ,

𝛼‖𝑥 − 𝑦‖2 ≤ ⟨∇𝑓(𝑥) − ∇𝑓(𝑦)|𝑥 − 𝑦⟩ ≤ ‖∇𝑓(𝑥) − ∇𝑓(𝑦)‖‖𝑥 − 𝑦‖

⟹ 𝛼‖𝑥 − 𝑦‖ ≤ ‖∇𝑓(𝑥) − ∇𝑓(𝑦)‖ ≤ 𝑀‖𝑥 − 𝑦‖ ⟹ 𝛼 ≤ 𝑀

Soit 𝑝0 ∈ ℝ∗+. On pose 𝑔(𝑥) = 𝑥 − 𝑝0 ∇𝑓(𝑥). On a alors :

⟨𝑔(𝑥) − 𝑔(𝑦) − (𝑥 − 𝑦)|𝑔(𝑥) − 𝑔(𝑦) − (𝑥 − 𝑦)⟩ = ⟨𝑝0 (∇𝑓(𝑥) − ∇𝑓(𝑦))|𝑝0 (∇𝑓(𝑥) − ∇𝑓(𝑦))⟩ =

𝑝02 ‖∇𝑓(𝑥) − ∇𝑓(𝑦)‖22 ≤ 𝑝02 𝑀2 ‖𝑥 − 𝑦‖2

et

⟨𝑔(𝑥) − 𝑔(𝑦) − (𝑥 − 𝑦)|𝑔(𝑥) − 𝑔(𝑦) − (𝑥 − 𝑦)⟩ = ‖𝑔(𝑥) − 𝑔(𝑦)‖2 − 2⟨𝑔(𝑥) − 𝑔(𝑦)|(𝑥 − 𝑦)⟩ +
‖𝑥 − 𝑦‖2

= ‖𝑔(𝑥) − 𝑔(𝑦)‖2 + 2𝑝0 ⟨(∇𝑓(𝑥) − ∇𝑓(𝑦))|(𝑥 − 𝑦)⟩ − ‖𝑥 − 𝑦‖2 ≤ 𝑝02 𝑀2 ‖𝑥 − 𝑦‖2

⇒ ‖𝑔(𝑥) − 𝑔(𝑦)‖2 + 2𝑝0 𝛼‖𝑥 − 𝑦‖2 ≤ (𝑝02 𝑀2 + 1)‖𝑥 − 𝑦‖2

⇒ ‖𝑔(𝑥) − 𝑔(𝑦)‖2 ≤ (𝑝02 𝑀2 − 2𝑝0 𝛼 + 1)‖𝑥 − 𝑦‖2

2𝛼
⇒ ‖𝑔(𝑥) − 𝑔(𝑦)‖2 < ‖𝑥 − 𝑦‖2 pour 0 < 𝑝0 < ,
𝑀2

2𝛼
Donc 0 < 𝑝0 < ⟹ 𝑔 lipchitzienne de rapport 𝜅 < 1, d’où le résultat.
𝑀2

Algorithme du gradient à pas optimal

Soit 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ). La méthode du gradient à pas optimal consiste aussi à prendre la direction de
descente 𝑑(𝑘−1) = −∇𝑓(𝑥 (𝑘−1) ) mais cherche à trouver le pas qui donnerait la plus faible valeur de 𝑓
en 𝑥 (𝑘−1) dans la direction 𝑑(𝑘−1) , autrement dit, 𝑝𝑘−1 est une solution du problème
𝑓 (𝑥 (𝑘−1) − 𝑝𝑘−1 ∇𝑓(𝑥 (𝑘−1) )) ≤ 𝑓 (𝑥 (𝑘−1) − 𝑝∇𝑓(𝑥 (𝑘−1) )) ∀𝑝 ∈ ℝ∗+. Ce problème est un problème
de minimisation d’une fonction réelle à valeurs réelles et l’obtention d’une solution se fait par
l’annulation de la dérivée de 𝑓 (𝑥 (𝑘−1) − 𝑝∇𝑓(𝑥 (𝑘−1) )) par rapport à 𝑝. L’algorithme s’écrit alors :

𝑥 (0) ∈ ℝ𝑛 donné
Pour 𝑘 = 0,1, …
𝑑(𝑘) = −∇𝑓(𝑥 (𝑘) )
si 𝑑(𝑘) = 0 Stop Alg (2)
résolution du problème de minimisation pour la recherche du pas optimal 𝑝𝑘
𝑥 (𝑘+1) = 𝑥 (𝑘) + 𝑝𝑘 𝑑(𝑘)
{ fin de pour

Théorème :

32
Soit 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ) telle que lim 𝑓(𝑥) = +∞, alors :
‖𝑥‖→+∞

- La suite (𝑥 (𝑘) )𝑘∈ℕ de l’algorithme Alg (2) est bien définie,

𝑙
- La suite (𝑥 (𝑘) )𝑘∈ℕ est bornée et si La suite (𝑥 (𝑘 ) ) est une sous suite convergente vers 𝑥̿ ,
𝑙∈ℕ
on a forcément ∇𝑓(𝑥̿ ) = 0. SI de plus 𝑓 est convexe, on a 𝑓(𝑥̿ ) = inf
𝑛
𝑓
ℝ
- Si 𝑓 est strictement convexe, on a alors lim 𝑓(𝑥 (𝑘) ) = 𝑥̅ avec 𝑓(𝑥̅ ) = inf
𝑛
𝑓
𝑘→+∞ ℝ

Preuve :

Elle est laissée au soin du lecteur.

Algorithme du gradient conjugué

Soit 𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ). La méthode du gradient conjugué consiste à générer à chaque itération une
direction de descente pour former avec toutes les précédentes une famille libre. Théoriquement
parlant, le nombre d’itérations maximal pour la convergence est 𝑛, la dimension de ℝ𝑛 . L’algorithme
est alors :

𝑥 (0) ∈ ℝ𝑛 donné
𝑔(0) = ∇𝑓(𝑥 (0) )
si 𝑔(0) = 0 Stop
𝑑(0) = − 𝑔(0)
recherche du pas optimal 𝑝0
𝑥 (1) = 𝑥 (0) + 𝑝0 𝑑(0)
Pour 𝑘 = 1, … . . faire Alg (3)
𝑔(𝑘) = ∇𝑓(𝑥 (𝑘) )
si 𝑔(𝑘) = 0 Stop
recherche de la direction de déscente 𝑑(𝑘) telle que ( 𝑑(𝑖) )0≤𝑘≤𝑘 soit une famille libre
recherche du pas optimal 𝑝𝑘 en 𝑥 (𝑘) dans la direction 𝑑(𝑘)
𝑥 (𝑘+1) = 𝑥 (𝑘) + 𝑝𝑘 𝑑(𝑘)
{fin pour

𝑓: ℝ𝑛 ⟶ ℝ
Application : Etude et recherche du minimum de la fonction 1 avec
𝑥 ⟼ ⟨𝐴𝑥|𝑥⟩ − ⟨𝑏|𝑥⟩
2
𝐴 symétrique définie positive

Justification :

𝑓: ℝ𝑛 ⟶ ℝ
Nous pouvons montrer que la fonction continue 1 avec 𝐴 symétrique
𝑥 ⟼ ⟨𝐴𝑥|𝑥⟩ − ⟨𝑏|𝑥⟩
2
définie positive est une fonction strictement convexe et que lim 𝑓(𝑥) = +∞. Elle admet donc un
‖𝑥‖⟶+∞
minimum unique 𝑥̅ tel que ∇𝑓(𝑥̅ ) = 𝐴𝑥 − 𝑏 = 0. Le trouver revient donc à résoudre le système linéaire
𝐴𝑥 = 𝑏.

Application de la méthode du gradient à pas fixe pour la recherche de x̅ :

L’algorithme Alg (1) s’écrit pour cette fonction :

33
 𝑥 (0) ∈ ℝ𝑛 et 𝑝0 ∈ ℝ∗+ donnés
Pour 𝑘 = 0,1, …
𝑑(𝑘) = 𝑏 − 𝐴𝑥 (𝑘)
Alg (1)
si 𝑑(𝑘) = 0 Stop
𝑥 (𝑘+1) = 𝑥 (𝑘) + 𝑝0 𝑑(𝑘)
{ fin de pour

A l’itération 𝑘 + 1, on a 𝑥 (𝑘+1) = 𝑥 (𝑘) + 𝑝0 𝑑(𝑘) = (𝐼 − 𝑝0 𝐴)𝑥 (𝑘) + 𝑝0 𝑏

La convergence est alors obtenue pour 𝑝0 ∕ 𝜌(𝐼 − 𝑝0 𝐴) < 1 où 𝜌(𝑀) est le rayon spectral de 𝑀 pour
2
𝑀 ∈ ℳ𝑛 (ℝ). Ceci est vrai pour tout 𝑝0 ∈ ]0, 𝜚(𝐴)[

Application de la méthode du gradient à pas optimal pour la recherche de 𝑥̅ :

L’algorithme Alg (2) s’écrit pour cette fonction :

𝑥 (0) ∈ ℝ𝑛 donné
Pour 𝑘 = 0,1, …
𝑑(𝑘) = 𝑏 − 𝐴𝑥 (𝑘)
si 𝑑(𝑘) = 0 Stop
⟨𝑑(𝑘) |𝑑(𝑘)⟩
𝑝𝑘 =
⟨𝐴𝑑(𝑘)|𝑑(𝑘) ⟩
𝑥 (𝑘+1) = 𝑥 (𝑘) + 𝑝𝑘 𝑑(𝑘)
{ fin de pour
(𝑘) (𝑘)
⟨𝑑 |𝑑 ⟩
Le pas optimal dans la direction 𝑑(𝑘) = 𝑏 − 𝐴𝑥 (𝑘) est en effet égal à 𝑝𝑘 = (𝑘) (𝑘)
⟨𝐴𝑑 |𝑑 ⟩

Application de la méthode du gradient conjugué pour la recherche de 𝑥̅ :

L’algorithme Alg (3) s’écrit pour cette fonction :

𝑥 (0) ∈ ℝ𝑛 donné
𝑔(0) = 𝐴𝑥 (0) − 𝑏
si 𝑔(0) = 0 Stop
𝑑(0) = − 𝑔(0)
⟨𝑑(0) |𝑑(0)⟩
𝑝0 =
⟨𝐴𝑑(0) |𝑑(0) ⟩
𝑥 (1) = 𝑥 (0) + 𝑝0 𝑑(0)
Pour 𝑘 = 1, … . . faire
𝑔(𝑘) = 𝐴𝑥 (𝑘) − b
si 𝑔(𝑘) = 0 Stop
⟨𝐴𝑔(𝑘)|𝑑 (𝑘−1) ⟩
𝛽𝑘 =
⟨𝐴𝑑(𝑘−1)|𝑑(𝑘−1) ⟩
𝑑(𝑘) = −𝑔(𝑘) + 𝛽𝑘 𝑑(𝑘−1)
−⟨𝑑(𝑘)|𝑔(𝑘)⟩
𝑝𝑘 =
⟨𝐴𝑑(𝑘)|𝑑(𝑘) ⟩
𝑥 (𝑘+1) = 𝑥 (𝑘) + 𝑝𝑘 𝑑(𝑘)
{ fin pour

34
Le coefficient 𝛽𝑘 est choisi de telle manière que la direction de descente 𝑑(𝑘) soit orthogonale à 𝑑(𝑘−1) ,
relativement au produit scalaire définit par la matrice Toutefois, nous montrons ci-dessous que 𝑑(𝑘) est
orthogonale à toutes les directions de descente précédentes. Le pas optimal dans cette dernière
(𝑘) (𝑘)
−⟨𝑑 |𝑔 ⟩
direction est alors 𝑝𝑘 = (𝑘) (𝑘) .
⟨𝐴𝑑 |𝑑 ⟩

Propriétés du gradient conjugué :

1- 𝑑(𝑘) est une direction de descente stricte. En effet, ⟨ 𝑑(𝑘) | 𝑔(𝑘)⟩ = −⟨𝑔(𝑘)|𝑔(𝑘)⟩ +
2
𝛽𝑘 ⟨𝑑(𝑘−1)|𝑔(𝑘)⟩ = −‖𝑔(𝑘) ‖2 + 𝛽𝑘 ⟨𝑑(𝑘−1)|∇𝑓(𝑥 (𝑘) )⟩
2
= −‖𝑔(𝑘) ‖2 + 𝛽𝑘 ⟨𝑑(𝑘−1)|∇𝑓(𝑥 (𝑘−1) + 𝑝𝑘−1 𝑑(𝑘−1) )⟩

2 𝑑 (𝑓(𝑥 (𝑘−1) + 𝑝𝑑(𝑘−1) )) 2

= −‖𝑔(𝑘) ‖2 + 𝛽𝑘 = −‖𝑔(𝑘) ‖2 < 0
𝑑𝑝 |𝑝=𝑝𝑘−1

⟨ 𝑔(𝑙) | 𝑑(𝑘) ⟩ = 0 pour 𝑘 < 𝑙

(𝑙) (𝑘)
2- { ⟨𝑔 |𝑔 ⟩=0 pour 𝑘 < 𝑙
(𝑙) (𝑘)
⟨ 𝐴𝑑 | 𝑑 ⟩ = 0 pour 𝑘 < 𝑙

Les relations sont vraies pour 𝑙 = 1. Supposons qu’elles sont vraies jusqu’au rang 𝑙1 . Soit 𝑘 <
𝑙1 + 1.
Pour 𝑘 = 𝑙1 ⟨ 𝑔(𝑙1 +1)| 𝑑(𝑙1 ) ⟩ = 0 car le pas optimal pour avoir 𝑥 (𝑙1 +1) est tel qu’il minimise
𝑓(𝑥 (𝑙1 ) + 𝑝𝑑(𝑙1 ) ) autrement dit ∇𝑓(𝑥 (𝑙1 ) + 𝑝𝑙1 𝑑(𝑙1 ) ) = ⟨ 𝑔(𝑙1 +1)| 𝑑(𝑙1 ) ⟩ = 0.
Pour 𝑘 < 𝑙1 , ⟨ 𝑔(𝑙1 +1)| 𝑑(𝑘)⟩ = ⟨𝐴 𝑥 (𝑙1 +1) − 𝑏| 𝑑(𝑘)⟩ = ⟨𝐴( 𝑥 (𝑙1 ) + 𝑝𝑙 𝑑(𝑙1 ) ) − 𝑏| 𝑑(𝑘) ⟩ =
⟨𝐴 𝑥 (𝑙1 ) − 𝑏 + 𝑝𝑙 𝐴𝑑(𝑙1 ) | 𝑑(𝑘)⟩ = −⟨ 𝑔(𝑙1 ) |𝑑 (𝑘)⟩ − ⟨𝑝𝑙1 𝐴𝑑(𝑙1 )|𝑑(𝑘) ⟩ = 0 .

⟨ 𝑔(𝑙1 +1)| 𝑔(𝑘) ⟩ = ⟨ 𝑔(𝑙1 +1)|− 𝑑(𝑘) + 𝛽𝑘 𝑑(𝑘−1)⟩ = 0 d’après ce qui vient d’être démontré.

Pour 𝑘 = 𝑙1 , ⟨ 𝐴𝑑 (𝑙1 +1) | 𝑑(𝑙1 ) ⟩ = 0 .

1
Pour 𝑘 < 𝑙1 , ⟨ 𝐴𝑑 (𝑙1 +1)| 𝑑(𝑘) ⟩ = ⟨ 𝑑(𝑙1 +1)| 𝐴𝑑(𝑘) ⟩ = ⟨ 𝑑(𝑙1 +1) | 𝑔(𝑘) − 𝑔(𝑘+1) ⟩ = 0
𝑝𝑘
Ainsi la méthode du gradient conjuguée converge au plus en 𝑛 itérations.

II-3 Algorithmes de recherche du minimum pour 𝒇 ∈ 𝓒𝟐 (ℝ𝒏 , ℝ)

Nous supposons dans ce qui suit que 𝑓 ∈ 𝒞 2 (ℝ𝑛 , ℝ). Ainsi ∇𝑓 ∈ 𝒞 1 (ℝ𝑛 , ℝ𝑛 ) et nous avons
l’équivalence ∇𝑓(𝑥) = 0 ⟺ 𝑓(𝑥) = inf𝑛 𝑓(𝑦). Le problème se transforme alors en la recherche d’un
𝑦∈ℝ
zéro du gradient.

II.3.a Méthode de Newton :

Le développement du gradient en série de Taylor d’ordre 1 au voisinage de 𝑥̃ ∈ ℝ𝑛 pour une fonction
𝑓 ∈ 𝒞 2 (ℝ𝑛 , ℝ) s’écrit :

∇𝑓(𝑥) = ∇𝑓(𝑥̃) + 𝐷(∇𝑓(𝑥̃))(𝑥 − 𝑥̃) + ‖𝑥 − 𝑥̃‖𝜀(𝑥 − 𝑥̃)

35
où 𝜀 ∈ 𝒞 1 (ℝ𝑛 , ℝ) vérifiant lim 𝜀(𝑥 − 𝑥̃) = 0.
‖𝑥−𝑥̃‖→0

Notons 𝐻𝑓 (𝑥̃) = 𝐷(∇𝑓(𝑥̃)) la hessienne de 𝑓. Pour 𝑥 ∈ ℝ𝑛 tel que ∇𝑓(𝑥) = 0 , nous avons
−∇𝑓(𝑥̃) = 𝐻𝑓 (𝑥̃)(𝑥 − 𝑥̃) + ‖𝑥 − 𝑥̃‖𝜀(𝑥 − 𝑥̃)

La méthode de Newton7 pour trouver le minimum consiste à construire une suite (𝑥 (𝑘) )𝑘∈ℕ ∈ ℝ𝑛 avec
l’algorithme :

𝑥 (0) ∈ ℝ𝑛 donné
{
𝐻𝑓 (𝑥 (𝑘) )(𝑥 (𝑘) − 𝑥 (𝑘+1) ) = ∇𝑓(𝑥 (𝑘) )

où 𝐻𝑓 (𝑥 (𝑘) ) est la matrice hessienne de 𝑓 en 𝑥 (𝑘) .

Proposition :

La méthode de Newton pour trouver le minimum d’une fonction 𝑓 ∈ 𝒞 2 (ℝ𝑛 , ℝ) convexe est une
méthode de descente.

Preuve :

On suppose qu’à l’itération 𝑘, 𝐻𝑓 (𝑥 (𝑘) ) inversible. Ceci implique que 𝐻𝑓 (𝑥 (𝑘) )(𝑥 (𝑘) − 𝑥 (𝑘+1) ) =
−1
∇𝑓(𝑥 (𝑘) ) ⟺ 𝑥 (𝑘+1) = 𝑥 (𝑘) − 𝐻𝑓 (𝑥 (𝑘) ) (∇𝑓(𝑥 (𝑘) )). 𝑓 ∈ 𝒞 2 (ℝ𝑛 , ℝ) convexe ⟹ 𝐻𝑓 (𝑥 (𝑘) ) est
positive. Comme 𝐻𝑓 (𝑥 (𝑘) ) est inversible alors elle est définie positive. Ceci implique que la méthode de
Newton est une méthode de descente avec un pas 𝑝 égale à 1 et une direction de descente 𝑑(𝑘) =
−1
−𝐻𝑓 (𝑥 (𝑘) ) (∇𝑓(𝑥 (𝑘) ))
∎

II.3.b Méthodes de quasi-Newton :

La méthode de Newton est rapide pour la recherche du minimum. Elle est cependant handicapée par
le calcul nécessaire pour la détermination de la hessienne à chaque pas d’itération. Les méthodes de
quasi-Newton sont développées pour éviter un tel calcul en construisant d’une manière peu coûteuse
une matrice 𝐵(𝑘) ≈ 𝐻𝑓 (𝑥 (𝑘) ) à chaque pas d’itération.

i- Méthode de Broyden8 :
La construction de la matrice 𝐵(𝑘) sensée approcher la hessienne de 𝑓 en 𝑥 (𝑘) se fait en remarquant
qu’une bonne approximation serait que 𝐵(𝑘) vérifie ∇𝑓(𝑥 (𝑘) ) − ∇𝑓(𝑥 (𝑘−1) ) = 𝐵(𝑘) (𝑥 (𝑘) − 𝑥 (𝑘−1) ).

La méthode de Broyden permet de déterminer les coefficients de 𝐵(𝑘) par la résolution du système :

𝐵(𝑘) (𝑥 (𝑘) − 𝑥 (𝑘−1) ) = ∇𝑓(𝑥 (𝑘) ) − ∇𝑓(𝑥 (𝑘−1) )

{
𝐵(𝑘) 𝑠 = 𝐵(𝑘−1) 𝑠 ∀𝑠 ⊥ 𝑥 (𝑘) − 𝑥 (𝑘−1)

L’algorithme est alors :

7
https://fr.wikipedia.org/wiki/Isaac_Newton
8
https://en.wikipedia.org/wiki/Charles_George_Broyden

36
 𝑥 (0) ∈ ℝ𝑛 et 𝐵(0) symétrique définie positive donnés
−1
𝑑(0) = −( 𝐵(0) ) ∇𝑓(𝑥 (0) )
Initialisation
𝑝0 pas optimal dans la direction 𝑑(0)
{𝑥 (1) = 𝑥 (0) + 𝑝0 𝑑(0)
𝑥 (𝑘−1) , 𝑥 (𝑘) 𝑒𝑡 𝐵(𝑘−1) connus
On détermine 𝐵(𝑘)
−1
Itération 𝑘 = 1,2, … 𝑑(𝑘) = −( 𝐵(𝑘) ) ∇𝑓(𝑥 (𝑘) )
𝑝𝑘 pas optimal dans la direction 𝑑(𝑘)
{ {𝑥 (𝑘+1) = 𝑥 (𝑘) + 𝑝𝑘 𝑑(𝑘)

ii- Méthode de BFGS (Broyden9, Fletcher, Goldfarb et Shanno) :

La méthode de Broyden présentée ci-dessus n’assure pas la symétrie de la matrice de 𝐵(𝑘) à l’itération
𝑘. La projection orthogonale de 𝐵(𝑘−1) sur l’ensemble 𝐸𝑘 = {𝐵 ∈ 𝑆𝑛 (ℝ) tel que 𝑦 (𝑘) = 𝐵(𝑘) 𝑠 (𝑘) }
muni de la norme de Schur, où 𝑆𝑛 (ℝ) est l’ensemble des matrices d’ordre 𝑛 symétriques à coefficients
réels, 𝑦 (𝑘) = ∇𝑓(𝑥 (𝑘) ) − ∇𝑓(𝑥 (𝑘−1) ) et 𝑠 (𝑘) = 𝑥 (𝑘) − 𝑥 (𝑘−1) remédie à ce problème. On montre que
𝑇 𝑇
𝑦 (𝑘) 𝑦 (𝑘) 𝐵(𝑘−1) 𝑠(𝑘) 𝑠(𝑘) 𝐵(𝑘−1)
cette projection est 𝑃𝐸𝑘 𝐵(𝑘−1) = 𝐵(𝑘) = 𝐵(𝑘−1) + 𝑇 − 𝑇
𝑠 (𝑘) 𝑦 (𝑘) 𝑠(𝑘) 𝐵(𝑘−1) 𝑠(𝑘)

III- Optimisation sous contraintes

Un problème d’optimisation sous contraintes est un problème qui s’exprime sous la forme :

Chercher 𝑥̅ ∈ 𝐾 tel que:

{𝑓(𝑥̅ ) = inf 𝑓(𝑥) (2)
𝑥∈𝐾

où 𝑓 est une application de ℝ𝑛 dans ℝ et 𝐾 un sous ensemble strictement inclus dans ℝ𝑛 .

Nous distinguons deux types de problèmes :

- 𝐾 défini par des contraintes d’égalités, autrement dit,

𝐾 = {𝑥 ∈ ℝ𝑛 ⁄𝑔𝑖 (𝑥) = 0 , 𝑖 = 1,2, … , 𝑝}
- 𝐾 défini par des contraintes d’inégalités, autrement dit,
𝐾 = {𝑥 ∈ ℝ𝑛 ⁄𝑔𝑖 (𝑥) ≤ 0 , 𝑖 = 1,2, … , 𝑝}

III-1 Résultats d’existence et d’unicité:

Théorème :

Soient 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) et 𝐾 un sous ensemble fermé de ℝ𝑛 , alors il existe 𝑥̅ ∈ 𝐾⁄𝑓(𝑥̅ ) = inf 𝑓(𝑥) si :
𝑥∈𝐾

1- 𝐾 est borné,

Ou si :

2- lim 𝑓(𝑥) = +∞
‖𝑥‖→+∞

9
https://en.wikipedia.org/wiki/Charles_George_Broyden

37
Preuve :

1- 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) et 𝐾 fermé borné donc 𝑓 atteint ses extrémums

2- lim 𝑓(𝑥) = +∞ ⇒ ∀𝐴 > 0, ∃𝑅 > 0 ∕ ‖𝑥‖ > 𝑅 ⇒ 𝑓(𝑥) > 𝐴. Le résultat est obtenu en
‖𝑥‖→+∞
remarquant que {𝑥 ∈ ℝ𝑛 ∕ 𝑓(𝑥) ≤ 𝐴} ∩ 𝐾 est fermé.

Théorème :

Soient 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) strictement convexe et 𝐾 convexe de ℝ𝑛 , alors il existe au plus un 𝑥̅ ∈ 𝐾 ⁄𝑓(𝑥̅ ) =

inf 𝑓(𝑥)
𝑥∈𝐾

Preuve :

Supposons qu’il existe (𝑥1 , 𝑥2 ) ∈ 𝐾×𝐾, avec 𝑥1 ≠ 𝑥2 et 𝑓(𝑥1 ) = 𝑓(𝑥2 ) ≤ 𝑓(𝑥)∀𝑥 ∈ 𝐾, alors on a
1 1 1 1
𝑓 ( 𝑥1 + 𝑥2 ) < 𝑓(𝑥1 ) + 𝑓(𝑥2 ) = 𝑓(𝑥1 ). Impossible.
2 2 2 2

III-2 Conditions d’optimalité simple:

Proposition :

Soient 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) et 𝐾 ⊂ ℝ𝑛 et soit 𝑥̅ ∈ 𝐾⁄𝑓(𝑥̅ ) = inf 𝑓(𝑥). On suppose que 𝑓 est différentiable
𝑥∈𝐾
en 𝑥̅ alors :
°
1- Si 𝑥̅ ∈ 𝐾 alors ∇𝑓(𝑥̅ ) = 0
2- Si 𝐾 est convexe alors ∀𝑥 ∈ 𝐾, ∇𝑓(𝑥̅ )(𝑥 − 𝑥̅ ) ≥ 0

Preuve :
° °
1- Si 𝑥̅ ∈ 𝐾 ⟹ ∃𝑟 > 0 ∕ 𝐵(𝑥̅ , 𝑟) ⊂ 𝐾. Soit 𝑧 ∈ ℝ𝑛 et 𝑡 « assez petit ». On a alors : 𝑓(𝑥̅ + 𝑡𝑧) −
𝑓(𝑥̅ ) = 𝑡〈∇𝑓(𝑥̅ ), 𝑧〉 + |𝑡|‖𝑧‖𝜀(𝑡𝑧) ⟹ ∇𝑓(𝑥̅ ) = 0
2- Si 𝐾 est convexe alors ∀𝑥 ∈ 𝐾, 𝑡𝑥 + (1 − 𝑡)𝑥̅ ∈ 𝐾 et 𝑓( 𝑡𝑥 + (1 − 𝑡)𝑥̅ ) = 𝑓(𝑥̅ ) +
𝑡〈∇𝑓(𝑥̅ ), 𝑥 − 𝑥̅ 〉 + |𝑡|‖𝑥 − 𝑥̅ ‖𝜀(𝑡(𝑥 − 𝑥̅ )) ⟹ ∇𝑓(𝑥̅ )(𝑥 − 𝑥̅ ) ≥ 0
∎

III-3 Conditions d’optimalité en cas de contraintes d’égalité

Théorème (Multiplicateurs de Lagrange10):
𝑡
Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) et soient 𝑔𝑖 ∈ 𝒞 1 (ℝ𝑛 , ℝ) pour 𝑖 = 1,2, … , 𝑝. On pose 𝑔 = (𝑔1 , 𝑔2 , … , 𝑔𝑝 ) et on
considère 𝐾 = {𝑥 ∈ ℝ𝑛 ⁄𝑔𝑖 (𝑥) = 0, 𝑖 = 1,2, … , 𝑝} et on considère 𝑥̅ ∈ ℝ𝑛 ⁄𝑓(𝑥̅ ) = inf 𝑓(𝑥). On
𝑥∈𝐾
𝑡
suppose que 𝑓 est différentiable en 𝑥̅ et que 𝑟𝑎𝑛𝑔(𝐷𝑔(𝑥̅ )) = 𝑝 alors il existe 𝜆 = (𝜆1 , 𝜆2 , … , 𝜆𝑝 ) ∈
ℝ𝑝 telle que :

10
https://fr.wikipedia.org/wiki/Joseph-Louis_Lagrange

38
 𝑝

∇𝑓(𝑥̅ ) + ∑ 𝜆𝑖 ∇𝑔𝑖 (𝑥̅ ) = 0

𝑖=1

Remarque:

Dans la pratique nous résolvons le système

𝑝

∇𝑓(𝑥̅ ) + ∑ 𝜆𝑖 ∇𝑔𝑖 (𝑥̅ ) = 0

{
𝑖=1
𝑔𝑖 (𝑥̅ ) = 0, 𝑖 = 1,2, … , 𝑝

III-4 Conditions d’optimalité en cas de contraintes d’inégalité

Théorème de Kuhn11 & Tucker12:
𝑡
Soit 𝑓 ∈ 𝒞(ℝ𝑛 , ℝ) et soient 𝑔𝑖 ∈ 𝒞 1 (ℝ𝑛 , ℝ) pour 𝑖 = 1,2, … , 𝑝. On pose 𝑔 = (𝑔1 , 𝑔2 , … , 𝑔𝑝 ) et on
considère 𝐾 = {𝑥 ∈ ℝ𝑛 ⁄𝑔𝑖 (𝑥) ≤ 0, 𝑖 = 1,2, … , 𝑝} et on considère 𝑥̅ ∈ ℝ𝑛 ⁄𝑓(𝑥̅ ) = inf 𝑓(𝑥). On
𝑥∈𝐾
suppose que 𝑓 est différentiable en 𝑥̅ et que {∇𝑔𝑖 (𝑥̅ )}𝑖∈ 𝐼(𝑥̅ ) où 𝐼(𝑥̅ ) = {𝑖 ∈ {1,2, … ; 𝑝}⁄𝑔𝑖 (𝑥) = 0}
est une famille libre, alors il existe 𝜆 = (𝜆𝑖 )𝑖∈ 𝐼(𝑥̅ ) de réels positifs tels que

∇𝑓(𝑥̅ ) + ∑ 𝜆𝑖 ∇𝑔𝑖 (𝑥̅ ) = 0

𝑖∈ 𝐼(𝑥̅ )

Remarque:

Dans la pratique nous résolvons le système

𝑝

∇𝑓(𝑥̅ ) + ∑ 𝜆𝑖 ∇𝑔𝑖 (𝑥̅ ) = 0

𝑖=1
𝜆𝑖 𝑔𝑖 (𝑥̅ ) = 0, 𝑖 = 1,2, … , 𝑝
𝑔𝑖 (𝑥̅ ) ≤ 0, 𝑖 = 1,2, … , 𝑝
{𝜆𝑖 ≥ 0, 𝑖 = 1,2, … , 𝑝

11
https://fr.wikipedia.org/wiki/Harold_W._Kuhn
12
https://fr.wikipedia.org/wiki/Albert_W._Tucker

39
Bibliographie :
[1] M. Ben Zid : Emploi de techniques de traitement de signal MIMO pour des applications dédiées
réseaux de capteurs sans fil, Thèse de doctorat, Université de Grenoble, 2012

[2] Ph. Guguen : Techniques multi-antennes émission-réception : Applications aux réseaux

domestiques sans fil, Thèse de doctorat, INSA Rennes, 2003

[3] J. Rappaz, M. Picasso : Introduction à l’analyse numérique, Presses polytechniques et universitaires

romandes, 2010

[4] F. Michaut, M. Bellanger : Filtrage adaptatif, Théorie et algorithmes, Lavoisier, 2005

[5] P. Lascaux, R. Théodor : Analyse numérique matricielle appliquée à l’art de l’ingénieur, Vol. 1,
Masson, 1986

[6] P. Lascaux, R. Théodor : Analyse numérique matricielle appliquée à l’art de l’ingénieur, Vol. 2,
Masson, 1987

[7] R. Herbin : Cours d’optimisation.

40