Convergence and Speed of Numerical Algorithms

Linear and Superlinear

LINEAR SUPERLINEAR
Error in each step?  Error in each step? 
Number of digits in each step ~O(k)?  Number of digits in each step? 
Number of steps?  Number of steps? 

Linear

Example: Roots of deg 2 polynomial using simple iterative method.

Function: f(x) = x^2 - (5+pi)*x + 5*pi
Iterative formula: x(i) = x(i-1) + f(x(i-1))
Starting point: x(0) = 3
Steps: n = 250
 
Approx. of pi:
   3.00000000000000,   3.28318530717959,   3.04009695910120,   3.23901867936753,
   3.06745326782948,   3.21073109550571,   3.08702383128038,   3.19141268791338,
   3.10130880594802,   3.17779539272799,   3.11182659467450,   3.16803007549971,
   3.11959751367942,   3.16095722945386,   3.12534494620636,   3.15580379296527,
   3.12959566363137,   3.15203488567297,   3.13273800506755,   3.14927195373162,
   3.13505965758343,   3.14724330539254,   3.13677402243610,   3.14575222117796,
   3.13803935221675,   3.14465545954307,   3.13897289923917,   3.14384833308301,
   3.13966144983165,   3.14325414263116,   3.14016917973654,   3.14281660028066,
   3.14054350680424,   3.14249434960695,   3.14081944416014,   3.14225698009734,
   3.14102283216501,   3.14208211718343,   3.14117273401983,   3.14195329196600,
   3.14128320901830,   3.14185837883921,   3.14136462369347,   3.14178844812563,
   3.14142462045735,   3.14173692270026,   3.14146883273909,   3.14169895764928,
   3.14150141270473,   3.14167098376073,   3.14152542053123,   3.14165037146146,
   3.14154311147608,   3.14163518335858,   3.14155614753261,   3.14162399199016,
   3.14156575345879,   3.14161574558349,   3.14157283178601,   3.14160966916469,
   3.14157804758483,   3.14160519170509,   3.14158189093672,   3.14160189244610,
   3.14158472297303,   3.14159946135238,   3.14158680980272,   3.14159766997370,
   3.14158834751416,   3.14159634997529,   3.14158948059899,   3.14159537731848,
   3.14159031552850,   3.14159466060425,   3.14159093075787,   3.14159413248434,
   3.14159138409803,   3.14159374333246,   3.14159171814787,   3.14159345658088,
   3.14159196429699,   3.14159324528428,   3.14159214567525,   3.14159308958762,
   3.14159227932624,   3.14159297486052,   3.14159237780875,   3.14159289032234,
   3.14159245037689,   3.14159282802928,   3.14159250384968,   3.14159278212783,
   3.14159254325182,   3.14159274830474,   3.14159257228580,   3.14159272338175,
   3.14159259367987,   3.14159270501691,   3.14159260944438,   3.14159269148454,
   3.14159262106066,   3.14159268151304,   3.14159262962028,   3.14159267416540,
   3.14159263592754,   3.14159266875120,   3.14159264057512,   3.14159266476168,
   3.14159264399976,   3.14159266182195,   3.14159264652325,   3.14159265965577,
   3.14159264838272,   3.14159265805958,   3.14159264975289,   3.14159265688342,
   3.14159265076252,   3.14159265601674,   3.14159265150648,   3.14159265537813,
   3.14159265205467,   3.14159265490755,   3.14159265245862,   3.14159265456080,
   3.14159265275627,   3.14159265430529,   3.14159265297560,   3.14159265411702,
   3.14159265313722,   3.14159265397829,   3.14159265325631,   3.14159265387606,
   3.14159265334406,   3.14159265380073,   3.14159265340872,   3.14159265374523,
   3.14159265345637,   3.14159265370433,   3.14159265349147,   3.14159265367419,
   3.14159265351734,   3.14159265365199,   3.14159265353640,   3.14159265363562,
   3.14159265355045,   3.14159265362356,   3.14159265356080,   3.14159265361468,
   3.14159265356843,   3.14159265360813,   3.14159265357405,   3.14159265360330,
   3.14159265357820,   3.14159265359975,   3.14159265358125,   3.14159265359713,
   3.14159265358350,   3.14159265359520,   3.14159265358516,   3.14159265359378,
   3.14159265358637,   3.14159265359273,   3.14159265358727,   3.14159265359195,
   3.14159265358794,   3.14159265359138,   3.14159265358843,   3.14159265359096,
   3.14159265358879,   3.14159265359066,   3.14159265358905,   3.14159265359043,
   3.14159265358925,   3.14159265359026,   3.14159265358939,   3.14159265359014,
   3.14159265358950,   3.14159265359005,   3.14159265358957,   3.14159265358998,
   3.14159265358963,   3.14159265358993,   3.14159265358968,   3.14159265358989,
   3.14159265358971,   3.14159265358987,   3.14159265358973,   3.14159265358985,
   enz...

Error (x-x*)/x*

If we use a semilogy scale, we get a linear error plot.

Number of digits

This graph is linear too.

Theory

In the linear case, the error is multiplied in each step by an almost constant convergence factor <= 1.

Convergence factor

The convergence factor is defined as the quotient of the error in the next and the error in this step. Or:

For a substitution method, where x(k+1) = F(x(k)), we get:

In the Linear Example
 
f(x) = x^2 - (5+pi)*x + 5*pi
F(x(k)) = x(k+1) = x(k) + f(x(k)) = x(k) + x(k)^2 - (5+pi)*x(k) + 5*pi
F(x) = x^2 - (4+pi)*x + 5*pi
F'(x) = 2*x - (4+pi)

Convergence factor = F'(pi) = 2*pi - 4 - pi =  pi-4 = -0.8584073464102

The approximation will be alternating at the left/right side of the exact value on the real axis. This is called spiral convergence. In general we have:

Number of digits

There's a link between the number of ditits and the relative error. See Digit.html.

If k is the first significant digit, i is the last correct digit and q is the total number of correct significant digits q = k-i+1, then we have (b is 10 for the decimal basis):

And the number of digits gained in each step is:

The number of ditits in each step increases by -Log(|rho|) or ~O(k).

For our example, we find:

    - Log(|-0.8584073464102|) = 0.06630657425311 digits/step or 15 steps/digit

This can be verified in the digit graph.

Number of steps

In each step, the absolute error is changed by a constant factor rho. From this theorem, we can estimate the number of steps before machine precision is reached.

The number of steps k ~O(Log(machine precision)).

In our example we have:

    k = (log(pi)+log(eps)-log(pi-3))/log(0.8584073464102) = 215.7773

Or we can find this by using:

    k = 16digits (IEEE double precision) * 15steps/digit = 240

This can be verified in the convergence graph.

Superlinear

Example: Newton Raphson

Function: f(x) = x^2 - (5+pi)*x + 5*pi
Iterative formula:  x(i) = x(i-1) - f(x(i-1))/fdiv(x(i-1));
Starting point: x(0) = 3
Steps: n = 7
 
Approx. of pi:
   3.00000000000000
   3.13223117230296
   3.14154596672343
   3.14159265241698
   3.14159265358979
   3.14159265358979
   3.14159265358979

Error (x-x*)/x*

In this case, the relative error graph is not linear. The convergence is superlinear.

Log error: Log((x-x*)/x*)

But if we take the logarithm the error graph is linear.

Number of digits

The number of digits is ~O(exp(k))
 

Theory

In the superlinear case, the error is raised in each step to an almost constant power, the convergence order m.

Convergence order m

For substitution methods with convergence order higher than one, the first derivatives of F(x) in the Taylor expansion of F are zero and we get:


The convergence order is the first m, so that rho(m) <> 0. And:

It can be proved that the convergence order of Newton-Raphson is 2, which makes it a quadratic process.

In the linear case the convergence order m is one, because F'(x*) <> 0.

Number of digits

To find the number of digits gained in each step, we work the same way as in the linear case:


And the number of digits is multiplied by the convergence order in each step!

This can be verified using the convergence graph. In this case m = 2 and the number of digits is multiplied by 2 in each step. This explains the exponential behaviour.

For m = 1 this morphs into the formula for the linear case.

Number of steps

Again, we take the same approach as in the linear case:

And we have k ~ O(Log(Log(machine precision))).

By Jeans (21/7/98).

Graphs are created using Matlab.
    DOWNLOAD THE M-FILES.

Back home: HOME