Rate of convergence
The rate of convergence for a convergent sequence describes how quickly the terms of the sequence converge to the limit. We discuss some cases below.
For the definitions below, the sequence is and the limit is . In symbols, we have:
Steadily linear, superlinear, and sublinear convergence
Suppose the following holds:
Clearly, (if were greater than 1, the sequence couldn't converge). We have three cases:
- , i.e., : In this case, the sequence converges to linearly, and the constant is called the rate of (linear) convergence. The use of the term "linear" signifies that the next error term is approximately a linear function of the preceding error term .
- : In this case, the sequence converges to superlinearly. In other words, a function that would approximate the behavior of the next error term in terms of the previous error term would decay faster than a linear function.
- : In this case, the sequence converges to sublinearly. In other words, a function that would describe the next error term in terms of the previous one would decay slower than a linear function.
Convergence of a power function form
Suppose is a real number. We say that the sequence converges to a limit with order of convergence if the following holds:
In other words, if we were to try to construct a function that approximately predicted in terms of , the order of zero of a the function at zero would be . Note that convergence of this form is superlinear.
Two special cases:
- , in which case we say the sequence converges quadratically or has quadratic convergence.
- , in which case we say the sequence converges cubically or has cubic convergence.
For further information, refer: logarithmic convergence
If the sequence converges sublinearly, and further:
then we say that the convergence is logarithmic. This use of terminology differs somewhat from the others, because it is not the case that we can use a logarithmic function to approximate the description of in terms of . (So what's the rationale of the term?)
Non-steady convergence or R-convergence
In some cases, the convergence of the sequence is not steadily of a certain type, but it still approximates that type.
We say that a sequence has R-convergence of a particular type to a limit if we can find a sequence such that, for all :
and the sequence has convergence to 0 of that type.
In particular, we can talk of R-linear convergence, R-superlinear convergence, R-sublinear convergence, R-quadratic convergence, R-logarithmic convergence, etc.