woodssnoop
- 9
- 0
Hello:
I am trying to determine the global error for the verlet integration algorithm: r_{i+1}=2r_{i}-r_{i-1}+\ddot{r}_{i}h^{2}
It is easy to show that this approximation is locally 4th order, by way of a Talyor expansion. I have look around extensively for a proof of the global error but have been unsuccessful in finding a reasonable derivation anywhere (the articles I have found seem to make too many unjustified assumption and/or glaze over the dropping of terms; similar to the wikipedia page on verlet integration). (1) Has anyone else ran across a good derivation of the verlet integrators global error? My attempts at finding the global error for this expression has proved to be quite difficult.
The numerical testing I have done has shown 2nd order global error, but I can't prove it. (2) I know I have to show that d_{k} \leq M n^2 for all k \leq n, where M is some constant, but how can I show this for an arbitrary M? In real analysis, you show an equation like this is true by showing that for any \epsilon you can find a n such that the expression holds, but I can't seem to frame my problem in those terms. I have been trying several different approaches, and my latest attempt is below.
My first step was to set up a difference equation for r_{i} and r(h*i) where r(h*i) is the exact solution and r_{i} is the approximate solution. After subtracting the two expression I get the difference formula:
d_{i+1}=2d_{i}-d_{i-1}-h^{2}(\ddot{r}_{i}-\ddot{r}(h*i)) - O(h^{4})
using the mean value theorem:
d_{i+1}=2d_{i}-d_{i-1}-h^{2}(\ddot{\xi}_{i}d_{i}) - O(h^{4}) for \xi\in[r_{i},r(h*i)]
\Leftrightarrow d_{i+1}-(2-h^{2}(\ddot{\xi}_{i}))d_{i}+d_{i-1}=-O(h^{4})
r is differentiable on the interval [0,h*n]. Which implies \ddot{\xi}_{i} has a maximum. Letting \epsilon=h^{2}\ddot{\xi}_{i} gives:
d_{i+1}-(2-\epsilon)d_{i}+d_{i-1}=-O(h^{4})
condensing further:
d_{i+1}-xd_{i}+d_{i-1}=-O(h^{4}) where x=2-\epsilon.
This expression can be written out in matrix form (shown below is just a 12X12 example) where A=
Taking the inverse of A yields:
The rows of A have a closed form solution:
a(i)=\frac{(x-\sqrt{x^{2}-4})^{i}-(x-\sqrt{x^{2}-4})^{i}}{2^{i}\sqrt{x^{2}-4}}
\Rightarrow d_{n}=\sum_{i=1}^{n}a(i)
This two can be expressed in a better way:
d_{n}=\frac{(\frac{x-\sqrt{x^{2}-4}}{2})^{n}(\sqrt{x^{2}-4}+x-2)+(\frac{x+\sqrt{x^{2}-4}}{2})^{n}(\sqrt{x^{2}-4}-x+2)-2\sqrt{x^{2}-4}}{x-2}
I am trying to show that d(n) \leq M n^2, but I have been having trouble show that this true.
I am trying to determine the global error for the verlet integration algorithm: r_{i+1}=2r_{i}-r_{i-1}+\ddot{r}_{i}h^{2}
It is easy to show that this approximation is locally 4th order, by way of a Talyor expansion. I have look around extensively for a proof of the global error but have been unsuccessful in finding a reasonable derivation anywhere (the articles I have found seem to make too many unjustified assumption and/or glaze over the dropping of terms; similar to the wikipedia page on verlet integration). (1) Has anyone else ran across a good derivation of the verlet integrators global error? My attempts at finding the global error for this expression has proved to be quite difficult.
The numerical testing I have done has shown 2nd order global error, but I can't prove it. (2) I know I have to show that d_{k} \leq M n^2 for all k \leq n, where M is some constant, but how can I show this for an arbitrary M? In real analysis, you show an equation like this is true by showing that for any \epsilon you can find a n such that the expression holds, but I can't seem to frame my problem in those terms. I have been trying several different approaches, and my latest attempt is below.
My first step was to set up a difference equation for r_{i} and r(h*i) where r(h*i) is the exact solution and r_{i} is the approximate solution. After subtracting the two expression I get the difference formula:
d_{i+1}=2d_{i}-d_{i-1}-h^{2}(\ddot{r}_{i}-\ddot{r}(h*i)) - O(h^{4})
using the mean value theorem:
d_{i+1}=2d_{i}-d_{i-1}-h^{2}(\ddot{\xi}_{i}d_{i}) - O(h^{4}) for \xi\in[r_{i},r(h*i)]
\Leftrightarrow d_{i+1}-(2-h^{2}(\ddot{\xi}_{i}))d_{i}+d_{i-1}=-O(h^{4})
r is differentiable on the interval [0,h*n]. Which implies \ddot{\xi}_{i} has a maximum. Letting \epsilon=h^{2}\ddot{\xi}_{i} gives:
d_{i+1}-(2-\epsilon)d_{i}+d_{i-1}=-O(h^{4})
condensing further:
d_{i+1}-xd_{i}+d_{i-1}=-O(h^{4}) where x=2-\epsilon.
This expression can be written out in matrix form (shown below is just a 12X12 example) where A=
Taking the inverse of A yields:
The rows of A have a closed form solution:
a(i)=\frac{(x-\sqrt{x^{2}-4})^{i}-(x-\sqrt{x^{2}-4})^{i}}{2^{i}\sqrt{x^{2}-4}}
\Rightarrow d_{n}=\sum_{i=1}^{n}a(i)
This two can be expressed in a better way:
d_{n}=\frac{(\frac{x-\sqrt{x^{2}-4}}{2})^{n}(\sqrt{x^{2}-4}+x-2)+(\frac{x+\sqrt{x^{2}-4}}{2})^{n}(\sqrt{x^{2}-4}-x+2)-2\sqrt{x^{2}-4}}{x-2}
I am trying to show that d(n) \leq M n^2, but I have been having trouble show that this true.