3
$\begingroup$
  1. From the way linear/quadratic/cubic convergence of a sequence are defined, I wonder why they are called linear/quadratic/cubic, in the sense of some connections to linear/quadratic/cubic functions.

    Here are the definitions of linear/quadratic/cubic convergence of a sequence in my words based on Wikipedia

    Suppose that the sequence $\{x_k\}$ converges to the number $L$. Suppose $q > 1$.

    When $\lim_{k\to \infty} \frac{|x_{k+1}-L|}{|x_k-L|^q} = μ$ and $μ ∈ (0, 1)$, we say that the sequence (Q-)converges linearly if $q=1$, quadratically if $q=2$, and cubically if $q=3$.

  2. Similarly, how is logarithmic convergence connected to a logarithm function? The definition of logarithmic convergence is from the same link to Wikipedia:

    If the sequences converges sublinearly and additionally $ \lim_{k\to \infty} \frac{|x_{k+2} - x_{k+1}|}{|x_{k+1} - x_k|} = 1, $ then it is said the sequence $\{x_k\}$ converges logarithmically to $L$.

I found a plot of linear, linear, quadratic and logarithmic rates of convergence for an example in Wikipedia, which seems to suggest some connection, although it is not clear to me how they are connected: enter image description here

Thanks for clarification!

  • 1
    @RickDecker: No. I asked $f$or connections to those special functions.2012-09-23

3 Answers 3

1

It's simply that $x^q$ is a linear function of $x$ if $q=1$, a quadratic function of $x$ if $q=2$ and a cubic function of $x$ if $q=3$. Convergence "logarithmically" is different, and that definition really doesn't have any necessary connection to a logarithm function.

  • 1
    Suppose $|x_{n+1} - L| = c |x_n - L|^q$. If $q = 1$, $\log |x_n - L| = A + B n$ for some constants $A$ and $B$, so you get a straight line plot. If q > 1, $\log |x_n - L| = A + B q^n$ for some constants $A$ and $B$, and your plot shows exponential growth. One case of logarithmic convergence is where $|x_n - L| \approx c/n^p$ for some p > 0, and then your plot of $\log |x_n - L| = \log c - p \log n$ will look like a logarithm function.2012-02-17
0

Alright, this thread is like 5 years old, but here goes:

Suppose you have several methods to find the root of the function $f(x) = x(x-4)^2$. The first method you try is the bisection method. Set up bounds of -0.5 and 1 (don't use symmetric bounds for this example) and here's the results of the first few iterations:

$1.0, -0.5, 0.25, -0.125, 0.0625, -0.03125, 0.015625, -0.0078125, 0.00390625$

Now, we obviously know that this is converging to $0$, but consider the number of iterations it takes to find a "correct" digit. The first $0$ is found in iteration 1, the second $0$ is found in iteration 3, and the third is found in iteration 6. We could go on like this, but given the particular properties of base10, we'd know that it takes about 3-4 iterations to find a new correct digit.

That's linear convergence.

Let's try quadratic, Newton's Method:

Our guess will be at x = 1.

$1, -2, -0.8, -0.2, -0.0173, -0.000149, -1.11*10^{-8}$

Now, look at how it took 2 iterations to find the first zero. Then 2 more to find the second one. Then 1 iteration to find the next 2 zeros. Then 1 iteration to find 4 more. The precision doubles each term. So why is that called quadratic convergence and not exponential convergence, or something like that?

Think of the derivative of the linear function and the quadratic function:

$f(x) = c, f(x) = 2x$

If "x" here represents the order of magnitude of the error in the method for a given iteration, then you can see here that these derivatives correlate pretty well to the type of convergence it has.

Why the originators of the term decided to name it this way is beyond me, but that's the logic behind it. I'd assume that logarithmic convergence is just an extension of that idea:

Consider the sequence $\frac{1}{n}$. If you do some work with that, you'd see that it is logarithmically convergent. The first correct digit comes at iteration 2: $\frac{1}{2} = 0.5$, then iteration 11: $\frac{1}{11} = 0.09...$, then iteration 101, and so on.

The derivative of the logarithm is $f(x) = \frac{1}{x}$. If you think of "x" represents the same thing as before, then you can see why it somewhat makes sense.