Thiele's interpolation formula
Encyclopedia
In mathematics
, Thiele's interpolation formula is an interpolation formula for a function f(•) of a single variable, due to the Danish
mathematician
Thorvald Nicolai Thiele
. It is expressed as a continued fraction
, where ρ represents the reciprocal difference:
Here is a version of Thiele interpolation in Algol 68
:
¢ The MODE of lx and ly here should really be a UNION of "something REAL", "something COMPLex",
and "something SYMBOLIC" ... ¢
PROC thiele:=([]REAL lx,ly, REAL x) REAL:
BEGIN
[]REAL xx=lx[@1],yy=ly[@1];
INT n=UPB xx;
IF UPB yy=n THEN
¢ Assuming that the values of xx are distinct ... ¢
[0:n-1,1:n]REAL p;
p[0,]:=yy[];
FOR i TO n-1 DO p[1,i]:=(xx[i]-xx[1+i])/(p[0,i]-p[0,1+i]) OD;
FOR i FROM 2 TO n-1 DO
FOR j TO n-i DO
p[i,j]:=(xx[j]-xx[j+i])/(p[i-1,j]-p[i-1,j+1])+p[i-2,j+1]
OD
OD;
REAL a:=0;
FOR i FROM n-1 BY -1 TO 2 DO a:=(x-xx[i])/(p[i,1]-p[i-2,1]+a) OD;
yy[1]+(x-xx[1])/(p[1,1]+a)
ELSE
error; ~ ¢ Unequal length arrays supplied ¢
FI
END;
Note that, although it works in most cases, it is sensitive to input values, especially those due to equally spaced abscissæ. (Essentially, in such a case, it may reduce to the ratio of two polynomials, which may have factors in common - thus yielding a 0/0 form.)
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Thiele's interpolation formula is an interpolation formula for a function f(•) of a single variable, due to the Danish
Denmark
Denmark is a Scandinavian country in Northern Europe. The countries of Denmark and Greenland, as well as the Faroe Islands, constitute the Kingdom of Denmark . It is the southernmost of the Nordic countries, southwest of Sweden and south of Norway, and bordered to the south by Germany. Denmark...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Thorvald Nicolai Thiele
Thorvald N. Thiele
Thorvald Nicolai Thiele was a Danish astronomer, actuary and mathematician, most notable for his work in statistics, interpolation and the three-body problem. He was the first to propose a mathematical theory of Brownian motion...
. It is expressed as a continued fraction
Continued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on...
, where ρ represents the reciprocal difference:
Here is a version of Thiele interpolation in Algol 68
ALGOL 68
ALGOL 68 isan imperative computerprogramming language that was conceived as a successor to theALGOL 60 programming language, designed with the goal of a...
:
¢ The MODE of lx and ly here should really be a UNION of "something REAL", "something COMPLex",
and "something SYMBOLIC" ... ¢
PROC thiele:=([]REAL lx,ly, REAL x) REAL:
BEGIN
[]REAL xx=lx[@1],yy=ly[@1];
INT n=UPB xx;
IF UPB yy=n THEN
¢ Assuming that the values of xx are distinct ... ¢
[0:n-1,1:n]REAL p;
p[0,]:=yy[];
FOR i TO n-1 DO p[1,i]:=(xx[i]-xx[1+i])/(p[0,i]-p[0,1+i]) OD;
FOR i FROM 2 TO n-1 DO
FOR j TO n-i DO
p[i,j]:=(xx[j]-xx[j+i])/(p[i-1,j]-p[i-1,j+1])+p[i-2,j+1]
OD
OD;
REAL a:=0;
FOR i FROM n-1 BY -1 TO 2 DO a:=(x-xx[i])/(p[i,1]-p[i-2,1]+a) OD;
yy[1]+(x-xx[1])/(p[1,1]+a)
ELSE
error; ~ ¢ Unequal length arrays supplied ¢
FI
END;
Note that, although it works in most cases, it is sensitive to input values, especially those due to equally spaced abscissæ. (Essentially, in such a case, it may reduce to the ratio of two polynomials, which may have factors in common - thus yielding a 0/0 form.)