Trigonometrisk interpolation
I matematik är trigonometrisk interpolation interpolation med trigonometriska polynom . Interpolation är processen att hitta en funktion som går igenom vissa givna datapunkter . För trigonometrisk interpolation måste denna funktion vara ett trigonometriskt polynom, det vill säga summan av sinus och cosinus för givna perioder. Denna form är speciellt lämpad för interpolering av periodiska funktioner .
Ett viktigt specialfall är när de givna datapunkterna är jämnt fördelade, i vilket fall lösningen ges av den diskreta Fouriertransformen .
Formulering av interpolationsproblemet
Ett trigonometriskt polynom av grad K har formen
-
()
0 Detta uttryck innehåller 2 K + 1 koefficienter, a , a 1 , … a K , b 1 , …, b K , och vi vill beräkna dessa koefficienter så att funktionen passerar genom N punkter:
Eftersom det trigonometriska polynomet är periodiskt med period 2π, kan N -punkterna fördelas och ordnas i en period som
(Observera att vi i allmänhet inte kräver att dessa punkter är lika fördelade.) Interpolationsproblemet är nu att hitta koefficienter så att det trigonometriska polynomet p uppfyller interpolationsvillkoren.
Formulering i det komplexa planet
Problemet blir mer naturligt om vi formulerar det i det komplexa planet . Vi kan skriva om formeln för ett trigonometriskt polynom som där i är den imaginära enheten . Om vi sätter z = e ix , så blir detta
med
Detta reducerar problemet med trigonometrisk interpolation till det med polynominterpolation på enhetscirkeln . Existens och unikhet för trigonometrisk interpolation följer nu omedelbart av motsvarande resultat för polynominterpolation.
För mer information om formulering av trigonometriska interpolerande polynom i det komplexa planet, se sid. 156 av Interpolation med Fourierpolynom .
Lösning av problemet
Under ovanstående förhållanden finns det en lösning på problemet för varje given uppsättning datapunkter { x k , y k } så länge som N , antalet datapunkter, inte är större än antalet koefficienter i polynomet, dvs. , N ≤ 2 K +1 (en lösning kan eller kanske inte existerar om N >2 K +1 beroende på den speciella uppsättningen av datapunkter). Dessutom är det interpolerande polynomet unikt om och endast om antalet justerbara koefficienter är lika med antalet datapunkter, dvs N = 2 K + 1. I resten av denna artikel kommer vi att anta att detta villkor gäller.
Udda antal poäng
Om antalet punkter N är udda, säg N=2K+1 , ger lagrangeformeln för polynominterpolation på polynomformuleringen i det komplexa planet att lösningen kan skrivas i formen
-
()
var
Faktorn i denna formel kompenserar för det faktum att den komplexa planformuleringen också innehåller negativa potenser av och är därför inte ett polynomuttryck i . Riktigheten av detta uttryck kan lätt verifieras genom att observera att och att är en linjär kombination av de högra potenserna av . När du använder identiteten
-
()
koefficienten kan skrivas i formen
-
()
Jämnt antal poäng
Om antalet punkter N är jämnt, säg N=2K , ger lagrangeformeln för polynominterpolation på polynomformuleringen i det komplexa planet att lösningen kan skrivas i formen
-
()
var
-
()
kan konstanterna Detta orsakas av att interpoleringsfunktionen ( 1 ) innehåller ett udda antal okända konstanter. Ett vanligt val är att kräva att den högsta frekvensen är av formen en konstant gånger , dvs termen försvinner, men i allmänhet kan fasen för den högsta frekvensen väljas till . För att få ett uttryck för får vi genom att använda ( 2 ) att ( 3 ) kan skrivas på formuläret
Detta ger
och
Observera att försiktighet måste iakttas för att undvika oändligheter orsakade av nollor i nämnarna.
Ekvidistanta noder
Ytterligare förenkling av problemet är möjlig om noderna är på samma avstånd, dvs.
se Zygmund för mer information.
Udda antal poäng
Ytterligare förenkling genom att använda ( 4 ) skulle vara ett självklart tillvägagångssätt, men är självklart involverat. Ett mycket enklare tillvägagångssätt är att överväga Dirichlet-kärnan
där är udda. Det kan lätt ses att är en linjär kombination av de rätta potenserna av och uppfyller
Eftersom dessa två egenskaper unikt definierar koefficienterna i ( 5 ), följer det att
Här förhindrar sinc -funktionen alla singulariteter och definieras av
Jämnt antal poäng
För till och med definierar vi Dirichlet-kärnan som
Återigen kan det lätt ses att är en linjär kombination av de högra potenserna av , innehåller inte term och uppfyller
Med hjälp av dessa egenskaper följer det att koefficienterna i ( 6 ) ges av
Observera att inte innehåller också. Observera slutligen att funktionen försvinner vid alla punkter . Multiplar av denna term kan därför alltid läggas till, men den utelämnas vanligtvis.
Genomförande
En MATLAB-implementering av ovanstående kan hittas här och ges av:
0 funktion P = triginterp ( xi,x,y ) % TRIGINTERP Trigonometrisk interpolation. % Inmatning: % xi utvärderingspunkter för interpolanten (vektor) % x ekvidistanserade interpolationsnoder (vektor, längd N) % y interpolationsvärden (vektor, längd N) % Utdata: % P-värden för den trigonometriska interpolanten (vektor) N = längd ( x ); % Justera avståndet för den givna oberoende variabeln. h = 2 / N ; skala = ( x ( 2 ) -x ( 1 ) ) / h ; x = x / skala ; xi = xi / skala ; % Utvärdera interpolant. P = nollor ( storlek ( xi )); för k = 1 : Np = P + y ( k ) * trigcardinal ( xi - x ( k ) , N ); slutfunktion tau = trigcardinal ( x,N ) ws = varning ( 'off' , ' MATLAB:divideByZero') ; % Form är olika för jämn och udda N. om rem ( N , 2 ) == 1 % udda tau = sin ( N * pi * x / 2 ) ./ ( N * sin ( pi * x / 2 )); annars % jämn tau = sin ( N * pi * x / 2 ) ./ ( N * tan ( pi * x / 2 )); slutvarning ( ws ) tau ( x == ) = 1 ; _ % fixvärde vid x=0
Relation med den diskreta Fouriertransformen
Det speciella fallet där punkterna xn är lika fördelade är särskilt viktigt. I det här fallet har vi
Transformationen som mappar datapunkterna y n till koefficienterna ak , bk erhålls från den diskreta Fouriertransformen ( DFT ) av ordningen N.
(På grund av hur problemet formulerades ovan har vi begränsat oss till udda antal poäng. Detta är inte strikt nödvändigt; för jämna antal poäng inkluderar man en annan cosinuster som motsvarar Nyquist-frekvensen . )
Fallet med cosinus-endast interpolation för punkter med lika mellanrum, motsvarande en trigonometrisk interpolation när punkterna har jämn symmetri , behandlades av Alexis Clairaut 1754. I detta fall är lösningen ekvivalent med en diskret cosinustransform . Sinusexpansionen för lika åtskilda punkter, motsvarande udda symmetri, löstes av Joseph Louis Lagrange 1762, för vilken lösningen är en diskret sinustransform . Det fullständiga cosinus- och sinusinterpolerande polynomet, som ger upphov till DFT, löstes av Carl Friedrich Gauss i opublicerat arbete omkring 1805, då han också härledde en snabb Fourier- transformalgoritm för att snabbt utvärdera den. Clairaut, Lagrange och Gauss var alla angelägna om att studera problemet med att sluta sig till omloppsbanan för planeter , asteroider , etc., från en ändlig uppsättning observationspunkter; eftersom banorna är periodiska var en trigonometrisk interpolation ett naturligt val. Se även Heideman et al. (1984).
Tillämpningar inom numerisk beräkning
Chebfun , ett helt integrerat mjukvarusystem skrivet i MATLAB för beräkning med funktioner, använder trigonometrisk interpolation och Fourier-expansion för beräkning med periodiska funktioner. Många algoritmer relaterade till trigonometrisk interpolation är lätt tillgängliga i Chebfun ; flera exempel finns här .
- Kendall E. Atkinson, An Introduction to Numerical Analysis (2nd edition), Avsnitt 3.8. John Wiley & Sons, New York, 1988. ISBN 0-471-50023-2 .
- MT Heideman, DH Johnson och CS Burrus, " Gauss and the history of the fast Fourier transform ," IEEE ASSP Magazine 1 (4), 14–21 (1984).
- GB Wright, M. Javed, H. Montanelli och LN Trefethen, " Extension of Chebfun to periodic functions ," SIAM. J. Sci. Comput. 37 (2015), C554-C573
- A. Zygmund, Trigonometric Series , Volym II, Kapitel X, Cambridge University Press, 1988.