Проекция точки на выпуклые множества

Расстояние d от точки v до множества Х в евклидовом пространстве определяется по формуле d = inf ê ê v - х ê ê;.

xÎ Х

Определение 3.3. Точка р Î называется проекцией точки v на множество Х, если ê ê v - р ê ê = inf ê ê v - х ê ê;.

xÎ Х

Теорема 3.5. Для любого множества Х ¹ Æ и любой точки v существует точка рÎ , являющаяся проекцией точки v.

Доказательство. Если vÎ X, то p = v, d =0. Пусть vÎ X. Так как X¹ Æ, то существует точка у Î Х. Рассмотрим множество:

Y={x/x Î Х, //v-x//£ //v-y//}. (3.4)

Очевидно, что расстояние от v до х совпадает с расстоянием от v до Y и проекция точки v на X совпадает с проекциейточки v на Y (если эта проекция существует). Найдем проекцию v на Y. В силу определения нижней грани существует последовательность {x_k}Ì Y, такая что

lim // v - x_k // = d (3.5)

k ¥

Из ограниченности Y следует ограниченность последовательности {x_k}, поэтому из неё можно выделить последовательность {x_ki} такую что

lim x_ki = p, (3.6)

i ¥

где pÎ Ì .

Окончательно получаем также, что // v - p // = d, т.е. p есть проекция точки v.

Теорема 3.6. Для того, чтобы точка рÎ была проекцией точки vÎ Е_n на выпуклое множество Х необходимо и достаточно, чтобы для любого xÎ Х выполнялось неравенство

< (x-p), (v-p)> £ 0. (3.7)

По определению скалярного произведения

< (x-p), (v- p)> = ||x -p|| × || v-p|| cos((x-p), (v-p)), (3.8)

то есть знак скалярного произведения определяется углом между векторами (x-p) и (v-p). Таким образом (см. рисунок 3.4) точка pÎ тогда и только тогда является проекцией v когда угол между (x-p) и (v-p) не острый для любой точки хÎ .

 

v

p

x

X

Рис. 3. 4.

 

Доказательство

1.Необходимость. Пусть р проекция точки v на Х. Если vÎ , то p = v и неравенство (3.7) обращается в равенство.

Рассмотрим случай, когда vÏ . Возьмем произвольную точку хÎ и рассмотрим

z(a)= (1-a)p + a x, где aÎ [0, 1] (3.9)

Так как р – проекция, то

0 £ ||x - z(a)||² + || v-p||²=-2a < (x-p), (v-p)> + a²|| x-p||² (3.10)

для всех aÎ [0, 1]. Это неравенство возможно при всех aÎ [0, 1] лишь в том случае, если выполняется неравенство (3.7).

2. Достаточность. Пусть (3.7) справедливо для любого хÎ , тогда для любого xÎ Х получим:

|| v-x||² = ||(v -p)+(p-x)||² =|| v-p||² + 2 < (v-p), (p -x)> + || p -x||²³ || v-p||²

т.е. p есть проекция v на X

Следствие 3.2. Проекция любой точки vÎ Е_n на выпуклое множество Х единственна.

Доказательство. Если vÎ , то p=v. Если vÏ , то || v-x||> 0 для всякого хÎ . Допустим, что кроме проекции р точки v существует ещё проекция p' ¹ p. Для них || р-р' ||> 0, || v-р|| = || v-р' ||. Тогда

|| v-p||² = ||(v –p’)+(p’-p)||² =|| v-p||² + 2 < (v-p’), (p-p)> +|| p’-p||².

Откуда следует что || v-p||²> ||(v –p’)||. Полученное противоречие доказывает теорему.

Следует сделать замечание, что для множества, не являющегося выпуклым, следствие может не выполняться (см. рис. 3.5)

р₁

v

Х р₂

 

Рис. 3. 5