Transineegalitatea

Inegalitatea de permutare , sau inegalitatea despre secvențele monotone sau „ trans -inegalitatea ”, afirmă că produsul punctual a două seturi de numere este maximul posibil dacă seturile sunt monotone (adică ambele sunt simultan nedescrescătoare ). sau simultan necrescător), iar cel mai mic posibil dacă mulţimile sunt de monotonitate opusă (atunci una este nedescrescătoare, iar cealaltă este necrescătoare).

Cu alte cuvinte, dacă și , atunci pentru o permutare arbitrară a numerelor , este valabilă următoarea inegalitate: $x_1\leqslant x_2 \leqslant \dots\leqslant x_n$ $y_1\leqslant y_2 \leqslant \dots\leqslant y_n$ $\sigma$ $\{1,2,\puncte,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

În special, dacă , atunci indiferent de comanda . $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}$

O consecință a inegalității de permutare este inegalitatea Chebyshev pentru sume .

Dovada

Să notăm . Pentru demonstrație, este convenabil să reformulam oarecum afirmația: $V(\sigma)=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)))$

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

Aici este setul tuturor permutărilor posibile și este permutarea identică . $S_{n}$ $\sigma _{0}:\x\mapsto x$

Ideea principală a dovezii este că, dacă pentru unii , atunci schimbând valorile lui și , nu vom scădea valoarea sumei . $\sigma (i)>\sigma (j)$ $i<j$ $\sigma (i)$ $\sigma (j)$ $V(\sigma )$

Luați în considerare suma indicată pentru o permutare și o astfel de pereche . Luați în considerare permutarea formată din inversiunile acestei perechi. $\sigma \not =\sigma _{0)$ $i,j$ $\sigma$

\sigma ':x\mapsto \left\{{\begin{matrix}\sigma (j),&x=i,\\\sigma (i),&x=j,\\\sigma (x), &x\nu \în \{{i,j}\}.\end{matrice}}\right.

Prin definitie,

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)})

Prin alegere și ipoteza de ordonare , inegalitatea este adevărată , astfel încât . $i,j$ $X y$ $(x_{j}-x_{i})(y_{\sigma (i)} -y_{\sigma (j)})\geq 0$ $V(\sigma ')\geq V(\sigma )$

Prin urmare, putem reduce numărul de inversiuni fără a scădea valoarea (de exemplu, fixând inversiunile în ordinea de sortare cu bule ). Drept urmare, un astfel de proces va duce la transformarea în , deci . $V(\sigma )$ $\sigma$ $\sigma _{0}$ $V(\sigma)\leq V(\sigma _{0})$

Generalizări

Pentru permutări multiple

Fie secvențe ordonate date . Să notăm . Permutarea identică va fi totuși notată ca . $s$ $x_{1}^{(i)}\leq x_{2}^{(i)}\leq \dots \leq x_{n}^{(i)},\ i=1,\dots , s$ ${\displaystyle 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}$

Apoi pentru orice set . $V(\sigma _{1},\dots,\sigma _{s})\leq V(\sigma _{0},\dots,\sigma _{0})$ $(\sigma _{1},\dots,\sigma _{s})$

Dovada

Se dovedește în mod similar cu inegalitatea obișnuită de permutare (un caz special al acesteia pentru ). $s=2$

Fără pierderea generalității, vom presupune că , deoarece altfel putem pur și simplu înmulți toate permutările fără a modifica valoarea sumei. $\sigma _{1}=\sigma _{0}$ $\sigma _{1}^{-1)$

Dacă cel puțin una dintre permutări este diferită de , atunci pentru aceasta (o notăm cu ) există astfel încât . $\sigma _{1},\dots ,\sigma _{s)$ $\sigma _{0}$ $\sigma _{k)$ $i<j$ $\sigma _{k}(i)>\sigma _{k}(j)$

Apoi, dacă în toate permutările din mulțimea pentru care \sigma (i) > \sigma (j) valorile și sunt interschimbate , atunci valoarea nu va scădea, dar numărul total de inversiuni între ele va deveni mai mic. $\sigma$ $(\sigma _{1},\dots,\sigma _{s})$ $\sigma (i)$ $\sigma (j)$ $V$ $(\sigma _{1},\dots,\sigma _{s})$

Efectuând astfel de acțiuni de numărul necesar (finit) de ori, ajungem la mulțime fără a scădea valoarea lui . $(\sigma _{0},\dots,\sigma _{0})$ $V$

Pentru funcții convexe

Ideea de demonstrație prin corectarea pas cu pas a inversiilor este aplicabilă unei clase mai largi de cazuri decât doar produsul punctual.

Fie o funcție convexă și ordonată în ordine nedescrescătoare. Apoi $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})

Dovada

Prin definiția unei funcții convexe, dacă , atunci , adică . Înlocuind și adăugând la ambele valori , obținem . Cu alte cuvinte, cu cât argumentul este mai mare, cu atât este mai mare înclinarea în sus a funcției și cu atât este mai valoros să adăugați o valoare mai mare acolo pentru a maximiza suma. $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})$

Ca și în dovedirea inegalității obișnuite de permutare, alegem astfel încât . $i<j$ $\sigma (i)>\sigma (j)$

Apoi, așa cum este descris mai sus, . Acest lucru ne permite să efectuăm o inducție similară cu cazul obișnuit. $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)})$

Înmulțind toate valorile cu , putem obține o inegalitate similară, dar cu un semn în direcția opusă, pentru funcțiile concave . $f$ $-unu$

Consecințele

pentru (funcție convexă): inegalitatea obișnuită de permutare pentru mulțimi și $f(x)=e^{x}$ $e^{x_{1)),\dots ,e^{x_{n})$ $e^{y_{1}},\dots ,e^{y_{n}}$

la (funcție convexă): $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})}$

După reducerea ambelor părți cu , obținem din nou inegalitatea obișnuită de permutare. ${\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2)))))$

pentru (funcție concavă): $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})}$

După luarea exponentului din ambele părți: ; $\prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{ i}+y_{i})}$

pentru (funcție concavă): $f(x)={\frac {1}{x}}$ ${\displaystyle \sum \limits _{i=1}^{n}{\frac {1}{x_{i}+y_{\sigma (i)))}\geq \sum \limits _{i=1 }^{n}{\frac {1}{x_{i}+y_{i))))$

Încercări nereușite de generalizare

În 1946, a fost publicată o încercare (Scripta Mathematica 1946, 12(2), 164-169) de a generaliza inegalitatea după cum urmează:

Pentru și două seturi de numere reale și , $n\ge 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)}

dacă numărul de inversiuni în permutare este mai mic decât în permutare . $\pi$ $\sigma$

Cu toate acestea, mai târziu s-a dovedit că această generalizare este valabilă numai pentru . Deoarece există contraexemple pentru această generalizare, cum ar fi: $n=3$ $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.}

Consecințele

Inegalitatea de permutare este interesantă prin faptul că vă permite să combinați intuitiv pe o bază comună inegalități numerice complet diferite, utilizate în diferite domenii ale matematicii.

Această secțiune tratează seturi de numere de lungime și presupune că notația pentru denotă , adică bucle de index. $n$ $x_{i}$ $i>n$ $x_{in)$

Inegalitatea Cauci-Bunyakovsky

Conform inegalității de permutare, pentru orice , . $k$ $\sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{ a_{i}^{2}}$

De aici rezultă un caz special al inegalității Cauci-Bunyakovsky:

\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 \ limite _{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 mod similar, împărțind suma peste toate deplasările posibile ale indicelui dimensional și folosind o generalizare pe mai multe permutări, se obține o inegalitate mai generală pentru numerele întregi : $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}}

Inegalitatea generală Cauci-Bunyakovsky

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}

Dacă valorile și sunt normalizate în așa fel încât , în consecință, se obține inegalitatea Cauchy-Bunyakovsky. Pentru a face acest lucru, este suficient să împărțiți totul la , și totul la . Deoarece inegalitatea Cauci-Bunyakovsky permite astfel de diviziuni fără a schimba adevărul, aceasta dovedește afirmația. $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)))$

Inegalități medii

Patratică și aritmetică

Inegalitatea dintre media patratică și media aritmetică este derivată elementar din cazul particular al inegalității Cauci-Bunyakovsky demonstrat mai sus.

Aritmetică și geometrică

Inegalitatea dintre media aritmetică și geometrică afirmă că

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

Înmulțind ambele părți cu și luând în considerare puterile-lea ale variabilelor, vedem că aceasta este la fel ca $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}

Ultima inegalitate este ușor de obținut din generalizarea inegalității de permutare la mai multe permutări pt $\sigma _{k}(i)=i+(k-1)$

Geometric și armonic

Aducem inegalitatea la aceeași formă ca cea anterioară:

{\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}}}}}

Având în vedere puterile-lea ale variabilelor, obținem $n$

n\stânga({\frac {1}{x_{1)}}\dreapta)\dots \left({\frac {1}{x_{n))}\right)\leq \left({ \frac {1}{x_{1}}}\right)^{n}+\puncte \left({\frac {1}{x_{n}}}\right)^{n}

Ultima inegalitate este ușor de obținut prin aplicarea directă a inegalității de permutare pentru mai multe permutări.

Link -uri

L. V. Radzivilovskiy. Generalizarea inegalității de permutare și a inegalității mongole // Educație matematică . - 2006. - Nr. 10 .
V. I. Murashko, S. M. Gorsky, Ya. I. Sandrygailo. Funcții KφKψ-convexe și generalizări ale inegalităților clasice // PFMT. - 2018. - Emisiune. 37 , nr 4 . — S. 98–102 .
Yue Kwok Choy, Inegalitatea de rearanjare