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

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

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

Определение. Отображение в метрическом пространстве называется сжимающим, если существует такое число , что для любых и из выполнено

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

Преобразования вида называются итерациями преобразования .

Точка такая, что , называется неподвижной точкой отображения .

Теорема. Пусть — сжимающее отображение, тогда существует единственная точка такая, что , и для любой точки последовательность итераций сходится к .

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

Имеем . Откуда Откуда при следует:
Зафиксируем . Выберем номер , удовлетворяющий условию:
Это можно сделать всегда, так как , и, следовательно, при . Таким образом, критерий Коши выполняется и и последовательность сходится. Обозначим предел этой последовательности через . Так как непрерывно, то имеем . Покажем, что точка единственна. Пусть , () такие, что , . Тогда . Так как , то получаем противоречие.

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

Пусть — вещественная функция, отображающая отрезок в . Предположим также, что функция дифференцируема на , и на . Таким образом, — сжимающее отображение (это следует из теоремы Лагранжа). Выберем некоторую начальную точку . Положим: (). Тогда теорема о сжимающем отображении говорит, что последовательность сойдётся к неподвижной точке отображения . Изобразим этот процесс графически с помощью так называемой паутинной диаграммы. Паутинная диаграмма строится следующим образом. Начинаем в точке , перемещаемся в точку , затем в . И вообще, на каждом шаге перемещаемся из точки в , а затем в . Построение этих шагов на экране и даёт графическое представление процесса сходимости при .


Паутинная диаграмма Паутинная диаграмма

Ниже приведена программа на языке 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.

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