Mathématique : Archives

D	L	M	M	J	V	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

« 2010-01-08 | Page d'accueil | 2010-01-30 »

21/01/2010

Liens vers des sites de mathématiques

Academy of Sciences of the Czech Republic; American Institute of Mathematics; Argonne National Lab, Mathematics and Computer Science; AT&T Bell Laboratories Research; Australian CSIRO Math/Stat; Australian Mathematical Sciences Institute (AMSI); Basic Research Institute in the Mathematical Sciences; Budapest Semesters in Mathematics Program; CMU Center for Nonlinear Analysis; Center for Advanced Studies, Research and Development in Sardinia Applied Math Group; Center for Applied Mathematics and Theoretical Physics (U Maribor); CCM, The Center for Coputational Mathematics, University of Colorado, Denver; Center for Dynamical Systems and Nonlinear Studies; Centre for Engineering and Industrial Mathematics (U Wollongong); Centre for Experimental & Constructive Mathematics; Center for Gravitational Physics and Geometry; Centre Emile Borel; Centre for Industrial and Applied Mathematics (U South Australia); Centre for Innovation in Mathematics Teaching; Centro Internazionale Matematico Estivo; Centre International de Mathématiques Pures et Appliquées; Centre International de Recontres Mathématiques (CIRM); Centro de Investigación en Matemáticas A.C (Mexico); Centre de Mathématiques (École Polytechnique); Centre de Mathematiques Appliquees (École des Mines de Paris); Center for Mathematical Analysis, Geometry, and Dynamical Systems; Center for the Mathematical Sciences (UWisconsin); Centre de Recerca Matemàtica (Barcelona); Centre de recherches mathématiques (UMontréal); Center for Research in Scientific Computation (at NCSU); Center for Statistical and Mathematical Computing; Centrum voor Wiskunde en Informatica (CWI); Claremont Research Institute of Applied Mathematical Sciences (CRIAMS); The Clay Mathematics Institute (CMI); Collège de France, Sciences Mathématiques, Physiques et Naturelles; Computer Algebra Information Network; Cornell Center for Applied Mathematics; Courant Institute of NYU; CTI Centre for Mathematics and Statistics; Diffiety Instute of the Russian Academy of Natural Sciences; DIMACS; Euler Institute fot Discrete Mathematics and its Applications; The Euler International Mathematical Institute; Erwin Schrodinger Institute of Mathematical Physics; Euromath Center; EURHomogenization; The Fields Institute for Research in Mathematical Sciences; Fuzzy Logic Laboratory Linz; Geometry Center (UMinn); Groupe Fractales (INRIA); Indian Statistical Institute; Industrial Mathematics Institute (Linz); Institut de Mathématiques de Bordeaux; Institut des Hautes Etudes Scientifiques IHES; Institute for Advanced Study; Institute of Applied and Computational Mathematics; Institute for Computational Fluid Dynamics; Institute for Computer Applications in Science and Engineering; Institute of Cybernetics, Applied Math. Dept. (Estonia); Institute of Mathematics and Geometry (Faculty of Civil Engineering and Architecture) University of Innsbruck, Austria; Institut für Dynamische Systeme (Bremen); Institute for Experimental Mathematics (Essen); Institute for Mathematical Research (FIM, ETH-Zuerich); Institute for Studies in Theoretical Physics and Mathematics (IPM); Institut Fourier, Université Joseph Fourier; Institut Henri Poincare; Institute of Information Theory and Automation (Czech Academy of Sciences); Institute of Mathematical Sciences (India); Institut of Mathematics, University of Liege; Institut d'Informatique et de Mathématiques Appliquées de Grenoble; Institute for Mathematics and its Applications; Institut de Mathématiques Appliquées; Institute of Mathematics and Computer Science in Medicine (IMDM); Institut de Mathématique de Jussieu (Paris VI et Paris VII); Institute of Mathematics and Informatics (Bulgarian Academy of Sciences); Institute of Mathematics and Informatics Lithuania; Institute of Mathematics, Physics and Mechanics (Ljubljana); Institute of Mathematics of the Polish Academy of Sciences; Instituto de Matemática Pura e Aplicada (Brazil); Instituto de Matematicas y Estadistica (Uruguay); Institute of Mathematical Sciences Hong Kong; Instituto Nacional de Pesquisas Espaciais Brazil (applied math); Institute of Numerical Mathematics (RAS); Institute for Pure and Applied Mathematics at UCLA; Institut de Recherche Mathématique Avancée (IRMA); Institut de Recherche Mathematique de Rennes (IRMAR); Institut des sciences mathematiques (ISM); Institute of Statistical Mathematics (Japan); International Centre of Excellence for Education in Mathematics (ICE-EM); International Centre for Mathematical Sciences, Edinburgh; International Centre for Theoretical Physics; Isaac Newton Institute for Mathematical Sciences; Konrad-Zuse-Zentrum (Berlin); Laboratory for Computer Aided Mathematics (U Helsinki); Manchester Centre for Computational Mathematics; Mathematical Analysis Research Group; Mathematical Sciences Research Institute; Mathematics Institute of the Romanian Academy (IMAR); Mathematisches Forschungsinstitut Oberwolfach; Max-Planck Institut f"ur Mathematik, Bonn; Max-Planck Institut f"ur Mathematik in den Naturwissenschaften, Leipzig; Mittag-Leffler Institute; Pacific Institute for the mathematical sciences; pLab Project (Salzburg); Programme de Recherches Coordonnées, Mathématiques et Informatique; Research Centre of Applied Mathematics CIRAM (Bologna); Research Institute for Mathematical Sciences RIMS (Kyoto); Research Institute for Symbolic Computation (RISC-Linz); Steklov Institute of Mathematics, Russian Academy of Sciences; Steklov Mathematical Institute; Systems Analysis Laboratory (Helsinki UT); Tata Institute of Fundamental Research (India); University of Graz Institute of Mathematics; Unión Matemática Argentina; UMass Center for Geometry Analysis Numerics and Graphics; University of Minnesota Geometry Center; University of Nevada, Reno Mathematics Center; Virtual Institute of Mathematical Sciences; Visual Math Institute; Weierstraß-Institute for Applied Analysis and Stochastics (WIAS)
Magnet High Schools in Mathematics: Bronx High School of Science; Central Virginia Governor's School for Science and Technology; Illinois Mathematics and Science Academy; Massachusetts Academy of Mathematics and Science; Mississippi School for Mathematics and Science; Montgomery Blair High School; New Horizons Governor's School (VA); North Carolina School of Science and Mathematics; Oklahoma School of Science and Mathematics; Roanoke Valley Governor's School for Science and Technology (VA); Thomas Jefferson High School for Science and Technology

Les flottants au format double

suivant: Opérations sur les flottants monter: Les réels précédent: Virgule fixe et flottante. Index

Les flottants au format `double`

Cette section développe les notions de la section précédente pour les flottants machine, utilisables dans les langage de programmation usuels, elle peut être omise. La représentation d'un double en mémoire se compose de 3 parties : le bit de signe s = ±1 sur 1 bit, la mantisse M

[0, 2⁵²[ sur 52 bits, et l'exposant e

[0, 2¹¹[ sur 11 bits. Pour les nombres ``normaux'', l'exposant est en fait compris entre 1 et 2¹¹ - 2, le nombre représenté est le rationnel

(1 + $displaystyle {frac{{M}}{{2^{52}}}}$ )2^e+1-2¹⁰

Pour écrire un nombre sous cette forme, il faut d'abord chercher par quel multiple de 2 il faut le diviser pour obtenir un réel r dans [1, 2[, ce qui permet de déterminer l'exposant e. Ensuite on écrit la représentation en base 2 de r - 1

[0, 1[. Exemples :

-2
Signe négatif. Il faut diviser sa valeur absolue 2 par 2¹ pour être entre 1 et 2 dont e + 1 - 2¹⁰ = 1, l'exposant est e = 2¹⁰. On a alors r = 1, r - 1 = 0. Représentation
1 10000000000 00000000...0000
1.5=3/2
Signe positif, compris entre 1 et 2 dont l'exposant vérifie e + 1 - 2¹⁰ = 0 soit e = 2¹⁰ -1 = 2⁹ +2⁸ +2⁷ +2⁶ +2⁵ +2⁴ +2³ +2² +2¹ +2⁰. On a r - 1 = 1/2 = 2^-1. D'où la représentation
0 01111111111 10000000...0000
6.4=32/5
Positif. Il faut le diviser par 2² pour avoir 8/5 [1, 2[ donc e + 1 - 2¹⁰ = 2 soit e = 2¹⁰ + 1. Ensuite r = 3/5 qu'il faut écrire en base 2 (cf. section précédente), on écrit donc les 52 premiers éléments du développement avec une règle d'arrondi du dernier bit au nombre le plus proche. Ici le bit suivant le dernier 1001 est un 1, on arrondit donc à 1010. D'où la représentation
0 1000000001 100110011001...10011010

On observe que la représentation en base 2 de 6.4 a du être arrondie (car elle est infinie en base 2) bien qu'elle soit exacte (finie) en base 10. Seuls les entiers et les rationnels dont le dénominateur est une puissance de 2 peuvent être représentés exactement. Ceci entraine des résultats qui peuvent surprendre comme par exemple le fait que 0.3 - 3*0.1 n'est pas nul.

Des représentations spéciales (avec e = 0 ou e = 2¹¹ - 1) ont été introduites pour représenter ± (pour les flottants plus grands en valeur absolue que le plus grand flottant représentable), et pour représenter les nombres non nuls plus petits que le plus petit flottant représentable de la manière exposée ci-dessus (on parle de flottants dénormalisés), ainsi que le nombre NaN (Not a Number) lorsqu'une opération a un résultat indéfini (par exemple 0/0).

suivant: Opérations sur les flottants monter: Les réels précédent: Virgule fixe et flottante. Index

Retour à la page principale de mat249

Source : http://www-fourier.ujf-grenoble.fr/~parisse/mat249/mat249...

Source :

Séries entières

suivant: Série alternée monter: Développement de Taylor, séries précédent: La fonction exponentielle Index

Séries entières.

Les séries de type prendre la limite lorsque n tend vers l'infini du développement de Taylor en x=0 sont de la forme

$displaystyle sum_{{n=0}}^{infty}$ a_nxⁿ : = $displaystyle lim_{{ k rightarrow +infty}}^{}$ $displaystyle sum_{{n=0}}^{k}$ a_nxⁿ, a_n = $displaystyle {frac{{f^{[n]}(0)}}{{n!}}}$

On peut s'intéresser plus générallement à $sum_{{n=0}}^{infty}$ a_nxⁿ lorsque a_n est un complexe quelconque, c'est ce qu'on appelle une série entière, on peut aussi les voir comme des polynômes généralisés.

S'il existe un point x₀ tel que | a_nx₀ⁿ| est borné (ce sera le cas en particulier si la série converge en x₀), alors

| a_nxⁿ| = | a_nx₀ⁿ|| $displaystyle {frac{{x}}{{x_0}}}$ |ⁿ

M| $displaystyle {frac{{x}}{{x_0}}}$ |ⁿ

la série converge donc en x si | x| < | x₀| et on peut majorer le reste de la série au rang n par

| R_n|

M $displaystyle {frac{{ vertfrac{x}{x_0}vert^n}}{{1-vertfrac{x}{x_0}vert}}}$

la vitesse de convergence est donc du même type que pour le théorème du point fixe (le nombre de termes à calculer pour trouver une valeur approchée avec k décimales dépend linéairement k, les constantes sont d'autant plus grandes que | x| est grand).

Théorème 5 S'il existe un rang n₀, un réel M > 0 et un complexe x₀ tels que pour n > n₀, on ait :

| a_nx₀|ⁿ

alors la série converge pour | x| < | x₀| et pour n

n₀, on a :

| R_n|

M $displaystyle {frac{{ vertfrac{x}{x_0}vert^n}}{{1-vertfrac{x}{x_0}vert}}}$

(3)

On en déduit qu'il existe un réel positif R 0 éventuellement égal à + tel que la série converge (la limite de la somme jusqu'à l'infini existe) lorsque | x| < R et n'existe pas lorsque | x| > R, ce réel est appelérayon de convergence de la série. Par exemple ce rayon vaut + pour l'exponentielle, le sinus ou le cosinus. Il est égal à 1 pour la série géométrique xⁿ (car elle diverge si | x| > 1 et converge si | x| < 1). On ne peut pas dire ce qui se passe génériquement lorsqu'on est à la limite, c'est-à-dire lorsque | x| = R (si R + ). Mais cela n'a en fait pas trop d'importance en pratique car même si la série converge, elle converge souvent trop lentement pour donner de bonnes approximations. En fait, la vitesse de convergence d'une série entière de rayon R + est en gros la même que celle d'une série géométrique de raison | x|/R.

Lorsque 2 séries ont un rayon de convergence non nul, alors on peut effectuer leur somme, leur produit comme des polynômes et la série somme/produit a un rayon de convergence au moins égal au plus petit des 2 rayons de convergence des arguments. On peut inverser une série entière non nulle en 0 en appliquant

(1 + x)^-1 = 1 - x + x² - x³ + ...

et on obtient une série entière de rayon de convergence non nul. On peut aussi composer deux séries entières g et f en gof (avec les règles de calcul de composition des polynômes) si f (0) = 0. On peut enfin dériver et intégrer une série entière terme à terme dans son rayon de convergence.

On dit qu'une fonction est développable en série entière en 0 si elle est égale à son développement de Taylor en 0 sommé jusqu'en l'infini dans un disque de centre 0 et de rayon non nul. Les fonctions exponentielle, sinus, cosinus sont donc développables en série entière en 0. La fonction tangente également car le dénominateur cosinus est non nul en 0, mais son rayon de convergence n'est pas l'infini et le calcul des a_n est assez complexe. La fonction (1 + x) est développable en séries entières pour tout avec un rayon de convergence 1 (ou l'infini pour entier positif).

(1 + x) = 1 +

x + $displaystyle {frac{{alpha (alpha-1)}}{{2!}}}$ x² + ... + $displaystyle {frac{{alpha (alpha-1) ... (alpha -n +1)}}{{n!}}}$ xⁿ + ...

Pour

= - 1, c'est la série géométrique de raison - x, en effet si | x| < 1 :

$displaystyle sum_{{n=0}}^{k}$ (- x)ⁿ = $displaystyle {frac{{1-(-x)^{k+1}}}{{1+x}}}$ $displaystyle rightarrow_{{krightarrow infty}}^{}$ $displaystyle {frac{{1}}{{1+x}}}$

En intégrant par rapport à x, on obtient que ln(1 + x) est développable en série entière en 0 de rayon de convergence 1 et

ln(1 + x) = $displaystyle sum_{{n=0}}^{infty}$ $displaystyle {frac{{(-x)^{n+1}}}{{n+1}}}$

On peut calculer de manière analogue le développement en série entière de arctan(x) en iintégrant celui de 1/(1 + x²), de même pour arccos(x) et arcsin(x) en intégrant celui de (1 - x²)^-1/2.

arctan(x) = $displaystyle sum_{{n=0}}^{infty}$ (- 1)ⁿ $displaystyle {frac{{x^{2n+1}}}{{2n+1}}}$ ,

On peut donc calculer ln, arctan, ... par ces formules, mais il faut répondre à la question où arrête-t-on la somme pour obtenir une précision donnée? Dans le cas de ln(1 + x), on pourrait répondre comme avec l'exponentielle en majorant la dérivée n + 1-ième, mais ce n'est plus faisable pour arctan, arcsin, arccos. On va donner un autre critère qui ne nécessite pas de calculer cette dérivée mais utilise l'alternance des signes dans la somme.

suivant: Série alternée monter: Développement de Taylor, séries précédent: La fonction exponentielle Index

Retour à la page principale de mat249

Source : http://www-fourier.ujf-grenoble.fr/~parisse/mat249/mat249...

Index - fourier.ujf-grenoble.fr

suivant: À propos de ce monter: Mat 249 précédent: Quelques références

Index

atan: Séries entières.
Bezout: Arithmétique des polynomes: Bézout
bit: Les flottants au format
complexe: Types composés.
contractante: Le point fixe
convexe: La méthode de Newton.
cos: La fonction exponentielle
determinant: Déterminant
diagonalisation: Réduction exacte des endomorphismes
division euclidienne: Entiers courts et longs
double: Les flottants au format
erreur: Erreur absolue, relative et | Erreurs d'arrondis du pivot
exp: La fonction exponentielle
exposant: Les flottants au format
expression: Types composés.
factorisation: Multiplicité des racines. | Factorisation dans . | Calcul approché des racines | Factorisation dans | Factorisation exacte
flottant: Les flottants au format
fonction: Types composés.
Gauss: Le pivot de Gauss
integration: Intégration numérique
interpolation: Approximation polynomiale
inverse: Inverse
iterations inverses: Itérations inverses
ker: Noyau
lagrange: Approximation polynomiale | Approximation polynomiale
liste: Types composés.
ln: La fonction logarithme
LU: La méthode de factorisation
mantisse: Les flottants au format
matrice: Types composés.
multiplicite: Multiplicité des racines.
Newton: La méthode de Newton. | La méthode de Newton.
Newton-Cotes: Newton-Cotes
noyau: Noyau
ordre: Ordre d'une méthode
pivot: Le pivot de Gauss
point fixe: Le point fixe
point milieu: Les rectangles et les
polynome: Types composés.
polynome caracteristique: Polynome caractéristique
polynome minimal: Polynome minimal
puissance: Méthode de la puissance
quadrature: Intégration numérique
racine: Multiplicité des racines. | Calcul approché des racines
racines rationnelles: Factorisation exacte
rationnel: Entiers courts et longs
rectangle: Les rectangles et les
reduction: Réduction sous forme échelonnée
rref: Réduction sous forme échelonnée
sequence: Types composés.
serie alternee: Série alternée
serie entiere: Séries entières.
Simpson: Simpson
sin: La fonction exponentielle
squarefree: Multiplicité des racines.
Sturm: Factorisation dans
symbole: Types composés.
Taylor: Développement de Taylor, séries
trapeze: Les rectangles et les
vecteur: Types composés.; Source :; http://www-fourier.ujf-grenoble.fr/~parisse/mat249/mat249...

Erreur absolue, relative et propagation des erreurs

suivant: Types composés. monter: Les réels précédent: Erreurs Index

Erreur absolue, relative et propagation des erreurs.

On a vu précédemment que pour représenter un réel, on devait l'arrondir, ce qui introduit une erreur même si le réel est connu exactement (par exemple 1/10). Voyons comment se propagent les erreurs dans les opérations arithmétiques de base : on distingue l'addition, la multiplication et l'inversion. La soustraction se ramène à l'addition car le calcul de l'opposé n'introduit aucune erreur nouvelle. Pour l'addition, si |x - x₀|

$varepsilon_{0}^{}$ et si | y - y₀|

$varepsilon_{1}^{}$ alors par l'inégalité triangulaire ( | a + b|

| a| + | b|), on a :

|(x + y) - (x₀ + y₀)|

| x - x₀| + | y - y₀|

$displaystyle varepsilon_{0}^{}$ + $displaystyle varepsilon_{1}^{}$

on dit que les erreurs absolues s'additionnent.

Définition 1 L'erreur absolue est définie comme un majorant de la valeur absolue de la différence entre le nombre réel et son représentant double :

| x - x₀|

Mais comme il faut représenter x₀ + y₀ en machine, on doit ajouter une erreur d'arrondi, qui est proportionnelle à la valeur absolue de x₀ + y₀ d'où la notion d'erreur relative :

Définition 2 L'erreur relative est égale à l'erreur absolue divisée par la valeur absolue du nombre

| x - x₀|

| x₀|

Remarquons au passage que les erreurs de mesure expérimentales sont pratiquement toujours des erreurs relatives.

Donc lorsqu'on effectue une addition (ou une soustraction) de deux réels sur machine, on doit additionner les deux erreurs absolues sur les opérandes et ajouter une erreur d'arrondi (relative de 2^-53, à titre d'exercice, on pourra vérifier que cette erreur d'arrondi est majorée par l'erreur absolue de la somme x + y dès l'instant où x et y ont eux-même une erreur d'arrondi).

Lorsqu'on effectue une multiplication de deux nombres x, y dont les représentants x₀, y₀ sont non nuls, on a

$displaystyle leftvertvphantom{ frac{xy-x_0 y_0}{x_0 y_0} }right.$ $displaystyle {frac{{xy-x_0 y_0}}{{x_0 y_0}}}$ $displaystyle left.vphantom{ frac{xy-x_0 y_0}{x_0 y_0} }rightvert$ = $displaystyle leftvertvphantom{ frac{x}{x_0} frac{y}{y_0} -1) }right.$ $displaystyle {frac{{x}}{{x_0}}}$ $displaystyle {frac{{y}}{{y_0}}}$ - 1) $displaystyle left.vphantom{ frac{x}{x_0} frac{y}{y_0} -1) }rightvert$ = $displaystyle leftvertvphantom{ (frac{x}{x_0}-1)(frac{y}{y_0} -1)+(frac{x}{x_0}-1)+(frac{y}{y_0} -1) }right.$ ( $displaystyle {frac{{x}}{{x_0}}}$ -1)( $displaystyle {frac{{y}}{{y_0}}}$ -1) + ( $displaystyle {frac{{x}}{{x_0}}}$ -1) + ( $displaystyle {frac{{y}}{{y_0}}}$ - 1) $displaystyle left.vphantom{ (frac{x}{x_0}-1)(frac{y}{y_0} -1)+(frac{x}{x_0}-1)+(frac{y}{y_0} -1) }rightvert$

l'erreur relative est donc la somme des erreurs relatives et du produit des erreurs relatives (on peut souvent négliger le produit devant la somme). Il faut aussi y ajouter une erreur relative d'arrondi de 2^-53 surx₀y₀.

On observe que la multiplication est une opération posant moins de problèmes que l'addition, car on manipule toujours des erreurs relatives, par exemple si l'erreur relative sur deux doubles x et y non nuls est de 2^-53, alors l'erreur relative sur xy sera de

2^-53 +2^-53 +2^-106 +2^-53

3×2^-53

Lorsque l'erreur relative sur les données est grande devant 2^-53, l'erreur relative d'arrondi final est négligeable, on peut alors dire que les erreurs relatives s'additionnent pour un produit (c'est aussi vrai pour un quotient: exercice!). Par contre, si on additionne deux nombres dont le représentant de la somme est proche de 0, la somme des erreurs absolues peut devenir non négligeable par rapport à la somme des représentants, entrainant une erreur relative très grande. Par exemple si x est représenté par x₀ = 1 + 2^-52 avec une erreur d'arrondi de 2^-53 et y par y₀ = - 1 avec la même erreur d'arrondi, l'addition de x et yrenvoie 2^-52 avec une erreur absolue de 2*2^-53 (ici il n'y a pas d'arrondi lorsqu'on fait la somme). C'est une erreur relative de 1 (qui domine largement l'erreur d'arrondi) ce qui signifie que dans la mantisse, seul le premier bit sur les 52 a un sens, la perte de précision est très grande.

Une autre conséquence importante est que l'addition de réels sur machine n'est pas une opération associative, par exemple

(2.0^-53 +2.0^-53) + 1.0

1 + 2^-52

alors que

(2.0^-53 +1.0) + 2.0^-53

Si on a plusieurs termes à additionner, il faut commencer par additionner entre eux les termes les plus petits, pour que les petits termes ne soient pas absorbés un à un dans les erreurs d'arrondi (les petits ruisseaux font les grands fleuves).

Exercice : pour calculer la valeur numérique d'une dérivée de fonction, il vaut mieux calculer (f (x + h) - f (x - h))/(2h) que (f (x + h) - f (x))/h. Attention à ne pas prendre h trop petit, sinon x + h = x.

Remarquons néanmoins que les erreurs calculées ici sont des majorations des erreurs réelles (ou si on préfère l'erreur obtenue dans le pire des cas), statistiquement les erreurs sur les résultats sont moindres. Il est d'ailleurs souvent trop difficile de calculer la majoration rigoureuse de l'erreur pour des calculs complexes. Lorsqu'on doute de la précision d'un calcul, un test peu couteux consiste à refaire ce calcul en utilisant des flottants en précision plus grande et tester si le résultat varie en fonction du nombre de chiffres significatifs utilisés. On peut aussi faire varier légèrement les données et observer la sensibilité du résultat. Si on veut travailler en toute rigueur sans pour autant calculer les erreurs à priori, il faut utiliser un logiciel utilisant des intervalles pour représenter les réels (par exemple la bibliothèque C MPFI).

suivant: Types composés. monter: Les réels précédent: Erreurs Index

Retour à la page principale de mat249

Source : http://www-fourier.ujf-grenoble.fr/~parisse/mat249/mat249...

Arithmétique des polynomes: Bézout et applications

On considère les polynômes à une variable à coefficients dans ou ou . Les algorithmes de base déjà évoqués sont l'évaluation en un point (méthode de Horner), l'addition, la soustraction, la multiplication et la division euclidienne de A par B 0 :

A = BQ + R, deg(R) < deg(B)

A l'aide de la division euclidienne, on peut calculer le PGCD de deux polynômes par l'algorithme d'Euclide. Nous allons présenter l'algorithme d'Euclide étendu (ou de Bézout)

Théorème 7 Étant donnés 2 polynômes A et B, il existe deux polynômes U, V tels que

AU + BV = pgcd(A, B), deg(U) < deg(B),deg(V) < deg(A)

Algorithme :
On construit en fait 3 suites (U_n), (V_n) et (R_n) telles que :

AU_n + BV_n = R_n

on initialise U₀ = 1, V₀ = 0, R₀ = A et U₁ = 0, V₁ = 1, R₁ = B
on calcule les indices n + 2 en fonction de n et n + 1 en effectuant la division euclidienne de R_n par R_n+1

R_n = Q_nR_n+1 + R_n+2, U_n+2 = U_n - Q_nU_n+1, V_n+2 = V_n - Q_nV_n+1
on s'arrête au dernier reste non nul

Exemple :
A = x³ -1, B = x² + 1, les rangs 0 et 1 sont donnés ci-dessus. Au rang 2, Q₀ est le quotient euclidien de A par B (fonction quo) donc x, d'où

U₂ = 1, V₂ = - x, R₂ = - x - 1

Puis on divise x² + 1 par - x - 1, quotient - x + 1, donc

U₃ = x - 1, V₃ = 1 + x(- x + 1) = 1 + x - x², R₃ = 2

Preuve de l'algorithme :
On montre facilement par récurrence que la relation AU_n + BV_n = R_n est conservée. Comme R_n est la suite des restes, le dernier reste non nul est bien le pgcd de A et B. D'autre part, examinons les degrés des V_k. Supposons que deg(A) deg(B) (sinon on échange A et B). Au rang n = 0, V₀ = 0 donc V₂ = - Q₀V₁, aux rangs suivants le degré de Q_n est non nul (car le degré de R_n+1 est strictement inférieur au degré de R_n) On montre donc par récurrence que la suite des degrés de V_n est croissante et que :

deg(V_n+2) = deg(Q_n) + deg(V_n+1)

Comme deg(Q_n)=deg(R_n)-deg(R_n+1), on en déduit que

deg(V_n+2) + deg(R_n+1) = deg(V_n+1) + deg(R_n) = ... = deg(V₁) + deg(R₀) = deg(A)

Donc si n + 2 est le rang du dernier reste non nul, V_n+2 = V et degV=degA-degR_n+1 est donc strictement inférieur au degré de A (car R_n+1, l'avant-dernier reste non nul, est de degré plus grand ou égal à 1). On en déduit enfin que le degré de U est strictement inférieur au degré de B, car AU = R - BV, le degré de BV est strictement inférieur à celui de B plus celui de A.

L'identité de Bézout permet de résoudre plus générallement une équation du type

Au + Bv = C

où A, B, C sont trois polynômes donnés, à condition que C soit divisible par le pgcd de A et B. L'ensemble des solutions s'obtient à partir d'une solution particulière U, V de Bézout, notons c = C/gcd(A, B), on a alors

A(cU) + B(cV) = c gcd(A, B) = C

et l'ensemble des solutions est donné par u = cU - PB, v = cV + PA où P est un polynôme quelconque. Si le degré de C est plus petit que le degré de A plus le degré de B, il existe une solution ``priviligiée'', on prend pour u le reste de la division euclidienne de cU par B, v est alors le reste de la division euclidienne de cV par A pour des raisons de degré.

Exemple : si on veut résoudre

(x³ -1)u + (x² +1)v = 2x²

on multiplie U = x - 1 et V = 1 + x - x² par x² ce qui donne une solution

u = x²(x - 1), v = x²(1 + x - x²)

l'ensemble des solutions est de la forme

u + P(x² +1), v - P(x³ - 1)

et la solution priviligiée (de degrés minimaux) est

- x + 1 = rem(x²(x - 1), x² +1), x² - x + 1 = rem(x²(1 + x - x²), x³ - 1)

L'identité de Bézout intervient dans de nombreux problèmes en particulier la décomposition en éléments simples d'une fraction rationnelle. Si le dénominateur D d'une fraction se factorise en produit de 2 facteurs D = AB premiers entre eux, alors il existe deux polynômes u et v tels que N = Au + Bv, donc

$displaystyle {frac{{N}}{{D}}}$ = $displaystyle {frac{{Au+Bv}}{{AB}}}$ = $displaystyle {frac{{u}}{{B}}}$ + $displaystyle {frac{{v}}{{A}}}$

Si de plus N/D est une fraction propre (degré de N plus petit que celui de D), alors u/B et v/A sont encore des fractions propres (en calculant le reste de la division euclidienne pour u et v comme expliqué ci-dessus).

Par exemple :

$displaystyle {frac{{2x^2}}{{(x^3-1)(x^2+1)}}}$ = $displaystyle {frac{{(-x+1)(x^3-1)+(x^2-x+1)(x^2+1)}}{{(x^3-1)(x^2+1)}}}$ = $displaystyle {frac{{-x+1}}{{x^2+1}}}$ + $displaystyle {frac{{x^2-x+1}}{{x^3-1}}}$

Les applications sont diverses, citons

le calcul de primitive de fraction rationnelles (et tout ce qui s'y ramène), par exemple

$displaystyle {frac{{2x^2}}{{(x^3-1)(x^2+1)}}}$ = = $displaystyle {frac{{-x+1}}{{x^2+1}}}$ + $displaystyle {frac{{x^2-x+1}}{{x^3-1}}}$

Puis on fait apparaitre la dérivée du dénominateur au numérateur pour éliminer les x, 2x = (x² + 1)'

$displaystyle {frac{{-x+1}}{{x^2+1}}}$ = - $displaystyle {frac{{1}}{{2}}}$ $displaystyle {frac{{(x^2+1)'}}{{x^2+1}}}$ + $displaystyle {frac{{1}}{{x^2+1}}}$ + $displaystyle {frac{{x^2-x+1}}{{x^3-1}}}$

= - $displaystyle {frac{{1}}{{2}}}$ ln(x² +1) + arctan(x) + $displaystyle {frac{{x^2-x+1}}{{x^3-1}}}$

pour faire le calcul complet, il faut aussi décomposer la fraction restante (exercice!)
le calcul de transformée de Laplace inverse de fractions rationnelles, l'idée est la même, sauf qu'on remplace l'intégrale par la transformée de Laplace inverse (et les formules donnant la transformée inverse de 1/(x - p), 1/(x² + p²), p/(x² + p²) respectivement exp(px), sin(xp)/p, cos(px)) (calcul non exigible à l'examen)
le calcul du terme d'ordre n du développement de Taylor en 0 d'une fraction rationnelle. On décompose, et on se ramène à des séries dont le terme général est connu, comme (a + x)^-n. Par exemple pour connaitre le développement de 1/(x² - 3x + 2), on factorise le dénominateur 1/((x - 1)(x - 2)), on décompose

$displaystyle {frac{{1}}{{(x-1)(x-2)}}}$ = $displaystyle {frac{{-1}}{{x-1}}}$ + $displaystyle {frac{{1}}{{x-2}}}$ = $displaystyle {frac{{1}}{{1-x}}}$ - $displaystyle {frac{{1}}{{2}}}$ $displaystyle {frac{{1}}{{1-frac{x}{2}}}}$

et on développe, le terme d'ordre n est donc 1 - (1/2)ⁿ⁺¹.

Il faut néanmoins savoir factoriser un polynôme, ce dont nous parlerons dans la section suivante.

Exercice : Calculer l'intégrale

$displaystyle {frac{{1}}{{(x-1)(x^2+1)}}}$

en utilisant l'identité de Bézout pour décomposer la fraction rationnelle. Trouver à l'aide de cette décomposition le terme d'ordre n du développement de Taylor de la fraction à intégrer, vérifier avec un logiciel de calcul formel que les termes d'ordre 0 à 3 sont corrects.

Una autre application est l'élimination dans les systèmes polynomiaux, par exemple considérons le système de 2 équations à 2 inconnues (intersection d'une ellipse et d'un cercle) :

x² + y² -9 = 0, x² +2y² - 2xy - 7 = 0

En calculant les coefficients de Bézout des 2 polynômes en x x² + y² - 9 et x² +2y² - 2xy - 7 et en multipliant au besoin par le PPCM (plus grand commun multiple) des dénominateurs, on obtient à droite de l'équation de Bézout un polynôme ne dépendant que de y et qui s'annule aussi aux solutions du système, on peut alors résoudre en y (en factorisant) puis en x. Ici par exemple ce polynome est 5y⁴ -32y² + 4. Cette méthode se systématise, le polynome obtenu par élimination d'une variable est appelé résultant.

suivant: monter: précédent:

Retour à la page principale de mat249

Source : http://www-fourier.ujf-grenoble.fr/~parisse/mat249/mat249...

Mathématique

Cours, définitions, Vidéos, théorèmes, exercices, corrigés, livres sur les mathématiques, Livres Rares, Livres anciens de mathématiques

Recherchez sur le site (cours, livres, Agregation, etc.)

Liens utiles

Rechercher

CODE PROMO

Liens mathématiques divers

Livres en pdf

Cours

Documents Mathématiques

Août 2026

Notes récentes

Archives

Catégories

Derniers weblogs mis à jour

Liens Sites Amis

21/01/2010

Liens vers des sites de mathématiques

Les flottants au format double

Les flottants au format `double`

Séries entières

Séries entières.

Index - fourier.ujf-grenoble.fr

Index

Erreur absolue, relative et propagation des erreurs

Erreur absolue, relative et propagation des erreurs.

Arithmétique des polynomes: Bézout et applications

$displaystyle {frac{{-x+1}}{{x^2+1}}}$	=	- $displaystyle {frac{{1}}{{2}}}$ $displaystyle {frac{{(x^2+1)'}}{{x^2+1}}}$ + $displaystyle {frac{{1}}{{x^2+1}}}$ + $displaystyle {frac{{x^2-x+1}}{{x^3-1}}}$
	=	- $displaystyle {frac{{1}}{{2}}}$ ln(x² +1) + arctan(x) + $displaystyle {frac{{x^2-x+1}}{{x^3-1}}}$