Apliko de Splajn-funkcioj:
signifa metodo de komputora matematiko

D-ro Ivan L. Andronov
Odesa Ŝtata Universitato, katedro de astronomio,
park im. T.G. Ŝevĉenko, 270014 Odessa, Ukrainio, root@astro.odessa.ua


Ni revuas diversajn flankojn de uzado de matematika aparato de splajn-funkcioj: interpolado, glatigado de tabele determinataj funkcioj; numera integralado de funkcioj kaj ĝiaj kvadratoj; komparo kun rezultoj de Fourier-a analizo. Novaj metodoj de serĉo de periodo de varia signalo kaj de restarigado de signalo influita per "aparata funkcio" estas proponitaj.


1. Enkonduko

Dum lasta tempo la sciencistoj el diversaj landoj tre interesiĝas pri tie ĉi nomataj splajn-(spline) funkcioj, aparte pri la "kubaj splajnoj" (Ahlberg k.a. 1967, Kornejĉuk 1984, Marĉuk 1980, Zavjalov k.a. 1980 kaj aliaj monografioj). Uzado de tiaj ĉi funkcioj estas tre efektiva kaj havas kelkajn avantaĝojn kompare kun la aliaj metodoj.

En tiu ĉi artikolo ni mallonge diskutas kelkajn plej uzatajn aplikojn de la metodo. Post difino de splajnoj (sekcio 2) ni priskribos metodon de glatigo de pereksperimente mezuritaj valoroj de la funkcio (sekcio 3), de komputora integralado funkcioj (sekcio 4) kaj ĝiaj kvadratoj (sekcio 5). En sekcio 7 ni diskutas Fourier-spektron de kubaj splajn-funkcioj kaj komparas splajnajn kaj trigonometriajn aproksimaĵojn. Bonaj interpolaj proprecoj de splajnoj povus esti uzataj por la restarigado de funkcioj tiel, ke oni aplikas valorojn influitajn per la mezurilo (sekcio 6) kaj por la esploro de eblaj periodaĵoj de varia signalo (sekcio 8).


2. Polinomaj splajnoj

2.1 Difino

La polinoma splajno de potenco n kaj difekto k estas la funkcio, kia estus kalkulita per la formulo (vidu cititajn monografiojn):

S(x)=Bj0+Bj1h+…+Bjnhn, (1)

kie h=x–xj; j=l, se xl≤x<l+1; xl, l=l…L — la argumentoj de tie ĉi nomataj "karakterizaj punktoj" de splajno. Estas notinde, ke nun ni uzas L=N (kvanto da interpolitaj punktoj), sed eble N≤L (vidu sekcio 3). Ekster la intervalo [xi, xL] ekzistas du eblecoj por kalkulo de j: se splajno estas neperioda, j=L, se x<x1, kaj j=L, se x≥xL. Por splajno kun la periodo P,j=L por ambaŭ okazoj, sed h=P+x−xL, se 0≤x≤x1. Por facileco de sekvaj esploroj, oni numeras "karakterizajn punktojn" laŭ la ordo de pliiĝo da argumentoj: x1<x2…<xL. Parametro n estas la potenco de polinomo (1). Difekto k montras al ni, kie "glata" estas splajno: ĉiaj derivatoj de splajno de potenco ĝis (n−k) inkluzive estas kontinua eĉ en "karakterizaj punktoj".

Ĉi tie ni devas skribi kelkajn notojn. La polinomo ĉie havas kontinuajn derivatojn de ĉia potenco. Oni povas skribi ankaŭ, ke la polinomo havas difekton k=0. Formale oni plusas novan karakterizaĵon −k, sed praktike tio ĉi signifas, ke splajnoj estas pli vasta klaso.

Splajnoj estas kompleksaj funkcioj. Por diversaj argumentoj, la funkcioj uzataj por kalkulado estas diversaj, kontraŭ maniere kompare kun ĉiaj analitikaj funkcioj. Problemoj de nepolinomaj splajnoj estas interesaj por teoriistoj (ekz. Laurent 1972), sed polinomaj splajnoj, kiaj estas nur parto de ĉiaj splajnoj, estas la plej ofte uzata parto, kaj ni diskutas nur ilin.


2.2 Ekzemploj

Splajnoj estis tre ofte uzitaj, sed ne havis tian ĉi nomon. Ekz. splajno de nula potenco (Fig. 1, n = 0), laŭ difine estas konstanta funkcio en ĉiu subintervalo kun (eble) diversaj valoroj en ĉiu. Difekto k=1, tial la funkcio ne estas kontinua, sed la derivato de potenco (−1= integralo) jes estas tia. " Histogramo" montranta kiomojn da ia fizika karakterizaĵo en subintervaloj povas esti la plej uzata ekzemplo. Tiuj ĉi splajnoj (n=0, k=1) ankaŭ estas uzataj por serĉo de periodaĵoj de varia signalo (metodo de Jurkevich 1971) aŭ por aproksimado de rentgenaj observoj per kosmaj sputnikoj (ekz. Hearn kaj Richardson 1977).

La splajnoj (n=1, k=1) estas linioj interligantaj "karakterizajn punktojn" (fig. 1, "n=1"). Ili estas ofte uzataj por la interpolado de funkciaj valoroj, presitaj en tabeloj.

Tamen la plej ofte uzataj funkcioj en modernaj kalkuloj estas kubaj (n=3, k=1) splajnoj. Ili estas la plej glataj funkcioj, kiuj havas en intervalo [x1, xL] kontinuan derivaton de potenco 2 kaj kiaj interpolas fiksitajn punktojn, tial en tia ĉi klaso da funkcioj, la kuba splajno minimumigas integralon

dx (2)

(ekz. Forsythe k.a. 1977).


2.3 Bazaj splajn–funkcioj

Iu splajno kun fiksitaj argumentoj de "karakterizaj punktoj" x1…xL povas esti kalkulita kiel

(3)

kie cj estas koeficientoj (ĉi-okaze egalaj al la valoroj de funkcio yj=y(xj)), kaj Sj(x) — la "bazaj funkcioj" difinitaj laŭ kondiĉoj

(4)

 

Fig. 1. Periodaj (P=1) bazaj splajnoj S1(x) por L=4 egaldistancaj laŭ argumento "karakterizaj punktoj" kaj difekto k=1 por diversaj n.

Kompreneble, ke ekzistas senfina nombro da funkcioj havantaj tian ĉi proprecon, kaj ĉiaj tiaj funkcioj povas esti uzataj por la aproksimado. Tamen, se ni fiksus klason de funkcioj, la bazaj funkcioj ekestus determinataj. Se Sj(x) estas splajno, la linia kombinacio (3) estas ankaŭ la splajno de la samaj valoroj de n kaj


2.4 Kial komputi koeficientojn de splajnoj?

Antaŭe ni diskutis abstraktajn formulojn priskribantajn kunajn proprecojn. Sed por praktika apliko necesas havi klaran metodon de komputado de parametroj Bjm el ekvacio (1).

Por la plej simpla okazo n=0, k=1, oni povas skribi Bj0=yj:

y(x)=yj, (5)

kie j estas determinata laŭ menciitaj kondiĉoj. Se n=1, k=1,

y(x)=yjw+yj+1w, (6)

kie w=h/hj, h=x−xj, hj=xj+1−xj, w=l−w. Laŭ Forsythe k.a. (1977), okaze de n=3, k=1,

y(x)=yjw+yj+1w,+((w3wj+(w3−w)β1+1), (7)

kie la valorojn de parametroj βj oni povas komputi, solvante sistemon de L liniaj ekvacioj:

(8)

(perioda splajno, kian ni markas kiel "slajno de tipo I", aŭ

(9)

(slpajno II) aŭ β1L=0,

(10)

(splajno III), kie Dj=(yj+1−yj)/hj, j=1…L−1; DL=(y1−yL)/hL, hL=P+ x1−xL (indekso L nur por periodaj splajnoj I), kaj

(11)

estas aproksimaĵo por la tri-potenca derivato de aproksimata funkcio (tia ĉi valoro estas preciza, se la funkcio estas polinomo (n≤3, k=0)).

Uzante ekvacion (7), oni povas skribi derivatojn:

(12)

aŭ, kompare kun ekv. (1), por la karakterizaj punktoj,

y'(xj)=Bj1=Dj−hj(2βjj+1)
y''(xj)=2Bj2=6βj(13)
y'''(xj)=6Bj3=6(βj+1−βj/hj,   j=l…L−l

Por j=L estas du eblecoj: por la perioda splajno I oni povas simple uzi indekson 1 por (L+1), kaj por la splajnoj II kaj III

y'(xL)=DL−1+hL−1+2βL)
y''(xL)=6βL(14)
y'''(xL)=y'''(xL−1).

Estas notinde, ke la splajno III true minimumigas integralon (2). Tiu ĉi splajno estas ofte nomata kiel "natura splajno", la plej glata sence de ekv. (2) funkcio. Sed tiu ĉi splajno ne estas la plej bone aproksimanta funkcio — ni misaproksimas du-potencan derivaton de funkcio apud limoj de intervalo: y''(x1)=y''(xL)=0. Tia ĉi kondiĉo ne estas trua por ĉiuj funkcioj. Pro tio Forsythe k.a. (1977) proponis uzi aliajn limkondiĉojn : aproksimi tri-potencan derivaton apud limoj uzante kvar apudajn "karakterizajn punktojn", alivorte: aproksimi tiujn ĉi kvar punktojn per polinomo (n=3, k=0), kaj uzi tia maniere kalkulitajn derivatojn y'''(x1) kaj y'''(xL). Tiu ĉi splajno II aproksimas analitikajn funkciojn pli bone, ol la splajnoj III (vd. ankaŭ Andronov 1985a, 1986). Por komparo, bazaj funkcioj por polinomo, interpolanta ĉiujn punktojn estas

(15)

Tiu ĉi Lagrange-a polinomo (funkcio IV laŭ nia signifo) aproksimas "karakterizajn punktojn", sed inter ili la variaĵoj de polinomo povas esti multoble pli grandaj kompare kun la variaĵoj de funkcio (fig. 2, 3).

Fig. 2. Bazaj funkcioj (I-IV) por L=10 kaj j=1.

Fig. 3. Bazaj funkcioj (I-IV) por L=10 kaj j=5.


3. Glatigaj splajnoj : du manieroj de komputo

3.1 Metodo de "ĉiupunkta" splajno

Tre ofte oni devas aproksimi eksperimentajn valorojn per ia glata funkcio. Uzante splajnojn, tiu ĉi tasko povas esti solvata dumaniere. Pli malnova (kaj pli uzata) metodo bazas sin sur la minimumigado de sumo

(16)

kie pi estas ia "kontribua koeficiento" dependa de precizeco de valoro yi; potenco de derivato m estas 2 (Marĉuk 1980) aŭ 3 (Vondrak 1969, Picchio 1981); λ2 — ia parametro karakterizanta gradon de aproksimeco inter punktoj kaj aproksimanta kurbo. Se λA2=0, la "glatiga" funkcio estas interpolanta splajno (kun "karakterizaj punktoj" ĉe la samaj argumentoj, kiel "eksperimentaj punktoj"). Se λ2≠0, la funkciaj valoroj ĉe "karakterizaj punktoj" estas variigitaj, kaj la splajno interpolas tiujn "korektitajn" punktojn. En tiu ĉi metodo ne estas tute klara la fizika senco de la parametroj λ2 kaj p1. Variigante ĝiajn valorojn, oni povas komputi multajn splajnojn, tial estas necese ellabori konkretajn kriteriojn por tio.

3.2 La metodo de "malplej grandaj kvadratoj"

Bazaj splajn-funkcioj (4) povas esti uzataj por komputado de koeficientoj Cj (ekvacio (3)) laŭ kondiĉo, ke

(17)

estas minimuma (se aliaj parametroj havas la samajn valorojn). Kontraŭ la metodo priskribita en sekcio 3.1, tie ĉi la "karakterizaj punktoj" povas havi argumentojn ne egalaj al argumentoj de "eksperimentaj punktoj" (ekz. Andronov 1985a). Oni povas skribi sistemon de L "normalaj ekvacioj"

(18)

(19)

ke

(20)

Se la valoroj yip1=const=1/N. Ĉi-okaze oni povas komputi precizecon de la koeficientoj Cj laŭ ekvacio

(21)

kie (Vjk) estas matrico inversa rilate al la matrico (Amj):

(22)

(ekz. Ceseviĉ 1970). Laŭ la difino de bazaj funkcioj (4), ρj estas precizeco de la komputitaj valoroj S(xj).

Estas notinde, ke por neperiodaj funkcioj (II-IV, 3), la valoro de ρj pliiĝas ĉe la limoj de intervalo. Kompare malgranda valoro de ρj apud centro de intervalo por interpolanta Lagrange-a polinomo (IV) estas ligita kun la pli granda sentiveco de tiu ĉi funkcio de malgrandaj variaĵoj de aproksimita funkcio. Tamen ĉe la limoj de intervalo, la valoroj ρj multoble pliiĝas ankaŭ por la funkcio (IV). Por fiksita tipo de funkcio, la valoroj ρj estas pli malgrandaj, se la kvanto da "glatigataj" punktoj estas pli granda apud tia "karakteriza punkto".

La FORTRAN-lingvaj programoj uzantaj la menciitajn me-todojn estas publicitaj fare de l'aŭtoro (1985).


4. Integralado de funkcioj per splajnoj

Laŭ la ekvacioj (3), (4), oni povas skribi

(23)

kie

(24)

Se la argumentoj xj da kelkaj aproksimataj funkcioj estas la samaj, oni povas komputi koeficientojn Gj kaj post multfoje (se necese) kalkuli integralojn (23) kun diversaj vektoroj yj. Tiuj ĉi "kvadraturaj" formuloj estas ĉiam uzataj (metodoj de Newton-Cotes, Ĉebiŝev (vd. ekz. Marĉuk 1980, Krilov 1959), sed bazaj funkcioj ankaŭ povas esti splajnoj.

Por plej simpla (kaj ofta) okazo, "karakterizaj punktoj" estas egaldistancaj laŭ argumento; kaj la integralon (23) oni povas skribi tial

(25)

kie

(26)

En tab.1 ni skribis koeficientojn gj por L=9, polinomo IV (ekz. Dimarskij k.a. 1963) kaj splajnoj II, III (Andronov 1986).

Tab. 1. Koeficientoj por kvadraturaj formuloj de la funkcioj II-IV

EIIIIIIV
E1, E9361391071989
E2, E8 13206030805888
E3, E7 898862618−928
E4, E6 109340274410496
E5 1035182702−4540
E 8383682172828350

Ĉiujn koeficientojn oni povas skribi tial

Estas notinde, ke gj=gL+i−j.

La glatigaj splajnoj ankaŭ povas esti uzataj por integralado (vidu Andronov 1986 por detaladiskuto kaj FORTRAN-lingvaj programoj).


5. Integralado de kvadratoj de funkcioj

Por iuj taskoj oni devas komputi integralon de funkcia kvadrato. Splajnoj ankaŭ estas uzeblaj por tiu ĉi celo. La tuta integralo estas la sumo de integraloj tra subintervaloj. Por kuba splajno

(27)

kie h=x−xj; b=Bj0, c=Bj2, e=Bj3. Se x=xj+1, oni povas ankaŭ uzi la ekvacion (7). Tial

(28)

kie Y0=yj, Y1=yj+l, Y2=βj, Y3=βj+1 kaj

(29)

Se kalkuli simetrian matricon

(30)

oni povas uzi ĝin en ekv.(28) anstataŭ Gkl. Tio ĉi signifas, ke la matrico Tkl estas la analogo de tie ĉi nomata "metrika tensoro" uzata aparte en la relativeca teorio.


6. Restarigado de funkcioj

Ĉiuj valoroj ricevitaj per mezuriloj ne estas precizaj. Krom la eraroj karakterizantaj precizecon, estas influo de mezurilo al la mezurata proceso. En ĉiuj mezuroj ni uzas filtrilon (de tempo, spaco, ondlongo, energio k.t.p.). En multaj okazoj ni povas skribi integralan ekvacion

(31)

Laŭ la ekvacioj (3,4),

(32)

kie

(33)

yj estas "mezuritaj" valoroj; g(x') estas tie ĉi nomata "aparata funkcio" dependa de proprecoj de mezurilo; fm=f(xm) — la restarigita funkcio. Se oni aproksimas funkcion f(x) per fiksitaj bazaj funkcioj, komputante la matricon Umj, oni povas restarigas "influitajn" valorojn. Oni ĉiam uzas por tiu ĉi celo nur metodon de rapida Fourier-a, transformo (FFT – Fast Fourier Transform, v. ekz. Brault kaj White 1971). Tamen kubaj splajnoj ankaŭ povas esti uzeblaj (Andronov 1987a). En ambaŭ metodoj, la rezultoj forte dependas de uzata "lima frekvenco". Okaze de polinomaj splajnoj tiun ĉi rolon ludas la distanco inter "karakterizaj punktoj" de splajno (v. ankaŭ sekcion 7). "Glatigaj splajnoj" montras pli bonajn rezultojn kompare kun la "interpolantaj", tial "glatigo" funkcias kiel "reguligo". La nura malavantaĝo de tiu ĉi metodo estas ligita kun malfacilaĵoj de kalkulo de matricaj elementoj.

Alia metodo bazita sur la loka aproksimado de funkcio per polinomo e kvara potenco (ankaŭ splajn-aproksimado: n=4, k=4) estis proponita fare de l'aŭtoro (1985b).


7. Fourier-a spektroj de splajnoj

Se la funkcio estas aproksimata per la formulo

y(x)=C0+C1s1+C2c1+C3s2+C4c2+…+CL−1sM+CLcM (34)

kie L=2M+1, sm=sin(2πmx), cm=cos(2πmx) (argumentoj estas transformitaj tiel, ke la periodo P=1), la koeficientojn Cj oni povas komputi, solvante sistemon de liniaj ekvacioj:

(35)
(36)

kie

k.t.p. Se x1 estus kalkulata, tial x1=iJ/N+const (J&no;0 — ĉiu entjero), la Fourier-a transformo estus

(37)

Oni povas ankaŭ skribi, ke

C2msm+C2m+icm=Rmcos(2πmxi―…øm)(38)

kie Rm kaj øm estas la amplitudo kaj fazo de sinus-kurbo No m:

Rmsinøm=C2m (39)
Rmcosøm=C2m+i

Ekz., sur fig. 4 estas desegnitaj Fourier-spektroj (dependeco Rm de m) por periodaj bazaj splajnoj kun L=4, 8 kaj 16). Pliigante L, oni povas pliigi kontribuon de oscilaĵo kun grandaj m.

Fig. 4. Fourier-spektroj da periodaj bazaj kubaj splajnoj (n=3, k=l).

La "lima frekvenco" m0 (montranta por kiaj m>m0 la oscilaĵoj ne estas signifaj) dependas de kvanto da "karakterizaj punktoj" L. El fig.4, m0≈L/2+2±1. Tial se valoroj de L estas la samaj por "splajna" kaj "trigonometria" aproksimado, la splajnoj aproksimas "eksperimentaj" punktoj pli bone iomete — ili havas "ekstrajn oscilajojn" kun m>L/2.

Estas notinde, ke la grado de proksimeco inter punktoj kaj kurbo pliiĝas kun pliiĝo de L. Tamen se pli multe da parametroj oni havas, malpli precizaj estas ties valoroj. Tial oni povas serĉi "optimuman" valoron de kvanto da komputataj parametroj.


8. Serĉo de periodo de varia signalo

La matematika tasko jenas: estas du vektoroj ti, yi, i=1…N. Estas necese komputi parametrojn T), P, C1…CL, por kiuj la valoro de tie ĉi nomata "testa funkcio"

Q(T0,p;t1…tN;yN;C1…CL)

havas ekstremon (v. Pelt 1980, Heck k.a. 1985, Andronov 1988 por revuoj). Oni povas uzi ekvacion (17). Tiam xi=dec((ti−T0)/P), kie xi estas la fazo de i−a punkto, T0 – "komenca epoko", P – testa periodo, dec(x) – decimala parto de x:0≤dec(x;)<1. Komputante la funkcion Q por diversaj periodoj, oni povas determini "plej bonan" periodon. Parametroj C1…CL por ĉia testa periodo estas komputataj per la metodo de "malplej grandaj kvadratoj" (v. sekcion 3.2).

Fig. 5. Splajnoj (n=0, k=1; n=1, k=2; n=3, k=1) aproksimantaj la "testan" sinuson determinatan en 20 punktoj. Du kurboj estas desegnitaj por diversaj valoroj da "komenca epoko".

Bedaŭrinde, por ĉiuj splajnoj la funkcio Q dependas de la "komenca epoko" T0 (v. fig.5). Tial estas necese pli foje "glatigi" "glatigendajn funkciojn":

(40)

kie xlk=(k–1/(KL), xlk=(l−)/L+x1k estas argumentoj de "karakterizaj punktoj" de splajno S(x,k) Por ĉiu k estas determinitaj la parametroj Cj, kaj "glatigata" (laŭ (39)) kurbo estas uzata en ekv.(17) anstataŭ "trua splajno" j CjSj(xi).

La precizeco de kurba valoro ĉe argumento x povas esti kalkulata per la formulo

(41)

Splajno (n=0, k=1) estas uzata en la metodo de Jurkevich (1971); (n=1, k=2) – de Marraco kaj Muzzio (1980); (n=3, k=1) – de Andronov (1985a, 1988). Fazaj kurboj por tiuj ĉi metodoj estas montrataj en fig. 5. Pli detale la metodo estas priskribita fare de l'aŭtoro (1987b) kaj unue uzata en astronomio per Andronov kaj Richter (1987).


9. Finaj rimarkoj

La priskribitaj taskoj ne estas ĉiuj aplikoj de aparato de splajn-funkcioj. Estas multaj monografioj pri tiu ĉi temo (ekz. Steĉkin kaj Subbotin 1976, Topoljanskij kaj Krilova 1977 pri metodoj de solvado de diferencialaj ekvacioj uze de splajnoj). Tamen ni volis nur montri diversajn problemojn kaj direktojn ligitajn kun splajnoj. Por ĉiuj taskoj ekzistas multaj solvoj, kaj aperadas novaj flankoj de tiu ĉi disvolvata metodo.

Splajnoj ne estas analitikaj funkcioj — ĝiaj derivatoj ne estas kontinuaj ĉe "karakterizaj punktoj". Ili ne havas klaran fizikan sencon (kiel ekz. Fourier-oscilaĵoj), tial ni devas ne forgesi, ke splajnoj estas ne granda fizika invento, sed signifa kaj fruktodona ilo de komputora matematiko.


10 Literaturo


Fonto: Scienca Revuo Vol. 46 (1995)(1) -166 pp. 20-38. STEB: http://www.eventoj.hu/steb/