Мир фракталов

Матрица статей Список статей Всячина Контакты

Сжимающие отображения

Определение и основная теорема

Определение. Отображение $f{:}\, X \rightarrow X$ в метрическом пространстве $(X, d)$ называется сжимающим, если существует такое число $s \in \left]0, 1\right[$ , что для любых $x_1$ и $x_2$ из $X$ выполнено

$d(f(x_1), f(x_2)) \le s d(x_1, x_2).$

Константа $s$ называется коэффициентом сжатия отображения $f$ .

Преобразования вида $f(f(\ldots f(x)\ldots) = f^{\circ^n}$ называются итерациями преобразования $f$ .

Точка $a$ такая, что $f(a) = a$ , называется неподвижной точкой отображения $f$ .

Теорема. Пусть $f{:}\, X \rightarrow X$ — сжимающее отображение, тогда существует единственная точка $a$ такая, что $f(a) = a$ , и для любой точки $x_0 \in X$ последовательность итераций $x_0, x_1 = f(x_0), x_2 = f^{\circ^2}(x_0), \ldots, x_n = f^{\circ^n}(x_0)$ сходится к $a$ .

Доказательство. Покажем, что последовательность $\{x_n\}$ фундаментальна. Для этого воспользуемся критерием Коши:

$\{x_n\} \to \Leftrightarrow \forall \varepsilon > 0 \; \exists N > 0 \; \forall n, m > N :\, d(x_n, x_m) < \varepsilon.$ Имеем $d(x_{n+1}, x_n) = d(f(x_n), f(x_{n-1}) \le$ $s d(x_n, x_{n-1}) = d(f(x_{n-1}), f(x_{n-2})) \le$ $s^2 d(x_{n-1}, x_{n-2}) \le$ $\ldots \le$ $s^n d(x_0, x_1)$ . Откуда $d(x_{n+k}, x_n) \le$ $d(x_{n+k}, x_{n+1}) + d(x_{n+1}, x_n) \le$ $d(x_{n+k}, x_{n+2}) + d(x_{n+2}, x_{n+1}) + d(x_{n+1}, x_n) \le$ $(s^{n+k-1} + \ldots + s^{n+1} + s^n)d(x_1, x_0) \le$ $\frac{s^n}{1 - s}d(x_1, x_0).$ Откуда при $n > m$ следует: $d(x_n, x_m) \le \frac{s^m}{1 - s}d(x_0, x_1).$ Зафиксируем $\varepsilon > 0$ . Выберем номер $N$ , удовлетворяющий условию: $\frac{s^m}{1 - s}d(x_0, x_1) < \varepsilon, \qquad m > N.$ Это можно сделать всегда, так как $s < 1$ , и, следовательно, $s^m \rightarrow 0$ при $m \rightarrow \infty$ . Таким образом, критерий Коши выполняется и и последовательность $\{x_n\}$ сходится. Обозначим предел этой последовательности через $a$ . Так как $f$ непрерывно, то имеем $f(a) = f(\lim\{x_n\}) =$ $\lim f(x_n) = \lim x_{n+1} = a$ . Покажем, что точка $a$ единственна. Пусть $a_1$ , $a_2$ ( $a_1 \neq a_2$ ) такие, что $f(a_1) = a_1$ , $f(a_2) = a_2$ . Тогда $d(a_1, a_2) = d(f(a_1), f(a_2)) \le s d(a_1, a_2)$ . Так как $s < 1$ , то получаем противоречие.

Паутинные диаграммы

Пусть $f{:}\, \mathbb{R} \rightarrow \mathbb{R}$ — вещественная функция, отображающая отрезок $[a, b]$ в $[a, b]$ . Предположим также, что функция $f(x)$ дифференцируема на $[a, b]$ , и $|f'(x)| \le s < 1$ на $[a, b]$ . Таким образом, $f$ — сжимающее отображение (это следует из теоремы Лагранжа). Выберем некоторую начальную точку $x_0 \in [a, b]$ . Положим: $x_{n+1} = f(x_n)$ ( $n = 1, 2, \ldots$ ). Тогда теорема о сжимающем отображении говорит, что последовательность $\{x_n\}$ сойдётся к неподвижной точке отображения $f$ . Изобразим этот процесс графически с помощью так называемой паутинной диаграммы. Паутинная диаграмма строится следующим образом. Начинаем в точке $(x_0, x_1)$ , перемещаемся в точку $(x_1, x_1)$ , затем в $(x_1, x_2)$ . И вообще, на каждом шаге перемещаемся из точки $(x_{n-1}, x_n)$ в $(x_n, x_n)$ , а затем в $(x_n, x_{n+1})$ . Построение этих шагов на экране и даёт графическое представление процесса сходимости при $n \rightarrow \infty$ .

Ниже приведена программа на языке Pascal (компилятор Free Pascal Compiler) с использованием OpenGL, строящая паутинные диаграммы.

program WebDiag;

uses
	gl, glut;

function f(x : Double) : Double;

begin
	f := cos(x) - 0.15 * (x + 1);
end;

procedure Draw; cdecl;

const
	dx = 0.05;
	Iter = 200;
	x0 = 0.9;
	
var
	x, x1, x2  : Double;
	i          : Cardinal;
	
begin
	glClearColor(0.0, 0.0, 0.0, 1.0);
	glClear(GL_COLOR_BUFFER_BIT);
	glColor3f(1.0, 1.0, 1.0);

	{Рисуем основной прямоугольник}
	glBegin(GL_LINE_LOOP);
	glVertex2f(0.0, 0.0);
	glVertex2f(0.0, 1.0);
	glVertex2f(1.0, 1.0);
	glVertex2f(1.0, 0.0);
	glEnd;
    
	{Рисуем диагональ}
	glBegin(GL_LINES);
	glVertex2f(0.0, 0.0);
	glVertex2f(1.0, 1.0);
	glEnd;

	{Рисуем график функции}
	glBegin(GL_LINE_STRIP);
	x := 0.0;
	while x <= 1.0 + 0.5*dx do 
	begin
		glVertex2f(x, f(x));
		glVertex2f(x, f(x));
		x := x + dx
	end;
	glEnd;

	{Рисуем паутину}
	x1 := x0;
	for i := 1 to Iter do
	begin
		x2 := f(x1);
		glBegin(GL_LINES);
		glVertex2f(x1, x1);
		glVertex2f(x1, x2);
		glVertex2f(x1, x2);
		glVertex2f(x2, x2);
		glEnd;
		x1 := x2;
	end;
	glFlush();
	glutSwapBuffers();
end;


var
	Rel : glFloat;
	
begin
	glutInit(@argc, argv);
	glutInitWindowPosition(0, 0);
	glutInitWindowSize(640, 640);
	glutInitDisplayMode(GLUT_RGB or GLUT_DOUBLE);
	glutCreateWindow('Паутинные диаграммы');
	glutDisplayFunc(@Draw);

	glMatrixMode(GL_PROJECTION);
	glLoadIdentity;
	glTranslatef(-0.9, -0.9, 0.0);
	glScalef(1.8, 1.8, 0.0);

	glutMainLoop()
end.

Смотрите также: