Summenpermutation, Verstaendnisproblem

03.03.2007, 17:52

Crock

Summenpermutation, Verstaendnisproblem

Moin, die Informatiker unter euch kennen bestimmt TeX-Erfinder Donald E. Knuth und seine Buecherreihe "The Art of Computer Programming". Nun ja, ich lese die gerade, und in seinen mathematischen "Basic Concepts" stosse ich auf ein Verstaendnisproblem. Hier der Auszug:

Zitat:

We frequently need to interchange the summation order [also] in a more general situatuion, where the relation $\begin{eqnarray*} S(j) \end{eqnarray*}$ depends in i as well as j. In such a case we can denote the relation by $\begin{eqnarray*} S(i,j) \end{eqnarray*}$ . The interchange of summation can always be carried out, in theory at leas, as follow:

$\begin{eqnarray*} \sum\limits_{R(i)}\sum\limits_{S(i,j)}a_{ij}=\sum\limits_{S'(j)}\sum\limits_{R'(i,j)}a_{ij} \end{eqnarray*}$

where $\begin{eqnarray*} S'(j) \end{eqnarray*}$ is the relation "there is an integer i such that both $\begin{eqnarray*} R(i) \end{eqnarray*}$ and $\begin{eqnarray*} S(i,j) \end{eqnarray*}$ are true"; and $\begin{eqnarray*} R'(i,j) \end{eqnarray*}$ is the relation "both $\begin{eqnarray*} R(i) \end{eqnarray*}$ and $\begin{eqnarray*} S(i,j) \end{eqnarray*}$ are true". For exampe, if the summation is $\begin{eqnarray*} \sum_{i=1}^{n}\sum_{j=1}^{i}a_{ij} \end{eqnarray*}$ , then $\begin{eqnarray*} S'(j) \end{eqnarray*}$ is the relation "there is an integer i such that $\begin{eqnarray*} 1 \le i \le n \end{eqnarray*}$ and $\begin{eqnarray*} 1 \le j \le i \end{eqnarray*}$ ", that is, $\begin{eqnarray*} j \le i \le n \end{eqnarray*}$ . Thus,

$\begin{eqnarray*} \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}a_{ij}=\sum\limits_{j=1}^{n}\sum\limits_{i=j}^{n}a_{ij} \end{eqnarray*}$

Ich verstehe ehrlichgesagt, nicht einmal die allgemeine Formel, noch kann ich das konkrete Beispiel nachvollziehen. Ist das wieder was simples extrem kompliziert (so, wie der Knuth schon mal ueber eine halbe Seite erzaehlt hat, wie man rausfindet, ob ein String ein einem anderen vorkommt?) Bitte um Hilfe.

03.03.2007, 18:44

Leopold

Auf diesen Beitrag antworten »

Hier geht es darum, über welchen der Indizes $\begin{eqnarray*} i,j \end{eqnarray*}$ als erstes (äußere Summe) und über welchen als zweites (innere Summe) summiert wird. Und die innere Summe hängt eben von der äußeren ab. Das ist sozusagen das diskrete Analogon des Satzes von Fubini (mehrdimensionale Integralrechnung).

Im Beispiel ist ein dreieckiges Schema vorgegeben. Die $\begin{eqnarray*} a_{ij} \end{eqnarray*}$ sind irgendwelche addierbaren Objekte (wobei natürlich Kommutativ- und Assoziativgesetz unterstellt werden). Wenn man sich $\begin{eqnarray*} i \in \left\{ 1,2,\ldots,n \right\} \end{eqnarray*}$ als erstes vorgibt, dann gibt es zu diesem fest gewählten $\begin{eqnarray*} i \end{eqnarray*}$ die $\begin{eqnarray*} j \end{eqnarray*}$ -Werte $\begin{eqnarray*} \left\{ 1,2,\ldots,i \right\} \end{eqnarray*}$ . Am besten stellst du dir das als Matrix vor. $\begin{eqnarray*} i \end{eqnarray*}$ gibt den Zeilenindex, $\begin{eqnarray*} j \end{eqnarray*}$ den Spaltenindex an:

$\begin{eqnarray*} \begin{matrix} a_{11} & & & & \\ a_{21} & a_{22} & & & \\ a_{31} & a_{32} & a_{33} & & \\ \vdots & \vdots & \vdots & & \\ a_{n1} & a_{n2} & a_{n3} & \ldots & a_{nn} \end{matrix} \end{eqnarray*}$

Du kannst nun diese Elemente zeilenweise addieren:

$\begin{eqnarray*} \left( a_{11} \right) + \left( a_{21} + a_{22} \right) + \left( a_{31} + a_{32} + a_{33} \right) + \ldots \end{eqnarray*}$

Wenn du dir eine Klammer oben vornimmst, siehst du, daß der Index $\begin{eqnarray*} i \end{eqnarray*}$ sich dabei nicht verändert, der Index $\begin{eqnarray*} j \end{eqnarray*}$ aber von 1 bis $\begin{eqnarray*} i \end{eqnarray*}$ durchläuft, z.B. die dritte Klammer ( $\begin{eqnarray*} i=3 \end{eqnarray*}$ ):

$\begin{eqnarray*} a_{31} + a_{32} + a_{33} = \sum_{j=1}^3~a_{3j} \end{eqnarray*}$

Und jetzt mußt du alle diese Klammern addieren:

$\begin{eqnarray*} \sum_{j=1}^1~a_{1j} + \sum_{j=1}^2~a_{2j} + \sum_{j=1}^3~a_{3j} + \ldots \end{eqnarray*}$

Und wenn du die Glieder dieser großen Summe anschaust, sehen die ja alle ähnlich aus. Nur die obere Summationsgrenze und der erste Index ändern sich. Das kann man kürzer schreiben:

$\begin{eqnarray*} \sum_{i=1}^n~\sum_{j=1}^i~a_{ij} \end{eqnarray*}$

Jetzt der andere Fall, die Summation nach Spalten. Schau dir zunächst noch einmal das obige dreieckige Schema an. Dann geht es los:

$\begin{eqnarray*} \left( a_{11} + a_{21} + a_{31} + \ldots \right) + \left( a_{22} + a_{32} + \ldots \right) + \left( a_{33} + \ldots \right) + \ldots \end{eqnarray*}$

In jeder Klammer bleibt hier der Index $\begin{eqnarray*} j \end{eqnarray*}$ unverändert, während $\begin{eqnarray*} i \end{eqnarray*}$ von $\begin{eqnarray*} j \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ läuft, z.B. die zweite Klammer:

$\begin{eqnarray*} a_{22} + a_{32} + \ldots = \sum_{i=2}^n~a_{i2} \end{eqnarray*}$

Und die Addition aller dieser Klammern sieht dann so aus:

$\begin{eqnarray*} \sum_{i=1}^n~a_{i1} + \sum_{i=2}^n~a_{i2} + \sum_{i=3}^n~a_{i3} + \ldots \end{eqnarray*}$

Das kann man wieder kürzer so schreiben:

$\begin{eqnarray*} \sum_{j=1}^n~\sum_{i=j}^n~a_{ij} \end{eqnarray*}$

Da die Summation nach Zeilen oder nach Spalten aber dasselbe liefert, folgt:

$\begin{eqnarray*} \sum_{i=1}^n~\sum_{j=1}^i~a_{ij} = \sum_{j=1}^n~\sum_{i=j}^n~a_{ij} \end{eqnarray*}$

03.03.2007, 18:51

Tobias

Auf diesen Beitrag antworten »

Ok, also es geht darum zwei Summen zu vertauschen. Wenn die Summenindizes unabhängig voneinander sind, kann man einfach die Summen vertauschen. Das folgt sofort aus dem Kommutativgesetz:

$\begin{eqnarray*} \sum_{i=1}^n \sum_{j=1}^{n} a_{ij} = \sum_{j=1}^n \sum_{i=1}^{n} a_{ij} \end{eqnarray*}$

Nun kann es aber sein, dass der Index der inneren Summe von dem Index der äußeren Summe abhängig ist. Das beschreibt Knuth mit den Relationen:

Die äußere Summe laufe über alle i, die die Relation R(i) erfüllen. Z.B. $\begin{eqnarray*} R(i) \equiv 1 \leq i \leq n \end{eqnarray*}$ .

Die innere Summe laufe über alle j, die eine Relation S(i, j) erfüllen und i ist der Summationsindex der äußeren Summe. Z.B. $\begin{eqnarray*} S(i, j) \equiv i \leq j \leq n \end{eqnarray*}$ .

Würde man hier die Summen stumpf umdrehen, müsse man über alle j summieren, die S(i, j) erfüllen, aber ohne i zu kennen. Das geht also nicht. Knuth sucht eine Modifikation von S(i, j) zu S'(j) so, dass S'(j) nur noch von j abhängig ist. (In der Prädikatenlogik würde das bedeuten, dass nur j eine freie Variable ist.) Gleichzeitig müssen aber die Summanden gleichbleiben, wenn auch in einer anderen Reihenfolge.

Wir binden die freie Variable i in S(i, j) mit einem Existenz-Quantor.

$\begin{eqnarray*} S'(j) \equiv \exists i \; : \; S(i, j) \wedge R(i) \end{eqnarray*}$
Wenn es ein i gibt, das sowohl S(i, j) als auch R(i) wahr macht, dann wird das ausgewählte j auf jeden Fall in der Summe vorkommen.

Nun muss in der zweiten Summe nur noch über allen i summiert werden, für die S(i, j) und R(i) wahr wird. Das es mindestens so ein i gibt, ist schon durch S'(j) festgelegt. D.h. der Index i wird nun von j abhängig.
$\begin{eqnarray*} R'(i, j) \equiv R(i) \wedge S(i, j) \end{eqnarray*}$

03.03.2007, 18:54

Crock

Auf diesen Beitrag antworten »

Vielen vielen Dank an euch beide!
Der Groschen ist gefallen.

03.03.2007, 18:55

Leopold

Auf diesen Beitrag antworten »

Na super, jetzt hat Crock ja eine konkrete (Leopold) und eine allgemeine (Tobias) Beschreibung des Sachverhalts. smile

EDIT
Und wenn Crock Lust hat, kann er ja im Beispiel einmal die Summation weder nach Zeilen noch nach Spalten, sondern "nach Schrägen" durchführen. Wie müßte man das kurz notieren?

Neue Frage »

Antworten »

Summenpermutation, Verstaendnisproblem

Verwandte Themen