-
Notifications
You must be signed in to change notification settings - Fork 2
/
index.html
207 lines (202 loc) · 13.3 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
<!DOCTYPE html>
<html lang="fr">
<head>
<meta charset="utf-8">
<title>Labo 2 - Algo num</title>
<!-- Latest compiled and minified CSS -->
<link rel="stylesheet" href="style/bootstrap.min.css">
<!-- Main css -->
<link rel="stylesheet" href="style/main.css" >
</head>
<body>
<div class="container">
<div class="page-header">
<h1>2231.3 - Algorithme numérique : Laboratoire n°2</h1>
<i>Groupe B1</i>
<p>Auteurs :</p>
<ul>
<li>Raphael Margueron</li>
<li>Damian Petroff</li>
<li>Bastien Wermeille</li>
</ul>
</div>
<div class="row">
<div class="col-md-12 col-sm-12">
<h2>Utilisation</h2>
<p>Il est possible de simuler les étapes des différentes méthodes. Entrez une fonction, un point d'entré et cliquer sur le bouton <em>Suivant</em> et <em>Précédent</em> pour visualiser les différentes étapes de résolution.</p>
<p>Le système s'arrête dès qu'un zéro a été atteint. Le ε utilisé est 1e<sup>-10</sup>. Il est possible de zoomer avec la molette de souris, mais aussi en maintenant la touche <i>shift</i> et en faisant une sélection avec la souris.</p>
</div>
</div>
<hr>
<div class="row">
<div class="col-md-3 col-sm-12">
<form id="form">
<label for="eq">f(x) = </label>
<input type="text" id="eq" value="x / (1 - x^2 )" />
<input class="btn btn-primary" type="submit" value="Draw" />
</form>
<p>Itérations = <span id="nbIteration">0</span></p>
<div>
<input class="btn btn-default" type="submit" value="Previous Step" id="previous" />
<input class="btn btn-default" type="submit" value="Next Step" id="next" />
</div>
<hr>
<form id="method">
<div class="form-check">
<input class="form-check-input" type="radio" name="methodOption" id="method3" value="fixedPoint" checked>
<label class="form-check-label" for="method3">Point fixe</label>
</div>
<div class="form-check">
<input class="form-check-input" type="radio" name="methodOption" id="method2" value="tangent">
<label class="form-check-label" for="method2">Tangente</label>
</div>
<div class="form-check">
<input class="form-check-input" type="radio" name="methodOption" id="method1" value="dichotomy">
<label class="form-check-label" for="method1">Dichotomie</label>
</div>
</form>
<form id="startPoint">
<div class="form-group" id="x1Group">
<label for="x1">X1</label>
<input type="text" class="form-control" id="x1" placeholder="X1" value="2">
</div>
<div class="form-group" id="x2Group">
<label for="x2">X2</label>
<input type="text" class="form-control" id="x2" placeholder="X2" value="-1">
</div>
</form>
<hr>
<div>
<h3>Zéros de la fonction (dans [-100;100])</h3>
<div id="zeros"></div>
</div>
</div>
<div class="col-md-9 col-sm-12">
<div id="canvas"></div>
</div>
<div class="col-md-12 col-sm-12">
<div>
<h3>Resultats</h3>
<div id="result"></div>
</div>
</div>
</div>
<hr>
<div class="row">
<div class="col-md-12">
<h1>Rapport</h1>
<h2>Contextualisation</h2>
<p>Dans le cadre du deuxième laboratoire d'algorithme numérique (Haute-École Arc : <a href='https://www.he-arc.ch/sites/www.he-arc.ch/files/Reglements/04%20Formation%20de%20base/43%20Ing%C3%A9nierie/430.100%20Descriptifs%20de%20modules%20Informatique/RS430.100.17.2231%20Sciences%20II%20dlm.pdf'>Module 2231.3</a>), il nous a été demandé de réaliser un algorithme JavaScript pour pouvoir trouver les racines des fonctions suivantes :</p>
<ul>
<li><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>sin</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>-</mo><mfrac><mi>x</mi><mn>13</mn></mfrac><mo>=</mo><mn>0</mn></math></li>
<li><math xmlns="http://www.w3.org/1998/Math/MathML"><mfrac><mi>x</mi><mrow><mn>1</mn><mo>-</mo><msup><mi>x</mi><mn>2</mn></msup></mrow></mfrac><mo>=</mo><mn>0</mn></math></li>
</ul>
<p>Nous devons pouvoir trouver toutes les solutions dans l'intervalle (admis fermé,fermé) : [100,100].</p>
<p>Les algorithmes et les contraintes suivantes nous ont été imposés :</p>
<ul>
<li>Dichotomie : Calculer l'erreur de l'algorithme</li>
<li>Pente (Newton) : Si le X<sub>0</sub> choisi ne permet pas de converger vers une valeur, l'algorithme nous demandera d'augmenter ou de baisser la valeur du X<sub>0</sub></li>
<li>Point fixe : Ajuster la valeur de lamba dynamiquement pour trouver une solution</li>
</ul>
<p>Nous avons choisi de réaliser la méthode du <em>Point Fixe</em>, mais avons également implémenté un rendu graphique pour les deux autres méthodes. Cependant, nous n'avons pas implémenté la fonction <i>solve</i> de ces deux dernières méthodes.</p>
<h2>Méthodologie de développement</h2>
<h3>Affichage des fonctions</h3>
<p>La première tâche que nous avons réalisée a été la recherche d'une bibliothèque permettant d'afficher des fonctions mathématiques quelconques, notemment celles qui tendent vers l'infinie. Notre choix s'est tourné vers la bibliothèque <a href='https://github.com/mauriciopoppe/function-plot'>function-plot de Mauriciopoppe</a> qui répond à notre critère principal. L'étape suivante a été de vérifier qu'elle ne nous limitait pas dans l'affichage de traits supplémentaires. Pour symboliser les passages des algorithmes (que nous avons appelé : pas <=> step)</p>
<p>Une fois ces tests effectués, nous avons réalisé l'implémentation des différentes méthodes.</p>
<h3>Les algorithmes</h3>
<p>Nous avons uniquement utilisé le cours de Monsieur Stéphane Gobron, notre professeur, pour la réalisation de ce travail. Voici la référence de son cours sur son site internet.
<a href='http://www.stephane-gobron.net/Core/Courses/3_HE-Arc/NumericalAlgorithms/BSc2_AlgorithmesNumeriques_Chap2_v1-6-0.pdf'>Cours (lien du 17.03.2018)</a>
</p>
<h3>Structure du code</h3>
<p>Afin de pouvoir intégrer n'importe quel algorithme à notre solution. Nous avons opté sur un développement orienté objet utilisant l'héritage. Nous avons donc deux classes principales : Plot et Algorithm (classe abstraite). Puis pour chacun des algorithmes nous avons créé une classe dérivée de la classe Algorithm. Chacune des classes dérivées doit ensuite implémenter la fonction draw(), nextStep() et solve(). La class Plot, comme son nom l'indique, permet de gérer l'affichage du graphique mais aussi de gérer le mode 'pas à pas' <=> 'step by step' pour l'affichage de l'algorithme.</p>
<p>Avec cette structure de code, il nous est très facile d'ajouter d'autres algorithmes et également de modifier leurs comportements.</p>
<p>Afin de tester notre structure, nous avons réalisé la partie affichage de la méthode Dichotomie et Tangente pour le défi. A noter que la méthode d'affichage pour ces deux méthodes ne détectent pour l'instant pas la divergence ou la boucle infinie.</p>
<h3>Algorithm (classe Algorithm)</h3>
<p>
Cette classe comme expliqué ci-dessus est une classe abstraite d'où chaque algorithme devera être spécifié. Les quelques fonctions implémentées dans cette classe sont décrite ci-dessous.
</p>
<h4>Previous Step</h4>
<p>
Cette fonction va uniquement retirer 1 au pointeur de progression du dessin. Cela aura pour effect d'afficher un pas en moins. Lors des prochaines 'NextStep' il n'y aura pas besoin de recalculer le 'pas' mais juste de l'afficher.
</p>
<h4>isEquals</h4>
<p>
Retourne vrai la différence relative entre les deux valeurs est plus petite que l'epsilon.
</p>
<h3>Dichotomie (classe Dichotomy)</h3>
<p>Pour cette classe, nous avons besoin de deux inputs, la borne inférieure et supérieure.</p>
<p>Puis nous avons codé l'algorithme qui était exprimé sous forme de pseudocode dans le cours (Page 12)</p>
<h3>Méthode de la tangente, aussi appelée méthode de la pente ou méthode de Newton (classe Tangent)</h3>
<p>Pour cette classe, nous n’avons eu que besoin "d'un point de départ" duquel l'algorithme va commencer à essayer de converger vers la racine.</p>
<p>Nous avions normalement à implémenter une fonction d'approximation de la dérivée d'une fonction en un point (droite tangente). Elle est basée sur la définition de la dérivée, où nous choisissons un "h" (aussi appelé delta ou k) très faible puis selon le principe des approximations linéaire trouvé la valeur de la dérivé.</p>
<p>Mais ayant très bien compris comment implémenter une telle fonction, ajouté au fait que nous trouvé une bibliothèque permettant de trouver la dérivée analytique d'une fonction. Nous avons choisi de simplement évaluer la dérivée analytique au lieu d'utiliser une telle approximation.</p>
<h3>Point fixe (classe FixedPoint)</h3>
<p>Pour le moment uniquement cette classe permet de trouver toutes les racines d'une fonction dans l'intervale. (c-à-d : qui implemente la fonction solve)</p>
<p>Voici des explications assez simple pour chacune des fonctions principales de la classe</p>
<h4>Contructeur</h4>
<p>
Le constructeur va initalise le objet avec comme lambda 1, récupérer le point fixe (point de départ) et initialiser les variables qui sont utile à la gestion de la classe.
</p>
<h4>Next Step</h4>
<p>
Cette fonction permet de calculer le prochain 'pas' de la recherche de racine. Elle va être impossible à appeler une fois qu'une racine à été trouvée. Ce n'est donc pas avec cette fonction que les racines sont trouvées. Elle a uniquement pour but didactique de comprendre l'algorithme.
</p>
<h4>Draw</h4>
<p>
Cette fonction va dessiner la fonction mathématique entrée et afficher à chaque 'pas' les fléches pour indiqué le parcours.
</p>
<h4>Solve</h4>
<p>
Cette fonction, reprends en partie le code du next step mais adapte mieux le lambda et trouve toutes les solutions dans l'intervale des objectifs. Nous avons fixé le nombre d'intération maximal à 100, après ce cap nous concidérons que la fonction diverge nous adaptons ensuite le lambda.
</p>
<p>
Dès qu'une solution est trouvée, elle est ajoutée à un dictionnaire. Pour ensuite pouvoir les affichées dans l'interface sous la forme d'un vecteur (Compatibilité firefox [mathml]).
</p>
<h2>Tests</h2>
<p>En plus des fonctions mathématiques proposées, nous avons également testé notre code avec différentes fonctions tel que <i>sin(x)</i> afin de valider que notre algorithme trouvait tous les zéros dans l'intervale.</p>
<h2>Conclusion</h2>
<p>Nous pensons avons rempli le cahier des charges. L'utilisteur a la possibilité de visualiser les différentes étapes de l'algorithme, le graphe permet de visualiser les fonctions:{f(x); g(x); x}. Nous avons implémenté une version non parfaite permettant de détecter si notre fonction tend vers un résultat ou non.</p>
<p>Nous avons également réalisé une fonctionnalité supplémentaire intéressante qui est la possibilité de pouvoir directement saisir une fonction dans un champ.</p>
<h2>Perspectives</h2>
<p>Nous avons basé notre développement sur la possibilité de facilement ajouter des fonctionnalitées. Il serait intéressant de pouvoir comparer de manière pratiques les différentes méthodes. Afin de voir à quelle vitesse elles convergent vers une solution.</p>
</div>
</div>
<hr>
<footer>
<h2>Références de développement</h2>
<ul class="a-autoFill">
<li><a href="https://blog.sicara.com/compare-best-javascript-chart-libraries-2017-89fbe8cb112d"></a></li>
<li><a href="https://mauriciopoppe.github.io/function-plot/"></a></li>
<li><a href="https://github.com/mauriciopoppe/function-plot"></a></li>
<li><a href="http://mathjs.org/examples/browser/plot.html"></a></li>
<li><a href="http://seiyria.com/bootstrap-slider/"></a></li>
<li><a href="https://jquery.org/license/"></a></li>
</ul>
<hr>
<h2>Bibliothèques</h2>
<p>Toutes les bibliothèques utilisées sont libres d'utilisation.</p>
<ul>
<li><em>Function-Plot</em> License MIT</li>
<li><em>Math.js</em> Apache 2.0 License</li>
<li><em>Bootstrap</em> License MIT</li>
<li><em>JQuery</em> License MIT</li>
</ul>
</footer>
</div>
<!-- Latest compiled and minified JavaScript -->
<script src="script/external/jquery.min.js"></script>
<!-- Math equation parsing -->
<!--<script src="https://unpkg.com/[email protected]/dist/math.min.js"></script>-->
<script src="script/external/math.min.js"></script>
<!-- load http://maurizzzio.github.io/function-plot/ -->
<script src="script/external/d3.min.js"></script>
<script src="script/external/[email protected]"></script>
<!-- Main script -->
<script src="script/Plot.js"></script>
<script src="script/Algorithm.js"></script>
<script src="script/FixedPoint.js"></script>
<script src="script/Dichotomy.js"></script>
<script src="script/Tangent.js"></script>
<script src="script/script.js"></script>
</body>
</html>