Contractions

A special type of affine transformation is a contractive transformation.

You can make a big fuss about how you define a contractive transform but put as bluntly as possible - it makes things smaller.

If you really want an accurate definition, then an affine transformation f is contractive if for all x and y:

   d(f(x),f(y)) <= s d(x,y)

where s is a constant between 0 and 1 and d(x,y) is the distance between the points x and y. You can see from the definition that a contractive transformation moves points closer together.

The constant s is called a contraction factor of the transformation and the largest such value gives you a measure of how much the contractive transformation moves points together - in other words, it tells you just how contractive the transformation is.

Why are contractive transformations important?

The reason is that if you take a point, any point, and apply the transformation and then apply the transformation to the result and so on the sequence of points so generated moves closer and closer to a fixed point or limit. That is, if you iterate a contractive affine transformation it eventually settles down to a stable result. 

In mathematical terms iterating an affine transformation on a point x is written

x, f(x), f(f(x)) f(f(f(x)))

and so on. It is usual to write fn(x) to mean the result of applying f n times to x. This allows us to write the important property of a contractive transformation as:

fn(x) -> z as n -> infinity

where -> is read as "tends to".

That is as n gets bigger fn(x) tends to a fixed value z.

Iterated function systems

At the moment you may not be able to see where fractals come into this. The answer is that a contractive affine transformation can generate a fractal.

By repeating the transformation an infinite number of times any starting pattern is transformed into a repeating pattern with the same structure at any level of detail - and this is one of the basic characteristics of a fractal set.

To make this idea practical we need to define an Iterated Function System or IFS.

This is just a collection of contractive affine maps c1, c2 and so on to cn. The contraction factor of the set of transformations is simply the largest of each of their individual contraction factors.

All we have at the moment is a set of transformations - what is interesting is the way that they work together.

The usual way of combining transformations is to apply them one after another. For example, c2 c3 c1(x) is just the result of applying c1 to x and then c3 to the result and then c2 to the result of that. This is just the familiar composition of functions.

An IFS, on the other hand, combines its transformations by allowing them to each act on the original and forming the union of all their results.

Of course this doesn't make any sense unless you think of the transformations acting on sets of points. That is, if A is a set of points then the result of applying the IFS to A is:

c1(A) U c2(A) U c3(A) and so on

where U means the "union of" and c1(A) is the set of points that A is transformed into.

You can see that an IFS tends to produce a set of images of the original set each one smaller than the original. 

<ASIN:1840467134>

<ASIN:0120790696>