Kunfaldaĵo:

En matematiko, kaj precipe en funkcia analizo, kunfaldaĵo estas matematika operacio, kiu prenas du funkciojn f, g kaj produktas trian funkcion kiu, iusense, reprezentas la kvanton de superkuŝo inter f kaj inversigita kaj translaciita versio de g.

Vida klarigo de kunfaldaĵo. Faru ĉiun ondoformon funkcio de la lokokupa variablo

τ

. Inversigu laŭ tempo iun el la ondoformoj kaj adiciu je t por ebligu al ĝi gliti tien kaj reen laŭ la

τ

-akso restante senmova rilate al t. Fine, komencigu la funkcion ĉe negativa infinito kaj glitigu ĝin al pozitiva infinito. Kie la du funkcioj kruciĝas, trovu la integraĵon de ilia produto. La rezulta ondoformo (ne vidigita ĉi tie) estas la kunfaldaĵo de la du funkcioj. Se la senmova ondoformo estas impulsa unuo, la fina rezulto estas la originala versio de la glita ondoformo, ĉar ĝi estas denove inversigita laŭ tempo, ĉar la dekstra eĝo trafas la impulsan unuon unue kaj la maldekstra eĝo laste. Tio ankaŭ ĝenerale estas la kialo por la inversigo laŭ tempo, ĉar kompleksajn signalojn oni povas konsideri konsisti el impulsaj unuoj

Difino

La kunfaldaĵon de $f\,$ kaj $g\,$ oni skribas jene: $f * g \,$ . Ĝi estas difinita kiel la integraĵo de la produto de la du funkcioj kiam unu estas inversigita kaj translaciita. Tial ĝi estas specifa speco de integraĵa transformo:

La integraĵa amplekso dependas de la domajno en kiu la funkcioj estas difinitaj; ofte a = -∞ kaj b = +∞. Dum la simbolo $t\,$ estas uzata supre, ĝi ne devas reprezenti la domajnon tempan. Kaze de finita integraĵa amplekso, $f\,$ kaj $g\,$ ofte estas konsiderataj etendi periode en ambaŭ direktoj, por ke la termino $\displaystyle g(t-\tau)$ ne implicu malobservi amplekson. Oni iam nomas tian uzadon de periodaj domajnoj cirkla kunfaldaĵo aŭ perioda kunfaldaĵo. Kompreneble etendigo per nuloj ankaŭ eblas. Uzi nul-etenditajn aŭ infinitajn domajnojn oni iam nomas linia kunfaldaĵo, precipe en la diskreta kazo sube.

Diskreta kunfaldaĵo

Por diskretaj funkcioj, oni povas uzi diskretan version de la kunfalda operacio. Ĝin donas

Kiam oni multiplikas du polinomojn, la koeficientojn de la produto donas la kunfaldaĵo de la originala koeficientaj sinsekvoj, en ĉi tiu senso (uzante edendojn kun nuloj, kiel menciite supre).

Por ĝeneraligi la suprajn kazojn, la kunfaldaĵo estas difinebla por ajnaj du integreblaj funkcioj difinitaj sur loke kompakta topologia grupo.

Komputi diskretajn kunfaldaĵojn per la supra formulo rekte aplikata prenas Landau-notacion O(N²) aritmetikaj operacioj por N punktoj, sed tio estas reduktebla al O(N log N) per diversaj rapidaj algoritmoj.

Rapidaj kunfaldaj algoritmoj

Praktike, cifereca signalpritraktado kaj aliaj aplikaĵoj de diskretaj kunfaldaĵoj tipe utiligas rapidajn kunfaldajn algoritmojn por pliigi la rapidon de la kunfaldaĵo al komplekseco O(N log N).

La plej oftaj rapidaj algoritmoj uzas rapidajn Fourier-transformojn (FFT) per la kunfalda teoremo: la cikla kunfaldaĵo de du sinsekvoj estas trovebla, se oni prenas FFT-on de ĉiu sinsekvo, multiplikas laŭpunkte, kaj faras inversan FFT-on. Neciklaj kunfaldaĵoj, ekzemple liniaj kunfaldaĵoj estas komputeblaj per cikla kunfaldaĵo uzanta nul-pakadon.

Ekzistas ankaŭ multaj aliaj rapidaj kunfaldaj algoritmoj kiuj ne uzas FFT-ojn mem, ekzemple numerteoriaj transformaj algoritmoj.