In the most basic of terms, what does contraction mapping mean?

2.1k Views Asked by At

So, I have been solving a number of exercises involving contraction mapping. However, I am struggling to understand what exactly contraction mapping is at its most basic. All I really understand from the concept is that if we have two sets, then one specific point on the set is being mapped closer to another - I'm not sure if I have the right definition.

Can somebody please explain this to me in the most layman way possible?

1

There are 1 best solutions below

0
On

Your intuition is (informally) very close. Take any two points in your set and calculate their distance from each other. A function is a contraction mapping if, after you apply the function to the two points, they get closer together no matter which two points you started with.

What a contraction mapping does, in other words, is to squeeze all the points closer together.

There are a few problems with this informal view. First of all, how do we define the distance between two points? In the case of well-known sets, there is often a standard way of doing this. If $a$ and $b$ are real numbers, for instance, their Euclidean distance is $|a - b|$. In general, however, we have to be very specific about what we mean by distance and define a metric on our set.

A metric is a function that takes in two points, and returns a non-negative real number representing the distance between them. For instance, the Euclidean metric on the real numbers is $d(x, y) = |x - y|$. Not all functions represent a sensible notion of distance - for instance $d(x, y) = 0$ would be rather useless. Because of this, we have to make sure that our metric satisfies several rules. You might like to look these rules up if you are interested, but you can just take it on faith that any function satisfying these rules behaves like we'd expect distance to behave.

A set with a metric defined on it is called a metric space. Let's consider a metric space $X$, and let's write the metric as $d_X(x, y)$. Similarly, consider another metric space $Y$ with metric $d_Y(x, y)$.

A contraction mapping is then, more formally, a function $f: X \to Y$ (it takes in an element in $X$ and returns an element in $Y$) such that:

$d_Y(f(x), f(y)) < d_X(x, y)$

Because $f(x)$ and $f(y)$ are the points $x$ and $y$ after the contraction mapping is applied, this is saying precisely that $f$ makes the distance between $x$ and $y$ smaller!