how to check convergence of a vector in practice?

Question

Let's say I have a final solution vector that I know, denoted by $v_{\mathrm{final}}$ and access to a series of vectors from different time steps $\left\{v_{0}, v_{1},\ldots, v_{\mathrm{final} - 1}\right\}$.

How would you check in practice whether the series of vectors converge to $v_{\mathrm{final}}$. For now I am computing the sum of the absolute difference between consecutive vectors and checking whether it goes to $0$.

My question is: how can I check that it indeed goes to $0$ ? fit a linear regression through the difference and check whether the slope is negative ?. And at the same time check that $\left\vert v_{\mathrm{final} - 1} - v_{\mathrm{final}}\right\vert < \epsilon\ ?$.

Thanks :)

Answer 1

You can never tell if a sequence converges just by looking at a finite number of its elements. Generally in practice, you just set a tolerance, and when the iterants change by less than the tolerance, you have to assume it converges to some value within that tolerance of the last computed element.

A common technique used in root-finding is to track not a sequence of points, but a sequence of intervals. Start with two endpoints $a_0, b_0$ for which the function values $f(a_0)$ and $f(b_0)$ have opposite signs. Then you calculate some estimate $c_0\in (a_0, b_0)$ of the root and calculate $f(c_0)$. If it has the same sign as $f(a_0)$, then you set $a_1 = c_0, b_1 = b_0$, otherwise you set $a_1 = a_0, b_1 = c_0$ and repeat. As you can always choose $c_0 = \frac {a_0+b_0}2$, any well-designed technique can be expected to cut the interval in at least half with each step, so you are guaranteed convergence (though convergence by bisection is slow, so we prefer other methods).

Obviously, this doesn't apply directly to your vector situation. But you might be able to adapt it to the coordinates of your vectors (any problem of calculation of numbers can be recast into a problem of finding a root).

If you can't consider the coordinates separately, then you may just have to work on hope. You can indeed improve your confidence by examining the last several iterations before the end, to see if the differences are decreasing. If they are, then it is probably converging. If not, you should keep going until it settles down.

But the call of whether to do this is up to you, depending on the value that extra confidence has for you, and the amount of computing resources that must be expended to obtain it.