Свёртка (математический анализ)

У этого термина существуют и другие значения, см. Свёртка.

Свёртка, конволюция — операция в функциональном анализе, которая при применении к двум функциям ${\displaystyle f}$ и ${\displaystyle g}$ возвращает третью функцию, соответствующую взаимнокорреляционной функции ${\displaystyle f(x)}$ и ${\displaystyle g(-x)}$. Операцию свёртки можно интерпретировать как «схожесть» одной функции с отражённой и сдвинутой копией другой. Понятие свёртки обобщается для функций, определённых на произвольных измеримых пространствах, и может рассматриваться как особый вид интегрального преобразования. В дискретном случае свёртка соответствует сумме значений ${\displaystyle f}$ с коэффициентами, соответствующими смещённым значениям ${\displaystyle g}$, то есть ${\displaystyle (f*g)(x)=f(1)g(x-1)+f(2)g(x-2)+f(3)g(x-3)+\dots }$

Свёртка двух прямоугольных импульсов: в результате даёт треугольный импульс.

Свёртка прямоугольного импульса (входного сигнала) с импульсным откликом RC цепи

Определение

Пусть ${\displaystyle f,g:\mathbb {R} ^{n}\to \mathbb {R} }$ — две функции, интегрируемые относительно меры Лебега на пространстве ${\displaystyle \mathbb {R} ^{n}}$. Тогда их свёрткой называется функция ${\displaystyle f*g:\mathbb {R} ^{n}\to \mathbb {R} }$, определённая формулой

${\displaystyle (f*g)(x)\ }$

${\displaystyle {\stackrel {\mathrm {def} }{=}}\ \int \limits _{\mathbb {R} ^{n}}f(y)\,g(x-y)\,dy=\int \limits _{\mathbb {R} ^{n}}f(x-y)\,g(y)\,dy.}$

В частности, при ${\displaystyle n=1}$ формула принимает вид

${\displaystyle (f*g)(x)\ }$

${\displaystyle {\stackrel {\mathrm {def} }{=}}\ \int \limits _{-\infty }^{\infty }f(y)\,g(x-y)\,dy=\int \limits _{-\infty }^{\infty }f(x-y)\,g(y)\,dy.}$

Свёртка ${\displaystyle (f*g)(x)}$ определена при почти всех ${\displaystyle x\in {\mathbb {R} ^{n}}}$ и интегрируема.

В случае, когда ${\displaystyle x\in \mathbb {R} }$, а функции ${\displaystyle f(x),~g(x)}$ определены на промежутке ${\displaystyle [0,+\infty )}$, свёртку можно записать в виде

${\displaystyle (f*g)(x)\ }$

${\displaystyle {\stackrel {\mathrm {def} }{=}}\ \int \limits _{0}^{x}f(y)\,g(x-y)\,dy=\int \limits _{0}^{x}f(x-y)\,g(y)\,dy.}$

Впервые интегралы, являющиеся свёрткой двух функций, встречаются в трудах Леонарда Эйлера (1760-е годы); позднее свёртка появляется у Лапласа, Лакруа, Фурье, Коши, Пуассона и других математиков. Обозначение свёртки функций при помощи звёздочки впервые предложил Вито Вольтерра в 1912 году на своих лекциях в Сорбонне (опубликованы годом позже)^[1].

Свойства

Коммутативность:

${\displaystyle f*g=g*f}$.

Ассоциативность:

${\displaystyle f*(g*h)=(f*g)*h}$.

Линейность (дистрибутивность по сложению и ассоциативность с умножением на скаляр):

${\displaystyle (f_{1}+f_{2})*g=f_{1}*g+f_{2}*g}$,

${\displaystyle f*(g_{1}+g_{2})=f*g_{1}+f*g_{2}}$,

${\displaystyle (af)*g=a(f*g)=f*(ag),\quad \forall a\in \mathbb {R} }$.

Правило дифференцирования:

${\displaystyle \mathrm {D} (f*g)=\mathrm {D} f*g=f*\mathrm {D} g}$,

где ${\displaystyle \mathrm {D} f}$ обозначает производную функции ${\displaystyle f}$ по любой переменной.

Преобразование Лапласа:

${\displaystyle {\mathcal {L}}\{f(x)*g(x)\}={\mathcal {L}}\{f(x)\}\cdot {\mathcal {L}}\{g(x)\}}$.

Свойство фурье-образа:

${\displaystyle {\mathfrak {F}}[f*g]={\mathfrak {F}}[f]\cdot {\mathfrak {F}}[g]}$,

где ${\displaystyle {\mathfrak {F}}[]}$ обозначает преобразование Фурье функции.

Если ${\displaystyle {\mathcal {W}}}$ является матрицей дискретного преобразования Фурье, то:

${\displaystyle {\mathcal {W}}(C^{(1)}x\ast C^{(2)}y)=({\mathcal {W}}C^{(1)}\bullet {\mathcal {W}}C^{(2)})(x\otimes y)={\mathcal {W}}C^{(1)}x\circ {\mathcal {W}}C^{(2)}y}$,

где ${\displaystyle \bullet }$ — символ торцевого произведения матриц^{[2][3][4][5][6]}, ${\displaystyle \otimes }$ обозначает произведение Кронекера, ${\displaystyle \circ }$ — символ произведения Адамара (тождество является следствием свойств отсчётного скетча^[7]).

Пример

График функции ${\displaystyle {\color {Red}g(x)}}$— количество выпавшего снега в килограммах на начало часа.

Пусть стоит задача вычислить, как будет изменяться количество снега на каком-либо участке земли в зависимости от времени. Решение этой задачи можно разделить на два этапа:

1. построить модель выпадения снега и модель таяния снега.
2. каким-то образом соединить эти две модели в одну.

   

   График ${\displaystyle {\color {Blue}f(x)}}$ зависимости количества нерастаявшего снега от времени прошедшего с момента его выпадения.

Задачи первого этапа решаются путём наблюдений и опытов, а задачи второго этапа — свёрткой получившихся на первом этапе моделей.

Пусть в результате решения задачи на первом этапе было построено две зависимости (математические модели):

• зависимость количества выпавшего снега от текущего времени ${\displaystyle {\color {Red}g(t)}}$,
• зависимость доли нерастаявшего снега от времени, прошедшего с момента его выпадения ${\displaystyle {\color {Blue}f(\tau )}}$.

Если бы снег не начинал таять, количество всех выпавших осадков ${\displaystyle G}$ можно было бы посчитать путём сложения в дискретном случае:

${\displaystyle G=\sum _{t=0}^{T}g(t)}$,

или путём интегрирования в случае непрерывном:

${\displaystyle G=\int \limits _{0}^{T}g(t)\,dt}$.

Но в данном случае таяние снега имеет место и, более того, оно зависит не только от текущего общего количества снега, но и от того, в какой момент времени выпал этот конкретный объём снега. Так снег, выпавший две недели назад, может уже испариться, в то время как снег, выпавший полчаса назад, ещё будет лежать и даже не начнёт подтаивать.

Получается, что для снега, выпавшего в разное время, нужно построить свою модель таяния и как-то сложить все эти модели вместе.

Для этих целей и можно использовать понятие математической свёртки. Пусть в момент времени ${\displaystyle t}$ рассматривается снег, который выпал в момент времени ${\displaystyle \tau }$, тогда

• ${\displaystyle \tau }$ — время выпадения снега. Например, 13:00;
• ${\displaystyle {\color {Red}g(\tau )}}$ — количество выпавшего в момент ${\displaystyle {\tau }}$ снега. Например, 7 кг;
• ${\displaystyle t}$ — момент времени, для которого нам нужно узнать состояние выпавшего в ${\displaystyle \tau }$ снега. Например, 15:00;
• ${\displaystyle t-\tau }$ — количество времени, прошедшее с момента выпадения до момента расчёта оставшейся доли снега. То есть 15:00 − 13:00;
• ${\displaystyle {\color {Blue}f(t-\tau )}}$ — доля снега, которая не растаяла после того, как пролежала ${\displaystyle t-\tau }$ часов.

Нужно для каждого количества ${\displaystyle {\color {Red}g(\tau )}}$ снега, выпавшего в момент времени ${\displaystyle \tau }$, сложить множество моделей ${\displaystyle f(t-\tau )}$ в одну функцию. Если это сделать, получится сумма в дискретном случае:

${\displaystyle w(t)=\sum \limits _{\tau =0}^{t}g(\tau )f(t-\tau ),}$

или интеграл в непрерывном:

${\displaystyle w(t)=\int \limits _{\tau =0}^{t}g(\tau )f(t-\tau )d\tau .}$

Графически функция ${\displaystyle w(t)}$ изображена ниже, где разными цветами представлены вклады каждой кучи снега из графика ${\displaystyle {\color {Red}g(x)}}$.

График функции ${\displaystyle w(t)}$, где разным цветом представлен вклад каждой кучи снега (цвета вкладов соответствуют цветам куч выпавшего снега на графике ${\displaystyle {\color {Red}g(x)}}$ выше)

Функция ${\displaystyle w(t)}$ полностью моделирует поведение снега, выпавшего согласно модели ${\displaystyle {\color {Red}g(x)}}$. Так, на графике выше видно, что общее количество снега увеличивается тремя скачками, но снег начинает таять сразу, не дожидаясь выпадения других осадков.

Свёртка на группах

Пусть ${\displaystyle G}$ — группа, оснащённая мерой ${\displaystyle m}$, и ${\displaystyle f,g:G\to \mathbb {R} }$ — две функции, определённые на ${\displaystyle G}$. Тогда их свёрткой называется функция^{[источник не указан 1814 дней]}

${\displaystyle (f*g)(x)=\int \limits _{G}f(y)\,g\left(xy^{-1}\right)\,m(dy),\quad \forall x\in G.}$

Свёртка мер

Пусть есть борелевское пространство ${\displaystyle (\mathbb {R} ,{\mathcal {B}}(\mathbb {R} ))}$ и две меры ${\displaystyle \mu ,\nu$ :{\mathcal {B}}(\mathbb {R} )\to \mathbb {R} } . Тогда их свёрткой называется мера^{[источник не указан 1814 дней]}

${\displaystyle \mu *\nu (A)=\mu \otimes \nu \left(\{(x,y)\in \mathbb {R} ^{2}\mid x+y\in A\}\right),\quad \forall A\in {\mathcal {B}}(\mathbb {R} ),}$

где ${\displaystyle \mu \otimes \nu }$ обозначает произведение мер ${\displaystyle \mu }$ и ${\displaystyle \nu }$.

Свойства

• Пусть ${\displaystyle \mu ,\nu }$ абсолютно непрерывны относительно меры Лебега ${\displaystyle m}$. Обозначим их производные Радона — Никодима:

${\displaystyle f_{\mu }={\frac {d\mu }{dm}},\quad f_{\nu }={\frac {d\nu }{dm}}.}$

Тогда ${\displaystyle \mu *\nu }$ также абсолютно непрерывна относительно ${\displaystyle m}$, и её производная Радона — Никодима ${\displaystyle f_{\mu *\nu }={\frac {d\mu *\nu }{dm}}}$ имеет вид^{[источник не указан 1814 дней]}

${\displaystyle f_{\mu *\nu }=f_{\mu }*f_{\nu }.}$

• Если ${\displaystyle \mu ,\nu }$ — вероятностные меры, то ${\displaystyle \mu *\nu }$ также является вероятностной мерой.

Свёртка распределений

Если ${\displaystyle \mathbb {P} ^{X},\mathbb {P} ^{Y}}$ — распределения двух независимых случайных величин ${\displaystyle X}$ и ${\displaystyle Y}$, то^{[источник не указан 1814 дней]}

${\displaystyle \mathbb {P} ^{X+Y}=\mathbb {P} ^{X}*\mathbb {P} ^{Y},}$

где ${\displaystyle \mathbb {P} ^{X+Y}}$ — распределение суммы ${\displaystyle X+Y}$. В частности, если ${\displaystyle X,Y}$ абсолютно непрерывны и имеют плотности ${\displaystyle f_{X},f_{Y}}$, то случайная величина ${\displaystyle X+Y}$ также абсолютно непрерывна и её плотность имеет вид:

${\displaystyle f_{X+Y}=f_{X}*f_{Y}.}$

См. также

• Обратная свертка (деконволюция)
• Взаимнокорреляционная функция
• Автокорреляционная функция
• Свёртка последовательностей

Примечания

1. Domínguez A.  A History of the Convolution Operation // IEEE Pulse. — 2015. — Vol. 6, no. 1. — P. 38—49. Архивировано 3 февраля 2016 года.
2. Slyusar, V. I. (December 27, 1996). "End products in matrices in radar applications" (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архивировано (PDF) 27 июля 2020. Дата обращения: 1 августа 2020.
3. Slyusar, V. I. (1997-05-20). "Analytical model of the digital antenna array on a basis of face-splitting matrix products" (PDF). Proc. ICATT-97, Kyiv: 108—109. Архивировано (PDF) 25 января 2020. Дата обращения: 1 августа 2020.
4. Slyusar, V. I. (1997-09-15). "New operations of matrices product for applications of radars" (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74. Архивировано (PDF) 25 января 2020. Дата обращения: 1 августа 2020.
5. Slyusar, V. I. (March 13, 1998). "A Family of Face Products of Matrices and its Properties" (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379—384. doi:10.1007/BF02733426. Архивировано (PDF) 25 января 2020. Дата обращения: 1 августа 2020.
6. Slyusar, V. I. (2003). "Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels" (PDF). Radioelectronics and Communications Systems. 46 (10): 9—17. Архивировано (PDF) 20 сентября 2020. Дата обращения: 1 августа 2020.
7. Ninh, Pham; Rasmus, Pagh (2013). Fast and scalable polynomial kernels via explicit feature maps. SIGKDD international conference on Knowledge discovery and data mining. Association for Computing Machinery. doi:10.1145/2487575.2487591.

Литература

• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа, — М.: Наука, 2004 (7-е изд.).
• Ширяев А. Н. Вероятность, — М.: Наука. 1989.
• Напалков В. В. Уравнения свертки в многомерных пространствах. — М., Наука, 1982. — Тираж 3500 экз. — 240 с.

Ссылки

• Java-Applet
• Java-Applet
• Линейная и циклическая свертка  (рус.). Дата обращения: 15 ноября 2010.