Nonlinear Fractal Interpolating Functions
R. Kobes, H. Letkeman Department of
Physics, University of Winnipeg, Winnipeg, Manitoba, R3B 2E9
Canada randy@theory.uwinnipeg.ca
Abstract:
We consider two nonlinear generalizations of fractal interpolating
functions generated from iterated function systems. The first corresponds
to fitting data using a
K^{th}order polynomial, while
the second relates to the freedom of adding certain arbitrary functions.
An escapetime algorithm that can be used for such systems to generate
fractal images like those associated with Julia or Mandelbrot sets is also
described.
An Iterated
Function System (IFS) can be used to construct a fractal interpolating
function for a given set of data [1,2]. The simplest
such system defines an IFS
with coefficients
a_{n}, c_{n},
e_{n}, and f_{n} determined from discrete
data points (t_{i}, x_{i}), i = 0, 1,..., N. Such an IFS
interpolates the data set in the sense that, under certain assumptions on
the coefficients [1], the
attractor of the IFS is a graph that passes through the data points. In
this particular case, the IFS of Eq. (1) uses a
linear (in t) function between adjacent points to interpolate the
data.
Various generalizations of fractal interpolating functions have been
considered, including those for higher dimensional functions, the use of
hidden variables, and extensions to certain nonlinear distortions [3,4,5,6,7]. In this
note we describe a generalization whereby the transformation incorporates
a K^{th}order polynomial (in
t) interpolation. We also discuss certain classes of nonlinear
functions that can arise in such interpolating functions, and show how
such functions can, with the use of a particular escapetime algorithm, be
used to generate fractal images.
Linear Interpolating Functions We first review
the construction of a linear fractal interpolating function. Suppose we
have data points (t_{i}, x_{i}), i = 0...N, describing a function
x(t). Consider the IFS of Eq. (1) and impose,
for n = 1, 2,..., N,
This leads to determination of the coefficients as
a_{n} = , 
e_{n} =

c_{n} = , 
f_{n} =
,  
(3) 
whereby the transformation of Eq. (1) can be
written as
W_{n}(t) t^{} 
= 
t_{n} + t_{n  1} 

W_{n}(x) x^{} 
= 
x_{n} + x_{n  1} 
(4) 
Thus,
W_{n}(x) x^{} is determined by a linear (in t)
interpolating function constructed between the points ( t_{n  1}, x_{n
 1}) and (t_{n}, x_{n}). Assuming that
the corresponding IFS transformation is contractive, so that the distance
d (t, x) between any two points in the range of
interest satisfies
d
(W_{n}(t), W_{n}(x))s_{n} d (t, x),where 0 < s_{n}1
is the contractivity factor, graphs of fractal interpolating functions can
be made by applying the standard random iteration algorithm to the IFS:
 initialize (t, x) to a point in the
interval of interest
 for a set number of iterations
 randomly select a transformation
W_{n}(t, x)
 plot (
t^{}, x^{}) =
W_{n}(t, x)
 set (t, x) = ( t^{}, x^{})
 end for
A generalization of this type of fractal interpolating function can be
found by considering an IFS of the form
W_{n}(t) 
= 
a_{n}t +
e_{n} 

W_{n}(x) 
= 
c_{n}t +
f_{n} + g_{n}(x) 
(5) 
where g_{n}(x) is, at this stage, an
arbitrary function (Ref. [1] has
considered the cases
g_{n}(x) =
d_{n}x and
g_{n}(x) =
d_{n}x^{2}). Imposing the conditions (2) leads to
the same expressions for a_{n} and e_{n} as
in Eq. (3) but
c_{n} and f_{n} given by
c_{n} =  , f_{n}
=  . 
(6) 
The resulting transformation then has the same form as Eq. (4) with the
following replacements:
x_{n} 

x_{n} +
g_{n}(x) 
g_{n}(x_{N}) 

x_{n  1} 

x_{n  1} +
g_{n}(x) 
g_{n}(x_{0}). 
(7) 
Quadratic and Higher Order Interpolating
Functions The interpolating function of the last section used a
linear (in t) approximation between adjacent points. In this
section we indicate how a quadratic, and then arbitrary K^{th}order polynomial,
approximation may be constructed. Let us consider a transformation of the
form
W_{n}(t) 
= 
a_{n}t +
e_{n} 

W_{n}(x) 
= 
c_{n}t +
d_{n}t^{2} + f_{n} 
(8) 
and impose the conditions, for
n = 2, 3,..., N,
W_{n} = , W_{n} = , W_{n} = . 
(9) 
The point t_{m} is determined as
t_{m} = t_{N} + t_{0} 
(10) 
with corresponding point x_{m}. The coefficients of
the IFS are determined as
a_{n} 
= 


e_{n} 
= 


c_{n} 
= 


d_{n} 
= 


f_{n} 
= 

(11) 
With this, the transformation can be written as
W_{n}(t) t^{} 
= 
t_{n} + t_{n  2} 

W_{n}(x) x^{} 
= 
x_{n} + x_{n  1} 


+ 
x_{n  2} 
(12) 
which thus uses a quadratic (in t^{}) interpolating function between the points
(t_{n}, x_{n}), ( t_{n  1}, x_{n
 1}), and ( t_{n 
2}, x_{n  2}).
As in the previous section, including an arbitrary function
g_{n}(x) in the IFS transformation via
W_{n}(t) 
= 
a_{n}t +
e_{n} 

W_{n}(x) 
= 
c_{n}t +
d_{n}t^{2} + f_{n} +
g_{n}(x) 
(13) 
is straightforward. The conditions (9) leads to
determination of the point t_{m} of Eq. (10) as before,
together with the accompanying point x_{m}. The
transformation itself has the same form as Eq. (12) with the
following replacements:
x_{n} 

x_{n} +
g_{n}(x) 
g_{n}(x_{N}) 

x_{n  1} 

x_{n  1} +
g_{n}(x) 
g_{n}(x_{m}) 

x_{n  2} 

x_{n  2} +
g_{n}(x) 
g_{n}(x_{0}). 
(14) 
From these considerations, the pattern to constructing a K^{th}order fractal
interpolating function is apparent. Start with a transformation of the
form
W_{n}(t) 
= 
a_{n}t +
e_{n} 

W_{n}(x) 
= 
B_{n}^{(0)} +
B_{n}^{(1)}t +
B_{n}^{(2)}t^{2} +...+
B_{n}^{(K)}t^{K} 
(15) 
and impose the conditions, for
n = K, K + 1,...,
N,
W_{n} = , W_{n} = , ..., W_{n} = 
(16) 
which determine the coefficients B_{n}^{(i)}
of Eq. (15), as well as
the K  1 intermediate points t_{mj}, j = 1, 2,..., K  1 and
corresponding x_{mj} points. The resulting transformation
will be of the form given by Lagrange's formula for a K^{th}order polynomial
interpolating function constructed from K + 1 points:
W_{n}(t) t^{} 
= 
t_{n} + t_{n  K} 

W_{n}(x) x^{} 
= 
x_{n} + 


+ 
x_{n  1} +...+ 


+ 
x_{n  K} 
(17) 
The inclusion of an arbitrary function
g_{n}(x) in the transformation
W_{n}(x) of Eq. (15), as was done
for the linear and quadratic transformations of Eqs. (5) and (13)
respectively, is straightforward. As might be expected, the use of these
higherorder interpolating functions can increase the accuracy of the
interpolation significantly, at least for smooth functions. As an informal
example, consider the interpolation of the function x^{4}exp(
x)cos(x)  a comparison of the relative error using a linear
vs. a quadratic interpolation function appears in Fig. 1, where it can
be seen that the a quadratic interpolation offers an orderofmagnitude
improvement in the fit over most of the range.
Figure: Comparison of interpolations of x^{4}exp(
x)cos(x) using a linear (boxes) and a quadratic (stars)
function.

EscapeTime Algorithm In this section we
describe an algorithm for generating fractal images like those for Julia
or Mandelbrot sets from IFS interpolating functions. As well as allowing
one to associate fractal images with discrete data sets, this will also
offer another comparison of the detail available from linear
vs. higherorder fractal interpolation functions.
Suppose we have an IFS transformation W_{n}(t,
x), generated by some data points (x_{i},
y_{i}), i = 0,
1,..., N, which includes a nonlinear function
g_{n}(x), as was done for the linear and quadratic
transformations of Eqs. (5) and (13)
respectively. We now continue the real variable x of this
transformation to complex values: xz =
(z_{R}, z_{I}), in effect defining a complex
map:
t_{n + 1} 
= 
a_{n}t_{n} +
e_{n} 

z_{n + 1} 
= 
B_{n}^{(0)} +
B_{n}^{(1)}t_{n} +
B_{n}^{(2)}t_{n}^{2}
+...+
B_{n}^{(K)}t_{n}^{K} +
g_{n}(z_{n}) 
(18) 
for n = 0, 1,..., N.
We can then, in analogy with the algorithm used for Julia sets, define the
following escapetime algorithm to generate a fractal pattern:
 for each pixel in a region of interest
 initialize t
 initialize z = (z_{R},
z_{I}) to the pixel coordinates
 for n = 0, 1,...,
N
 calculate (
t^{}, z^{}) =
W_{n}(t, z)
 break if
exceeds a maximum
 set (t, z) = ( t^{}, z^{})
 end for
 plot the pixel
 end for
where the pixel is plotted using a coloring
algorithm based upon, amongst perhaps other factors, the number of
iterations attained when the break condition was met [8].
The arbitrariness of the function g_{n}(x) and
the data set (t_{i}, x_{i}) used to fix the
IFS leads to a wide variety of possible fractal images. An interesting
class of functions g_{n}(x) to consider are those
for which, when continued to the complex plane xz = (z_{R}, z_{I}), lead to
a map having a fixed point z_{I}^{*}
= 0 = Img_{n}(z_{R},
z_{I}^{*}). In such a case one could augment the
usual condition of the escapetime algorithm to cease iteration: > , where is some suitably large value, to also cease
iteration when  z_{I}
< , where is a suitably
small value. The coloring algorithm used to plot a pixel, which depends on
the number of iterations attained when this breakout condition was met
(if at all), will then lead to structure in the region where the breakout
condition on the magnitude of z is not met.
We give two examples of fractal images generated this way for the
choice
g_{n}(x)
=  0.4x + 0.5x^{2} + 0.2x^{3}, with
the data generated from the logistic map x_{n + 1} =
3.4x_{n}(1  x_{n}), with n = 0, 1,...60. The first one,
appearing on the left in Fig. 2, corresponds
to the generalization Eq. (5) of a linear
(in t) fractal interpolating function, while the second image on
the right of Fig. 2 corresponds
to the generalization Eq. (13) of a
quadratic (in t) interpolating function. A coloring algorithm that
simply mapped a color to the number of iterations attained when the
breakout condition became satisfied was used in both cases.
Figure 2: Fractal images from a
tlinear (top) and tquadratic (bottom) interpolating
function
 These figures
illustrate, in the interior of the fractal object, the richer structure
arising from the quadratic over the linear interpolation function. In this
region the breakout condition 
z_{I} < is satisfied,
which numerically for 10^{5} is attained after a
relatively small number (1030) of iterations.
Conclusions We considered two nonlinear
generalizations of fractal interpolating functions constructed from
iterated function systems. One  using a
K^{th}order interpolating
polynomial  can potentially improve the accuracy of fractal interpolating
functions. The other  use of certain arbitrary functions in the IFS 
can, together with an appropriate escapetime algorithm, generate fractal
images of the type associated with Julia or Mandelbrot sets.
This work was supported by the Natural Sciences and Engineering Research
Council of Canada.

 1
 M. F. Barnsley, Fractals Everywhere (Academic Press, San
Diego, CA, 1993)
 2
 H. O. Peitgen, H. Jürgens, and D. Saupe, Chaos and Fractals  New
Frontiers of Science (Springer, New York, 1992).
 3
 M. F. Barnsley, J. Elton, D. Hardin, and P. Massopust, Hidden
Variable Fractal Interpolation Functions, SIAM J. Math. Anal.
20 (1989), 12181242.
 4
 P. R. Massopust, Fractal Functions, Fractal Surfaces and
Wavelets (Academic Press, San Diego, CA, 1994).
 5
 L. M. Kocic and A. C. Simoncelli, Fractal Interpolation in
Creating Prefractal Images, Visual Mathematics 2, No. 2
(2000).
 6
 H. O. Peitgen and D. Saupe, The Science of Fractal Images
(Springer, New York, 1988).
 7
 E. Gröller, Modeling and Rendering of Nonlinear Iterated Function
Systems, Institute of Computer Graphics, Technical University of
Vienna Report TR18629412 (1994).
 8
 J. Barrallo and D. M. Jones, Coloring Algorithms for Dynamical
Systems in the Complex Plane, Visual Mathematics 1, No. 4
(1999).
VisMath
HOME 