4. Affine invariance As we mentioned before, by s(D,M)we denote both the IFS and the interpolation scheme (depending on M = {M_{i}, i = 1,.., n}) that associates to D Ì R^{3 }the function f whose graph F_{D,M} is the unique attractor of s(D,M). Definition 2. An interpolation scheme s(D,M) is invariant upon transformation w: R^{3}® R^{3 } iff for any DÌ R^{3}, where F_{D,M } denotes the attractor of the IFS s(D,M). Definition 3. An interpolation
scheme s(D,M)
is weakly invariant upon w
iff there exists a set of matrices M' = {M_{i}',
i = 1,.., n} such that, for any DÌ
R^{3},
Note that invariance upon w is weak invariance with M' =M. In this section we will examine the invariance of the interpolation
scheme introduced according to Theorem
1 with respect to affine mappings
w:
R^{3}®
R^{3
}having
the same structure as transformations
w_{i}, more precisely
with a, a_{1}, b, b_{i }and g, g_{i } real parameters, and a_{1} > 0. We will give conditions for the strict invariance of the general scheme, and will also discuss an interesting and very useful case of weak invariance. Let w transform the data set D into the set of points w(D) = D^{*}= { P_{i}^{*} = [x_{i}^{*} y_{i}^{* }z _{i}^{*}], i = 0, 1,..., n}. Notice that the special form of the matrix W introduced in (14) guarantees that w transform pairs of points having strictly increasing abscissas into pairs of points having the same property, therefore it is possible to build the IFS s(D^{*},M ) = {R^{3}; w_{1}^{*}, ..., w_{n}^{*}} and consider the interpolation function corresponding to the transformed data set. At this point we need a general lemma, first. Also let (f_{° }g)(x) = g(f(x)). Lemma 2. Given the IFS s(D) = {R^{3}; w_{1}, ..., w_{n}} and a transformation w having equation (14), if w_{i}_{° }w = w_{° }w_{i}^{* } (i = 1,..., n) , then w(F_{D}) = F_{w(D) .} Proof. Let G denote the piecewise
linear interpolant of D. Then the
Hutchinson orbit of G is a sequence of polygonal lines converging
(in Hausdorff metric) to F_{D},
let this be {L_{k} = W^{ k}(G),
k
=
0, 1,...}. Also denote by L_{0}^{*} = w(L_{0})
the piecewise linear interpolant of D^{*
}=
w(D),
and
let L_{k}^{*} = W^{*}(L_{k}_{-1}^{*}),
k
=
1, 2,... where W^{*}( . ) = È_{i
}w_{i}^{*}(
. ). The sequence {L_{k}^{*}} is the Hutchinson
orbit of w(L_{0})
and, therefore, F_{w(D)
}=
lim_{k ®¥ }L_{k}^{*}
. If the diagram
commutes for all i, namely if w_{i}_{° }w = w_{° }w_{i}^{*} , then at every new iteration k it holds L_{k}^{*} = w(L_{k}), which means that F_{w(D) }= lim_{k®¥ }L_{k}^{*} = lim_{k ®¥ }w(L_{k}) = w(F_{D}) , being w a continuous function in R^{3}. à Lemma 3 (Translation case). Let the affine mapping w be the translation w(P) = P + v, or, equivalently, let W = I in (14). Then the interpolation scheme is strictly invariant under w, namely (12) holds. Proof. According to (5)
w_{i }(P) = P_{i }+A_{i
}(P
-P_{n})
and, analogously
w_{i}^{*}(P) = P_{i}^{*}+A_{i
}^{*}(P
-P_{n}^{*}),
with
Lemma 4 (Linear case). Let the affine mapping w have zero translation part, v = 0, so that it reduces to the linear transformation w(P) =WP. Let W have lower-triangular form with g_{2}= 0. Then, (12) is valid if and only if b_{2 }= g_{3}. Proof. Under the assumptions of the Lemma, the difference d_{i } will have the value d_{i }= (w_{°}w_{i}^{*}- w_{i}_{° }w)(P) = (A_{i}^{*}W - WA_{i})(P -P_{n}), where A_{i}^{* }is given by (16). For M=M', the matrix D = A_{i}^{*}W - WA_{i} has the following form So, D is the zero matrix for all feasible M if and only if b_{2 }= g_{3}. Then, d_{i}= 0, the diagram (15) commute, and w(F_{D,M}) = F_{w(D),M}. à The Lemmas 2, 3 and 4 can be combined into Theorem 3. Let the affine mapping w be defined by (14). Let the matrix W have lower-triangular form with g_{2}= 0. Then, the interpolation scheme s(D,M)is strictly invariant under w, namely (12) holds if and only if b_{2 }= g_{3}. The next example uses a specific visual approach to illustrate Theorem 3. Example 3. Let D = {(0, 0, 0), (1/4, 0, 1/2), (1/2, 1/2, 1/2), (3/4, 1, 1/2), (1, 1, 0)}be the data, and let the choice d_{1}= 0, d_{2}= 1/4, d_{3}= 1/4, d_{4}= 0, h_{1}= 0, h_{2}= 0, h_{3}= 0, h_{4}= -1/4, l_{1}= 1/4 , l_{2}= 0, l_{3}=l_{4}=-1/4, m_{1}= 0, m_{2}= -1/4, m_{3}= 1/4, m_{4}= 0 be made. By this, the parameter matrix set M is fully determined as well as the hyperbolic IFS s(D) ={R^{3}; w_{1}, w_{2}, w_{3}, w_{4}}with the attractor F_{D}. Further, consider two different linear maps w(P) =WP and q(P) =W_{1}P, where W and W_{1} are defined by The Figure 4 (above) shows three diagrams. The leftmost one is the graph w(F_{D}), the middle one is F_{w(D) }and the rightmost one represents both graphs simultaneously. Let the vector valued function g(x), 0 £ x £ 1, correspond to the graph w(F_{D}) and let g^{*}(x), 0 £ x £ 1, correspond to F_{w(D)}. To compare two graphs better, the function e(x) = |g(x) -g^{*}(x)|, 0 £ x £ 1, is calculated (Fig. 4, below).
Figure 4. Affine invariance. Let q(F_{D}) be the graph of the function h(x), 0 £ x £ 1, and let F_{q(D)} be the graph of h^{*}(x), 0 £ x £ 1. The Figure 5 shows the similar comparison as above. This time the difference between the graphs q(F_{D}) and F_{q(D)} (or h and h^{*}) is visible (left). This is proved by the graph of e (x) = |h(x) - h^{*}(x) |, 0 £ x £ 1, being different from zero.
Figure 5. Failure of affine invariance . The following theorem gives the conditions of weak invariance of an interpolating IFS. Theorem 4. Let s(D,M)be a hyperbolic block diagonal IFS. Let w be defined by (14) with W being a regular block diagonal matrix ( b_{1 }= g_{1}= 0 ).Then, the scheme s(D,M) is weakly invariant under w, namely (13) holds. Proof. Since s(D,M)
is a block diagonal, there exists a hyperbolic IFS t(D_{yz},M)
so that s(D,M)
is its lifting (Definition 1), i.e.,
the 2D data set D_{yz}
= {Q_{i} = [ y_{i } z_{i}]^{T
},
i
= 0, 1,..., n} obey conditions (11).
In the matrix form, these conditions are
where r_{i} = [ f_{i } g_{i}]^{T }. Since the scheme s(D,M) is invariant upon translation (Lemma 3), one can restrict transformation w given by (14) to the linear case w(P) = WP with W being a regular block diagonal matrix Now, w(P_{i}) = [a_{1}x_{i }b_{2}y_{i}+ b_{3}z_{i }g_{2}y_{i}+ g_{3}z_{i}]^{T} or, shortly w(P_{i}) = [a_{1}x_{i }(NQ_{i})^{T} ]^{T}. Multiplying (17) with N from the left, and using I = N^{-}^{1}N (since W is regular, N is invertable) one gets NQ_{i-}_{1 }= NM_{i }N^{-}^{1}NQ_{0 }+ Nr_{i}, NQ_{i }= NM_{i}N^{-}^{1}NQ_{n}+ Nr_{i}, which, by denoting takes the formEquations (19) are conditions (11) for the data set D_{yz}^{* }with v_{i}^{*}(y, z) = M_{i}^{*}[y z]^{T }+ r_{i}^{*}. Since M_{i}^{*}and M_{i }are similar matrices, they share eigenvalues, so t(D_{yz}^{*},M') is also a hyperbolic IFS and M' = {M_{i}^{*}, i = 1,.., n}. Let D^{*} be a lifting of the data D_{yz}^{*} on the mesh x_{0}< x_{1}< ...< x_{n} and let s(D^{*},M') be the lifting of t(D_{yz}^{*},M'). By Theorem 2, s(D^{*},M') = {R^{3}; w_{1}^{*}, ..., w_{n}^{*}} is also a hyperbolic block diagonal IFS. Let M_{i}^{*} be the lower-right 2x2 block of the matrix A_{i}^{*} that corresponds to the mapping w_{i}^{*}. Then, the first equality in (18) implies A_{i}^{*}= WA_{i}W^{-1 }or A_{i}^{*}W = WA_{i}, for i = 1,..., n, i.e., by Lemma 2, w( F_{D,M}) = F_{w(D),M' }. |