Faltungs-Rechner

(a * b)[k] = Σᵢ a[i] × b[k − i] Länge = m + n − 1

a, b

Die beiden Folgen, als Zahlen mit Semikolon getrennt eingetippt. Ihre Reihenfolge spielt keine Rolle — die Faltung ist kommutativ, ein Vertauschen der beiden Felder liefert also dasselbe Ergebnis. Sie müssen nicht gleich lang sein und dürfen Dezimalzahlen oder negative Werte enthalten. Jedes Feld nimmt bis zu zweihundert Glieder auf.

k

Der Index des Eintrags, der gerade entsteht, von 0 bis zur Länge des Ergebnisses minus eins. Er wird nicht neben jeden Wert geschrieben, weil eine durch Kommas getrennte Reihe bereits eine Reihenfolge hat: Die erste Zahl ist k = 0, die zweite ist k = 1. Die Referenztabelle unten schreibt die Indizes für das voreingestellte Paar einzeln hin — dort ist die Stelle, an der man nachsieht, wenn die Positionen das sind, was geprüft werden soll.

a[i] × b[k − i]

Ein Produkt in der Summe. Für jedes k läuft der Index i über jede Position, an der beide Folgen ein Glied haben; die Anzahl der addierten Produkte steigt deshalb von eins an den Enden auf die Länge der kürzeren Folge in der Mitte. Das Muster der Überlappung ist der ganze Gedanke: Eine Folge gleitet an der anderen vorbei, und die Produkte werden Spalte für Spalte eingesammelt. Man nennt das eine gleitende Summe, weil dasselbe Fenster über die ganze Reihe wandert.

Σᵢ

Die Summe über diese Produkte, also ein Eintrag des Ergebnisses. Jeder Eintrag wird auf sechs Nachkommastellen gerundet, und die daneben angegebene Gesamtsumme ist die Summe dieser gerundeten Einträge und nicht der ungerundeten — wer die auf dem Panel gedruckten Zahlen addiert, erhält deshalb genau die gedruckte Gesamtsumme.

m + n − 1

Die Länge des Ergebnisses, die selbst als eigener Wert ausgegeben wird. Zwei Folgen mit je drei Gliedern ergeben fünf Einträge; eine einzelne Zahl, mit einer dreigliedrigen Folge gefaltet, ergibt drei. Die Einträge über die längere der beiden Folgen hinaus sind der Grund, warum dies die volle Faltung ist und nicht die Art, die nur den Teil behält, in dem sich die Folgen vollständig überlappen.

Nehmen Sie diese Seite, wenn zwei Folgen zu einer Verteilung verknüpft werden sollen: die Anzahl der Weisen, auf die zwei Würfel jede Augensumme treffen, die Wirkung eines Fensters auf eine Reihe, die Koeffizienten eines Produkts zweier Polynome. Ein gleitender Mittelwert ist genau eine solche Faltung, und beide Begriffe greifen hier ineinander. Wenn die Frage dagegen eine einzelne Folge für sich betrifft — ihre Glieder, ihre Summe, ihr Muster —, deckt das die Seite zum Folgen-Rechner ab, und wer das Fenster eines gleitenden Mittelwerts wählt, ist bei der Seite zum Durchschnitts-Rechner richtig.

1. Eins, zwei, drei gegen vier, fünf, sechs

   1. k = 0: Nur die ersten Glieder überlappen sich, also 1 × 4 = 4
   2. k = 1: 1 × 5 + 2 × 4 = 5 + 8 = 13
   3. k = 2: 1 × 6 + 2 × 5 + 3 × 4 = 6 + 10 + 12 = 28
   4. k = 3: 2 × 6 + 3 × 5 = 12 + 15 = 27
   5. k = 4: Nur die letzten Glieder überlappen sich, 3 × 6 = 18
   6. Das Ergebnis ist 4, 13, 28, 27, 18, und seine Summe ist 90, also auch 6 × 15

   Die letzte Zeile ist die Kontrolle, die diese Seite leicht zu glauben macht: Die Summe einer Faltung ist immer das Produkt der beiden Folgensummen, hier 1 + 2 + 3 = 6 gegen 4 + 5 + 6 = 15. Das fällt aus der Algebra heraus, weil jedes Produkt im Ergebnis ein Produkt aus je einem Glied der beiden Folgen ist und jedes solche Paar genau einmal vorkommt.

2. Zwei Würfel und die Form ihrer Augensummen

   1. Ein Würfel hat für jede seiner sechs Seiten genau eine Möglichkeit, also besteht jede Folge aus sechs Einsen
   2. Sie zu falten zählt die Paare, die auf jede Summe kommen: k = 0 ergibt 1 × 1 = 1 Möglichkeit für die Augensumme 2
   3. k = 1 ergibt 1 + 1 = 2 Möglichkeiten für die Augensumme 3, und die Anzahl steigt weiter
   4. Der Höhepunkt ist 6, in der Mitte, und das ist die Augensumme 7
   5. Das Ergebnis ist 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, und seine Summe ist 36

   Das ist der Zentraler Grenzwertsatz im Kleinen: Zwei flache Verteilungen ergeben gefaltet eine dreieckige, und ein dritter Würfel würde sie weiter zur Glockenform runden. Die Gesamtsumme 36 ist zugleich die Kontrolle — das Produkt der beiden Folgensummen ist 6 × 6, also jedes geordnete Paar von Seiten, ein Ausgang für jedes Paar.

3. Eine einzelne Zahl skaliert die ganze Folge

   1. Eine Folge aus einem einzigen Glied hat nichts, womit sie sich überlappen könnte, jeder Eintrag des Ergebnisses ist also dieses Glied mal einem Glied der anderen Folge
   2. k = 0: 2 × 1 = 2
   3. k = 1: 2 × 2 = 4
   4. k = 2: 2 × 3 = 6
   5. Das Ergebnis ist 2, 4, 6, und die Summe ist 12, also 2 × 6

   Der entartete Fall lohnt sich einmal, weil er zeigt, dass das Bild vom Verschieben ein Ende hat: Ist eine Folge nur ein Glied lang, gibt es nie mehr als ein Produkt zu addieren, und die Faltung fällt auf eine Multiplikation zusammen. Aus demselben Grund liefert die Längenformel m + n − 1 hier 1 + 3 − 1 = 3 und nichts Größeres.

Diese Seite rechnet die volle Faltung und nur die volle Faltung. Die beiden Varianten, die nur einen Teil des Ergebnisses behalten, werden nicht angeboten: die eine, die eine Folge in der Länge der längeren Eingabe zurückgibt, und die andere, die nur die Positionen zurückgibt, an denen sich die Folgen vollständig überlappen. Keine von beiden ist für zwei Folgen gerader Länge sauber definiert, und das volle Ergebnis ist das, was sie beide enthält — die kürzeren Varianten sind Ausschnitte daraus und keine anderen Rechnungen. Jede Folge darf höchstens zweihundert Glieder enthalten, und jeder Wert ist auf einen Betrag von 1.000.000 begrenzt; das ist eine Grenze der Anzeige, denn eine Faltung multipliziert erst und addiert dann, große Einträge laufen also lange vor dem Überlauf einer Gleitkommazahl aus dem lesbaren Bereich. Jeder Eintrag des Ergebnisses wird auf sechs Nachkommastellen gerundet, und die angegebene Gesamtsumme ist die Summe der gerundeten Einträge, sodass das Addieren der gedruckten Zahlen von Hand die gedruckte Gesamtsumme reproduziert statt einer leicht abweichenden. Das Ergebnis ist eine durch Kommas getrennte Zahlenreihe und wird nicht lokalisiert: Das Komma trennt dort die Glieder und ist kein Dezimaltrenner, und der Dezimaltrenner innerhalb einer Zahl bleibt ein Punkt, in welcher Sprache die Seite auch gelesen wird. Die Positionen tragen die Indizes und sind nicht einzeln beschriftet; die Referenztabelle gibt die Indizes für das voreingestellte Paar ausdrücklich an.

Wie faltet man zwei Folgen von Hand?

Man lässt die eine Folge an der anderen vorbeigleiten und addiert an jeder Lage die Produkte. Bei 1, 2, 3 gegen 4, 5, 6 ist der erste Eintrag 1 × 4 = 4, der zweite ist 1 × 5 + 2 × 4 = 13, und so weiter bis 3 × 6 = 18 am anderen Ende. Die Faltung hat fünf Einträge, weil zwei dreigliedrige Folgen auf die Länge 3 + 3 − 1 kommen.

Wie prüfe ich, ob eine Faltung stimmt?

Man addiert das Ergebnis und vergleicht es mit dem Produkt der beiden Folgensummen. Bei 1, 2, 3 gegen 4, 5, 6 steht 90 gegen 6 × 15, und beide müssen übereinstimmen. Der Grund ist, dass jeder Eintrag des Ergebnisses eine Summe paarweiser Produkte ist und jedes mögliche Paar aus den beiden Folgen in genau einer dieser Summen vorkommt.

Warum hat das Ergebnis mehr Einträge als jede der beiden Folgen?

Weil die volle Faltung auch die Positionen behält, an denen sich die Folgen nur teilweise überlappen. Bei 1, 2, 3 gegen 4, 5, 6 sind das fünf Positionen: an jedem Ende eine, an der ein einzelnes Paar zusammentrifft, und drei in der Mitte, an denen es mehrere sind. Die beiden kürzeren Varianten der Operation — die mit der Länge der längeren Eingabe und die, die nur vollständige Überlappungen behält — sind beide Ausschnitte aus diesem Ergebnis.

Was hat das Falten zweier Würfel mit Wahrscheinlichkeit zu tun?

Es zählt die Ausgänge. Ein einzelner Würfel ist eine Folge aus sechs Einsen, eine je Seite, und diese Folge mit sich selbst gefaltet zählt die geordneten Paare, die jede Augensumme ergeben: eine Weise für die 2, zwei Weisen für die 3, ansteigend auf sechs Weisen für die 7 und danach wieder fallend. Die Gesamtsumme des Ergebnisses, 36, ist die Anzahl der geordneten Paare — teilt man jeden Eintrag dadurch, erhält man die Wahrscheinlichkeit.

Ist ein gleitender Mittelwert eine Faltung?

Ja. Ein gleitender Mittelwert nimmt ein Fenster gleicher Gewichte — etwa fünf Tage mit je einem Fünftel — und schiebt es über die Reihe, und genau das ist die Faltung mit diesem Fenster als einer der beiden Folgen. Deshalb taucht die Operation beim Glätten, bei Filtern und in der Bildverarbeitung auf: Das Verschobene ist eine Menge von Gewichten, das Geglättete die Folge.

• Convolution — the definition, the sum over overlapping products, and the length of the result — Wolfram MathWorld (United States)
• Cauchy Product — the same rule applied to the coefficients of two power series, which is what convolving two polynomial coefficient lists computes — Wolfram MathWorld (United States)
• Faltung — der Eintrag im deutschen Wörterbuch, der die Schreibweise und die Herkunft des Wortes belegt — DWDS (Deutschland)