[EventHorizon]

If you have an unknown linear function, f(x), and you wish to find it's definite integral between z and z+1, the value can be found if you know the value of the function at those end points, z and z+1. The value of the definite integral is (f(z)+f(z+1))/2.

As shown in the topic "Integrate an unknown quadratic," the same thing can be done with quadratics. The value of a definite integral between z and z+2 is (f(z)+4*f(z+1)+f(z+2))/3.

Ignoring the constant factor (so the coefficient for f(z)=1), the pattern for linear functions is (1,1).

The pattern for quadratic functions is (1,4,1).

Does the same possibility exist for cubics? If so, what is the pattern for cubics?

For which degree of polynomials can you do this? Is there a way to predict the pattern for an nth-degree polynomial?

I know the answer to 2 of the questions, and have a good idea (but may be way off) on the third and fourth.

[Guest]

From f(z) to f(z+3), the cofficients would be (3/2,9/2,9/2,3/2) for definite integral between (z+3) and z

Going by how I solved it, I would say such a solution is possible for any degree of polynomial.

Also, I observed that the sum of all coefficients is equal to n(n+1) where n is the degree of polynomial.

Further generalisation can be made on this and it is possible to derive a generalised formula for a polynimal of nth degree. But I'm too tired for that now

Edited September 16, 2010 by DeeGee

[Guest]

On further thought, finding the coefficients here is the same as expressing (x+n)ⁿ - xⁿ as a function of (x+n-1)^(n-1), (x+n-2)^(n-2) and so on. This is always possible because you will always have as many equations as the number of variables.

[Guest]

For which degree of polynomials can you do this? Is there a way to predict the pattern for an nth-degree polynomial?

I'm sure it's possible for any degree of polynomial.

It is always possible to derive an exact solution of the derivative from the finite difference formula of a polynomial of degree n (as long as you believe in Taylor's theorem) using at most an n-point stencil (or is it n-1?). It's easier when the kernel is uniform, which, thankfully, it is in this case. Anyway, you end up with an n-diagonal matrix of finite difference coefficients, the inverse of which would be the coefficients for computing the integral of f'(x), a polynomial of degree n-1. It should be sufficient then to show that any such matrix is invertible, which IIRC is true if none of the occupied diagonals contains a zero, which they do not.

I suppose it might be just as easy to develop a 'finite sum' method directly, but whatever. Maybe later...

[EventHorizon]

From f(z) to f(z+3), the cofficients would be (3/2,9/2,9/2,3/2) for definite integral between (z+3) and z

Going by how I solved it, I would say such a solution is possible for any degree of polynomial.

Also, I observed that the sum of all coefficients is equal to n(n+1) where n is the degree of polynomial.

Further generalisation can be made on this and it is possible to derive a generalised formula for a polynimal of nth degree. But I'm too tired for that now

I asked for the first coefficient to be normalized to 1, which makes the correct pattern of (1,3,3,1). Though your coefficients are off by a factor of 4. A quick check using f(x)=1 shows your coefficients producing a value of 12, but the area is obviously 3. Maybe you just normalized them funny, or omitted the /4 from integration.

Just two quick and easily provable observations. The pattern will be symmetric. The sum of the coefficients will be the degree of the polynomial (equivalently the length being integrated over), since f(x)=1 should work out right.

I haven't calculated it out, but I'm curious as to what the pattern is for quartics. Since you should be able to plug in a quadratic and have it work out, but you have the right values sampled to calculate using the quadratic's pattern as well. Interesting stuff...

I agree that it seems like it is always possible, and d3k3 looks like he's found a method that could lead to a proof (though I don't see the diagonalization yet).

This just leaves predicting the pattern (and possibly a more rigorous existence proof).

[Guest]

This just leaves predicting the pattern (and possibly a more rigorous existence proof).

It would seem that we've been guilty of over-thinking...

For any set of n points (x_i, y_i) where all x_i are all different, there exists a unique polynomial of order not exceeding n-1 that passes through all points. Once it is known, you can then simply evaluate its definite integral between the appropriate limits. Note that the value of x₀ is arbitrary, since you could just as easily compute the polynomial as a function of (x-x₀). I don't know of a closed-form solution for obtaining the polynomial coefficients, but it is proven that such a polynomial exists, and, because all polynomials have an antiderivative, the integral can therefore always be evaluated.

[Guest]

Of course there's a closed-form solution to the polynomial: the Lagrange polynomial! And you don't even have to compute it, just its basis functions.

[EventHorizon]

It would seem that we've been guilty of over-thinking...

For any set of n points (x_i, y_i) where all x_i are all different, there exists a unique polynomial of order not exceeding n-1 that passes through all points. Once it is known, you can then simply evaluate its definite integral between the appropriate limits. Note that the value of x₀ is arbitrary, since you could just as easily compute the polynomial as a function of (x-x₀). I don't know of a closed-form solution for obtaining the polynomial coefficients, but it is proven that such a polynomial exists, and, because all polynomials have an antiderivative, the integral can therefore always be evaluated.

As you say, the values (and x positions) of f(x), f(x+1), ..., f(x+n), uniquely define a polynomial of at most order n. However, that says nothing about whether the definite integral is obtainable through a simple linear combination of those values, never needing to find the function itself or perform the integration.

The way I see it, there are more variables than equations. When multiplied out, (x+n)^n has a coefficient for each power of x up to n. For the whole polynomial, there are n of these terms of decreasing degree. So there's a total of about n*(n+1)/2 variables. n of these always cancel out in the definite integral, so there's something like n(n-1)/2 variables and n+1 equations. Granted, those variables are somewhat correlated and always seem to work out nicely.

Edited September 17, 2010 by EventHorizon

[EventHorizon]

I calculated the pattern for quartics. Because it doesn't work out as neatly as for the others, I'll just make the coefficients integral instead of making the first one 1.

The pattern is (7,32,12,32,7) with a factor of (2/45) which assumes the points are spaced out 1 apart, which was part of the stated problem.

Earlier I stated that it would be interesting to find out since you could plug in a quadratic and find the answer a couple ways. You can actually break up the answer for quartics into the pattern for quadratics.

(f(0) + 4*f(1) + f(2))*8 + (f(2) + 4*f(3) + f(4))*8 - (f(0) + 4*f(2) + f(4))

The constant factor makes sense as well since combining the 7.5 (15/2) times the value of the quadratic pattern that the above gives and the 1/3 factor from quadratics results in 1/3 * 2/15 = 2/45

[Guest]

It seems as though Mssrs. Newton & Cotes considered this problem some 300 years ago....