В статье
было предложено доказать некоторые утверждения о проекциях на выпуклое множество. Здесь я показываю решения. Для их понимания необходимо знать сформулированные в цитируемой статье определения.
Стандартизуем обозначения. Буквы могут не быть и могут быть с индексами:
- A (распространённое имя для точек) — проецируемые точки;
- B (тоже распространённое имя), Y (в паре с X) — некоторые другие, вспомогательные точки;
- C (convex, на картинках отмечается зелёным цветом) — выпуклое множество;
- P (projection, отмечается зелёным цветом) — их проекции;
- S (support) — опорные прямые;
- X (обозначение на короткое время) — переменная точка.
Существование и единственность проекции
Теорема. Если выпуклое множество C замкнуто (т.е. содержит свою границу), то проекция на это множество существует, принадлежит границе и определяется единственным образом.
Существование. Эта часть доказательства демонстрирует типичное для матанализа рассуждение — на уровне 1 курса физ.-мат. или технических специальностей вузов. Если вы не готовы разбирать такое, можно пропустить и сразу перейти к единственности (там будет чисто школьная геометрия).
Множество всех возможных расстояний ρ(A, X), когда X пробегает всё множество C — обозначим его R — ограничено снизу числом 0.
Тогда множество R имеет нижнюю грань d. Это означает, что R не имеет значений, меньших d, и в то же время как угодно близко к d имеются значения из R, большие или равные d. (Это фундаментальное свойство при некоторых изложениях входит в систему аксиом, определяющих действительные числа.)
Тогда для любого натурального n существует точка X_n множества C такая, что
d ≤ ρ(A, X_n) < d + 1/n.
Сразу отметим сходимость
ρ(A, X_n) → d. (*)
Все эти точки лежат в замкнутом круге радиуса d + 1 с центром A. Так как этот круг есть компактное множество, то последовательность точек X_n содержит сходящуюся подпоследовательность, предел которой назовём P. Так как множество C замкнуто, то точка P лежит в C. А в силу непрерывности функции расстояния, из (*) следует
ρ(A, P) = d.
Причём d > 0. В противном случае P = A и точка A, как предел последовательности точек замкнутого множества C, ему принадлежит.
Таким образом, P есть проекция точки A на множество C.
Любая окрестность точки P содержит такую точку B, что ρ(A, B) < d (не выходя из кружочка с центром P можно сдвинуться в направлении к A), так что B не лежит в С. Поэтому точка P не является внутренней для множества С, и значит, она принадлежит границе С.
Вообще-то у последовательности точек X_n могут быть разные сходящиеся подпоследовательности. Но их пределы совпадают, так как имеет место...
Единственность. Допустим, что точка A имеет 2 различные проекции: P₁ и P₂.
Так как P₁ и P₂ обе ближайшие к A, то |AP₁| = |AP₂|. Треугольник AP₁P₂ равнобедренный. Так как P₁ и P₂ обе принадлежат C, то в C лежит и весь отрезок P₁P₂. Но тогда его середина — точка P — находится от точки A на расстоянии, меньшем, чем |AP₁|. А это противоречит определению проекции.
Проецирующая и опорная прямые
Пусть точка A лежит вне выпуклого замкнутого множества C и P — её проекция на C. Прямую AP и луч AP будем называть проецирующими.
Проведем через точку P прямую S перпендикулярно к AP. Эту прямую будем называть опорной.
Опорная прямая делит плоскость на две полуплоскости. Про ту из них, которая содержит точку A, будем говорить, что она по эту сторону от прямой S. Противоположную полуплоскость назовём той стороной. Саму прямую S будем считать принадлежащей той стороне.
Предложение. Пусть прямые AP и S перпендикулярны и пересекаются в точке P. Точка P является проекцией точки A, а S является, соответственно, опорной прямой, тогда и только тогда, когда
а) P принадлежит C,
б) множество C находится по ту сторону относительно S.
Доказательство. 1. Пусть P является проекцией.
а) P принадлежит C по определению проекции.
б) Предположим, что множество C имеет точку X по эту сторону:
Тогда весь отрезок PX лежит в C, а ∠APY < 90°. Поэтому на отрезке PX можно выбрать точку Y так, чтобы ∠AYP был тупым. В △AYP против бóльшего угла лежит бóльшая сторона, поэтому ρ(A, P) > ρ(A, Y). А это противоречит тому, что P — проекция точки A. Противоречие показывает, что такой точки X по эту сторону быть не может.
2. Обратно, пусть условия а) и б) выполнены. Тогда любая точка X из множества C находится на расстоянии от A, не меньшем, чем расстояние ρ(A, P). В самом деле, все точки с меньшим расстоянием находятся в круге с центром в точке A и радиусом ρ(A, P) (окрашенном серым):
⎕
Следствие. Все точки луча PA проецируются в P. ⎕
Но множество точек, проецирующихся в P, может этим не ограничиваться:
Упражнение. Сравните с проецированием на прямую.
Эти общие сведения о выпуклых множествах и опорных гиперплоскостях я привёл здесь для полноты дальнейшего изложения.
Сравнение расстояний
Теорема. Пусть точки A₁ и A₂ лежат вне замкнутого выпуклого множества C, а P₁ и P₂ — соответственно их проекции на С. Тогда
ρ(P₁, P₂) ≤ ρ(A₁, A₂).
Доказательство. Сначала рассмотрим случай, когда прямые A₁P₁ и A₂P₂ параллельны.
Случаи параллельности проецирующих прямых
Возможно, что лучи A₁P₁ и A₂P₂ имеют противоположные направления:
Тогда сравним катеты прямоугольных треугольников, в которых A₁A₂ и P₁P₂ служат гипотенузами, и применим теорему Пифагора.
Если же лучи A₁P₁ и A₂P₂ сонаправлены, то дело обстоит ещё проще:
Здесь опорные прямые S₁ и S₂ совпадают между собой и с прямой P₁P₂, так как иначе
точка P₂ множества С окажется по эту сторону от опорной прямой S₁.
Пусть теперь прямые A₁P₁ и A₂P₂ пересекаются. Точку пересечения назовём O. (Совсем не обязательно это будет началом координат; но ничто не мешает, если надо, поместить начало координат именно здесь.)
Невозможные конфигурации
Не лишним будет рассмотреть и исключить несколько конфигураций, невозможных по определению проекции и/или в силу её единственности.
Точка O не может быть по эту сторону от обеих опорных прямых, ибо в таком случае она бы проецировалась сразу в две точки P₁ и P₂.
На следующих картинках (листайте!) приведены невозможные конфигурации. Проекция P₂ (окрашена зелёным) должна принадлежать C, но находится по эту сторону от опорной прямой S₁:
Далее, предположим, что O находится по ту сторону относительно S₁ и по эту сторону относительно S₂. Тогда ∠A₁OA₂ не может быть острым или прямым.
В самом деле, пусть точка B — проекция точки A₁ на прямую A₂P₂.
Если ∠A₁OA₂ острый (см. рис.), то точка B лежит на отрезке OA₂ и |BP₂| = |BO| + |OP₂|, поэтому точка B, а с ней и P₁, находятся по эту сторону от опорной прямой S₂. Это противоречит тому, что P₁ принадлежит C, а множество C всё лежит по ту сторону от S₂.
Если ∠A₁OA₂ прямой, то точка B попадает в O и оказывается по эту сторону от S₂, а с ней и P₁.
Если же угол тупой, то конфигурации могут быть как невозможные,
так и вполне возможные:
Доказательство в возможных конфигурациях
Наводящее соображение. Если точки A₁ и A₂ перемещать по этосторонним частям проецирующих прямых, то их точки-проекции не изменятся. Такие смещённые точки будем обозначать A'₁ и A'₂ соответственно. Нужно построить эти точки так, чтобы расстояние между ними
ρ(A'₁, A'₂) ≤ ρ(A₁, A₂). (**)
Для этого надо придумать такой способ уменьшения отрезка A₁A₂, чтобы это укорочение гарантировать. И тогда остаётся получить неравенство
ρ(P₁, P₂) ≤ ρ(A'₁, A'₂). (***)
В общем случае, прямую A₁A₂ будем перемещать параллельно себе в направлении к точке O — при этом отрезок A'₁A'₂ становится короче A₁A₂ — до того момента, как один из концов отрезка A'₁A'₂ не совпадёт с соответствующей точкой-проекцией. Реализуем эту идею.
1. В случае, когда O находится по ту сторону относительно S₁ и по эту сторону относительно S₂ имеем, как показано выше, тупой ∠A₁OA₂.
В треугольнике A₁OA₂ сторона A₁O содержит точку P₁ (которая не может совпасть с точкой O, так как в случае совпадения O окажется уже по ту сторону относительно S₂), а сторона A₂O не содержит точки P₂ (она находится дальше по лучу A₂O, чем точка O, см. рис. 4a, 4b).
Поэтому в результате параллельного переноса прямой A₁A₂ точка A'₁ совпадёт с P₁, а точка A'₂ будет лежать на отрезке A₂O. Следующие картинки демонстрируют возможные ситуации:
И есть еще возможность, когда точки A₁, O и A₂ не образуют треугольник! Это когда две "вершины" совпадают. При этом точка O, будучи потусторонней для A₁, с ней совпадать не может. Поэтому O = A₂.
В этом случае проецирующий луч A₁O проходит через точку P₁, которая и служит концом A'₁ укороченного отрезка A'₁A'₂.
2. Теперь рассмотрим ситуацию, в которой точка O находится по ту сторону относительно и S₁, и S₂. В ней мы ещё имеем свободу выбора индексов ₁ и ₂. Присвоим индекс ₁ тому концу отрезка A₁A₂, который при параллельном переносе первым достигнет точки-проекции, которая и будет точкой P₁. При этом точка A'₂ всё еще будет лежать на отрезке A₂P₂. См. следующие рисунки:
Если точки A'₁ и A'₂ расположены на лучах OA₁ и OA₂ ближе к точке O, чем исходные ("нештрихованные") точки, и A'₁A'₂ ∥ A₁A₂, то в силу подобия треугольников OA₁A₂ и OA'₁A'₂ имеем
|A'₁A'₂| ≤ |A₁A₂|. (**)
В крайнем случае точка A'₂ тоже совпадёт с проекцией P₂. В этом случае неравенство |P₁P₂| ≤ |A₁A₂| тривиально; этот случай в дальнейшем не будем рассматривать.
3. Итак, во всех ситуациях рис. 4а,b, 5a – e, 6a,b мы получили отрезок A'₁A'₂, для которого верно неравенство (**).
Так как точка A'₁ = P₁ принадлежит S, то она лежит по ту сторону относительно S₂. Поэтому в △A'₁P₂A'₂ ∠A'₁P₂A'₂ ≥ 90°. А так как в треугольнике против бóльшего угла лежит бóльшая сторона, то
|P₁P₂| = |A'₁P₂| ≤ |P₁A'₂| = |A'₁A'₂|,
что в сочетании с (**) и даёт
|P₁P₂| ≤ |A₁A₂|.
Доказательство завершено. ⎕
Обсуждение
Ну вот, теперь осталась самая скучная и нудная часть работы — записать доказательство на языке векторов и скалярных произведений. А то как-то несолидно получается! Затем, векторный стиль изложения может быть перенесён на произвольную размерность n без тяжёлых хирургических вмешательств.
Но я здесь не буду этим заниматься по понятным, надеюсь, мотивам.
Побочным, и приятным, эффектом такого переписывания может оказаться поглощение полученным рассуждением особых случаев. Например, когда
A₁P₁ ∥ A₂P₂ или O = A₂.
А то неизящно это, разбирать столько отдельных вариантов конфигурации.
Вот так, например, выглядит картина, если смещать отрезок A₁A₂ в случае сонаправленных лучей A₁P₁ и A₂P₂:
Полученное доказательство не поражает своим изяществом. Вполне возможно, что существует и более лаконичное доказательство, и я бы с удовольствием с ним познакомился. Но
- оно наверное будет не таким элементарным,
- человеческая психология такова, что так как я уже получил именно такое доказательство, то мне придумать другое, это практически невозможно.
Следующая задача
Понятие проекции на C можно расширить, сняв требование, чтобы точка A была вне C. Тогда проекцией точки множества C будет являться сама эта точка.
Будет ли в таком случае верно утверждение теоремы?