diff options
author | Prefetch | 2023-10-21 14:21:59 +0200 |
---|---|---|
committer | Prefetch | 2023-10-21 14:21:59 +0200 |
commit | bd13537ee2fb704b02b961b5d06dd4f406f19a71 (patch) | |
tree | 03b525ead00b8b6ae46af8f5f6eee67dab713a27 /source/know/concept/convolution-theorem | |
parent | fc85814ec669f8158179e8ed16ff45d73e236dac (diff) |
Improve knowledge base
Diffstat (limited to 'source/know/concept/convolution-theorem')
-rw-r--r-- | source/know/concept/convolution-theorem/index.md | 77 |
1 files changed, 44 insertions, 33 deletions
diff --git a/source/know/concept/convolution-theorem/index.md b/source/know/concept/convolution-theorem/index.md index d10d85d..3f9eafb 100644 --- a/source/know/concept/convolution-theorem/index.md +++ b/source/know/concept/convolution-theorem/index.md @@ -7,54 +7,59 @@ categories: layout: "concept" --- -The **convolution theorem** states that a convolution in the direct domain -is equal to a product in the frequency domain. This is especially useful -for computation, replacing an $$\mathcal{O}(n^2)$$ convolution with an -$$\mathcal{O}(n \log(n))$$ transform and product. +The **convolution theorem** states that a convolution in the real domain +is equal to a product in the frequency domain. +This fact is especially useful for computation, +as it allows replacing an $$\mathcal{O}(n^2)$$ convolution +with an $$\mathcal{O}(n \log(n))$$ transform and product. ## Fourier transform -The convolution theorem is usually expressed as follows, where -$$\hat{\mathcal{F}}$$ is the [Fourier transform](/know/concept/fourier-transform/), -and $$A$$ and $$B$$ are constants from its definition: +The convolution theorem is usually expressed as follows, +where $$\hat{\mathcal{F}}$$ is the [Fourier transform](/know/concept/fourier-transform/), +and $$A$$ and $$B$$ are the constants from its definition: $$\begin{aligned} \boxed{ \begin{aligned} - A \cdot (f * g)(x) &= \hat{\mathcal{F}}{}^{-1}\{\tilde{f}(k) \: \tilde{g}(k)\} \\ - B \cdot (\tilde{f} * \tilde{g})(k) &= \hat{\mathcal{F}}\{f(x) \: g(x)\} + A \cdot (f * g)(x) + &= \hat{\mathcal{F}}{}^{-1}\Big\{ \tilde{f}(k) \: \tilde{g}(k) \Big\} + \\ + B \cdot (\tilde{f} * \tilde{g})(k) + &= \hat{\mathcal{F}}\Big\{ f(x) \: g(x) \Big\} \end{aligned} } \end{aligned}$$ {% include proof/start.html id="proof-fourier" -%} -We expand the right-hand side of the theorem and -rearrange the integrals: +We expand the right-hand side of the theorem and rearrange the integrals: $$\begin{aligned} - \hat{\mathcal{F}}{}^{-1}\{\tilde{f}(k) \: \tilde{g}(k)\} - &= B \int_{-\infty}^\infty \tilde{f}(k) \Big( A \int_{-\infty}^\infty g(x') \: e^{i s k x'} \dd{x'} \Big) e^{-i s k x} \dd{k} + \hat{\mathcal{F}}{}^{-1}\Big\{ \tilde{f}(k) \: \tilde{g}(k) \Big\} + &= B \int_{-\infty}^\infty \tilde{f}(k) \bigg( A \int_{-\infty}^\infty g(x') \: e^{i s k x'} \dd{x'} \bigg) e^{-i s k x} \dd{k} \\ - &= A \int_{-\infty}^\infty g(x') \Big( B \int_{-\infty}^\infty \tilde{f}(k) \: e^{-i s k (x - x')} \dd{k} \Big) \dd{x'} + &= A \int_{-\infty}^\infty g(x') \bigg( B \int_{-\infty}^\infty \tilde{f}(k) \: e^{-i s k (x - x')} \dd{k} \bigg) \dd{x'} \\ &= A \int_{-\infty}^\infty g(x') \: f(x - x') \dd{x'} - = A \cdot (f * g)(x) + \\ + &= A \cdot (f * g)(x) \end{aligned}$$ Then we do the same again, this time starting from a product in the $$x$$-domain: $$\begin{aligned} - \hat{\mathcal{F}}\{f(x) \: g(x)\} - &= A \int_{-\infty}^\infty f(x) \Big( B \int_{-\infty}^\infty \tilde{g}(k') \: e^{-i s x k'} \dd{k'} \Big) e^{i s k x} \dd{x} + \hat{\mathcal{F}}\Big\{ f(x) \: g(x) \Big\} + &= A \int_{-\infty}^\infty f(x) \bigg( B \int_{-\infty}^\infty \tilde{g}(k') \: e^{-i s x k'} \dd{k'} \bigg) e^{i s k x} \dd{x} \\ - &= B \int_{-\infty}^\infty \tilde{g}(k') \Big( A \int_{-\infty}^\infty f(x) \: e^{i s x (k - k')} \dd{x} \Big) \dd{k'} + &= B \int_{-\infty}^\infty \tilde{g}(k') \bigg( A \int_{-\infty}^\infty f(x) \: e^{i s x (k - k')} \dd{x} \bigg) \dd{k'} \\ &= B \int_{-\infty}^\infty \tilde{g}(k') \: \tilde{f}(k - k') \dd{k'} - = B \cdot (\tilde{f} * \tilde{g})(k) + \\ + &= B \cdot (\tilde{f} * \tilde{g})(k) \end{aligned}$$ {% include proof/end.html id="proof-fourier" %} @@ -62,45 +67,51 @@ $$\begin{aligned} ## Laplace transform -For functions $$f(t)$$ and $$g(t)$$ which are only defined for $$t \ge 0$$, +For functions $$f(t)$$ and $$g(t)$$ that are only defined for $$t \ge 0$$, the convolution theorem can also be stated using the [Laplace transform](/know/concept/laplace-transform/): $$\begin{aligned} - \boxed{(f * g)(t) = \hat{\mathcal{L}}{}^{-1}\{\tilde{f}(s) \: \tilde{g}(s)\}} + \boxed{ + (f * g)(t) + = \hat{\mathcal{L}}{}^{-1}\Big\{ \tilde{f}(s) \: \tilde{g}(s) \Big\} + } \end{aligned}$$ -Because the inverse Laplace transform $$\hat{\mathcal{L}}{}^{-1}$$ is -unpleasant, the theorem is often stated using the forward transform -instead: +Because the inverse Laplace transform $$\hat{\mathcal{L}}{}^{-1}$$ is usually difficult, +the theorem is often stated using the forward transform instead: $$\begin{aligned} - \boxed{\hat{\mathcal{L}}\{(f * g)(t)\} = \tilde{f}(s) \: \tilde{g}(s)} + \boxed{ + \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\} + = \tilde{f}(s) \: \tilde{g}(s) + } \end{aligned}$$ {% include proof/start.html id="proof-laplace" -%} We expand the left-hand side. Note that the lower integration limit is 0 instead of $$-\infty$$, -because we set both $$f(t)$$ and $$g(t)$$ to zero for $$t < 0$$: +because we choose to set both $$f(t)$$ and $$g(t)$$ to zero for $$t < 0$$: $$\begin{aligned} - \hat{\mathcal{L}}\{(f * g)(t)\} - &= \int_0^\infty \Big( \int_0^\infty g(t') \: f(t - t') \dd{t'} \Big) e^{-s t} \dd{t} + \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\} + &= \int_0^\infty \bigg( \int_0^\infty g(t') \: f(t - t') \dd{t'} \bigg) e^{-s t} \dd{t} \\ - &= \int_0^\infty \Big( \int_0^\infty f(t - t') \: e^{-s t} \dd{t} \Big) g(t') \dd{t'} + &= \int_0^\infty \bigg( \int_0^\infty f(t - t') \: e^{-s t} \dd{t} \bigg) \: g(t') \dd{t'} \end{aligned}$$ Then we define a new integration variable $$\tau = t - t'$$, yielding: $$\begin{aligned} - \hat{\mathcal{L}}\{(f * g)(t)\} - &= \int_0^\infty \Big( \int_0^\infty f(\tau) \: e^{-s (\tau + t')} \dd{\tau} \Big) g(t') \dd{t'} + \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\} + &= \int_0^\infty \bigg( \int_0^\infty f(\tau) \: e^{-s (\tau + t')} \dd{\tau} \bigg) \: g(t') \dd{t'} \\ - &= \int_0^\infty \Big( \int_0^\infty f(\tau) \: e^{-s \tau} \dd{\tau} \Big) g(t') \: e^{-s t'} \dd{t'} + &= \int_0^\infty \bigg( \int_0^\infty f(\tau) \: e^{-s \tau} \dd{\tau} \bigg) \: g(t') \: e^{-s t'} \dd{t'} \\ &= \int_0^\infty \tilde{f}(s) \: g(t') \: e^{-s t'} \dd{t'} - = \tilde{f}(s) \: \tilde{g}(s) + \\ + &= \tilde{f}(s) \: \tilde{g}(s) \end{aligned}$$ {% include proof/end.html id="proof-laplace" %} |