on Mon Jul 02 2007, "John Maddock" <john-AT-johnmaddock.co.uk> wrote:

> The main index page you refer to there scrolls so slowly on my

> system as to be unusable - the sample page

>

http://randysimons.com/overige/multicolumn/ is much better in this

> respect, but the amount of scrolling up and down to read the columns

> is IMO intolerable. How would this cope with a page like this:

>

http://freespace.virgin.net/boost.regex/toolkit/html/math_toolkit/backgrounders/remez.html> that which as well as being much longer than the average reference

> page has more than it's fair share of media objects?

One would columnize entire sections, or tuples of sections, before

moving on to a separate area. So for example (your page uses a

subheading that matches the main heading, which is a bit weird. I also

used elipses liberally because you'd be able to fit lots more

horizontally in a column than I can here with a fixed-width font.

+------------------------------+------------------------------+------------------------------+

|** The Remez Method ** | We want to find the "best" | In the following discussion |

| |rational approximation, where |we'll use a concrete example |

|The Remez algorithm is a |"best" is defined to be the |to illustrate the Remez |

|methodology for locating the |approximation that has the |method: an approximation to |

|minimax rational approximation|least deviation from f(x). We |the function ex over the range|

|to a function. This short |can measure the deviation by |[-1, 1]. |

|article gives a brief overview|way of an error function: | |

|of the method, but it should | |Before we can begin the Remez |

|not be regarded as a thorough |Eabs(x) = f(x) - R(x) |method, we must obtain an |

|theoretical treatment, for | |initial value for the location|

|that you should consult your |which is expressed in terms of|of the extrema of the error |

|favorite textbook. |absolute error, but we can |function. We could "guess" |

| |equally use relative error: |these, but a much closer first|

|Imagine that you want to |... |approximation can be obtained |

|approximate some function f(x)| |by first constructing an |

|by way of a rational function | Unfortunately we don't know |interpolated polynomial |

|R(x), where R(x) may be either|where the extrema of the error|approximation to f(x). |

|a polynomial P(x) or a ratio |function are located! | |

|of two polynomials P(x)/Q(x) | |In order to obtain the N+1 |

|(a rational | ** The Remez Method ** |coefficients of the |

|function). Initially we'll | |interpolated polynomial we |

|concentrate on the polynomial |The Remez method is an |need N+1 points (x0...xN): |

|case, as it's by far the |iterative technique which, |with our interpolated form |

|easier to deal with, later |given a broad range of |passing through each of those |

|we'll extend to the full |assumptions, will converge on |points that yields N+1 |

|rational function case. |the extrema of the error |simultaneous equations: |

| |function, and therefore the | |

| |minimax solution. | |

+------------------------------+------------------------------+------------------------------+

| f(xi) = P(xi) = c0+ c1xi... +| |

|cNxiN | |

| | |

|Which can be solved for the | |

|coefficients c0...cNin P(x). | |

| | |

|Obviously this is not a | |

|minimax solution, indeed our | Initial Interpolated Approximation |

|only guarantee is that f(x) | |

|and P(x) touch at N+1 | |

|locations, away from those | |

|points the error may be | |

|arbitrarily large. However, we| |

|would clearly like this | |

|initial approximation to be as| |

|close to f(x) as possible, and+------------------------------+------------------------------+

|it turns out that using the | Which has a peak relative | ** Remez Step 1 *** |

|zeros of an orthogonal |error of 1.2x10-3. | ... |

|polynomial as the initial | | |

|interpolation points is a good|While this is a pretty good | |

|choice. In our example we'll |approximation already, judging| |

|use the zeros of a Chebyshev |by the shape of the error | |

|polynomial as these are |function we can clearly do | |

|particularly easy to |better. Before starting on the| |

|calculate, interpolating for a|Remez method propper, we have | |

|polynomial of degree 4, and |one more step to perform: | |

|measuring relative error we |locate all the extrema of the | |

|get the following error |error function, and store | |

|function: |these locations as our initial| |

| |Chebyshev control points. | |

| | ... | |

+------------------------------+------------------------------+------------------------------+

--

Dave Abrahams

Boost Consulting

http://www.boost-consulting.comThe Astoria Seminar ==>

http://www.astoriaseminar.com-------------------------------------------------------------------------

This SF.net email is sponsored by DB2 Express

Download DB2 Express C - the FREE version of DB2 express and take

control of your XML. No limits. Just data. Click to get it now.

http://sourceforge.net/powerbar/db2/_______________________________________________

Boost-docs mailing list

[hidden email]
Unsubscribe and other administrative requests:

https://lists.sourceforge.net/lists/listinfo/boost-docs