Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #39370

Re: Fiting squares under a curve.

Show all headers | View raw

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> OK, lets try a more formal approach.

That's always my preference...  Thanks.

> We have a function f(x) which is defined over x = 0.0 to 1.0, and is
> always non-negative.
>
> We have a set of values x_0 ... x_N, in ascending order. x_0 = 0.0,
> x_N = 1.0. These define N-1 non-overlapping intervals.

I think you mean you have an N and wish to find the x_i.  If you have
the x_i you can't change anything to minimise the "error" function
you've defined.

But I think you suggested that N was also up for grabs because you
could, within reason, add cells (but I am not 100% sure I know what the
cells correspond to in this version).

> The integral f(x) from x=0 to x = 1.0 is known to be less than 1.0.
>
> The optimisation problem is to define the set of points such that the sum
>
> for each interval 
>
> | integral f(x) from x_i to x_i+1 - (x_i+1 - x_i)^2 |
>
> is at a minimum.

A curious problem.  I can't visualise it well.  I suspect it's hard.

> Additionally, an interval cannot be less than delta_min, which will be
> 1 pixel, so usually between 0.01 and 0.001, because the range x = 0 -
> 1.0 will generally span 100 to 1000 pixels.

So let me check a few cases.  For f(x) = 1 the only perfect solution has
N = 2 and the x_i being just [0,1].  If N is given and > 2, then the
best solution is to pack the internal x_i (0 < i < N) as close to 0 or 1
as possible.

And for f(x) = 1/2 the optimum solution has N = 3 and the x_i at [0,
1/2, 1].  Again, for N > 3, packing the extra points close to 0, 1/2 or
1 seems optimal.

For f(x) = x, I don't know the best N, but for N = 3 the optimum
solution is (I think) [0, 1/3, 1] with an error of 5/90.  I don't think
that can be beaten for larger N, but I've not played around with it
much.

Do you agree with these solutions?

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 06:59 -0700
  Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-15 15:17 +0100
    Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 08:06 -0700
      Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-15 22:33 +0100
        Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 15:01 -0700
          Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-16 00:33 +0100
            Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-17 03:25 -0700
              Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-17 14:22 +0100
                Re: Fiting squares under a curve. Andy Walker <anw@cuboid.co.uk> - 2021-09-17 16:25 +0100
                Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-17 20:59 +0100
                Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-23 02:14 -0700

csiph-web