help in Integral Maximization

**Ackbeet** · August 23rd 2010, 01:37 PM

I don't just tell people my answers. But I'll help you to arrive at it.

First idea: assume equal intervals. Then the area under the linear pieces $\{x_{1},\dots,x_{N}\}$ paired with $\{y_{1},\dots,y_{N}\}$ is given by the trapezoidal rule

$\int_{x_{1}}^{x_{N}}f(x)\,dx=\frac{x_{N}-x_{1}}{N}(y_{1}+2y_{2}+2y_{3}+\dots+2y_{N-1}+y_{N}).$

In looking at this formula, what values can I swap without changing the sum?

**mido22** · August 23rd 2010, 01:39 PM

Originally Posted by Ackbeet

I don't just tell people my answers. But I'll help you to arrive at it.

First idea: assume equal intervals. Then the area under the linear pieces $\{x_{1},\dots,x_{N}\}$ paired with $\{y_{1},\dots,y_{N}\}$ is given by the trapezoidal rule

$\int_{x_{1}}^{x_{N}}f(x)\,dx=\frac{x_{N}-x_{1}}{N}(y_{1}+2y_{2}+2y_{3}+\dots+2y_{N-1}+y_{N}).$

In looking at this formula, what values can I swap without changing the sum?

i can't understand anything from these formula

**Ackbeet** · August 23rd 2010, 05:17 PM

Whoops. I forgot the factor of two. It should be the following:

$\displaystyle{\int_{x_{1}}^{x_{N}}f(x)\,dx=\frac{x _{N}-x_{1}}{2N}(y_{1}+2y_{2}+2y_{3}+\dots+2y_{N-1}+y_{N})}.$

Here is the explanation of this formula: the LHS is merely a symbol representing, in this case, the area under all the piecewise linear functions (another way to think of it: it's the sum of all the areas of the trapezoids).

The RHS of this formula shows you how to compute that area. To get this formula, merely note that the width of each trapezoid is equal to the width of the whole interval divided by the number of intervals, which is

$\displaystyle{\frac{x_{N}-x_{1}}{N}}.$

Now, the area of the jth trapezoid is given by (merely translating the formula you gave me):

$\displaystyle{\frac{x_{N}-x_{1}}{N}\left(\frac{y_{j}+y_{j+1}}{2}\right)}.$

You can think of this expression as the width times the average of the heights on the right and left sides of the subinterval. Does this make sense?

Now, if I add all those areas up, I get this:

$\displaystyle{\frac{x_{N}-x_{1}}{N}\left(\frac{y_{0}+y_{1}}{2}+\frac{y_{1}+y _{2}}{2}+\dots+\frac{y_{N-1}+y_{N}}{2}\right)}$

$\displaystyle{=\frac{x_{N}-x_{1}}{2N}(y_{0}+y_{1}+y_{1}+y_{2}+\dots+y_{N-1}+y_{N})}$

$\displaystyle{=\frac{x_{N}-x_{1}}{2N}(y_{0}+2y_{1}+2y_{2}+\dots+2y_{N-1}+y_{N}).}$

All the middle terms are in the sum twice, and the endpoints are there only once.

Does this make the formula clear to you?

**mido22** · August 23rd 2010, 06:55 PM

Originally Posted by Ackbeet

Whoops. I forgot the factor of two. It should be the following:

$\displaystyle{\int_{x_{1}}^{x_{N}}f(x)\,dx=\frac{x _{N}-x_{1}}{2N}(y_{1}+2y_{2}+2y_{3}+\dots+2y_{N-1}+y_{N})}.$

Here is the explanation of this formula: the LHS is merely a symbol representing, in this case, the area under all the piecewise linear functions (another way to think of it: it's the sum of all the areas of the trapezoids).

The RHS of this formula shows you how to compute that area. To get this formula, merely note that the width of each trapezoid is equal to the width of the whole interval divided by the number of intervals, which is

$\displaystyle{\frac{x_{N}-x_{1}}{N}}.$

Now, the area of the jth trapezoid is given by (merely translating the formula you gave me):

$\displaystyle{\frac{x_{N}-x_{1}}{N}\left(\frac{y_{j}+y_{j+1}}{2}\right)}.$

You can think of this expression as the width times the average of the heights on the right and left sides of the subinterval. Does this make sense?

Now, if I add all those areas up, I get this:

$\displaystyle{\frac{x_{N}-x_{1}}{N}\left(\frac{y_{0}+y_{1}}{2}+\frac{y_{1}+y _{2}}{2}+\dots+\frac{y_{N-1}+y_{N}}{2}\right)}$

$\displaystyle{=\frac{x_{N}-x_{1}}{2N}(y_{0}+y_{1}+y_{1}+y_{2}+\dots+y_{N-1}+y_{N})}$

$\displaystyle{=\frac{x_{N}-x_{1}}{2N}(y_{0}+2y_{1}+2y_{2}+\dots+2y_{N-1}+y_{N}).}$

All the middle terms are in the sum twice, and the endpoints are there only once.

Does this make the formula clear to you?

but with this formula and the test case :
4
2 3 5 6
1 2 1 2

= (6-2)/(2*4)*(1+4+2+2)=4.5
and the correct answer is 7

**Ackbeet** · August 24th 2010, 02:09 AM

Your test case has non-uniform x-intervals, for which the formula here is invalid. If you have non-uniform x-intervals, then you have to use the more general formula:

$\displaystyle{\int_{a}^{b}f(x)\,dx=\frac{1}{2}\sum _{j=2}^{N}(x_{j}-x_{j-1})(y_{j}+y_{j-1}).}$

For your test case, this more general formula yields
$\displaystyle{\int_{a}^{b}f(x)\,dx=\frac{1}{2}\lef t[1\times 3+2\times 3+1\times 3\right]=\frac{1}{2}\,(4\times 3)=6.}$

I don't think the correct answer is 7. Check your work again.

I think you might find it easier to work with the uniform-interval formula. It certainly provides more ideas readily to my mind.

**mido22** · August 24th 2010, 02:51 AM

Originally Posted by Ackbeet

Your test case has non-uniform x-intervals, for which the formula here is invalid. If you have non-uniform x-intervals, then you have to use the more general formula:

$\displaystyle{\int_{a}^{b}f(x)\,dx=\frac{1}{2}\sum _{j=2}^{N}(x_{j}-x_{j-1})(y_{j}+y_{j-1}).}$

For your test case, this more general formula yields
$\displaystyle{\int_{a}^{b}f(x)\,dx=\frac{1}{2}\lef t[1\times 3+2\times 3+1\times 3\right]=\frac{1}{2}\,(4\times 3)=6.}$

I don't think the correct answer is 7. Check your work again.

I think you might find it easier to work with the uniform-interval formula. It certainly provides more ideas readily to my mind.

thx i will try now but the correct answer is really 7 see problem link thx ackbeet >>

**Ackbeet** · August 24th 2010, 02:54 AM

Where do you get 7? I quote from the link:

...the integral of the polygonal line is the shaded area, with a value of 6.

**mido22** · August 24th 2010, 02:55 AM

Originally Posted by Ackbeet

Where do you get 7? I quote from the link:

here in the second test case
https://www.spoj.pl/problems/INTEGMAX/

**Ackbeet** · August 24th 2010, 03:00 AM

Ah, I see it now. Well, the author is contradicting himself there. The picture at the beginning of that file is precisely the same test case as the one where, later, he says the area is 7. The 7 is a typo. Trust me, the answer is 6. The author was correct the first time.

**mido22** · August 24th 2010, 03:03 AM

Originally Posted by Ackbeet

Ah, I see it now. Well, the author is contradicting himself there. The picture at the beginning of that file is precisely the same test case as the one where, later, he says the area is 7. The 7 is a typo. Trust me, the answer is 6. The author was correct the first time.

i know that sokution of picture is 6
but when you change Y,s to this range
1,2,2,1
the answer will be seven
some one give me hint
he told me about trapiziums , and said that each height will be x2-x1 and so on but he left for me to choose Y,s
and his solution accepted???

**mido22** · August 24th 2010, 03:18 AM

i found a solution
i should sort Y values
then i should take height as follows
h[0]=x[1]-x[0] , h[n]=h[n]-h[n-1]
then loop from i=0 to n
h[i+1]=x[i+2]-x[i]
finally
loop from i=0 to n
sum=sum+(h[i]*y[i])
then the answer is y/2

thx very much for ur help

**Ackbeet** · August 24th 2010, 03:22 AM

Yeah, I mis-spoke. The 7 comes from the maximized area, with the assignment of y's that you mentioned in post # 40. I will have to think about your solution. Do you understand your solution as posted in Post # 41?

**mido22** · August 24th 2010, 03:24 AM

Originally Posted by Ackbeet

Yeah, I mis-spoke. The 7 comes from the maximized area, with the assignment of y's that you mentioned in post # 40. I will have to think about your solution. Do you understand your solution as posted in Post # 41?

i think that

but i am waiting for ur reply about ur opinion for this solution

**Ackbeet** · August 24th 2010, 04:35 AM

Well, for the uniform interval case, with area formula given and explained in Post # 33, I think it's fairly clear that you can swap any of the interior points (points 2 through N-1), and not change the sum, right? In addition, you can swap the two endpoints (points 1 and N) without changing the sum. Does that suggest anything to you?

I don't yet have a theory for the non-uniform case, although I do have some ideas. I'll have to think about it.

The algorithm you posted in Post # 41 is a mystery to me. Where you found that algorithm, is there an explanation for why it produces the maximized area?

**mido22** · August 24th 2010, 04:40 AM

Originally Posted by Ackbeet

Well, for the uniform interval case, with area formula given and explained in Post # 33, I think it's fairly clear that you can swap any of the interior points (points 2 through N-1), and not change the sum, right? In addition, you can swap the two endpoints (points 1 and N) without changing the sum. Does that suggest anything to you?

I don't yet have a theory for the non-uniform case, although I do have some ideas. I'll have to think about it.

The algorithm you posted in Post # 41 is a mystery to me. Where you found that algorithm, is there an explanation for why it produces the maximized area?

my father told me that

but he is in his work nw
and the solution he told me is accepted
but u make him reach this formula by your idea with trapeziums
i think u can get better formula waiting u

Thread: help in Integral Maximization

LinkBack

Thread Tools

Display

Similar Math Help Forum Discussions

Maximization

Maximization

Maximization

Maximization

Maximization

Search Tags