This is a tricky problem that seems to defy wolfram alpha, most/all of the commercially available numerical integrators on the market, and even my trusty TI-84.

Evaluate \[ \int_{-\pi}^{\pi} \left(\frac{x}{\pi}\right)^{100001}\sin(x) dx \] and in general, write an algorithm that can compute \[ S_n = \int_{-\pi}^{\pi} \left(\frac{x}{\pi}\right)^{n}\sin(x) dx \] to at least 10 digits of accuracy in linear time.

Hint: \(S_n \le 2\), why?

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestFor \(n\) even, the integral is zero. For \(n\) odd, we may use the series expansion of \(\sin(x)\). But faster methods might exist.

Log in to reply

\(1.9738221879\times 10^{-9}\)

aka \(\frac{2\pi^2}{(n+1)(n+2)}\) for odd n

But why did you put up the spoiler? It is not hard to get the definite integral for say n = 1..10. Then not hard to get the pattern and hence the basic recurrence. Then not hard to compare to the series for \(\sin\pi\) and consider the error.

Log in to reply

Haha, nice job: that's a first order approximation, the solution is actually \[S_n = -\sum_{\Delta=1}^\infty \frac{(-1)^\Delta 2\pi^{2\Delta}}{(2\Delta)!{n\choose 2\Delta}}\]

I'm assuming you mean the spoiler I posted on Chandler's post: I wanted to encourage people to derive the full series rather than the obvious pattern. While the error of your method decays w.r.t to \(O(n^{-4})\), it may not be very accurate for low values of \(n\).

The exercise was given more as a word of caution: an elegant solution isn't always great; especially when working in the domain of numerical algorithms, care must be taken to verify instabilities in your chosen method.

Log in to reply

S(2n) will be zero since the integrand is odd function. For S(2n+1), you can use integration by parts twice to get \(S_{2n+1} = 2-\frac{2n(2n+1)}{\pi^2}S_{2n-1}\) From here, also using the initial condition that \(S_1 = 2\) you can find all values of \(S_n\)

Log in to reply

Hi Shouvik, this is the obvious recurrence associated with the problem. However, there's an interesting phenomenon that occurs when using this recurrence. Namely, using double precision floating point arithmetic, then after around 12 iterations, this series becomes unstable

unstable

If you're interested, this was a problem I considered for an optimization problem @ Cornell University this past spring, and I wrote up my experience with the problem here.

Log in to reply

The link I shared is broken, the correct one is https://www.dropbox.com/s/9jc9hnl5g2w5wh7/lsq2.pdf.

Log in to reply

python:

Of course you'll have to mess with this slightly to actually use exponents as high as 100001, but you get the idea...

Log in to reply

Hi chandler, while the solution is correct by construction, it is unfortunately unstable numerically. For example, here's the list of values your method tabulates for just the first 100 terms: http://repl.it/P4Z, in which it claims S(99) = 1.1941919707663291e+95. For one thing, we can note that the value of the integral is bounded above by \[S_n \le \int_{-\pi}^{\pi} \left(\frac{x}{\pi}\right)^n dx = \frac{2}{n+1} \le 2\] One of the difficulties faced in solving this problem is finding a stable series that can compute or approximate this integral. It can be shown via a bit of analysis (or alternatively, recasting this into a nonlinear first order recurrence relation \(S_{n} = 2 - \frac{n(n-1)}{\pi^2}S_{n-2}\)) that suppose \(S_3\) is computed with a round off error of \(\epsilon\), then in general, for odd \(n\), the error in the above computed series is at around \(\frac{n!}{\pi^{n-1}}\epsilon\), which grows asymptotic to \(O\left(\left(\frac{n}{e\pi}\right)^n \right)\).

However you're close, and with a little bit of cleverness, you can derive a stable series from this unstable series. Hint: look at the first order non-linear recurrence, find a way to express it as a first order linear recurrence, reduce it to a different sum, and find what function it corresponds to as the truncated taylor expansion of. That will help you in transforming this series into an infinite series that is stable.

Log in to reply

Note that Mathematica does, in fact, handle this integral incredibly well with the right tweaks.

Log in to reply