0
$\begingroup$

If I have a set of data points obtained from a numerical approximation say

15.3828 15.2458 15.2095 15.2003

how can I estimate the rate of convergence?

$\endgroup$
2
  • $\begingroup$ They're eigenvalues corresponding to matrix systems of increasing size. So the grid size of the problem is being refined 16x16, 32x32 etc $\endgroup$
    – user146506
    Apr 29, 2014 at 1:28
  • $\begingroup$ It corresponds to the solution of a PDE, where the grid size is being refined at successive steps. I only need an estimate of the rate at which it is converging rather than a definite answer. It seems straightforward but for some reason im struggling with it $\endgroup$
    – user146506
    Apr 29, 2014 at 1:32

1 Answer 1

0
$\begingroup$

If these are successive approximations after $k$ steps, and the assumption is that each step reduces the absolute error by a factor of $\alpha < 1$, then you'd expect $$ \frac{\left|x_{k+1} - x\right|}{\left|x_k - x\right|} = \alpha \text{,} $$ where $x$ is the true value.

For a sequence of approximations $x_0,\ldots,x_N$, you could assume that $x_N$ is the true value. Then you'd expect that $$ \left|x_k - x_N\right| = \left|x_0 - x_N\right|\alpha^k $$ meaning that you can find $\alpha$ by fitting the function $$ k \to \left|x_0 - x_N\right|\alpha^k $$ to the $(x,y)$-pairs $$ (1, \left|x_1 - x_N\right|), \ldots, (N-1, \left|x_{N-1} - x_N\right|) $$


Since your approximations seems to be the result of varying some mesh size, you need to adjust this approach a bit. If the approximation $x_k$ corresponds mesh width $h_k$, we'd expect $$ |x_k - x| = C(h_k)^\alpha \text{.} $$

Again assuming that $x_0,\ldots,x_N$ is a series of approximations, this time for mesh widths $h_0,\ldots,h_N$, you'd then fit this function to the $(x,y)$-pairs $$ (h_0, \left|x_0 - x_N\right|), \ldots, (h_{N-1}, \left|x_{N-1} - x_N\right|) \text{.} $$

Since $\ln |x_k - x| = \alpha\ln C + \alpha\ln h_k)$, one can instead use linear regression on the $(x,y)$-pairs $$ (\ln h_0, \ln \left|x_0 - x_N\right|), \ldots, (\ln h_{N-1}, \ln \left|x_{N-1} - x_N\right|) \text{.} $$

If I do this with MATLB (using polyfit) I find $\alpha \approx 2.2$.

$\endgroup$
2
  • $\begingroup$ Could I calculate it using: $k=\frac{ \ln \left( \frac{ x_{n+1}}{x_{n}} \right)}{\ln \left( \frac{ x_{n}}{x_{n-1}} \right)}.$ $\endgroup$
    – user146506
    Apr 29, 2014 at 1:43
  • $\begingroup$ Thankyou! much appreciated $\endgroup$
    – user146506
    Apr 29, 2014 at 2:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .