Wiki du LAMA (UMR 5127) - Contributions [fr]

MATH203 : Introduction à l'algèbre

2008-03-19T20:41:18Z

Ebouv :

Feuilles de TD :
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD1-M2AL.pdf 1]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD2-M2AL.pdf 2]

== Que sont les mathématiques ==

En mathématique on étudie les propriétés d'objets tels que les nombres, les droites, ... Ces objets sont dénotés par des "expressions" comme
* x^2 - 1,
* Le milieu du segment [A,B],
* f est continue.

Chaque domaine des mathématiques possède son propre "vocabulaire" pour écrire des expressions et ce vocabulaire est introduit dans chacun de vos cours.

===L'égalité===
L'égalité joue un rôle particulier en mathématique car elle est "substitutive" : si deux expressions a et b sont égales, on peut remplacer a
par b dans toute expression sans en changer la valeur. Il faut tout de même faire attention aux variables liées. Considérons l'exemple suivant:

Soit y un réel et x = y + 2, on a donc x - y = 2.
Pour <math>x \in \mathbb{R}</math>, définissons la fonction f(x) = x^2 - y^2 = (x - y)(x + y).
On a donc pour tout <math>x \in \mathbb{R}</math> f(x) = 2(x + y) (pour un x particulier).

On a commis une erreur car x est une variable liée dans la seconde phrase. On peut toujours changer le nom des variables liées et écrire

Soit y un réel et x = y + 2, on a donc x - y = 2.
Pour <math>z \in \mathbb{R}</math>, définissons la fonction f(z) = z^2 - y^2 = (z - y)(z + y).
On a donc f(x) = 2(x + y).

===Les énoncés===
Parmis les expressions certaines sont des "énoncés", c'est à dire des expressions dont la valeur est vraie ou fausse comme
* x^2 - 1 = (x - 1)(x + 1)
* Les trois droites sont concourantes
* Toute fonction continue est dérivable (cet énoncé est faux, mais on peut l'écrire !)
Les mathématiques ont pour objet de découvrir quels énoncés sont vrais en partant uniquement "d'axiomes" qui sont des énoncés que l'on adment comme
vrais dans un domaine donné des mathématiques.

Tous les énoncés mathématiques peuvent être ecrits en utilisant les "briques" de construction suivantes :
* Des énoncés atomiques propre à chaque domaine des mathématique comme <math>x\in E</math>, "f est continue", ... Attention: certains énoncés atomiques peuvent être transformés en énoncés plus complexe en faisant appel à une définition (c'est le cas de "f est continue").
* l'implication : notée <math>A \Rightarrow B</math>, <math>A \rightarrow B</math>, A implique B, A est une condition suffisante pour B, B est une condition nécessaire pour A, si A alors B, ...

Attention, l'implication mathématique est très différente de l'implication en langage courant qui contient souvent une relation de cause à effet voire qui exprime une équivalence : "si tu ne mange pas ta soupe tu n'aura pas de déssert" est une équivalence en langue naturelle.

<math>A \Rightarrow B</math> est faux uniquement si A est vrai et B est faux. Dans les trois autres cas, l'implication mathématique est vraie. Pour ce persuader que c'est cela qu'il faut faire, considérer l'énoncé suivant (qui est bien vrai ?) :

Si n est divisible par 4 alors n est pair

* Pour n = 2 on obtient "Faux implique Vrai"
* Pour n = 3 on obtient "Faux implique Faux"
* Pour n = 4 on obitent "Vrai implique Vrai"

* La conjonction : notée "A et B", "<math>A \land B</math>", ... Le sens devrait être clair
* La disjonction : notée "A ou B", "<math>A \lor B</math>", ... C'est le ou usuel. A ou B est vrai si l'un des deux enoncés au moins est vrai. Il ne faut pas le confondre avec le "ou exclusif", utilisé en informatique, et qui est faux lorsque les deux énoncés sont vrais en même temps.
* La négation : notée "non A", "A est faux", "il est faux que A", "<math>\lnot A</math>", ... On a non A est vrai si et seulement si A est faux et donc aussi non A est faux si et seulement si A est vrai.
* L'équivalence : notée "A équivalent à B", "A si et seulement si B", "A est une condition nécessaire et suffisante pour B", "<math>A \Leftrightarrow B</math>", "<math>A \leftrightarrow B</math>". "<math>A \Leftrightarrow B</math>" peut être défini comme "(A implique B) et (B implique A)".
* La quantification universelle : notée "pour tout x A", "on a A pour tout x", "quelque soit x A", <math>\forall x A</math>, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.
* La quantification existentielle : notée "il existe x tel que A", "on a A pour au moins un x", "on peut trouver un x tel que A", <math>\exists x A</math>, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.

==Qu'est-ce qu'une preuve==

===Définitions===
*Une preuve est un texte pour convaincre constitué d'une suite d'étapes telles qu'à chacune d'elles, on a :
# des connaissances : liste d'objets connus, de théorèmes, d'hypothèses locales au problème
# un but à démontrer
* Pour passe d'une étape à l'autre, on peut :
# chercher à simplifier le but/le diviser
# utiliser des connaissances pour progresser (montrer le but, obtenir de nouvelles connaissances, faire un lemme...)

===6X2+2+... briques de bases===
* Si le but est dans la liste des connaissances ou si A et ¬ A sont dans les connaissances, alors la preuve est finie.
* 6X2 briques de bases:
# ''' Montrer que A=>B ''': Ajouter A aux hypothèses et montrer B / ''' Utiliser que A=B ''': Démontrer A pour pouvoir ajouter B aux connaissances
# ''' Montrer que A et B ''' : Deux preuves dont l'ordre n'a pas d'importance / ''' Utiliser que A et B ''' : Rajouter A et B aux connaissances, et utiliser l'une et/ou l'autre
# ''' Montrer que A ou B ''' : On montre A ou B, au choix / ''' Utiliser que A ou B ''' : Raisonner par disjonction de cas, on a alors deux preuves; rajouter A aux connaissances et montrer le but '' et '' rajouter B dans les connaissances et montrer le but
# ''' Montrer que ¬ A ''' : Supposer A et chercher une contradiction / ''' Utiliser que ¬ A ''' : Montrer A et en déduire une contradiction
# ''' Montrer que ∀ x, A ''' : Montrer A pour un x '' quelconque '' / ''' Utiliser que ∀ x, A ''' : Prendre le x qui nous intéresse et supposer A(x).
# ''' Montrer que ∃ x, A ''' : Montrer A pour un x bien choisi / ''' Utiliser que ∃ x, A ''': Prendre un '' nouveau '' x et supposer A(x)
* ''' Démonstration par l'absurde ''' : Si le but est A, alors on suppose ¬ A et on cherche une contradiction (particulièrement fréquent pour montrer un '' ou '', '' ∃ '', ou un '' énoncé atomique ''.
* Il existe d'autres briques propres au domaine dans lequel on se place ('' exemple '' : preuve par récurrence en arithmétique)

==Ensembles, Fonctions, Relations==

===Théorie des ensembles===
* ''' Schéma de compréhension ''' : {x ∈ A / P(x)} est l'ensemble des x de A qui ont la propriété P
* ''' Paradoxe de Russel ''' : Soit A={x / x <math> \notin </math> x}. Si A ∈ A alors A <math> \notin </math> A et si A <math> \notin </math> A alors A ∈ A. D'où une contradiction qui aboutit au théorème de Zermels et Frankel, modifiant le schéma de compréhension : {x '' ∈ A '' / ...}
* ''' Construction des ensembles ''' :
# A ∪ B={x / x ∈ A ou x ∈ B}
# A ∩ B={x / x ∈ A et x ∈ B}
# Ac={x <math> \notin </math> A}
# A-B=A ∩ Bc={x / x ∈ A et x <math> \notin </math> B}
# P(A) : ensemble des parties de A; B ∈ P(A) si et seulement si B ⊂ A ⇔ ∀ x (x ∈ B ⇒ x ∈ A)
# AXB où X est appelé produit cartésien : ensemble de couples; {(a,b) P(P(A ∪ B)) / a ∈ A b ∈ B}
* ''' Inverse d'une relation R ''' : Soit R ⊂ P(AXB), on peut '' toujours '' définir R-1. R-1={(b,a) / b ∈ B, a ∈ A, et (a,b) ∈ R}

===Fonction de A dans B===
* notée A → B, F(A,B)
* F(A,B)=déf{R ⊂ (AXB) / ∀ a ∈ A ∀ b, b' ∈ B, ((aRb) et (aRb')) ⇒ (b=b')
* Si f ∈ F(A,B), on écrit b=f(a).

===Application de A dans B===
* notée A'A,B) ou BA
* A(A,B)={f ∈ F(A,B) / ∀ a ∈ A ∃ b ∈ B tel que b=f(a)}

===Restriction===
Soient f ∈ F(A,B) et A' ⊂ A, fl`A' ∈ F(A',B)={(a,b) / a ∈ A' et b=f(a)}

===Image directe===
Soient f ∈ F(A,B) et A' ⊂ A, f(A')={b ∈ B / ∃ a ∈ A' b=f(a)}

=== Image réciproque===
Soient f ∈ F(A,B) et B' ⊂ B f-1(B')={a ∈ A / f(a) ∈ B' }

=== Inclusion===
A ⊂ B ⇔ (x ∈ A ⇒ x ∈ B)

===Injection===
* notée parfois A <math>\hookrightarrow </math> B
* Soit f une application de A dans B, ∀ a, a' ∈ A (f(a)=f(a') ⇒ a=a') ⇔ f est injective.

===Surjection===
Soit f une application de A dans B. ∀ b ∈ B ∃ a ∈ A tel que b=f(a) ⇔ f est surjective.

===Bijection===
(∀ a ∈ A ∃! b ∈ B tel que b=f(a) et ∀ b ∈ B ∃! a ∈ A tel que b=f(a)) ⇔ f est bijective (f est alors injective '' et '' surjective).

===Composition ===
* Soient f ∈ F(A,B) et g ∈ F(B,C). gof(x) ∈ F(A,C) est définie par gof(x)=g(f(x)).
* fog injective, g surjective ⇒ f injective
: fog surjective, f injective ⇒ g surjective
: fog injective ⇒ g injective
: fog surjective ⇒ f surjective

===Relation d'ordre large ===
≤ ≥ ⊂ divise dans lN

R ⊂ (AXA) est d'ordre large si et seulement si elle est :
# '' réflexive '' : ∀ a ∈ A aRa
# '' antisymétrique '' : ∀ a, a' ∈ A (aRa' et a'Ra) ⇒ a=a'
# '' transitive '' : ∀ a, b, c ∈ A (aRb et bRc) ⇒ aRc

===Relation d'équivalence===
=, ⇔, avoir même reste dans la division par n

R ⊂ (AXA) est d'équivalence si et seulement si elle est :
# '' réflexive '' : ∀ a ∈ A aRa
# '' symétrique '' : ∀ a, a' ∈ A aRa' ⇒ a'Ra
# '' transitive '' : ∀ a, b, c ∈ A (aRb et bRc) ⇒ aRc

===Quotients===
* ''' Définition ''' : On a un ensemble E et &equiv; une relation d'équivalence sur E. Le quotient de E par &equiv; noté E/&equiv; est l'ensemble des classes d'équivalence de &equiv;.
* ''' Classe d'équivalence ''' : La classe d'équivalence de x est x={y ∈ E / x &equiv; y} ⇔ ∀ a ∈ E (a ∈ x ⇔ a &equiv; x)
* ''' Propriétés ''' : Soient E un ensemble et &equiv; une relation d'équivalence sur E.
# ∀ x, y ∈ E (x &equiv; y ⇔ x=y)
# L'ensemble des classes d'équivalence est une partition de E
* ''' Construction de l'ensemble des rationnels par quotient ''' : Q={(n,d) l n∈Z, d∈lN*}, soit &equiv; / ((n,d) &equiv; (n',d') ⇔ nd'=n'd). &equiv; est une relation d'équivalence, et l'ensemble des rationnels est le quotient de Q par &equiv;.
* ''' Relever une opération sur le quotient '''
* ''' Loi interne ''' : f:EXE → E telle que si x &equiv; x' et y &equiv; y' alors f(x,y) &equiv; f(x',y').

==Arithmétique==

===Récurrence===
* ''' Principe '''
* ''' Récurrence généralisée '''

=== Division euclidienne===
* ''' Définition '''
* ''' Preuve de l'existence et de l'unicité par récurrence sur p ≥ 0 '''
===Divisibilité===

===PGCD===
* ''' Signification '''
* ''' Preuve de l'existence '''
* ''' Algorithme d'Euclide '''
# '' Propriétés ''
# '' Description ''
# '' Autre algorithme ''

===Théorème de Bezout===
* ''' Enoncé '''
* ''' Preuve '''
* ''' Corollaire '''
* ''' Réciproque '''

===Théorème de Gauss ===
* ''' Enoncé '''
* ''' Preuve '''

===Nombres premiers et décomposition===
* ''' Définition '''
* ''' Corollaire du théorème de Gauss '''
* ''' Théorème de décomposition '''

==Arithmétique modulaire==

===Définition de la congruence modulo n===
* ''' Congruence ''' : relation d'équivalence
* ''' Notation ''' : a&equiv;nb a&equiv;b(mod n) a=b(mod n)
* a&equiv;nb ⇔ b-a est un multiple de n
* a&equiv;nb ⇔ a%n=b%n
* Z/nZ est le quotient de Z par la relation d'équivalence modulo n.
# a&equiv;na%n
# Z/nZ={0,1,2,...,n-1} est un ensemble fini à n éléments.
# Z/nZ est un anneau commutatif non intègre. Tout élément non nul de Z/nZ est inversible si et seulement si n est premier. On note alors Z/nZ=Z/pZ.

===Petit théorème de Fermat===
* ''' Enoncé ''': '' <math>a^p = a \pmod p</math> si <math>p \in \mathbb N</math> est premier.'' Ceci peut aussi s'écrire
<math>a^{p-1} = 1 \pmod p</math> mais il faut alors que <math>p</math> ne divise pas <math>a</math>.
* ''' Preuve ''' : Dans (Z/pZ-{0},X) groupe à p-1 éléments, on veut montrer que ap-1=1(mod p).
: ∃ m tel que am=1. {an/n ∈ Z} est un sous groupe de Z/pZ fini, d'où ∃ n' tel que an=an' or p est premier donc an' a un inverse. D'où an-n'=1 ou an'-n=1.
: Montrons que le plus petit n tel que an=1 divise p-1 (théorème de Lagrange). On '' partitionne '' Z/pZ en une famille d'ensembles de '' même cardinal '' que {an}, tout élément de Z/pZ peut s'écrire sous la forme α a θ .
:: La donnée d'une telle partition revient à donner une relation d'équivalence sur Z/pZ : β R γ ⇔ ∃ e ∈ Z tel que β = γ α e.
::: R est réflexive : β=β α 0 d'où β R β
::: R est symétrique : ∃ e tel que β = γ α e donc γ=βα-e car α est inversible, d'où si β R γ alors γ R β
::: R est transitive : ∃ e,f tels que β = γ α e et γ=δ αf implique β = δ α e+f, donc si β R γ et γ R δ alors β R δ
:: 1={1,a,a2,...an-1}=A et b={b,ab,a2b,...an-1b}=B. Soit f:A→B telle que f(x)=xb, f-1(x)=xb-1. fof-1=id et f-1of=id donc f est bijective. Il en résulte que chaque classe est de taille n, d'où n l p-1.
: n l p-1 ⇒ ∃ q ∈ Z tel que p-1=qn et an=1 ⇒ ap-1=aqn=(an)q=1

==Compléments sur les polynômes==

===FTA ou théorème de d'Alembert===
* ''' Enoncé ''': '' Tout polynôme de degré supérieur ou égal à 1 à coefficients dans <math>\mathbb{C}</math> a au moins un racine dans <math>\mathbb{C}</math>. ''
* ''' Preuve ''' :
: Soient <math> z=a_0+a_1z+ \dots +a_nz^n</math> un polynôme à coefficients dans <math>\mathbb{C}[z]</math>. Définissons <math>f:\mathbb{C} \rightarrow \mathbb{R}</math> par <math>f(z)=|P(z)|</math>. On va montrer que P admet une racine dans <math>\mathbb{C}</math>.
::* Montrons que <math> \lim_{\mid z \mid \longmapsto \infty} f(z)=\infty </math> :
::: On a <math> f(z)=\mid z^n (\frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} + a_n) \mid </math>, or labl=lallbl, d'où :

<math> f(z)= \mid z^n \mid \mid a_n + (\frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z}) \mid </math> or la+bl ≥ llal-lbll, d'où :

<math> f(z) \geq \mid z^n \mid \mid \mid a_n \mid - \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid \mid </math>
::: Cherchons R tel que si lzl>R alors <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid <\mid \frac{a_n}{2} \mid</math> :
:::: <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid \geq \mid \frac{a_0}{z^n} \mid + \mid \frac{a_1}{z^{n-1}} \mid +\dots + \mid \frac{a_{n-1}}{z} \mid </math>
:::: <math> \mid \frac{a_{n-1}}{z} \mid < \mid \frac{a_n}{2n} \mid</math>si <math> \mid z \mid > \mid 2n \frac{a_{n-1}}{a_n} \mid </math> ... <math> \mid \frac{a_0}{z^n} \mid < \mid \frac{a_0}{z} \mid < \mid \frac{a_n}{2n} \mid </math> si <math> \mid z \mid > max(1, \mid 2n \frac{a_0}{a_n}\mid) </math> c'est à dire <math> \mid \frac{a_p}{z^{n-p}} \mid < \mid \frac{a_p}{z} \mid < \mid \frac{a_n}{2n} \mid </math> si <math> \mid z \mid > max (1, \mid 2n \frac{a_p}{a_n} \mid)</math> ∀ p ∈ [lO;nl[. Donc si <math> \mid z \mid > max (1, \mid 2n \frac{a_0}{a_n} \mid, \dots, \mid 2n \frac{a_{n-1}}{a_n} \mid=R ) </math> alors <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid <\mid \frac{a_n}{2} \mid</math>.
::: D'où si lzl>R, alors <math> f(z) > \mid z^n \mid \mid \mid a_n \mid - \mid \mid \frac{a_n}{2} \mid \mid </math>, soit <math> f(z)> \mid z^n \mid \mid \frac{a_n}{2} \mid </math>
::: Cherchons z tel que ∀ M, f(z)>M. Il suffit que lzl>R et lzln>lzl> 2M/lanl. D'où si <math> \mid z \mid > max(1, \frac{2M}{\mid a_n \mid}, \frac{2na_0}{a_n}, \dots, \frac{2na_{n-1}}{a_n})=r</math> alors f(z)>M, c'est à dire <math> \lim_{\mid z \mid \longmapsto \infty} f(z)=\infty </math>.

'' Graphiquement '': Soit D={z/ lzl<r}, pour tout z n'appartenant pas à D f(z)>M. En particulier, il n'existe pas z n'appartenant pas à D tel que f(z)=0; z ≥ r n'est pas une racine.
::* Montrons qu'il existe z0 ∈ D tel que f atteint son minimum en z0.
::#f(D) ⊂ lR+ donc f(D) est une partie de lR minorée par 0. Par l'axiome de la borne inférieure, f(D) admet une borne inférieure.
::# Montrons que Inf(f(D)) est atteinte.
::## C est compact donc on peut trouver une suite z0, z1... ∈ D telle que f(zn) tend vers Inf(f(D)) quand n tend vers + ∞ .
::## f est une fonction continue car P(z) est continue, et z → lzl est continue?
::## <math> f(\lim_{n \rightarrow \infty}z_n)=\lim_{n \rightarrow \infty}(f(z_n))=Inf(f(D)) </math>. Soit m=Inf(f(D)) et soit <math>l= \lim_{n \rightarrow \infty}z_n</math>, f(l)=m et l ∈ D. f atteint son minimum en l ∈ D.
::# Montrons par l'absurde que m=Inf(f(D))=f(l)=0, c'est à dire trouvons z tel que lP(z)l<m alors que par hypothèse c'est impossible. Supposons que P n'a pas de racine. Posons Q(z)=P(z-l) et g(z)=f(z-l)=lQ(z)l.
::## g atteint son minimum en 0. Q(z)=b0+bpzp+...+bnzn où bp est le plus petit coefficient non nul autre que b0 ≠ 0, et lb0l=m.
::## On cherche z tel que bpzp=-b0C où C ∈ lR+ ⇔ <math> z^p=-C \frac{b_0}{b_p}=\lambda e^{i\theta} \Leftrightarrow z=\lambda ^{1/p}e^{i\theta /p} </math>
::## lbp+1zp+1+...+bnznl ≤ lzpl(lbp+1zl+lbp+2z2l+...+lbnzn-pl) or lbp+1zl ≤ lbp/(2n)l si lzl ≤ lbp/(2bp+qn)l ... lbp+qzql ≤ lbp/(2n)l si lzl ≤ min(1,lbp/(2nbp+ql), c'est à dire lbp/1zp+1+...+bnznl ≤ lbnzpl/2 si lzl ≤ min(1,lbp/(2nbp+1)l,...lb0/bql)=r.
::## Si on prend lzl=r, z=rei θ et bpzp=-b0C où C ∈ lR+. bp(rei θ )p=-b0C, ei θ =-cb0/(rpbp)=Kei ω . Pour que K=1, on prend lCl=lrpbp/b0l. D'où z=rei arg(-b0/bp)/p.
::## Q(z)=b0+bpzp+ ε avec ε ≤ lbpzp/2l. D'où bpzp=bprpei arg(-b0/bp)=-lbplrpei arg(b0). D'où Q(z)=(lb0l-lbprpl)ei arg(b0)+ε, soit Q(z) ≤ (lb0l-lbprpl)ei arg(b0)+lεl ≤ lb0l-lbprpl+lεl<lb0l<m

'' Conclusion '': P a une racine z0 telle que lQ(0)l=lP(z0-l)l=m=0, c'est à dire que P a une racine z0=l ∈ D.

===Fonctions polynômes/Polynômes===
* Un ''' polynôme ''' de degré d est un élément de lRd+1 : P=(a0,a1,...,ad) est un '' vecteur ''.
Il est néanmoins possible de faire quelques opérations supplémentaires sur les polynômes :
:*+ sur des vecteurs de taille différente
:*division euclidienne
:*produit
:*dérivation
* ''' Fonction polynôme ''' :

Soit P un polynôme à coefficients dans lK=C, lR, Q, Z/pZ
P(x) est une foction de lK → lK qui a x associe a0+a1x+...adxd si P=(a0,a1,...,ad)
* ''' Egalité de deux polynômes ''' :

Dans lR, C et Q, deux polynômes sont égaux si et seulement si les fonctions associées sont égales.
Ce n'est pas le cas dans Z/pZ.

'' Exemple '': dans Z/2Z, P=1+X+X2 et Q=1, x ∈ {0;1}.
P(0)=Q(1)=1 et P(0)=P(1)=1 donc les fonctions sont égales bien que les polynômes soient différents.

'' Remarque '' : Il existe 4 polynômes de degré 2 dans Z/2Z.
* ''' Dérivation ''' :

P' est une opération formelle sur les coefficients car <math>\lim_{h \longmapsto 0} \frac{P(x+h)-P(x)}{h}</math> n'a pas de sens dans Z/pZ.

Si P=(a0,a1,...,ad) (d°=d), alors P'=(a1,2a2,...,dad) (d°=d-1)
* ''' PGCD et polynômes de Bezout ''' :
:* '' Plus grand '' diviseur commun : celui qui a le plus grand degré (donc plus grand à une constante multiplicative près)
:* ''Remarques '' :
:# Stathme : valeur absolue dans Z, degré d'un polynôme ∈ lN
:# Pour les polynômes, l'algorithme d'Euclide st la preuve de l'existence du PGCD
:* Algorithme d'Euclide : preuve par récurrence sur d°P+d°Q
:# 0 &and; Q=Q et P &and; 0=P
:# Si d°P+d°Q=0 : les deux polynômes sont constants, P &and; Q=1=P=Q et donc P &and; Q existe
:# Hypothèse de récurrence : On suppose que P' &and; Q' existe pour tout P' et pour tout Q' tels que d°P'+d°Q' ≤ d°P+d°Q. On a d°P+d°Q>0
:## Supposons d°Q ≥ d°P (sinon on échange P et Q). On effectue la division puissance croissante de Q par P : Q=SP+R où d°R<d°P. Soit D un polynôme : si D l P et D l Q alors D l SP-Q=R; si D l P et D l R alors D l SP+R=Q. Ainsi l'ensemble des diviseurs communs de P et Q est celui des diviseurs de P et R.
:## Par récurrence P &and; Q existe ( puisque d°P+d°Q<d°P+d°P ≤ d°P+d°Q)
:* Polynômes de Bezout
:# Si P &and; Q=D alors ∃ U, V deux polynômes tels que UP+VQ=D
:# '' Existence '' : On remonte l'algorithme (par récurrence sur d°P+d°Q)
:## Si P=0 et Q <math>\neq</math> 0 : 0.P+1.Q=Q=P &and;Q
:## Si P <math>\neq</math>0 et Q=0 : 1.P+0.Q=P=P &and; Q
:## Si d°P+d°Q=0 : <math>P=a\neq 0</math> et <math>Q=b\neq 0</math> : a-1.a+0.b=1=P &and; Q
:## Si d°P+d°Q>0 avec d°P ≤ d°Q : Q=SP+R. Par récurrence, on a trouvé U et V tels que UP+VR=P &and; Q= P &and; R soit (U-VS)P+VQ=P &and; Q

===Construction d'un nouveau corps===
* Soit P un polynôme d'un corps lK. On peut quotienter lK[X] par P, c'est à dire poser P=0. On quotiente par la relation d'équivalence avoir même reste dans la division par P (même preuves que dans Z/nZ).

On obtient un corps si et seulement si P est irréductible, c'est à dire que P ne peut pas s'écrire P=QR avec d°Q>0 et d°R>0.
::'' Remarques :''
::: En d°2 et 3 : P est irréductible si et seulement si P n'a pas de racine
::: a racine de P si et seulement si (X-a) l P
* ''' Construction de F4 ''' : lK=Z/2Z
:* Dans Z/pZ :
:::Tous les polynômes de degré 2 sont de la forme X2+aX+b, donc il y a p2 polynômes.
:::Tous les polynômes réductibles de degré 2 sont de la forme (X-a)(X-b), donc il y a p(p+1)/2 polynômes.
:::(a+b)p=ap+bp
:*X2, X2+X=X(X+1), et X2+1=(X+1)2 sont réductibles, contrairement à X2+X+1.
:*On pose X2+X+1=0, soit X2=X+1

F4={0,1,X,X+1}={0,1,α,β}, donc 0={P(X2+X+1) l P ∈ lK[X]}, 1={P(X2+X+1)+1 l P ∈ lK[X]}, α={P(X2+X+1)+X l P ∈ lK[X]}, et β={P(X2+X+1)+X+1 l P ∈ lK[X]}.
<center>
{| border="1"
| + || 0 || 1 || α || β
|-
| 0 || 0 || 1 || α || β
|-
| 1 || 1 || 0 || β || α
|-
| α || α || β || 0 || 1
|-
| β || β || α || 1 || 0
|}

{| border="1"
| × || 0 || 1 || α || β
|-
| 0 || 0 || 0 || 0 || 0
|-
| 1 || 0 || 1 || α || β
|-
| α || 0 || α || β || 1
|-
| β || 0 || β || 1 || α
|}
</center>
* ''' Construction de <math>\mathbb{C}</math> ''' : lK=lR
:*P=1+X2 est irréductible : X2=-1 et on pose X=i

Tous les restes de la division par 1+X2 sont de la forme a+bX=a+ib

D'où <math>\mathbb{C}</math>=P[lR]/1+X2={a+ib l a,b ∈ lR}
:*<math>\mathbb{C}</math>=P[lR]/1+X+X2={a+jb l a,b ∈ lR}

==Permutations==
===Définition===
Une permutation est une bijection sur un ensemble fini. On note Sn l'ensemble des permutations de {1,2,...,n}
===Notation===
<math> \sigma=\begin{pmatrix}1 & 3 & 4 & 5 & 2 \\ 2 & 4 & 1 & 3 & 5\end{pmatrix} </math>. Sur chaque ligne figurent une fois tous les éléments de 1 à n. σ(1)=2 et σ-1(2)=1.
===Composition===
*Si σ, σ' ∈ Sn alors σ•σ' est aussi une permutation.

idn ∈ Sn : <math> id_n=\begin{pmatrix}1 & 2 & 3 & \dots & n \\ 1 & 2 & 3 & \dots & n\end{pmatrix} </math>

σ•id=σ (id est neutre pour •), σ•σ-1=id
*{Sn,•} est un groupe non commutatif.
:*<math> S_2=\{\begin{pmatrix}1 & 2 \\ 1 & 2 \end{pmatrix},\begin{pmatrix}1 & 2 \\ 2 & 1 \end{pmatrix} \}=\{ id_2, \sigma \} </math>, où σ•σ=id
:*<math> S_3=\{ (132),(213), (321), (123), (231), (312) \} </math>
===Support de σ===

===Transposition===

===Signature===

MATH203 : Introduction à l'algèbre

2008-03-12T20:57:19Z

Ebouv :

Feuilles de TD :
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD1-M2AL.pdf 1]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD2-M2AL.pdf 2]

== Que sont les mathématiques ==

En mathématique on étudie les propriétés d'objets tels que les nombres, les droites, ... Ces objets sont dénotés par des "expressions" comme
* x^2 - 1,
* Le milieu du segment [A,B],
* f est continue.

Chaque domaine des mathématiques possède son propre "vocabulaire" pour écrire des expressions et ce vocabulaire est introduit dans chacun de vos cours.

===L'égalité===
L'égalité joue un rôle particulier en mathématique car elle est "substitutive" : si deux expressions a et b sont égales, on peut remplacer a
par b dans toute expression sans en changer la valeur. Il faut tout de même faire attention aux variables liées. Considérons l'exemple suivant:

Soit y un réel et x = y + 2, on a donc x - y = 2.
Pour <math>x \in \mathbb{R}</math>, définissons la fonction f(x) = x^2 - y^2 = (x - y)(x + y).
On a donc pour tout <math>x \in \mathbb{R}</math> f(x) = 2(x + y) (pour un x particulier).

On a commis une erreur car x est une variable liée dans la seconde phrase. On peut toujours changer le nom des variables liées et écrire

Soit y un réel et x = y + 2, on a donc x - y = 2.
Pour <math>z \in \mathbb{R}</math>, définissons la fonction f(z) = z^2 - y^2 = (z - y)(z + y).
On a donc f(x) = 2(x + y).

===Les énoncés===
Parmis les expressions certaines sont des "énoncés", c'est à dire des expressions dont la valeur est vraie ou fausse comme
* x^2 - 1 = (x - 1)(x + 1)
* Les trois droites sont concourantes
* Toute fonction continue est dérivable (cet énoncé est faux, mais on peut l'écrire !)
Les mathématiques ont pour objet de découvrir quels énoncés sont vrais en partant uniquement "d'axiomes" qui sont des énoncés que l'on adment comme
vrais dans un domaine donné des mathématiques.

Tous les énoncés mathématiques peuvent être ecrits en utilisant les "briques" de construction suivantes :
* Des énoncés atomiques propre à chaque domaine des mathématique comme <math>x\in E</math>, "f est continue", ... Attention: certains énoncés atomiques peuvent être transformés en énoncés plus complexe en faisant appel à une définition (c'est le cas de "f est continue").
* l'implication : notée <math>A \Rightarrow B</math>, <math>A \rightarrow B</math>, A implique B, A est une condition suffisante pour B, B est une condition nécessaire pour A, si A alors B, ...

Attention, l'implication mathématique est très différente de l'implication en langage courant qui contient souvent une relation de cause à effet voire qui exprime une équivalence : "si tu ne mange pas ta soupe tu n'aura pas de déssert" est une équivalence en langue naturelle.

<math>A \Rightarrow B</math> est faux uniquement si A est vrai et B est faux. Dans les trois autres cas, l'implication mathématique est vraie. Pour ce persuader que c'est cela qu'il faut faire, considérer l'énoncé suivant (qui est bien vrai ?) :

Si n est divisible par 4 alors n est pair

* Pour n = 2 on obtient "Faux implique Vrai"
* Pour n = 3 on obtient "Faux implique Faux"
* Pour n = 4 on obitent "Vrai implique Vrai"

* La conjonction : notée "A et B", "<math>A \land B</math>", ... Le sens devrait être clair
* La disjonction : notée "A ou B", "<math>A \lor B</math>", ... C'est le ou usuel. A ou B est vrai si l'un des deux enoncés au moins est vrai. Il ne faut pas le confondre avec le "ou exclusif", utilisé en informatique, et qui est faux lorsque les deux énoncés sont vrais en même temps.
* La négation : notée "non A", "A est faux", "il est faux que A", "<math>\lnot A</math>", ... On a non A est vrai si et seulement si A est faux et donc aussi non A est faux si et seulement si A est vrai.
* L'équivalence : notée "A équivalent à B", "A si et seulement si B", "A est une condition nécessaire et suffisante pour B", "<math>A \Leftrightarrow B</math>", "<math>A \leftrightarrow B</math>". "<math>A \Leftrightarrow B</math>" peut être défini comme "(A implique B) et (B implique A)".
* La quantification universelle : notée "pour tout x A", "on a A pour tout x", "quelque soit x A", <math>\forall x A</math>, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.
* La quantification existentielle : notée "il existe x tel que A", "on a A pour au moins un x", "on peut trouver un x tel que A", <math>\exists x A</math>, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.

==Qu'est-ce qu'une preuve==

===Définitions===
*Une preuve est un texte pour convaincre constitué d'une suite d'étapes telles qu'à chacune d'elles, on a :
# des connaissances : liste d'objets connus, de théorèmes, d'hypothèses locales au problème
# un but à démontrer
* Pour passe d'une étape à l'autre, on peut :
# chercher à simplifier le but/le diviser
# utiliser des connaissances pour progresser (montrer le but, obtenir de nouvelles connaissances, faire un lemme...)

===6X2+2+... briques de bases===
* Si le but est dans la liste des connaissances ou si A et ¬ A sont dans les connaissances, alors la preuve est finie.
* 6X2 briques de bases:
# ''' Montrer que A=>B ''': Ajouter A aux hypothèses et montrer B / ''' Utiliser que A=B ''': Démontrer A pour pouvoir ajouter B aux connaissances
# ''' Montrer que A et B ''' : Deux preuves dont l'ordre n'a pas d'importance / ''' Utiliser que A et B ''' : Rajouter A et B aux connaissances, et utiliser l'une et/ou l'autre
# ''' Montrer que A ou B ''' : On montre A ou B, au choix / ''' Utiliser que A ou B ''' : Raisonner par disjonction de cas, on a alors deux preuves; rajouter A aux connaissances et montrer le but '' et '' rajouter B dans les connaissances et montrer le but
# ''' Montrer que ¬ A ''' : Supposer A et chercher une contradiction / ''' Utiliser que ¬ A ''' : Montrer A et en déduire une contradiction
# ''' Montrer que ∀ x, A ''' : Montrer A pour un x '' quelconque '' / ''' Utiliser que ∀ x, A ''' : Prendre le x qui nous intéresse et supposer A(x).
# ''' Montrer que ∃ x, A ''' : Montrer A pour un x bien choisi / ''' Utiliser que ∃ x, A ''': Prendre un '' nouveau '' x et supposer A(x)
* ''' Démonstration par l'absurde ''' : Si le but est A, alors on suppose ¬ A et on cherche une contradiction (particulièrement fréquent pour montrer un '' ou '', '' ∃ '', ou un '' énoncé atomique ''.
* Il existe d'autres briques propres au domaine dans lequel on se place ('' exemple '' : preuve par récurrence en arithmétique)

==Ensembles, Fonctions, Relations==

===Théorie des ensembles===
* ''' Schéma de compréhension ''' : {x ∈ A / P(x)} est l'ensemble des x de A qui ont la propriété P
* ''' Paradoxe de Russel ''' : Soit A={x / x <math> \notin </math> x}. Si A ∈ A alors A <math> \notin </math> A et si A <math> \notin </math> A alors A ∈ A. D'où une contradiction qui aboutit au théorème de Zermels et Frankel, modifiant le schéma de compréhension : {x '' ∈ A '' / ...}
* ''' Construction des ensembles ''' :
# A ∪ B={x / x ∈ A ou x ∈ B}
# A ∩ B={x / x ∈ A et x ∈ B}
# Ac={x <math> \notin </math> A}
# A-B=A ∩ Bc={x / x ∈ A et x <math> \notin </math> B}
# P(A) : ensemble des parties de A; B ∈ P(A) si et seulement si B ⊂ A ⇔ ∀ x (x ∈ B ⇒ x ∈ A)
# AXB où X est appelé produit cartésien : ensemble de couples; {(a,b) P(P(A ∪ B)) / a ∈ A b ∈ B}
* ''' Inverse d'une relation R ''' : Soit R ⊂ P(AXB), on peut '' toujours '' définir R-1. R-1={(b,a) / b ∈ B, a ∈ A, et (a,b) ∈ R}

===Fonction de A dans B===
* notée A → B, F(A,B)
* F(A,B)=déf{R ⊂ (AXB) / ∀ a ∈ A ∀ b, b' ∈ B, ((aRb) et (aRb')) ⇒ (b=b')
* Si f ∈ F(A,B), on écrit b=f(a).

===Application de A dans B===
* notée A'A,B) ou BA
* A(A,B)={f ∈ F(A,B) / ∀ a ∈ A ∃ b ∈ B tel que b=f(a)}

===Restriction===
Soient f ∈ F(A,B) et A' ⊂ A, fl`A' ∈ F(A',B)={(a,b) / a ∈ A' et b=f(a)}

===Image directe===
Soient f ∈ F(A,B) et A' ⊂ A, f(A')={b ∈ B / ∃ a ∈ A' b=f(a)}

=== Image réciproque===
Soient f ∈ F(A,B) et B' ⊂ B f-1(B')={a ∈ A / f(a) ∈ B' }

=== Inclusion===
A ⊂ B ⇔ (x ∈ A ⇒ x ∈ B)

===Injection===
* notée parfois A <math>\hookrightarrow </math> B
* Soit f une application de A dans B, ∀ a, a' ∈ A (f(a)=f(a') ⇒ a=a') ⇔ f est injective.

===Surjection===
Soit f une application de A dans B. ∀ b ∈ B ∃ a ∈ A tel que b=f(a) ⇔ f est surjective.

===Bijection===
(∀ a ∈ A ∃! b ∈ B tel que b=f(a) et ∀ b ∈ B ∃! a ∈ A tel que b=f(a)) ⇔ f est bijective (f est alors injective '' et '' surjective).

===Composition ===
* Soient f ∈ F(A,B) et g ∈ F(B,C). gof(x) ∈ F(A,C) est définie par gof(x)=g(f(x)).
* fog injective, g surjective ⇒ f injective
: fog surjective, f injective ⇒ g surjective
: fog injective ⇒ g injective
: fog surjective ⇒ f surjective

===Relation d'ordre large ===
≤ ≥ ⊂ divise dans lN

R ⊂ (AXA) est d'ordre large si et seulement si elle est :
# '' réflexive '' : ∀ a ∈ A aRa
# '' antisymétrique '' : ∀ a, a' ∈ A (aRa' et a'Ra) ⇒ a=a'
# '' transitive '' : ∀ a, b, c ∈ A (aRb et bRc) ⇒ aRc

===Relation d'équivalence===
=, ⇔, avoir même reste dans la division par n

R ⊂ (AXA) est d'équivalence si et seulement si elle est :
# '' réflexive '' : ∀ a ∈ A aRa
# '' symétrique '' : ∀ a, a' ∈ A aRa' ⇒ a'Ra
# '' transitive '' : ∀ a, b, c ∈ A (aRb et bRc) ⇒ aRc

===Quotients===
* ''' Définition ''' : On a un ensemble E et &equiv; une relation d'équivalence sur E. Le quotient de E par &equiv; noté E/&equiv; est l'ensemble des classes d'équivalence de &equiv;.
* ''' Classe d'équivalence ''' : La classe d'équivalence de x est x={y ∈ E / x &equiv; y} ⇔ ∀ a ∈ E (a ∈ x ⇔ a &equiv; x)
* ''' Propriétés ''' : Soient E un ensemble et &equiv; une relation d'équivalence sur E.
# ∀ x, y ∈ E (x &equiv; y ⇔ x=y)
# L'ensemble des classes d'équivalence est une partition de E
* ''' Construction de l'ensemble des rationnels par quotient ''' : Q={(n,d) l n∈Z, d∈lN*}, soit &equiv; / ((n,d) &equiv; (n',d') ⇔ nd'=n'd). &equiv; est une relation d'équivalence, et l'ensemble des rationnels est le quotient de Q par &equiv;.
* ''' Relever une opération sur le quotient '''
* ''' Loi interne ''' : f:EXE → E telle que si x &equiv; x' et y &equiv; y' alors f(x,y) &equiv; f(x',y').

==Arithmétique==

===Récurrence===
* ''' Principe '''
* ''' Récurrence généralisée '''

=== Division euclidienne===
* ''' Définition '''
* ''' Preuve de l'existence et de l'unicité par récurrence sur p ≥ 0 '''
===Divisibilité===

===PGCD===
* ''' Signification '''
* ''' Preuve de l'existence '''
* ''' Algorithme d'Euclide '''
# '' Propriétés ''
# '' Description ''
# '' Autre algorithme ''

===Théorème de Bezout===
* ''' Enoncé '''
* ''' Preuve '''
* ''' Corollaire '''
* ''' Réciproque '''

===Théorème de Gauss ===
* ''' Enoncé '''
* ''' Preuve '''

===Nombres premiers et décomposition===
* ''' Définition '''
* ''' Corollaire du théorème de Gauss '''
* ''' Théorème de décomposition '''

==Arithmétique modulaire==

===Définition de la congruence modulo n===
* ''' Congruence ''' : relation d'équivalence
* ''' Notation ''' : a&equiv;nb a&equiv;b(mod n) a=b(mod n)
* a&equiv;nb ⇔ b-a est un multiple de n
* a&equiv;nb ⇔ a%n=b%n
* Z/nZ est le quotient de Z par la relation d'équivalence modulo n.
# a&equiv;na%n
# Z/nZ={0,1,2,...,n-1} est un ensemble fini à n éléments.
# Z/nZ est un anneau commutatif non intègre. Tout élément non nul de Z/nZ est inversible si et seulement si n est premier. On note alors Z/nZ=Z/pZ.

===Petit théorème de Fermat===
* ''' Enoncé ''': '' <math>a^p = a \pmod p</math> si <math>p \in \mathbb N</math> est premier.'' Ceci peut aussi s'écrire
<math>a^{p-1} = 1 \pmod p</math> mais il faut alors que <math>p</math> ne divise pas <math>a</math>.
* ''' Preuve ''' : Dans (Z/pZ-{0},X) groupe à p-1 éléments, on veut montrer que ap-1=1(mod p).
: ∃ m tel que am=1. {an/n ∈ Z} est un sous groupe de Z/pZ fini, d'où ∃ n' tel que an=an' or p est premier donc an' a un inverse. D'où an-n'=1 ou an'-n=1.
: Montrons que le plus petit n tel que an=1 divise p-1 (théorème de Lagrange). On '' partitionne '' Z/pZ en une famille d'ensembles de '' même cardinal '' que {an}, tout élément de Z/pZ peut s'écrire sous la forme α a θ .
:: La donnée d'une telle partition revient à donner une relation d'équivalence sur Z/pZ : β R γ ⇔ ∃ e ∈ Z tel que β = γ α e.
::: R est réflexive : β=β α 0 d'où β R β
::: R est symétrique : ∃ e tel que β = γ α e donc γ=βα-e car α est inversible, d'où si β R γ alors γ R β
::: R est transitive : ∃ e,f tels que β = γ α e et γ=δ αf implique β = δ α e+f, donc si β R γ et γ R δ alors β R δ
:: 1={1,a,a2,...an-1}=A et b={b,ab,a2b,...an-1b}=B. Soit f:A→B telle que f(x)=xb, f-1(x)=xb-1. fof-1=id et f-1of=id donc f est bijective. Il en résulte que chaque classe est de taille n, d'où n l p-1.
: n l p-1 ⇒ ∃ q ∈ Z tel que p-1=qn et an=1 ⇒ ap-1=aqn=(an)q=1

==Compléments sur les polynômes==

===FTA ou théorème de d'Alembert===
* ''' Enoncé ''': '' Tout polynôme de degré supérieur ou égal à 1 à coefficients dans C a au moins un racine dans C. ''
* ''' Preuve ''' :
: Soient <math> (z)=a_0+a_1z+ \dots +a_nz^n</math> un polynôme à coefficients dans C[z] et f:C → lR telle que f(z)=lP(z)l
:Montrons que P admet une racine dans C.
::* Montrons que <math> \lim_{\mid z \mid \longmapsto \infty} f(z)=\infty </math> :
::: On a <math> f(z)=\mid z^n (\frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} + a_n) \mid </math>, or labl=lallbl, d'où :

<math> f(z)= \mid z^n \mid \mid a_n + (\frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z}) \mid </math> or la+bl ≥ llal-lbll, d'où :

<math> f(z) \geq \mid z^n \mid \mid \mid a_n \mid - \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid \mid </math>
::: Cherchons R tel que si lzl>R alors <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid <\mid \frac{a_n}{2} \mid</math> :
:::: <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid \geq \mid \frac{a_0}{z^n} \mid + \mid \frac{a_1}{z^{n-1}} \mid +\dots + \mid \frac{a_{n-1}}{z} \mid </math>
:::: <math> \mid \frac{a_{n-1}}{z} \mid < \mid \frac{a_n}{2n} \mid</math>si <math> \mid z \mid > \mid 2n \frac{a_{n-1}}{a_n} \mid </math> ... <math> \mid \frac{a_0}{z^n} \mid < \mid \frac{a_0}{z} \mid < \mid \frac{a_n}{2n} \mid </math> si <math> \mid z \mid > max(1, \mid 2n \frac{a_0}{a_n}\mid) </math> c'est à dire <math> \mid \frac{a_p}{z^{n-p}} \mid < \mid \frac{a_p}{z} \mid < \mid \frac{a_n}{2n} \mid </math> si <math> \mid z \mid > max (1, \mid 2n \frac{a_p}{a_n} \mid)</math> ∀ p ∈ [lO;nl[. Donc si <math> \mid z \mid > max (1, \mid 2n \frac{a_0}{a_n} \mid, \dots, \mid 2n \frac{a_{n-1}}{a_n} \mid=R ) </math> alors <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid <\mid \frac{a_n}{2} \mid</math>.
::: D'où si lzl>R, alors <math> f(z) > \mid z^n \mid \mid \mid a_n \mid - \mid \mid \frac{a_n}{2} \mid \mid </math>, soit <math> f(z)> \mid z^n \mid \mid \frac{a_n}{2} \mid </math>
::: Cherchons z tel que ∀ M, f(z)>M. Il suffit que lzl>R et lzln>lzl> 2M/lanl. D'où si <math> \mid z \mid > max(1, \frac{2M}{\mid a_n \mid}, \frac{2na_0}{a_n}, \dots, \frac{2na_{n-1}}{a_n})=r</math> alors f(z)>M, c'est à dire <math> \lim_{\mid z \mid \longmapsto \infty} f(z)=\infty </math>.

'' Graphiquement '': Soit D={z/ lzl<r}, pour tout z n'appartenant pas à D f(z)>M. En particulier, il n'existe pas z n'appartenant pas à D tel que f(z)=0; z ≥ r n'est pas une racine.
::* Montrons qu'il existe z0 ∈ D tel que f atteint son minimum en z0.
::#f(D) ⊂ lR+ donc f(D) est une partie de lR minorée par 0. Par l'axiome de la borne inférieure, f(D) admet une borne inférieure.
::# Montrons que Inf(f(D)) est atteinte.
::## C est compact donc on peut trouver une suite z0, z1... ∈ D telle que f(zn) tend vers Inf(f(D)) quand n tend vers + ∞ .
::## f est une fonction continue car P(z) est continue, et z → lzl est continue?
::## <math> f(\lim_{n \rightarrow \infty}z_n)=\lim_{n \rightarrow \infty}(f(z_n))=Inf(f(D)) </math>. Soit m=Inf(f(D)) et soit <math>l= \lim_{n \rightarrow \infty}z_n</math>, f(l)=m et l ∈ D. f atteint son minimum en l ∈ D.
::# Montrons par l'absurde que m=Inf(f(D))=f(l)=0, c'est à dire trouvons z tel que lP(z)l<m alors que par hypothèse c'est impossible. Supposons que P n'a pas de racine. Posons Q(z)=P(z-l) et g(z)=f(z-l)=lQ(z)l.
::## g atteint son minimum en 0. Q(z)=b0+bpzp+...+bnzn où bp est le plus petit coefficient non nul autre que b0 ≠ 0, et lb0l=m.
::## On cherche z tel que bpzp=-b0C où C ∈ lR+ ⇔ <math> z^p=-C \frac{b_0}{b_p}=\lambda e^{i\theta} \Leftrightarrow z=\lambda ^{1/p}e^{i\theta /p} </math>
::## lbp+1zp+1+...+bnznl ≤ lzpl(lbp+1zl+lbp+2z2l+...+lbnzn-pl) or lbp+1zl ≤ lbp/(2n)l si lzl ≤ lbp/(2bp+qn)l ... lbp+qzql ≤ lbp/(2n)l si lzl ≤ min(1,lbp/(2nbp+ql), c'est à dire lbp/1zp+1+...+bnznl ≤ lbnzpl/2 si lzl ≤ min(1,lbp/(2nbp+1)l,...lb0/bql)=r.
::## Si on prend lzl=r, z=rei θ et bpzp=-b0C où C ∈ lR+. bp(rei θ )p=-b0C, ei θ =-cb0/(rpbp)=Kei ω . Pour que K=1, on prend lCl=lrpbp/b0l. D'où z=rei arg(-b0/bp)/p.
::## Q(z)=b0+bpzp+ ε avec ε ≤ lbpzp/2l. D'où bpzp=bprpei arg(-b0/bp)=-lbplrpei arg(b0). D'où Q(z)=(lb0l-lbprpl)ei arg(b0)+ε, soit Q(z) ≤ (lb0l-lbprpl)ei arg(b0)+lεl ≤ lb0l-lbprpl+lεl<lb0l<m

'' Conclusion '': P a une racine z0 telle que lQ(0)l=lP(z0-l)l=m=0, c'est à dire que P a une racine z0=l ∈ D.

===Fonctions polynômes/Polynômes===
* Un ''' polynôme ''' de degré d est un élément de lRd+1 : P=(a0,a1,...,ad) est un '' vecteur ''.
Il est néanmoins possible de faire quelques opérations supplémentaires sur les polynômes :
:*+ sur des vecteurs de taille différente
:*division euclidienne
:*produit
:*dérivation
* ''' Fonction polynôme ''' :

Soit P un polynôme à coefficients dans lK=C, lR, Q, Z/pZ
P(x) est une foction de lK → lK qui a x associe a0+a1x+...adxd si P=(a0,a1,...,ad)
* ''' Egalité de deux polynômes ''' :

Dans lR, C et Q, deux polynômes sont égaux si et seulement si les fonctions associées sont égales.
Ce n'est pas le cas dans Z/pZ.

'' Exemple '': dans Z/2Z, P=1+X+X2 et Q=1, x ∈ {0;1}.
P(0)=Q(1)=1 et P(0)=P(1)=1 donc les fonctions sont égales bien que les polynômes soient différents.

'' Remarque '' : Il existe 4 polynômes de degré 2 dans Z/2Z.
* ''' Dérivation ''' :

P' est une opération formelle sur les coefficients car <math>\lim_{h \longmapsto 0} \frac{P(x+h)-P(x)}{h}</math> n'a pas de sens dans Z/pZ.

Si P=(a0,a1,...,ad) (d°=d), alors P'=(a1,2a2,...,dad) (d°=d-1)
* ''' PGCD et polynômes de Bezout ''' :
:* '' Plus grand '' diviseur commun : celui qui a le plus grand degré (donc plus grand à une constante multiplicative près)
:* ''Remarques '' :
:# Stathme : valeur absolue dans Z, degré d'un polynôme ∈ lN
:# Pour les polynômes, l'algorithme d'Euclide st la preuve de l'existence du PGCD
:* Algorithme d'Euclide : preuve par récurrence sur d°P+d°Q
:# 0 &and; Q=Q et P &and; 0=P
:# Si d°P+d°Q=0 : les deux polynômes sont constants, P &and; Q=1=P=Q et donc P &and; Q existe
:# Hypothèse de récurrence : On suppose que P' &and; Q' existe pour tout P' et pour tout Q' tels que d°P'+d°Q' ≤ d°P+d°Q. On a d°P+d°Q>0
:## Supposons d°Q ≥ d°P (sinon on échange P et Q). On effectue la division puissance croissante de Q par P : Q=SP+R où d°R<d°P. Soit D un polynôme : si D l P et D l Q alors D l SP-Q=R; si D l P et D l R alors D l SP+R=Q. Ainsi l'ensemble des diviseurs communs de P et Q est celui des diviseurs de P et R.
:## Par récurrence P &and; Q existe ( puisque d°P+d°Q<d°P+d°P ≤ d°P+d°Q)
:* Polynômes de Bezout
:# Si P &and; Q=D alors ∃ U, V deux polynômes tels que UP+VQ=D
:# '' Existence '' : On remonte l'algorithme (par récurrence sur d°P+d°Q)
:## Si P=0 et Q <math>\neq</math> 0 : 0.P+1.Q=Q=P &and;Q
:## Si P <math>\neq</math>0 et Q=0 : 1.P+0.Q=P=P &and; Q
:## Si d°P+d°Q=0 : <math>P=a\neq 0</math> et <math>Q=b\neq 0</math> : a-1.a+0.b=1=P &and; Q
:## Si d°P+d°Q>0 avec d°P ≤ d°Q : Q=SP+R. Par récurrence, on a trouvé U et V tels que UP+VR=P &and; Q= P &and; R soit (U-VS)P+VQ=P &and; Q

MATH203 : Introduction à l'algèbre

2008-03-10T11:57:43Z

Ebouv :

Feuilles de TD :
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD1-M2AL.pdf 1]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD2-M2AL.pdf 2]

== Que sont les mathématiques ==

En mathématique on étudie les propriétés d'objets tels que les nombres, les droites, ... Ces objets sont dénotés par des "expressions" comme
* x^2 - 1,
* Le milieu du segment [A,B],
* f est continue.

Chaque domaine des mathématiques possède son propre "voacabulaire" pour écrire des expressions et ce vocabulaire est introduit dans chacun de vos cours.

L'égalité joue un rôle particulier en mathématique car elle est "subtitutive" : si deux expressions a et b sont égales, on peut remplacer a
par b dans toute expression sans en changer la valeur. Il faut tout de même faire attention aux variables liées. Considérons l'exemple suivant:

Soit y un réel et x = y + 2, on a donc x - y = 2.
Pour <math>x \in \mathbb{R}</math>, définissons la fonction f(x) = x^2 - y^2 = (x - y)(x + y).
On a donc pour tout <math>x \in \mathbb{R}</math> f(x) = 2(x + y) (pour un x particulier).

On a commis une erreur car x est une variable liée dans la seconde phrase. On peut toujours changer le nom des variables liées et écrire

Soit y un réel et x = y + 2, on a donc x - y = 2.
Pour <math>z \in \mathbb{R}</math>, définissons la fonction f(z) = z^2 - y^2 = (z - y)(z + y).
On a donc f(x) = 2(x + y).

Parmis les expressions certaines sont des "énoncés", c'est à dire des expressions dont la valeur est vraie ou fausse comme
* x^2 - 1 = (x - 1)(x + 1)
* Les trois droites sont concourantes
* Toute fonction continue est dérivable (cet énoncé est faux, mais on peut l'écrire !)
Les mathématiques ont pour objet de découvrir quels énoncés sont vrais en partant uniquement "d'axiomes" qui sont des énoncés que l'on adment comme
vrais dans un domaine donné des mathématiques.

Tous les énoncés mathématiques peuvent être ecrit en utilisant les "briques" de construction suivantes :
* Des énoncés atomiques propre à chaque domaine des mathématique comme <math>x\in E</math>, "f est continue", ... Attention: certains énoncés atomiques peuvent être transformés en énoncés plus complexe en faisant appel à une définition (c'est le cas de "f est continue").
* l'implication : notée <math>A \Rightarrow B</math>, <math>A \rightarrow B</math>, A implique B, A est une condition suffisante pour B, B est une condition nécessaire pour A, si A alors B, ...

Attention, l'implication mathématique est très différente de l'implication en langage courant qui contient souvent une relation de cause à effet voire qui exprime une équivalence : "si tu ne mange pas ta soupe tu n'aura pas de déssert" est une équivalence en langue naturelle.

<math>A \Rightarrow B</math> est faux uniquement si A est vrai et B est faux. Dans les trois autres cas, l'implication mathématique est vraie. Pour ce persuader que c'est cela qu'il faut faire, considérer l'énoncé suivant (qui est bien vrai ?) :

Si n est divisible par 4 alors n est pair

* Pour n = 2 on obtient "Faux implique Vrai"
* Pour n = 3 on obtient "Faux implique Faux"
* Pour n = 4 on obitent "Vrai implique Vrai"

* La conjonction : notée "A et B", "<math>A \land B</math>", ... Le sens devrait être clair
* La disjonction : notée "A ou B", "<math>A \lor B</math>", ... C'est le ou usuel. A ou B est vrai si l'un des deux enoncés au moins est vrai. Il ne faut pas le confondre avec le "ou exclusif", utilisé en informatique, et qui est faux lorsque les deux énoncés sont vrais en même temps.
* La négation : notée "non A", "A est faux", "il est faux que A", "<math>\lnot A</math>", ... On a non A est vrai si et seulement si A est faux et donc aussi non A est faux si et seulement si A est vrai.
* L'équivalence : notée "A équivalent à B", "A si et seulement si B", "A est une condition nécessaire et suffisante pour B", "<math>A \Leftrightarrow B</math>", "<math>A \leftrightarrow B</math>". "<math>A \Leftrightarrow B</math>" peut être défini comme "(A implique B) et (B implique A)".
* La quantification universelle : notée "pour tout x A", "on a A pour tout x", "quelque soit x A", <math>\forall x A</math>, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.
* La quantification existentielle : notée "il existe x tel que A", "on a A pour au moins un x", "on peut trouver un x tel que A", <math>\exists x A</math>, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.

==Qu'est-ce qu'une preuve==

*''' Définitions ''' :
**Une preuve est un texte pour convaincre constitué d'une suite d'étapes telles qu'à chacune d'elles, on a :
:# des connaissances : liste d'objets connus, de théorèmes, d'hypothèses locales au problème
:# un but à démontrer
** Pour passe d'une étape à l'autre, on peut :
:# chercher à simplifier le but/le diviser
:# utiliser des connaissances pour progresser (montrer le but, obtenir de nouvelles connaissances, faire un lemme...)
*''' 6X2+2+... briques de bases ''' :
** Si le but est dans la liste des connaissances ou si A et ¬ A sont dans les connaissances, alors la preuve est finie.
** 6X2 briques de bases:
:# ''' Montrer que A=>B ''': Ajouter A aux hypothèses et montrer B / ''' Utiliser que A=B ''': Démontrer A pour pouvoir ajouter B aux connaissances
:# ''' Montrer que A et B ''' : Deux preuves dont l'ordre n'a pas d'importance / ''' Utiliser que A et B ''' : Rajouter A et B aux connaissances, et utiliser l'une et/ou l'autre
:# ''' Montrer que A ou B ''' : On montre A ou B, au choix / ''' Utiliser que A ou B ''' : Raisonner par disjonction de cas, on a alors deux preuves; rajouter A aux connaissances et montrer le but '' et '' rajouter B dans les connaissances et montrer le but
:# ''' Montrer que ¬ A ''' : Supposer A et chercher une contradiction / ''' Utiliser que ¬ A ''' : Montrer A et en déduire une contradiction
:# ''' Montrer que ∀ x, A ''' : Montrer A pour un x '' quelconque '' / ''' Utiliser que ∀ x, A ''' : Prendre le x qui nous intéresse et supposer A(x).
:# ''' Montrer que ∃ x, A ''' : Montrer A pour un x bien choisi / ''' Utiliser que ∃ x, A ''': Prendre un '' nouveau '' x et supposer A(x)
** ''' Démonstration par l'absurde ''' : Si le but est A, alors on suppose ¬ A et on cherche une contradiction (particulièrement fréquent pour montrer un '' ou '', '' ∃ '', ou un '' énoncé atomique ''.
** Il existe d'autres briques propres au domaine dans lequel on se place ('' exemple '' : preuve par récurrence en arithmétique)

==Ensembles, Fonctions, Relations==

*''' Théorie des ensembles '''
** ''' Schéma de compréhension ''' : {x ∈ A / P(x)} est l'ensemble des x de A qui ont la propriété P
** ''' Paradoxe de Russel ''' : Soit A={x / x <math> \notin </math> x}. Si A ∈ A alors A <math> \notin </math> A et si A <math> \notin </math> A alors A ∈ A. D'où une contradiction qui aboutit au théorème de Zermels et Frankel, modifiant le schéma de compréhension : {x '' ∈ A '' / ...}
** ''' Construction des ensembles ''' :
:# A ∪ B={x / x ∈ A ou x ∈ B}
:# A ∩ B={x / x ∈ A et x ∈ B}
:# Ac={x <math> \notin </math> A}
:# A-B=A ∩ Bc={x / x ∈ A et x <math> \notin </math> B}
:# P(A) : ensemble des parties de A; B ∈ P(A) si et seulement si B ⊂ A ⇔ ∀ x (x ∈ B ⇒ x ∈ A)
:# AXB où X est appelé produit cartésien : ensemble de couples; {(a,b) P(P(A ∪ B)) / a ∈ A b ∈ B}
** ''' Inverse d'une relation R ''' : Soit R ⊂ P(AXB), on peut '' toujours '' définir R-1. R-1={(b,a) / b ∈ B, a ∈ A, et (a,b) ∈ R}
*''' Fonction de A dans B ''' :
** notée A → B, F(A,B)
** F(A,B)=déf{R ⊂ (AXB) / ∀ a ∈ A ∀ b, b' ∈ B, ((aRb) et (aRb')) ⇒ (b=b')}
** Si f ∈ F(A,B), on écrit b=f(a).
*''' Application de A dans B ''' :
** notée A'A,B) ou BA
** A(A,B)={f ∈ F(A,B) / ∀ a ∈ A ∃ b ∈ B tel que b=f(a)}
*''' Restriction ''' : Soient f ∈ F(A,B) et A' ⊂ A, fl`A' ∈ F(A',B)={(a,b) / a ∈ A' et b=f(a)}
*''' Image directe ''' : Soient f ∈ F(A,B) et A' ⊂ A, f(A')={b ∈ B / ∃ a ∈ A' b=f(a)}
*''' Image réciproque ''' : Soient f ∈ F(A,B) et B' ⊂ B f-1(B')={a ∈ A / f(a) ∈ B' }
*''' Inclusion ''' : A ⊂ B ⇔ (x ∈ A ⇒ x ∈ B)
*''' Injection ''' :
** notée parfois A <math>\hookrightarrow </math> B
** Soit f une application de A dans B, ∀ a, a' ∈ A (f(a)=f(a') ⇒ a=a') ⇔ f est injective.
*''' Surjection ''' : Soit f une application de A dans B. ∀ b ∈ B ∃ a ∈ A tel que b=f(a) ⇔ f est surjective.
*''' Bijection ''' : (∀ a ∈ A ∃! b ∈ B tel que b=f(a) et ∀ b ∈ B ∃! a ∈ A tel que b=f(a)) ⇔ f est bijective (f est alors injective '' et '' surjective).
*''' Composition ''' :
** Soient f ∈ F(A,B) et g ∈ F(B,C). gof(x) ∈ F(A,C) est définie par gof(x)=g(f(x)).
** fog injective, g surjective ⇒ f injective
: fog surjective, f injective ⇒ g surjective
: fog injective ⇒ g injective
: fog surjective ⇒ f surjective
*''' Relation d'ordre large ''' : ≤ ≥ ⊂ divise dans lN

R ⊂ (AXA) est d'ordre large si et seulement si elle est :
:# '' réflexive '' : ∀ a ∈ A aRa
:# '' antisymétrique '' : ∀ a, a' ∈ A (aRa' et a'Ra) ⇒ a=a'
:# '' transitive '' : ∀ a, b, c ∈ A (aRb et bRc) ⇒ aRc
*''' Relation d'équivalence ''' : =, ⇔, avoir même reste dans la division par n

R ⊂ (AXA) est d'équivalence si et seulement si elle est :
:# '' réflexive '' : ∀ a ∈ A aRa
:# '' symétrique '' : ∀ a, a' ∈ A aRa' ⇒ a'Ra
:# '' transitive '' : ∀ a, b, c ∈ A (aRb et bRc) ⇒ aRc
*''' Quotients '''
** ''' Définition ''' : On a un ensemble E et &equiv; une relation d'équivalence sur E. Le quotient de E par &equiv; noté E/&equiv; est l'ensemble des classes d'équivalence de &equiv;.
** ''' Classe d'équivalence ''' : La classe d'équivalence de x est x={y ∈ E / x &equiv; y} ⇔ ∀ a ∈ E (a ∈ x ⇔ a &equiv; x)
** ''' Propriétés ''' : Soient E un ensemble et &equiv; une relation d'équivalence sur E.
:# ∀ x, y ∈ E (x &equiv; y ⇔ x=y)
:# L'ensemble des classes d'équivalence est une partition de E
** ''' Construction de l'ensemble des rationnels par quotient ''' : Q={(n,d) l n∈Z, d∈lN*}, soit &equiv; / ((n,d) &equiv; (n',d') ⇔ nd'=n'd). &equiv; est une relation d'équivalence, et l'ensemble des rationnels est le quotient de Q par &equiv;.
** ''' Relever une opération sur le quotient '''
** ''' Loi interne ''' : f:EXE → E telle que si x &equiv; x' et y &equiv; y' alors f(x,y) &equiv; f(x',y').

==Arithmétique==

*''' Récurrence '''
** ''' Principe '''
** ''' Récurrence généralisée '''
*''' Division euclidienne '''
** ''' Définition '''
** ''' Preuve de l'existence et de l'unicité par récurrence sur p ≥ 0 '''
*''' Divisibilité '''
*''' PGCD '''
** ''' Signification '''
** ''' Preuve de l'existence '''
** ''' Algorithme d'Euclide '''
:# '' Propriétés ''
:# '' Description ''
:# '' Autre algorithme ''
*''' Théorème de Bezout '''
** ''' Enoncé '''
** ''' Preuve '''
** ''' Corollaire '''
** ''' Réciproque '''
*''' Théorème de Gauss '''
** ''' Enoncé '''
** ''' Preuve '''
*''' Nombres premiers et décomposition '''
** ''' Définition '''
** ''' Corollaire du théorème de Gauss '''
** ''' Théorème de décomposition '''

==Arithmétique modulaire==

*''' Définition de la congruence modulo n '''
** ''' Congruence ''' : relation d'équivalence
** ''' Notation ''' : a&equiv;nb a&equiv;b(mod n) a=b(mod n)
** a&equiv;nb ⇔ b-a est un multiple de n
** a&equiv;nb ⇔ a%n=b%n
** Z/nZ est le quotient de Z par la relation d'équivalence modulo n.
:# a&equiv;na%n
:# Z/nZ={0,1,2,...,n-1} est un ensemble fini à n éléments.
:# Z/nZ est un anneau commutatif non intègre. Tout élément non nul de Z/nZ est inversible si et seulement si n est premier. On note alors Z/nZ=Z/pZ.
*''' Petit théorème de Fermat '''
** ''' Enoncé ''': '' <math>a^p = a \pmod p</math> si <math>p \in \mathbb N</math> est premier.'' Ceci peut aussi s'écrire
<math>a^{p-1} = 1 \pmod p</math> mais il faut alors que <math>p</math> ne divise pas <math>a</math>.
** ''' Preuve ''' : Dans (Z/pZ-{0},X) groupe à p-1 éléments, on veut montrer que ap-1=1(mod p).
: ∃ m tel que am=1. {an/n ∈ Z} est un sous groupe de Z/pZ fini, d'où ∃ n' tel que an=an' or p est premier donc an' a un inverse. D'où an-n'=1 ou an'-n=1.
: Montrons que le plus petit n tel que an=1 divise p-1 (théorème de Lagrange). On '' partitionne '' Z/pZ en une famille d'ensembles de '' même cardinal '' que {an}, tout élément de Z/pZ peut s'écrire sous la forme α a θ .
:: La donnée d'une telle partition revient à donner une relation d'équivalence sur Z/pZ : β R γ ⇔ ∃ e ∈ Z tel que β = γ α e.
::: R est réflexive : β=β α 0 d'où β R β
::: R est symétrique : ∃ e tel que β = γ α e donc γ=βα-e car α est inversible, d'où si β R γ alors γ R β
::: R est transitive : ∃ e,f tels que β = γ α e et γ=δ αf implique β = δ α e+f, donc si β R γ et γ R δ alors β R δ
:: 1={1,a,a2,...an-1}=A et b={b,ab,a2b,...an-1b}=B. Soit f:A→B telle que f(x)=xb, f-1(x)=xb-1. fof-1=id et f-1of=id donc f est bijective. Il en résulte que chaque classe est de taille n, d'où n l p-1.
: n l p-1 ⇒ ∃ q ∈ Z tel que p-1=qn et an=1 ⇒ ap-1=aqn=(an)q=1

==Compléments sur les polynômes==

* ''' FTA ou théorème de d'Alembert ''' :
** ''' Enoncé ''': '' Tout polynôme de degré supérieur ou égal à 1 à coefficients dans C a au moins un racine dans C. ''
** ''' Preuve ''' :
: Soient <math> (z)=a_0+a_1z+ \dots +a_nz^n</math> un polynôme à coefficients dans C[z] et f:C → lR telle que f(z)=lP(z)l
:Montrons que P admet une racine dans C.
::*** Montrons que <math> \lim_{\mid z \mid \longmapsto \infty} f(z)=\infty </math> :
::: On a <math> f(z)=\mid z^n (\frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} + a_n) \mid </math>, or labl=lallbl, d'où :

<math> f(z)= \mid z^n \mid \mid a_n + (\frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z}) \mid </math> or la+bl ≥ llal-lbll, d'où :

<math> f(z) \geq \mid z^n \mid \mid \mid a_n \mid - \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid \mid </math>
::: Cherchons R tel que si lzl>R alors <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid <\mid \frac{a_n}{2} \mid</math> :
:::: <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid \geq \mid \frac{a_0}{z^n} \mid + \mid \frac{a_1}{z^{n-1}} \mid +\dots + \mid \frac{a_{n-1}}{z} \mid </math>
:::: <math> \mid \frac{a_{n-1}}{z} \mid < \mid \frac{a_n}{2n} \mid</math>si <math> \mid z \mid > \mid 2n \frac{a_{n-1}}{a_n} \mid </math> ... <math> \mid \frac{a_0}{z^n} \mid < \mid \frac{a_0}{z} \mid < \mid \frac{a_n}{2n} \mid </math> si <math> \mid z \mid < max(1, \mid 2n \frac{a_0}{a_n}\mid) </math> c'est à dire <math> \mid \frac{a_p}{z^{n-p}} \mid < \mid \frac{a_p}{z} \mid < \mid \frac{a_n}{2n} \mid </math> si <math> \mid z \mid > max (1, \mid 2n \frac{a_p}{a_n} \mid)</math> ∀ p ∈ [lO;nl[. Donc si <math> \mid z \mid > max (1, \mid 2n \frac{a_0}{a_n} \mid, \dots, \mid 2n \frac{a_{n-1}}{a_n} \mid=R ) </math> alors <math> \mid \frac{a_0}{z^n} +\frac{a_1}{z^{n-1}} +\dots + \frac{a_{n-1}}{z} \mid <\mid \frac{a_n}{2} \mid</math>.
::: D'où si lzl>R, alors <math> f(z) > \mid z^n \mid \mid \mid a_n \mid - \mid \mid \frac{a_n}{2} \mid \mid </math>, soit <math> f(z)> \mid z^n \mid \mid \frac{a_n}{2} \mid </math>
::: Cherchons z tel que ∀ M, f(z)>M. Il suffit que lzl>R et lzln>lzl> 2M/lanl. D'où si <math> \mid z \mid > max(1, \frac{2M}{\mid a_n \mid}, \frac{2na_0}{a_n}, \dots, \frac{2na_{n-1}}{a_n})=r</math> alors f(z)>M, c'est à dire <math> \lim_{\mid z \mid \longmapsto \infty} f(z)=\infty </math>.

'' Graphiquement '': Soit D={z/ lzl<r}, pour tout z n'appartenant pas à D f(z)>M. En particulier, il n'existe pas z n'appartenant pas à D tel que f(z)=0; z ≥ r n'est pas une racine.
::*** Montrons qu'il existe z0 ∈ D tel que f atteint son minimum en z0.
::#f(D) ⊂ lR+ donc f(D) est une partie de lR minorée par 0. Par l'axiome de la borne inférieure, f(D) admet une borne inférieure.
::# Montrons que Inf(f(D)) est atteinte.
::## C est compact donc on peut trouver une suite z0, z1... ∈ D telle que f(zn) tend vers Inf(f(D)) quand n tend vers + ∞ .
::## f est une fonction continue car P(z) est continue, et z → lzl est continue?
::## <math> f(\lim_{n \rightarrow \infty}z_n)=\lim_{n \rightarrow \infty}(f(z_n))=Inf(f(D)) </math>. Soit m=Inf(f(D)) et soit <math>l= \lim_{n \rightarrow \infty}z_n</math>, f(l)=m et l ∈ D. f atteint son minimum en l ∈ D.
::# Montrons par l'absurde que m=Inf(f(D))=f(l)=0, c'est à dire trouvons z tel que lP(z)l<m alors que par hypothèse c'est impossible. Supposons que P n'a pas de racine. Posons Q(z)=P(z-l) et g(z)=f(z-l)=lQ(z)l.
::## g atteint son minimum en 0. Q(z)=b0+bpzp+...+bnzn où bp est le plus petit coefficient non nul autre que b0 ≠ 0, et lb0l=m.
::## On cherche z tel que bpzp=-b0C où C ∈ lR+ ⇔ <math> z^p=-C \frac{b_0}{b_p}=\lambda e^{i\theta} \Leftrightarrow z=\lambda ^{1/p}e^{i\theta /p} </math>
::## lbp+1zp+1+...+bnznl ≤ lzpl(lbp+1zl+lbp+2z2l+...+lbnzn-pl) or lbp+1zl ≤ lbp/(2n)l si lzl ≤ lbp/(2bp+qn)l ... lbp+qzql ≤ lbp/(2n)l si lzl ≤ min(1,lbp/(2nbp+ql), c'est à dire lbp/1zp+1+...+bnznl ≤ lbnzpl/2 si lzl ≤ min(1,lbp/(2nbp+1)l,...lb0/bql)=r.
::## Si on prend lzl=r, z=rei θ et bpzp=-b0C où C ∈ lR+. bp(rei θ )p=-b0C, ei θ =-cb0/(rpbp)=Kei ω . Pour que K=1, on prend lCl=lrpbp/b0l. D'où z=rei arg(-b0/bp)/p.
::## Q(z)=b0+bpzp+ ε avec ε ≤ lbpzp/2l. D'où bpzp=bprpei arg(-b0/bp)=-lbplrpei arg(b0). D'où Q(z)=(lb0l-lbprpl)ei arg(b0)+ε, soit Q(z) ≤ (lb0l-lbprpl)ei arg(b0)+lεl ≤ lb0l-lbprpl+lεl<lb0l<m

'' Conclusion '': P a une racine z0 telle que lQ(0)l=lP(z0-l)l=m=0, c'est à dire que P a une racine z0=l ∈ D.

MATH203 : Introduction à l'algèbre

2008-03-09T21:13:40Z

Ebouv :

MATH203 : Introduction à l'algèbre

2008-03-09T21:11:54Z

Ebouv :

MATH206 : Probabilités et Statistiques

2008-01-29T07:48:57Z

Ebouv :

Feuilles de TD :
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD1-MATH206.pdf 1]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD2-MATH206.pdf 2]

==Vocabulaire de probabilité==

* ''' Population ''' : Groupe d'objets étudiés. Elle peut-être :
**"réelle" : les Français, les étudiants de ce cours...
** "virtuelle" : l'ensemble des lancés de dés possibles...
* '''Sous-population, échantillon '''
* '''Expérience ''' : Choisir un élément dans une population.
* '''Evénement''' : L'événement se produit lorsque l'élément appartient à la sous-population.
* '''Partition ''' : Découpage d'un ensemble en plusieurs sous-ensembles disjoints.
* '''Cardinal ''' : Nombre d'éléments d'un ensemble.
* '''Fréquence ''' d'un sous ensemble A ⊂ Ω : <math> F(A)=\frac{\displaystyle {card(A)}}{\displaystyle{card}(\Omega)} </math>
* '''Variable aléatoire ''' et ''' Série statistique ''' : Application d'une population Ω dans un ensemble X quelconque.

==Estimateur ponctuel==

* '''Moyenne ''' et '''espérance''' (rappel et "sens")
Formule de la moyenne (resp. espérance) d'une série statistique (resp. variable aléatore) X sur un population <math>\Omega</math>:
<math>\displaystyle M(X) = E(X) = \frac{\sum_{i \in \Omega} X_i}{Card(\Omega)}</math>
La moyenne est le nombre x qui remplace le mieux <math>X_i</math> pour l'ensemble de la population quand on regarde l' '''erreur quadratique'''
donnée par la formule suivante (preuve facile en dérivant f):
<math>\displaystyle f(x) = \sum_{i \in \Omega} (X_i - x)^2</math>

On définit deux types d'erreurs :
# ''' l'erreur absolue ''' : <math> \mid X_i -xi \mid </math>
# ''' l'erreur quadratique ''' : <math> (X_i -x)^2 </math>

L'erreur quadratique est aussi liée à la variance V(X) car:

<math>\displaystyle V(X) = \frac{\sum_{i \in \Omega} (X_i - E(X))^2}{Card(\Omega)} = \frac{f(E(x))}{Card(\Omega)}</math>

''Rappel'' : On a aussi <math>V(X) = E(X^2) - E(X)^2</math>

* Propriété de la moyenne (linéarité) : E(X + Y) = E(X) + E(Y) et E(aX) = aE(X)

* Définition d'estimateur et de biais :

Un '''estimateur''' est une "formule" permettant de calculer un nombre à partir de la variable aléatoire restreinte à un échantillon.

Un estimateur estime un paramètre P(X) si il converge vers P(X) lorsque la taille de l'échantillon tend vers la taille de la population
(cela n'a guère se sens que sur les populations infinies ...)

Un estimateur pour P(X) est '''sans biais''', si son espérance est égale à P(X) lorsqu'on le considère comme une variable aléatoire sur la population des échantillons de taille n fabriquée à partir de <math>\Omega</math> (notée <math>\Omega^{(n)}</math>).

** Estimateur de la moyenne : la moyenne sur l'échantillon est un estimateur sans biais de la moyenne sur la population entière. Soit A={1;...;n} l'échantillon, <math>e(X)=\frac{\sum_{i \in A} X_i}{n} </math>

Démonstration :
<math> E ( \frac{\sum_{i \in A} X_i}{n} ) = \frac{1}{n} E(\sum_{i \in A} X_i)= \frac{1}{n} \sum_{i \in A} E(X_i)=\frac{1}{n} \times n E(X) =E(X) </math>

** Estimateur de la variance (avec et sans remise) :

Si on note <math>\sigma^2</math> la variance d'un échantillon de taille n dans une population de taille N, on obtient un estimateur sans biais
de la variance avec les formules suivantes:

<math>\displaystyle \frac{n}{n-1}\sigma^2</math> dans le cas de tirage avec remise de l'échantillon

<math>\displaystyle \frac{N-1}{N} \frac{n}{n-1}\sigma^2</math> dans le cas de tirage sans remise (qui vaut bien <math>\sigma^2</math> lorque n = N).
Démonstration :
'' Rappel préalable : '' <math> V(X)=E( (X-E(X))^2)= E (X^2 -2XE(X)+E(X)^2)=E(X^2)-2E(X)E(X)+E(x)^2=E(X^2)-E(X)^2 </math>
'' Calcul préalable : '' Soit X une variable aléatoire sur &Omega, soient X1 et X2 deux variables aléatoires.
** avec remise : <math> E(X_1X_2)= \frac{1}{N^2} \left( \sum_{i,j \in \Omega} X_iX_j \right)=E(X)^2 </math>
** sans remise : <math> E(X_1X_2)=\frac{\sum_{i,j \in \Omega ; i \neq j }X_iX_j}{N(N-1)} = \frac{\sum_{i,j \in \Omega}X_iX_j - \sum_{i \in \Omega}X_i^2}{N(N-1)}=\frac{ \left( \sum_{i \in \Omega} X_i \right) ^2 - \sum_{i \in \Omega }X_i^2}{N(N-1)}= E(X)^2 \frac{N}{N-1} - \frac{E(X^2)}{N-1}</math>
Soit Ω une population de taille N, soit X une variable aléatoire sur Ω, on s'intéresse aux échantillons de taille n.
On a V(x) variance de la population et <math>\sigma^2</math> la variance d'un échantillon A de taille n.
<math> \sigma^2 (A)=\frac{\sum_{i \in A} \left( X_i- \frac{\sum_{i \in A}X_i}{n} \right) ^2}{n}= \frac{n-1}{n} \sum_{i \in A} (X_i^2) - \frac{\sum_{i \neq j \in A} X_iX_j}{n^2}</math> D'où
<math> E(\sigma^2(A))=\frac{n-1}{n^2} \sum_{i \in A} E(X_i^2) - \frac{1}{n^2} \sum_{i \neq j \in A} E(X_iX_j)= \frac{n-1}{n} E(X^2) - \frac{n-1}{n} E(X_1X_2)</math>
** avec remise : <math> E(\sigma^2(A))= \frac{n-1}{n} (E(X^2) - E(X)^2)= \frac{n-1}{n} V(X) </math>
** sans remise : <math> E(\sigma^2(A))= \frac{n-1}{n} (E(X^2) - E(X)^2 \frac{N}{N-1} + \frac{E(X^2)}{N-1})= \frac{n-1}{n} \frac{N}{N-1}V(X) </math>

On prend donc en général, pour estimateur sans biais de V(X) sur un échantillon <math>A \subset \Omega</math> la valeur appelée variance empirique de Y :
<math>\displaystyle \sigma'^2 = \frac{1}{Card(A)-1}\sum_{i \in A} (y_i - \overline y)^2</math>

Remarque: pour faire le calcul pour l'estimateur de variance, le point principal est de calculer l'espérance de <math>X_1X_2</math> où <math>X_1</math> et <math>X_2</math> sont deux variables aléatoires obtenues à partir d'une variable aléatoire X en choisissant deux individus au hasard. On a besoin de faire ce calcul à la fois pour un choix de deux individus avec remise et sans remise.

==Un peu de dénombrement==

* Cardinal du '''produit cartésien ''': le produit des cardinaux.

* Tirage '''sans ordre et sans remise ''' de p parmi n, c-à-d nombre de parties à p éléments d'un ensemble à n éléments :

<center><math>\displaystyle C^p_n</math></center>
Démonstration :
On veut choisir p+1 éléments parmi n+1, sans ordre, sans remise. Soit <math> E_n^p </math> l'ensemble des parties à p éléments de {1;...;n}.
<math> E_{n+1}^{p+1}= F_{n+1}^{p+1} \cup G_{n+1}^{p+1}</math> de sorte que <math> F_{n+1}^{p+1} </math> est l'ensemble des p+1 éléments qui contiennent n+1,
et <math> G_{n+1}^{p+1} </math> est l'ensemble des p+1 éléments qui ne contiennent pas n+1. On a <math> F_{n+1}^{p+1} \cap G_{n+1}^{p+1} = \emptyset</math>.
D'autre part <math> G_{n+1}^{p+1}=E_{n}^{p+1} </math>. Soit f: <math> E_n^p \rightarrow F_{n+1}^{p+1}</math>, <math> card(E_{n+1}^{p+1})=card(E_n^p) + card(E_n^{p+1})</math>
''Remarque : '' Deux ensembles en bijection ont le même cardinal.

* Tirage '''avec ordre et sans remise ''' de p parmi n, c-à-d nombre de p-uplets d'un ensemble à n éléments (nombre d'injections de {1;...;p} dans un ensemble à n éléments) :

<center> <math>\displaystyle A^p_n</math></center>
Démonstration:
Soit <math> A_n^p </math> le nombre d'injection, <math> A_n^1=n </math> et <math> A_{n+1}^{p+1}=(n+1) \times A_n^p</math>.
D'où <math> A_n^p= n A_{n-1}^{p-1}=n(n-1)(n-2) ... (n-p+1) </math>

* Tirage '''avec ordre et avec remise ''' de p parmi n, c-à-d nombre de tirage avec remise et avec ordre de p-élemnts parmis n (nombre d'applications de {1;...;p} dans un ensemble à n éléments) :

<center><math>n^p</math></center>
Démonstration :
<math> card(E \times E \times E \times ... \times E)=(cardE)^p=n^p </math>

* Tirage '''sans ordre et avec remise ''' de p parmi n :

<center><math>\displaystyle C^{p}_{n+p-1} = C^{n-1}_{n+p-1}</math></center>
Démonstration : 
On place n-1 jetons dans n+p-1 cases, il reste p cases libres. Il y a <math> C_{n+p-1}^{n-1}=C_{n-1+p}^{p}</math> choix.
Soit f: <math> E \rightarrow \begin{Bmatrix}0;\dots;p\end{Bmatrix} </math> soit f associe à x le nombre de fois où x a été choisi.
On a <math> \sum_{x \in E} f(x)=p</math>, ce qui revient à n-1 jetons et p cases vides.

<center> Choix de p éléments parmi n 
<table border="1">
<tr> <th> Ordre\Remise </th> <th> Sans (0≤p≤n) </th> <th> Avec (0≤p)</th>
</tr>
<tr> <th> Sans </th> <td> <math>\displaystyle C^p_n</math> </td> <td> <math>\displaystyle C^p_{n+p-1}</math></td> </tr>
<tr> <th> Avec </th> <td> <math>\displaystyle A^p_n</math> </td> <td> <math> n^p </math> </td> </tr>
</table>
</center>

'' Rappel des formules usuelles pour les coefficients binomiaux :''

* avec factorielle : <math>\displaystyle C^p_n = \frac{A^p_n}{p!} = \frac{n!}{(n-p)!p!} = \frac{n(n-1)...(n-p+1)}{p!}</math>
* triangle de Pascal : <math>\displaystyle C^0_n = C^n_n = 1, C^{n-p}_n = C^p_n</math> et <math>\displaystyle C^{p+1}_{n+1} = C^p_n + C^{p+1}_n (0 \leq p \leq n - 1)</math>
* Formule du binôme de Newton et applications comme <math>\displaystyle \sum_{p=0}^n C^p_n = 2^n</math>.

Démonstration : 
Soit <math> f(x)=(x+1)^n </math>, <math> f(x)= \sum_{p=0}^n C_n^p x^p</math>. En particulier, f(1)=2n.

==Probabilité et lois usuelles==

* ''' Probabilité ''' (ou loi de probabilité) sur un ensemble <math>\Omega</math>: un nombre associé P(E) aux sous-ensembles <math>E \subset \Omega</math> d'un ensemble (pas toujours tous les sous-ensembles) tel que :
** <math>P(\emptyset) = 0</math>
** <math>P(\Omega) = 1</math>
** <math>P(E \cup F) = P(E) + P(F)</math> si <math>E \cap F = \emptyset</math>
:: '' Conséquences : ''
:::μ (A C)=1- μ (A)
::: <math>[(A \Rightarrow B) \Leftrightarrow (A \subset B)] \Rightarrow \mu (B) \geq \mu (A)</math>
::: <math> \mu (A \cup B)= \mu (A) + \mu (B) - \mu (A \cap B)</math> si A et B non disjoints.
* ''' Évènements = Sous-ensemble ''' . Evénements certains, impossibles, incompatibles. Implication entre évènement et inégalité sur les probas.
* Cas des ensembles finis et probabilité uniforme :
: Pour '' définir une loi de probabilité sur un ensemble fini '' Ω, il suffit de donner la probabilité des singletons.
Démonstration : 
A={x1;...;xn} avec n=card(A). A={x1} ∪ {x2} ∪ ... ∪ {xn} où les singletons sont disjoints.
D'où μ (A)= μ (x1) + ... + μ (xn). Donner une loi sur Ω fini, c'est donner μ (x) pour tout x de Ω.

: La '' loi de probabilité uniforme '' sur Ω fini est l'unique probabilité sur Ω telle que μ (x)=p pour tout x dans Ω avec <math>p=\frac{1}{card(\Omega)} </math>.
Démonstration : 
Ω = {x1;...;xN} avec N=card(Ω). D'où μ (Ω)= μ (x1) + ... + μ (xN)=Np. Or μ (Ω)=1. Donc p=1/N.

: Si A ⊂ Ω et μ est une loi de probabilité uniforme sur Ω alors <math>\mu (A)=\frac{ card(A) }{card( \Omega )} </math>.
Démonstration : 
N=card(Ω) et n=card(A) où A={x1;...; xn</sub}.
On a <math> \mu (A)= \sum_{i=1}^n \mu (x_i)=\sum_{i=1}^n \frac{1}{N}=\frac{n}{N}</math>.

* ''' Loi image ''' (image réciproque d'un ensemble Ω dans Ω') :

Soit X une variable aléatoire sur Ω, à valeurs dans Ω' (X fonction de Ω dans Ω'). On a une loi μ sur Ω. On construit une loi sur Ω', image de μ par X et notée μX. On a pour A inclus dans Ω μ (A)=μ (X-1(A)).

Si Ω est un ensemble ordonné et μ une loi sur Ω, on définit F la ''' fonction de répartition ''' telle que <math> x \in \Omega , F(x)= \mu ( \{ a \in \Omega \mid a \leq x \} )</math>. F est croissante et tend vers 1.
Démonstration :
Si x ≤ y ∈ Ω et {a/ a ≤ x} ⊂ {a/a ≤ y } alors μ ({a/a ≤ x}) ≤ μ ({a/a ≤ y}); d'où F(x) ≤ F(y).

* ''' Variable aléatoire discrète '''
* Lois discrètes usuelles
** '''Loi indicatrice''' ou '''loi de Bernouilli ''' (I(p)) :

Soit X une variable aléatoire sur Ω à valeurs dans {0;1}. X(x)=1 si et seulement si x ∈ E ⊂ Ω (E=X-1(1)).

Cette loi est déterminée par μ X (1)= μ (E)=p (d'où μ X (0)= μ (EC)=1-p).

::: Espérance : E(X)=p
::: Variance : V(X)=p(1-p)
::: Ecart-type : <math>\sigma (X)=\sqrt{p(1-p)} </math>

** '''Loi de Pascal''' (Pa(p)) :

Ω est muni d'une loi uniforme, E ∈ Ω est un événement. On réalise plusieurs expériences '' indépendantes'' jusqu'à obtenir un succès. Soit X le nombre total d'expériences (succès inclus). X est à valeurs dans lN*.

Cette loi est déterminée par μ (E)=p ∈ ]0;1[; μ (X=k)=(1-p) k-1p ∈ ]0;1[.

::: Espérance : E(X)=1/p
::: Variance : V(X)=1/(p2)
::: Ecart-type : <math>\sigma (X)=1/p </math>
** Loi binomiale
** Loi hypergéométrique
** Loi de Poisson
* Lois continues

==Théorème de la limite centrale==

==Intervalle de confiance==

MATH206 : Probabilités et Statistiques

2008-01-28T22:56:29Z

Ebouv :

Feuilles de TD :
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD1-MATH206.pdf 1]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD2-MATH206.pdf 2]

==Vocabulaire de probabilité==

* ''' Population ''' : Groupe d'objets étudiés. Elle peut-être :
**"réelle" : les Français, les étudiants de ce cours...
** "virtuelle" : l'ensemble des lancés de dés possibles...
* '''Sous-population, échantillon '''
* '''Expérience ''' : Choisir un élément dans une population.
* '''Evénement''' : L'événement se produit lorsque l'élément appartient à la sous-population.
* '''Partition ''' : Découpage d'un ensemble en plusieurs sous-ensembles disjoints.
* '''Cardinal ''' : Nombre d'éléments d'un ensemble.
* '''Fréquence ''' d'un sous ensemble A ⊂ Ω : <math> F(A)=\frac{\displaystyle {card(A)}}{\displaystyle{card}(\Omega)} </math>
* '''Variable aléatoire ''' et ''' Série statistique ''' : Application d'une population Ω dans un ensemble X quelconque.

==Estimateur ponctuel==

* '''Moyenne ''' et '''espérance''' (rappel et "sens")
Formule de la moyenne (resp. espérance) d'une série statistique (resp. variable aléatore) X sur un population <math>\Omega</math>:
<math>\displaystyle M(X) = E(X) = \frac{\sum_{i \in \Omega} X_i}{Card(\Omega)}</math>
La moyenne est le nombre x qui remplace le mieux <math>X_i</math> pour l'ensemble de la population quand on regarde l' '''erreur quadratique'''
donnée par la formule suivante (preuve facile en dérivant f):
<math>\displaystyle f(x) = \sum_{i \in \Omega} (X_i - x)^2</math>

On définit deux types d'erreurs :
# ''' l'erreur absolue ''' : <math> \mid X_i -xi \mid </math>
# ''' l'erreur quadratique ''' : <math> (X_i -x)^2 </math>

L'erreur quadratique est aussi liée à la variance V(X) car:

<math>\displaystyle V(X) = \frac{\sum_{i \in \Omega} (X_i - E(X))^2}{Card(\Omega)} = \frac{f(E(x))}{Card(\Omega)}</math>

''Rappel'' : On a aussi <math>V(X) = E(X^2) - E(X)^2</math>

* Propriété de la moyenne (linéarité) : E(X + Y) = E(X) + E(Y) et E(aX) = aE(X)

* Définition d'estimateur et de biais :

Un '''estimateur''' est une "formule" permettant de calculer un nombre à partir de la variable aléatoire restreinte à un échantillon.

Un estimateur estime un paramètre P(X) si il converge vers P(X) lorsque la taille de l'échantillon tend vers la taille de la population
(cela n'a guère se sens que sur les populations infinies ...)

Un estimateur pour P(X) est '''sans biais''', si son espérance est égale à P(X) lorsqu'on le considère comme une variable aléatoire sur la population des échantillons de taille n fabriquée à partir de <math>\Omega</math> (notée <math>\Omega^{(n)}</math>).

** Estimateur de la moyenne : la moyenne sur l'échantillon est un estimateur sans biais de la moyenne sur la population entière. Soit A={1;...;n} l'échantillon, <math>e(X)=\frac{\sum_{i \in A} X_i}{n} </math>

Démonstration :
<math> E ( \frac{\sum_{i \in A} X_i}{n} ) = \frac{1}{n} E(\sum_{i \in A} X_i)= \frac{1}{n} \sum_{i \in A} E(X_i)=\frac{1}{n} X n E(X) =E(X) </math>

** Estimateur de la variance (avec et sans remise) :

Si on note <math>\sigma^2</math> la variance d'un échantillon de taille n dans une population de taille N, on obtient un estimateur sans biais
de la variance avec les formules suivantes:

<math>\displaystyle \frac{n}{n-1}\sigma^2</math> dans le cas de tirage avec remise de l'échantillon

<math>\displaystyle \frac{N-1}{N} \frac{n}{n-1}\sigma^2</math> dans le cas de tirage sans remise (qui vaut bien <math>\sigma^2</math> lorque n = N).
Démonstration :
'' Rappel préalable : '' <math> V(X)=E( (X-E(X))^2)= E (X^2 -2XE(X)+E(X)^2)=E(X^2)-2E(X)E(X)+E(x)^2=E(X^2)-E(X)^2 </math>
'' Calcul préalable : '' Soit X une variable aléatoire sur &Omega, soient X1 et X2 deux variables aléatoires.
** avec remise : <math> E(X_1X_2)= \frac{1}{N^2} \left( \sum_{i,j \in \Omega} X_iX_j \right)=E(X)^2 </math>
** sans remise : <math> E(X_1X_2)=\frac{\sum_{i,j \in \Omega ; i \neq j }X_iX_j}{N(N-1)} = \frac{\sum_{i,j \in \Omega}X_iX_j - \sum_{i \in \Omega}X_i^2}{N(N-1)}=\frac{ \left( \sum_{i \in \Omega} X_i \right) ^2 - \sum_{i \in \Omega }X_i^2}{N(N-1)}= E(X)^2 \frac{N}{N-1} - \frac{E(X^2)}{N-1}</math>
Soit Ω une population de taille N, soit X une variable aléatoire sur Ω, on s'intéresse aux échantillons de taille n.
On a V(x) variance de la population et <math>\sigma^2</math> la variance d'un échantillon A de taille n.
<math> \sigma^2 (A)=\frac{\sum_{i \in A} \left( X_i- \frac{\sum_{i \in A}X_i}{n} \right) ^2}{n}= \frac{n-1}{n} \sum_{i \in A} (X_i^2) - \frac{\sum_{i \neq j \in A} X_iX_j}{n^2}</math> D'où
<math> E(\sigma^2(A))=\frac{n-1}{n^2} \sum_{i \in A} E(X_i^2) - \frac{1}{n^2} \sum_{i \neq j \in A} E(X_iX_j)= \frac{n-1}{n} E(X^2) - \frac{n-1}{n} E(X_1X_2)</math>
** avec remise : <math> E(\sigma^2(A))= \frac{n-1}{n} (E(X^2) - E(X)^2)= \frac{n-1}{n} V(X) </math>
** sans remise : <math> E(\sigma^2(A))= \frac{n-1}{n} (E(X^2) - E(X)^2 \frac{N}{N-1} + \frac{E(X^2)}{N-1})= \frac{n-1}{n} \frac{N}{N-1}V(X) </math>

On prend donc en général, pour estimateur sans biais de V(X) sur un échantillon <math>A \subset \Omega</math> la valeur appelée variance empirique de Y :
<math>\displaystyle \sigma'^2 = \frac{1}{Card(A)-1}\sum_{i \in A} (y_i - \overline y)^2</math>

Remarque: pour faire le calcul pour l'estimateur de variance, le point principal est de calculer l'espérance de <math>X_1X_2</math> où <math>X_1</math> et <math>X_2</math> sont deux variables aléatoires obtenues à partir d'une variable aléatoire X en choisissant deux individus au hasard. On a besoin de faire ce calcul à la fois pour un choix de deux individus avec remise et sans remise.

==Un peu de dénombrement==

* Cardinal du '''produit cartésien ''': le produit des cardinaux.

* Tirage '''sans ordre et sans remise ''' de p parmi n, c-à-d nombre de parties à p éléments d'un ensemble à n éléments :

<center><math>\displaystyle C^p_n</math></center>
Démonstration :
On veut choisir p+1 éléments parmi n+1, sans ordre, sans remise. Soit <math> E_n^p </math> l'ensemble des parties à p éléments de {1;...;n}.
<math> E_{n+1}^{p+1}= F_{n+1}^{p+1} \cup G_{n+1}^{p+1}</math> de sorte que <math> F_{n+1}^{p+1} </math> est l'ensemble des p+1 éléments qui contiennent n+1,
et <math> G_{n+1}^{p+1} </math> est l'ensemble des p+1 éléments qui ne contiennent pas n+1. On a <math> F_{n+1}^{p+1} \cap G_{n+1}^{p+1} = \emptyset</math>.
D'autre part <math> G_{n+1}^{p+1}=E_{n}^{p+1} </math>. Soit f: <math> E_n^p \rightarrow F_{n+1}^{p+1}</math>, <math> card(E_{n+1}^{p+1})=card(E_n^p) + card(E_n^{p+1})</math>
''Remarque : '' Deux ensembles en bijection ont le même cardinal.

* Tirage '''avec ordre et sans remise ''' de p parmi n, c-à-d nombre de p-uplets d'un ensemble à n éléments (nombre d'injections de {1;...;p} dans un ensemble à n éléments) :

<center> <math>\displaystyle A^p_n</math></center>
Démonstration:
Soit <math> A_n^p </math> le nombre d'injection, <math> A_n^1=n </math> et <math> A_{n+1}^{p+1}=(n+1) \times A_n^p</math>.
D'où <math> A_n^p= n A_{n-1}^{p-1}=n(n-1)(n-2) ... (n-p+1) </math>

* Tirage '''avec ordre et avec remise ''' de p parmi n, c-à-d nombre de tirage avec remise et avec ordre de p-élemnts parmis n (nombre d'applications de {1;...;p} dans un ensemble à n éléments) :

<center><math>n^p</math></center>
Démonstration :
<math> card(E \times E \times E \times ... \times E)=(cardE)^p=n^p </math>

* Tirage '''sans ordre et avec remise ''' de p parmi n :

<center><math>\displaystyle C^{p}_{n+p-1} = C^{n-1}_{n+p-1}</math></center>
Démonstration : 
On place n-1 jetons dans n+p-1 cases, il reste p cases libres. Il y a <math> C_{n+p-1}^{n-1}=C_{n-1+p}^{p}</math> choix.
Soit f: <math> E \rightarrow \begin{Bmatrix}0;\dots;p\end{Bmatrix} </math> soit f associe à x le nombre de fois où x a été choisi.
On a <math> \sum_{x \in E} f(x)=p</math>, ce qui revient à n-1 jetons et p cases vides.

<center> Choix de p éléments parmi n 
<table border="1">
<tr> <th> Ordre\Remise </th> <th> Sans (0≤p≤n) </th> <th> Avec (0≤p)</th>
</tr>
<tr> <th> Sans </th> <td> <math>\displaystyle C^p_n</math> </td> <td> <math>\displaystyle C^p_{n+p-1}</math></td> </tr>
<tr> <th> Avec </th> <td> <math>\displaystyle A^p_n</math> </td> <td> <math> n^p </math> </td> </tr>
</table>
</center>

'' Rappel des formules usuelles pour les coefficients binomiaux :''

* avec factorielle : <math>\displaystyle C^p_n = \frac{A^p_n}{p!} = \frac{n!}{(n-p)!p!} = \frac{n(n-1)...(n-p+1)}{p!}</math>
* triangle de Pascal : <math>\displaystyle C^0_n = C^n_n = 1, C^{n-p}_n = C^p_n</math> et <math>\displaystyle C^{p+1}_{n+1} = C^p_n + C^{p+1}_n (0 \leq p \leq n - 1)</math>
* Formule du binôme de Newton et applications comme <math>\displaystyle \sum_{p=0}^n C^p_n = 2^n</math>.

Démonstration : 
Soit <math> f(x)=(x+1)^n </math>, <math> f(x)= \sum_{p=0}^n C_n^p x^p</math>. En particulier, f(1)=2n.

==Probabilité et lois usuelles==

* ''' Probabilité ''' (ou loi de probabilité) sur un ensemble <math>\Omega</math>: un nombre associé P(E) aux sous-ensembles <math>E \subset \Omega</math> d'un ensemble (pas toujours tous les sous-ensembles) tel que :
** <math>P(\emptyset) = 0</math>
** <math>P(\Omega) = 1</math>
** <math>P(E \cup F) = P(E) + P(F)</math> si <math>E \cap F = \emptyset</math>
:: '' Conséquences : ''
:::μ (A C)=1- μ (A)
::: <math>[(A \Rightarrow B) \Leftrightarrow (A \subset B)] \Rightarrow \mu (B) \geq \mu (A)</math>
::: <math> \mu (A \cup B)= \mu (A) + \mu (B) - \mu (A \cap B)</math> si A et B non disjoints.
* ''' Évènements = Sous-ensemble ''' . Evénements certains, impossibles, incompatibles. Implication entre évènement et inégalité sur les probas.
* Cas des ensembles finis et probabilité uniforme :
: Pour '' définir une loi de probabilité sur un ensemble fini '' Ω, il suffit de donner la probabilité des singletons.
Démonstration : 
A={x1;...;xn} avec n=card(A). A={x1} ∪ {x2} ∪ ... ∪ {xn} où les singletons sont disjoints.
D'où μ (A)= μ (x1) + ... + μ (xn). Donner une loi sur Ω fini, c'est donner μ (x) pour tout x de Ω.

: La '' loi de probabilité uniforme '' sur Ω fini est l'unique probabilité sur Ω telle que μ (x)=p pour tout x dans Ω avec <math>p=\frac{1}{card(\Omega)} </math>.
Démonstration : 
Ω = {x1;...;xN} avec N=card(Ω). D'où μ (Ω)= μ (x1) + ... + μ (xN)=Np. Or μ (Ω)=1. Donc p=1/N.

: Si A ⊂ Ω et μ est une loi de probabilité uniforme sur Ω alors <math>\mu (A)=\frac{ card(A) }{card( \Omega )} </math>.
Démonstration : 
N=card(Ω) et n=card(A) où A={x1;...; xn</sub}.
On a <math> \mu (A)= \sum_{i=1}^n \mu (x_i)=\sum_{i=1}^n \frac{1}{N}=\frac{n}{N}</math>.

* ''' Loi image ''' (image réciproque d'un ensemble Ω dans Ω') :

Soit X une variable aléatoire sur Ω, à valeurs dans Ω' (X fonction de Ω dans Ω'). On a une loi μ sur Ω. On construit une loi sur Ω', image de μ par X et notée μX. On a pour A inclus dans Ω μ (A)=μ (X-1(A)).

Si Ω est un ensemble ordonné et μ une loi sur Ω, on définit F la ''' fonction de répartition ''' telle que <math> x \in \Omega , F(x)= \mu ( \{ a \in \Omega \mid a \leq x \} )</math>. F est croissante et tend vers 1.
Démonstration :
Si x ≤ y ∈ Ω et {a/ a ≤ x} ⊂ {a/a ≤ y } alors μ ({a/a ≤ x}) ≤ μ ({a/a ≤ y}); d'où F(x) ≤ F(y).

* ''' Variable aléatoire discrète '''
* Lois discrètes usuelles
** '''Loi indicatrice''' ou '''loi de Bernouilli ''' (I(p)) :

Soit X une variable aléatoire sur Ω à valeurs dans {0;1}. X(x)=1 si et seulement si x ∈ E ⊂ Ω (E=X-1(1)).

Cette loi est déterminée par μ X (1)= μ (E)=p (d'où μ X (0)= μ (EC)=1-p).

::: Espérance : E(X)=p
::: Variance : V(X)=p(1-p)
::: Ecart-type : <math>\sigma (X)=\sqrt{p(1-p)} </math>

** '''Loi de Pascal''' (Pa(p)) :

Ω est muni d'une loi uniforme, E ∈ Ω est un événement. On réalise plusieurs expériences '' indépendantes'' jusqu'à obtenir un succès. Soit X le nombre total d'expériences (succès inclus). X est à valeurs dans lN*.

Cette loi est déterminée par μ (E)=p ∈ ]0;1[; μ (X=k)=(1-p) k-1p ∈ ]0;1[.

::: Espérance : E(X)=1/p
::: Variance : V(X)=1/(p2)
::: Ecart-type : <math>\sigma (X)=1/p </math>
** Loi binomiale
** Loi hypergéométrique
** Loi de Poisson
* Lois continus

==Théorème de la limite centrale==

==Intervalle de confiance==

MATH206 : Probabilités et Statistiques

2008-01-28T22:51:30Z

Ebouv :

Feuilles de TD :
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD1-MATH206.pdf 1]
[http://www.lama.univ-savoie.fr/~raffalli/pdfs/TD2-MATH206.pdf 2]

==Vocabulaire de probabilité==

* ''' Population ''' : Groupe d'objets étudiés. Elle peut-être :
**"réelle" : les Français, les étudiants de ce cours...
** "virtuelle" : l'ensemble des lancés de dés possibles...
* '''Sous-population, échantillon '''
* '''Expérience ''' : Choisir un élément dans une population.
* '''Evénement''' : L'événement se produit lorsque l'élément appartient à la sous-population.
* '''Partition ''' : Découpage d'un ensemble en plusieurs sous-ensembles disjoints.
* '''Cardinal ''' : Nombre d'éléments d'un ensemble.
* '''Fréquence ''' d'un sous ensemble A ⊂ Ω : <math> F(A)=\frac{\displaystyle {card(A)}}{\displaystyle{card}(\Omega)} </math>
* '''Variable aléatoire ''' et ''' Série statistique ''' : Application d'une population Ω dans un ensemble X quelconque.

==Estimateur ponctuel==

* '''Moyenne ''' et '''espérance''' (rappel et "sens")
Formule de la moyenne (resp. espérance) d'une série statistique (resp. variable aléatore) X sur un population <math>\Omega</math>:
<math>\displaystyle M(X) = E(X) = \frac{\sum_{i \in \Omega} X_i}{Card(\Omega)}</math>
La moyenne est le nombre x qui remplace le mieux <math>X_i</math> pour l'ensemble de la population quand on regarde l' '''erreur quadratique'''
donnée par la formule suivante (preuve facile en dérivant f):
<math>\displaystyle f(x) = \sum_{i \in \Omega} (X_i - x)^2</math>

On définit deux types d'erreurs :
# ''' l'erreur absolue ''' : <math> \mid X_i -xi \mid </math>
# ''' l'erreur quadratique ''' : <math> (X_i -x)^2 </math>

L'erreur quadratique est aussi liée à la variance V(X) car:

<math>\displaystyle V(X) = \frac{\sum_{i \in \Omega} (X_i - E(X))^2}{Card(\Omega)} = \frac{f(E(x))}{Card(\Omega)}</math>

''Rappel'' : On a aussi <math>V(X) = E(X^2) - E(X)^2</math>

* Propriété de la moyenne (linéarité) : E(X + Y) = E(X) + E(Y) et E(aX) = aE(X)

* Définition d'estimateur et de biais :

Un '''estimateur''' est une "formule" permettant de calculer un nombre à partir de la variable aléatoire restreinte à un échantillon.

Un estimateur estime un paramètre P(X) si il converge vers P(X) lorsque la taille de l'échantillon tend vers la taille de la population
(cela n'a guère se sens que sur les populations infinies ...)

Un estimateur pour P(X) est '''sans biais''', si son espérance est égale à P(X) lorsqu'on le considère comme une variable aléatoire sur la population des échantillons de taille n fabriquée à partir de <math>\Omega</math> (notée <math>\Omega^{(n)}</math>).

** Estimateur de la moyenne : la moyenne sur l'échantillon est un estimateur sans biais de la moyenne sur la population entière. Soit A={1;...;n} l'échantillon, <math>e(X)=\frac{\sum_{i \in A} X_i}{n} </math>

Démonstration :
<math> E ( \frac{\sum_{i \in A} X_i}{n} ) = \frac{1}{n} E(\sum_{i \in A} X_i)= \frac{1}{n} \sum_{i \in A} E(X_i)=\frac{1}{n} X n E(X) =E(X) </math>

** Estimateur de la variance (avec et sans remise) :

Si on note <math>\sigma^2</math> la variance d'un échantillon de taille n dans une population de taille N, on obtient un estimateur sans biais
de la variance avec les formules suivantes:

<math>\displaystyle \frac{n}{n-1}\sigma^2</math> dans le cas de tirage avec remise de l'échantillon

<math>\displaystyle \frac{N-1}{N} \frac{n}{n-1}\sigma^2</math> dans le cas de tirage sans remise (qui vaut bien <math>\sigma^2</math> lorque n = N).
Démonstration :
'' Rappel préalable : '' <math> V(X)=E( (X-E(X))^2)= E (X^2 -2XE(X)+E(X)^2)=E(X^2)-2E(X)E(X)+E(x)^2=E(X^2)-E(X)^2 </math>
'' Calcul préalable : '' Soit X une variable aléatoire sur &Omega, soient X1 et X2 deux variables aléatoires.
** avec remise : <math> E(X_1X_2)= \frac{1}{N^2} \left( \sum_{i,j \in \Omega} X_iX_j \right)=E(X)^2 </math>
** sans remise : <math> E(X_1X_2)=\frac{\sum_{i,j \in \Omega ; i \neq j }X_iX_j}{N(N-1)} = \frac{\sum_{i,j \in \Omega}X_iX_j - \sum_{i \in \Omega}X_i^2}{N(N-1)}=\frac{ \left( \sum_{i \in \Omega} X_i \right) ^2 - \sum_{i \in \Omega }X_i^2}{N(N-1)}= E(X)^2 \frac{N}{N-1} - \frac{E(X^2)}{N-1}</math>
Soit Ω une population de taille N, soit X une variable aléatoire sur Ω, on s'intéresse aux échantillons de taille n.
On a V(x) variance de la population et <math>\sigma^2</math> la variance d'un échantillon A de taille n.
<math> \sigma^2 (A)=\frac{\sum_{i \in A} \left( X_i- \frac{\sum_{i \in A}X_i}{n} \right) ^2}{n}= \frac{n-1}{n} \sum_{i \in A} (X_i^2) - \frac{\sum_{i \neq j \in A} X_iX_j}{n^2}</math> D'où
<math> E(\sigma^2(A))=\frac{n-1}{n^2} \sum_{i \in A} E(X_i^2) - \frac{1}{n^2} \sum_{i \neq j \in A} E(X_iX_j)= \frac{n-1}{n} E(X^2) - \frac{n-1}{n} E(X_1X_2)</math>
** avec remise : <math> E(\sigma^2(A))= \frac{n-1}{n} (E(X^2) - E(X)^2)= \frac{n-1}{n} V(X) </math>
** sans remise : <math> E(\sigma^2(A))= \frac{n-1}{n} (E(X^2) - E(X)^2 \frac{N}{N-1} + \frac{E(X^2)}{N-1})= \frac{n-1}{n} \frac{N}{N-1}V(X) </math>

On prend donc en général, pour estimateur sans biais de V(X) sur un échantillon <math>A \subset \Omega</math> la valeur appelée variance empirique de Y :
<math>\displaystyle \sigma'^2 = \frac{1}{Card(A)-1}\sum_{i \in A} (y_i - \overline y)^2</math>

Remarque: pour faire le calcul pour l'estimateur de variance, le point principal est de calculer l'espérance de <math>X_1X_2</math> où <math>X_1</math> et <math>X_2</math> sont deux variables aléatoires obtenues à partir d'une variable aléatoire X en choisissant deux individus au hasard. On a besoin de faire ce calcul à la fois pour un choix de deux individus avec remise et sans remise.

==Un peu de dénombrement==

* Cardinal du '''produit cartésien ''': le produit des cardinaux.

* Tirage '''sans ordre et sans remise ''' de p parmi n, c-à-d nombre de parties à p éléments d'un ensemble à n éléments :

<center><math>\displaystyle C^p_n</math></center>
Démonstration :
On veut choisir p+1 éléments parmi n+1, sans ordre, sans remise. Soit <math> E_n^p </math> l'ensemble des parties à p éléments de {1;...;n}.
<math> E_{n+1}^{p+1}= F_{n+1}^{p+1} \cup G_{n+1}^{p+1}</math> de sorte que <math> F_{n+1}^{p+1} </math> est l'ensemble des p+1 éléments qui contiennent n+1,
et <math> G_{n+1}^{p+1} </math> est l'ensemble des p+1 éléments qui ne contiennent pas n+1. On a <math> F_{n+1}^{p+1} \cap G_{n+1}^{p+1} = \emptyset</math>.
D'autre part <math> G_{n+1}^{p+1}=E_{n}^{p+1} </math>. Soit f: <math> E_n^p \rightarrow F_{n+1}^{p+1}</math>, <math> card(E_{n+1}^{p+1})=card(E_n^p) + card(E_n^{p+1})</math>
''Remarque : '' Deux ensembles en bijection ont le même cardinal.

* Tirage '''avec ordre et sans remise ''' de p parmi n, c-à-d nombre de p-uplets d'un ensemble à n éléments (nombre d'injections de {1;...;p} dans un ensemble à n éléments) :

<center> <math>\displaystyle A^p_n</math></center>
Démonstration:
Soit <math> A_n^p </math> le nombre d'injection, <math> A_n^1=n </math> et <math> A_{n+1}^{p+1}=(n+1) \times A_n^p</math>.
D'où <math> A_n^p= n A_{n-1}^{p-1}=n(n-1)(n-2) ... (n-p+1) </math>

* Tirage '''avec ordre et avec remise ''' de p parmi n, c-à-d nombre de tirage avec remise et avec ordre de p-élemnts parmis n (nombre d'applications de {1;...;p} dans un ensemble à n éléments) :

<center><math>n^p</math></center>
Démonstration :
<math> card(E \times E \times E \times ... \times E)=(cardE)^p=n^p </math>

* Tirage '''sans ordre et avec remise ''' de p parmi n :

<center><math>\displaystyle C^{p}_{n+p-1} = C^{n-1}_{n+p-1}</math></center>
Démonstration : 
On place n-1 jetons dans n+p-1 cases, il reste p cases libres. Il y a <math> C_{n+p-1}^{n-1}=C_{n-1+p}^{p}</math> choix.
Soit f: <math> E \rightarrow \begin{Bmatrix}0;\dots;p\end{Bmatrix} </math> soit f associe à x le nombre de fois où x a été choisi.
On a <math> \sum_{x \in E} f(x)=p</math>, ce qui revient à n-1 jetons et p cases vides.

<center> Choix de p éléments parmi n 
<table border="1">
<tr> <th> Ordre\Remise </th> <th> Sans (0≤p≤n) </th> <th> Avec (0≤p)</th>
</tr>
<tr> <th> Sans </th> <td> <math>\displaystyle C^p_n</math> </td> <td> <math>\displaystyle C^p_{n+p-1}</math></td> </tr>
<tr> <th> Avec </th> <td> <math>\displaystyle A^p_n</math> </td> <td> <math> n^p </math> </td> </tr>
</table>
</center>

'' Rappel des formules usuelles pour les coefficients binomiaux :''

* avec factorielle : <math>\displaystyle C^p_n = \frac{A^p_n}{p!} = \frac{n!}{(n-p)!p!} = \frac{n(n-1)...(n-p+1)}{p!}</math>
* triangle de Pascal : <math>\displaystyle C^0_n = C^n_n = 1, C^{n-p}_n = C^p_n</math> et <math>\displaystyle C^{p+1}_{n+1} = C^p_n + C^{p+1}_n (0 \leq p \leq n - 1)</math>
* Formule du binôme de Newton et applications comme <math>\displaystyle \sum_{p=0}^n C^p_n = 2^n</math>.

Démonstration : 
Soit <math> f(x)=(x+1)^n </math>, <math> f(x)= \sum_{p=0}^n C_n^p x^p</math>. En particulier, f(1)=2n.

==Probabilité et lois usuelles==

* ''' Probabilité ''' (ou loi de probabilité) sur un ensemble <math>\Omega</math>: un nombre associé P(E) aux sous-ensembles <math>E \subset \Omega</math> d'un ensemble (pas toujours tous les sous-ensembles) tel que :
** <math>P(\emptyset) = 0</math>
** <math>P(\Omega) = 1</math>
** <math>P(E \cup F) = P(E) + P(F)</math> si <math>E \cap F = \emptyset</math>
:: '' Conséquences : ''
:::μ (A C)=1- μ (A)
::: <math>[(A \Rightarrow B) \Leftrightarrow (A \subset B)] \Rightarrow \mu (B) \geq \mu (A)</math>
::: <math> \mu (A \cup B)= \mu (A) + \mu (B) - \mu (A \cap B)</math> si A et B non disjoints.
* ''' Évènements = Sous-ensemble ''' . Evénements certains, impossibles, incompatibles. Implication entre évènement et inégalité sur les probas.
* Cas des ensembles finis et probabilité uniforme :
: Pour '' définir une loi de probabilité sur un ensemble fini '' Ω, il suffit de donner la probabilité des singletons.
Démonstration : 
A={x1;...;xn} avec n=card(A). A={x1} ∪ {x2} ∪ ... ∪ {xn} où les singletons sont disjoints.
D'où μ (A)= μ (x1) + ... + μ (xn). Donner une loi sur Ω fini, c'est donner μ (x) pour tout x de Ω.

: La '' loi de probabilité uniforme '' sur Ω fini est l'unique probabilité sur Ω telle que μ (x)=p pour tout x dans Ω avec <math>p=\frac{1}{card(\Omega)} </math>.
Démonstration : 
Ω = {x1;...;xN} avec N=card(Ω). D'où μ (Ω)= μ (x1) + ... + μ (xN)=Np. Or μ (Ω)=1. Donc p=1/N.

: Si A ⊂ Ω et μ est une loi de probabilité uniforme sur Ω alors <math>\mu (A)=\frac{ card(A) }{card( \Omega )} </math>.
Démonstration : 
N=card(Ω) et n=card(A) où A={x1;...; xn</sub}.
On a <math> \mu (A)= \sum_{i=1}^n \mu (x_i)=\sum_{i=1}^n \frac{1}{N}=\frac{n}{N}</math>.

* ''' Loi image ''' (image réciproque d'un ensemble Ω dans Ω') :

Soit X une variable aléatoire sur Ω, à valeurs dans Ω' (X fonction de Ω dans Ω'). On a une loi μ sur Ω. On construit une loi sur Ω', image de μ par X et notée μX. On a pour A inclus dans Ω μ (A)=μ (X-1(A)).

Si Ω est un ensemble ordonné et μ une loi sur Ω, on définit F la ''' fonction de répartition ''' telle que <math> x \in \Omega , F(x)= \mu ( \{ a \in \Omega \mid a \leq x \} )</math>. F est croissante et tend vers 1.
Démonstration :
Si x ≤ y ∈ Ω et {a/ a ≤ x} ⊂ {a/a ≤ y } alors μ ({a/a ≤ x}) ≤ μ ({a/a ≤ y}); d'où F(x) ≤ F(y).

* ''' Variable aléatoire discrète '''
* Lois discrètes usuelles
** '''Loi indicatrice''' ou '''loi de Bernouilli ''' (I(p)) :

Soit X une variable aléatoire sur Ω à valeurs dans {0;1}. X(x)=1 si et seulement si x ∈ E ⊂ Ω (E=X-1(1)).

Cette loi est déterminée par μ X (1)= μ (E)=p (d'où μ X (0)= μ (EC)=1-p).

: Espérance : E(X)=p
: Variance : V(X)=p(1-p)
: Ecart-type : <math>\sigma (X)=\sqrt{p(1-p)} </math>

** '''Loi de Pascal''' (Pa(p)) :

Ω est muni d'une loi uniforme, E ∈ Ω est un événement. On réalise plusieurs expériences '' indépendantes'' jusqu'à obtenir un succès. Soit X le nombre total d'expériences (succès inclus). X est à valeurs dans lN*.

Cette loi est déterminée par μ (E)=p ∈ ]0;1[; μ (X=k)=(1-p) k-1p &isin ]0;1[.

: Espérance : E(X)=1/p
: Variance : V(X)=1/(p2)
: Ecart-type : <math>\sigma (X)=1/p </math>
** Loi binomiale
** Loi hypergéométrique
** Loi de Poisson
* Lois continus

==Théorème de la limite centrale==

==Intervalle de confiance==

MATH206 : Probabilités et Statistiques

2008-01-28T22:29:00Z

Ebouv :