для всех хи Х2 е X. Константа s называется коэффициентом сжатия отображения /. На Рис. 2.2.2 показан пример сжимающего отображения на (R2, d2), примененного к множеству точек в R2.

42_Фракталы и вейвлеты для сжатия изображений в действ^

Рис. 2.2.1. Сжимающее отображение, преобразующее множество точек в R2

На Рис. 2.2.2 показано преобразование, примененное более одного раза. Сначала fix) вычисляется для точки х, затем / применяется к результату и вычисляется fifix)). Вы можете продолжить этот процесс и вычислить flf(j{x))) и так далее. Преобразования, получаемые таким многократным применением/, называются итерациями /. и8* итерация/обозначается /°л, то есть,/°%х) = ДД.. .fix)...)), где/применяется п раз.

Заметим, что fix),f>2(x)Jf>3(x),... образуют последовательность в X. Пусть/-сжимающее отображение с коэффициентом сжатия s. Заметим, что

^0Ч4/оМ)(ф^(/о(""1)(4/>+",\4^"4'/0*(4

Заметим также, что

4,/0Чф4'/^)+^(4/о2«)+.--+^оМ)(4/"Ч4

< (l + s + s2 +... + sk-l]d{X,f(X))<-L.d(X,f(X))

l — s

где последнее неравенство следует из разложения ряда (l-s)'\ так как О < s < 1. Так, например, если п <т, мы получим

JL S

Так как s < 1, то выражение в правой части стремится к 0 при п,т —> ©о. Другими словами, последовательность {f°n(x)} является последовательностью Коши в (X,d). Так как, далее, (X,d) - это полное метрическое пространство, эта последовательность сходится к пределу Xf е X, то есть

\imf°n(x)=x

П—>о°

Системы итерируемых функций

43

Точка х/ обладает особым свойством. Что произойдет, если

МЫ ПрИМеНИм/к ДГу?

Так ка,к/°п(х) —оба выражения в правой части стремятся к 0, а, следовательно, выражение в левой части - тоже 0. Другими словами,

Точка х/ называется неподвижной точкой /. Как много неподвижных точек может иметь сжимающее отображение? Предположим, что существует другая неподвижная точка >у отображения/, то есть Дуу) = >у. Тогда

Так как 5 < 1, то из неравенства следует, что с1(х^ >у) = 0, то есть Д/ = >у. Таким образом, сжимающее отображение / на (Ху(Г) имеет одну и только одну неподвижную точку в X. Заметим, что поскольку имеется только одна неподвижная точка, то {/°%х)} сходится к этой неподвижной точке независимо от начальной точки х. Это подытоживается в следующей теореме: