Révision 81 pobysoPythonSage/src/sageSLZ/sageSLZ-Notes.html
| sageSLZ-Notes.html (revision 81) | ||
|---|---|---|
| 306 | 306 |
<h2>The approximation interval problem</h2> |
| 307 | 307 |
|
| 308 | 308 |
<p>When Sollya computes an approximation polynomial for a given function, |
| 309 |
degree and range, it also returns the approximation error (and the center of |
|
| 310 |
the interval as well).</p> |
|
| 309 |
degree and range, it also returns the approximation error (refered to, in the sequel, |
|
| 310 |
as the |
|
| 311 |
<span class="langElem">computedError</span> and the center of |
|
| 312 |
the interval as well). |
|
| 313 |
</p> |
|
| 311 | 314 |
|
| 312 |
<p>Very often we want to solve a slightly different problem: for a given |
|
| 313 |
function, degree, lower bound and approximation error, computed the |
|
| 315 |
<p>Very often, we want to solve a slightly different problem: for a given |
|
| 316 |
function, degree, lower bound and approximation error (referred to, in the |
|
| 317 |
sequel, as the |
|
| 318 |
<span class="langElem">targetError</span> ), compute the |
|
| 314 | 319 |
approximation polynomial and the upper bound of the interval comprised between |
| 315 |
it and the upper bound for which the approximation error stands.</p> |
|
| 320 |
it and the lower bound for which the approximation error stands. |
|
| 321 |
</p> |
|
| 316 | 322 |
|
| 317 |
<p>Very often the idea is to break a given “large” into a
|
|
| 323 |
<p>The idea is to break a given initially “large” interval into a
|
|
| 318 | 324 |
collection of smaller intervals because for the given function-degree-error the |
| 319 | 325 |
initial interval is too large.</p> |
| 320 | 326 |
|
| 321 |
<p>The naive approach is to:</p> |
|
| 327 |
<p>The most naive approach is to:</p>
|
|
| 322 | 328 |
<ol> |
| 323 |
<li>give it a try with the initial data;</li> |
|
| 329 |
<li>give it a try with the initial data (a very probably too high upper bound |
|
| 330 |
for the given <span class="langElem">targetError</span>);</li> |
|
| 324 | 331 |
<li>when you get a too large error, reduce (e. g. divide by 2) the interval by |
| 325 | 332 |
lowering the upper bound until the computed error matches the target |
| 326 | 333 |
error;</li> |
| ... | ... | |
| 330 | 337 |
</ol> |
| 331 | 338 |
|
| 332 | 339 |
<p>In step 2 you may have to compute several polynomials until the computed |
| 333 |
error is below or equal to the expected error. You must not decrease the |
|
| 334 |
interval width too agressively. There is no point in getting a too small approximation error since it multiplies the number of interval (and |
|
| 340 |
error is below or equal to the expected error. But you must not decrease the |
|
| 341 |
interval width too agressively: there is no point in getting a too small |
|
| 342 |
approximation error since it multiplies the number of interval (and |
|
| 335 | 343 |
lengthens the subsequent manipulations that are made on each sub-interval).</p> |
| 336 | 344 |
|
| 337 | 345 |
<p>In step 3 you probably inutily compute polynomials for too large intervals |
| 338 | 346 |
and you could know it from the previous computations.</p> |
| 339 | 347 |
|
| 340 | 348 |
<p>The whole idea is to reduce the number of polynomial computations and get the |
| 341 |
maximum width (compatible with the expected approwimaiton error).</p>
|
|
| 349 |
maximum width (compatible with the target error).</p>
|
|
| 342 | 350 |
|
| 343 | 351 |
<p>This process has different aspects:</p> |
| 344 | 352 |
<ol> |
| ... | ... | |
| 347 | 355 |
<li>reuse the computation already done in previous steps.</li> |
| 348 | 356 |
</ol> |
| 349 | 357 |
|
| 350 |
<p>For point 1, can something be done with the derivative at the upper bound or |
|
| 351 |
at the center point of the interval (also given by Sollya).</p> |
|
| 358 |
<p>We use two strategies.</p> |
|
| 359 |
<p>The first is in the inner function that computes the first approximation |
|
| 360 |
polynomial. If the upper bound is too high, we shrink the interval by a non |
|
| 361 |
linear (and complex) factor computed from the ratio beetwen the obtained |
|
| 362 |
error and the target error.<br>The whole idea is not to end up with a too |
|
| 363 |
small interval.</p> |
|
| 364 |
<p>This only takes into account aspect 1</p>. |
|
| 365 |
<p>The second strategy is in the outer function. In this function the |
|
| 366 |
computed intervals returned by the inner function give all correct |
|
| 367 |
approximation errors. The computation of next upper bound will take into |
|
| 368 |
account the value of the previous interval and that of the previous |
|
| 369 |
computed error.</p> |
|
| 370 |
<p>If the errors ratio is lower than 2, we try the same interval length |
|
| 371 |
as given by the previous computation. If larger we increase the next |
|
| 372 |
interval but by a small margin (log2(errorsRatio).</p> |
|
| 352 | 373 |
|
| 353 |
<p>For point 2, can some type of data structure keep the informations (which |
|
| 354 |
ones ?) and allow for an efficient reuse.</p> |
|
| 355 |
|
|
| 356 |
<p>Adjacent question: is it possible, given a the result of a previous |
|
| 357 |
computation, to forecast the effect on the approximation precision of a degree |
|
| 358 |
in(de)crease?</p> |
|
| 374 |
<p>In this case, aspects 1 and 2 are considered </p> |
|
| 375 |
|
|
| 376 |
<p>For the moment, we do not resort to more complex forcasting techniques |
|
| 377 |
(using the derivative of the function?). This could be an option if the |
|
| 378 |
present strategies did not output enough performance. </p> |
|
| 359 | 379 |
</body> |
| 360 | 380 |
</html> |
Formats disponibles : Unified diff