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

Στα μαθηματικά, η **ανισότητα της αναδιάταξης** δίνει ότι για κάθε n πραγματικούς αριθμούς x_1 \leq x_2 \leq \ldots \leq x_n και y_1 \leq y_2 \leq \ldots \leq y_n και οποιαδήποτε μετάθεση \pi \colon [n] \to [n], ισχύει ότι
:x_1 y_1 + x_2 y_2 + \ldots + x_n y_n \geq x_1 y_{\pi(1)} + x_2 y_{\pi(2)} + \ldots + x_n y_{\pi(n)} \geq x_1y_n + x_2 y_{n-1} \ldots + 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 δεν δίνει μεγαλύτερο άθροισμα από την μετάθεση \pi = (1 \; 2 \; \ldots \; n). Έστω ότι \pi είναι μία μετάθεση με το μέγιστο άθροισμα. Θα αποδείξουμε ότι δεν μπορούν να υπάρχουν i > j τέτοια ώστε y_{\pi(i)} . Τότε θεωρούμε την μετάθεση \pi' που αντιμεταθέτει τους δείκτες i, j, δηλαδή \pi'(i) = j και \pi'(j) = i και \pi'(k) = \pi(k) για κάθε k \neq i, j.

Τότε το άθροισμα αλλάζει κατά
:
\begin{align}
\Delta & =  x_1 y_{\pi'(1)} + \ldots + x_n y_{\pi'(n)} - (x_1 y_{\pi(1)} + \ldots + x_n y_{\pi(n)}) \\
& = x_i y_{\pi'(i)} + x_j y_{\pi'(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{align}

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

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

## Εφαρμογές

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

Η ανισότητα Νέσμπιττ λέει ότι για οποιοσδήποτε θετικούς πραγματικούς αριθμούς a, b, c,
:
\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} \geq \frac{3}{2}.


Χωρίς βλάβη της γενικότητας, αφού η ανισότητα είναι συμμετρική ως προς τα a, b, c μπορούμε να θεωρήσουμε ότι a \geq b \geq c, και επομένως έχουμε ότι a + b \geq a + c \geq b + c και ότι
:
\frac{1}{b + c} \geq \frac{1}{a + c} \geq \frac{1}{a + b}.

Επομένως από την ανισότητα της αναδιάταξης έχουμε ότι 
:
\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} \geq \frac{b}{b + c} + \frac{c}{a + c} + \frac{a}{a + b},
και 
:
\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} \geq \frac{c}{b + c} + \frac{a}{a + c} + \frac{b}{a + b}.

Αθροίζοντας της δύο ανισότητες, λαμβάνουμε
:
2 \cdot \left( \frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} \right) \geq \frac{b + c}{b + c} + \frac{a + c}{a + c} + \frac{a + b}{a + b} = 3.

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

### Απόδειξη της ανισότητας Κωσύ-Σβαρτς
Θα αποδείξουμε την εξής μορφή της ανισότητας Κωσύ-Σβαρτς για 2n θετικούς πραγματικούς αριθμούς a_1, \ldots, a_n και b_1, \ldots, b_n,
:
\left(a_1^2 + \ldots + a_n^2\right) \cdot \left(b_1^2 + \ldots + b_n^2\right) \geq \left( a_1b_1 + \ldots + a_n b_n\right)^2.

Αναπτύσσοντας τα δύο μέλη έχουμε ότι η ανισότητα είναι ισοδύναμη με την 
:
\sum_{i = 1}^n \sum_{j = 1}^n a_i^2 b_i^2 \geq \sum_{i = 1}^n \sum_{j = 1}^n a_ib_i a_jb_j.

Θεωρώντας την ακολουθία με n^2 στοιχεία,
:
x = \left(a_1 b_1, \ldots , a_1b_1, a_2b_2, \ldots, a_2b_2, \ldots , a_nb_n, \ldots, a_nb_n\right),

και την αναδιάταξή της
:
y = \left(a_1 b_1, \ldots , a_1b_n, a_2b_1, \ldots, a_2b_n, \ldots , a_nb_1, \ldots, a_nb_n\right),

έχουμε ότι από την ανισότητα της αναδιάταξης 
:
\sum_{i = 1}^n \sum_{j = 1}^n a_i^2 b_i^2 = x^T x \geq x^T y = \sum_{i = 1}^n \sum_{j = 1}^n a_ib_i a_jb_j,

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

### Απόδειξη της ανισότητας αριθμητικού-γεωμετρικού μέσου
Η ανισότητα αριθμητικού-γεωμετρικού μέσου δίνει ότι για κάθε n θετικούς πραγματικούς αριθμούς a_1, \ldots, a_n
:
\frac{a_1 + \ldots + a_n}{n} \geq \sqrt[n]{a_1 + \ldots + a_n}.

Η ανισότητα αυτή είναι ομογενής, δηλαδή αν θεωρήσουμε b_i = \lambda a_i για οποιαδήποτε σταθερά \lambda > 0, τότε η μορφή της ανισότητας δεν αλλάζει, δηλαδή, 
:
\frac{b_1 + \ldots + b_n}{n} = \frac{\lambda a_1 + \ldots + \lambda a_n}{n} = \lambda \cdot \frac{a_1 + \ldots + a_n}{n},\quad και \quad \sqrt[n]{b_1 \cdot \ldots \cdot b_n} = \sqrt[n]{(\lambda a_1) \cdot \ldots \cdot (\lambda a_n)} = \lambda \cdot \sqrt[n]{a_1 \cdot \ldots \cdot a_n}.
Επομένως, 
:\frac{a_1 + \ldots + a_n}{n} \geq \sqrt[n]{a_1 + \ldots + a_n} αν και μόνο αν \frac{b_1 + \ldots + b_n}{n} \geq \sqrt[n]{b_1 + \ldots + b_n}.
Συνεπώς, χωρίς βλάβη της γενικότητας θεωρούμε a_1 \leq \ldots \leq a_n με γινόμενο a_1 \cdot \ldots \cdot a_n = 1. Θεωρούμε επίσης 
:
\begin{align}
x_1 & = a_1, \\
x_2 & = a_1 a_2, \\
 & \vdots \\
x_n & = a_1 \cdots \ldots \cdot a_n = 1.
\end{align}

Από την ανισότητα της αναδιάταξης
:
a_1 + \ldots + a_n = \frac{x_1}{x_n} + \frac{x_2}{x_1} + \ldots + \frac{x_n}{x_{n-1}} \geq \frac{x_1}{x_1} + \ldots + \frac{x_n}{x_n} = n.
Δηλαδή,
:
\frac{a_1 + \ldots + a_n}{n} \geq 1 = \sqrt[n]{a_1 \cdot \ldots \cdot a_n}.


### Εφαρμογή σε πρόβλημα βελτιστοποίησης
Έστω ότι θέλουμε να τοποθετήσουμε n ανεμογεννήτριες με αποδόσεις \eta_1, \ldots, \eta_n σε n πιθανές θέσεις με ροή ανέμου r_1, \ldots , r_n. Αν τοποθετήσουμε την i-οστή ανεμογεννήτρια στην j-οστή θέση τότε λαμβάνουμε \eta_i \cdot r_j ενέργεια. Πώς πρέπει να βάλουμε τις ανεμογεννήτριες στις θέσεις που έχουμε ώστε να μεγιστοποιήσουμε την συνολική ενέργεια που θα λάβουμε; 

Πρέπει να βρούμε την μετάθεση \pi, ώστε να μεγιστοποιήσουμε το άθροισμα,
:\sum_{i = 1}^n \eta_i \cdot r_{\pi(i)}.
Από την ανισότητα της αναδιάταξης, το άθροισμα μεγιστοποιείται όταν η \pi έχει την ίδια διάταξη με την \eta, που οδηγεί στον απλό αλγόριθμο: τοποθετούμε την ανεμογεννήτρια με την μέγιστη απόδοση στην θέση με την μέγιστη ροή, μετά την ανεμογεννήτρια με την δεύτερη μέγιστη απόδοση στην θέση με την δεύτερη μέγιστη ροή, κ.ο.κ.

## Παραπομπές


Κατηγορία:Ανισότητες