root / pobysoPythonSage / src / sageSLZ / sageSLZ-Notes.html @ 85
Historique | Voir | Annoter | Télécharger (15,34 ko)
1 | 67 | storres | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
|
---|---|---|---|
2 | 67 | storres | "http://www.w3.org/TR/html4/loose.dtd">
|
3 | 67 | storres | <html>
|
4 | 67 | storres | <head>
|
5 | 67 | storres | <meta http-equiv="content-type" content="text/html; charset=iso-8859-1"> |
6 | 67 | storres | <style type="text/css"> |
7 | 67 | storres | /* Mise ? jour 2010-12-20 */ |
8 | 67 | storres | /* La police proportionnelle de base est une Helvetica de 10 */ |
9 | 67 | storres | /* La police fixe de base est une Courrier de 10 */ |
10 | 67 | storres | /** Corps */ |
11 | 67 | storres | body {background-color: #FFFFFF; |
12 | 67 | storres | font-family : helvetica, arial, sans-serif; |
13 | 67 | storres | font-size : 10pt; |
14 | 67 | storres | font-weight : normal; |
15 | 67 | storres | font-style : normal} |
16 | 67 | storres | /* |
17 | 67 | storres | */ |
18 | 67 | storres | /** Page de couverture */ |
19 | 67 | storres | /* |
20 | 67 | storres | --------------------------------------------------------------- |
21 | 67 | storres | / ------------------------------------ |
22 | 67 | storres | / table.coverHeader | td.coverHeaderLeft / td.coverHeaderRight | |
23 | 67 | storres | / ------------------------------------ |
24 | 67 | storres | / |
25 | 67 | storres | / ------------------------------------ |
26 | 67 | storres | / / / |
27 | 67 | storres | div.cover / / p.coverTitle / |
28 | 67 | storres | / / / |
29 | 67 | storres | / div.coverTitle ------------------------------------ |
30 | 67 | storres | / / / |
31 | 67 | storres | / / p.coverSubTitle / |
32 | 67 | storres | / / / |
33 | 67 | storres | / ------------------------------------ |
34 | 67 | storres | --------------------------------------------------------------- |
35 | 67 | storres | |
36 | 67 | storres | */ |
37 | 67 | storres | @media print {div.cover {page-break-after:always} |
38 | 67 | storres | div.coverTitle {top : 250pt}} |
39 | 67 | storres | div.cover {margin-bottom : 100pt; |
40 | 67 | storres | text-align : center;} |
41 | 67 | storres | table.coverHeader {position : relative; |
42 | 67 | storres | top : 0; |
43 | 67 | storres | width : 90%; |
44 | 67 | storres | font-size: 12pt; |
45 | 67 | storres | font-family : helvetica, arial, sans-serif; |
46 | 67 | storres | font-weight: bold} |
47 | 67 | storres | table.coverHeader td.coverHeaderLeft {text-align : left} |
48 | 67 | storres | table.coverHeader td.coverHeaderRight {text-align : right} |
49 | 67 | storres | div.coverTitle {position : relative; |
50 | 67 | storres | margin-top : 100pt; |
51 | 67 | storres | text-align : center; |
52 | 67 | storres | border : solid ; |
53 | 67 | storres | margin-left : 20%; |
54 | 67 | storres | margin-right : 20%} |
55 | 67 | storres | /* Voir h1 */ |
56 | 67 | storres | p.coverTitle {text-align : center ; |
57 | 67 | storres | font-size : 20pt ; |
58 | 67 | storres | font-weight : bold ; |
59 | 67 | storres | font-family : helvetica, arial, sans-serif; |
60 | 67 | storres | text-indent : 0pt} |
61 | 67 | storres | p.coverSubTitle{text-align : center ; |
62 | 67 | storres | font-size : 16pt ; |
63 | 67 | storres | font-weight : normal; |
64 | 67 | storres | font-family : helvetica , arial , sans-serif; |
65 | 67 | storres | margin-top : 30pt; |
66 | 67 | storres | text-indent : 0pt} |
67 | 67 | storres | /* ?l?ments "en ligne" */ |
68 | 67 | storres | abbr {font-family : helvetica, arial, sans-serif; |
69 | 67 | storres | font-style : normal; |
70 | 67 | storres | font-weight : bold} |
71 | 80 | storres | /* Identique ? abbr */ |
72 | 67 | storres | acronym {font-family : helvetica, arial, sans-serif; |
73 | 67 | storres | font-style : normal; |
74 | 67 | storres | font-weight : bold} |
75 | 67 | storres | address {font-family : helvetica, arial, sans-serif; |
76 | 67 | storres | font-style : italic; |
77 | 67 | storres | margin-left : 20pt; |
78 | 67 | storres | margin-right : 20pt} |
79 | 67 | storres | blocquote {font-family : helvetica, arial, sans-serif; |
80 | 67 | storres | font-style : italic; |
81 | 67 | storres | margin-left : 20pt; |
82 | 67 | storres | margin-right : 20pt} |
83 | 67 | storres | cite {font-family : helvetica, arial, sans-serif; |
84 | 67 | storres | font-style : italic; |
85 | 67 | storres | font-weight : normal} |
86 | 67 | storres | /* ? utiliser dans une division de code pour les marges et dans un ?l?ment |
87 | 67 | storres | "pre" pour pr?server l'indentation) : div.code->pre->code. */ |
88 | 67 | storres | code {font-family : courier, monospace; |
89 | 67 | storres | font-style : normal; |
90 | 67 | storres | font-weight : normal} |
91 | 67 | storres | div.code {margin-left : 30pt; |
92 | 67 | storres | margin-right : 30pt} |
93 | 67 | storres | del {text-decoration : line-through} |
94 | 67 | storres | dfn {font-family: helvetica, arial, sans-serif; |
95 | 67 | storres | font-style: italic; |
96 | 67 | storres | font-weight: normal} |
97 | 67 | storres | ins {text-decoration : none; |
98 | 67 | storres | background-color : #FFFF00} |
99 | 67 | storres | kbd {font-family : times, serif; |
100 | 67 | storres | font-style : italic; |
101 | 67 | storres | font-weight : normal} |
102 | 67 | storres | pre {} |
103 | 67 | storres | /* ? travailler pour ?viter les guillemets anglo-saxons. */ |
104 | 67 | storres | q {} |
105 | 67 | storres | /* On introduit un ?l?ment div.samp pour ajouter le retrait */ |
106 | 67 | storres | samp {font-family : courier, monospace; |
107 | 67 | storres | font-style : normal; |
108 | 67 | storres | font-weight : normal} |
109 | 67 | storres | div.samp {margin-left : 30pt; |
110 | 67 | storres | margin-right : 30pt} |
111 | 67 | storres | strong {font-weight : bold} |
112 | 67 | storres | var {font-family : courier, monospace; |
113 | 67 | storres | font-style : italic; |
114 | 67 | storres | font-weight: normal} |
115 | 67 | storres | /* Span sp?cialis?s. */ |
116 | 67 | storres | /* Mot ou expression ?trang?re */ |
117 | 67 | storres | span.foreign {font-style : italic} |
118 | 67 | storres | /* ?l?ments de langage : |
119 | 67 | storres | - nom de commande ou de programme ; |
120 | 67 | storres | - nom de variable, de fonction, de classe, de module ; |
121 | 67 | storres | - propri?t@?, param?tre, valeur, champ, objet, nom de balise ; |
122 | 67 | storres | - nom de cl? de registre ; |
123 | 67 | storres | - mot-cl? d'un langage ; |
124 | 67 | storres | . */ |
125 | 67 | storres | span.langElem {font-family : helvetica, arial, sans-serif; |
126 | 67 | storres | font-style : normal; |
127 | 67 | storres | font-weight : bold} |
128 | 67 | storres | /* R?pertoires, fichiers, extensions de fichier (e. g. .jpeg) */ |
129 | 67 | storres | span.pathfile {font-family: courier, monospace; |
130 | 67 | storres | font-style : italic; |
131 | 67 | storres | font-weight: normal} |
132 | 67 | storres | span.urlAddress{font-family : courier monospace; |
133 | 67 | storres | font-style : italic; |
134 | 67 | storres | font-weight : bold } |
135 | 67 | storres | /* ?l?ments "bloc" */ |
136 | 67 | storres | h1 {text-align : center ; |
137 | 67 | storres | font-size : 20pt ; |
138 | 67 | storres | font-weight : bold ; |
139 | 67 | storres | font-family : helvetica, arial, sans-serif} |
140 | 67 | storres | h2 {font-size : 16pt ; |
141 | 67 | storres | font-weight : bold ; |
142 | 67 | storres | font-family : helvetica, arial, sans-serif} |
143 | 67 | storres | h3 {font-size: 14pt ; |
144 | 67 | storres | font-weight : normal; |
145 | 67 | storres | font-family : helvetica, arial, sans-serif; |
146 | 67 | storres | margin-left : 10pt} |
147 | 67 | storres | h4 {font-size : 12pt; |
148 | 67 | storres | font-family : helvetica, arial , sans-serif; |
149 | 67 | storres | font-weight: normal; |
150 | 67 | storres | margin-left : 15pt} |
151 | 67 | storres | h5 {font-size : 12pt ; |
152 | 67 | storres | font-family : helvetica, arial, sans-serif; |
153 | 67 | storres | font-weight : normal; |
154 | 67 | storres | font-style : italic; |
155 | 67 | storres | margin-left : 15pt} |
156 | 67 | storres | h6 {font-size : 10pt; |
157 | 67 | storres | font-family : helvetica, arial, sans-serif; |
158 | 67 | storres | font-size : 8pt; |
159 | 67 | storres | font-weight : bold; |
160 | 67 | storres | font-style : normal; |
161 | 67 | storres | margin-left : 15pt; |
162 | 67 | storres | text-align : right} |
163 | 67 | storres | p {font-size : 10pt; |
164 | 67 | storres | font-family : helvetica, arial, sans-serif; |
165 | 67 | storres | margin-left : 20pt; |
166 | 67 | storres | margin-right : 20pt; |
167 | 67 | storres | text-align : justify ; |
168 | 67 | storres | text-indent : 2em} |
169 | 67 | storres | /* Listes */ |
170 | 67 | storres | ul {font-size: 10pt; |
171 | 67 | storres | font-family: helvetica, arial, sans-serif; |
172 | 67 | storres | text-align: justify; |
173 | 67 | storres | margin-left: 20pt; |
174 | 67 | storres | margin-right: 20pt} |
175 | 67 | storres | ol {font-size: 10pt; |
176 | 67 | storres | font-family: helvetica, arial, sans-serif; |
177 | 67 | storres | text-align: justify; |
178 | 67 | storres | margin-left: 20pt; |
179 | 67 | storres | margin-right: 20pt} |
180 | 67 | storres | dl {font-size: 10pt; |
181 | 67 | storres | font-family: helvetica, arial, sans-serif; |
182 | 67 | storres | margin-left: 20pt; |
183 | 67 | storres | margin-right: 20pt} |
184 | 67 | storres | dl dt {font-weight: bold} |
185 | 67 | storres | dd {font-size: 10pt; |
186 | 67 | storres | font-family: helvetica, arial, sans-serif; |
187 | 67 | storres | text-align: justify; |
188 | 67 | storres | margin-left: 10pt} |
189 | 67 | storres | /* Tableaux */ |
190 | 67 | storres | p.tableCaption {text-align : center ; |
191 | 67 | storres | font-size : 12pt ; |
192 | 67 | storres | font-weight : bold ; |
193 | 67 | storres | font-family : helvetica, arial, sans-serif; |
194 | 67 | storres | text-ident : 0pt } |
195 | 67 | storres | table {margin-left: 20pt; |
196 | 67 | storres | margin-right: 20pt} |
197 | 67 | storres | /* Deux options pour les cellules titres : soit un ?l?ment en-t?te (avec |
198 | 67 | storres | ligne et cellules), soit des ?l?ments cellule en-t?te. */ |
199 | 67 | storres | thead tr td {text-align: center; |
200 | 67 | storres | text-indent : 0pt; |
201 | 67 | storres | font-size: 10pt; |
202 | 67 | storres | font-family: helvetica, arial, sans-serif; |
203 | 67 | storres | font-weight: bold} |
204 | 67 | storres | th {text-align: center; |
205 | 67 | storres | text-indent : 0pt; |
206 | 67 | storres | font-size: 10pt; |
207 | 67 | storres | font-family: helvetica, arial, sans-serif; |
208 | 67 | storres | font-weight: bold} |
209 | 67 | storres | |
210 | 67 | storres | td {font-size : 10pt ; |
211 | 67 | storres | font-family : helvetica, arial, sans-serif; |
212 | 67 | storres | vertical-align: top; |
213 | 67 | storres | padding-left : 1em; |
214 | 67 | storres | padding-right : 1em} |
215 | 67 | storres | td.numeric {font-size : 10pt ; |
216 | 67 | storres | font-family : Courier New, Courier, monospace; |
217 | 67 | storres | font-weight : bold; |
218 | 67 | storres | vertical-align: top; |
219 | 67 | storres | text-align : right; |
220 | 67 | storres | padding-right : 2em} |
221 | 67 | storres | td.middle {font-size : 10pt ; |
222 | 67 | storres | font-family : helvetica, arial, sans-serif; |
223 | 67 | storres | vertical-align: middle} |
224 | 67 | storres | /* Pour ?viter les marges dans les cellules de tableau */ |
225 | 67 | storres | td p {font-size : 10pt; |
226 | 67 | storres | font-family : helvetica, arial, sans-serif; |
227 | 67 | storres | margin-left : 0pt; |
228 | 67 | storres | margin-right : 0pt; |
229 | 67 | storres | text-indent : 0} |
230 | 67 | storres | /* Introduction ? une (x*sous) section */ |
231 | 67 | storres | p.heading {font-size : 10pt; |
232 | 67 | storres | font-family : helvetica, arial, sans-serif; |
233 | 67 | storres | font-weight : bold; |
234 | 67 | storres | margin-left : 20pt; |
235 | 67 | storres | margin-right : 20pt; |
236 | 67 | storres | text-align : justify; |
237 | 67 | storres | text-indent : 0pt} |
238 | 67 | storres | /* Conclusion d'une (*sous-) section */ |
239 | 67 | storres | p.footer {font-size : 10pt; |
240 | 67 | storres | font-family : helvetica, arial, sans-serif; |
241 | 67 | storres | font-weight : bold; |
242 | 67 | storres | margin-left : 20pt; |
243 | 67 | storres | margin-right : 20pt; |
244 | 67 | storres | text-align : justify; |
245 | 67 | storres | text-indent : 0pt} |
246 | 67 | storres | /* Illustration */ |
247 | 67 | storres | div.illustration {text-align : center; |
248 | 67 | storres | margin : 15pt} |
249 | 67 | storres | /* Rien de bien d?fini encore pour ces mod?les (id?e : |
250 | 67 | storres | images avec texte ? gauche ou ? droite) */ |
251 | 67 | storres | img.right {} |
252 | 67 | storres | img.left {} |
253 | 67 | storres | p.illustrationCaption {font-family : Helvetica, arial, sans-serif ; |
254 | 67 | storres | font-size : 12pt; |
255 | 67 | storres | font-weight : bold; |
256 | 67 | storres | text-align : center; |
257 | 67 | storres | text-indent : 0pt } |
258 | 67 | storres | /* Sommaire */ |
259 | 67 | storres | ul.summary {font-family : Helvetica , Arial , sans-serif; |
260 | 67 | storres | font-size : 12pt} |
261 | 67 | storres | /* Filets horizontaux */ |
262 | 67 | storres | hr {} |
263 | 67 | storres | hr.fiftypc {margin-left: 25%; |
264 | 67 | storres | margin-right: 25%;} |
265 | 67 | storres | hr.twentypc {margin-left: 40%; |
266 | 67 | storres | margin-right: 40%;} |
267 | 67 | storres | /* Notes */ |
268 | 80 | storres | /* L'appel de note est r?alis? par un ?l?ment "a" de classe callNote */ |
269 | 67 | storres | a.callNote {} |
270 | 80 | storres | /* Le retour de note est r?alis? par un ?l?ment "a" de classe retFromNote */ |
271 | 67 | storres | a.retFromNote {} |
272 | 67 | storres | /* Liste des notes proprement dite */ |
273 | 67 | storres | ol.notes {margin-left: 0%; |
274 | 67 | storres | margin-right: 0%} |
275 | 67 | storres | /* ?lements de navigation */ |
276 | 67 | storres | table.navTable {border : none ; |
277 | 67 | storres | width : 100%} |
278 | 67 | storres | table.navTable td {width : 20% ; |
279 | 67 | storres | border : none ; |
280 | 67 | storres | text-align : center ; |
281 | 67 | storres | vertical-align : middle} |
282 | 67 | storres | /* ?l?ments divers (? trier)*/ |
283 | 67 | storres | /* ?l?ments pour la table des mati?res */ |
284 | 67 | storres | div.abstract {font-size : 12pt ; |
285 | 67 | storres | font-style : italic ; |
286 | 67 | storres | font-family : Helvetica, Arial , sans-serif ; |
287 | 67 | storres | margin-left : 50pt ; |
288 | 67 | storres | margin-right : 50pt ; |
289 | 67 | storres | margin-top : 15pt ; |
290 | 67 | storres | margin-bottom : 10pt ; |
291 | 67 | storres | border : solid ; |
292 | 67 | storres | padding : 5pt} |
293 | 67 | storres | div.abstract p {margin-left : 0pt; |
294 | 67 | storres | margin-right : 0pt; |
295 | 67 | storres | text-indent : 0pt} |
296 | 67 | storres | div.toc {margin-left : 50pt} |
297 | 67 | storres | ul.toc {font-size : 14pt ; |
298 | 67 | storres | font-family : Helvetica , Arial , sans-serif} |
299 | 80 | storres | </style>
|
300 | 67 | storres | <title>sageSLZ Notes</title> |
301 | 67 | storres | </head>
|
302 | 67 | storres | |
303 | 67 | storres | <body>
|
304 | 67 | storres | <h1>sageSLZ Notes</h1> |
305 | 67 | storres | |
306 | 67 | storres | <h2>The approximation interval problem</h2> |
307 | 67 | storres | |
308 | 67 | storres | <p>When Sollya computes an approximation polynomial for a given function,
|
309 | 81 | storres | degree and range, it also returns the approximation error (refered to, in the sequel, |
310 | 81 | storres | as the |
311 | 81 | storres | <span class="langElem">computedError</span> and the center of |
312 | 81 | storres | the interval as well). |
313 | 81 | storres | </p>
|
314 | 67 | storres | |
315 | 81 | storres | <p>Very often, we want to solve a slightly different problem: for a given
|
316 | 81 | storres | function, degree, lower bound and approximation error (referred to, in the |
317 | 81 | storres | sequel, as the |
318 | 81 | storres | <span class="langElem">targetError</span> ), compute the |
319 | 67 | storres | approximation polynomial and the upper bound of the interval comprised between |
320 | 81 | storres | it and the lower bound for which the approximation error stands. |
321 | 81 | storres | </p>
|
322 | 67 | storres | |
323 | 81 | storres | <p>The idea is to break a given initially “large” interval into a |
324 | 67 | storres | collection of smaller intervals because for the given function-degree-error the |
325 | 67 | storres | initial interval is too large.</p>
|
326 | 67 | storres | |
327 | 81 | storres | <p>The most naive approach is to:</p> |
328 | 67 | storres | <ol>
|
329 | 81 | storres | <li>give it a try with the initial data (a very probably too high upper bound
|
330 | 81 | storres | for the given <span class="langElem">targetError</span>);</li> |
331 | 69 | storres | <li>when you get a too large error, reduce (e. g. divide by 2) the interval by
|
332 | 69 | storres | lowering the upper bound until the computed error matches the target |
333 | 67 | storres | error;</li>
|
334 | 69 | storres | <li>this upper bound becomes the lower bound of the next interval, always
|
335 | 67 | storres | using the orginal upper bound and repeat the process until you can cover |
336 | 67 | storres | the all initial interval with the computed sub-interval.</li>
|
337 | 67 | storres | </ol>
|
338 | 67 | storres | |
339 | 67 | storres | <p>In step 2 you may have to compute several polynomials until the computed
|
340 | 81 | storres | error is below or equal to the expected error. But you must not decrease the |
341 | 81 | storres | interval width too agressively: there is no point in getting a too small |
342 | 81 | storres | approximation error since it multiplies the number of interval (and |
343 | 69 | storres | lengthens the subsequent manipulations that are made on each sub-interval).</p>
|
344 | 67 | storres | |
345 | 69 | storres | <p>In step 3 you probably inutily compute polynomials for too large intervals
|
346 | 67 | storres | and you could know it from the previous computations.</p>
|
347 | 67 | storres | |
348 | 69 | storres | <p>The whole idea is to reduce the number of polynomial computations and get the
|
349 | 81 | storres | maximum width (compatible with the target error).</p>
|
350 | 67 | storres | |
351 | 67 | storres | <p>This process has different aspects:</p> |
352 | 67 | storres | <ol>
|
353 | 67 | storres | <li>for a given interval (be it too small or too large) and the given
|
354 | 67 | storres | (computed) error, compute the new best upper bound;</li>
|
355 | 67 | storres | <li>reuse the computation already done in previous steps.</li> |
356 | 67 | storres | </ol>
|
357 | 67 | storres | |
358 | 81 | storres | <p>We use two strategies.</p> |
359 | 81 | storres | <p>The first is in the inner function that computes the first approximation
|
360 | 81 | storres | polynomial. If the upper bound is too high, we shrink the interval by a non |
361 | 81 | storres | linear (and complex) factor computed from the ratio beetwen the obtained |
362 | 81 | storres | error and the target error.<br>The whole idea is not to end up with a too
|
363 | 81 | storres | small interval.</p>
|
364 | 81 | storres | <p>This only takes into account aspect 1</p>. |
365 | 81 | storres | <p>The second strategy is in the outer function. In this function the
|
366 | 81 | storres | computed intervals returned by the inner function give all correct |
367 | 81 | storres | approximation errors. The computation of next upper bound will take into |
368 | 81 | storres | account the value of the previous interval and that of the previous |
369 | 81 | storres | computed error.</p>
|
370 | 81 | storres | <p>If the errors ratio is lower than 2, we try the same interval length
|
371 | 81 | storres | as given by the previous computation. If larger we increase the next |
372 | 81 | storres | interval but by a small margin (log2(errorsRatio).</p>
|
373 | 67 | storres | |
374 | 81 | storres | <p>In this case, aspects 1 and 2 are considered </p> |
375 | 81 | storres | |
376 | 81 | storres | <p>For the moment, we do not resort to more complex forcasting techniques
|
377 | 81 | storres | (using the derivative of the function?). This could be an option if the |
378 | 81 | storres | present strategies did not output enough performance. </p>
|
379 | 67 | storres | </body>
|
380 | 67 | storres | </html> |