# COURS D' ANALYSE NUMERIQUE (BAC2 IAGE)

## Djamba Tunda-Olembe

► To cite this version:

Djamba Tunda-Olembe. COURS D' ANALYSE NUMERIQUE (BAC2 IAGE). Licence. ANALYSE NUMÉRIQUE, Université Protestante de Lubumbashi, Congo-Kinshasa. 2024, pp.83. hal-04949671

HAL Id: hal-04949671

https://hal.science/hal-04949671v1

Submitted on 15 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
REPUBLIQUE DEMOCRATIQUE DU CONGO
ENSEIGNEMENT SUPERIEUR ET UNIVERSITAIRE
UNIVERSITE PROTESTANTE DE LUBUMBASHI

COURS D' ANALYSE NUMERIQUE
(BAC2 IAGE)

PAR MASTER ING CIVIL TUNDA-OLEMBE DJAMBA

NOVEMBRE 2024
# DESCRIPTIF DU COURS D' ANALYSE NUMERIQUE

FACULTE : SCIENCES INFORMATIQUES

INTITULE : ANALYSE NUMERIQUE

VOLUME : 2 crédits

PROMOTION : BAC2 IAGE

TITULAIRE : MASTER ING TUNDA-OLEMBE DJAMBA

PROFIL ACADEMIQUE : CT

EMAIL : djambatunda@gmail.com

TELEPHONE : 0974762941

## I. LIMINAIRE

L' **Analyse numérique** constitue une discipline scientifique qui s' occupe de methodes nimeriques et de la programmation scientifique. L' analyse numerique a comme objectif la conception , l'analyse et l' implémentation d' algorithmes pour la résolution numérique des problèmes mathématiques qui proviennent de la modélisation des phénomènes réels. Il est à l'interface des mathématiques et de l'informatique. Elle s'intéresse tant aux fondements qu'à la mise en pratique des méthodes permettant de résoudre, par des calculs purement numériques, des problèmes mathématiques.

Plus formellement, l'analyse numérique est l'étude des algorithmes permettant de résoudre numériquement par discrétisation les problèmes de *mathématiques continues* (distinguées des mathématiques discrètes). Cela signifie qu'elle s'occupe principalement de répondre de façon numérique à des questions à variable réelle ou complexe comme l'algèbre linéaire numérique sur les champs réels ou complexes, la recherche de solution numérique d'équations différentielles et d'autres problèmes liés survenant dans les sciences physiques et l'ingénierie. Branche des mathématiques appliquées, son développement est étroitement lié à celui des outils informatiques.

Certains problèmes de mathématiques peuvent être résolus numériquement (c.-à-d., sur ordinateur) de façon exacte par un algorithme en un nombre fini d'opérations. Ces algorithmes sont parfois appelés *méthodes directes* ou qualifiés de *finis*. Des exemples sont l'élimination de Gauss-Jordan pour la résolution d'un système d'équations linéaires et l'algorithme du simplexe en optimisation linéaire. L'utilisation des Méthodes numériques est grandement facilitée par les ordinateurs. XXe siècle a permis l'application des méthodes numériques dans de nombreux domaines scientifiques, techniques et économiques, avec souvent des effets importants.
## II. PREREQUIS

- COURS D' ANALYSE MATHÉMATIQUE

- COURS D' ALGÈBRE

- COURS DE PROGRAMMATION AVEC LES LANGAGES C ET C++

- COURS DE PROGRAMMATION AVEC LE LANGAGE PYTHON

- COURS DE PROGRAMMATION AVEC LE LANGAGE JAVA

## III. OBJECTIFS GENERAUX

Au termes de ce cours l'étudiant ou l'étudiante sera capable de :

1. analyser, de comprendre et d'utiliser divers méthodes et algorithmes représentatifs en matière de résolution numérique de problèmes mathématiques par ordinateur ou à l'aide d'une calculatrice de poche ;

2. analyser et de comprendre le comportement numérique des méthodes de résolutions des équations linéaires et non-linéaires;

3. analyser, de comprendre et d'utiliser les méthodes numériques d'analyse de données par interpolation et par moindres carrées;

4. analyser, de comprendre et d'utiliser les méthodes numériques de dérivation et d'intégration.

## IV. OBJECTIFS SPECIFIQUES

Au termes de ce cours étudiant ou l'étudiante sera capable de :

1. résoudre numériquement un problème mathématique à l'aide d'une calculatrice de poche;

2. implémenter des méthodes numériques dans un logiciel et vérifier leurs comportements mathématiques;

## V. COMPETENCES VISEES

Au termes de ce cours étudiant ou l'étudiante va :

1. Acquérir des méthodes de résolutions numériques des problèmes mathématiques;

2. Être capable d'identifier de problèmes pratiques qui exigent des méthodes numériques pour être résolus;

3. Acquérir des connaissances en analyse numérique qui seront utile dans le domaine d'informatique de gestion.
# VI. PLAN DU COURS

- Chapitre 1 : Introduction à l' Analyse numerique ;

- Chapitre 2 : Resolution des equations non-lineaires ;

- Chapitre 3 : Interpolation et approximation ;

- Chapitre 4 : Methodes des moindres carrées ;

- Chapitre 5 : Derivation numerique ;

- Chapitre 6 : Intregration numerique;

- Chapitre 7 : Algebre lineaire numerique.

# VII. BIBLIOGRAPHIE ET AUTRES SOURCES

## A. Livres

1. Calvi, J-P: " Analyse numérique ", Éditions UPS Université de Toulouse, Toulouse, 2011

2.Quaterteroni, A. et al. : " Méthodes numériques : Algorithmes ; analyse et applications ", Éditions Springer-Verlag Milan, 2017

4. Mustapha, L., :" Analyse numérique et exercices résolues" , Éditions Ellynpes , Bruxelles, 2017

## B. Cours

1. Jansen, M., " Cours de calcul formel et numérique", Universite Libre Bruxelles.

# VIII. LOGICIELS A UTILISER

1. Microsoft visual studio;

2. Compilateur Python

3. Compilateur Java

# IX. METHODE DE COMMUNICATION

1. Cours théorique orienté vers la pratique ;

2. Travaux et discussion en groupe ;

3. Organisation TD et TP ;

4. Autoformation.
# X. METHODE D'EVALUATION

1. Travaux pratiques ;

2. Travaux dirigés

3. Interrogations ;

4. Examen
# CHAPITRE 1. INTRODUCTION A L' ANALYSE NUMERIQUE.

## 1. 1 PRESENTATION

L' **Analyse numerique** constitue une discipline scientifique qui s' occupe des methodes numeriques et la programmation scientifique. Les methodes numeriques ont comme objectif la conception, l'analyse et l' implémentation d' algorithmes pour la résolution numérique des problèmes mathématiques qui proviennent de la modélisation des phénomènes réels. Il est à l'interface des mathématiques et de l'informatique. Elle s'intéresse tant aux fondements qu'à la mise en pratique des méthodes permettant de résoudre, par des calculs purement numériques, des problèmes mathématiques.

Plus formellement, l'analyse numérique est l'étude des algorithmes permettant de résoudre numériquement par discrétisation les problèmes de *mathématiques continues* (distinguées des mathématiques discrètes). Cela signifie qu'elle s'occupe principalement de répondre de façon numérique à des questions à variable réelle ou complexe comme l'algèbre linéaire numérique sur les champs réels ou complexes, la recherche de solution numérique d'équations différentielles et d'autres problèmes liés survenant dans les sciences physiques et l'ingénierie. Branche des mathématiques appliquées, son développement est étroitement lié à celui des outils informatiques.

Certains problèmes de mathématiques peuvent être résolus numériquement (c.-à-d., sur ordinateur) de façon exacte par un algorithme en un nombre fini d'opérations. Ces algorithmes sont parfois appelés *méthodes directes* ou qualifiés de *finis*. Des exemples sont l'élimination de Gauss-Jordan pour la résolution d'un système d'équations linéaires et l'algorithme du simplexe en optimisation linéaire.

L'utilisation de l'Analyse numérique est grandement facilitée par les ordinateurs. L'accroissement de la disponibilité et de la puissance des ordinateurs depuis la seconde moitié du XXe siècle a permis l'application des methodes numérique dans de nombreux domaines scientifiques, techniques et économiques, avec souvent des effets importants.
L'étude des erreurs forme une partie importante de l'analyse numérique. Les erreurs introduites dans la solution d'un problème ont plusieurs origines. Les erreurs d'arrondis surviennent car il est impossible de représenter en pratique tous les nombres réels exactement sur une machine à états finis (ce que sont en fin de compte tous les ordinateurs numériques). Les erreurs de troncature sont commises par exemple quand une méthode itérative est terminée et que la solution approchée obtenue diffère de la solution exacte. De façon similaire, la discrétisation d'un problème (aussi appelée quantification dans les applications pratiques de calcul numérique) induit une erreur de discrétisation (en) (erreur de quantification dans les applications pratiques) car la solution du problème discret ne coïncide pas exactement avec la solution du problème continu.

Une fois que l'erreur est générée, elle se propagera généralement tout au long du calcul. Cela conduit à la notion de stabilité numérique¹ : un algorithme est numériquement stable si une erreur, une fois générée, ne croît pas trop durant le calcul (dans une méthode de calcul itératif, une erreur trop grande peut dans certains cas faire diverger l'algorithme qui ne parviendra pas à approcher la solution). Cela n'est possible que si le problème est bien conditionné, ce qui signifie que la solution ne change que d'une faible quantité si les données du problème sont changées d'un montant faible. Ainsi, si un problème est mal conditionné, alors la moindre erreur dans les données provoquera une erreur très importante dans la solution trouvée.

Un des problèmes les plus simples est l'évaluation d'une fonction à un point donné. Mais même l'évaluation d'un polynôme approchant n'est pas aussi évidente qu'il y parait : la méthode de Horner est souvent plus efficace que la méthode élémentaire basée sur les coefficients du polynôme développé et la simple somme de ses termes. Généralement, il est important d'estimer à l'avance et de contrôler les erreurs d'arrondis survenant lors de l'utilisation d'opérations arithmétiques en virgule flottante.

L'interpolation tente de résoudre ou d'approcher la solution au problème suivant : étant donné la valeur connue d'une certaine fonction en un certain nombre de points, quelle valeur prend cette fonction en un autre point quelconque situé entre deux points donnés ? Une méthode très simple est d'utiliser l'interpolation linéaire, qui suppose que la fonction inconnue évolue linéairement entre chaque paire de points successifs connus. Cette méthode peut être généralisée
en interpolation polynomiale, qui est parfois plus précise (on peut en
chiffrer la précision si les dérivées de la fonction sont connues jusqu'à
l'ordre N pour une interpolation à N points) et nécessite de plus petites
tables de valeurs connues, mais elle souffre du phénomène de Runge.

D'autres méthodes d'interpolation utilisent des fonctions localisées telles
que les splines ou la compression par ondelettes.

L'extrapolation est très similaire à l'interpolation, sauf que cette fois on veut déterminer la valeur d'une fonction en un point situé hors de l'intervalle des points connus. Dans certains cas (par exemple pour l'extrapolation de valeurs de fonctions cycliques, logarithmiques ou exponentielles), il est possible de réduire un problème d'extrapolation dans un domaine de définition très étendu voire infini, à un problème d'interpolation dans le sous-espace fini contenant les points connus.

La **régression** est une question voisine, prenant en compte l'imprécision des données. Il s'agira très souvent de mesures expérimentales entachées d'inévitables erreurs. Étant donné certains points, et la mesure de la valeur à ces points, on veut déterminer une fonction s'ajustant le mieux possible à ces valeurs. On recherche cette fonction dans une classe de fonctions simples, de façon à minimiser l'erreur effectuée. La méthode des moindres carrés est une façon courante de procéder.

Un autre problème fondamental est **le calcul des solutions d'un système d' équations donnée.** Deux cas sont communément distingués, suivant que l'équation est linéaire ou non.

De nombreux efforts ont été consacrés au développement de méthodes
de résolution de systèmes d'équations linéaires. Les méthodes
standards incluent l'élimination de Gauss-Jordan, et la décomposition
LU. Les méthodes itératives telles que la méthode de Gauss-Seidel et la
méthode de Jacobi sont généralement préférées sur les larges systèmes
d'équations.

Les algorithmes de recherche de racines d'une
fonction sont utilisés pour résoudre les équations non linéaires (elles
sont nommées ainsi car la racine d'une fonction est un argument pour
lequel la fonction retourne zéro). Si la fonction est différentiable et que
sa dérivée est connue, alors la méthode de Newton est un choix
populaire. La linéarisation est une autre technique pour la résolution
d'équations non linéaires.
Dans les **problèmes d'optimisation**, on recherche un point d'un ensemble en lequel une fonction définie sur cet ensemble est minimale (ou maximale). Cet ensemble est souvent défini comme une partie d'un espace vectoriel délimitée par des **contraintes**, c'est-à-dire par des égalités, des inégalités, des appartenances, définies au moyen d'autres fonctions.

L'intégration numérique, également connue comme quadrature numérique, recherche la valeur d'une intégrale définie. Les méthodes populaires sont basées sur les formules de Newton-Cotes (avec par exemple la méthode du point médian ou la méthode des trapèzes) ou utilisent les méthodes de quadrature de Gauss. Cependant si la dimension du domaine d'intégration devient large, ces méthodes deviennent aussi prohibitivement onéreuses. Dans cette situation, on peut utiliser une méthode de Monte-Carlo, une méthode de quasi-Monte-Carlo ou, dans des dimensions modestement larges, la méthode des grille incomplète (en).

L'analyse numérique traite également du calcul (de façon approchée) des **solutions d'équations différentielles**, que ce soit des équations différentielles ordinaires, ou des équations aux dérivées partielles.

Les **équations aux dérivées partielles** sont résolues en discrétisant d'abord l'équation, en l'amenant dans un sous-espace de dimension finie. Ceci peut être réalisé par une méthode des éléments finis, une méthode des différences finies ou, particulièrement dans l'ingénierie, une méthode des volumes finis. La justification théorique de ces méthodes implique souvent des théorèmes de l'analyse fonctionnelle. Ceci réduit le problème à la résolution d'une équation algébrique.
## 1.2 Bref aperçu sur l'ordinogramme et le pseudocode.

Dans ce fascicule, nous utiliserons la notion d'algorithmes et nous chercherons à résoudre le problème de l'expression de ces algorithmes. En effet, un algorithme doit être communiqué :

- D'abord à l'agent (humain ou machine) qui sera appelé à l'exécuter ;

- Ensuite à toute personne désireuse de l'apprendre, de l'étudier et, éventuellement, d'apporter des modifications.

Pour que cette communication atteigne son but, il faut que le moyen d'expression soit clairement précisé et défini. Pour ce faire nous utiliserons l'ordinogramme (ou organigramme) et le pseudo-code.

### 1- Ordinogramme

Un ordinogramme (voir figure ci-dessous) est un schéma symbolique conventionnel destiné à mettre en évidence les différentes étapes d'un algorithme et les relations qui existent entre celles-ci.

<figure><img src="image_2.png" /></figure>

Pour construire un ordinogramme, nous utiliserons quatre symboles fondamentaux :

#### a) Les flèches

Les flèches haut, bas, gauche et droite indiquent le sens du traitement.
<figure><img src="image_3.png" /></figure>

### b) La « boîte » de traitement

Elle sera représentée à l'aide d'un rectangle à une « entrée » et une « sortie ». La nature du traitement sera inscrite à l'intérieur de la boîte.

<figure><img src="image_4.png" /></figure>

### c) La « boîte » de décision

Lors d'un traitement, il peut arriver que l'on ait à choisir, à un moment donné, entre deux voies possibles. Nous exprimerons ce choix à l'aide de la « décision » que nous schématiserons par un losange à une « entrée » et deux « sorties ». Le contenu du losange est une condition (ou une combinaison de conditions) logique ; c'est-à-dire qu'elle n'admet que deux valeurs possibles : Vrai ou Faux, Oui ou Non, ....

<figure><img src="image_5.png" /></figure>

### d) Le nœud de jonction

Un nœud de jonction nous servira à traduire la convergence de deux chemins en un point.

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>
### e) Remarques

Les quatre symboles ci-dessus constituent les symboles de base à partir desquels se confectionnent les ordinogrammes. Il est cependant possible que l'on ait, dans certains cas, à utiliser d'autres symboles auxiliaires.

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

## 2- Pseudo-code

Le pseudo-code est un langage informel qui vise à exprimer un algorithme en restant indépendant de l'agent (humain ou machine) qui sera appelé à l'exécuter. Par exemple, quand nous écrivons :

### Lire A

Nous ne faisons aucune hypothèse sur la nature de l'organe d'entrée (clavier de terminal, lecteur de cartes, ...) ou sur la forme de la donnée à lire. Nous voulons tout simplement exprimer une action :

### Lire une donnée et attribuer la valeur lue à la variable A.

Une fois l'algorithme conçu, il va être nécessaire de traduire le pseudo-code dans un langage « compréhensible » par la machine.
# CHAPITRE 2. RESOLUTION DES EQUATIONS NON-LINEAIRES DE TYPE f (x).

## Introduction

Le numéricien est souvent confronté à la résolution d'équations algébriques de la forme :

$$f(x) = 0 \qquad (1)$$

et ce dans toutes sortes de contextes. Introduisons dès maintenant la terminologie qui nous sera utile pour traiter ce problème.

## Définition

Une valeur de $x$ solution de $f(x) = 0$ est appelée une racine ou un zéro de la fonction $f(x)$ et sera notée $x_s$.

### I- localisation de la racine de $f(x) = 0$

Soit $f(x)$ une fonction continue dont on veut calculer les racines (voir Fig. 1).

<figure><img src="image_17.png" /><figcaption>Figure 1</figcaption></figure>
Il faut d'abord :

- s'assurer que cette fonction a des racines

- isoler ou localiser chaque racine dans un intervalle monotone.

Pour cela, on peut chercher les variations de $f(x) = 0$ par l'étude de sa dérivée ou de manière graphique.

Ainsi, si $f(x) = 0$ est continue entre $[a ; b]$ et si $N$ est le nombre de racines dans ce cet intervalle :

- si $f(a) \times f(b) < 0$ alors $N$ est impair

- si $f(a) \times f(b) > 0$ alors $N$ est pair ou égal à 0

**NB** : En général, on ignore les variation et la forme de $f(x)$. Pour déceler les racines situées dans l'intervalle $[a ; b]$, on subdivise l'intervalle $[a ; b]$ en plusieurs intervalles de longueur h, petite devant les variations présumées. On a donc :

$$x_0 = a$$

$$x_1 = a + h$$

$$x_2 = a + 2h$$

∴

$$x_n = a + nh$$

- si $f(x_i) \times f(x_{i+1}) < 0$ alors il existe au moins une racine dans l'intervalle $[x_i ; x_{i+1}]$

- si $f(x_i) \times f(x_{i+1}) > 0$ alors il existe un nombre pair ou nul de racines.

Cette méthode (corollaire du théorème de Rolle) ne permet pas de déterminer les racines doubles.

**Remarque : cas particulier d'un polynôme**

Soit $P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ un polynôme. Cette fonction a au plus $n$ racines réelles et on montre qu'elles sont toutes contenues dans l'intervalle $[-R ; R]$ avec :

$$R = \frac{\max\{|a_i| \mid i=0,\dots,n\}}{a_n} + 1$$
## II- méthode de dichotomie ou de la bissection

### 1- principe de la méthode

La méthode de la bissection repose sur une idée toute simple, à savoir qu'en général, de part et d'autre d'une solution de l'équation (1), la fonction $f(x)$ change de signe et passe du positif au négatif et vice-versa (voir Fig. 1). De toute évidence, ce n'est toujours pas le cas puisque la fonction $f(x)$ peut aussi être tangente à l'axe des $x$.

Supposons que l'on ait localisé une et une seule racine $x_s$ dans l'intervalle $[a ; b]$, c'est-à-dire qu'il y ait effectivement un changement de signe autour de la racine ($f(a) \times f(b) < 0$).
Posons que :

$x_s = \frac{a+b}{2}$, milieu de $[a ; b]$.

* Si $f(a) \times f(x_s) < 0$ ou $f(x_s) \times f(b) > 0$, alors la solution $x_s$ se trouve dans l'intervalle $[a ; x_s]$. On remplace alors $b$ par $x_s$

* Si $f(a) \times f(x_s) > 0$ ou $f(x_s) \times f(b) < 0$, alors la solution $x_s$ se trouve dans l'intervalle $[x_s ; b]$. On remplace alors $a$ par $x_s$.

On obtient donc un nouvel intervalle $[a ; b]$ différent du précédent intervalle. Ce nouvel intervalle sera utilisé pour rechercher la racine de l'équation en usant de la procédure suscitée. Cela nous amène à l'algorithme suivant :

### 2- Pseudo-code

Algorithme dichotomie
a, b, c, x_s, ε des réels
faire (début)

- $x_s = \frac{a+b}{2}$

- si $f(a) \times f(x_s) < 0$ alors

- $b \leftarrow x_s$
  sinon $a \leftarrow x_s$

- jusqu'à ce que $\frac{|a-b|}{2} \le \varepsilon$

fin (faire)
imprimer $x_s$
fin
### 3. Ordinogramme

<figure><img src="image_18.png" /><figcaption>Figure 2</figcaption></figure>

### 4- Nombre d'itérations

On remarque aisément que la longueur de l'intervalle $[a ; b]$ entourant la racine $x_s$ est divisée par deux à chaque itération. Cette constatation permet de déterminer à l'avance le nombre d'itérations nécessaires pour obtenir une certaine erreur absolue $\Delta x_s = \frac{|b-a|}{2}$ sur la racine. Soit $L = b - a$ la longueur de l'intervalle de départ. Après une itération, le nouvel intervalle est de longueur $\frac{L}{2}$ et après $n$ itérations, la longueur de l'intervalle est :

$$ \frac{L}{2^n} = \frac{|b-a|}{2^n} $$

La valeur de $n$ nécessaires pour avoir $\frac{L}{2^n} = \Delta x_s$ est après résolution :

$$ n \geq \frac{\ln(b-a) - \ln \varepsilon}{\ln 2} $$
## 5- Critères d'arrêt des calculs

* 1er cas : si l'incertitude recherchée est atteinte, c'est-à-dire $\Delta x_s = \frac{|x_{n+1}-x_n|}{2} \le \varepsilon$.

* 2ième cas : si pendant le calcul de $x_s$, on rencontre $f(x_n) = 0$, alors $x_s = x_n$.

* 3ième cas : à la suite d'accumulation de valeurs tronquées, il peut arriver que $f(x_n) \times f(x_{n+1}) > 0$. On arrête alors les calculs et $x_s = x_{n-1}$ et $\Delta x_s = \Delta x_{n-1}$.

* 4ième cas : si le nombre maximal d'itérations $N_{max}$ est atteint.

**Remarques importantes**

Il peut arriver des cas ou la méthode de dichotomie achoppe.

<figure><img src="image_19.png" /><figcaption>Figure 3</figcaption></figure>

## III- méthode des points fixes ou des approximations successives

### 1- Définition du point fixe ou point invariant

Un point fixe d'une fonction $g(x)$ est une valeur de $x$ qui reste invariante pour cette fonction, c'est-à-dire toute solution de l'équation $x = g(x)$ est un point fixe de $g(x)$.

### 2- Principe de la méthode

Supposons que l'équation $f(x) = 0$ peut s'écrire sous la forme $x = g(x)$ ou $g(x)$ est une nouvelle fonction continue. La solution $x_s$ se trouve à l'intersection de la bissectrice $y = x$ et de la courbe de $g(x)$ (voir figure 4).

Supposons connue une valeur approchée $x_0 = a$ de la racine. A $x_0 = a$ correspond sur la courbe de $g(x)$ un point $M_0$. Si nous faisons $x_1 = g(x_0)$ à travers la bissectrice, $x_1$ est la nouvelle valeur approchée de la racine. A $x_1$ correspond le point $M_1$ sur la courbe de $g(x)$ dont l'ordonnées est $g(x_1)$. Ainsi, si nous posons :
$$ 
\begin{array}{l}
x_1 = g(x_0) \\
x_2 = g(x_1) \\
\vdots \\
x_{n+1} = g(x_n)
\end{array}
 $$

On définit de la sorte une suite :

$$ 
\begin{cases} x_0 = a \\ x_{n+1} = g(x_n) \quad \forall n > 0 \end{cases} 
 $$

Si cette suite (converge) a une limite $x_s$, cette limite est telle que $x_s = g(x_s)$. C'est un point fixe de $g(x)$. Cette limite, si elle existe est la racine de $f(x) = 0$.

<figure><img src="image_20.png" /><figcaption>Figure 4</figcaption></figure>

### 3- Organigramme

<figure><img src="image_21.png" /><figcaption>Figure 5</figcaption></figure>
## 4- Convergence de la méthode

Soit $x_s$ qui est à la fois une racine de $f(x)$ et un point fixe de $g(x)$. On définit l'erreur à l'étape $n$ comme étant $e_n = x_n - x_s$.

On cherche à déterminer sous quelles conditions l'algorithme converge vers $x_s$. Ce sera bien sûr le cas si l'erreur tend vers 0 si $n$ devient grand.

A l'étape $n + 1$, on a :

$$e_{n+1} = x_{n+1} - x_s$$

Or $x_{n+1} = g(x_n)$ et $x_s = g(x_s)$

$$\text{D'où } e_{n+1} = x_{n+1} - g(x_s) = g(x_s + e_n) - g(x_s)$$

Si nous faisons un développement de Taylor de la fonction $g(x)$ autour de la racine $x_s$, on a :

$$e_{n+1} = \left\{ g(x_s) + g'(x_s)x_s + \frac{g''(x_s)x_s^2}{2!} + \frac{g'''(x_s)x_s^3}{3!} + \dots \right\} - g(x_s)$$

On conclut donc que :

$$e_{n+1} = g'(x_s)x_s + \frac{g''(x_s)x_s^2}{2!} + \frac{g'''(x_s)x_s^3}{3!} + \dots$$

### a) Condition de convergence

Si $g'(x_s) \neq 0$ et si on néglige les termes d'ordre supérieur ou égal à 2 en $e_n$, on obtient :

$$e_{n+1} = e_n g'(x_s)$$

Soit $\frac{e_{n+1}}{e_n} = g'(x_s)$

L'erreur ne pourra donc diminuer que si $|g'(x_s)| < 1$.

$|g'(x_s)| < 1$ est une condition nécessaire de convergence de la méthode des points fixes.

### b) Taux de convergence

Le taux de convergence d'une méthode des points fixes est donnée par $|g'(x_s)|$. En effet, plus $|g'(x_s)|$ est petit, plus l'erreur diminue vite et donc plus la convergence est rapide.
### c) Ordre d'une méthode

Dans le cas du taux de convergence, le cas limite est $g'(x_s) = 0$. Dans ce cas, on néglige tous les termes d'ordre supérieur ou égal à 3 en $e_n$ dans le développement de Taylor. Ainsi :

$$e_{n+1} = \frac{e_n^2 g''(x_s)}{2}$$

NB : on dit qu'une méthode des points fixes converge à l'ordre $p$ si $|e_{n+1}| = C |e_{n+1}|^p$ ou $C$ est une constante.

#### Remarque :

* Si $|g'(x_s)| < 1$ et $|g'(x_s)| \neq 0$, la méthode converge à l'ordre 1. La convergence est linéaire.

* Si $|g'(x_s)| = 0$ et $|g''(x_s)| \neq 0$, la méthode converge à l'ordre 2. La convergence est quadratique.

* Si $|g'(x_s)| = 0$, $|g''(x_s)| = 0$ et $|g'''(x_s)| \neq 0$, la méthode converge à l'ordre 3.

### d) Bassin d'attraction

La convergence d'une méthode des points fixes est également assujettie au choix de la valeur initiale $x_0$. En effet, un mauvais choix de $x_0$ peut résulter en un algorithme divergent, même si la condition de convergence est respectée. Ainsi, le bassin d'attraction de la racine $x_s$ est l'ensemble des valeurs initiales $x_0$ pour lesquelles $x_n$ tend vers $x_s$ lorsque $n$ tend vers l'infini. C'est donc l'ensemble de tous les points $x_0$ pour lesquels la méthode converge vers $x_s$.

### e) Point attractif ou répulsif

* Un point fixe $x_s$ est dit attractif si $|g'(x_s)| < 1$.

* Un point fixe $x_s$ est dit répulsif si $|g'(x_s)| > 1$.

* Le cas où $|g'(x_s)| = 1$ est indéterminé.

## 5- Incertitude de la méthode

Si la méthode converge, la différence entre les deux derniers termes consécutifs représente l'incertitude et est de la forme :

$$|x_{n+1} - x_n| \le \varepsilon$$

Avec $\varepsilon$ fixée d'avance.
IV- méthode de Newton

La méthode de Newton est l'une des méthodes les plus utilisées pour la résolution des équations non linéaires. Cette méthode possède également une belle interprétation géométrique. On peut cependant obtenir son algorithme en utilisant un développement de Taylor.

1- Principe de la méthode

a) Algorithmes par le développement de Taylor

Soit une équation à résoudre de la forme $f(x) = 0$. A partir d'une valeur initiale $x_0$ qui est une valeur approchée de la solution $x_s$ recherchée, on cherche une correction $\delta x$ telle que :

$$f(x_0 + \delta x) = 0$$

En faisant un développement de Taylor autour de $x = x_0$, on obtient :

$$f(x_0) + f'(x_0)\delta x + \frac{f''(x_0)(\delta x)^2}{2!} + \frac{f'''(x_0)(\delta x)^3}{3!} + \cdots = 0$$

Négligeons, dans l'expression ci-dessus, les termes d'ordre supérieur ou égal à 2. On obtient :

$$f(x_0) + f'(x_0)\delta x = 0$$

Soit

$$\delta x = - \frac{f(x_0)}{f'(x_0)}$$

La correction $\delta x$ est en principe la quantité que l'on doit ajouter à $x_0$ pour annuler la fonction $f(x)$. Puisque nous avons négligé les termes d'ordre supérieur ou égal à 2 dans le développement de Taylor, cette correction n'est pas parfaite et on pose :

$$x_1 = x_0 + \delta x$$

$$\text{Soit donc : } x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$

Soit $x_1$ la nouvelle valeur approchée de la solution recherchée. Si nous reprenons toute la démonstration ci-dessus à partir de $x_1$, on obtient donc de proche en proche :

$$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$

$$x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}$$

$$x_3 = x_2 - \frac{f(x_2)}{f'(x_2)}$$

⋮
D'où la relation de récurrence de Newton :
$$ 
\begin{cases} x_0 = a \\ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} ; \forall n \end{cases}
$$

b) Algorithme par interprétation géométrique

On suppose que $f(x)$ est définie, continue et dérivable dans le domaine considérée et qu'elle y possède une racine. Sur la figure ci-dessous, on a représenté la fonction $f(x)$, la valeur initiale $x_0$ qui est la valeur approchée de la racine et le point $M_0(x_0, f(x_0))$ appartenant à $C_f$.

La droite tangente à $C_f$ en $M_0$ est de pente $f'(x_0)$ et a pour équation :

$$y = f(x_0) + f'(x_0)(x - x_0)$$

Cette droite coupe l'axe (ox) en y = 0, c'est-à-dire que pour $x = x_1$, $y = 0$ et on obtient

$$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$

On reprend ensuite le raisonnement à partir du nouveau point $M_1(x_1, f(x_1))$. De proche en proche, on a :

$$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$

$$x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}$$

D'où la relation de récurrence de Newton :

$$
\begin{cases} x_0 = a \\ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} ; \forall n \end{cases}
$$

<figure><img src="image_22.png" /></figure>
## 2- Organigramme

<figure><img src="image_23.png" /></figure>

## 3- Analyse de la convergence

La méthode de Newton est un cas particulier de la méthode des points fixes où :

$$g(x) = x - \frac{f(x)}{f'(x)} \text{ et } g(x) = x$$

$$g'(x) = 1 - \frac{[f'(x)]^2 - f(x)f''(x)}{[f'(x)]^2}$$

Soit après calcul

$$g'(x) = \frac{f(x)f''(x)}{[f'(x)]^2}$$

Puisque $x_s$ est une racine de $f(x)$, alors $f(x_s) = 0$. D'où on tire que $g'(x_s) = 0$ si on suppose que $f'(x_s) \neq 0$

On vient de montrer que la convergence de la méthode de Newton est au moins quadratique.

**NB :**

Dans le cas où $f'(x_s) = 0$, le résultat précédent n'est plus vrai dans la mesure où $g'(x_s)$ pourra être différent de 0.
### 4- Remarques : choix de $x_0$ pour que la méthode converge

Si $f$ est définie dans l'intervalle $[a; b]$ et vérifie :

* $f(a) \times f(b) < 0$

* $\forall x \in [a; b], f'(x) \neq 0$ (strictement monotone)

* $\forall x \in [a; b], f''(x) \neq 0$ (concavité dans le même sens)

Alors en choisissant $x_0 \in [a; b]$ tel que $f(x_0) \times f''(x_0) > 0$, la méthode de Newton converge vers la solution recherchée.

### V- méthode de la sécante ou de Lagrange

La méthode de Newton possède de grands avantages, mais elle nécessite le calcul de la dérivée de $f(x)$. Si la fonction est complexe, cette dérivée peut être difficile à évaluer et peut résulter en une expression complexe. On contourne cette difficulté en remplaçant le calcul de la pente $f'(x)$ de la droite tangente à la courbe.

#### 1- Principe de la méthode (figure ci-dessous)

A partir de deux valeurs approchées $x_0$ et $x_1$ de la racine $x_s$ recherchée, on construit une suite de valeurs $x_i$ qui converge vers $x_s$. $x_{i+1}$ se déduit de $x_{i-1}$ et de $x_i$ par interpolation linéaire. Graphiquement, si $M_i$ est le point de coordonnées $(x_i, f(x_i))$, $x_{i+1}$ est l'abscisse du point d'intersection de l'axe (ox) et de la droite passant par les points $M_i(x_i, f(x_i))$ et $M_{i-1}(x_{i-1}, f(x_{i-1}))$.

La droite $M_i M_{i-1}$ a pour équation $y = Ax + B$ avec :

$$ \begin{cases} A x_i + B = f(x_i) \\ A x_{i-1} + B = f(x_{i-1}) \end{cases} $$

Soit donc que :

$$ \begin{aligned} A &= \frac{f(x_i) - f(x_{i-1})}{x_i - x_{i-1}} \\ B &= f(x_i) - x_i \frac{f(x_i) - f(x_{i-1})}{x_i - x_{i-1}} \end{aligned} $$

Comme à $x = x_{i+1}$, on a $y = 0$ alors on obtient :

$$ x_{i+1} = x_i - \frac{f(x_i)(x_i - x_{i-1})}{f(x_i) - f(x_{i-1})} $$
La généralisation de cette relation donne la relation de récurrence de la méthode des sécantes :

$$ \begin{cases} x_{n+1} = x_n - \frac{f(x_n)(x_n - x_{n-1})}{f(x_n) - f(x_{n-1})} & \forall n \end{cases} $$

<figure><img src="image_24.png" /></figure>

## 2- Remarque

* Il faut fournir au départ deux valeurs initiales. C'est ce qu'on appelle un algorithme à deux pas.

* On choisit les valeurs initiales le plus près possible de la racine recherchée. Il n'est cependant pas nécessaire qu'il y ait un changement de signe dans l'intervalle $[x_0; x_1]$ comme dans le cas de la méthode de dichotomie.

* L'algorithme se termine si $|x_{n+1} - x_n| \le \epsilon$.
PROBLEME

Selon le théorème d'Archimède, tout corps plongé dans un fluide reçoit de la part de celui-ci une poussée verticale dirigée de bas en haut et égale au poids du volume de fluide déplacé par le corps. Supposons qu'une sphère de rayon $r$, de masse volumique $\rho_s$ est plongée dans un fluide de masse volumique $\rho_l$ et est en équilibre comme le montre la figure ci-dessous.

<figure><img src="image_25.png" /></figure>

Le volume de la sphère et sont poids sont respectivement :

$$v_s = \frac{4}{3}\pi r^3 \text{ et } P_s = m_s g = \rho_s v_s g = \frac{4}{3}\pi \rho_s r^3.$$

Le volume du liquide déplacé et son poids sont respectivement :

$$v_l = \frac{1}{3}\pi x^2 (3r - x) \text{ et } P_l = m_l g = \rho_l v_l g = \frac{1}{3}\pi \rho_l x^2 (3r - x).$$

La sphère étant en équilibre, alors $P_s = P_l$ soit donc :

$$\frac{4}{3}\pi \rho_s r^3 = \frac{1}{3}\pi \rho_l x^2 (3r - x).$$

Supposons que le fluide soit de l'eau ($\rho_l = 1000 \text{ kg.m}^{-3}$) et que la sphère soit un corps de masse volumique ($\rho_s = 200 \text{ kg.m}^{-3}$) de rayon unité ($r = 1 \text{ m}$).

On veut connaitre la profondeur d'immersion $x$ de la sphère. Pour cela, on résoudra l'équation :

$$x^3 - 3x^2 + 0.8 = 0$$

Qui est une équation non-linéaire dont on cherche la racine.
### Résolution du problème

Dans le cas du problème posé en début de chapitre, l'équation admet au plus $n = 3$ racines réelles contenues dans l'intervalle $[-R; R] = [-4; 4]$ avec $R = \frac{|-3|}{1} + 1 = 4$. En faisant une tabulation par pas de 1 (voir tableau) on note que :

$$f(-1) \times f(0) < 0, f(0) \times f(1) < 0 \text{ et } f(2) \times f(3) < 0.$$

<table><tr><td>x</td><td>-4</td><td>-3</td><td>-2</td><td>-1</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td></tr><tr><td>f(x)</td><td>-111.2</td><td>-53.2</td><td>-19.2</td><td>-3.2</td><td>0.8</td><td>-1.2</td><td>-3.2</td><td>0.8</td><td>16.8</td></tr></table>

Puisque $x > 0$, alors la profondeur d'immersion peut se trouver dans les intervalles $x \in [0m; 1m]$ et $[2m; 3m]$. Ce qui signifierait que lors de l'oscillation de la balle, la première profondeur qu'elle atteindrait se situerait dans l'intervalle $[2m; 3m]$. A la fin de l'oscillation, lorsqu'elle est en équilibre, la profondeur se situerait dans l'intervalle $[0m; 1m]$. cherchons par exemple $x \in [2m; 3m]$.

### Méthode de dichotomie :

Si on pose que $\varepsilon = 10^{-2}$ alors la solution est $x = 2.905 \text{ m}$ après 10 itérations (voir tableau).

<table><tr><td>n</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td>a</td><td>2.000</td><td>2.500</td><td>2.750</td><td>2.875</td><td>2.875</td><td>2.875</td><td>2.891</td><td>2.898</td><td>2.902</td><td>2.904</td><td>2.904</td></tr><tr><td>b</td><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td><td>2.938</td><td>2.906</td><td>2.906</td><td>2.906</td><td>2.906</td><td>2.906</td><td>2.905</td></tr><tr><td>c</td><td>2.500</td><td>2.750</td><td>2.875</td><td>2.938</td><td>2.906</td><td>2.891</td><td>2.898</td><td>2.902</td><td>2.904</td><td>2.905</td><td>2.905</td></tr><tr><td>f(a)</td><td>-3.200</td><td>-2.325</td><td>-1.091</td><td>-0.233</td><td>-0.233</td><td>-0.233</td><td>-0.114</td><td>-0.053</td><td>-0.023</td><td>-0.007</td><td>-0.007</td></tr><tr><td>f(c)</td><td>-2.325</td><td>-1.091</td><td>-0.233</td><td>0.261</td><td>0.008</td><td>-0.114</td><td>-0.053</td><td>-0.023</td><td>-0.007</td><td>0.000</td><td>-0.003</td></tr><tr><td>Δx = <div style="display: inline-block; vertical-align: middle; text-align: center;"><div style="border-bottom: 1px solid black; padding-bottom: 1px;">(b - a)</div><div style="padding-top: 1px;">2</div></div></td><td>5.E-01</td><td>3.E-01</td><td>1.E-01</td><td>6.E-02</td><td>3.E-02</td><td>2.E-02</td><td>8.E-03</td><td>4.E-03</td><td>2.E-03</td><td>1.E-03</td><td>5.E-04</td></tr></table>

### Méthode du point fixe :

Posons que $x = g(x)$ avec $g(x) = (3x^2 - 0.8)^{\frac{1}{3}}$. On montre aisément que $x = g(x)$ est équivalent à $f(x) = 0$.

On représente graphiquement $y = x$ et $g(x)$ (voir graphique 2).

$$x \in [2m; 3m] \quad g'(x) = \frac{1}{3} \cdot 6x (3x^2 - 0.8)^{-\frac{2}{3}}$$

$$g'(2) = 0.79 < 1 \text{ et } g'(3) = 0.68 < 1$$

D'où pour $x \in [2m; 3m]$, $|g'(x)| < 1$ la méthode est donc convergente.

Si on pose que $\varepsilon = 10^{-2}$, $x_0 = 2$ alors la solution est $x = 2.887 \text{ m}$ après 11 itérations (voir tableau).

<table><tr><td>n</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td></tr><tr><td>x<sub>n</sub></td><td>2.000</td><td>2.237</td><td>2.423</td><td>2.561</td><td>2.603</td><td>2.736</td><td>2.787</td><td>2.823</td><td>2.849</td><td>2.866</td><td>2.878</td><td>2.887</td></tr><tr><td>Δx = |x<sub>n+1</sub> - x<sub>n</sub>|</td><td>2.E-01</td><td>2.E-01</td><td>1.E-01</td><td>1.E-01</td><td>7.E-02</td><td>5.E-02</td><td>4.E-02</td><td>3.E-02</td><td>2.E-02</td><td>1.E-02</td><td>8.E-03</td></tr></table>

### Méthode de Newton

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^3 - 3x_n^2 + 0.8}{3x_n^2 - 6x_n}$$

Si on pose que $\varepsilon = 10^{-2}$, $x_0 = 2.1$ alors la solution est $x = 2.905 \text{ m}$ après 7 itérations (voir tableau).
Si on pose que $\epsilon = 10^{-2}$, $x_0 = 2.1$ alors la solution est $x = 2.905 \text{ m après } 7 \text{ itérations (voir tableau)}$.

<table><thead><tr><th>n</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><td>x<sub>n</sub></td><td>2.100</td><td>7.130</td><td>5.209</td><td>3.998</td><td>3.299</td><td>2.984</td><td>2.909</td><td>2.905</td></tr><tr><td>&Delta;x = |x<sub>n+1</sub> - x<sub>n</sub>|</td><td></td><td>5.E+00</td><td>2.E+00</td><td>1.E+00</td><td>7.E-01</td><td>3.E-01</td><td>7.E-02</td><td>4.E-03</td></tr></tbody></table>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

Exercices sur la résolution des équations de type $f(x) = 0$

Exercice 1

On donne une fonction $f$ définie sur $[\alpha; \beta]$. On subdivise $[\alpha; \beta]$ en plusieurs petits intervalles de longueur $p$ et on suppose que la racine $v$ de cette fonction appartient à l'un de ces petits intervalles. Donner l'ordinogramme qui permet de localiser pas à pas la racine $v$.

Indications : se référer au cours

Exercice 2

On considère la fonction $f(x) = e^x + 3\sqrt{x} - 2$ sur l'intervalle $[0; 1]$.

1- Montrer qu'il existe une racine $\alpha$ pour la fonction $f$ dans $[0; 1]$ et qu'elle est unique.

2- On veut calculer $\alpha$ par une méthode des approximations successives convenablement choisie. En particulier, on se donne deux méthodes $x = g_1(x)$ où les fonctions $g_1$ et $g_2$ sont définies comme suit :

$$g_1(x) = \ln(2 - 3\sqrt{x})$$ $$g_2(x) = \frac{(2 - e^{-x})^2}{9}$$

Laquelle de ces deux méthodes utiliseriez-vous pour calculer numériquement la racine de la fonction $f$ ? Justifier votre réponse.

3- Représenter la marche de la méthode choisie pour $x_0 = 0$.

4- En utilisant la méthode de dichotomie sur $[0; 1]$, estimer le nombre d'itérations nécessaires pour calculer la racine $\alpha$ de la fonction $f$ avec une tolérance de $10^{-3}$.

Calculer la racine $\alpha$ par cette méthode à $10^{-3}$ près.
Indications :

1- $f(0) = -1$; $f(1) = e + 1 > 0$ et la fonction $f$ est continue et strictement croissante sur $[0; 1]$. Donc il existe une racine $\alpha \in [0; 1]$ de $f$ et elle est unique.

$$2-g_1(\alpha) = \ln(2-3\sqrt{\alpha}) = \ln(e^\alpha) = \alpha \arctan e^\alpha + 3\sqrt{\alpha} - 2 = 0 \Leftrightarrow e^\alpha = 2-3\sqrt{\alpha}$$

$$g_2(\alpha) = \frac{(2-\alpha)^2}{9} = \frac{(3\sqrt{\alpha})^2}{9} = \alpha \arctan e^\alpha + 3\sqrt{\alpha} - 2 = 0 \Leftrightarrow 3\sqrt{\alpha} = 2 - e^\alpha$$

D'où $\alpha$ est un point fixe pour chacune des deux méthodes.

Considérons maintenant la fonction $g_1$ définie dans l'intervalle $[0; \frac{4}{9}]$ (ensemble de définition). $|g'_1(x)| = \left|\frac{3}{4\sqrt{x}-6x}\right|, \forall x \in [0; \frac{4}{9}]$

$\forall x \in [0; \frac{4}{9}], |g'_1(x)| > 1$. La condition de convergence n'étant pas respectée, cette méthode ne converge pas (on peut aussi calculer $g''_1$ et procéder à un tableau de variation).

Considérons maintenant la fonction $g_2$ sur $[0; 1]$ qui contient la racine. $|g'_2(x)| = \left|\frac{2e^x(e^x-2)}{9}\right|$. Soit : $|g'_2(1)| = \left|\frac{2e(e-2)}{9}\right| < 1$ et $|g'_2(0)| = \left|\frac{2(1-2)}{9}\right| = \frac{2}{9} < 1$

$\forall x \in [0; 1], |g'_2(x)| > 1$. La méthode est convergente. Elle sera donc choisie.

$$3- \frac{|b-a|}{2^n} \le 10^{-\beta} \Rightarrow n \ge \frac{\log|b-a|+\beta\log 10}{\log 2} \approx 10 \text{ itérations}$$

Exercice 3

On veut calculer les racines de l'équation $f(x) = \frac{x}{2} - \sin(x) + \frac{\pi}{6} - \frac{\sqrt{3}}{2} = 0$ dans l'intervalle $[-\frac{\pi}{2}; \pi]$.

1- Tracer le graphe de la fonction $f$. Combien de racines possède la fonction ? faire la tabulation de la fonction en utilisant un pas de $\frac{\pi}{6}$.

2- On pose que la fonction possède deux racines $\alpha_1$ et $\alpha_2$.

a) Peut-on appliquer la méthode de dichotomie pour calculer ces racines ? pourquoi ?

b) Dans le cas où c'est possible, estimer le nombre minimale d'itérations pour calculer la (les) racine(s) avec une tolérance de $10^{-10}$ après avoir choisi un intervalle convenable.

3- Ecrire la méthode de Newton pour la fonction $f$.

Cette fois-ci, on pose que $\alpha_2 \in [\frac{2\pi}{3}; \frac{5\pi}{6}]$. Choisir $x_0$ de manière que la méthode converge vers $\alpha_2$. Trouver l'ordre de convergence de la méthode pour les deux racines.

4- On considère maintenant la méthode des approximations successives $x_{n+1} = g(x_n)$ avec :

$$g(x_n) = \sin(x_n) + \frac{x_n}{2} - \left(\frac{\pi}{6} - \frac{\sqrt{3}}{2}\right)$$

On veut calculer la racine $\alpha > 0$.

a) Démontrer que $g(\alpha) = \alpha - f(\alpha) = 0$

b) En observant que $\alpha \in [\frac{2\pi}{3}; \pi]$, établir si cette méthode est convergente.

Indications :

1- D'après le graphe, la fonction possède 2 racines comprises dans les intervalles $\alpha_1 = [-\frac{\pi}{2}; 0]$ et $\alpha_2 = [\frac{2\pi}{3}; \pi]$

<table><thead><tr><th>x</th><th>-π/2</th><th>-π/3</th><th>-π/6</th><th>0</th><th>π/6</th><th>π/3</th><th>π/2</th><th>2π/3</th><th>5π/6</th><th>π</th></tr></thead><tbody><tr><th>x</th><td>-1.57</td><td>-1.05</td><td>-0.52</td><td>0.00</td><td>0.52</td><td>1.05</td><td>1.57</td><td>2.09</td><td>2.62</td><td>3.14</td></tr><tr><th>f(x)</th><td>-0.13</td><td>0.00</td><td>-0.10</td><td>-0.34</td><td>-0.58</td><td>-0.68</td><td>-0.56</td><td>-0.16</td><td>0.47</td><td>1.23</td></tr></tbody></table>
2- On peut appliquer la méthode de dichotomie pour trouver $\alpha_2$ car on remarque que $f(-\frac{\pi}{2}) \times f(0) < 0$.

Dans le cas de $\alpha_1$, cela n'est pas possible car $f(\frac{2\pi}{3}) \times f(\pi) > 0$

Le nombre d'itérations pour calculer $\alpha_2$ est :

$$ \frac{|b-a|}{2^n} \le 10^{-\beta} \Rightarrow n \ge \frac{\log|b-a| + \beta \log 10}{\log 2} \approx 32 \text{ itérations} $$

3- La méthode de Newton s'écrit :

$$ x_{n+1} = g(x_n) \text{ avec } g(x) = x - \frac{f(x)}{f'(x)} = x - \frac{\frac{x}{2}\sin x + \frac{\pi}{6}\sqrt{\frac{3}{2}}}{\frac{1}{2}\cos x} $$

Pour que la méthode de Newton converge vers $\alpha_2$, il faut que $f(x_0) \times f''(x_0) > 0$. Utilisons donc l'intervalle $\alpha_2 = [\frac{2\pi}{3}; \frac{5\pi}{6}]$ avec : $f''(x) = \sin x$

$$ f\left(\frac{2\pi}{3}\right) \times f''\left(\frac{2\pi}{3}\right) = -0,16 \times \frac{\sqrt{3}}{2} < 0 \quad \text{et} \quad f\left(\frac{5\pi}{6}\right) \times f''\left(\frac{5\pi}{6}\right) = 0,47 \times \frac{1}{2} > 0 $$

On a donc $x_0 = \frac{5\pi}{6}$.

$$ 4 - \alpha - f(\alpha) = \frac{\alpha}{2} + \sin(\alpha) - \left(\frac{\pi}{6} - \frac{\sqrt{3}}{2}\right) = g(\alpha) $$

On sait que $g'(\alpha) = 1 - f'(\alpha) = \frac{1}{2} + \cos(\alpha)$

$$ \frac{2\pi}{3} \le \alpha \le \pi \text{ alors } -0 \le \frac{1}{2} + \cos(\alpha) \le -0,5 \Rightarrow |g'(\alpha)| < 1. \text{ la méthode converge vers } \alpha. $$

## Exercice 4

Une particule se déplace sur un plan incliné qui fait un angle $\theta$ par rapport à l'horizontale (voir figure ci-dessous). On note que $\theta$ croit à un taux constant $\omega$ tel que :

Acti

$$ \frac{d\theta}{dt} = \omega $$

A la fin du mouvement à t secondes, la position de la particule est donnée par :

$$ x(t) = \frac{g}{2\omega^2} \left( \frac{e^{\omega t} - e^{-\omega t}}{2} - \sin \omega t \right) $$

Supposons que la particule s'est déplacée de 0.53 m en 1 s. Trouver par la méthode de dichotomie, avec une tolérance de $10^{-5}$, le taux $\omega$ pour lequel $\theta$ change si l'intervalle de départ est $[\omega_0 = 0.1; \omega_1 = 1]$. on prendra $g = 10 \text{ m/s}^2$.

<figure><img src="image_28.png" /></figure>

**Indications** : on trouve $\omega = 0,31706 \text{ rad au bout de 16 itérations}$

## Exercice 5

Un mobile décrit un mouvement rectiligne uniformément varié d'équation : $x(t) = \frac{1}{2}a_0t^2 + v_0t + x_0$

On pose : $x_0 = -c$ ($c > 0$); $v_0 = 0\text{ms}^{-1}$; $a_0 = 2\text{ms}^{-2}$; $x(t) = f(t)$

On veut évaluer le temps $t$ ($t > 0$) nécessaire au mobile pour passer par le point origine.

Pour cela, on résoudra l'équation : $f(t) = t^2 - c = 0$.

**Application numérique** : aux questions 2, 3 et 4, on prendra $c = 5$.
### 1) Localisation de la racine

a) combien de racines possède $f(t)$ et dans quel intervalle sont-elles contenues?

b) montrer qu'il existe une solution unique $t_s \in [0; +\infty[$.

c) en déduire les valeurs de $c$ pour lesquelles $t_s \in [0; c]$.

### 2) Méthode de dichotomie

On considère maintenant que l'intervalle de départ est $[0; c]$. On utilise la méthode de dichotomie pour résoudre l'équation $f(t) = 0$.

a) donner les 7 premières valeurs, avec 5 chiffres significatifs, de $t_i$ en remplissant le tableau ci-dessous.

<table><thead><tr><th>Indice i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>Borne inférieure a<sub>i</sub></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Borne supérieure b<sub>i</sub></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>t<sub>i</sub></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

b) déterminer le nombre d'itérations nécessaires pour avoir une erreur $\epsilon \le 10^{-\beta}$ avec $\beta \in N^*$ dans les cas suivants: $\beta = 3$ et $\beta = 5$.

### 3) Méthode des approximations successives

Pour évaluer le temps $t$ ($t > 0$) nécessaire au mobile pour passer par le point origine, on propose la méthode suivante: $A_0 = \begin{cases} t_0 & \text{avec } g(t) = \frac{t}{2c}(3c - t_n^2) \\ t_{n+1} = \frac{t_n}{2c}(3c - t_n^2) & \text{avec } g(t) = \frac{t}{2c}(3c - t_n^2) \end{cases}$.

a) montrer que 0 est un point fixe de $f(t)$.

b) pour quelles valeurs de $t_0$ la méthode $A_0$ est-elle convergente?

c) représenter géométriquement la marche de la méthode pour $t_0 = 2s$.

d) donner les 6 premières valeurs avec 5 chiffres significatifs, de $t_i$ en remplissant le tableau ci-dessous. En déduire la racine et la précision obtenue.

<table><thead><tr><th>Indice i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><td>t<sub>i</sub></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

### 4) Méthode de Newton

a) déterminer la relation de récurrence entre $t_{n+1}$ et $t_n$ à partir de la méthode de Newton.

b) On pose $g(t_n) = t_{n+1}$. Montrer que $g'(f) = \frac{f(t)f''(t)}{[f'(t)]^2}$.

c) quel est l'ordre de convergence de cette méthode?

d) montrer que pour $t_0 = \sqrt{\frac{4c}{3}}$ la méthode de Newton converge vers la racine. Calculer les 5 premiers termes de la suite $(t_n)_{n=0,4}$ avec 5 chiffres significatifs. Quelle est la précision obtenue?

e) comparer avec la valeur exacte de $c = 2.23607$.

**Indications**

**Localisation de la racine**

Cette fonction a au plus 2 racines réelles.

$f$ est monotone $\forall x \ge 0$ et $f(t) \in [-c; +\infty[$. D'où il existe une solution unique $t_s \in [0; +\infty[$.

Si $t_s \in [0; c]$ alors $f(0) \times f(c) < 0 \Rightarrow c > 1$.
### Méthode de dichotomie

$\beta = 3 \Rightarrow n = 13$ itérations; $\beta = 5 \Rightarrow n = 19$ itérations

### Méthode des approximations successives

$$g(0) = \frac{0}{2c}(3c - 0) = 0$$

$$g'(t) = \frac{3}{2c}(c - t^2), \text{ la méthode est convergente si } |g'(t)| < 1 \Rightarrow \frac{\sqrt{c}}{3} < t < \frac{\sqrt{5c}}{3}$$

La racine est $t_s = 2,23607$ et $\Delta \approx 0$

### Méthode de Newton

$$t_{n+1} = t_n - \frac{f(t)}{f'(t)}$$

$$\text{La méthode converge vers la racine si } |g'(t_0)| < 1 \Rightarrow g'\left(\sqrt{\frac{4c}{3}}\right) = \frac{c}{3} \times \frac{3}{8c} = \frac{1}{8} < 1$$

$t_s = 2,23607$ s
# Chapitre 3 : Interpolation et approximation

## Problème :

Soit un tableau donnant la répartition statistique des âges des membres d'une association des élèves, étudiants et cadres d'un village. Supposons que l'on ait ordonné ces personnes par ordre croissant de leur âge. Trouver par interpolation l'âge de la 72<sup>ième</sup> personne.

<table><thead><tr><td>Tranche d'âge</td><td>Effectif</td><td>Effectif croissant cumulé</td></tr></thead><tbody><tr><td>[0; 10[</td><td>14</td><td>14</td></tr><tr><td>[10; 20[</td><td>32</td><td>46</td></tr><tr><td>[20; 30[</td><td>55</td><td>101</td></tr><tr><td>[30; 40[</td><td>45</td><td>146</td></tr><tr><td>[40; 50[</td><td>16</td><td>162</td></tr><tr><td>[50; 60[</td><td>14</td><td>176</td></tr><tr><td>[60; 70[</td><td>20</td><td>196</td></tr><tr><td>[70; 80[</td><td>4</td><td>200</td></tr><tr><td>Total</td><td>200</td><td></td></tr></tbody></table>

## Introduction

Il arrive souvent que la fonction $f(x)$ que l'on doit traiter soit définie d'une façon qui rende sa manipulation aisée, ou encore ce qui est le plus fréquent, qu'elle soit définie pour un certain nombre de valeurs discrètes de la variable. Il est dans ce cas nécessaire de remplacer la fonction $f(x)$ à traiter par une fonction approchée $g(x)$ plus simple ou encore par un ensemble de fonctions puis de traiter non plus $f(x)$ mais $g(x)$. Dans ce chapitre, on imposera à $g(x)$ de coïncider avec $f(x)$ pour un certain nombre de valeurs de $x$ tel que $g(x_i) = f(x_i)$. On parlera donc de **polynôme de collocation**. Notons que le degré de $g(x)$ sera égal à $n - 1$ où $n$ est le nombre de valeurs où $f(x)$ est définie.

### I- Interpolation linéaire

Etant donnée une fonction numérique $f(x)$ définie en deux points $a$ et $b$ du segment $[a; b]$ (voir figure ci-dessous), on peut approcher $f(x)$ par le polynôme $g(x)$ de degré 1 (c'est donc un monôme !!!) qui coïncide avec $f(x)$ en $a$ et $b$.

Le polynôme $g(x)$ est tel que $g(x) = Ax + B$ avec :

$$g(a) = f(a) \text{ et } g(b) = f(b)$$
Le polynôme $g(x)$ sera donc :

$$g(x) = \frac{f(a) - f(b)}{a - b} x + \frac{af(b) - bf(a)}{a - b}$$

Ou encore :

$$g(x) = f(a) \frac{x-b}{a-b} - f(b) \frac{x-a}{a-b}$$

<figure><img src="image_29.png" /></figure>

**NB** : on montre que l'erreur est de la forme :

$$|f(x) - g(x)| \le \frac{(b-a)^2}{2} M''$$

Où $M''$ est un majorant de $|f''(x)|$, avec $M'' = \sup|f''(x)|$. $f''(x)$ est calculée en utilisant les méthodes décrites dans le chapitre suivant.

## II- Interpolation quadratique

Entres trois points distincts $M_0(a_0, f(a_0))$, $M_1(a_1, f(a_1))$, $M_2(a_2, f(a_2))$ d'une fonction $f(x)$, il passe un polynôme unique $g(x)$ coïncidant avec $f(x)$ (voir figure ci-dessous). $g(x)$ est de degré 2 et est de la forme :

$$g(x) = c_0 + c_1x + c_2x^2$$

$$\text{Avec : } g(a_0) = f(a_0), g(a_1) = f(a_1) \text{ et } g(a_2) = f(a_2)$$

ActiveI
Accédez
<figure><img src="image_30.png" /></figure>

On obtient donc le système de 3 équations à 3 inconnues ci-dessous qu'on peut résoudre par les méthodes déjà connues.

$$ egin{cases} c_0 + c_1 a_0 + c_2 a_0^2 = f(a_0) \ c_0 + c_1 a_1 + c_2 a_1^2 = f(a_1) \ c_0 + c_1 a_2 + c_2 a_2^2 = f(a_2) \end{cases} $$

**Exemple** : interpolons la fonction $f(x) = \sin x$ entre les points $0, \pi, \frac{\pi}{2}$.

$$ g(0) = f(0) = 0 $$

$$ g(\pi) = f(\pi) = 0 $$

$$ g\left(\frac{\pi}{2}\right) = f\left(\frac{\pi}{2}\right) = 1 $$

On obtient :

$$ \begin{cases} c_0 = f(0) = 0 \\ c_0 + c_1 \frac{\pi}{2} + c_2 \frac{\pi^2}{4} = 1 \\ c_0 + c_1 \pi + c_2 \pi^2 = 0 \end{cases} \rightarrow \begin{cases} c_0 = 0 \\ c_1 = \frac{4}{\pi} \\ c_2 = -\frac{4}{\pi^2} \end{cases} $$

Soit donc :

$$ g(x) = \frac{4}{\pi^2} x(\pi - x) $$

∧ ∨
### III- Interpolation de Lagrange

L'interpolation de Lagrange est une façon simple et systématique de construire un polynôme de collocation. Etant donné $n + 1$ points $M_i(x_i, f(x_i))$ (pour $i = 0, 1, 2, \dots, n$), on suppose un instant que l'on sait construire $n + 1$ polynômes $L_i(x)$ de degré $n$ et satisfaisant les conditions suivantes :

$$ \begin{cases} L_i(x_i) = 1 & \forall i \\ L_i(x_k) = 0 & \forall k \neq i \end{cases} $$

Cela signifie que le polynôme $L_i(x)$ de degré $n$ prend la valeur 1 en $x_i$ et s'annule en tous les autres points de collocation. Dans ce cas, on a :

$$ g(x) = \sum_{i=0}^{n} f(x_i) L_i(x) $$

#### 1- Recherche des $L_i(x)$

##### a) Cas d'un polynôme de degré 1

Il s'agit de déterminer le polynôme de degré 1 dont la courbe (qui est une droite !!!) passe par les deux points $M_0(x_0, f(x_0))$, $M_1(x_1, f(x_1))$. On doit donc construire 2 polynômes $L_0(x)$ et $L_1(x)$ de degré 1 qui vérifient :

$$ \begin{aligned} L_0(x_0) &= 1; & L_1(x_0) &= 0 \\ L_0(x_1) &= 0; & L_1(x_1) &= 1 \end{aligned} $$

Le polynôme $L_0(x)$ doit s'annuler en $x = x_1$. On pense immédiatement au polynôme $(x - x_1)$ qui s'annule en $x = x_1$ mais qui vaut $(x_0 - x_1)$ en $x = x_0$. Pour s'assurer d'une valeur 1 en $x = x_0$, il suffit de faire la division appropriée afin d'obtenir :

$$ L_0(x) = \frac{x - x_1}{x_0 - x_1} $$

Un raisonnement similaire pour $L_1(x)$ donne :

$$ L_1(x) = \frac{x - x_0}{x_1 - x_0} $$

Ainsi, le polynôme de Lagrange de degré 1 est donc :

$$ \begin{aligned} g(x) &= f(x_0)L_0(x) + f(x_1)L_1(x) \\ g(x) &= \frac{x - x_1}{x_0 - x_1}f(x_0) + \frac{x - x_0}{x_1 - x_0}f(x_1) \end{aligned} $$

Activer Win

##### b) Cas d'un polynôme de degré 2

Si on cherche le polynôme de degré 2 passant par trois points $M_0(x_0, f(x_0))$, $M_1(x_1, f(x_1))$, $M_2(x_2, f(x_2))$, on doit construire trois fonctions $L_i(x)$.
La fonction $L_0(x)$ s'annule cette fois en $x = x_1$ et $x = x_2$. On pense alors au polynôme $(x - x_1)(x - x_2)$ qui vaut $(x_0 - x_1)(x_0 - x_2)$ en $x = x_0$. Pour satisfaire à la condition $L_0(x_0) = 1$, il suffit de diviser le coefficient par cette valeur et de poser :

$$L_0(x) = \frac{(x - x_1)(x - x_2)}{(x_0 - x_1)(x_0 - x_2)}$$

De la même manière, on a :

$$L_1(x) = \frac{(x - x_0)(x - x_2)}{(x_1 - x_0)(x_1 - x_2)}$$

$$L_2(x) = \frac{(x - x_0)(x - x_1)}{(x_2 - x_0)(x_2 - x_1)}$$

Ainsi, le polynôme de Lagrange de degré 1 est donc :

$$g(x) = f(x_0)L_0(x) + f(x_1)L_1(x) + f(x_2)L_2(x)$$

### c) Cas d'un polynôme de degré n

Activ

On analyse le cas général de la même façon. L'expression générale pour la fonction $L_i(x)$ est donc :

$$L_i(x) = \frac{(x - x_0) \cdots (x - x_{i-1})(x - x_{i+1}) \cdots (x - x_n)}{(x_i - x_0) \cdots (x_i - x_{i-1})(x_i - x_{i+1}) \cdots (x_i - x_n)}$$

On peut aussi l'écrire :

$$L_i(x) = \prod_{\substack{k=0 \\ k \neq i}}^{n} \left( \frac{x - x_k}{x_i - x_k} \right)$$

## 2- Polynôme de Lagrange

Le polynôme de Lagrange sera donc de la forme :

$$g(x) = \sum_{i=0}^{n} f(x_i) L_i(x)$$

Ou encore :

$$g(x) = \sum_{i=0}^{n} \left\{ f(x_i) \prod_{\substack{k=0 \\ k \neq i}}^{n} \left( \frac{x - x_k}{x_i - x_k} \right) \right\}$$
### 3- Erreur de calcul

On cherche un majorant $|f(x) - g(x)|$ pour $x \in [a, b]$. De manière générale, on montre que :

$$|f(x) - g(x)| \le \frac{(b - a)^{n+1}}{(n + 1)!} M^{(n+1)}$$

Où $M^{(n+1)}$ est un majorant de $f^{(n+1)}$ sur $[a, b]$.

L'erreur peut encore s'écrire :

$$\varepsilon(x) = \left| \frac{f^{(n+1)}(c)}{(n+1)!} \prod_{i=0}^{n} (x - x_i) \right|$$

$$\text{Où } f^{(n+1)}(c) = \sup |f^{(n+1)}(x_i)|$$

### 4- Exemple

Calculons par interpolation de Lagrange, la fonction $f(x) = \sin x$ entre les points $0, \pi, \frac{\pi}{2}$.

Les polynômes $L_i(x)$ sont telles que :

$$L_0(x) = \frac{(x - \pi)(x - \frac{\pi}{2})}{(0 - \pi)(0 - \frac{\pi}{2})}$$

$$L_1(x) = \frac{(x - 0)(x - \frac{\pi}{2})}{(\pi - 0)(\pi - \frac{\pi}{2})}$$

$$L_2(x) = \frac{(x - 0)(x - \pi)}{\left(\frac{\pi}{2} - 0\right)\left(\frac{\pi}{2} - \pi\right)}$$

Soit donc :

$$g(x) = f(0)L_0(x) + f(\pi)L_1(x) + f\left(\frac{\pi}{2}\right)L_2(x)$$

$$g(x) = 0 \times L_0(x) + 0 \times L_1(x) + 1 \times L_2(x)$$

$$g(x) = -\frac{4}{\pi^2}(x^2 - \pi x) \Rightarrow g(x) = \frac{4}{\pi^2}x(\pi - x)$$

### Représentation graphique

$$\text{Interpolation linéaire : } g(x) = \begin{cases} \frac{2}{\pi}x & \text{pour } x \in [0, \frac{\pi}{2}] \\ -\frac{2}{\pi}x + 2 & \text{pour } x \in [\frac{\pi}{2}, \pi] \end{cases}$$

$$\text{Interpolation quadratique et de Lagrange : } g(x) = \frac{4}{\pi^2}x(\pi - x)$$
<table><thead><tr><th>valeur</th><th>x</th><th>sinx</th><th>lineaire</th><th>quadratique</th></tr></thead><tbody><tr><td>pi/8</td><td>0.39269908</td><td>0.38268343</td><td>0.25</td><td>0.4375</td></tr><tr><td>pi/4</td><td>0.78539816</td><td>0.70710678</td><td>0.5</td><td>0.75</td></tr><tr><td>3pi/8</td><td>1.17809725</td><td>0.92387953</td><td>0.75</td><td>0.9375</td></tr><tr><td>pi/2</td><td>1.57079633</td><td>1</td><td>1</td><td>1</td></tr><tr><td>5pi/8</td><td>1.96349541</td><td>0.92387953</td><td>0.75</td><td>0.9375</td></tr><tr><td>6pi/8</td><td>2.35619449</td><td>0.70710678</td><td>0.5</td><td>0.75</td></tr><tr><td>7pi/8</td><td>2.74889357</td><td>0.38268343</td><td>0.25</td><td>0.4375</td></tr><tr><td>pi</td><td>3.14159265</td><td>1.2251E-16</td><td>0</td><td>0</td></tr></tbody></table>

<figure><img src="image_31.png" /></figure>

# Exercices sur l'Interpolation et approximation

## Exercice 1 :

La température initiale d'un objet est de 0°C, puis de 5°C après une minute et 3°C après deux minutes. On utilisera les températures absolues (en Kelvin). On note que $T_{(K)} = t_{(°C)} + 273$.

1- Quelle est sa température à 30 secondes si on procède à une approximation linéaire du temps?

2- Déterminer par interpolation quadratique, la température à 30 secondes.

3- une quatrième mesure donne une température de 0°C après 3 minutes. Déterminer le polynôme d'interpolation de Lagrange sur les quatre mesures. Calculer la température à 30 secondes.

NB : dans tout l'exercice, on exprimera le temps en minutes.

### Indications :

$$1 \ T = 5t + 273 \ ; \text{ pour } t = 30s = 0,5\min \Rightarrow T = 275,5K$$

$$2 \ T = -3,5t^2 + 8,5t + 273 \ ; \text{ pour } t = 30s = 0,5\min \Rightarrow T = 276,375K$$

$$3 \ T = \frac{(t-1)(t-2)(t-3)}{(0-1)(0-2)(0-3)} \times 273 + \frac{(t-0)(t-2)(t-3)}{(1-0)(1-2)(1-3)} \times 278 + \frac{(t-0)(t-1)(t-3)}{(2-0)(2-1)(2-3)} \times 276 + \frac{(t-0)(t-1)(t-2)}{(3-0)(3-1)(3-2)} \times 27$$

$$\text{pour } t = 30s = 0,5\min \Rightarrow T = 276,75K$$

## Exercice 2 :

On veut calculer $\ln(529,62)$. Dans une table de logarithme népérien, on trouve :

<table><tr><td>x</td><td>529</td><td>530</td></tr><tr><td>ln(x)</td><td>6,270988</td><td>6,272877</td></tr></table>

1- déterminer une valeur approximative de $\ln(529,62)$ par la méthode de Lagrange.

2- Déterminer l'erreur $\varepsilon(529,62)$.

3- Comparer la valeur approchée de $\ln(529,62)$ avec celle calculée par une machine.

Ac

### Indications :

$$\ln(x) = \frac{(x - 530)}{(529 - 530)} \times 6,270988 + \frac{(x - 529)}{(530 - 529)} \times 6,272877 \Rightarrow \ln(529,62) = 6,2721592$$

$$\varepsilon(529,62) = \left| (529,62 - 529)(529,62 - 530) \frac{f''(c)}{2!} \right| = 4.10^{-7}$$

$$\text{avec } f''(c) = \sup|f''(x)| = \sup\left|\frac{1}{x^2}\right| = \frac{1}{529^2}$$

La valeur calculée par la machine est : $\ln(529,62) = 6,2721598$
# Exercice 3

Le tableau de valeurs expérimentales a été obtenu en mesurant la vitesse en km/h d'un véhicule toutes les 5 secondes.

<table><thead><tr><td>t (s)</td><td>V (km/h)</td></tr></thead><tbody><tr><td>0</td><td>55</td></tr><tr><td>5</td><td>60</td></tr><tr><td>10</td><td>58</td></tr><tr><td>15</td><td>54</td></tr></tbody></table>

## 1/ interpolation linéaire et quadratique

a) représenter graphiquement la vitesse en fonction du temps.

b) quelle est la vitesse du véhicule à $t = 2,5 \text{ s}$ si l'on procède à une approximation linéaire du temps entre 0 et 5 secondes ?

c) trouver par interpolation quadratique à partir des temps $t = 0; 5; 10 \text{ s}$, la vitesse du véhicule lorsque $t = 2,5 \text{ s}$.

## 2/interpolation de Lagrange

Le polynôme d'interpolation de Lagrange est le polynôme de degré $n$ passant par les $n + 1$ points $(x_0, y_0), (x_1, y_1), \dots, (x_k, y_k), \dots, (x_n, y_n)$. La formule générale est :

$$P_n(x) = \sum_{k=0}^{n} \frac{L_k(x)}{L_k(x_k)} y_k$$

Avec $L_k(x) = (x - x_0)(x - x_1) \dots (x - x_{k-1})(x - x_{k+1}) \dots (x - x_n)$

a) montrer que $P_n(x_j) = y_j$

b) donner l'ordinogramme de la méthode de Lagrange

c) déterminer le polynôme de Lagrange à partir de tous les points du tableau. En déduire la vitesse à $t = 2,5 \text{ s}$.

d) placer la vitesse à $t = 2,5 \text{ s}$ sur la courbe $v = f(t)$ pour les 3 méthodes

e) conclure sur les 3 méthodes.

**Indications :**

1/ interpolation linéaire et quadratique

$v = 0,28t + 15,3$ ; d'où pour $t = 2,5 \text{ s}$ alors $v = 16 \text{ m/s}$ ou $57,6 \text{ km/h}$.

$v = -0,04t^2 + 0,48t + 15,3$ ; d'où pour $t = 2,5 \text{ s}$ alors $v = 16,25 \text{ m/s}$ ou $58,5 \text{ km/h}$.

2/ interpolation de Lagrange

$$P_n(x_j) = 0 \times y_1 + 0 \times y_2 + \dots + \frac{L_k(x_j)}{L_k(x_k)} \times y_j + \dots + y_j = y_j$$

pour $t = 2,5 \text{ s}$ alors $v = 16,34 \text{ m/s}$ ou $58,82 \text{ km/h}$
# Chapitre 4 : Méthode des moindres carrés

## Problème :

Soit un tableau donnant les mesures de la caractéristique intensité-tension d'un dipôle linéaire. Trouver par la méthode des moindres carrés, la valeur de la résistance. On montrera par le calcul que la caractéristique est de la forme $U = aI + b$ où $b$ est une valeur que l'on négligera.

<table><tr><td>I (A)</td><td>0</td><td>0.005</td><td>0.01</td><td>0.012</td><td>0.017</td><td>0.02</td><td>0.024</td><td>0.028</td><td>0.03</td></tr><tr><td>U (V)</td><td>0</td><td>0.5</td><td>1</td><td>1.3</td><td>1.6</td><td>2</td><td>2.3</td><td>2.8</td><td>3</td></tr></table>

## 1- Principe de la méthode

Le problème intervient au cours de l'interprétation des résultats expérimentaux. Considérons le problème posé. On pourrait songer à représenter $U(I) = f(x)$ par une ligne passant par tous les points expérimentaux. De toute évidence, cela n'a pas de sens du point de vue physique, et on devra au contraire représenter $f(x)$ par une courbe passant par tous les points expérimentaux, ou alors ne passant par aucun d'eux.

Une première méthode consiste à tracer à « l'œil » la fonction $g(x)$ censée représenter le mieux possible la fonction $f(x)$ décrite par les points expérimentaux.

Evidemment, il est préférable d'avoir une méthode plus sûre. Pour cela :

* On choisit une forme de fonction $g(x)$ censée représenter $f(x)$. $g(x)$ est choisis, soit parce qu'elle correspond à la forme qu'on attend pour les résultats, soit d'après la configuration des résultats. Ainsi, $g(x)$ peut-être :

- Une linéaire $g(x) = ax + b$

- Une exponentielle $g(x) = ae^{bx}$

- Une polynômiale $g(x) = a_n x^n + a_{n-1} x^{n-1} + \dots$

* On détermine les différents paramètres de la loi $g(x)$ de telle sorte que $g(x)$ passe le plus près possible des points expérimentaux ; c'est-à-dire si la quantité $S$ est minimum avec :

$$S = \sum_{i=1}^{n} [y_i - g(x_i)]^2$$
En d'autres termes, si :

$$ \frac{\partial S}{\partial a_0} = 0; \frac{\partial S}{\partial a_1} = 0; \frac{\partial S}{\partial a_2} = 0; \dots; \frac{\partial S}{\partial a_n} = 0 $$

On obtient un système de $n + 1$ équations à $n + 1$ inconnues.

## 2- Loi linéaire ou droite des moindres carrés

C'est le cas où on choisit pour $g(x)$ un polynôme de degré 1 représenté par une droite (voir figure ci-dessous) de la forme :

$$ g(x) = ax + b = a_0x + a_1 $$

<figure><img src="image_32.png" /></figure>

Activ

La quantité S étant minimale, on :

$$ \begin{align} \frac{\partial S}{\partial a_0} = 0 \quad &\rightarrow \quad \frac{\partial}{\partial a_0} \left\{ \sum_{i=1}^{n} [y_i - ax_i - b]^2 \right\} = 0 \nonumber \\ &\rightarrow \quad \sum_{i=1}^{n} \{-2x_i[y_i - ax_i - b]\} = 0 \nonumber \\ &\rightarrow \quad -2 \sum_{i=1}^{n} x_i y_i - 2a \sum_{i=1}^{n} x_i^2 + 2b \sum_{i=1}^{n} x_i = 0 \tag{1} \end{align} $$

De la même manière :

$$ \frac{\partial S}{\partial b} = 0 \quad \rightarrow \quad \frac{\partial}{\partial b} \left\{ \sum_{i=1}^{n} [y_i - ax_i - b]^2 \right\} = 0 $$
$$
\begin{gather*}
\sum_{i=1}^{n} \{-2[y_i - ax_i - b]\} = 0 \\
-2 \sum_{i=1}^{n} y_i + 2a \sum_{i=1}^{n} x_i + 2nb = 0
\end{gather*}
$$

On a donc un système de 2 équations à 2 inconnues.

$$
\left\{
\begin{array}{l}
a \sum_{i=1}^{n} x_i^2 + b \sum_{i=1}^{n} x_i = \sum_{i=1}^{n} x_i y_i \\
\\
a \sum_{i=1}^{n} x_i + nb = \sum_{i=1}^{n} y_i
\end{array}
\right.
$$

Après résolution, les coefficients $a$ et $b$ de $g(x) = ax + b$ sont tels :

$$
a = \frac{n(\sum_{i=1}^{n} x_i y_i) - (\sum_{i=1}^{n} x_i)(\sum_{i=1}^{n} y_i)}{n(\sum_{i=1}^{n} x_i^2) - (\sum_{i=1}^{n} x_i)^2}
$$

$$
b = \frac{(\sum_{i=1}^{n} x_i)(\sum_{i=1}^{n} x_i y_i) - (\sum_{i=1}^{n} x_i^2)(\sum_{i=1}^{n} x_i)}{(\sum_{i=1}^{n} x_i)^2 - n(\sum_{i=1}^{n} x_i^2)}
$$

3- Loi exponentielle

Si $g(x) = ae^{bx}$ on peut se ramener au cas linéaire en posant :

$$
\ln(g(x)) = lna + bx
$$

Au lieu de prendre comme points expérimentaux $(x_i, y_i)$ on prendra plutôt $(x_i, \ln(y_i))$

La résolution se ramène à celle de la droite des moindres carrés en posant :

$$
A = \ln(a), B = b, \text{ et } h(x) = \ln(g(x))
$$

D'où $h(x) = A + Bx$

Exercices sur la Méthode des moindres carrés

**Exercice 1 : étude de la balance de Cotton**

Au cours d'une expérience sur la balance de Cotton, une étudiante est amenée à faire varier le courant $I_e$ dans l'électro-aimant, le courant dans la balance étant fixée à $I_b = 4,75 \text{ A}$. Pour chaque valeur de $I_e$, elle équilibre la balance en plaçant des masses sur le plateau. Les résultats de cette expérience sont consignés dans le tableau ci-dessous:
<table><thead><tr><td>$I_e$</td><td>$M(g)$</td><td>$B(T)$</td></tr></thead><tbody><tr><td>0,6</td><td>5</td><td>0,49</td></tr><tr><td>0,8</td><td>7</td><td>0,69</td></tr><tr><td>1</td><td>8</td><td>0,79</td></tr><tr><td>1,2</td><td>10</td><td>0,98</td></tr><tr><td>1,4</td><td>12</td><td>1,18</td></tr><tr><td>1,6</td><td>14</td><td>1,38</td></tr></tbody></table>

a) Marquer sur un graphique les points expérimentaux $B = f(I_e)$.

b) Déterminer par la méthode des moindres carrés, la loi linéaire $B = f(I_e)$, et représenter cette courbe sur le graphique précédent.

c) On démontre que $B = \frac{Mgd_2}{l_bLd_1}$ et on pose que $d_1 = d_2 = 15cm; L = 2,1cm; g = 9,8 \text{ ms}^{-2}$.

Sachant que $I_{e1} = 0,5A$ et $I_{e2} = 2A$, déterminer les masses $(M_i)_{i=1,2}$ nécessaires à l'équilibre de la balance.

**Indications :**

b) la loi linéaire $B = f(I_e) = 0,87 I_e - 0,04$

c) $B = 98,25 M$. pour $I_e = 0,5A$ alors $B = 0,4T$ et $M = 4,1 g$

pour $I_e = 2A$ alors $B = 1,7T$ et $M = 17 g$

**Exercice 2 : méthode des moindres carrés**

Les données suivantes concernent la population des Etats-Unis en millions d'habitants.

<table><thead><tr><td>Année</td><td>1920</td><td>1930</td><td>1940</td><td>1950</td><td>1960</td><td>1970</td></tr></thead><tbody><tr><td>Population (M̄)</td><td>105,711</td><td>123,203</td><td>131,669</td><td>150,697</td><td>179,323</td><td>203,212</td></tr></tbody></table>

Trouver l'équation de la droite des moindres carrés correspondant à ces valeurs et estimer la population aux années 1910, 1965 et 2000.

NB : on exprimera les résultats à $10^{-3}$ près. On suppose que l'unité qui exprime le nombre d'habitants est $M̄$ avec $1 M̄ = 10^6 = 1 \text{ million}$.

On montre que pour une droite des moindres carrés de la forme $y = ax + b$, les coefficients $a$ et $b$ sont :

$$a = \frac{n(\sum_{i=1}^{n} x_i y_i) - (\sum_{i=1}^{n} x_i)(\sum_{i=1}^{n} y_i)}{n(\sum_{i=1}^{n} x_i^2) - (\sum_{i=1}^{n} x_i)^2}$$ $$b = \frac{(\sum_{i=1}^{n} x_i)(\sum_{i=1}^{n} y_i) - (\sum_{i=1}^{n} x_i)(\sum_{i=1}^{n} y_i)}{(\sum_{i=1}^{n} x_i)^2 - n(\sum_{i=1}^{n} x_i)^2}$$

**Indications :**

La droite des moindres carrés est population($M̄$) = 1.928 année - 3601.508

Pour l'année 1910 population($M̄$) = 1.928 × 1910 - 3601.508 = 80.972

Pour l'année 1965 population($M̄$) = 1.928 × 1965 - 3601.508 = 187.012

Pour l'année 2000 population($M̄$) = 1.928 × 2000 - 3601.508 = 254.492

Active
# Chapitre 5 : Dérivation numérique

## Problème

Lors de la décharge d'un condensateur de capacité $C = 10^{-5} F$ dans un dipôle non linéaire, on a relevé les tensions suivantes aux bornes du condensateur (voir tableau) :

<table><tr><td>t (ms)</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td></tr><tr><td>U (V)</td><td>4.0</td><td>3.5</td><td>3.0</td><td>2.0</td><td>1.1</td><td>0.7</td><td>0.5</td><td>0.4</td><td>0.3</td></tr></table>

On note que l'intensité qui a parcouru le circuit est de la forme $i = -C \frac{dU}{dt}$

Déterminer l'intensité du courant pour chaque valeur du temps $t_i$. En déduire la valeur maximale de l'intensité du courant qui a circulé dans le circuit.

## Introduction

Le calcul numérique de la dérivée point par point intervient :

- Pour une fonction dont la dérivée a une fonction analytique complexe.

- Pour une fonction que l'on connaît seulement en certains points (voir problème ci-dessus)

A partir des valeurs de $f(x)$ en différents points, on calculera donc une approximation de la dérivée première et des autres dérivées successives.

Par exemple, si l'on connaît la position d'une particule à intervalles de temps réguliers, on peut obtenir sa vitesse et son accélération par le calcul des dérivées.

# I- Cas d'une fonction définie en des points régulièrement espacés

## 1- Méthode des différences centrées

On suppose qu'on connaît $f(x)$ en des points régulièrement espacés, c'est-à-dire que $x_{i+1} = x_i + h$, avec $h$ le pas ou l'intervalle entre deux valeurs consécutives.

Pour calculer les dérivées successives $f^{(n)}(x)$, on utilise les points situés de part et d'autre de $x_i$.

Activité
<figure><img src="image_33.png" /></figure>

a) Dérivée première $f'(x)$

On sait que : $f(x_{i+1}) = f(x_i + h)$

$$
\text{Car } x_{i+1} = x_i + h \text{ et } x_{i-1} = x_i - h
$$

En utilisant un développement limité de Taylor autour de $h = 0$, on a :

$$
f(x_{i+1}) = f(x_i + h) = f(x_i) + hf'(x_i) + \frac{h^2}{2!}f''(x_i) + \frac{h^3}{3!}f'''(x_i) + \dots \quad (1)
$$

$$
f(x_{i-1}) = f(x_i - h) = f(x_i) - hf'(x_i) + \frac{h^2}{2!}f''(x_i) - \frac{h^3}{3!}f'''(x_i) + \dots \quad (2)
$$

Faisons la soustraction des deux termes. On obtient :

$$
f'(x_i) = \frac{f(x_i + h) - f(x_i - h)}{2h} - \frac{h^2}{3!} f'''(x_i)
$$

En posant $\theta(h^2) = \frac{h^2}{3!}f'''(x_i)$ et en négligeant les termes d'ordre supérieur ou égal à $h^2$, une approximation de la dérivée première est :

$$
f'(x_i) = \frac{f(x_i + h) - f(x_i - h)}{2h} = \frac{f(x_{i+1}) - f(x_{i-1})}{2h}
$$

On note que la tangente en $M_i$ (voir figure ci-dessus) est remplacée par la droite $M_{i-1}M_{i+1}$.
Plus $h$ est petit, c'est-à-dire $x_{i-1}$ plus proche de $x_{i+1}$, plus le résultat est proche de la valeur exacte de $f'(x)$.

b) Dérivée seconde $f''(x)$

Faisons une addition des équations (1) et (2). On obtient :

$$
f(x_i + h) + f(x_i - h) = 2f(x_i) + h^2 f''(x_i) + \theta(h^4)
$$
En négligeant les termes d'ordre supérieur ou égal à $h^4$, une approximation de la dérivée seconde est :

$$f''(x_i) = \frac{f(x_i + h) + f(x_i - h) - 2f(x_i)}{h^2} = \frac{f(x_{i+1}) + f(x_{i-1}) - 2f(x_i)}{h^2}$$

### c) Tableau récapitulatif

Si l'on se réfère aux résultats précédents, on peut constituer une table nous donnant l'expression des dérivées successives.

<table><thead><tr><th></th><th>f(x<sub>i-2</sub>)</th><th>f(x<sub>i-1</sub>)</th><th>f(x<sub>i</sub>)</th><th>f(x<sub>i+1</sub>)</th><th>f(x<sub>i+2</sub>)</th></tr></thead><tbody><tr><th>2hf'(x<sub>i</sub>)</th><td></td><td>-1</td><td>0</td><td>1</td><td></td></tr><tr><th>h<sup>2</sup>f''(x<sub>i</sub>)</th><td></td><td>1</td><td>-2</td><td>1</td><td></td></tr><tr><th>2h<sup>3</sup>f'''(x<sub>i</sub>)</th><td>-1</td><td>2</td><td>0</td><td>-2</td><td>1</td></tr><tr><th>h<sup>4</sup>f''''(x<sub>i</sub>)</th><td>1</td><td>-4</td><td>6</td><td>-4</td><td>1</td></tr></tbody></table>

## 2- Méthode des différences à droite (ou avant)

Pour calculer les dérivées successives $f^{(n)}(x)$, cette méthode utilise les points situés de à droite de $x_i$, c'est-à-dire $x_{i+1}, x_{i+2}, x_{i+3}, \dots$.

### a) Dérivée première à droite $f'_d(x)$

En utilisant un développement limité de Taylor autour de $h = 0$, on a :

$$f(x_{i+1}) = f(x_i + h) = f(x_i) + hf'(x_i) + \frac{h^2}{2!}f''(x_i) + \frac{h^3}{3!}f'''(x_i) + \dots \quad (3)$$

En posant $\theta(h^2) = \frac{h^2}{2}f''(x_i)$ et en négligeant les termes d'ordre supérieur ou égal à $h^2$, une approximation de la dérivée première à droite est :

$$f'_{d}(x_i) = \frac{f(x_i + h) - f(x_i)}{h} = \frac{f(x_{i+1}) - f(x_i)}{h}$$

Cette approximation est moins bonne qu'avec les différences centrées.

### b) Dérivée seconde à droite $f''_d(x)$

En utilisant un développement limité de Taylor autour de $h = 0$, on a :

$$f(x_{i+2}) = f(x_i + 2h) = f(x_i) + 2hf'(x_i) + \frac{4h^2}{2!}f''(x_i) + \frac{8h^3}{3!}f'''(x_i) + \dots \quad (4)$$

Faisons la soustraction des équations (3) et (4). On obtient :
$$f(x_{i+2}) - 2f(x_{i+1}) = -f(x_i) + h^2 f''(x_i) + \theta(h^3)$$

En posant $\theta(h^3) = h^3 f'''(x_i)$ et en négligeant les termes d'ordre supérieur ou égal à $h^2$, une approximation de la dérivée seconde à droite est :

$$f''_{d}(x_i) = \frac{f(x_i + 2h) - 2f(x_i + h) + f(x_i)}{h^2} = \frac{f(x_{i+2}) - 2f(x_{i+1}) + f(x_i)}{h^2}$$

### c) Tableau récapitulatif

Si l'on se réfère aux résultats précédents, on peut constituer une table nous donnant l'expression des dérivées successives.

Termes des dérivées

<table><thead><tr><th>Dérivées</th><th>f(x<sub>i</sub>)</th><th>f(x<sub>i+1</sub>)</th><th>f(x<sub>i+2</sub>)</th><th>f(x<sub>i+3</sub>)</th><th>f(x<sub>i+4</sub>)</th></tr></thead><tbody><tr><td>hf'(x<sub>i</sub>)</td><td>-1 <sup>(1)</sup></td><td>1 <sup>(2)</sup></td><td></td><td></td><td></td></tr><tr><td>h<sup>2</sup>f''(x<sub>i</sub>)</td><td>1</td><td>-2 <sup>(3)</sup></td><td>1</td><td></td><td></td></tr><tr><td>h<sup>3</sup>f'''(x<sub>i</sub>)</td><td>-1</td><td>3</td><td>-3</td><td>1</td><td></td></tr><tr><td>h<sup>4</sup>f''''(x<sub>i</sub>)</td><td>1</td><td>-4</td><td>6</td><td>-4</td><td>1</td></tr></tbody></table>

**Remarque : calcul des coefficients des termes de chaque dérivée.**

Connaissant la dérivée première, on en déduit les autres dérivées par un simple calcul. Par exemple, pour le calcul de chacun des différents termes de la dérivée seconde, on soustrait le coefficient de la case 1 (voir tableau) et celui de la case 2 (voir tableau) pour obtenir le coefficient multiplicatif du deuxième terme de la dérivée seconde à la case 3 (voir tableau). Les cases qui n'ont pas de coefficient sont prises égales à 0. Pour le calcul des premiers termes, on suppose que la case contenant l'expression littérale des dérivées est aussi prise égale à 0.

## 3- Méthode des différences à gauche (ou arrière)

Pour calculer les dérivées successives $f^{(n)}(x)$, cette méthode utilise les points situés de à gauche de $x_i$, c'est-à-dire $x_{i-1}, x_{i-2}, x_{i-3}, \dots$.

On obtient comme dans le cas de la méthode des différences à droite, le même résultat en remplaçant $x_{i+1}$ par $x_{i-1}$.
a) Dérivée première à gauche $f'_g(x)$

$$f'_{g}(x_i) = \frac{f(x_i) - f(x_i - h)}{h} = \frac{f(x_i) - f(x_{i-1})}{h}$$

b) Dérivée seconde à gauche $f''_g(x)$

$$f''_{g}(x_i) = \frac{f(x_i) - 2f(x_i - h) + f(x_{i-2})}{h^2} = \frac{f(x_i) - 2f(x_{i-1}) + f(x_{i-2})}{h^2}$$

c) Tableau récapitulatif

Si l'on se réfère aux résultats précédents, on peut constituer une table nous donnant l'expression des dérivées successives.

<table><thead><tr><th rowspan="2">Dérivées</th><th colspan="5">Termes des dérivées</th></tr><tr><th>f(x<sub>i</sub>)</th><th>f(x<sub>i-1</sub>)</th><th>f(x<sub>i-2</sub>)</th><th>f(x<sub>i-3</sub>)</th><th>f(x<sub>i-4</sub>)</th></tr></thead><tbody><tr><td>hf'(x<sub>i</sub>)</td><td>1 <sup>(1)</sup></td><td>-1 <sup>(2)</sup></td><td></td><td></td><td></td></tr><tr><td>h<sup>2</sup>f''(x<sub>i</sub>)</td><td>1</td><td>-2 <sup>(3)</sup></td><td>1</td><td></td><td></td></tr><tr><td>h<sup>3</sup>f'''(x<sub>i</sub>)</td><td>1</td><td>-3</td><td>3</td><td>-1</td><td></td></tr><tr><td>h<sup>4</sup>f''''(x<sub>i</sub>)</td><td>1</td><td>-4</td><td>6</td><td>-4</td><td>1</td></tr></tbody></table>

**Remarque : calcul des coefficients des termes de chaque dérivée.**

Connaissant la dérivée première, on en déduit les autres dérivées par un simple calcul. Par exemple, pour le calcul de chacun des différents termes de la dérivée seconde, on prend l'opposé du coefficient de la case 1 (voir tableau) et on l'additionne avec le coefficient de la case 2 (voir tableau) pour obtenir le coefficient multiplicatif du deuxième terme de la dérivée seconde à la case 3 (voir tableau). Les cases qui n'ont pas de coefficient sont prises égales à 0. Pour le calcul des premiers termes, on suppose que la case contenant l'expression littérale des dérivées est aussi prise égale à 0.

## II- Cas d'une fonction définie en des points non régulièrement espacés

Il peut arriver que l'on cherche la dérivée en un point x pour une fonction f(x) définie en des points non régulièrement espacés. Dans ce cas, on approche f(x) par un polynôme de degré n (confère chapitre sur l'interpolation). Une approximation de la dérivée est donnée par la dérivée du polynôme trouvé. Dans le cas général, on se contente d'une interpolation linéaire ou quadratique.
## 1- Approximation linéaire

Si on peut calculer la dérivée de $f(x)$ en un point $x \in [x_i; x_{i+1}]$, on peut approcher $f(x)$ par la droite :

$$P(x) = f(x_i) + \frac{f(x_{i+1}) - f(x_i)}{x_{i+1} - x_i} (x - x_i)$$

D'où :

$$P'(x) = \frac{f(x_{i+1}) - f(x_i)}{x_{i+1} - x_i}$$

Les résultats sont bons au centre de l'intervalle $[x_i; x_{i+1}]$ mais non aux extrémités.

## 2- Approximation quadratique

Si $x \in [x_{i-1}; x_{i+1}]$, $x_i$ étant le point le plus proche de $x$, on a :

$$P(x) = ax^2 + bx + c$$

Avec :

$$P'(x) = 2ax + b$$

Il suffit de trouver les coefficients $a, b, c$ en résolvant le système :

$$\begin{cases} f(x_{i-1}) = ax_{i-1}^2 + bx_{i-1} + c \\ f(x_i) = ax_i^2 + bx_i + c \\ f(x_{i+1}) = ax_{i+1}^2 + bx_{i+1} + c \end{cases}$$

Soit donc :

$$P'(x) = \frac{(2x - x_i - x_{i-1}) T_i - (2x - x_{i+1} - x_i) T_{i-1}}{x_{i+1} - x_i}$$

Avec :

$$T_i = \frac{f(x_{i+1}) - f(x_i)}{x_{i+1} - x_i} ; \quad T_{i-1} = \frac{f(x_i) - f(x_{i-1})}{x_i - x_{i-1}}$$

### Résolution du problème

On sait que

$i = -\frac{dq}{dt}$ lors de la décharge d'un condensateur et,

$i = \frac{dq}{dt}$ lors de la charge d'un condensateur.

Puisque $q = CU$ on en déduit que $\frac{dq}{dt} = C \frac{dU}{dt} = C \frac{dU}{dt}$ avec $C$ qui est une constante
$$L'\text{'intensité qui a parcouru le circuit sera de la forme } i = -C\frac{au}{dt}$$

$$La dérivée en 0 est une dérivée à droite de la forme i = -C\frac{U(t_1)-U(t_0)}{t_1-t_0}$$

$$La dérivée en 8 est une dérivée à gauche de la forme i = -C\frac{U(t_8)-U(t_7)}{t_8-t_7}$$

$$Les autres dérivées sont des dérivées centrales de la forme i = -C\frac{U(t_{i+1})-U(t_{i-1})}{2h}$$

On en déduit le tableau suivant :

<table><tr><td>t(ms)</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td></tr><tr><td>U(V)</td><td>4.0</td><td>3.5</td><td>3.0</td><td>2.0</td><td>1.1</td><td>0.7</td><td>0.5</td><td>0.4</td><td>0.3</td></tr><tr><td>I(× 10<sup>-2</sup>A)</td><td>0.5</td><td>0.5</td><td>0.75</td><td>1.</td><td>0.65</td><td>0.3</td><td>0.1</td><td>0.1</td><td>0.1</td></tr></table>

$$L'\text{'intensité maximale qui a parcouru le circuit est de } I = 10^{-2}A$$

# Exercices sur la Dérivation numérique

## Exercice 1: Déplacement d'un mobile

Une voiture de formule 1, assimilée à un point matériel, se déplace en ligne droite lors d'une course. On recueille dans un tableau, la distance parcourue par le mobile en fonction du temps.

<table><tr><td>t(s)</td><td>0</td><td>2</td><td>4</td><td>6</td><td>8</td></tr><tr><td>x(m)</td><td>20</td><td>40</td><td>100</td><td>200</td><td>340</td></tr></table>

a) calculer à partir des dérivées centrales, la vitesse et l'accélération de la voiture aux temps $t = 2s; 4s; 6s$.

b) calculer, à partir des dérivées à gauche ou à droite, la vitesse et l'accélération de la voiture aux temps $t = 0s; 8s$.

c) quelle est la nature du mouvement? Justifier votre réponse.

### Indications

$$\text{dérivées centrales : } v = \frac{dx}{dt} = \frac{x(t_{i+1})-x(t_{i-1})}{2h}; \quad a = \frac{dv}{dt} = \frac{d^2x}{dt^2} = \frac{x(t_{i+1})-2x(t_i)+x(t_{i-1})}{h^2} \quad \text{avec } h = 2s$$

$$\begin{cases} t = 2s \Rightarrow v = 20\,\text{ms}^{-1}; \quad a = 10\,\text{ms}^{-2} \\ t = 4s \Rightarrow v = 40\,\text{ms}^{-1}; \quad a = 10\,\text{ms}^{-2} \\ t = 6s \Rightarrow v = 60\,\text{ms}^{-1}; \quad a = 10\,\text{ms}^{-2} \end{cases}$$

$$t = 0s \text{ : dérivées à droite : } v = \frac{dx}{dt} = \frac{x(t_{i+1})-x(t_i)}{h^2} = 10\,\text{ms}^{-1}; \quad a = \frac{dv}{dt} = \frac{d^2x}{dt^2} = \frac{x(t_i)-2x(t_{i+1})+x(t_{i+2})}{h^2} = 10\,\text{ms}^{-2}$$

$$t = 8s \text{ : dérivées à gauche : } v = \frac{dx}{dt} = \frac{x(t_i)-x(t_{i-1})}{h^2} = 70\,\text{ms}^{-1}; \quad a = \frac{d^2x}{dt^2} = \frac{x(t_i)-2x(t_{i-1})+x(t_{i-2})}{h^2} = a = 10\,\text{ms}^{-2}$$

$$\text{mouvement rectiligne uniformément accéléré car } a = cte \text{ et } \bar{v} \cdot \bar{a} > 0$$

## Exercice 2: décharge d'un condensateur

Lors de la décharge d'un condensateur de capacité $C = 10^{-5}F$ dans un dipôle non linéaire, on a relevé les tensions suivantes aux bornes du condensateur (voir tableau):

<table><tr><td>t(ms)</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td></tr><tr><td>U(V)</td><td>4</td><td>3,5</td><td>3</td><td>2</td><td>1,1</td><td>0,7</td><td>0,5</td><td>0,4</td><td>0,3</td></tr></table>

a) calculer l'intensité du courant à $t = 0ms$ et à $t = 8ms$ en utilisant respectivement la dérivée à droite et à gauche.

b) calculer l'intensité du courant aux temps $t = 1; 2; 3; 4; 5; 6; 7 ms$ en utilisant la dérivée centrale.
c) compléter le tableau et tracer le graphe $I = f(f)$.

d) déterminer la valeur maximale de l'intensité du courant qui a circulé dans le circuit.

### Indications

$$h = t_{i+1} - t_i = 1 \text{ms}$$

Pour $t = 1; 2; 3; 4; 5; 6$ ms on a une dérivée centrale : $i(t_i) = -C \frac{dU}{dt} = -C \frac{U(t_{i+1})-U(t_{i-1})}{2h}$

Pour $t = 0 \text{ms on a une dérivée à droite : } i(t_i) = -C \frac{dU}{dt} = -C \frac{U(t_{i+1})-U(t_i)}{2h}$

Pour $t = 8 \text{ms on a une dérivée à gauche : } i(t_i) = -C \frac{dU}{dt} = -C \frac{U(t_i)-U(t_{i-1})}{h^2}$

<table><tr><td>$I(\times 10^{-2}A)$</td><td>0,5</td><td>0,5</td><td>0,75</td><td>0,95</td><td>0,65</td><td>0,3</td><td>0,15</td><td>0,1</td><td>0,1</td></tr></table>

$$I_{\text{max}} = 0,95 \times 10^{-2} A$$

### Exercice 3 : calcul de la tension dans un circuit R, L

Dans un circuit avec une tension $E(t)$ et une inductance $L$, la première loi de Kichhoff donne la relation :

$$E = L \frac{di}{dt} + Ri$$

Où $R$ est la résistance dans le circuit et $i$ le courant. Supposons qu'on a mesuré pour plusieurs valeurs du temps $t$, l'intensité $i$. Les résultats sont consignés dans le tableau ci-dessous :

<table><tr><td>$t(s)$</td><td>1,00</td><td>1,01</td><td>1,02</td><td>1,03</td><td>1,04</td></tr><tr><td>$i(A)$</td><td>3,10</td><td>3,12</td><td>3,14</td><td>3,18</td><td>3,24</td></tr></table>

On pose que l'inductance est constante avec $L = 0,98 \text{ Henries}$. De même, $R = 0,142 \text{ Ohms}$.

Calculer la tension $E(t)$ pour les 5 valeurs de l'expérience.

### Indications

<table><tr><td>$t(s)$</td><td>1,00</td><td>1,01</td><td>1,02</td><td>1,03</td><td>1,04</td></tr><tr><td>$E(V)$</td><td>2,400</td><td>2,403</td><td>3,386</td><td>5,352</td><td>7,320</td></tr></table>
# Chapitre 6 : Intégration numérique

## Problème

On donne la courbe déduite du tableau ci-dessous :

<table><thead><tr><td>Proportion (x)</td><td>Puissance (GW)</td></tr></thead><tbody><tr><td>0</td><td>30.00</td></tr><tr><td>0.1</td><td>29.00</td></tr><tr><td>0.2</td><td>24.00</td></tr><tr><td>0.3</td><td>20.66</td></tr><tr><td>0.4</td><td>19.41</td></tr><tr><td>0.5</td><td>19.04</td></tr><tr><td>0.6</td><td>18.72</td></tr><tr><td>0.7</td><td>18.49</td></tr><tr><td>0.8</td><td>18.30</td></tr><tr><td>0.9</td><td>15.49</td></tr><tr><td>1</td><td>0.77</td></tr></tbody></table>

<figure><img src="image_34.png" /></figure>

Cette courbe indique la proportion de l'année où la demande d'électricité atteint ou dépasse un niveau de puissance donné (en gigawatts ou GW) pour un service d'électricité. L'aire sous cette courbe est tout simplement l'énergie totale E vendue au cours de l'année. Cette donnée est donc importante pour l'entreprise en question. En déduire l'énergie totale E.

On note que $E = \int_{x_i}^{x_f} P \, dx$, avec :

$E$ = GW année; $P$ = puissance en GW; $x_i$ = proportion initiale; $x_f$ = proportion finale

## Introduction

Lorsqu'une fonction $f(x)$ est définie et continue dans l'intervalle $[a; b]$, l'intégration de $f(x)$ est basée principalement sur la relation :

$$I = \int_{a}^{b} f(x) \, dx = F(b) - F(a)$$

Où $F(x)$ est une primitive de $f(x)$.

Cette méthode de calcul n'est pas toujours réalisable si $F(x)$ ne peut s'exprimer à l'aide de fonctions élémentaires, ou si $F(x)$ n'est définie que par un ensemble de valeurs numériques provenant de résultats expérimentaux.
Il est possible d'approcher la valeur de $I$ en évaluant l'aire $S$ comprise entre l'axe $(ox)$ et les parallèles à $(oy)$ menées par $a$ et $b$. Cette aire est constituée d'une somme finie de $n$ aires élémentaires $A_i$ de base $h = \frac{b-a}{n}$ et de formes plus ou moins complexe et qui caractérise la méthode utilisée. On a :

$$I = \int_{a}^{b} f(x) dx$$

Avec

$$J = S = \sum_{i=0}^{n} A_{i}; \quad I = J \pm R(f)$$

$J$ = valeur approchée de $I$; $R(f)$ = l'erreur

**NB** : il existe plusieurs méthodes, mais dans notre cas, nous n'en étudierons que deux.

### III- Méthode des rectangles

#### 1- Principe

Considérons une subdivision de l'intervalle $[a; b]$ en $n$ parties égales de longueur $h = \frac{b-a}{n}$.

La méthode consiste à remplacer $f(x)$ par une fonction en escalier définie par $g(x_i) = f(x_i)$ (voir figure ci-dessous).

L'aire élémentaire $A_i$ est celle d'un rectangle définie par la base (largeur) $h$ et une hauteur (longueur) $f(x_i)$, soit donc :

$$A_i = h f(x_i)$$

<figure><img src="image_35.png" /></figure>

La valeur approchée de l'intégrale est de la forme :

$$J = \sum_{i=0}^{n} A_{i} = \sum_{i=0}^{n} h f(x_{i}) = \frac{b-a}{n} \sum_{i=0}^{n} f(x_{i})$$
Ou encore :

$$
J = \frac{b-a}{n} [f(x_0) + \dots + f(x_n)]
$$

On sait aussi que $x_i = a + ih$. On peut donc écrire que

$$
J = \frac{b-a}{n} \sum_{i=0}^{n} f(a+ih)
$$

2- Calcul d'erreur

L'erreur élémentaire εᵢ(h) est la différence entre l'aire en dessous de f(x) délimitée par xᵢ₋₁
et xᵢ et l'aire en dessous de g(x) délimitée par ces mêmes coordonnées. Soit donc :

$$
\epsilon_i(h) = \int_{x_{i-1}}^{x_i} f(x)dx - h f(x_{i-1}) \text{ Avec } x_{i-1} = x_i - h
$$

Posons F(x) la primitive de f(x). Il vient donc que :

$$
\epsilon_i(h) = F(x_i) - F(x_i - h) - hf(x_i - h)
$$

Si l'on fait un développement limité de εᵢ(h) autour de h = 0, on a :

$$
\epsilon_i(h) = \epsilon_i(0) + h\epsilon'_i(0) + \frac{h^2}{2}\epsilon''_i(0) + \dots
$$

On calcule chaque terme du développement limité et on s'arrête lorsqu'un terme est non nul.

On a donc :

$$
\epsilon_i(0) = F(x_i) - F(x_i) - 0 \times f(x_i) = 0
$$

$$
\epsilon'_{i}(h) = f(x_{i} - h) - f(x_{i} - h) + hf'(x_{i} - h) = hf'(x_{i} - h)
$$

$$
\epsilon'_{i}(0) = f(x_{i}) - f(x_{i}) - 0 \times f'(x_{i}) = 0
$$

$$
\epsilon''_{i}(h) = f'(x_{i} - h) - h f''(x_{i} - h)
$$

$$
\epsilon''_{i}(0) = f'(x_{i}) - 0 \times f''(x_{i}) = f'(x_{i}) \neq 0
$$

$$
\text{Soit donc : } \epsilon_i(h) = \frac{h^2}{2} \epsilon_i''(0) = \frac{h^2}{2} f'(x_i)
$$

L'erreur totale est la somme de toutes les erreurs. On a :

$$
R(f) = \sum_{i=0}^{n} |\epsilon_i(h)| = \frac{h^2}{2} \sum_{i=0}^{n} |f'(x_i)|
$$

$$
\text{Posons } M_1 = \max_{i=0,n} |f'(x_i)|
$$

On montre que : $R(f) \le \frac{(b-a)^2}{2n^2} nM_1$

Soit : $R(f) \le \frac{(b-a)^2}{n} M_1$
### 3- Algorithme

<figure><img src="image_36.png" /></figure>

## IV- Méthode des trapèzes

### 1- Principe

Considérons une subdivision de l'intervalle $[a; b]$ en $n$ parties égales de longueur $h = \frac{b-a}{n}$.

La méthode consiste à remplacer $f(x)$ par une brisée définie par $g(x_i) = f(x_i)$ et à calculer l'aire de chaque trapèze élémentaire (voir figure ci-dessous).

L'aire élémentaire $A_i$ du trapèze compris entre $x_{i-1}$ et $x_i$ est celle d'un trapèze définie par la base $f(x_i)$, sa largeur $f(x_{i-1})$ et sa hauteur $h$, soit donc :

$$A_i = \frac{f(x_i) + f(x_{i-1})}{2} (x_i - x_{i-1}) = h \frac{f(x_i) + f(x_{i-1})}{2}$$
<figure><img src="image_37.png" /></figure>

La valeur approchée de l'intégrale est de la forme :

$$J = \sum_{i=1}^{n} A_i = \sum_{i=1}^{n} \frac{f(x_i) + f(x_{i-1})}{2} (x_i - x_{i-1}) = \frac{b-a}{2n} \sum_{i=1}^{n} (f(x_i) + f(x_{i-1}))$$

En développant cette expression avec $x_0 = a$; $x_n = b$, on a :

$$J = \frac{b-a}{2n} [f(x_0) + f(x_1) + f(x_2) + f(x_3) + \dots + f(x_{n-1}) + f(x_{n-1}) + f(x_n)]$$

$$J = \frac{b-a}{2n} [f(a) + 2f(x_1) + 2f(x_2) + \dots + 2f(x_{n-1}) + f(b)]$$

$$J = \frac{b-a}{2n} \left[ f(a) + f(b) + 2 \sum_{i=1}^{n-1} f(x_i) \right]$$

NB : on peut aussi poser que : $x_i = a + ih$.

Act

## 2- Calcul d'erreur

L'erreur élémentaire $\varepsilon_i(h)$ est la différence entre l'aire en dessous de $f(x)$ délimitée par $x_{i-1}$ et $x_i$ et l'aire en dessous de $g(x)$ délimitée par ces mêmes coordonnées. Soit donc :

$$\varepsilon_i(h) = \int_{x_{i-1}}^{x_i} f(x)dx - (x_i - x_{i-1}) \frac{f(x_i) + f(x_{i-1})}{2}$$

Posons $F(x)$ la primitive de $f(x)$ et $x_{i-1} = x_i - h$. Il vient donc que :

$$\varepsilon_i(h) = F(x_i) - F(x_i - h) - \frac{h}{2} [f(x_i) + f(x_i - h)]$$

Si l'on fait un développement limité de $\varepsilon_i(h)$ autour de $h = 0$, on a :

$$\varepsilon_i(h) = \varepsilon_i(0) + h\varepsilon'_i(0) + \frac{h^2}{2}\varepsilon''_i(0) + \frac{h^3}{6}\varepsilon'''_i(0) + \dots$$

On calcule chaque terme du développement limité et on s'arrête lorsqu'un terme est non nul.
On a donc :

$$
\begin{align*}
\varepsilon_i(0) &= F(x_i) - F(x_i) - \frac{0}{2} \times [f(x_i) + f(x_i)] = 0 \\
\varepsilon_i(h) &= f(x_i - h) - \frac{1}{2}f(x_i) - \frac{1}{2}f(x_i - h) + \frac{h}{2}f'(x_i - h) = \frac{1}{2}f(x_i - h) - \frac{1}{2}f(x_i) + \frac{h}{2}f'(x_i - h)
\end{align*}
$$

$$
\begin{align*}
\epsilon_i'(h) &= f(x_i - h) - \frac{1}{2}f(x_i) - \frac{1}{2}f(x_i - h) + \frac{h}{2}f'(x_i - h) = \frac{1}{2}f(x_i - h) - \frac{1}{2}f(x_i) + \\
&\qquad \frac{h}{2}f'(x_i - h) \\
\epsilon_i'(0) &= \frac{1}{2}f(x_i) - \frac{1}{2}f(x_i) - \frac{0}{2} \times f'(x_i) = 0
\end{align*}
$$

$$
\begin{align*}
\epsilon''_{i}(h) &= -\frac{1}{2}f'(x_{i}-h) + \frac{1}{2}f'(x_{i}-h) - \frac{h}{2}f''(x_{i}-h) = -\frac{h}{2}f''(x_{i}-h) \\
\epsilon''_{i}(0) &= 0 \times f''(x_{i}) = 0
\end{align*}
$$

$$
\begin{align*}
\epsilon'''_{i}(h) &= -\frac{1}{2}f''(x_{i}-h) + \frac{h}{2}f'''(x_{i}-h) \\
\epsilon'''_{i}(0) &= -\frac{1}{2}f''(x_{i}) + \frac{0}{2} \times f'''(x_{i}) = -\frac{1}{2}f''(x_{i}) \neq 0
\end{align*}
$$

Soit donc :

$$
\epsilon_i(h) = \frac{h^3}{6} \epsilon'''_i(0) = -\frac{h^3}{12} f'(x_i)
$$

L’erreur totale est la somme de toutes les erreurs. On a :

$$
R(f) \leq \sum_{i=1}^{n} |\epsilon_i(h)| = \frac{h^3}{12} \sum_{i=1}^{n} |f''(x_i)|
$$

$$
\text{Posons } M_2 = \max_{i=1,n} |f''(x_i)|
$$

On montre que :

$$
R(f) \le \frac{(b-a)^3}{12n^3} nM_2
$$

Soit :

$$
R(f) \le \frac{(b-a)^3}{12n^2} M_2
$$
# 1- Algorithme

<figure><img src="image_38.png" /></figure>

## Résolution du problème

La proportion est calculée par pas de $h = 0.1$. On a donc $n = 10$ intervalles.

## Méthode des rectangles

$$J = \frac{b-a}{n} \sum_{i=0}^{n} f(x_i)$$

$$J = \frac{1-0}{10} (30 + 29 + 24 + 20.66 + 19.41 + 19.04 + 18.72 + 18.49 + 18.3 + 15.49 + 0.77)$$

$J = 21.388 \text{ GW année}$

L'erreur se calcule en recherchant chaque dérivée première. On ne calculera pas les dérivées à gauche et à droite pour les valeurs extrêmes car elles sont aberrantes. On calculera donc les dérivées centrales pour les autres valeurs (voir tableau ci-dessous).

On note que $M_1 = \sup|f'(x)| = 147.2$
D'où

$$R(f) \le \frac{(1-0)^2}{10} \times 87.65 = 8.765$$

On a donc : $E = J \pm R(f) = (21.388 \pm 8.765) \text{ GW année}$

Méthode des trapèzes

$$J = \frac{b-a}{2n} \left[ f(a) + f(b) + 2 \sum_{i=1}^{n-1} f(x_i) \right]$$

$$J = \frac{1-0}{2 \times 10} (30 + 0.77 + 2 \times (29 + 24 + 20.66 + 19.41 + 19.04 + 18.72 + 18.49 + 18.3 + 15.49))$$

J = 19.8495 GW année

L'erreur se calcule en recherchant chaque dérivée seconde. On ne calculera pas les dérivées à gauche et à droite pour les valeurs extrêmes car elles sont aberrantes. On calculera donc les dérivées centrales pour les autres valeurs (voir tableau ci-dessous).

On note que $M_1 = \sup|f''(x)| = 1191$

D'où

$$R(f) \le \frac{(1-0)^3}{12 \times (10)^2} \times 1191 = 0.9925$$

On a donc : $E = J \pm R(f) = (19.8495 \pm 0.9925) \text{ GW année}$

<table><thead><tr><th>Proportion (x)</th><th>0</th><th>0.1</th><th>0.2</th><th>0.3</th><th>0.4</th><th>0.5</th><th>0.6</th><th>0.7</th><th>0.8</th><th>0.9</th><th>1</th></tr></thead><tbody><tr><th>Puissance (GW)</th><td>30</td><td>29</td><td>24</td><td>20.66</td><td>19.41</td><td>19.04</td><td>18.72</td><td>18.49</td><td>18.3</td><td>15.49</td><td>0.77</td></tr><tr><th>f'(x)</th><td>-30</td><td>-41.7</td><td>-22.95</td><td>-8.1</td><td>-3.45</td><td>-2.75</td><td>-2.1</td><td>-15</td><td>-87.65</td><td></td><td></td></tr><tr><th>f''(x)</th><td>-400</td><td>166</td><td>209</td><td>88</td><td>5</td><td>9</td><td>4</td><td>-262</td><td>-1191</td><td></td><td></td></tr></tbody></table>

## Exercices sur l'intégration numérique

### Exercice 1 : Déplacement d'une particule dans un fluide

1) Rappeler le principe de la méthode:

a) des rectangles

b) des trapèzes

On donne l'intégrale suivante : $I = \int_a^b f(x) dx$.

2) Rappeler (en les démontrant) les expressions de $I$, $J_n$, $R(f)$ pour ces deux méthodes suscitées.

3) Donnez les ordinogrammes de résolution de ces deux méthodes.

4) Application

Si une particule de masse $m$ se déplace dans un fluide, elle est sujette à une force de viscosité $R$ qui est une fonction de la vitesse. La relation entre la résistance $R$, la vitesse $v$ et le temps $t$ est donnée par l'équation :

$$t = \int_{v_0}^{v(t)} \frac{m}{R(u)} du$$

supposons que $R(u) = u\sqrt{u}$ où $R$ est en Newton et $v$ en $ms^{-1}$. Si $m = 10kg, v_0 = 10ms^{-1}$, approximer le temps requis pour que la vitesse diminue jusqu'à $5ms^{-1}$ en utilisant:

a) la méthode des rectangles avec $h = 1$

b) la méthode des trapèzes avec $h = 1$

c) comparer avec la valeur exacte qui est $t = 2,6197s$.

NB : On prendra le soin de calculer aussi l'erreur pour chaque méthode.
**Indications :**

Se référer au cours pour les principes

<table><tr><td>i</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td>u<sub>i</sub></td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td>f(u<sub>i</sub>)</td><td>0,09</td><td>0,07</td><td>0,05</td><td>0,04</td><td>0,04</td><td>0,03</td></tr></table>

Méthode des rectangles : $J_n = 3,2433 \text{ s}; R(f) = 0,7500 \text{ s}; t = (3,2433 \pm 0,7500) \text{ s}$

Méthode des trapèzes : $J_n = 2,6380 \text{ s}; R(f) = 0,0417 \text{ s}; t = (2,6380 \pm 0,0417) \text{ s}$

La méthode des trapèzes donne une valeur proche de la valeur exacte.

**Exercice 2 :** Capacité d'un condensateur

Pour déterminer la capacité C d'un condensateur, une méthode simple consiste à le brancher à un générateur de tension $U_g = 3V$ et de mesurer l'intensité du courant $I(t)$ avec un ampèremètre numérique rapide. Les mesures ont donné :

<table><tr><td>t (ms)</td><td>0</td><td>2</td><td>4</td><td>6</td><td>8</td><td>10</td><td>12</td><td>14</td><td>16</td><td>18</td><td>20</td><td>22</td><td>24</td><td>26</td></tr><tr><td>I (mA)</td><td>0</td><td>1.027</td><td>1.054</td><td>0.812</td><td>0.556</td><td>0.357</td><td>0.220</td><td>0.132</td><td>0.077</td><td>0.045</td><td>0.025</td><td>0.014</td><td>0.008</td><td>0.004</td></tr></table>

Dans la suite, on exprimera tous les résultats à $10^{-3}$ près.

1- Tracer le graphe $I = f(t)$.

2- Déterminer la capacité C (en $\mu F$) du condensateur par la méthode des trapèzes.

3- Comparer avec la valeur exacte qui est de $C = 3\mu F$.

**Indications :**

$$C = \frac{1}{U} \int_{0}^{26} i \, dt \text{ avec } h = \frac{b-a}{n} = \frac{26-0}{13} = 2 \, \text{ms}$$

$$C = 2,886 \, \mu F; R(f) = 0,722 \, \mu F; C = (2,886 \pm 0,722) \, \mu F$$

**Exercice 3 :** Aire d'un disque

Considérons le disque limité par le cercle d'équation $x^2 + y^2 = a^2$. Par raison de symétrie, l'aire du disque est le double de l'aire limitée par le demi-cercle d'équation $y = f(x) = \sqrt{a^2 - x^2}$ et l'axe (ox).

a) Calculer analytiquement l'aire $S(a) = 2 \int_{-a}^{+a} f(x)dx$ du disque en fonction du rayon $a$. On effectuera un changement de variable en posant $x = a\cos(t)$.

b) Evaluer $J_n$ et l'erreur $R(f)$ en fonction de $a$ par la méthode des rectangles. On posera que le nombre d'intervalle est $n = 4$.

c) Que vaut, par la méthode des rectangles, la valeur de l'aire $S(a)$ si $a = 20 \text{cm}$.

d) Comparer les résultats obtenus avec la valeur exacte pour $a = 20 \text{cm}$.

**Indications :**

$$\text{Méthode directe : } S(a) = 2 \int_{-a}^{+a} \sqrt{a^2 - x^2} \, dx = 2 \int_{0}^{\pi} (1 - \cos 2t) \, dt = \pi a^2 = 1257,14 \, \text{cm}^2$$

$$\text{Méthode des rectangles : } S(a) = 2 \int_{-a}^{+a} \sqrt{a^2 - x^2} \, dx = \frac{a^2}{2} (1 + \sqrt{3}) = 1092,82 \, \text{cm}^2$$

$$R(f) = \frac{(a + a)^2}{4} \times \sup|f'(x)| = \frac{a^2}{\sqrt{3}} = 230,94 \, \text{cm}^2$$

**Exercice 4 :**

La méthode des rectangles consiste à remplacer la fonction $f$ par une fonction $g$ en escalier définie par $g(x_i) = f(x_i)$ pour $x_{i-1} \le x \le x_i$. on donne : $I = \int_a^b sh(x)dx$.

1- Déterminer une valeur approchée de $ch(0,5)$ à partir de la table de $sh(x)$ suivant :
<table><tr><td>x</td><td>0</td><td>0,1</td><td>0,2</td><td>0,3</td><td>0,4</td><td>0,5</td></tr><tr><td>sh(x)</td><td>0</td><td>0,1002</td><td>0,2013</td><td>0,3045</td><td>0,4108</td><td>0,5211</td></tr></table>

2- Comparer avec la valeur réelle.

Indications :

$$J_n = 0,15379; R(f) = \frac{(0,5-0)^2}{2\times5} \times 1,1276 = 0,02819; ch(0,5) = 1 + ch(0) \approx J_n + 1 = 1,15379$$

La valeur réelle est $ch(0,5) = 1,1276$. La différence entre la valeur réelle et la valeur calculée est $\Delta= 1,15379 - 1,1276 = 0,02619$ qui tend sensiblement vers $R(f)$.
# Chapitre 7 : Algebre lineaire numerique

## 1. Methodes matricelles numeriques.

### Introduction

Dans ce chapitre, nous procéderons par la résolution de certains exercices.

* Lecture et impression d'une matrice ligne par ligne.

* Recopie d'une matrice $A(i, j)$ dans une matrice $B(i, j)$.

* Construction d'une matrice nulle et d'une matrice unité.

* Produit et quotient d'une matrice par un réel non nul.

* Somme, différence et produit de deux matrices.

* Résolution d'un système d'équations par la méthode du pivot de Gauss.

* Résolution d'un système d'équations par la méthode de Jacobi.

### I- Opérations élémentaires

Dans cette partie, nous présenterons uniquement des exemples d'algorithmes (ordinogrammes ou pseudo-codes).

#### 1- Lecture et impression d'une matrice ligne par ligne

On désire lire tous les éléments d'une matrice et ensuite les afficher ligne par ligne.

Algorithme *Lecture_impression*

A tableau n × m

i, j, n, m entier

Pour i ← 1, n faire

Pour j ← 1, m faire

lire $A(i,j)$

fin (j)

fin (i)

Pour i ← 1, n faire

Pour j ← 1, m faire

afficher $A(i,j)$

fin (j)

fin (i)

fin

<figure><img src="image_39.png" /></figure>
2- Recopie d'une matrice A(i, j) dans une matrice B(i, j)

Algorithme Recopie
A, B tableaux n × m
i, j, n, m entier
Pour i ← 1, n faire
Pour j ← 1, m faire
lire A(i, j)
B(i, j) ← A(i, j)
fin (j)
fin (i)
Pour i ← 1, n faire
Pour j ← 1, m faire
afficher B(i, j)
fin (j)
fin (i)
fin

<figure><img src="image_40.png" /></figure>
### 3- Construction d'une matrice nulle et d'une matrice unité

On veut construire une matrice nulle $U(i,j)$ et une matrice unité $I(i,j)$ toutes deux de
dimension $n \times n$.

Algorithme Nulle_unité

$U, I$ tableaux $n \times n$

$i, j, n$ entier

Pour $i \leftarrow 1, n$ faire

Pour $j \leftarrow 1, n$ faire

$U(i, j) \leftarrow 0$

Si $i = j$ alors

$I(i, j) \leftarrow 1$

Sinon $I(i, j) \leftarrow 0$

afficher $U(i, j), I(i, j)$

fin (j)

fin (i)

fin

<figure><img src="image_41.png" /></figure>
## 4- Produit et quotient d'une matrice par un réel non nul

On veut multiplier et ensuite diviser une même matrice $A(i, j)$ par un réel $\alpha$.

Algorithme quotient_produit

A, AP, AQ tableaux n × m

i, j, n, m entier

Pour i ← 1, n faire

Pour j ← 1, m faire

lire A(i, j)

AP(i, j) ← $\alpha * A(i, j)$

AQ(i, j) ← $A(i, j)/\alpha$

fin (j)

fin (i)

Pour i ← 1, n faire

Pour j ← 1, m faire

afficher AP(i, j), AQ(i, j)

fin (j)

fin (i)

fin

<figure><img src="image_42.png" /></figure>
## 5- Somme, différence et produit de deux matrices

On veut faire la somme $S(i,j)$, la différence $D(i,j)$ et le produit $P(i,j)$ de deux matrices $A(i,j)$ et $B(i,j)$ de dimension $n \times n$.

Algorithme somme_différence_produit

A, B, S, D, P tableaux n × n

i, j, k, n entier

Pour i ← 1, n faire

Pour j ← 1, n faire

lire A(i,j), B(i,j)

$S(i,j) \leftarrow A(i,j) + B(i,j)$

$D(i,j) \leftarrow A(i,j) - B(i,j)$

fin (j)

fin (i)

Pour i ← 1, n faire

Pour j ← 1, n faire

$P(i,j) \leftarrow 0$

Pour k ← 1, n

$P(i,j) \leftarrow P(i,j) + A(i,k) \ast B(k,j)$

fin (k)

fin (j)

fin (i)

Pour i ← 1, n faire

Pour j ← 1, n faire

afficher S(i,j), D(i,j), P(i,j)

fin (j)

fin (i)

fin

<figure><img src="image_43.png" /></figure>
## II- Résolution d'un système d'équations par la méthode du pivot de Gauss

Résolvons le système ci-dessous par la méthode du pivot de Gauss :

$$ egin{cases} a+b+c=-3 \\ 4a+2b+c=0 \\ 9a+3b+c=5 \end{cases} $$

Pour la résolution, on choisit successivement chaque ligne comme ligne pivot ; le pivot étant le premier élément non nul de la ligne. Ainsi :

* On divise la première ligne par $a_{11}$. Ensuite,

* On annule le premier terme de chacune des autres lignes :

- A la deuxième ligne, on retranche la ligne $L_1$ multipliée par $a_{21}$, c'est-à-dire
  $$L_2 - L_1 \times a_{11}$$

- A la troisième ligne, on retranche la ligne $L_1$ multipliée par $a_{31}$, c'est-à-dire
  $$L_3 - L_1 \times a_{13}$$

* On prend maintenant la deuxième ligne $L_2$ comme ligne pivot et la nouvelle valeur $a'_{22}$ comme élément pivot. On divise $L_2$ par $a'_{22}$.

- A la première ligne, on retranche la ligne $L_2$ multipliée par $a'_{12}$, c'est-à-dire
  $$L_1 - L_2 \times a'_{12}$$

- A la troisième ligne, on retranche la ligne $L_2$ multipliée par $a'_{32}$, c'est-à-dire
  $$L_3 - L_2 \times a'_{32}$$

* On prend maintenant la deuxième ligne $L_2$ comme ligne pivot et la nouvelle valeur $a'_{22}$ comme élément pivot. On divise $L_2$ par $a'_{22}$.

- A la première ligne, on retranche la ligne $L_2$ multipliée par $a'_{12}$, c'est-à-dire
  $$L_1 - L_2 \times a'_{12}$$

- A la troisième ligne, on retranche la ligne $L_2$ multipliée par $a'_{32}$, c'est-à-dire
  $$L_3 - L_2 \times a'_{32}$$

* On prend maintenant la deuxième ligne $L_3$ comme ligne pivot et la nouvelle valeur $a''_{33}$ comme élément pivot. On divise $L_3$ par $a''_{33}$.

- A la première ligne, on retranche la ligne $L_3$ multipliée par $a''_{13}$, c'est-à-dire
  $$L_1 - L_3 \times a''_{13}$$

- A la deuxième ligne, on retranche la ligne $L_3$ multipliée par $a''_{23}$, c'est-à-dire
  $$L_2 - L_3 \times a''_{23}$$

Ce mode de calcul annule de ce fait les autres termes de la matrice pour n'obtenir qu'une matrice unité et les valeurs de $a, b, c$.

Le système à résoudre revient à :

$$ egin{vmatrix} 1 & 1 & 1 & -3 & L_1/1 & 1 & 1 & 1 & -3 & L_2/(-2) \\ 4 & 2 & 1 & 0 & \rightarrow & 4 & 2 & 1 & 0 & \rightarrow & 0 & -2 & -3 & 12 \\ 9 & 3 & 1 & 5 & & 9 & 3 & 1 & 5 & L_3 - 9L_1 & 0 & -6 & -8 & 32 \end{vmatrix} $$
$$
\left|
\begin{array}{ccc|c}
1 & 1 & 1 & -3 \\
0 & 1 & \frac{3}{2} & -6 \\
0 & -6 & -8 & 32
\end{array}
\right|
\quad
\begin{array}{l}
L_1 - L_2 \\
\rightarrow \\
L_3 + 6L_2
\end{array}
\quad
\left|
\begin{array}{ccc|c}
1 & 0 & -\frac{1}{2} & 3 \\
0 & 1 & \frac{3}{2} & -6 \\
0 & 0 & 1 & -4
\end{array}
\right|
\quad
\begin{array}{l}
L_3/1 \\
\rightarrow
\end{array}
\quad
\left|
\begin{array}{ccc|c}
1 & 0 & -\frac{1}{2} & 3 \\
0 & 1 & \frac{3}{2} & -6 \\
0 & 0 & 1 & -4
\end{array}
\right|
\quad
\begin{array}{l}
L_1 + \frac{1}{2}L_3 \\
\rightarrow \\
L_2 - \frac{3}{2}L_3
\end{array}
$$
$$
\begin{array}{c}
\begin{array}{c|c}
1 & 0 \\
0 & 1 \\
0 & 0
\end{array}
\\
\text{d'où}
\\
-4
\end{array}
\quad
\left\{
\begin{array}{l}
a = 1 \\
b = 0 \\
c = -4
\end{array}
\right.
$$

NB : l’algorithme de résolution n’est pas donné afin de simplifier la compréhension.

### III- Résolution d'un système d'équations par la méthode de Jacobi

Considérons le système linéaire suivant :

$$
\left\{
\begin{array}{l}
a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + \cdots + a_{1n}x_n = b_1 \\
a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + \cdots + a_{2n}x_n = b_2 \\
\vdots \\
a_{n1}x_1 + a_{n2}x_2 + a_{n3}x_3 + \cdots + a_{nn}x_n = b_n
\end{array}
\right.
$$

On suppose que tous les éléments de la diagonale sont non nuls ($a_{ii} \neq 0$). Dans le cas où un élément de cette diagonale est nulle, on pivote cette ligne avec celle qui la précède ou la suit. A partir d'une approximation initiale, (valeurs arbitrairement choisies) $x_1^0, x_2^0, \dots, x_n^0$ comme dans le cas de la méthode du point fixe, on construit l'algorithme qui consiste à isoler le coefficient de la diagonale de chaque ligne du système. Ainsi on a :

$$x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1, j \neq i}^{n} a_{ij} x_j^{(k)} \right)$$

Remarques :

* On arrête les calculs lorsque deux valeurs successives de $x_i$ sont « suffisamment » voisines. On peut utiliser un critère de convergence absolue :

$$|x_i^{(k+1)} - x_i^{(k)}| \le \varepsilon$$

* On utilisera un critère simple de convergence pour montrer la convergence de la méthode comme dans le cas de la méthode du point fixe. On dira donc que la méthode de Jacobi est convergente si la matrice est diagonale strictement dominante, c'est-à-dire, si : $\forall i, |a_{ii}| > \sum_{j \neq i}^{n} |a_{ij}|$
## 2. Resolutions des systemes d'equations lineaires

### 2.1 Introduction

Un système de n équations à n inconnues $x_1, ..., x_n$ réelles est appelé système linéaire d'ordre $n$.

Ce système se présente sous la forme suivante:

$$ 
\left\{ 
\begin{array}{l} 
a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \\ 
a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \\ 
\vdots \\ 
a_{n1}x_1 + a_{n2}x_2 + \dots + a_{nn}x_n = b_n 
\end{array} 
\right. 
$$

Les $(a_{ij})_{1 \le i \le n}$ sont les coefficients.

Les $b_i$ $1 \le i \le n$ sont les termes du second membre du système.

Les $x_1, ..., x_n$ sont les inconnues.

Ce système peut être écrit sous forme matricielle de la manière suivante:

$$ 
\left[ 
\begin{array}{c} 
a_{11} \ a_{12} \ a_{13} \ \dots \ \dots \ a_{1n} \\ 
a_{21} \ a_{22} \ a_{23} \ \dots \ \dots \ a_{2n} \\ 
\dots \ \dots \ \dots \ \dots \ \dots \ \dots \\ 
a_{n1} \ a_{n2} \ a_{n3} \ \dots \ \dots \ a_{nn} 
\end{array} 
\right] 
\left[ 
\begin{array}{c} 
x_1 \\ 
x_2 \\ 
x_3 \\ 
x_n 
\end{array} 
\right] 
= 
\left[ 
\begin{array}{c} 
b_1 \\ 
b_2 \\ 
\dots \\ 
b_n 
\end{array} 
\right] 
\Leftrightarrow A_n X_n = B_n 
$$

<figure><img src="image_44.png" /></figure>

A est appelée matrice de transformation à n lignes et n colonnes

Exemple

$$ 
\left\{ 
\begin{array}{l} 
x + 3y + 4z = 50 \\ 
3x + 5y - 4z = 2 \\ 
4x + 7y - 2z = 31 
\end{array} 
\right. 
\quad \text{système linéaire} 
$$
## 2.2 Les méthodes directes

Les méthodes directes sont des algorithmes qui permettent de fournir des solutions **exactes** si elles existent en un nombre **fini** d'opérations. Ex: méthode de Cramer, Gauss, de Gauss-Jordan, Substitution ....

### 2.2.1 Cramer

L'existence et l'unicité de la solution d'un système linéaire dépend de la valeur du déterminant de $A$.

1- Si $det(A) \neq 0$ La matrice est dite **régulière** et le système admet une solution unique qui est donnée par la méthode de Cramer.

$$x_1 = \frac{det(A_1)}{det(A)}, \quad x_2 = \frac{det(A_2)}{det(A)}, \dots, \dots, \dots, \quad x_n = \frac{det(A_n)}{det(A)}$$

Le déterminant $det(A_i)$ est obtenu en remplaçant la $j^{\text{ème}}$ colonne de $A$ par $b_j$.

$$\det(A_i) = \begin{vmatrix} a_{11} & a_{12} & a_{13} & \dots & a_{1i-1} & b_1 & a_{1i+1} & \dots & a_{1n} \\ a_{21} & a_{22} & a_{23} & \dots & a_{2i-1} & b_2 & a_{2i+1} & \dots & a_{2n} \\ \vdots & \vdots & \vdots & \dots & \vdots & \vdots & \vdots & \dots & \vdots \\ a_{n1} & a_{n2} & a_{n3} & \dots & a_{ni-1} & b_n & a_{ni+1} & \dots & a_{nn} \end{vmatrix}$$

L'inconvénient de cette méthode qu'elle est couteuse en temps et en espace de stockage.

2- Si $det(A_i) = 0$ $A$ est dite matrice **singulière** et le système est dégénéré.

### Exemple

Soit le système suivant

$$\begin{cases} x+3y+4z = 50 \\ 3x+5y-4z = 2 \\ 4x+7y-2z = 31 \end{cases} \quad \text{La matrice } A \text{ du système est: } A = \begin{pmatrix} 1 & 3 & 4 \\ 3 & 5 & -4 \\ 4 & 7 & -2 \end{pmatrix}$$

Donc

$$\det A = \begin{vmatrix} 1 & 3 & 4 \\ 3 & 5 & -4 \\ 4 & 7 & -2 \end{vmatrix} = -8 \neq 0 \quad \text{Le système est régulier et admet alors la solution unique :}$$
$$
\begin{align*}
x_1 &= \begin{bmatrix} 50 & 3 & 4 \\ 2 & 5 & -4 \end{bmatrix} \\
&= \frac{317 - 2}{-8} = \frac{-24}{-8} = 3 \\
x_2 &= \begin{bmatrix} 1 & 50 & 4 \\ 3 & 2 & -4 \end{bmatrix} \\
&= \frac{431 - 2}{-8} = \frac{-40}{-8} = 5 \\
x_3 &= \begin{bmatrix} 1 & 3 & 50 \\ 3 & 5 & 2 \\ 4 & 7 & 31 \end{bmatrix} \\
&= \frac{-64}{-8} = 8
\end{align*}
$$
La solution est $x = (3,5,8)'$

2.2.2 Gauss sans pivotation

La méthode d'élimination de gauss est une méthode directe qui permet de résoudre un système d'équation linéaire Ax=b en un nombre fini d'opérations.

Elle consiste à transformer le système A*x=b en un système A'*x=b', où A' est une matrice triangulaire supérieure droite.

La matrice A' est obtenue par substitutions successives dans la matrice d'origine selon l'algorithme d'élimination de Gauss suivant:

1) La triangulatisation

pour $k=1$ jusqu'à $n-1$

$pivot \leftarrow a_{ik}$ (*stratégie de pivot *)

si $pivot \neq 0$ alors

pour $i=k+1$ jusqu'à $n$

$b_i \leftarrow b_i - \frac{a_{ik}}{pivot} b_k$

pour $j=k+1$ jusqu'à $n$

$a_{ij} \leftarrow a_{ij} - \frac{a_{ik}}{pivot} a_{kj}$

Fin pour

Fin pour

Fin Si

Fin

On appliquant cet algorithme de triangularisation le système devient le suivant

$$
\begin{pmatrix} a_{11} & \cdots & a_{1i} & \cdots & a_{1n} \\ 0 & \ddots & 0 & \ddots & 0 \\ 0 & \cdots & a_{ii} & \cdots & a_{in} \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & a_{nn} \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_i \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} b_1 \\ \vdots \\ b_i \\ \vdots \\ b_n \end{pmatrix}
$$
D'où la solution est
$$
\begin{cases} x_n = \frac{b_n}{a_n} \\ x_i = \frac{1}{a_{ii}} \left( b_i - \sum_{j=i+1}^n a_{ij} x_j \right) \end{cases}
$$
## 2) Résolution du système triangulaire

$$
\begin{array}{ll}
x_n \leftarrow \frac{b_n}{a_n} & \\
\text{pour } i = n-1 \text{ jusqu'à } 1 & \\
\quad \text{somme} \leftarrow 0 & \\
\text{pour } j = i+1 \text{ jusqu'à } n & \\
\quad \text{somme} \leftarrow \text{somme} + a_{ij}x_j & \\
\text{Fin pour} & \\
x_i \leftarrow \frac{b_i - \text{somme}}{a_{ii}} & \\
\text{Fin pour} &
\end{array}
$$

### 2.2.2.1 Gauss avec pivotation

* **Pivotation partielle**

Dans le cas où un des pivots est nul, on cherche un pivot non nul dans la même colonne.

Le pivot choisi est le plus grand en valeur absolu, il est appelé pivot maximal par colonne, celui-ci est trouvé on permute deux lignes, ce type de pivotation est appelée *pivotation partielle* (2)

Le pivot est choisi par la formule suivante :

$$ a_{rk}^{(k-1)} = \text{MAX} |a_{ik}^{(k-1)}| \quad i \in [k, n] \quad (2.2) $$

Exemple :

$$
\left\{
\begin{array}{l}
x + 3y + 4z = 50 \\
0x + 0y - 4z = 2 \\
0x + 7y - 2z = 31
\end{array}
\right.
\quad \text{On permute les lignes 2 et 3}
\qquad
\left\{
\begin{array}{l}
x + 3y + 4z = 50 \\
0x + 7y - 2z = 31 \\
0x + 0y - 4z = 2
\end{array}
\right.
$$

* **Pivotation totale**

Dans le cas de pivotation totale (3), le pivot choisi est le plus grand en valeur absolu dans toute matrice, il est donné par la formule suivante :

$$ a_{rm}^{(k-1)} = \text{MAX} |a_{ij}^{(k-1)}| \quad \begin{cases} k \le i \le n \\ k \le j \le n \end{cases} \quad (2.3) $$

Et on permute les colonnes *r* et *k* et les lignes *m* et *k*
Exemple 1 :

$$
\left\{
\begin{array}{l}
x + 3y + 4z = 50 \\
3x + 5y - 4z = 2 \\
4x + 77y - 2z = 31
\end{array}
\right.
\quad \text{On permute}
\quad
\left\{
\begin{array}{l}
4x + 77y - 2z = 31 \\
3x + 5y - 4z = 2 \\
x + 3y + 4z = 50
\end{array}
\right.
\quad \text{On permute la colonne 1 et 2}
\quad
\left\{
\begin{array}{l}
77y + 4x - 2z = 31 \\
5y + 3x - 4z = 2 \\
3y + 1x + 4z = 50
\end{array}
\right.
$$

Exemple 2 :

Résoudre le système suivant par la méthode de Gauss

$$
\text{pivot (1)}
\begin{bmatrix}
2x_1 + 4x_2 - 2x_3 &=& -6 \\
x_1 + 3x_2         &+& x_4 &=& 0 \\
3x_1 - x_2 + x_3 + 2x_4 &=& 8 \\
-x_2 + 2x_3 + x_4 &=& 6
\end{bmatrix}
$$
$$
\text{(2) = (2)-$a_{21}$/pivot (1)}
\begin{bmatrix}
2x_1 + 4x_2 - 2x_3 &=& -6 \\
x_1 + 3x_2         &+& x_4 &=& 0 \\
3x_1 - x_2 + x_3 + 2x_4 &=& 8 \\
-x_2 + 2x_3 + x_4 &=& 6
\end{bmatrix}
$$
$$
\text{(3) = (3)-$a_{31}$/pivot (1)}
\begin{bmatrix}
2x_1 + 4x_2 - 2x_3 &=& -6 \\
0 + x_2 + x_3 + x_4 &=& 3 \\
3x_1 - x_2 + x_3 + 2x_4 &=& 8 \\
-x_2 + 2x_3 + x_4 &=& 6
\end{bmatrix}
$$

2.2.3 Gauss Jordan

La méthode de Gauss-Jordan est une méthode très utilisée, elle agit sur les lignes d'une matrice en utilisant les mêmes opérations que celles de Gauss. Les opérations autorisées sont:

1. Échange de deux rangées.

2. Multipliez n'importe quelle ligne par une constante non nulle.

3. Remplacer une ligne par la somme de sur la ligne et un multiple constant d'une autre ligne.

aug.

On forme la matrice augmentée correspondante au système d'équations linéaires, après
application l'algorithme de gauss, on obtient la solution X ainsi que la matrice inverse

$$
A I b \rightarrow I A^{-1} X
$$
Exemple

$$
\text{Soit le système à résoudre :}
\begin{bmatrix}
1 & 3 & 3 \\
2 & 2 & 0 \\
3 & 3 & 6
\end{bmatrix}
\begin{pmatrix}
x_1 \\
x_2 \\
x_3
\end{pmatrix}
=
\begin{bmatrix}
0 \\
2 \\
11
\end{bmatrix}
$$

On forme tout d'abord la matrice $[A, b]$ :

$K=1 k=1$

$$
\text{Normalisation} \Rightarrow \begin{pmatrix} 1 & 3 & 3 & 0 \\ 2 & 2 & 0 & 2 \\ 3 & 3 & 6 & 11 \end{pmatrix} \quad \text{Réduction} \Rightarrow \begin{pmatrix} 1 & 3 & 3 & 0 \\ 0 & -4 & -6 & 2 \\ 0 & -6 & -3 & 11 \end{pmatrix}
$$

$K=2 k=2$

$$
\text{Normalisation} \Rightarrow \begin{pmatrix} 1 & 3 & 3 & 0 \\ 0 & 1 & 3/2 & -1/2 \\ 0 & -6 & 3 & 11 \end{pmatrix} \quad \text{Réduction} \Rightarrow \begin{pmatrix} 1 & 0 & -3/2 & 3/2 \\ 0 & 1 & 3/2 & -1/2 \\ 0 & 0 & 6 & 8 \end{pmatrix}
$$

$K=3 k=3$

$$
\text{Normalisation} \Rightarrow \begin{pmatrix} 1 & 0 & -3/2 & 3/2 \\ 0 & 1 & 3/2 & -1/2 \\ 0 & 0 & 1 & 4/3 \end{pmatrix} \quad \text{Réduction} \Rightarrow \begin{pmatrix} 1 & 0 & 0 & 7/2 \\ 0 & 1 & 0 & -5/2 \\ 0 & 0 & 1 & 4/3 \end{pmatrix}
$$

La solution est $x_i = a_{i,x+1}$, d'où : $x^* = (7/2 \ -5/2 \ 4/3)$

2.2.3.1 Inverse d'une matrice

Selon la méthode de Cramer, une matrice *A* de rang *n* n'est inversible que si son déterminant *Δ* est différent de zéro. Dans ce cas, le produit de *A* par la matrice inverse *A*⁻¹ donne la matrice unitaire *I*.

$$
A^{-1}A = A.A^{-1} = I \quad \text{où} \quad A I = A
$$

En appliquant la méthode de Cramer sur la matrice A, on peut déterminer A⁻¹.

Exemple :

$$
A = \begin{pmatrix} 1 & 3 & 3 \\ 2 & 2 & 0 \\ 3 & 2 & 6 \end{pmatrix} ; \quad I = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}
$$

On obtient en utilisant la méthode de $A^{-1} = \frac{1}{5} \begin{pmatrix} -2 & 2 & 1 \\ 2 & \frac{1}{2} & -1 \\ \frac{1}{3} & -\frac{7}{6} & \frac{2}{3} \end{pmatrix}$

Cramer :

Qui vérifie : $A^{-1}A = A.A^{-1} = I$

De même L’algorithme de Gauss-Jordan présenté au début de ce cours (méthode du pivot) opère aussi le passage de la matrice $C=[A,y]$ à la matrice $D=[I,X]$ où $X$ est la solution du système linéaire $A.X=y$ ; Soit $X=A^{-1}y$.

Après les opérations de l'algorithm e de Gauss-Jordan, on obtient : $D=A^{-1} \cdot C=A^{-1} \cdot [A,I]=[I,A^{-1}]$
Cette méthode, de calcul de l'inverse d'une matrice qui est résumée ci-dessous, permet de calculer $A^{-1}$
avec un nombre d'opérations nettement inférieur à celui de la méthode de Cramer.
**Transformation (A,I) ⇒ (I,A⁻¹)**

Pour $k = 1, 2, ..., n$, on a :

$$ \Rightarrow a_{k,j} = \frac{a_{k,j}}{a_{k,k}} $$

Pour $j = 2n,..., k$

$$ i = 1,2,...,k $$

Pour $j = 2n,..., k$

$$ i \neq j $$

$$ \Rightarrow a_{i,j} = a_{i,j} - a_{i,k} \cdot a_{k,j} $$

**Exemple :**

Soit la matrice $A = \begin{pmatrix} 1 & 3 & 3 \\ 2 & 2 & 0 \\ 3 & 2 & 6 \end{pmatrix}$. Calculer $A^{-1}$ par la méthode de Gauss Jordan.

$k=1$

$$ \text{Normalisation} \Rightarrow \begin{pmatrix} 1 & 3 & 3 & 1 & 0 & 0 \\ 2 & 2 & 0 & 0 & 1 & 0 \\ 3 & 2 & 6 & 0 & 0 & 1 \end{pmatrix}; \text{Réduction} \Rightarrow \begin{pmatrix} 1 & 3 & 3 & 1 & 0 & 0 \\ 0 & -4 & -6 & -2 & 1 & 0 \\ 0 & -7 & -3 & -3 & 0 & 1 \end{pmatrix} $$

$k=2$

$$ \text{Normalisation} \Rightarrow \begin{pmatrix} 1 & 3 & 3 & 1 & 0 & 0 \\ 0 & 1 & 3/2 & 1/2 & -1/4 & 0 \\ 0 & -7 & -3 & -3 & 0 & 1 \end{pmatrix}; \text{Réduction} \Rightarrow \begin{pmatrix} 1 & 0 & -3/2 & -1/2 & 3/4 & 0 \\ 0 & 1 & 3/2 & 1/2 & -1/4 & 0 \\ 0 & 0 & 15/2 & 1/2 & -7/4 & 1 \end{pmatrix} $$

$k=3$

$$ \text{Normalisation} \Rightarrow \begin{pmatrix} 1 & 0 & -3/2 & -1/2 & 3/4 & 0 \\ 0 & 1 & 3/2 & 1/2 & -1/4 & 0 \\ 0 & 0 & 1 & 1/15 & -7/30 & 2/15 \end{pmatrix}; \text{Réduction} \Rightarrow \begin{pmatrix} 1 & 0 & 0 & -2/5 & 2/5 & 1/5 \\ 0 & 1 & 0 & 2/5 & 1/10 & -1/5 \\ 0 & 0 & 1 & 1/15 & -7/30 & 2/15 \end{pmatrix} $$

Finalement, on vérifie que : $ \begin{pmatrix} -2 & 2 & 1 \\ 2 & 1/2 & -1 \\ 1/3 & -7/6 & 2/3 \end{pmatrix} A = I $

### 2.2.3 Factorisation LU

Il est très facile de résoudre un système triangulaire comme celui du Gauss que celui ordinaire de type $Ax=b$, donc on décompose $A$ sous forme LU avec $L$ matrice triangulaire inférieur et $U$ matrice triangulaire supérieure

$$ A = LU $$

$$ Ax = b \Leftrightarrow \begin{cases} (1) & Ly = b \\ (2) & Ux = y \end{cases} $$

$$ \ell_{i,k} = \frac{a_{ik}}{a_{kk}} = -m_{i,k} $$

<figure><img src="image_45.png" /></figure>

$$ M^{(k)} = \begin{pmatrix} 1 & \cdots & 0 & \cdots & 0 \\ 0 & \cdots & \cdots & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \ddots & -\ell_{k+1,k} & \ddots & \vdots \\ 0 & \cdots & -\ell_{n,k} & 0 & 1 \end{pmatrix} $$
On multiplions la matrice A par une matrice $M^{(k)}$

$$
\begin{align*}
A^{(k+1)} &= M^{(k)} A^{(k)} & A^{(l)} &= A \quad \text{et} \quad A^{(n)} &= U \\
U &= M^{(n-1)} \dots M^{(k)} \dots M^{(l)} A = M A \\
A &= M^{-1} U = LU \\
\text{donc} \quad L &= M^{-1}
\end{align*}
$$

Les matrices élémentaires $M^{(k)}$ sont inversibles et leurs inverses sont les matrices $L^{(k)}$ triangulaires inférieures telles que :

$$
\begin{align*}
L^{(k)} &= \begin{cases}
l_{ij} = 0 & \text{sauf } i = 1, n \\
l_{ii} = 1 & \text{sauf } i = k+1, n
\end{cases} \\
L^{(k)} &= I - (M^{(k)} - I) \\
M^{(k)} &= \begin{pmatrix}
1 & \cdots & 0 & \cdots & 0 \\
0 & \ddots & \ddots & \ddots & \vdots \\
0 & 0 & 1 & \cdots & 0 \\
\vdots & \ddots & \ddots & \ddots & \vdots \\
0 & \cdots & -\ell_{k+L,k} & \cdots & \vdots \\
0 & \cdots & -\ell_{n,k} & 0 & 1
\end{pmatrix} \\
L &= L^{(n=1)} \dots L^{(k)} \dots L^{(1)}
\end{align*}
$$

Algorithme LU

pour $k=1$ jusqu'à $n-1$
pivot $\leftarrow a_{kk}$ (* stratégie de pivot *)
si pivot $\neq 0$ alors
  $\ell_{kk} \leftarrow 1$
pour $i=k+1$ jusqu'à $n$
  $\ell_{ik} \leftarrow \frac{a_{ik}}{\text{pivot}}$
pour $j=k+1$ jusqu'à $n$
  $a_{ij} \leftarrow a_{ij} - \ell_{ik} a_{kj}$
fait
fait
sinon érreur
fait

2.3 Les méthodes itératives

Les méthodes itératives ou indirectes sont des algorithmes qui permettent de fournir des solutions approchées si elles existent en un nombre **infini** d'opérations. Ex: méthode de Jacobi, Gauss-Seidel....
### 2.3.1 La méthode de Jacobi (4)

Soit $D$ la diagonale de la matrice $A$, et $G$ le reste :

$$A = D + G$$

$$D = \begin{pmatrix} a_{11} & 0 & 0 & 0 & 0 \\ 0 & \ddots & 0 & 0 & 0 \\ 0 & 0 & a_{ii} & 0 & 0 \\ 0 & 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & 0 & a_{nn} \end{pmatrix} \quad G = \begin{pmatrix} 0 & a_{12} & a_{1i} & \cdots & a_{1n} \\ a_{21} & 0 & a_{i-1,j} & \ddots & \vdots \\ a_{i1} & a_{i,j-1} & 0 & a_{i-1,j} & a_{i,n} \\ \vdots & \ddots & a_{i,i+1} & 0 & a_{n-1,i} \\ a_{n1} & \cdots & a_{ni} & a_{n,i-1} & 0 \end{pmatrix}$$

$$Dx^{nov} = b - Gx^{old} \Leftrightarrow x^{nov} = D^{-1}(b - Gx^{old})$$

**Théorème de convergence :**

Si $A$ est une matrice à diagonale strictement dominante, alors la méthode de Jacobi converge

**Démonstration**

Jacobi :

$$x^{k+1} = (D)^{-1}(b - (E + F)x^k)$$

$$x^{k+1} = Cx^k + d \quad \text{avec} \quad C = D^{-1}(E + F), \quad d = D^{-1}b$$

$$\|C\|_{\infty} = \|D^{-1}(E + F)\|_{\infty} = \max_{i=1,\dots,n} \left( \frac{1}{|a_{ii}|} \sum_{j=1}^{n} |a_{ij}| \right) < 1$$

$$Ax = b \Leftrightarrow \begin{cases} 2x_1 + 4x_2 - 2x_3 & = -6 \\ x_1 + 3x_2 & + x_4 = 0 \\ 3x_1 - x_2 + x_3 + 2x_4 & = 8 \\ - x_2 + 2x_3 & + x_4 = 6 \end{cases}$$

soit $(\tilde{x}_1, \tilde{x}_2, \tilde{x}_3, \tilde{x}_4)$ une solution approchée

imaginons que $\tilde{A}\tilde{x} = \tilde{b}$ avec par exemple $\text{dist}(A, \tilde{A}) < \varepsilon$

$$\text{si on essayait:} \quad \begin{cases} x_1 = \frac{-6 - 4\tilde{x}_2 + 2\tilde{x}_3}{2} \\ x_2 = \frac{0 - \tilde{x}_1 - \tilde{x}_4}{3} \\ x_3 = \frac{8 - 3\tilde{x}_1 + \tilde{x}_2 - 2\tilde{x}_4}{1} \\ x_4 = \frac{6 + \tilde{x}_2 - 2\tilde{x}_3}{1} \end{cases} \quad \text{soit} \quad x_i = \frac{b_i - \sum_{j=1, j \neq i}^{n} a_{ij} \tilde{x}_j}{a_{ii}}$$
tant que $dist(Ax_{new}, b) > \varepsilon$ (i.e. $10^{-12}$)

$$x_i^{new} = \frac{b_i - \sum_{j=1, j \neq i}^{n} a_{ij} x_j^{old}}{a_{ii}}$$

fin

### 2.3.2 La méthode de Gauss Seidel (5)

Soit $E$ la triangulaire inférieure et $F$ la supérieure de la matrice $A$ :

$$A = D + E + F$$

$$E = \begin{pmatrix} 0 & 0 & 0 & \cdots & 0 \\ a_{21} & 0 & 0 & \cdots & \vdots \\ a_{i1} & a_{i,i-1} & 0 & 0 & 0 \\ \vdots & \ddots & a_{i,j-1} & 0 & 0 \\ a_{n1} & \cdots & a_{n,i} & a_{n,n-1} & 0 \end{pmatrix} \quad F = \begin{pmatrix} 0 & a_{12} & a_{1i} & \cdots & a_{1n} \\ 0 & 0 & a_{i-1,i} & \cdots & \vdots \\ 0 & 0 & 0 & a_{i-1,i} & a_{i,n} \\ \vdots & \ddots & 0 & 0 & a_{n-1,n} \\ 0 & \cdots & 0 & 0 & 0 \end{pmatrix}$$

$$(D + E)x^{new} = b - Fx^{old} \Leftrightarrow x^{new} = (D + E)^{-1}(b - Fx^{old})$$

$$(D + E)x^{new} = (b - Fx^{old}) \Leftrightarrow \begin{cases} M = D + E \\ N = -F \end{cases} \qquad (2.5)$$

Exemple

$$Ax = b \Leftrightarrow \begin{cases} 2x_1 + 4x_2 - 2x_3 = -6 \\ x_1 + 3x_2 + x_4 = 0 \\ 3x_1 - x_2 + x_3 + 2x_4 = 8 \\ -x_2 + 2x_3 + x_4 = 6 \end{cases}$$

$$\begin{cases} x_1 = \frac{-6 - 4\tilde{x}_2 + 2\tilde{x}_3}{2} \\ x_2 = \frac{0 - x_1 - \tilde{x}_4}{3} \\ x_3 = \frac{8 - 3x_1 + x_2 - 2\tilde{x}_4}{1} \\ x_4 = \frac{6 + x_2 - 2x_3}{1} \end{cases} \quad \text{soit } x_i = \frac{b_i - \sum_{j=1}^{i-1} a_{ij} x_j - \sum_{j=i+1}^{n} a_{ij} \tilde{x}_j}{a_{ii}}$$

tant que $dist(Ax_{new}, b) > \varepsilon$ (i.e. $10^{-12}$)

$$x_j^{new} = \frac{b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{new} - \sum_{j=i+1}^{n} a_{ij} x_j^{old}}{a_{ii}}$$

fin
Lorsqu'une inconnue est utilisée, c'est automatiquement la plus récente valeur qui est calculée. Ceci assure une convergence des calculs bien plus rapide que la méthode de JACOBI. On arrête les calculs lorsque les valeurs successives de $x_j$ sont suffisamment voisines. Pour cela, on peut utiliser,

* soit le critère de **Convergence absolue** (6) :

$$ \left| x_j^{(k+1)} - x_j^{(k)} \right| \le \varepsilon \qquad (2.6) $$

* soit le critère de **Convergence relative** (7) :

$$ \left| \frac{x_j^{(k+1)} - x_j^{(k)}}{x_j^{(k+1)}} \right| \le \varepsilon \qquad (2.7) $$

Pour les systèmes où les matrices qui sont de rang élevé, il n'est pas commode de faire le test de convergence sur chaque inconnue $x_j$.

Dans ce cas, on fait le test soit seulement sur certaines inconnues que l'on choisit, soit les quantités suivantes :

$$ \sum_{j=1}^{n} |x_j^{(k+1)} - x_j^{(k)}| \text{ ou } \left( \sum_{j=1}^{n} |x_j^{(k+1)} - x_j^{(k)}|^2 \right)^{1/2} \text{ ou } \sum_{j=1}^{n} \left| \frac{x_j^{(k+1)} - x_j^{(k)}}{x_j^{(k+1)}} \right| \text{ ou } \left( \sum_{j=1}^{n} \left| \frac{x_j^{(k+1)} - x_j^{(k)}}{x_j^{(k+1)}} \right|^2 \right)^{1/2} $$

La convergence du procédé ne dépend pas du choix des valeurs initiales $x_j^0$, mais seulement des valeurs des coefficients.

On montre que la convergence est assurée si on a, pour chaque valeur de $i$ (c'est à dire pour chaque ligne), la relation est vérifiée.

$$ |a_{ii}| \ge \sum_{j=1}^{n} |a_{ij}| \qquad (2.8) $$

Autrement dit, il y a convergence si chaque élément diagonal est supérieur ou égal, en module, à la somme des modules des autres éléments de sa ligne (la matrice A soit DFD (8)).

## 2.4 Quelque exemples élémentaires

*Exemple 1 :* Voici un aperçu d'exécution pour le système suivant par la méthode de Gauss

$$ Ax = b \Leftrightarrow \left\{ \begin{array}{l} \begin{array}{cccc} 4x_1 & -2x_2 & 2x_3 & = -2 \\ 4 x_1 & -3x_2 & -2x_3 & = -11 \\ 2x_1 & +3 x_2 & - x_3 & = -1 \end{array} \\ \begin{array}{l} 4 \ -2 \ 2 \\ 4 \ -3 \ -2 \\ 2 \ 3 \ -1 \end{array} \quad \left| \begin{array}{c} -2 \\ -11 \\ -1 \end{array} \right. \end{array} \right. $$

En appliquant l'algorithme de triangularisation de gauss on trouve le système suivant

<figure><img src="image_46.png" /></figure>
Après substitution on trouve la solution suivante

$$
X = (-1, 1, 2)
$$

$$
\text{Le déterminant est } \det(A) = (-1^0) \prod_{i=1}^{n} \text{pivot}_i = 4 \cdot -1 \cdot -18 = 72
$$

*Exemple 2* : Voici un aperçu d'exécution pour un autre système par la méthode de Gauss

$$
Ax = b \iff \left\{
\begin{array}{l@{\quad}c@{\quad}l@{\quad}l@{\quad}l}
5x_1 & + 2x_2 & - x_3 & = & 5 \\
x_1 & + 6x_2 & - 3x_3 & = & 4 \\
2x_1 & + x_2 & + 4x_3 & = & 7
\end{array}
\right.
\\[2ex]
\begin{array}{cccc|c}
5 & 2 & -1 & & 6 \\
1 & 6 & -3 & & 4 \\
2 & 1 & 4 & & 7
\end{array}
$$

En appliquant l'algorithme de triangularisation de gauss on trouve le système suivant :

<figure><img src="image_47.png" /></figure>

Après substitution on trouve la solution suivante

$$
X = (1, 1, 1)
$$

$$
\text{Le déterminant est } \det(A) = (-1^0) \prod_{i=1}^{n} \text{pivot}_i = 121
$$

*Exemple 3* : Voici un aperçu d'exécution pour le système suivant par la méthode de Gauss Seidel

$$
\begin{align*}
Ax = b \iff \left\{
\begin{array}{l}
2x_1 + x_2 - x_3 = 13 \\
x_1 - 5x_2 - x_3 = 8 \\
4x_1 + 2x_2 + 7x_3 = 16
\end{array}
\right.
\\[1.5ex]
2X1 + X2 \quad -X3 = 13 \quad \begin{array}{l} X1 = (13 - X2 + X3)/2 \\ X2 = (8 - X1 + X3)/5 \end{array} \\
\\
X1 - 5X2 - X3 = 8 \quad \rightarrow \quad 4X1 + 0X2 + 7X3 = 16 \quad \begin{array}{l} X3 = (16 - 4X1)/7 \end{array}
\end{align*}
$$

Après 3 itérations et $x^{(0)} = (1,0,0)^T$

$$
\text{On trouve la solution suivante } x^{(3)} = (6.0139050, -0.16744637, -1.1508029)^T
$$

*Exemple 4* : Voici un aperçu d'exécution pour le système suivant par la méthode de Gauss Seidel après la vérification de la convergence

Soit le système $Ax = b$
$$
\begin{vmatrix}
2 & 0 & 7 \\
-2 & 5 & 0 \\
6 & -2 & 2
\end{vmatrix}
*
\begin{vmatrix}
x1 \\
x2 \\
x3
\end{vmatrix}
=
\begin{vmatrix}
16 \\
23 \\
0
\end{vmatrix}
$$

En algèbre linéaire, une matrice carrée à coefficients réels ou complexes est dite à **diagonale dominante** lorsque le module de chaque terme diagonal est supérieur ou égal à la somme des modules des autres termes de sa ligne.

$$
\begin{array}{l}
A = (a_{ij}), \forall i, 1 \le i \le n \\
\qquad \forall j, 1 \le j \le m
\end{array}
$$

on a alors

$$
\forall i \in [1,n], |a_{ii}| > \sum_{j=1}^{n} |a_{ij}|
$$

On vérifier la formule pour les trois lignes :

$$
\begin{array}{lcl}
|2| < |0| + |7| & \text{pas bon} & \\
|5| > |-2|+|0| & \text{bon} & \\
|2| < |6|+|-2| & \text{pas bon} &
\end{array}
$$

Donc A n'est pas dominante

Pour avoir A strictement diagonale dominante il faut arranger A, donc si on permute la 1 colonne avec
la 3 colonne et on change la position des Xi, on obtient le système suivant

$$
\begin{vmatrix}
7 & 0 & 2 \\
0 & 5 & -2 \\
2 & -2 & 6
\end{vmatrix}
*
\begin{vmatrix}
x3 \\
x2 \\
x1
\end{vmatrix}
=
\begin{vmatrix}
16 \\
23 \\
0
\end{vmatrix}
$$

$$
\begin{array}{lcl}
|7| > |0| + |2| & \text{bon} & \\
|5| > |0| + |-2| & \text{bon} & \\
|6| > |2| + |-2| & \text{bon} &
\end{array}
$$

Une fois notre système set DFD, on exécute méthode de Gauss Seidel avec 5 itérations et comme
solution initiale $x^{(0)} = (1,0,0)^T$, on trouve la solution suivante

$$
X3=2, X2=5, X1=1
$$

Donc la solution est $x^{(5)} = (1,5,2)^T$

*Exemple 5* : Voici un aperçu d'exécution pour le système suivant par la méthode de Gauss-Jordan

$$
x_1 + 2x_2 + 3x_3 = 9
$$

$$
2x_1 - x_2 + x_3 = 8
$$

$$
3x_1 - x_3 = 3
$$

Etape 1 Former la matrice augmentée correspondant au système d'équations linéaires

$$
\begin{bmatrix}
1 & 2 & 3 & 9 \\
2 & -1 & 1 & 8 \\
3 & 0 & -1 & 3
\end{bmatrix} .
$$
Étape 2: Transformer la matrice augmentée en matrice sous forme d'échelons réduits par des opérations de lignes élémentaires.

$$ \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 3 \end{bmatrix} $$

Étape 3: Résoudre le système linéaire correspondant à la matrice en forme d'échelon de ligne réduite. La solution (s) sont également pour le système d'équations linéaires à l'étape 1.

$$ x_1 = 2, x_2 = -1, x_3 = 3 $$

Exercice

Est ce que le système linéaire $A x = b$ suivant converge et pour quoi ?

$$ A = \begin{pmatrix} 10 & 2 & 3 \\ 2 & 12 & 1 \\ 1 & 4 & 10 \end{pmatrix}, \quad x = \begin{pmatrix} x \\ y \\ z \end{pmatrix}, \quad b = \begin{pmatrix} -1 \\ 2 \\ 3 \end{pmatrix} $$

- Donner les matrices D, U et L qui correspondent à la décomposition $A = D - U - L$ de la méthode de Jacobi

- Résoudre le système linéaire $A x = b$ avec $x^{(0)} = (0, 0, 0)$ en 4 itérations.

FIN