wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> extremly annoying integral! - please help
        
(Message started by: Kaotis on Jan 19th, 2005, 9:41am)
Title: extremly annoying integral! - please help
Post by Kaotis on Jan 19th, 2005, 9:41am
[int]xxdx = ???
Title: Re: extremly annoying integral! - please help
Post by towr on Jan 19th, 2005, 10:07am
now that's a tricky one..

The integral doesn't result in an elementary function. So basicly there's no better way to write it then you allready did..
Title: Re: extremly annoying integral! - please help
Post by Icarus on Jan 19th, 2005, 7:37pm
There are a large number of elementary functions that are not the derivative of other elementary functions. This is one of them. When faced with these, we look for expressions which most easily allow us to calculate values. Surprisingly, expressing it as an integral is one of the best methods we have. Integrals are numerically very stable, so one can obtain good estimations easily (derivatives on the other hand are very unstable, so when confronted with a function defined in terms of a derivative we always look for another form).

So towr is right. [int]xxdx is pretty much the best form to express this function as. The only other reasonable alternative would be to express it as a Taylor series.
Title: Re: extremly annoying integral! - please help
Post by Kaotis on Jan 20th, 2005, 1:17am
Thank you for your replys but,

on 01/19/05 at 19:37:04, Icarus wrote:
 express it as a Taylor series.

And how do you do that?
Title: Re: extremly annoying integral! - please help
Post by towr on Jan 20th, 2005, 1:40am

on 01/19/05 at 19:37:04, Icarus wrote:
So towr is right.
Yay!! ;D

Here's an interesting piece I found at http://www.linux-egypt.org/archive/index.php/t-2103.html

Quote:
Outline of this integration problem
-----------------------------------

The algorithm for integration of elementary functions is known as the Risch algorithm. It will either compute the integral as an elementary function or else prove that the integral cannot be expressed as an elementary function.

For the integrand x^x, the Risch algorithm first converts it to exp-log form. Namely the integrand is:

exp(x*log(x)) .

We give names to the functions appearing here, namely

theta[1] = log(x), theta[2] = exp(x*theta[1]) .

We know that theta[1] is "transcendental over Q(x)" and we know that theta[2] is "transcendental over Q(x,theta[1])".

We now have the problem:

integral theta[2] dx .

Note that the "outermost" function in the integrand is theta[2], which is an exponential function.
Moreover, the integrand is a polynomial in theta[2].

For such a case, the integration theory tells us that the integral, if it exists as an elementary function, must be a similar polynomial in
theta[2],
namely

integral theta[2] dx = q(x)*theta[2] .

(Note that we need to know the theory behind this fact.)

We then differentiate both sides of the above equation, which yields

theta[2] = q'(x)*theta[2] + q(x)*(theta[2])' .

Now in this case, from the definition of theta[2] we have

(theta[2])' = (exp(x*log(x)))'
= exp(x*log(x)) * (log(x) + 1)
= theta[2] * (theta[1] + 1)

Therefore, we have

theta[2] = q'(x)*theta[2] + q(x)*(theta[1]+1)*(theta[2]) .

Since theta[2] is "transcendental over Q(x,theta[1])", we can equate coefficients of theta[2] on each side which gives

1 = q'(x) + (theta[1]+1)*q(x) .

Also, since theta[1] is "transcendental over Q(x)", equating
coefficients of this equation as polynomials in theta[1] gives

1 = q'(x) + q(x)
0 = q(x)

which has no solution.
(The second equation tells us that q(x) = 0 and therefore q'(x) = 0, which makes the first equation become 1 = 0, which is a contradiction.)

CONCLUSION: (integral x^x dx) does not exist as an elementary function.

-----------------------------------------------
Professor Keith Geddes
Symbolic Computation Group
School of Computer Science
University of Waterloo
200 University Avenue West
Waterloo ON N2L 3G1
CANADA

E-mail: kogeddes@uwaterloo.ca
URL: http://www.uwaterloo.ca/~kogeddes
-----------------------------------------------
Title: Re: extremly annoying integral! - please help
Post by Kaotis on Jan 20th, 2005, 4:10am
very interesting.
but still it doesn't give me an answer if i want to calculate the integral of this function from b to a.
:'(
Title: Re: extremly annoying integral! - please help
Post by towr on Jan 20th, 2005, 7:35am
The definite integral is known for a few values, but usually it's best to get the answer numerically.
Just chose a small value for dx and then sum f(i*dx)*dx from i=[a/dx] to [b/dx], or use some better approximation.
Title: Re: extremly annoying integral! - please help
Post by Barukh on Jan 20th, 2005, 9:09am
The chapter 4 of the following book (on line) has many numerical algorithms for integration of functions:

Numerical Recipes in C (http://www.library.cornell.edu/nr/cbookcpdf.html).

As you may see, it contains an enormous amount of information about practically any subject.
Title: Re: extremly annoying integral! - please help
Post by Kaotis on Jan 20th, 2005, 1:34pm

on 01/20/05 at 07:35:21, towr wrote:
Just chose a small value for dx and then sum f(i*dx)*dx from i=[a/dx] to [b/dx], or use some better approximation.


it's not a problem I've already build a small program that calculate an integral.

You said that this integral can be displayed as a Taylor series. right?
So how can i find this Taylor series?


Quote:
The chapter 4 of the following book (on line) has many numerical algorithms for integration of functions:

Numerical Recipes in C.

As you may see, it contains an enormous amount of information about practically any subject.


Great book, but from my first impression it deals more with algoritems then with what i need. (actually i don't know what i need :D )
Title: Re: extremly annoying integral! - please help
Post by towr on Jan 20th, 2005, 2:35pm

on 01/20/05 at 13:34:02, Kaotis wrote:
You said that this integral can be displayed as a Taylor series. right?
So how can i find this Taylor series?
Well, Icarus said that. But I'll give a shot, at something at least ;)

x^x = exp(x*log(x)) = [sum][supinfty]i=0 (x*log(x))i/i!
[int] xx = [int] [sum][supinfty]i=0 (x*log(x))i/i! = [sum][supinfty]i=0 [int] (x*log(x))i/i!
Title: Re: extremly annoying integral! - please help
Post by Icarus on Jan 20th, 2005, 4:49pm
How do you find any Taylor series? Let f(x) = [int]xxdx

Then f(x) = [sum]n f(n)(a)(x - a)n/n! (assuming that the series does in fact converge to f - this is not guaranteed).

You will not be able to expand it about 0 - f is not well-behaved near zero. But it will probably work for any other Real value.

f(1) = C (the constant of integration)
f'(x) = xx, so f'(1) = 1
f''(x) = xx(1 + ln x), so f''(1) = 11(1 + 0) = 1
f'''(x) = xx(1 + ln x)(1 + ln x + 1/x), so f'''(1) = 2
...

Really, though, this is only superior to numerical integration if you need to find f for a large number of values. Otherwise, numerical integration will produce the same answers without nearly as much effort.
Title: Re: extremly annoying integral! - please help
Post by Kaotis on Jan 20th, 2005, 9:54pm

on 01/20/05 at 16:49:20, Icarus wrote:
How do you find any Taylor series?

well you don't learn this in high school, anyway thank you for the effort.
but another interesting questoin i have in mind.
when X=0 is thier a meaning to 00?
or you can avoid that with som trick like you do with (x2-4)/x-2
?
Title: Re: extremly annoying integral! - please help
Post by towr on Jan 21st, 2005, 12:18am

on 01/20/05 at 21:54:04, Kaotis wrote:
but another interesting questoin i have in mind.
when X=0 is thier a meaning to 00?
As far as x^x is concerned there is some meaning to it, but only as a limit:
limit x->0 x^x = 1
In other cases what you might consider 0^0 may have a different value (f.i. limit x->0 0^x = 0).
Title: Re: extremly annoying integral! - please help
Post by THUDandBLUNDER on Jan 21st, 2005, 2:16am

Quote:
limit x->0 x^x = 1

Not necessarily. RTFFAQ (http://www.faqs.org/faqs/sci-math-faq/specialnumbers/0to0/).
Title: Re: extremly annoying integral! - please help
Post by towr on Jan 21st, 2005, 2:22am

on 01/21/05 at 02:16:37, THUDandBLUNDER wrote:
Not necessarily. RTFFAQ (http://www.faqs.org/faqs/sci-math-faq/specialnumbers/0to0/).
I can't find anything in that FAQ that disgrees with it..
Title: Re: extremly annoying integral! - please help
Post by Kaotis on Jan 21st, 2005, 4:19am
it's 1 if 0+
but if you go from the other side (-0) so it's lim ->  -1
Title: Re: extremly annoying integral! - please help
Post by Icarus on Jan 21st, 2005, 3:49pm
No, if x < 0, then xx is not even well-defined (for each rational value of x, it can be given any of a number of complex values; for irrational values of x, you could equally well give it any value on the circle or radius |x|^|x| about 0).

I take then that you are just starting in your study of calculus. In college, MacLaurin and Taylor series are a second semester Calculus topic, which is stll fairly early. Power series are a useful calculational tool when you can find them.
Title: Re: extremly annoying integral! - please help
Post by Eigenray on Jan 21st, 2005, 7:35pm
Another method for determining power series, which may or may not be easier than differentiating repeatedly, is as follows:

Let g(t) = (1+t)1+t = (1+t)(1+t)t = (1+t)etlog(1+t).
Substituting log(1+t) = t - t2/2 + t3/3 + O(t4),
g(t) = (1+t)et^2 - t^3/2 + t^4/3 + O(t^5),
and using ex = 1+x + x^2/2! + x^3/3! + ...,
g(t) = (1+t)[1 + (t2 - t3/2 +t4/3+...) + (t2+...)2/2 + O(t5) ]
= (1+t)[1 + t2 - t3/2 + 5t4/6 + O(t5) ]
= 1 + t + t2 + t3/2 + t4/3 + o(t5)
Integrating term by term, we get
[int](1+t)1+tdt = t + t2/2 + t3/3 + t4/8 + t5/15 + O(t6)
Title: Re: extremly annoying integral! - please help
Post by Kaotis on Jan 22nd, 2005, 12:40am

Quote:
I take then that you are just starting in your study of calculus.

Yes. But what I'm study doesn't satisfied me , so I come here  ;D




on 01/21/05 at 19:35:53, Eigenray wrote:
Another method for determining power series, which may or may not be easier than differentiating repeatedly, is as follows:

Let g(t) = (1+t)1+t = (1+t)(1+t)t = (1+t)etlog(1+t).
Substituting log(1+t) = t - t2/2 + t3/3 + O(t4),
g(t) = (1+t)et^2 - t^3/2 + t^4/3 + O(t^5),
and using ex = 1+x + x^2/2! + x^3/3! + ...,
g(t) = (1+t)[1 + (t2 - t3/2 +t4/3+...) + (t2+...)2/2 + O(t5) ]
= (1+t)[1 + t2 - t3/2 + 5t4/6 + O(t5) ]
= 1 + t + t2 + t3/2 + t4/3 + o(t5)
Integrating term by term, we get
[int](1+t)1+tdt = t + t2/2 + t3/3 + t4/8 + t5/15 + O(t6)


Nice...

Quote:
(1+t)etlog(1+t).
Substituting log(1+t) = t - t2/2 + t3/3 + O(t4)


should it be Ln and not Log or it's doesnt metter?
and I don't understand why log(1+t) = t - t2/2 + t3/3 + O(t4)?
Title: Re: extremly annoying integral! - please help
Post by Obob on Jan 22nd, 2005, 6:57am
To a mathematician Log always means Ln.  The base 10 log is only really studied because it is an easier concept to teach to high school students.  After all, the two functions only differ by a constant, since Log10[x]=Ln[x]/Ln[10].  If you look in most higher math books on analysis and such, it will be stated within either the introduction or the first page or so that Log denotes the natural logarithm.

The formula Kaotis speaks of for log[1+t] follows from expanding log[1+t] as a Taylor series about t=0.  For a further discussion of Taylor series see http://mathworld.wolfram.com/TaylorSeries.html.
Title: Re: extremly annoying integral! - please help
Post by THUDandBLUNDER on Jan 22nd, 2005, 10:23am

on 01/21/05 at 02:22:19, towr wrote:
I can't find anything in that FAQ that disgrees with it..

Yeah, sorry, I misread your post.
Title: Re: extremly annoying integral! - please help
Post by SWF on Jan 24th, 2005, 5:49pm
I don't know how useful the series expansions given above would be for this integral. When the upper limit of integration is large, accuracy at the upper end of the integral is all that matters since this function grows so rapidly. In that case expanding a Taylor series for accuracy at the lower limit of integration is not a good idea. Also, it will be tough to represent the xx rate of growth with a polynomial unless number of terms approaches int(x).

With this in mind, if the lower limit of integration is 'a', and upper limit is 'b' I come up with the following approximate value for the integral:

   e-b*( (b*e)b - (b*e)a ) / ( 1 + log(b) )

This works well for large b:  within 0.97% for a=1, b=10 and within 0.11% for a=1, b=40.

Adding a second term improves accuracy but the simple formula gets more complex. Add the following to the above for more accuracy:

 bb-1/ ( 1 + log(b) )3
 -baea-b/(2*b*(1+log(b))3)*(2+2b-2a+b*b+a*a-2ab+2(b-a)(1+b-a)log(b) + ( (b-a)*log(b) )2 )

The 2nd line above is part of the 2nd term, but is likely to be negligible compared to the first line. This additional term brings the approximation to within 0.06% for a=1, b=10, and within 0.001% for a=1, b=40.

When b is small, the accuracy is not so great- only within 8% for a=0.1, b=2. In that case designing a formula suitable for smaller values would be preferred. Part of the reason for this is that between 0 and 1, xx does not have drastically different values, and the lower end would not be negligible.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board