FACTA UNIVERSITATIS (NI

S)
Ser. Math. Inform. 15 (2000), 3748
FUNCTIONAL EQUATIONS FOR FRACTAL
INTERPOLANTS
Lj. M. Kocic and A. C. Simoncelli
This paper is dedicated to Professor R.

Z. Djordjevic
Abstract. For a given data set Y = {(x
i
, y
i
)}
n
i=0
, a fractal interpolating func-
tion : [x
0
, x
n
] R can be dened by a hyperbolic iterated function system

Y,d
= {R
2
; {w
i
}
n
i=1
} where w
i
are ane contractions in R
2
depending on an
n-dimensional vector d. Typically, w
i
: (x, y)
_
u
i
(x), v
i
(x, y)
_
where u
i
()
and v
i
(x, ) are contractions, and v
i
( , y) is a Lipschitz mapping.
The system
Y,d
has the unique attractor
Y,d
which is the graph of a
continuous function interpolating Y and satisfying the Read-Bajraktarevic
functional equation
(x) = v
i
_
u
1
i
(x), (u
1
i
(x)
__
, x [x
i1
, x
i
] , i = 1, . . . , n.
Using this equation, it is shown that has only a limited ane invariant prop-
erty. Correspondingly, the general form of ane transformations such that
(
Y,d
) =
(Y ),d
is specied. An application of the functional equation and
some examples are also given.
1. Introduction
Let an interpolatory data set Y = (x
i
, y
i
)
n
i=0
(n 2) be given, that is a
set of points from R
2
such that either x
i
= x
i+1
x
i
> 0 i, or x
i
< 0 i.
Also let a scaling vector d = [d
1
. . . d
n
]
T
be given, namely a vector from R
n
whose components are intended as vertical scaling factors.
With the pair (Y, d) one can associate the iterated function system (IFS
for short)
Y,d
= R
2
; w
i

n
i=1
, in which w
1
, . . . , w
n
are the ane trans-
formations of R
2
dened by
(1) w
i
: (x, y) (a
i
x + e
i
, c
i
x + d
i
y + f
i
) ,
Received June 16, 1999.
1991 Mathematics Subject Classication. Primary 41A05; Secondary 28A80, 39B22.
37
38 Lj. M. Kocic and A. C. Simoncelli
with the coecients
(2)
a
i
=
x
i1
x
n
x
0
, c
i
=
y
i1
x
n
x
0
d
i
y
n
y
0
x
n
x
0
,
e
i
= x
i
a
i
x
n
, f
i
= y
i
c
i
x
n
d
i
y
n
.
Let H(R
2
) denote the set of nonempty compact subsets of R
2
and let
h

be the Hausdor metric on H(R

2
) generated by the norm | |

dened
as |(x, y)|

= [x[ + [y[, 0 < < min

i
(1 [a
i
[)/(1 + [c
i
[). The space
(H(R
2
), h

) is a complete metric space. With =

Y,d
is canonically
associated the Hutchinson operator W

acting on (H(R
2
), h

) and dened
by
(3) W

() =
n
1
w
i
() .
If |d| = max
i
[d
i
[ < 1, then
Y,d
is hyperbolic, and W

is a contraction
in (H(R
2
), h

). The unique xed point of W

, namely the nonempty, closed,

bounded set
Y,d
R
2
such that
W

(
Y,d
) =
Y,d
is the unique attractor of
Y,d
. Under such conditions the following theorem
holds [1].
Theorem 1. The iterated function system
Y,d
corresponding to an arbi-
trary interpolatory data set Y and to a scaling vector d such that |d| =
max
i
[d
i
[ < 1 is hyperbolic, and its attractor is the graph of a continuous
function : [x
0
, x
n
] R that interpolates Y .
Because of this result, we refer to
Y,d
with |d| < 1, as a fractal interpo-
latory scheme, and call the function =
Y,d
, whose graph is the attractor
of
Y,d
, a fractal interpolating function. Also, we use the acronym IFS with
the meaning of iterated function system.
The Functional Equation
For i = 1, . . . , n, denote the x and y components of w
i
(x, y) in (1) by
(4) u
i
(x) = a
i
x + e
i
, v
i
(x, y) = c
i
x + d
i
y + f
i
,
respectively.
Functional Equations for Fractal Interpolants 39
Consider the functional equation
(5) (x) = v
i
(u
1
i
(x), (u
1
i
(x))) , x [x
i1
, x
i
] , i = 1, . . . , n.
If u
i
(x) and v
i
(x, y) are given by (4) with [d
i
[ < 1, then u
i
(x) is a bijection
[x
0
, x
n
] R, v
i
(x, ) Lip
(<1)
(R), and v
i
( , y) Lip(R), so that (5) is a
functional equation of Read-Bajraktarevic type [7]. It can be written as
(6) (x) = c
i
x e
i
a
i
+ d
i

_
x e
i
a
i
_
+ f
i
, x [x
i1
, x
i
] , i = 1, . . . , n.
Also, introducing the operator T : T dened piecewise by
(7) (T)(x) = (T
i
)(x) = c
i
x e
i
a
i
+ d
i

_
x e
i
a
i
_
+ f
i
, x [x
i1
, x
i
] ,
where i = 1, . . . , n, equation (6) can be put in the more compact form
(8) (x) = (T)(x) , x [x
0
, x
n
] .
By Theorem 2, below, fractal interpolating functions are characterized as
solutions of equation (8). The following lemma states a preliminary result,
namely that bounded solutions of (8) are continuous.
Lemma 1. Let : [x
0
, x
n
] R be a bounded function that satises equation
(8). Then is continuous.
Proof. Suppose that be discontinuous at the point t
0
[x
i
1
1
, x
i
1
],
i
1
1, . . . , n, with the jump L
0
= [(t
0
0) (t
0
+ 0)[ > 0. Consider
the point t
1
= u
1
i
1
(t
0
) and let i
2
1, . . . , n be the index such that t
1
=
u
1
i
1
(t
0
) [x
i
2
1
, x
i
2
]. Being, by (8), = T
i
1
on the interval [x
i
1
1
, x
i
1
],
and being [d
i
1
[ |d| < 1, we have
0 < L
0
= [(T
i
1
)(t
0
0)(T
i
1
)(t
0
+0)[ = [d
i
1
[ [(t
1
0)(t
1
+0)[ |d|L
1
so that t
1
is also a discontinuity point with a corresponding positive jump
L
1
. The discontinuity at t
1
is, in turn, the image of a discontinuity at
t
2
= u
1
i
2
(t
1
), with a corresponding jump L
2
, and L
1
|d| L
2
. Continuing
this process, after k steps, a point is reached where has a jump L
k
such
that
|d|
k
L
k
|d|
2
L
2
|d| L
1
L
0
, k 1
Therefore L
k
L
0
|d|
k
if k , which leads to the conclusion
that is unbounded. Thus, must be a continuous function.
40 Lj. M. Kocic and A. C. Simoncelli
Theorem 2. Let B denote the set of bounded functions [x
0
, x
n
] R. Let
B. A necessary and sucient condition for to be a fractal interpolating
function of the data set Y is that satisfy the Read-Bajraktarevic functional
equation (8) with T given by (7), where a
i
, c
i
, e
i
, f
i
are given by (2) and
|d| < 1.
Proof. (i) Let be a fractal interpolant for Y associated with the vertical
scaling vector d = [d
1
. . . d
n
]
T
, |d| < 1. Then, by Theorem 1, its graph

Y
R
2
is the xed point of the operator W

given by (3). Therefore, for

any P = (x, (x))
Y
there exist i 1, . . . , n and P

= (x

, (x

))
Y
such that x [x
i1
, x
i
], and P = w
i
(P

), which means
(9) x = a
i
x

+ e
i
, (x) = c
i
x

+ d
i
(x

) + f
i
, x [x
i1
, x
i
].
Being a
i
,= 0 since x
i
,= 0 for each i, (9) yields x

= (x e
i
)/a
i
and
(x) = c
i
x e
i
a
i
+ d
i

_
x e
i
a
i
_
+ f
i
,
which is (6).
(ii) Let satisfy (8). Let (B, d) be the metric space obtained by endow-
ing B with the max-norm d(, ) = max [(x) (x)[, x [x
0
, x
n
]. The
operator T dened by (7) is a contraction in (B, d) since
[(T)(x) (T)(x)[ = [d
i
[ [(u
1
i
(x)) (u
1
i
(x))[ [d
i
[ d(, ),
and therefore d(T, T) |d|d(, ).
Since T is a contraction in (B, d), it has a unique xed point and, according
to (8), this is . By Lemma 1, is also continuous. Let

be the graph of
. As a consequence of (6) we have
(T)(u
i
(x)) = v
i
(x, (x)) , x [x
0
, x
n
] , i = 1 , . . . , n,
which implies that, for x [x
0
, x
n
],
w
i
(x, (x)) = (u
i
(x), v
i
(x, (x))) = (u
i
(x), (T)(u
i
(x))) = (u
i
(x), (u
i
(x)))
which, in connection with the continuity of , leads to

=
n
_
i=1
w
i
(

) .
Functional Equations for Fractal Interpolants 41
This means that

is a xed point of the Hutchinson operator (3). Since

it is also a nonempty compact set of R
2
, it must be the unique attractor of
the IFS
Y,d
, which, by Theorem 1, is the graph of the interpolating fractal
function.
Remark 1. Notice that the interpolation property of can also be derived
directly from (8), by the following argument. From (6) it can be seen immediately
that (x
0
) = y
0
and (x
n
) = y
n
. Furthermore, being the xed point of T,
satises (x
i
) = (T)(x
i
) = c
i
u
1
i
(x
i
)+d
i
(u
1
i
(x
i
))+f
i
= c
i
x
n
+d
i
(x
n
)+f
i
=
c
i
x
n
+d
i
y
n
+f
i
= c
i
x
n
+d
i
y
n
+y
i
c
i
x
n
d
i
y
n
= y
i
for i = 1, . . . , n. Therefore
interpolates the set of data Y.
Ane Transformation of The Interpolatory Scheme
Lemma 2. Let be a regular ane mapping R
2
R
2
given by
(10) : (x, y) (px + qy + g, rx + sy + h), p, q, r, s, g, h R
and let F denote the graph of an arbitrary function f : I R (I R).
The set (F) is the graph of a function if and only if q = 0.
Proof. Let (x) = px +qf(x) +g and (x) = rx +sf(x) +h, so that the
image under of the point (x, f(x)) F has coordinates ((x), (x)).
(i) Suppose q = 0. Since is regular, it must be p ,= 0, therefore (x) is
invertible and (x) = (
1
(x) ) =
1
( (x) ) is obviously a function,
mapping (I) R.
(ii) Let now

F = (F) be the graph of a function

f. Let , I and
,= . Since is a regular ane mapping, it maps P = (, f()) F and
Q = (, f()) F , P ,= Q, into two dierent points (P) = ((), ())

F and (Q) = ((), ())

F . Two cases are possible: either () = (),
and then, since (P) ,= (Q), it must be () ,= (); or () ,= (), and
in this case again it must be () ,= () by the fact that

f is a function.
Therefore, the implication ,= () ,= () holds in any case. Now,
since () () = p( ) + q[f() f()] for any f, in order that the
inequality () () ,= 0 be valid whenever ,= 0 , it must be q = 0.
Otherwise, a function f can be found such that [f() f()]/( ) = p/q
and then () () = 0.
Lemma 2 suggests that ane transformation of a fractal interpolating
function can only be performed by means of a mapping with q = 0, i.e.,
(11) : (x, y) ((x), (x, y)) = (px + g, rx + sy + h) .
42 Lj. M. Kocic and A. C. Simoncelli
In fact, maps the data set Y into the data set

Y = (Y ) = ( x
i
, y
i
)
n
i=0
,
with x
i
= (x
i
), y
i
= (x
i
, y
i
). Since sign( x
i
) = sign(p) sign(x
i
), i ,
coecients a
i
, c
i
, e
i
,

f
i
can be dened according to (2) for the new data
set

Y , and the new fractal interpolating scheme is well dened. So is also
the function having graph

, the attractor of

Y ,d
. Note that the new
coecients are related to the old ones by
(12)
a
i
= a
i
, c
i
= (r/p)(a
i
d
i
) + (s/p)c
i
, e
i
= pe
i
+ g(1 a
i
) ,

f
i
= sf
i
+ re
i
+ h(1 d
i
) + (rg/p)(d
i
a
i
) + (sg/p)c
i
,
and by Theorem 2, satises a functional equation having the form of (6)
with the coecients (12), namely
(13) (x) = c
i
x e
i
a
i
+ d
i

_
x e
i
a
i
_
+

f
i
, x [ x
i1
, x
i
].
The following theorem establishes ane invariance of the fractal interpo-
latory scheme
Y,d
under a regular transformation of the type of .
Theorem 3. Let be the fractal interpolant of Y associated with d and
let =
Y,d
be the graph of . Let be the regular ane mapping given
by (11), and let

Y = (Y ). If is the interpolant of

Y associated with the
same d, and

=
(Y ),d
is its graph, then
(14) () =

.
Proof. Denoting the interval [x
0
, x
n
] by I, consider the function : I
R, and its graph . By Lemma 2, the set () is also the graph of a function,
say f : (I) R, so that any point P () has coordinates P =
(x, f(x)) , x (I). On the other hand, this point is the image under of
some point Q = (
1
(x), (
1
(x))) , therefore its ordinate must also
satisfy
(15) f(x) = (
1
(x), (
1
(x))), x (I).
So, equation (15) characterizes functions whose graph is the image under
of the graph of . Therefore (14) is equivalent to
(16) (x) = (
1
(x), (
1
(x))), x (I).
Functional Equations for Fractal Interpolants 43
Plugging this equation into (13) yields the functional equation for
(17)
(
1
(x), (
1
(x))) = c
i
x e
i
a
i
+ d
i

1
(
x e
i
a
i
), (
1
(
x e
i
a
i
))
_
+

f
i
,
that is also equivalent to (14).
We will show that (17) reduces to (6). This will lead to the conclusion
that (14) holds if and only if is a solution of (6), namely (by Theorem 2)
the fractal interpolating function for (Y, d). So, our assertion will be proved.
Since any ane transformation is a composition of a translation and a
linear transformation, it is sucient to prove the equivalence for these two
special cases of , separately:
a) The ane transformation given by (11) is a translation if p = s = 1,
r = 0, and g, h ,= 0.
In this case (x) = x + g , (x, y) = y + h, and, by (12),
a
i
= a
i
, c
i
= c
i
, e
i
= e
i
+ g(1 a
i
) ,

f
i
= f
i
+ h(1 d
i
) c
i
g .
Therefore, equation (17) takes the form
(x g) + h = c
i
_
x e
i
g(1 a
i
)
a
i
_
+ d
i

_
x e
i
g(1 a
i
)
a
i
g
_
+d
i
h + f
i
+ h c
i
g d
i
h,
which, by easy computations, becomes
(x g) = c
i
_
(x g) e
i
a
i
_
+ d
i

_
(x g) e
i
a
i
_
+ f
i
,
which, in turn, by the position t = x g yields
(t) = c
i
_
t e
i
a
i
_
+ d
i

_
t e
i
a
i
_
+ f
i
,
that is (6).
b) Transformation in (11) is a linear map if g = h = 0 and ps ,= 0.
44 Lj. M. Kocic and A. C. Simoncelli
In this case (x) = p x, (x, y) = r x + s y , and
a
i
= a
i
, c
i
= (r/p)(a
i
d
i
) + (s/p)c
i
, e
i
= pe
i
,

f
i
= sf
i
+ re
i
,
so (17) becomes
rx/p + s(x/p) = sc
i
_
x/p e
i
a
i
_
+ sd
i

_
x/p e
i
a
i
_
+ r(a
i
d
i
)
_
x pe
i
pa
i
_
+rd
i
_
x pe
i
pa
i
_
+ re
i
+ sf
i
,
which gives
s(x/p) = sc
i
_
x/p e
i
a
i
_
+ sd
i

_
x/p e
i
a
i
_
+ ra
i
_
x pe
i
pa
i
_
+ re
i
+ sf
i
(rx)/p ,
and nally
(x/p) = c
i
_
x/p e
i
a
i
_
+ d
i

_
x/p e
i
a
i
_
+ f
i
,
which again yields (6) by the variable transformation t = x/p .
Remark 2. For another proof of (14), see [6]. For monotonicity preserving
property of , see [4].
Application and Examples
It was suggested in [2, Chap. 6] that the integral of the interpolating
fractal function satisfying equation (8) can be calculated by
I =
_
x
n
x
0
(x)dx =
_
x
n
x
0
(T)(x)dx =
n

i=1
_
x
i
x
i1
(T
i
)(x)dx
=
n

i=1
_
x
i
x
i1
_
c
i
x e
i
a
i
+ d
i

_
x e
i
a
i
_
+ f
i
_
dx,
which, by the substitution x = a
i
t + e
i
becomes
(18) I =
n

i=1
_
x
n
x
0
_
c
i
t + d
i
(t) + f
i
_
a
i
dt = I + ,
Functional Equations for Fractal Interpolants 45
where
(19) =
n

i=1
a
i
d
i
, =
n

i=1
a
i
_
x
n
x
0
(c
i
t + f
i
)dt.
And it follows from (18) that
(20) I =

1
.
Also in [2, p. 221], Barnsley suggests that equals
_
x
n
x
0

0
(x)dx where
(21)
0
(x) = y
i
+
y
i
x
i
(x x
i
) , x
i
x x
i+1
, i = 0, 1, . . . , n 1 ,
is the piecewise linear interpolant to the data Y . But, by (19),
=
n

i=1
a
i
_
x
n
x
0
(c
i
t + f
i
)dt =
n

i=1
a
i
_
c
i
x
2
n
x
2
0
2
+ f
i
(x
n
x
0
)
_
=
n

i=1
x
i1
2
_
c
i
(x
n
+ x
0
) + 2f
i

,
which, after replacing a
i
, c
i
and f
i
by their expression (2) gives
=
n

i=1
x
i1
2
_
y
i1
+ y
i
d
i
(y
0
+ y
n
)

,
or
(22) =
n

i=1
y
i1
+ y
i
2
x
i1

y
0
+ y
n
2
n

i=1
d
i
x
i1
.
Note that the rst term on the right hand side of (22) is, by itself, the value
of
_
x
n
x
0

0
(x)dx. Therefore =
_
x
n
x
0

0
(x)dx is valid if and only if
(23) y
0
+ y
n
= 0 ,
or
(24) d
i
= 0 , i = 1, 2, . . . , n.
46 Lj. M. Kocic and A. C. Simoncelli
Example 1. The Cantor function x f(x) is the interpolating fractal
function that is dened by the data Y = (0, 0), (1/3, 1/2), (2/3, 1/2), (1, 1)
and the scaling vector d = [1/2 0 1/2]
T
.
Thus, by (19), = 1/3 and by (22) = 1/3, which gives, by (20),
I =
_
1
0
f(x)dx = 1/2, which is the known result [3]. Here, neither condition
(23) nor (24) is satised, and in fact diers from
_
1
0

0
(x)dx = 1/2, where

0
is the piecewise linear interpolant to Y .
Direct computation, based on (18) and on the functional equation for
Cantor function
f(x) =
_

_
1
2
f(3x) , 0 x
1
3
,
1
2
,
1
3
x
2
3
,
1
2
f(3x 2) +
1
2
,
2
3
x 1 .
also gives
I =
_
1
0

0
(x)dx =
_
1
0
1
2
f(t)
dt
3
+
_
1
0
1
2
dt
3
+
_
1
0
_
1
2
f(t) +
1
2
_
dt
3
,
i.e., I =
1
3
I +
1
3
, which yields I = 1/2.
Example 2. Consider the functional equation of type (6)
(25) f(x) =
_
f(2x) + x, 0 x 1/2 ,
f(2x 1) x + 1 , 1/2 x 1 ,
where [[ < 1, [[ < 1.
Comparing (25) with (6) immediately gives d
1
= , d
2
= and x
0
= 0,
x
1
= 1/2, x
2
= 1. Letting x = x
i
, i = 0, 1, 2 in (25) results in the following
linear system:
f(0) = f(0),
f(1/2) = f(1) + 1/2,
f(1/2) = f(0) + 1/2,
f(1) = f(1),
Functional Equations for Fractal Interpolants 47
wherefrom it follows f(0) = f(1) = 0 and f(1/2) = 1/2. Thus, the interpo-
lating data set is Y = (0, 0), (1/2, 1/2), (1, 0), and therefore, a
1
= a
2
=
1/2 which gives (by (19)) = ( + )/2 and (by (22)) = 1/4.
Thus,
I =
1
2(2 )
.
Note that the condition (23) is valid and, accordingly, =
_
1
0
f
0
(x)dx, where
f
0
is a tent function which interpolates the data Y .
It is interesting to note that for = = 1/4 the interpolant given by
(25) is in fact a smooth function, namely the quadratic polynomial f(x) =
2 x(1 x). For other smooth fractal objects and their applications, see [5].
Acknowledgments. A rst draft of this paper was prepared while the
rst author was visiting the Dipartimento di Matematica ed Applicazioni
of Universit a Federico II, Naples (Italy) in October 1998. The visit was
supported by the Italia-Yugoslavia Joint Protocol for Scientic Collaboration
1998/2000.
REFERENCES
1. M. F. Barnsley: Fractal functions and interpolation. Constr. Approx. 2
(1986), 303329.
2. M. F. Barnsley: Fractals Everywhere. Academic Press, 1993.
3. E. Hille and J.D. Tamarkin: Remarks on a known example of a monotone
continuous function. Amer. Math. Monthly 36 (1929), 255264.
4. Lj. M. Koci c: Monotone interpolation by fractal functions. In: Approxima-
tion and Optimization (Proceedings of ICAOR) (D.D.Stancu et al., eds.),
pp. 291298, Transilvania Press, 1997.
5. Lj. M. Koci c and A. C. Simoncelli: Towards free-form fractal modelling.
In: Mathematical Methods for Curves and Surfaces II (M. Dhlen, T. Ly-
che, and L.L. Schumaker, eds), pp. 287294, Vanderbilt University Press,
Nashville (TN.), 1998.
6. Lj. M. Koci c and A. C. Simoncelli: Notes on fractal interpolation. Novi
Sad J. Math., n. 3, 30 (2000), 5968 [ Publ. Dip. Mat. Appl. R.Cacciop-
poli Napoli, n. 14 (1999) (preprint)].
7. P. R. Massopust: Fractal Functions, Fractal Surfaces and Wavelets. Aca-
demic Press, 1994.
48 Lj. M. Kocic and A. C. Simoncelli
Faculty of Electronic Engineering
Department of Mathematics
18000 Nis, Yugoslavia
Dip. Matematica ed Applicazioni
Universit`a Federico II
Napoli, Italy