Statistiques
| Révision :

root / pobysoPythonSage / src / sageSLZ / sageSLZ-Notes.html

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 &ldquo;large&rdquo; 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>