# Convolutie

Convolutie (samenvouwing) is een wiskundige bewerking, aangeduid door $\,*\,$ (asterisk) of $\,\otimes \,$, op twee functies met als resultaat een nieuwe functie: de convolutie van beide. Synoniem voor convolutie is Duhamel-integraal of -som, Faltung-integraal of -som (Duits: vouwen). Een interpretatie van de convolutie is de transformatie van een van beide functies door de andere. Daarbij is het resultaat de oppervlakte van de overlap van beide functies, waarbij de tweede functie verschuift.
Het voorbeeld in figuur 1 kan men als volgt bekijken:
* De functies $f$ en $g$ zijn blokfuncties met een waarde 1 op het interval $[-0{,}5;0{,}5]$, en de waarde 0 elders.
* Aangezien deze functies symmetrisch zijn rond 0 (met andere woorden: voor elke $x$ geldt dat $f(x)=f(-x)$ en $g(x)=g(-x)$), is de gespiegelde versie van de functie, gelijk aan de functie zelf.
* De functie $g$ wordt dan verschoven met een factor $t$, waarbij $t$ varieert van $-\infty$ tot $+\infty$
* Op het moment dat $t$ gelijk is aan –1, is er nog geen enkele overlap voor beide functies. Immers, de verschuiving van $g$ met een factor $t=-1$ resulteert in een blokfunctie $g$ die een waarde 1 heeft voor alle waarden $\tau$ die voldoen aan $-1{,}5<\tau <-0{,}5$.
* Zodra $t$ echter groter wordt, is er een overlap van beide functies. Deze begint zeer klein, maar wordt maximaal als beide functies elkaar volledig overlappen. Dit is het geval bij $t=0$. Daar is dus ook de gemeenschappelijke oppervlakte het grootst.
* Daarna vermindert de overlap weer, en daalt de functie $f*g$.
Een gelijksoortige analyse kan men geven bij het voorbeeld in figuur 2.

## Voorbeelden
### Kansrekening

Op een druk kruispunt gebeuren elke week wel een of meer ongelukken. Het aantal ongelukken in de komende twee weken is de som van het aantal ongelukken van komende week en van de week daarna. Als de komende twee weken 5 ongelukken zullen gebeuren, kan dat de som zijn van 0 volgende week en 5 de week daarna, of 1 komende week en 4 daarna, of 2+3, 3+2, 4+1 of 5+0. Om de kans te bepalen dat de volgende twee weken 5 ongelukken zullen gebeuren, moeten de kansen op de genoemde mogelijkheden bij elkaar worden opgeteld. Die kans is de convolutie van de kansen van de komende week en van de week daarna.

### Uitleg van figuur 1

In bovenstaande figuur 1 zien we de convolutie van een blokfunctie met zichzelf. De blokfunctie is gedefinieerd als
    $f(x)={\begin{cases}1&{\mbox{als }}|x|\leq {\tfrac {1}{2}}\\\\0&{\mbox{als }}|x|>{\tfrac {1}{2}}\end{cases}}$
Voor de convolutie $f_{conv}$ geldt:
    $f_{\text{conv}}(t)=(f*f)(t)=\int _{-\infty }^{\infty }f(x)f(t-x)\,\mathrm {d} x$
Omdat
    $f(t-x)=0$ voor $x<t-{\tfrac {1}{2}}$ en $x>t+{\tfrac {1}{2}}$
volgt voor $|t|>1$
    $f_{\text{conv}}(t)=0$
Voor $0<t<1$ is
    $f_{\text{conv}}(t)=\int _{t-1/2}^{1/2}1\,\mathrm {d} x={\tfrac {1}{2}}-(t-{\tfrac {1}{2}})=-t+1$
en voor $-1<t<0$
    $f_{\text{conv}}(t)=\int _{-1/2}^{t+1/2}1\,\mathrm {d} x=t+{\tfrac {1}{2}}-(-{\tfrac {1}{2}})=t+1$
De convolutie $f_{\text{conv}}$ is dus een driehoeksfunctie, die getoond wordt in figuur 1.

## Definities

Laat $u$ en $v$ twee rijen getallen zijn, geïndexeerd door gehele getallen. De convolutie van $u$ en $v$, genoteerd $(u*v)(k)$ of $(u\otimes v)(k)$, is een nieuwe getallenrij waarvan de algemene term gegeven wordt door
    $(u*v)(k)=(u\otimes v)(k)=\sum _{i=-\infty }^{\infty }u(i)v(k-i)$
op voorwaarde dat de reekssom absoluut convergeert.
Laat $u$ en $v$ twee meetbare functies zijn op de reële getallen. De convolutie van $u$ en $v$ is een nieuwe functie $u*v$, met als voorschrift
    $(u*v)(t)=\int _{-\infty }^{\infty }u(s)v(t-s)\,\mathrm {d} s$
op voorwaarde dat de integraal bestaat in de absoluut convergente zin van Lebesgue.
Deze bewerking kan als een voortschrijdend gewogen gemiddelde van $u$ gezien worden, met $v$ (of eigenlijk: de spiegeling van $v$) als rij gewichten.

### Opmerking

In minder theoretische teksten wordt de convolutie van de functies $u$ en $v$, op een enigszins verwarrende manier, wel genoteerd als:
    $u(t)*v(t)$
Op de achtergrond speelt daarbij de gedachte dat de expliciete afhankelijkheid van de functies van de onafhankelijke variabele $t$ zichtbaar is.

## Eigenschappen
### Commutativiteit

    $f*g=g*f$

### Associativiteit

    $f*(g*h)=(f*g)*h$

### Distributiviteit

    $f*(g+h)=(f*g)+(f*h)$

### Associativiteit met het scalair vermenigvuldigen

    $a(f*g)=(a\,f)*g=f*(a\,g)$,
met $a$ een willekeurig complex (reëel) getal.

### Afgeleide

    ${\mathcal {D}}(f*g)={\mathcal {D}}f*g=f*{\mathcal {D}}g$,
met ${\mathcal {D}}f$ de afgeleide van $f$ (continu geval) en $({\mathcal {D}}f)(n)=f(n+1)-f(n)$ (discreet geval).

### Convolutiestelling

    ${\mathcal {F}}(f*g)={\sqrt {2\pi }}{\mathcal {F}}(f)\cdot {\mathcal {F}}(g)$,
met ${\mathcal {F}}(f)$ de fourier-getransformeerde van $f$.
Gelijkaardige eigenschappen gelden ook voor de Laplacetransformatie:
    ${\mathcal {L}}[f*g](s)={\mathcal {L}}[f](s)\cdot {\mathcal {L}}[g](s)$
en de Z-transformatie:
    ${\mathcal {Z}}[x*y](z)={\mathcal {Z}}[x](z)\cdot {\mathcal {Z}}[y](z)$

### Inverse

Soms wordt getracht, door zogeheten deconvolutie, uit de convolutie $f\star g$ van een onbekende functie $f$ en een bekende functie $g$, de onbekende $f$ terug te vinden. Dit is echter in lang niet alle gevallen mogelijk.

## Toepassingen
### Regeltechniek

Convolutie wordt onder meer gebruikt in de systeemtheorie, meer bepaald in de regeltechniek. De functies $u$ en $v$ stellen dan signalen voor. Rijen zijn signalen in discrete tijd, functies met reëel domein zijn signalen in continue tijd.
Een lineair tijdsinvariant systeem $S$ gegeven door de impulsantwoord $h$, geeft als output $x$ de convolutie van de impulsrespons met het ingangssignaal $u$:
    $x=h*u$
Deze uitdrukking geldt in de veronderstelling dat alle beginvoorwaarden van het systeem nul zijn (nultoestand).

### Coderingstheorie

In de coderingstheorie wordt bij een convolutiecode uitgegaan van bijvoorbeeld een binair schuifregister, waaraan een rij te coderen bits toegevoerd wordt. De uitvoer van het schuifregister is het te versturen codewoord; deze uitvoer kan worden opgevat als de convolutie van de pulsresponsie met de ingevoerde bitrij. De lengte van een codewoord is de lengte van de inputrij plus het aantal vertragingselementen in het schuifregister.

### Kansrekening

De convolutie vindt ook toepassing in de kansrekening. De kansdichtheid van de som van twee onderling onafhankelijke continue stochastische variabelen is de convolutie van de beide afzonderlijke dichtheden. Ook voor discrete stochastische variabelen geldt een overeenkomstige eigenschap.
De som van twee onafhankelijke continue stochastische variabelen is opnieuw continu, en haar dichtheidsfunctie is de convolutie van de twee afzonderlijke dichtheidsfuncties.
1. De stochastische variabelen $X$ en $Y$ zijn onderling onafhankelijk en beide exponentieel verdeeld met parameter $\lambda$. De kansdichtheid van de som van beide is voor $z>0$:
    $f_{X+Y}(z)=\int _{0}^{z}f_{X}(x)f_{Y}(z-x)\,\mathrm {d} x=\int _{0}^{z}\lambda e^{-\lambda x}\lambda e^{-\lambda (z-x)}\,\mathrm {d} x=\lambda ^{2}ze^{-\lambda z}$
De som $X+Y$ heeft dus een Erlang-verdeling met parameters $\lambda$ en 2.
2. De stochastische variabelen $X$ en $Y$ zijn onderling onafhankelijk en beide Poisson-verdeeld met respectievelijke parameters $\lambda$ en $\mu$. De kansfunctie van de som van beide is voor $n=0,1,\ldots$:
    $P(X+Y=n)=\sum _{k=0}^{n}P(X=k)P(Y=n-k)=\sum _{k=0}^{n}{\frac {\lambda ^{k}}{k!}}e^{-\lambda }{\frac {\mu ^{n-k}}{(n-k)!}}e^{-\mu }={\frac {(\lambda +\mu )^{n}}{n!}}e^{-(\lambda +\mu )}$
De som $X+Y$ heeft dus ook een Poisson-verdeling, maar met parameter $\lambda +\mu$.

## Generalisaties
### Distributies

Door uitbreiding van het begrip partiële integratie wordt de convolutie gedefinieerd op distributies.
De convolutie van een signaal $f(x)$ met een verschoven dirac-impuls $\delta (i-i_{0})$ is:
    $(\delta *v)(k)=\sum _{i=-\infty }^{\infty }\delta (i-i_{0})v(k-i)=v(k-i_{0})$,
want $\delta (i-i_{0})$ is overal nul, behalve voor $i=i_{0}$.
    $(\delta *f)(x)=\int _{-\infty }^{+\infty }\delta (t-t_{0})\cdot f(x-t)\cdot \mathrm {d} t=f(x-t_{0})$, want $\delta (t-t_{0})$ is overal nul, behalve voor $t=t_{0}$, waar geldt dat $\delta (t_{0})=f(t)=f(t_{0})$.
dus telkens een verschuiving.

### Topologische groepen

De natuurlijke thuishaven van de convolutie is die van een lokaal compacte groep $G$ met een linksinvariante maat $\mu$, de zogenaamde Haar-maat. We noteren de groepsbewerking multiplicatief met het symbool $\cdot ,$ bijvoorbeeld $g_{1}\cdot g_{2}$ is het product van $g_{1}$ en $g_{2}.$ Als $u$ en $v$ Haar-integreerbare functies zijn, wordt hun convolutie $u*v$ gedefinieerd door het voorschrift
    $\forall g\in G:(u*v)(g)=\int _{G}u(h)v(g\cdot h^{-1})\,\mathrm {d} \mu (h)$
Bovenstaande definities voor de convolutie van rijen of van reële functies zijn hiervan de speciale gevallen voor de optelgroepen der gehele getallen (met de telmaat) respectievelijk de reële getallen (met de lebesgue-maat).
* ↑ Vergelijk van der Blij, F. en van Tiel, J: Infinitesimaalrekening, Utrecht/Antwerpen 1969, Het Spectrum, p. 380