Ανισότητα της αναδιάταξης

Στα μαθηματικά, η ανισότητα της αναδιάταξης δίνει ότι για κάθε $n$ πραγματικούς αριθμούς $x_1\le x_2\le \dots \le x_n$ και $y_1\le y_2\le \dots \le y_n$ και οποιαδήποτε μετάθεση $\pi :[n]\to [n]$, ισχύει ότιΠρότυπο:RpΠρότυπο:RpΠρότυπο:RpΠρότυπο:Rp

$x_1{y}_1+x_2{y}_2+\dots +x_n{y}_n\ge x_1{y}_{\pi (1)}+x_2{y}_{\pi (2)}+\dots +x_n{y}_{\pi (n)}\ge x_1{y}_n+x_2{y}_{n-1}\dots +x_n{y}_1$.

Ή πιο απλά, το εσωτερικό γινόμενο $x^{T}y$ μεγιστοποιείται όταν $x$ και $y$ έχουν την ίδια διάταξη, και ελαχιστοποιείται όταν έχουν αντίθετη διάταξη.

Η ανισότητα αυτή χρησιμοποιείται για την απόδειξη άλλων βασικών ανισοτήτων, όπως η ανισότητα Κωσύ-Σβαρτς και η ανισότητα αριθμητικού-γεωμετρικού μέσου), καθώς επίσης και σε διάφορες αποδείξεις ορθότητας για άπληστους αλγορίθμους.

Παράδειγμα

Έστω ότι έχουμε $x_1=3,x_2=5,x_3=9$ και $y_1=4,y_2=7,y_3=12$. Από τον παρακάτω πίνακα επιβεβαιώνουμε ότι όταν πάρουμε το άθροισμα των γινομένων με την ίδια διάταξη μεγιστοποιείται το άθροισμα (δίνεται με μπλε χρώμα στον πίνακα), ενώ όταν το πάρουμε με την αντίθετη διάταξη ελαχιστοποιείται (δίνεται με κόκκινο χρώμα).

Μετάθεση $\pi$	Άθροισμα	Αποτέλεσμα
$(123)$	$3\cdot 4+5\cdot 7+9\cdot 12$	$155$
$(132)$	$3\cdot 4+5\cdot 12+9\cdot 7$	$135$
$(213)$	$3\cdot 7+5\cdot 4+9\cdot 12$	$149$
$(231)$	$3\cdot 7+5\cdot 12+9\cdot 4$	$117$
$(312)$	$3\cdot 12+5\cdot 4+9\cdot 7$	$119$
$(321)$	$3\cdot 12+5\cdot 7+9\cdot 4$	$107$

Απόδειξη

Θα αποδείξουμε ότι καμία μετάθεση $\pi$ δεν δίνει μεγαλύτερο άθροισμα από την μετάθεση $\pi =(12\dots n)$. Έστω ότι $\pi$ είναι μία μετάθεση με το μέγιστο άθροισμα. Θα αποδείξουμε ότι δεν μπορούν να υπάρχουν $i>j$ τέτοια ώστε $y_{\pi (i)}<y_{\pi (j)}$. Τότε θεωρούμε την μετάθεση ${\pi }^{\prime }$ που αντιμεταθέτει τους δείκτες $i,j$, δηλαδή ${\pi }^{\prime }(i)=j$ και ${\pi }^{\prime }(j)=i$ και ${\pi }^{\prime }(k)=\pi (k)$ για κάθε $k\ne i,j$.

Τότε το άθροισμα αλλάζει κατά

$\begin{array}{cc}\mathrm{\Delta }& =x_1{y}_{{\pi }^{\prime }(1)}+\dots +x_n{y}_{{\pi }^{\prime }(n)}-(x_1{y}_{\pi (1)}+\dots +x_n{y}_{\pi (n)})\\ & =x_i{y}_{{\pi }^{\prime }(i)}+x_j{y}_{{\pi }^{\prime }(j)}-(x_i{y}_{\pi (i)}+x_j{y}_{\pi (j)})\\ & =x_i{y}_{\pi (j)}+x_j{y}_{\pi (i)}-(x_i{y}_{\pi (i)}+x_j{y}_{\pi (j)})\\ & =x_i(y_{\pi (j)}-y_{\pi (i)})+x_j(y_{\pi (i)}-x_j{y}_{\pi (j)})\\ & =(y_{\pi (j)}-y_{\pi (i)})(x_i-x_j).\end{array}$

Από την υπόθεση ότι $i>j$ (δηλαδή $x_i\ge x_j$) και $y_{\pi (i)}<y_{\pi (j)}$, έχουμε ότι $\mathrm{\Delta }>0$. Επομένως, η μετάθεση ${\pi }^{\prime }$ οδηγεί σε μεγαλύτερο άθροισμα από την $\pi$. Άρα οποιαδήποτε μετάθεση έχει το μέγιστο άθροισμα δεν μπορεί να έχει τέτοια $i,j$ άρα πρέπει να έχει την ίδια διάταξη $x$.

Αντίστοιχα, θεωρώντας την $y{\text{'}}_i=-y_i$, προκύπτει το κάτω φράγμα.

Εφαρμογές

Απόδειξη της ανισότητας Νέσμπιττ

Η ανισότητα Νέσμπιττ λέει ότι για οποιοσδήποτε θετικούς πραγματικούς αριθμούς $a,b,c$,

$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b}\ge \frac{3}{2}.$

Χωρίς βλάβη της γενικότητας, αφού η ανισότητα είναι συμμετρική ως προς τα $a,b,c$ μπορούμε να θεωρήσουμε ότι $a\ge b\ge c$, και επομένως έχουμε ότι $a+b\ge a+c\ge b+c$ και ότι

$\frac{1}{b+c}\ge \frac{1}{a+c}\ge \frac{1}{a+b}.$

Επομένως από την ανισότητα της αναδιάταξης έχουμε ότι

$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b}\ge \frac{b}{b+c}+\frac{c}{a+c}+\frac{a}{a+b},$

και

$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b}\ge \frac{c}{b+c}+\frac{a}{a+c}+\frac{b}{a+b}.$

Αθροίζοντας της δύο ανισότητες, λαμβάνουμε

$2\cdot (\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b})\ge \frac{b+c}{b+c}+\frac{a+c}{a+c}+\frac{a+b}{a+b}=3.$

Τέλος, αναδιατάσσοντας λαμβάνουμε την ζητούμενη.

Απόδειξη της ανισότητας Κωσύ-Σβαρτς

Θα αποδείξουμε την εξής μορφή της ανισότητας Κωσύ-Σβαρτς για $2n$ θετικούς πραγματικούς αριθμούς $a_1,\dots ,a_n$ και $b_1,\dots ,b_n$,

$(a_1^2+\dots +a_n^2)\cdot (b_1^2+\dots +b_n^2)\ge {(a_1{b}_1+\dots +a_n{b}_n)}^2.$

Αναπτύσσοντας τα δύο μέλη έχουμε ότι η ανισότητα είναι ισοδύναμη με την

$\sum _{i=1}^n\sum _{j=1}^n{a}_i^2{b}_i^2\ge \sum _{i=1}^n\sum _{j=1}^n{a}_i{b}_i{a}_j{b}_j.$

Θεωρώντας την ακολουθία με $n^2$ στοιχεία,

$x=(a_1{b}_1,\dots ,a_1{b}_1,a_2{b}_2,\dots ,a_2{b}_2,\dots ,a_n{b}_n,\dots ,a_n{b}_n),$

και την αναδιάταξή της

$y=(a_1{b}_1,\dots ,a_1{b}_n,a_2{b}_1,\dots ,a_2{b}_n,\dots ,a_n{b}_1,\dots ,a_n{b}_n),$

έχουμε ότι από την ανισότητα της αναδιάταξης

$\sum _{i=1}^n\sum _{j=1}^n{a}_i^2{b}_i^2=x^{T}x\ge x^{T}y=\sum _{i=1}^n\sum _{j=1}^n{a}_i{b}_i{a}_j{b}_j,$

αφού $x$ και $y$ δεν έχουν πάντα την ίδια διάταξη, ενώ η $x$ έχει την ίδια διάταξη με τον εαυτό της.

Απόδειξη της ανισότητας αριθμητικού-γεωμετρικού μέσου

Η ανισότητα αριθμητικού-γεωμετρικού μέσου δίνει ότι για κάθε $n$ θετικούς πραγματικούς αριθμούς $a_1,\dots ,a_n$

$\frac{a_1+\dots +a_n}{n}\ge \sqrt[n]{a_1+\dots +a_n}.$

Η ανισότητα αυτή είναι ομογενής, δηλαδή αν θεωρήσουμε $b_i=\lambda a_i$ για οποιαδήποτε σταθερά $\lambda >0$, τότε η μορφή της ανισότητας δεν αλλάζει, δηλαδή,

$\frac{b_1+\dots +b_n}{n}=\frac{\lambda a_1+\dots +\lambda a_n}{n}=\lambda \cdot \frac{a_1+\dots +a_n}{n},$ και $\sqrt[n]{b_1\cdot \dots \cdot b_n}=\sqrt[n]{(\lambda a_1)\cdot \dots \cdot (\lambda a_n)}=\lambda \cdot \sqrt[n]{a_1\cdot \dots \cdot a_n}.$

Επομένως,

$\frac{a_1+\dots +a_n}{n}\ge \sqrt[n]{a_1+\dots +a_n}$ αν και μόνο αν $\frac{b_1+\dots +b_n}{n}\ge \sqrt[n]{b_1+\dots +b_n}$.

Συνεπώς, χωρίς βλάβη της γενικότητας θεωρούμε $a_1\le \dots \le a_n$ με γινόμενο $a_1\cdot \dots \cdot a_n=1$. Θεωρούμε επίσης

$\begin{array}{cc}{x}_1& =a_1,\\ x_2& =a_1{a}_2,\\ & ⋮\\ x_n& =a_1\cdots \dots \cdot a_n=1.\end{array}$

Από την ανισότητα της αναδιάταξης

$a_1+\dots +a_n=\frac{x_1}{x_n}+\frac{x_2}{x_1}+\dots +\frac{x_n}{x_{n-1}}\ge \frac{x_1}{x_1}+\dots +\frac{x_n}{x_n}=n$.

Δηλαδή,

$\frac{a_1+\dots +a_n}{n}\ge 1=\sqrt[n]{a_1\cdot \dots \cdot a_n}.$

Εφαρμογή σε πρόβλημα βελτιστοποίησης

Έστω ότι θέλουμε να τοποθετήσουμε $n$ ανεμογεννήτριες με αποδόσεις ${\eta }_1,\dots ,{\eta }_n$ σε $n$ πιθανές θέσεις με ροή ανέμου $r_1,\dots ,r_n$. Αν τοποθετήσουμε την $i$-οστή ανεμογεννήτρια στην $j$-οστή θέση τότε λαμβάνουμε ${\eta }_i\cdot r_j$ ενέργεια. Πώς πρέπει να βάλουμε τις ανεμογεννήτριες στις θέσεις που έχουμε ώστε να μεγιστοποιήσουμε την συνολική ενέργεια που θα λάβουμε;

Πρέπει να βρούμε την μετάθεση $\pi$, ώστε να μεγιστοποιήσουμε το άθροισμα,

$\sum _{i=1}^n{\eta }_i\cdot r_{\pi (i)}.$

Από την ανισότητα της αναδιάταξης, το άθροισμα μεγιστοποιείται όταν η $\pi$ έχει την ίδια διάταξη με την $\eta$, που οδηγεί στον απλό αλγόριθμο: τοποθετούμε την ανεμογεννήτρια με την μέγιστη απόδοση στην θέση με την μέγιστη ροή, μετά την ανεμογεννήτρια με την δεύτερη μέγιστη απόδοση στην θέση με την δεύτερη μέγιστη ροή, κ.ο.κ.