Неравенство четырёхугольника

Неравенство треугольника, из которого выводится неравенство четырёхугольника, известно с античности: в «Началах» Евклида предложение 20 книги I утверждает, что во всяком треугольнике сумма двух сторон больше третьей^[6]. Античные комментаторы отмечали, что этот факт очевиден, однако Евклид доказывал его строго^[7].

Само понятие метрического пространства, в котором неравенство четырёхугольника получает общий смысл, ввёл Морис Фреше в диссертации 1906 года Sur quelques points du calcul fonctionnel^[8][9]. Фреше выделил свойства расстояния — неотрицательность, симметрию и неравенство треугольника — в качестве аксиом, отделив их от конкретной евклидовой конструкции; сам термин он ещё не употреблял, называя такие объекты «классами (E)»^[10][11]. Название «метрическое пространство» (нем. metrischer Raum) предложил Феликс Хаусдорф в книге «Основы теории множеств» (1914)^[8][12].

Вывод неравенства для четырёх точек и его использование для доказательства непрерывности метрики стали стандартным элементом курсов функционального анализа с середины XX века. В отечественной учебной литературе оно приводится в книге Г. Е. Шилова «Математический анализ. Специальный курс» (1961), где названо неравенством четырёхугольника^[13].

Пусть ${\displaystyle (X,\rho )}$ — метрическое пространство, то есть множество ${\displaystyle X}$ с заданной на нём метрикой ${\displaystyle \rho \colon X\times X\to \mathbb {R} }$, удовлетворяющей аксиомам тождества, симметрии и неравенства треугольника. Тогда для любых четырёх точек ${\displaystyle x,y,z,u\in X}$ выполняется неравенство^[14][15]:

${\displaystyle {\bigl |}\,\rho (x,z)-\rho (y,u)\,{\bigr |}\leqslant \rho (x,y)+\rho (z,u).}$

Точки не обязаны быть попарно различными: неравенство остаётся верным и при их совпадении, а также в псевдометрическом пространстве, где различные точки могут находиться на нулевом расстоянии.

Раскрывая модуль, неравенство можно записать в виде двойного неравенства:

${\displaystyle -{\bigl (}\rho (x,y)+\rho (z,u){\bigr )}\ \leqslant \ \rho (x,z)-\rho (y,u)\ \leqslant \ \rho (x,y)+\rho (z,u),}$

то есть каждое из расстояний ${\displaystyle \rho (x,z)}$ и ${\displaystyle \rho (y,u)}$ отличается от другого не более чем на ${\displaystyle \rho (x,y)+\rho (z,u)}$.

Доказательство опирается на неравенство треугольника, применённое дважды — к пути из ${\displaystyle x}$ в ${\displaystyle z}$ через промежуточные точки ${\displaystyle y}$ и ${\displaystyle u}$ и к симметричному пути из ${\displaystyle y}$ в ${\displaystyle u}$^[17][18].

Последовательное применение неравенства треугольника к трём звеньям даёт (см. неравенство ломаной):

${\displaystyle \rho (x,z)\ \leqslant \ \rho (x,y)+\rho (y,u)+\rho (u,z);}$

${\displaystyle \rho (y,u)\ \leqslant \ \rho (y,x)+\rho (x,z)+\rho (z,u).}$

Вычтем из обеих частей первого неравенства величину ${\displaystyle \rho (y,u)}$, а из обеих частей второго — величину ${\displaystyle \rho (x,z)}$. С учётом симметрии метрики (${\displaystyle \rho (y,x)=\rho (x,y)}$ и ${\displaystyle \rho (u,z)=\rho (z,u)}$) получим:

${\displaystyle \rho (x,z)-\rho (y,u)\ \leqslant \ \rho (x,y)+\rho (z,u);}$

${\displaystyle \rho (y,u)-\rho (x,z)\ \leqslant \ \rho (x,y)+\rho (z,u).}$

Два числа ${\displaystyle t}$ и ${\displaystyle -t}$ не превосходят одной и той же величины ${\displaystyle M\geqslant 0}$ в точности тогда, когда ${\displaystyle |t|\leqslant M}$. Полагая ${\displaystyle t=\rho (x,z)-\rho (y,u)}$ и ${\displaystyle M=\rho (x,y)+\rho (z,u)}$, получаем требуемое:

${\displaystyle {\bigl |}\,\rho (x,z)-\rho (y,u)\,{\bigr |}\leqslant \rho (x,y)+\rho (z,u).}$

В доказательстве используются лишь симметрия и неравенство треугольника; аксиома тождества (${\displaystyle \rho (x,y)=0\Leftrightarrow x=y}$) не нужна, поэтому неравенство верно и для псевдометрик.

Случаи равенства

Неравенство нельзя усилить: существуют конфигурации, в которых оно обращается в равенство. На числовой прямой с метрикой ${\displaystyle \rho (a,b)=|a-b|}$ для точек ${\displaystyle x=0,\ y=1,\ u=3,\ z=4}$ имеем

${\displaystyle {\bigl |}\rho (x,z)-\rho (y,u){\bigr |}=|4-2|=2,\qquad \rho (x,y)+\rho (z,u)=1+1=2.}$

Другой случай равенства — совпадение трёх точек: при ${\displaystyle x=y=z}$ обе части равны ${\displaystyle \rho (z,u)}$. Таким образом, константа 1 при каждом из слагаемых правой части является наилучшей возможной.

При ${\displaystyle z=u}$ неравенство четырёхугольника переходит в так называемое обратное (или второе) неравенство треугольника^[19]:

${\displaystyle {\bigl |}\,\rho (x,z)-\rho (y,z)\,{\bigr |}\leqslant \rho (x,y).}$

Содержательно оно означает, что расстояния от двух точек до общей третьей точки различаются не более чем на расстояние между самими этими точками. В нормированном пространстве с метрикой ${\displaystyle \rho (x,y)=\|x-y\|}$ и при ${\displaystyle z=0}$ это даёт известное неравенство для нормы:

${\displaystyle {\bigl |}\,\|x\|-\|y\|\,{\bigr |}\leqslant \|x-y\|.}$

Верно и обратное: если для метрики выполняется обратное неравенство треугольника при всех тройках точек, то, применив его дважды, можно вывести полное неравенство четырёхугольника. В этом смысле два утверждения равносильны.

В планиметрии неравенство формулируется для длин сторон четырёхугольника. Пусть ${\displaystyle a,b,c,d}$ — длины последовательных сторон четырёхугольника ${\displaystyle ABCD}$ (в том числе вырожденного или невыпуклого). Тогда:

• каждая сторона не превосходит суммы трёх остальных:

${\displaystyle a\leqslant b+c+d,\quad b\leqslant a+c+d,\quad c\leqslant a+b+d,\quad d\leqslant a+b+c;}$

• модуль разности любых двух сторон не превосходит суммы двух оставшихся; например, для сторон ${\displaystyle a}$ и ${\displaystyle b}$:

${\displaystyle |a-b|\leqslant c+d.}$

Эти две системы неравенств равносильны: каждая из них означает, что наибольшая из четырёх длин не превосходит суммы трёх остальных. Действительно, из ${\displaystyle |a-b|\leqslant c+d}$ следует ${\displaystyle a-b\leqslant c+d}$, то есть ${\displaystyle a\leqslant b+c+d}$; обратно, из четырёх неравенств первой группы вытекает каждое неравенство второй.

Условие является не только необходимым, но и достаточным: если четыре положительных числа удовлетворяют этим неравенствам, то из отрезков таких длин можно составить (вообще говоря, невыпуклый или вырожденный) четырёхугольник. Это утверждение — частный случай общей теоремы о существовании многоугольника с заданными сторонами^[22].

В теории алгоритмов и динамическом программировании термином неравенство четырёхугольника (англ. quadrangle inequality) называют иное условие, наложенное на функцию стоимости ${\displaystyle w}$:

${\displaystyle w(a,c)+w(b,d)\ \leqslant \ w(a,d)+w(b,c)\qquad {\text{при}}\quad a\leqslant b\leqslant c\leqslant d.}$

Это условие, известное также как условие Монжа, ввела Эндрю Яо в 1980 году, обобщив приём, применённый Дональдом Кнутом в 1971 году для ускорения построения оптимальных двоичных деревьев поиска с ${\displaystyle O(n^{3})}$ до ${\displaystyle O(n^{2})}$ операций^[23]. С метрическим неравенством четырёхугольника оно не связано: метрика не обязана ему удовлетворять — например, функция ${\displaystyle w(x,y)={\sqrt {|x-y|}}}$, будучи метрикой на прямой, этому условию не удовлетворяет ни при каком расположении точек.