WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Перестановочное неравенство, или неравенство об одномонотонных последовательностях, или «транс-неравенство», утверждает, что скалярное произведение двух наборов чисел является максимальным возможным, если наборы одномонотонны (то есть оба одновременно неубывающие или одновременно невозврастающие), и минимально возможным, если наборы противоположной монотонности (то есть один неубывающий, другой невозврастающий).

Другими словами, если $x_{1}\leqslant x_{2}\leqslant \dots \leqslant x_{n}$ и $y_{1}\leqslant y_{2}\leqslant \dots \leqslant y_{n}$ , то для произвольной перестановки $\sigma$ чисел $\{1,2,\dots ,n\}$ выполняется неравенство:

x_{1}y_{n}+x_{2}y_{n-1}+\cdots +x_{n}y_{1}\leqslant x_{1}y_{\sigma (1)}+x_{2}y_{\sigma (2)}+\cdots +x_{n}y_{\sigma (n)}\leqslant x_{1}y_{1}+x_{2}y_{2}+\cdots +x_{n}y_{n}

В частности, если $y_{i}=x_{i}$ , то $x_{1}x_{\sigma (1)}+\dots +x_{n}x_{\sigma (n)}\leq {x_{1}}^{2}+\dots {x_{n}}^{2}$ независимо от упорядочивания $x_{1},\dots ,x_{n}$ .

Следствием перестановочного неравенства является неравенство Чебышёва для сумм.

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

Обозначим $V(\sigma )=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)}}$ . Для доказательство удобно несколько переформулировать утверждение:

\arg \max \limits _{\sigma \in S_{n}}{V(\sigma )}=\sigma _{0}

Здесь $S_{n}$ - множество всех возможных перестановок, а $\sigma _{0}:\ x\mapsto x$ - тождественная перестановка.

Основная идея доказательства состоит в том, что если $\sigma (i)>\sigma (j)$ для некоторых $i<j$ , то, поменяв местами значения $\sigma (i)$ и $\sigma (j)$ , мы не уменьшим значение суммы $V(\sigma )$ .

Рассмотрим указанную сумму для некоторой перестановки $\sigma \not =\sigma _{0}$ и такой пары $i,j$ . Рассмотрим перестановку, образуемую из $\sigma$ инверсий этой пары.

\sigma ':x\mapsto \left\{{\begin{matrix}\sigma (j),&x=i\\\sigma (i),&x=j\\\sigma (x),&x\not \in \{{i,j}\}\end{matrix}}\right.

.

По определению,

V(\sigma ')=V(\sigma )-x_{i}y_{\sigma (i)}-x_{j}y_{\sigma (j)}+x_{i}y_{\sigma (j)}+x_{j}y_{\sigma (i)}=V(\sigma )+(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})

Согласно выбору $i,j$ и предположению об упорядоченности $x,y$ , справедливо неравенство $(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})\geq 0$ , так что $V(\sigma ')\geq V(\sigma )$ .

Следовательно, мы можем уменьшать число инверсий, не уменьшая значения $V(\sigma )$ . В итоге такой процесс приведёт к превращению $\sigma$ в $\sigma _{0}$ , так что $V(\sigma )\leq V(\sigma _{0})$ .

Обобщения

Для нескольких перестановок

Пусть даны $s$ упорядоченных последовательностей $x_{1}^{(i)}\leq x_{2}^{(i)}\leq \dots \leq x_{n}^{(i)},\ i=1,\dots ,s$ . Обозначим $V(\sigma _{1},\dots ,\sigma _{s})=x_{\sigma _{1}(1)}^{(1)}x_{\sigma _{2}(1)}^{(2)}\dots x_{\sigma _{s}(1)}^{(s)}+\dots +x_{\sigma _{1}(n)}^{(1)}x_{\sigma _{2}(n)}^{(2)}\dots x_{\sigma _{s}(n)}^{(s)}$ . Тождественную перестановку по-прежнему будет обозначать как $\sigma _{0}$ .

Тогда $V(\sigma _{1},\dots ,\sigma _{s})\leq V(\sigma _{0},\dots ,\sigma _{0})$ для любого набора $(\sigma _{1},\dots ,\sigma _{s})$ .

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

Доказывается аналогично обычному перестановочному неравенству (частному случаю этого при $s=2$ ).

Не ограничивая общности, будем предполагать, что $\sigma _{1}=\sigma _{0}$ , поскольку иначе можно просто умножить все перестановки на $\sigma _{1}^{-1}$ , не изменив значение суммы.

Если хотя бы одна из перестановок $\sigma _{1},\dots ,\sigma _{s}$ отлична от $\sigma _{0}$ , то для неё (обозначим её $\sigma _{k}$ ) существуют $i<j$ такие, что $\sigma _{k}(i)>\sigma _{k}(j)$ .

Тогда, если во всех перестановках $\sigma$ из набора $(\sigma _{1},\dots ,\sigma _{s})$ , для которых \sigma (i) > \sigma (j), поменять местами значения $\sigma (i)$ и $\sigma (j)$ , то значение $V$ не уменьшиться, а общее количество инверрсий среди $(\sigma _{1},\dots ,\sigma _{s})$ станет меньше.

Производя такие действия нужное (конечное) количество раз, придём к набору $(\sigma _{0},\dots ,\sigma _{0})$ , не уменьшив значение $V$ .

Для выпуклых функций

Идея доказательства через пошаговое исправление инверсий применима для более широкого класса случаев, чем просто для скалярного произведения.

Пусть $f$ - выпуклая функция, $x$ и $y$ упорядочены по неубыванию. Тогда

f(x_{1}+y_{\sigma (1)})+\dots +f(x_{n}+y_{\sigma (n)})\leq f(x_{1}+y_{1})+\dots f(x_{n}+y_{n})

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

По определению выпуклой функции, если $x_{1}<x_{2},\ c>0$ , то $f(x_{1}+c)-f(x_{1})\leq f(x_{2}+c)-f(x_{2})$ , то есть $f(x_{1}+c)+f(x_{2})\leq f(x_{1})+f(x_{2}+c)$ . Подствляя $c=c_{2}-c_{1}$ и прибавляя к обоим $x_{1},x_{2}$ величину $c_{1}$ , получаем $f(x_{1}+c_{2})+f(x_{2}+c_{1})\leq f(x_{1}+c_{1})+f(x_{2}+c_{2})$ . Иными словами, чем больше аргумент, тем больше изгиб функции вверх, и тем более ценнее для максимизации суммы прибавлять большее значение именно туда.

Как и в доказательстве обыччного перестановочного неравенства, выберем $i<j$ такие, что $\sigma (i)>\sigma (j)$ .

Тогда, как описано выше, $f(x_{i}+y_{\sigma (i)})+f(x_{j}+y_{\sigma (j)})\leq f(x_{i}+y_{\sigma (j)})+f(x_{j}+y_{\sigma (i)})$ . Это позволяет провести индукцию, аналогичную обычному случаю.

Умножая все значения $f$ на $-1$ , можно вывести аналогичное неравенство, но со знаком в другую сторону, для вогнутых функций.

Следствия

при $f(x)=e^{x}$ (выпуклая функция): обычное перестановочное неравенство для наборов $e^{x_{1}},\dots ,e^{x_{n}}$ и $e^{y_{1}},\dots ,e^{y_{n}}$

при $f(x)=x^{2}$ (выпуклая функция): $\sum \limits _{i}^{n}{(x_{i}^{2}+2x_{i}y_{\sigma (i)}+y_{\sigma (i)}^{2})}\leq \sum \limits _{i}^{n}{(x_{i}^{2}+2x_{i}y_{i}+y_{i}^{2})}$

После сокращения обеих частей на $\sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2})}$ , опять получаем обычное перестановочное неравенство.

при $f(x)=\log {x}$ (вогнутая функция): $\sum \limits _{i=1}^{n}{\ln(x_{i}+y_{\sigma (i)})}\geq \sum \limits _{i=1}^{n}{\ln(x_{i}+y_{i})}$

После взятия экспоненты от обоих частей: $\prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{i}+y_{i})}$ ;

при $f(x)={\frac {1}{x}}$ (вогнутая функция): $\sum \limits _{i=1}^{n}{\frac {1}{x_{i}+y_{\sigma (i)}}}\geq \sum \limits _{i=1}^{n}{\frac {1}{x_{i}+y_{i}}}$

Неудачные попытки обобщения

В 1946 году была опубликована (Scripta Mathematica 1946, 12(2), 164—169) попытка следующего обобщения неравенства:

Для $n\geq 3$ и двух наборов вещественных чисел $x_{1}\leqslant \cdots \leqslant x_{n}$ и $y_{1}\leqslant \cdots \leqslant y_{n}$ ,

x_{1}y_{\sigma (1)}+\cdots +x_{n}y_{\sigma (n)}\leqslant x_{1}y_{\pi (1)}+\cdots +x_{n}y_{\pi (n)}

если число инверсий в перестановке $\pi$ меньше чем в перестановке $\sigma$ .

Однако впоследствии оказалось, что уже при $n=4$ для этого неравенства существуют контрпримеры. Например,

{\textstyle 0\cdot 0+1\cdot 1+2\cdot 10+3\cdot 2=27<31=0\cdot 2+1\cdot 1+2\cdot 0+3\cdot 10}

При $n=3$ это обобщение всегда верно.

Полезные следствия

Перестановочное неравенство интересно тем, что позволяет интуитивно объединить общей основой внешне совершенно непохожие, но очень много применяемые в разных областях математики числовые неравенства.

В этом разеделе мы будем рассмарвиать наборы чисел длины $n$ и подразумевать, что обозначение $x_{i}$ при $i>n$ обозначает $x_{i-n}$ , то есть индексы зациклены.

Неравенство Коши — Буняковского

Согласно перестановочному неравенство, для любого $k$ выполняется $\sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}]}\leq \sum \limits _{i=0}^{n-1}{a_{i}^{2}}$ .

Из этого можно вывести важный частный случай неравенства Коши-Буняковского:

$\left({\sum \limits _{i=0}^{n-1}{a_{i}}}\right)^{2}=\sum \limits _{i=0}^{n-1}\sum \limits _{j=0}^{n-1}{a_{i}a_{j}}=\sum \limits _{i=0}^{n-1}\sum \limits _{j=0}^{n-1}{a_{i}a_{i+j}}\leq \sum \limits _{j=0}^{n-1}{\sum \limits _{i=1}^{n}{a_{i}^{2}}}=n\sum \limits _{i=1}^{n}{a_{i}^{2}}$

Аналогично, разбивая сумму на $n^{k-1}$ частей по всем возможным $(k-1)$ -мерным сдвигам индексов и используя обобщение на несколько перестановок, можно вывести более общее неравенство для целых $k$ :

$\left({\sum \limits _{i=0}^{n-1}{a_{i}}}\right)^{k}\leq n^{k-1}\sum \limits _{i=0}^{n-1}{a_{i}^{k}}$

Общее неравенство Коши-Буняковского

2(a_{1}b_{1}+\dots +a_{n}b_{n})=a_{1}b_{1}+\dots +a_{n}b_{n}+b_{1}a_{1}+\dots +b_{n}a_{n}\leq a_{1}^{2}+\dots +a_{n}^{2}+b_{1}^{2}+\dots +b_{n}^{2}

Если нормировать значения $a_{i}$ и $b_{i}$ таким образом, чтобы выполнялось $a_{1}^{2}+\dots +a_{n}^{2}=b_{1}^{2}+\dots +b_{n}^{2}=1$ , то это влечёт неравенство Коши-Буняковского. Для этого достаточно разделить все $a_{i}$ на ${\sqrt {a_{1}^{2}+\dots +a_{n}^{2}}}$ , а все $b_{i}$ на ${\sqrt {b_{1}^{2}+\dots +b_{n}^{2}}}$ . Поскольку неравенство Коши-Буняковского допускает такие умножения без изменения истинности, то это доказывает утверждение.

Неравенства средних

Квадратичное и арифметическое

Нервенство между квадратичным и арифметическим средним элементарно выводимо из доказанного выше частного случая неравенства Коши-Буняковског.

Арифметическое и геометрическое

Неравенство между арифметическим и геометрическим средним гласит, что

{\sqrt[{n}]{x_{1}\dots x_{n}}}\leq {\frac {x_{1}+\dots +x_{n}}{n}}

Умножая обе части на $n$ и рассматривая $n$ -ые степени переменных, увидим, что это то же самое, что

nx_{1}\dots x_{n}\leq x_{1}^{n}+\dots x_{n}^{n}

x_{1}x_{2}\dots x_{n-1}x_{n}+x_{2}x_{3}\dots x_{n}x_{1}+\dots +x_{n}x_{1}\dots x_{n-2}x_{n-1}\leq x_{1}^{n}+\dots x_{n}^{n}

Последнее же неравенство легко получить, используя обобщение перестановочного неравенство на несколько перестановок при $\sigma _{k}(i)=i+(k-1)$

Геометрическе и гармоническое

Приведём неравенство к тому же виду, что и предыдущее:

{\sqrt[{n}]{x_{1}\dots x_{n}}}\geq {\frac {n}{{\frac {1}{x_{1}}}+\dots {\frac {1}{x_{n}}}}}

{\frac {1}{x_{1}}}+\dots {\frac {1}{x_{n}}}\geq {\frac {n}{\sqrt[{n}]{x_{1}\dots x_{n}}}}

Рассматривая $n$ -ые степени переменных, получаем

n\left({\frac {1}{x_{1}}}\right)\dots \left({\frac {1}{x_{n}}}\right)\leq \left({\frac {1}{x_{1}}}\right)^{n}+\dots \left({\frac {1}{x_{n}}}\right)^{n}

Последнее неравенство легко получить прямым применением перестановчного неравенства для нескольких перестановок.

Ссылки

Л. В. Радзивиловский. Обобщение перестановочного неравенства и монгольское неравенство // Математическое Просвещение. — 2006. — № 10.
Yue Kwok Choy, Rearrangement inequalitty

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии