[PDF] [PDF] Exo7 - Cours de mathématiques - Emathfr

[PDF] Algorithmique I - École normale supérieure de Lyon

1 7 Exercices 14 2 Diviser pour régner 15 2 1 Algorithme de Strassen 2 4 2 Résolution des récurrences avec second membre 19 de l' humour, dans un fichier pdf `a télécharger absolument (par dichotomie dans la liste triée des si), et le dernier n correspond `a la taille de la fenêtre autour de la 

[PDF] Calcul Scientifique: Cours, exercices corrigés et illustrations en

mais quand elles s'accumulent au cours d'algorithmes longs et complexes, elles peuvent variable est t et la seconde x (en suivant l'ordre lexicographique) La syntaxe La méthode de dichotomie (aussi appelée méthode de bisection)

[PDF] Calcul Scientifique: Cours, exercices corrigés et - Ceremade

lisés pour implémenter les divers algorithmes présentés, ce qui permet de vérifier , par la 5 15 Exercices Produit matrice-vecteur : temps CPU (en secondes) en fonction La méthode de dichotomie (aussi appelée méthode de bisection)

[PDF] EILCO : Analyse Numérique Chapitre 3 : Résolution - LMPA

Calcul Scientifique Cours, exercices corrigés et illustrations en Matlab et Octave Algorithmes de résolution Etude de la convergence Résolution numérique Méthode de dichotomie (Seconde variante) : Exemple f(x)=(5 − x)ex − 5 = 0, 

[PDF] EXAMEN 1 - Corrigé

4) Nous ne répondrons à aucune question concernant ces exercices, sauf si nous 5) L'examen est noté sur 100 points et compte pour 40 de la note finale (iii) [5 pts] Pour quels vecteurs initiaux ne peut-on pas démarrer l'algorithme?

[PDF] Optimisation

D'autres exemples sont dans la séance d'exercices Voir les exercices pour des exemples La dérivée seconde dans la direction v1 au point x = 0 est donc strictement négative, Définir un algorithme qui procède par dichotomie directe

[PDF] Exo7 - Cours de mathématiques - Emathfr

4 SOMMAIRE Cours et exercices de maths Le principe de dichotomie repose sur la version suivante du théorème des valeurs intermé- diaires : Même algorithme, mais avec cette fois en entrée la précision souhaitée : Dans la seconde on doit, à chaque calcul, limiter notre précision à 6 chiffres (ici 1 avant la virgule

[PDF] Algorithmes et programmation en Pascal TD corrigés

5) Faire un programme qui lit t1 et t2 et qui dit si t1 est < ou = ou > `a t2, en passant par la conversion en secondes Correction PROGRAM tp_comp; TYPE { cf 1) }

[PDF] Analyse Numérique : SMA-SMI S4 Cours, exercices et examens

Si x(0) est le vecteur initial donné, l'algorithme de Jacobi est de la forme : x (k+1) i = − La méthode de dichotomie consiste à approcher θ par encadrement, en réduisant à chaque étape Ecrire les dérivées premières et secondes de g 2

[PDF] Recueil dexercices pour les cours MTH2210x

Exercices pour les cours de calcul scientifique pour ingénieurs MTH2210B En relevant toutes les 10 secondes la vitesse d'écoulement de l'eau dans une conduite (c) Modifier l'algorithme de la bissection en remplaçant xm par x∗ m

[PDF] algorithme de dichotomie terminale s PDF Cours,Exercices ,Examens

[PDF] Algorithme de dichotomie, encadrement d'amplitude & #945; 1ère Mathématiques

[PDF] algorithme de dijkstra PDF Cours,Exercices ,Examens

[PDF] algorithme de dijkstra exercice corrigé PDF Cours,Exercices ,Examens

[PDF] algorithme de ford plus long chemin PDF Cours,Exercices ,Examens

[PDF] Algorithme de héron Terminale Mathématiques

[PDF] Algorithme de loi continue / densite Terminale Mathématiques

[PDF] Algorithme de mathématiques 2nde Mathématiques

[PDF] Algorithme de maths 1ère Mathématiques

[PDF] Algorithme de maths 2nde Mathématiques

[PDF] Algorithme de mesure d'angle 1ère Mathématiques

[PDF] Algorithme de niveau Seconde 2nde Mathématiques

[PDF] algorithme de parcours en largeur PDF Cours,Exercices ,Examens

[PDF] algorithme de parcours en profondeur en c PDF Cours,Exercices ,Examens

[PDF] ALGORITHME DE PILE OU FACE svp essayer de me faire comprendre cette algorithme 2nde Mathématiques

Cours de mathématiques

Première année

ComplémentsExo7

2

SommaireExo7

1Zéros des fonctions. ...............................................5

1

La dichotomie

5 2

La méthode de la sécante

10 3

La méthode de Newton

14

2Algorithmes et mathématiques. .................................19

1

P remierspas avec ??????.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2

Écriture des entiers

24
3

Calculs de sinus, cosinus, tangente

30
4

L esr éels

34
5

Arithmétique - Algorithmes r écursifs

39
6

P olynômes- Comple xitéd"un algorithme

45

3Cryptographie. ..................................................51

1

L echiffrement de César

51
2

L echiffrement de V igenère

56
3

La machine Enigma et les clés secr ètes

59
4

La cr yptographieà clé publique

65
5

L "arithmétiquepour RS A

68
6

L echiffrement RS A

72

4La chaînette. ....................................................79

1

L ecosinus hyperbolique

80
2

Équation de la chaînette

83
3

L ongueurd"une chaînette

88

5La règle et le compas. ...........................................95

1

Constructions et les tr oispr oblèmesgrecs

95
2 L esnombres constructibles à la r ègleet au compas 100
3

Éléments de théorie des corps

107
4

Corps et nombres constructibles

111
5

Applications aux pr oblèmesgrecs

115

6Leçons de choses. ..............................................119

1

T ravailleravec les vidéos

119
2

Alphabet grec

121
3

Écrire des mathématiques : L

ATEX en cinq minutes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4 F ormulesde trigonométrie : sinus, cosinus, tangente 124
5 F ormulaire: trigonométrie circulaire et hyperbolique 130
6

F ormulesde développements limités

133
7

F ormulaire: primitives

134 3

4SOMMAIRE

Cours et exercices de maths

1 Zéros des fonctionsExo7

?????ç?????? ?? ?? ??????? ?? ??????Dans ce chapitre nous allons appliquer toutes les notions précédentes sur les suites et les fonctions,

à la recherche des zéros des fonctions. Plus précisément, nous allons voir trois méthodes afin de

trouver des approximations des solutions d"une équation du type (f(x)AE0). 1.

La dichotomie

1.1.

Principe de la dichotomie

Le principe de dichotomie repose sur la version suivante duthéorème des valeurs intermé- diaires:Théorème 1 Soitf:[a,b]!Rune fonction continue sur un segment. Sif(a)¢f(b)É0, alors il existe`2[a,b] tel quef(`)AE0.

La conditionf(a)¢f(b)É0 signifie quef(a) etf(b) sont de signes opposés (ou que l"un des deux est

nul). L"hypothèse de continuité est essentielle!xy a f(a)Ç0bf(b)È0` xy af(a)È0b f(b)Ç0`

Ce théorème affirme qu"il existe au moins une solution de l"équation (f(x)AE0) dans l"intervalle

[a,b]. Pour le rendre effectif, et trouver une solution (approchée) de l"équation (f(x)AE0), il s"agit

maintenant de l"appliquer sur un intervalle suffisamment petit. On va voir que cela permet d"obte- nir un`solution de l"équation (f(x)AE0) comme la limite d"une suite.

6Zéros des fonctionsVoici comment construire une suite d"intervalles emboîtés, dont la longueur tend vers 0, et conte-

nant chacun une solution de l"équation (f(x)AE0). On part d"une fonctionf:[a,b]!Rcontinue, avecaÇb, etf(a)¢f(b)É0. Voici la première étape de la construction : on regarde le signe de la valeur de la fonctionf appliquée au point milieu aÅb2 -Sif(a)¢f(aÅb2 )É0, alors il existec2[a,aÅb2 ] tel quef(c)AE0. Sif(a)¢f(aÅb2)È0, cela implique quef(aÅb2)¢f(b)É0, et alors il existec2[aÅb2 ,b] tel que f(c)AE0.xy a baÅb2f(aÅb2 )È0xy a baÅb2 f(aÅb2 )Ç0 Nous avons obtenu un intervalle de longueur moitié dans lequel l"équation (f(x)AE0) admet une solution. On itère alors le procédé pour diviser de nouveau l"intervalle en deux.

Voici le processus complet :

Au rang 0 :

On posea0AEa,b0AEb. Il existe une solutionx0de l"équation (f(x)AE0) dans l"intervalle [a0,b0].

Au rang 1 :

-Sif(a0)¢f(a0Åb02 )É0, alors on posea1AEa0etb1AEa0Åb02 -sinon on posea1AEa0Åb02 etb1AEb. Dans les deux cas, il existe une solutionx1de l"équation (f(x)AE0) dans l"intervalle [a1,b1].

Au rang n:

supposons construit un intervalle [an,bn], de longueurb¡a2 n, et contenant une solutionxnde l"équation (f(x)AE0). Alors : -Sif(an)¢f(anÅbn2 )É0, alors on poseanÅ1AEanetbnÅ1AEanÅbn2 -sinon on poseanÅ1AEanÅbn2 etbnÅ1AEbn. Dans les deux cas, il existe une solutionxnÅ1de l"équation (f(x)AE0) dans l"intervalle [anÅ1,bnÅ1].

À chaque étape on a

a nÉxnÉbn. On arrête le processus dès quebn¡anAEb¡a2 nest inférieur à la précision souhaitée.

Comme (an) est par construction une suite croissante, (bn) une suite décroissante, et (bn¡an)!0

lorsquen!Å1, les suites (an) et (bn) sont adjacentes et donc elles admettent une même limite.

D"après le théorème des gendarmes, c"est aussi la limite disons`de la suite (xn). La continuité de

fmontre quef(`)AElimn!Å1f(xn)AElimn!Å10AE0. Donc les suites (an) et (bn) tendent toutes les deux vers`, qui est une solution de l"équation (f(x)AE0). 1.2.

Résultats numériques pour

p10 Nous allons calculer une approximation dep10. Soit la fonctionfdéfinie parf(x)AEx2¡10, c"est une fonction continue surRqui s"annule en§p10. De plusp10est l"unique solution positive de

Zéros des fonctions7l"équation (f(x)AE0). Nous pouvons restreindre la fonctionfà l"intervalle [3,4] : en effet 32AE9É10

donc 3Ép10et 42AE16Ê10 donc 4Êp10. En d"autre termesf(3)É0 etf(4)Ê0, donc l"équation

(f(x)AE0) admet une solution dans l"intervalle [3,4] d"après le théorème des valeurs intermédiaires,

et par unicité c"estp10, donc p102[3,4]. Notez que l"on ne choisit pas pourfla fonctionx7!x¡p10car on ne connaît pas la valeur dep10.

C"est ce que l"on cherche à calculer!xy

343.53.253.125Voici les toutes premières étapes :

1. On posea0AE3 etb0AE4, on a bienf(a0)É0 etf(b0)Ê0. On calculea0Åb02

AE3,5 puisf(a0Åb02) :

f(3,5)AE3,52¡10AE2,25Ê0. Doncp10est dans l"intervalle [3;3,5] et on posea1AEa0AE3 et b1AEa0Åb02

AE3,5.

2. On sait donc quef(a1)É0 etf(b1)Ê0. On calculef(a1Åb12)AEf(3,25)AE0,5625Ê0, on pose a2AE3 etb2AE3,25. 3. On calculef(a2Åb22)AEf(3,125)AE¡0,23...É0. Commef(b2)Ê0 alors cette foisfs"annule sur le second intervalle [a2Åb22 ,b2] et on posea3AEa2Åb22

AE3,125 etb3AEb2AE3,25.

À ce stade, on a prouvé : 3,125Ép10É3,25.

Voici la suite des étapes :

a

0AE3b0AE4

a

1AE3b1AE3,5

a

2AE3b2AE3,25

a

3AE3,125b3AE3,25

a

4AE3,125b4AE3,1875

a

5AE3,15625b5AE3,1875

a

6AE3,15625b6AE3,171875

a

7AE3,15625b7AE3,164062...

a

8AE3,16015...b8AE3,164062...

Donc en 8 étapes on obtient l"encadrement :

3,160Ép10É3,165

En particulier, on vient d"obtenir les deux premières décimales : p10AE3,16... 1.3.

Résultats numériques pour (1,10)1/12

Nous cherchons maintenant une approximation de (1,10)1/12. Soitf(x)AEx12¡1,10. On posea0AE1 etb0AE1,1. Alorsf(a0)AE¡0,10É0 etf(b0)AE2,038...Ê0.

8Zéros des fonctions

a

0AE1b0AE1,10

a

1AE1b1AE1,05

a

2AE1b2AE1,025

a

3AE1b3AE1,0125

a

4AE1,00625b4AE1,0125

a

5AE1,00625b5AE1,00937...

a

6AE1,00781...b6AE1,00937...

a

7AE1,00781...b7AE1,00859...

a

8AE1,00781...b8AE1,00820...

Donc en 8 étapes on obtient l"encadrement :

1,00781É(1,10)1/12É1,00821

1.4.

Calcul de l"erreur La méthode de dichotomie a l"énorme avantage de fournir un encadrement d"une solution`de

l"équation (f(x)AE0). Il est donc facile d"avoir une majoration de l"erreur. En effet, à chaque étape,

la taille l"intervalle contenant`est divisée par 2. Au départ, on sait que`2[a,b] (de longueur

b¡a); puis`2[a1,b1] (de longueurb¡a2); puis`2[a2,b2] (de longueurb¡a4); ...; [an,bn] étant de

longueurb¡a2 n. Si, par exemple, on souhaite obtenir une approximation de`à 10¡Nprès, comme on sait que anÉ`Ébn, on obtientj`¡anjÉjbn¡anjAEb¡a2 n. Donc pour avoirj`¡anjÉ10¡N, il suffit de choisir ntel queb¡a2 nÉ10¡N.

Nous allons utiliser le logarithme décimal :

b¡a2 nÉ10¡N()(b¡a)10NÉ2n ()log(b¡a)Ålog(10N)Élog(2n) ()log(b¡a)ÅNÉnlog2 ()nÊNÅlog(b¡a)log2

Sachantlog2AE0,301..., si par exempleb¡aÉ1, voici le nombre d"itérations suffisantes pour avoir

une précision de 10¡N(ce qui correspond, à peu près, àNchiffres exacts après la virgule).

10

¡10(»10 décimales) 34 itérations

10

¡100(»100 décimales) 333 itérations

10 ¡1000(»1000 décimales) 3322 itérations Il faut entre 3 et 4 itérations supplémentaires pour obtenir une nouvelle décimale.Remarque En toute rigueur il ne faut pas confondre précision et nombre de décimales exactes, par

exemple 0,999 est une approximation de 1,000 à 10¡3près, mais aucune décimale après la

virgule n"est exacte. En pratique, c"est la précision qui est la plus importante, mais il est plus

frappant de parler du nombre de décimales exactes.

Zéros des fonctions9

1.5.

Algorithmes Voici comment implémenter la dichotomie dans le langage??????. Tout d"abord on définit une

fonctionf(ici par exemplef(x)AEx2¡10) :Algorithme . dichotomie.py (1) Puis la dichotomie proprement dite : en entrée de la fonction, on a pour variablesa,betnle nombre d"étapes voulues.Algorithme . dichotomie.py (2) ???Même algorithme, mais avec cette fois en entrée la précision souhaitée :

Algorithme . dichotomie.py (3)

???Enfin, voici la version récursive de l"algorithme de dichotomie.

Algorithme . dichotomie.py (4)

10Zéros des fonctions

Mini-exercices

1. À la main, cal culerun encadrement à 0 ,1 près dep3. Idem avec 3p2. 2. Calculer une approxim ationdes solutions de l"équation x3Å1AE3x.

3.Est-il plus efficace de diviser l"intervalle en 4 au lieu d"en 2? (À chaque itération, la

dichotomie classique nécessite l"évaluation defen une nouvelle valeuraÅb2pour une précision améliorée d"un facteur 2.) 4. Écrire un algorithm epour calculer plusieurs solutions de ( f(x)AE0). 5. On se donne un tableau trié de tailleN, rempli de nombres appartenant à{1,...,n}. Écrire un algorithme qui teste si une valeurkapparaît dans le tableau et en quelle position.2.La méthode de la sécante 2.1.

Principe de la sécante

L"idée de la méthode de la sécante est très simple : pour une fonctionfcontinue sur un intervalle

[a,b], et vérifiantf(a)É0,f(b)È0, on trace le segment [AB] oùAAE(a,f(a)) etBAE(b,f(b)). Si le

segment reste au-dessus du graphe defalors la fonction s"annule sur l"intervalle [a0,b] où (a0,0) est le point d"intersection de la droite (AB) avec l"axe des abscisses. La droite (AB) s"appelle la sécante. On recommence en partant maintenant de l"intervalle [a0,b] pour obtenir une valeura00.xy ab AB a 0A 0a 00A 00

Zéros des fonctions11

Proposition 1Soitf:[a,b]!Rune fonction continue, strictement croissante et convexe telle quef(a)É0,

f(b)È0. Alors la suite définie par a est croissante et converge vers la solution`de (f(x)AE0). L"hypothèsefconvexesignifie exactement que pour toutx,x0dans [a,b] la sécante (ou corde) entre (x,f(x)) et (x0,f(x0)) est au-dessus du graphe def.xy x x

0(x,f(x))(x0,f(x0))Démonstration

1. J ustifionsd"abord la constructi onde la suite récurrente . L"équation de la droite passant par les deux points (a,f(a)) et (b,f(b)) est yAE(x¡a)f(b)¡f(a)b¡aÅf(a)

Cette droite intersecte l"axe des abscisses en (a0,0) qui vérifie donc 0AE(a0¡a)f(b)¡f(a)b¡aÅf(a),

donca0AEa¡b¡af(b)¡f(a)f(a). 2.

Croissance de ( an).

Montrons par récurrence quef(an)É0. C"est vrai au rang 0 carf(a0)AEf(a)É0 par hypothèse.

Supposons vraie l"hypothèse au rangn. SianÅ1Çan(un cas qui s"avéreraa posteriorijamais réa-

lisé), alors commefest strictement croissante, on af(anÅ1)Çf(an), et en particulierf(anÅ1)É0.

SinonanÅ1Êan. Commefest convexe : la sécante entre (an,f(an)) et (b,f(b)) est au-dessus

du graphe def. En particulier le point (anÅ1,0) (qui est sur cette sécante par définitionanÅ1)

est au-dessus du point (anÅ1,f(anÅ1)), et doncf(anÅ1)É0 aussi dans ce cas, ce qui conclut la

récurrence.quotesdbs_dbs45.pdfusesText_45