Metody numeryczne fizyki/Aproksymacja

W poprzednim rozdziale rozpatrywaliśmy interpolację funkcji, gdy liczba punktów (węzłów) jest istotnie duża, to należało by zbudować wielomian takiego stopnia ile jest węzłów. Interpolacja jest z tego względu niewygodna. Jeśli każdy punkt interpolowany posiada pewien błąd pomiarowy, to interpolowanie staje się zbyteczne, ze względu na to lepszym problem natomiast jest aproksymacja, która przechodzi pomiędzy punktami, ale to aproksymacja funkcji f(x) polega na wyznaczników takich współczynników aSzablon:Sub, aSzablon:Sub,...,aSzablon:Sub, które występują w funkcji aproksymującej: Szablon:CentrujWzór Aproksymacja dana wzorem Szablon:LinkWzór nazywamy aproksymacją liniową. A maszynach cyfrowych, często ogromną rolę odgrywa aproksymacja wymierna, którą to piszemy: Szablon:CentrujWzór Aby powiedzieć, co to jest aproksymacja funkcji należy wprowadzić pojęcie normy funkcji, która to definiujemy w przypadku funkcji ciągłych bez wagi i z wagą kolejno wzorami: Szablon:ElastycznyWiersz

Wprowadzenie do aproksymacji średniokwadratowej

W aproksymacji średniokwadratowej dla funkcji f(x) określonej w przedziale ⟨a,b⟩ poszukujemy minimum całki: Szablon:CentrujWzór lub na zbiorze dyskretnym zamiast całki Szablon:LinkWzór poszukujemy minimum sumy: Szablon:CentrujWzór

Wprowadzenie aproksymacji jednostajnej

W przypadku aproksymacji jednostajnej poszukujemy taką funkcję F(x), dla której jest najmniejsze maksimum różnicy pomiędzy funkcją F(x) a funkcją f(x) określonych na przedziale ⟨a,b⟩: Szablon:CentrujWzór

Omówienie aproksymacji średniokwadratowej

Poszukujemy funkcji aproksymującej, której to piszemy przy pomocy funkcji bazowej φSzablon:Sub(x) i współczynników aSzablon:Sub, przy czym te współczynniki są tak określone, by Szablon:LinkWzór przyjmowało wartość minimalną, przy funkcji wagowej w(xSzablon:Sub) większej od zera, wtedy napiśmy taką funkcję H przy naszych współczynnikach aSzablon:Sub: Szablon:CentrujWzór Aby funkcja względem współczynników aSzablon:Sub , czyli według Szablon:LinkWzór przyjmowała wartość ekstremalną, to wtedy musi zachodzić, że pochodna funkcji H Szablon:LinkWzór względem współczynników aSzablon:Sub powinna być równa zero: Szablon:CentrujWzór Jeśli do warunku na ekstremalną wartość funkcji H, czyli Szablon:LinkWzór, względem współczynników aSzablon:Sub wstawimy definicje funkcji H Szablon:LinkWzór, otrzymujemy: Szablon:CentrujWzór Równość Szablon:LinkWzór sugeruje, że można zdefiniować macierze: Szablon:ElastycznyWiersz Mając zdefiniowane macierze Szablon:LinkWzór, Szablon:LinkWzór i Szablon:LinkWzór możemy napisać równość Szablon:LinkWzór w postaci macierzowej przy nieosobliwej macierzy D: Szablon:CentrujWzór W wyniku aproksymacji średnio-kwadratowej otrzymujemy na podstawie Szablon:LinkWzór, że iloczyn macierzy D (zdefiniowanej przy pomocy funkcji φSzablon:Sub(xSzablon:Sub)) przez wektor A (zdefiniowanej przy pomocy współczynników aproksymacji aSzablon:Sub) jest równa wektorowi f (zdefiniowanej przy pomocy wartości funkcji f(xSzablon:Sub) dla j=0,1,..,m).

Omówienie aproksymacji wielomianowej

Przyjmijmy jako funkcje bazowe ciąg jednomianów xSzablon:Sup, dla i=0,1,2,..,m, do której zastosujemy warunek Szablon:LinkWzór i zmienimy w nim kolejność sumowania, otrzymujemy: Szablon:CentrujWzór Jeśli wprowadzimy następujące oznaczenia: Szablon:ElastycznyWiersz To otrzymamy równość na podstawie oznaczeń Szablon:LinkWzór i Szablon:LinkWzór i wejściowej równości Szablon:LinkWzór: Szablon:CentrujWzór Jak wiadomo układ równań określonych wzorem Szablon:LinkWzór jest układem Cramera o wyznaczniku głównym nie równym zero i stąd możemy wyznaczyć współczynniki aSzablon:Sub, których jest m+1, czyli w ten sposób mamy na podstawie tychże obliczonych współczynników wielomian aproksymacyjny. Jeśli ilość punktów aproksymacyjnych pokrywa się z liczbą stopnia wielomianów aproksymacyjnych, to H=0, w ten sposób funkcja aproksymacyjna staje się funkcją interpolacyjną, zwykle tak powinno być, że funkcja aproksymacyjna zbudowana na podstawie wielomianów, których stopień powinien być o wiele mniejszy niż liczba punktów aproksymacyjnych.

Wielomiany ortogonalne i ich aproksymacja przy pomocy tychże wielomianów

Przy wyznaczaniu funkcji aproksymacyjnej wielomianowej, której bazami są jednomiany odpowiednich potęg, który obliczenia są bardzo pracochłonne, a ponadto ich wyniki są niepewne. Dodatkowo mamy fakt, że przy zmianie stopnia wielomianu aproksymacyjnego wymaga ponownego rozwiązania układu normalnego, co przemawia przeciwko tejże metodzie. Ten fakt przemawia, żeby opisywać problem aproksymacyjny przy pomocy wielomianów ortogonalnych. Wielomianami ortogonalnymi nazywamy wielomiany, które spełniają warunek ortogonalności, oraz ich normy są większe niż zero, które te warunki możemy zapisać wzorami: Szablon:ElastycznyWiersz Wprowadźmy teraz zmienną q, która jest ilorazem różnicy starej zmiennej x i zmiennej xSzablon:Sub przez odstęp h, który to opisuje punkty jednakowo oddalone: Szablon:CentrujWzór Teraz wprowadźmy teraz funkcję Szablon:Formuła, które są wzajemnie ortogonalne, które spełniają warunek ortoganalności Szablon:LinkWzór dla j≠k: Szablon:CentrujWzór Zbudujmy teraz wielomian powiedziany tuż poniżej, której to piszemy wzorem ogólnikowym za pomocą sumy wielomianów o wzrastających stopniu zmiennej q, który każdy z składników jest iloczynem różnic z liczby q i pewnej liczby o zakresie od 0 do k+1: Szablon:CentrujWzór Wielomian Szablon:LinkWzór możemy zapisać w sposób ogólny przy w prowadzeniu oznaczenia qSzablon:Sup, który jest równy iloczynowi różnicy z liczby q i pewnej liczby o zakresie od 0 do k+1, zatem to oznaczenie możemy przepisać wzorem: Szablon:CentrujWzór Wzór Szablon:LinkWzór przy pomocy oznaczenia qSzablon:Sup, który jest zdefiniowany w punkcie Szablon:LinkWzór, możemy przepisać do postaci: Szablon:CentrujWzór Ciąg funkcji Szablon:LinkWzór, który to możemy napisać dla k=0,1,...,m, której kolejne elementy są wielomianami ortogonalnymi, piszemy je jako: Szablon:ElastycznyWiersz Można udowodnić po stosunkowo prostych obliczeniach, że wielomiany Szablon:LinkWzór, które są zapisane k=0,1,2,...,m, są ortogonalne do siebie, gdy one zapisane są na w sposób: Szablon:CentrujWzór Wzór Szablon:LinkWzór nazywamy wielomianami Grama, które są określone dla k=0,1,2,3,..m dla n+1 równoległych węzłów xSzablon:Sub, xSzablon:Sub,...,xSzablon:Sub. Wzór aproksymacyjny, który jest oparty na wielomianach Grama Szablon:LinkWzór jest odpowiednikiem wzoru Szablon:LinkWzór, piszemy: Szablon:CentrujWzór Jeśli weźniemy $m\le n$, to stałe sSzablon:Sub i cSzablon:Sub piszemy: Szablon:ElastycznyWiersz Gdy punkty nie są równoodległe do siebie, to objeżmy sobie pewien ciąg wielomianów φSzablon:Sub, i udowodnimy za pomocą indukcji matematyczne, że ten obrany wielomian jest ortogonalny, który to zapisujemy iteracyjnie w postaci: Szablon:ElastycznyWiersz W której to stałe βSzablon:Sub i αSzablon:Sub możemy określić wzorami: Szablon:ElastycznyWiersz Sprawdźmy, czy wielomian φSzablon:Sub jest wielomianem ortogonalnym z wielomianem φSzablon:Sub jako pierwszy krok twierdzenia o indukcji matematycznej: Szablon:CentrujWzór Następnym krokiem jest wykazanie, czy wielomian Szablon:LinkWzór w następnym założeniu indukcyjnym jest wielomianem ortogonalnym do pozostałych wielomianów, zatem na podstawie tego możemy powiedzieć: Szablon:CentrujWzór A także wykażemy dla zupełności wykładu, czy wielomian φSzablon:Sub(x) jest ortogonalny z wielomianem φSzablon:Sub: Szablon:CentrujWzór Możemy zbudować teraz wielomian ySzablon:Sub(x), który to jest odpowiednikiem wielomianu aproksymującego daną funkcję f(x), czyli wielomianu Szablon:LinkWzór, który to piszemy: Szablon:CentrujWzór Piszemy stałą bSzablon:Sub występujących w punkcie Szablon:LinkWzór, którą zapiszemy przy pomocy ilorazu funkcji CSzablon:Sub i funkcji SSzablon:Sub: Szablon:ElastycznyWiersz

Średniokwadratowa aproksymacja funkcji ciągłych

Weźmy teraz funkcję aproksymacyjną P(x), którą podobnie będziemy definiować jak w punkcie Szablon:LinkWzór, ale ta funkcja jest ciągłą funkcją jego argumentu, co dotyczy również funkcji f(x) aproksymowanej, których średniokwadratowa norma piszemy wedle następującego schematu: Szablon:CentrujWzór Aby wyznaczyć najmniejszą wartość funkcji HSzablon:Sub należy policzyć wszystkie pochodne tejże funkcji aproksymacyjnej względem współczynników aSzablon:Sub, aSzablon:Sub,...,aSzablon:Sub, które powinny przyjmować wartość zerową, stąd możemy wyznaczyć te nasze współczynniki, dzięki której możemy wyznaczyć wielomian aproksymacyjny.

Omówienie aproksymacji trygonometrycznej

Zagadnieniach naszych często spotykamy się z funkcjami, tzn. z funkcjami okresowymi o pewnym okresie, które to są zdefiniowane jako funkcja aproksymująca w postaci kombinacji liniowych funkcji trygonometrycznych, która zależy od zmiennej x ciągłej, definicję tejże funkcji piszemy: Szablon:CentrujWzór Bardzo interesującym przypadkiem, gdy funkcja f(x) ma okres 2L, i dalej na podstawie tego obierzmy sobie punkty aproksymujące, których postać jest następująca: Szablon:CentrujWzór Najpierw musimy udowodnić tożsamość matematyczną korzystając z definicji liczby zespolonej w postaci eksponentu Szablon:LinkWzór i Szablon:LinkWzór, które to wykorzystamy do liczenia wyrażenia poniżej wykorzystując, że węzły aproksymacji są przestawione według Szablon:LinkWzór, na tej podstawie dla k≠ 0 możemy napisać: Szablon:CentrujWzór Następnym krokiem jest wykorzystanie tożsamości policzonej w trzech punktach poniżej: Szablon:CentrujWzór Szablon:CentrujWzór Szablon:CentrujWzór Wielomian trygonometryczny Szablon:LinkWzór możemy zapisać używając, że xSzablon:Sub jest zdefiniowane sposobem Szablon:LinkWzór, zatem możemy podać ten nasz wielomian: Szablon:CentrujWzór Aby wyznaczyć współczynniki wielomianu aSzablon:Sub i bSzablon:Sub należy wykorzystać warunki ortogonalności Szablon:LinkWzór, Szablon:LinkWzór i Szablon:LinkWzór, a także będziemy korzystać z aproksymacji średnio-kwadratowej Szablon:LinkWzór dla funkcji f(x) określonej na dyskretnej ilości zmiennych: Szablon:CentrujWzór Zatem na podstawie Szablon:LinkWzór te nasze współczynniki aSzablon:Sub i bSzablon:Sub są określone na postawie wyliczonych kolejnych pochodnych pierwszego rzędu względem stałych, bo norma średniokwadratowa róźnicy funkcji aproksymowanej i aproksymujacej przyjmuje wartość najmniejszą dla funkcji aproksymującej Szablon:LinkWzór: Szablon:CentrujWzór Szablon:CentrujWzór

Funkcje sklejane i aproksymacja za pomocą niej

Omówimy tutaj aproksymację średnio-kwadratową dla węzłów aproksymacji jednakowo oddalonych xSzablon:Sub=a+ih przy ${}_{h=\frac{b-a}{n}}$ dla funkcji sklejanych trzeciego stopnia, zatem funkcja aproksymacyjna można przestawić jako kombinację liniową funkcji trzeciego stopnia ${\mathrm{\Phi }}_i^3(x)$ określonych w przedziale: Szablon:CentrujWzór Będziemy teraz rozważać aproksymację średnio-kwadratową funkcji ciągłej f(x), której norma poniżej przyjmuje wartość najmniejszą: Szablon:CentrujWzór Funkcja Szablon:LinkWzór jest funkcją parametrów cSzablon:Sub, którego chcemy napisać jego wartość najmniejszą, zatem musimy policzyć jego pierwszą pochodną względem odpowiednich współczynników, w ten sposób mamy n+3 niewiadomych określonych n+3 równań, których to wyznaczamy z równania zapisanego dla dowolnego j=-1,0,1,..n+1, zatem na podstawie tego możemy powiedzieć: Szablon:CentrujWzór Jeśli wprowadzimy następujące oznaczenie, która jest całką na przedziale od a do b na iloczynie funkcji ${\mathrm{\Phi }}_j^3$ i ${\mathrm{\Phi }}_i^3$, i ta cała całka jest podzielona przez liczbę h, zatem zapis równań Szablon:LinkWzór piszemy wzorami dla i=-1,0,1,..,n+1: Szablon:ElastycznyWiersz Jeśli wyznacznik główny tego rozwinięcia Szablon:LinkWzór, czyli określonej przez elementy Szablon:LinkWzór, jest nierówny zero, to mamy wtedy określone elementy cSzablon:Sub, które jednoznacznie są określone.

Następnym naszym etapem jest rozważanie funkcji f(x) określonej na elementach dyskretnych, dla którego warunek na aprosykację średniokwadratową Szablon:LinkWzór piszemy przy wadzie w(xSzablon:Sub) równą jeden: Szablon:CentrujWzór Aby funkcja Szablon:LinkWzór przyjmowała wartość najmniejszą, należy policzyć jego pierwszą pochodną względem współczynników cSzablon:Sub i przyrównać tą pochodną do zera, zatem na podstawie tego otrzymujemy układ równań na współczynniki cSzablon:Sub przy definicji elementów macierzy bSzablon:Sub podanych w tym samej linijce: Szablon:ElastycznyWiersz Jeśli wyznacznik główny tego rozwinięcia Szablon:LinkWzór, czyli określonej przez elementy Szablon:LinkWzór jest nierówny zero, to mamy wtedy określone elementy cSzablon:Sub, które jednoznacznie są określone.

Aproksymacja jednostajna przy pomocy wielomianów

Każdą funkcję możemy aproksymować wielomianami dowolnego stopnia Szablon:LinkWzór. Jeśli opis danej funkcji jest określonej przy pomocy szeregów Taylora, to wynik jej może być obcięty do wielomianu o stopniu jakiś tam, zatem możemy wybrać funkcję aproksymującą o stopniu n zapisując ją: Szablon:CentrujWzór Stopień wielomianu Szablon:LinkWzór jest taki, żeby wyrażenie zapisane poniżej miało najmniejszą wartość w przedziale <a,b>: Szablon:CentrujWzór przy wyznaczeniu wielomianu najlepszego stopnia, często korzysta się z twierdzenia Borela, który powiedział i wykazał , że dla każdej funkcji ciągłej f(x) na omawianej przedziale i dowolnej liczby naturalnej n istnieje dokładnie jeden wielomian, który aproksymuje funkcję f(x).

Metoda aproksymacji jednostajnych, czyli metoda szeregów potęgowych

Najlepszą metodą przy aproksymacji funkcji f(x) ciągłej na przedziale <a,b> jest rozwiniecie w postaci szeregów potęgowych Taylora, który to rozwiniemy w otoczeniu punktu xSzablon:Sub o promieniu zbieżności δ, co można powiedzieć: Szablon:CentrujWzór Rozwinięcie funkcji f(x) w szereg Taylora z dokładności do n-tego stopnia piszemy wzorem w otoczeniu punktu xSzablon:Sub: Szablon:CentrujWzór Różnica funkcji aproksymującej WSzablon:Sub i funkcji aproksymowanej WSzablon:Sub(x) jest wyrażona wzorem znanej z analizy matematycznej, którą to piszemy: Szablon:CentrujWzór Jeśli maksymalną wartość n+1 pochodnej funkcji f(x) na rozważanym przedziale określimy przez MSzablon:Sub, to według aproksymacji jednostajnej na podstawie Szablon:LinkWzór możemy powiedzieć, że zachodzi: Szablon:CentrujWzór Za pomocą funkcji Szablon:LinkWzór możemy policzyć dowolne przybliżenie funkcji dla dowolnego przybliżenia, który zależy od stopnia aproksymującej funkcji.

Naprawdę szybka transformacja Fouriera

Każdą funkcję określoną w n różnych punktach określonych na "n" punktach ${}_{x_{\beta }=\frac{2\pi \beta }{n}\text{, }\beta =0,1...,n-1}$ możemy przybliżać wielomianami trygonometrycznymi: Szablon:CentrujWzór Można udowodnić, że wzór Szablon:LinkWzór jest równoważny wzorowi: Szablon:CentrujWzór

• gdzie θ=1, mamy: Szablon:Formuła dla n parzystych.
• gdzie θ=0, mamy Szablon:Formuła dla n nieparzystych.

Udowodnijmy przejście od wzoru Szablon:LinkWzór do wzoru Szablon:LinkWzór dla n parzystego i nieparzystego. Dla n parzystego wzór Szablon:LinkWzór przepisujemy następująco: Szablon:CentrujWzór Jak można dalej udowodnić, że otrzymany końcowy wzór Szablon:LinkWzór jest równoważny wzorowi, które po krótkich perypetiach otrzymujemy Szablon:LinkWzór dla n parzystego. Rozpatrzmy teraz przypadek końcowy, gdy n jest nieparzyste, zatem w takim razie równość Szablon:LinkWzór możemy zapisać w sposób: Szablon:CentrujWzór Jak można dalej udowodnić, że otrzymany końcowy wzór Szablon:LinkWzór jest równoważna wzorowi, które po krótkich perypetiach otrzymujemy Szablon:LinkWzór dla n nieparzystego. Za pomocą aproksymacji średnio-kwadratowej możemy policzyć współczynniki cSzablon:Sub występujące we wzorze Szablon:LinkWzór i współczynniki aSzablon:Sub i bSzablon:Sub występujące we wzorze: Szablon:ElastycznyWiersz Naszym celem jest wyznaczenie współczynników Szablon:LinkWzór mając ciąg wartości xSzablon:Sub.

Wyliczanie współczynników cSzablon:Sub

Jest to metoda polegająca, która nosi nazwę szybkiej transformacji Fouriera. Wprowadźmy teraz nasze obliczenia wprowadzając oznaczenia: Szablon:ElastycznyWiersz Wzór Szablon:LinkWzór zapisujemy przy pomocy oznaczeń Szablon:LinkWzór i Szablon:LinkWzór: Szablon:CentrujWzór Każdą liczbę naturalną możemy rozłożyć na czynniki różne od jedności, co są iloczynami liczb rSzablon:Sub, którego wskaźnik jest od liczby i=1 do liczby p, co liczbę n możemy zapisać: Szablon:CentrujWzór Wprowadźmy teraz oznaczenie liczby nSzablon:Sub, które to mamy napisać dla v=0,1,..p-1, która jest iloczynem liczby rSzablon:Sub, które to "i" jest od v+1 do p, co można powiedzieć: Szablon:CentrujWzór Z równości Szablon:LinkWzór dla nSzablon:Sub możemy przyjąć, że nSzablon:Sub=1. Wzór Szablon:LinkWzór na podstawie Szablon:LinkWzór piszemy następującą tożsamością, która jest iloczynem liczb rSzablon:Sub od i=1 do v przez czynnik nSzablon:Sub: Szablon:CentrujWzór Każdą liczbę k w przedziału Szablon:Formuła, którą tą liczbę definiujemy jako sumę liczb zdefiniowanej w punkcie nSzablon:SubSzablon:LinkWzór pomnożonej przez ${}_{0\le {\alpha }_i\le r_i-1}$, możemy zapisać: Szablon:CentrujWzór Współczynniki αSzablon:Sub są elementami pewnego zbioru, który to posiada elementy jako liczby naturalne od 0 do rSzablon:Sub, co matematycznie: Szablon:CentrujWzór Każdy ułamek Szablon:Formuła mający jednoznaczny zapis dla dowolnej liczby naturalnej $\beta \in ⟨0;n-1⟩$, po wykorzystaniu tożsamości Szablon:LinkWzór, który zachodzi dla $0\le l_i\le r_i-1$, możemy zapisać w postaci: Szablon:CentrujWzór Współczynniki lSzablon:Sub, która jest elementem pewnego wzoru, który to zbiór posiada elementy z liczby naturalnej od 0 do rSzablon:Sub, co matematycznie to własność naszej liczby piszemy: Szablon:CentrujWzór Dodatkowo oznaczmy liczbę naturalną kSzablon:Sub i ułamek $\frac{{\beta }_v}{n_v}$, które są zdefiniowane przy pomocy liczby αSzablon:Sub Szablon:LinkWzór i lSzablon:Sub Szablon:LinkWzór, wiedząc, że zachodzi kSzablon:Sub<nSzablon:Sub, dla zmienności wskaźnika dolnego v od 0 do p (p=0,1,..p). Szablon:ElastycznyWiersz Napiszmy teraz wyraz, który jest iloczynem liczby k i β podzielonej przez liczbę n, zatem w takim razie korzystając z Szablon:LinkWzór i Szablon:LinkWzór możemy napisać równość, którą to piszemy mając na uwadze stałą całkowitą M występująca w obliczeniach poniżej: Szablon:CentrujWzór Mając już obliczenia przeprowadzone w punkcie Szablon:LinkWzór i definicji zmiennej w Szablon:LinkWzór podniesionej do potęgi o wykładniku kβ, wtedy możemy zapisać to wyrażenie w postaci: Szablon:CentrujWzór Wzór Szablon:LinkWzór, który przedstawia wzór na współczynniki cSzablon:Sub, które są współczynnikami rozwinięcia Szablon:LinkWzór, piszemy wzorem: Szablon:CentrujWzór Człony cSzablon:Sup występujące we wzorze Szablon:LinkWzór są to człony, które nazywamy współczynnikami manipulacyjnymi. Ze wzoru Szablon:LinkWzór współczynniki manipulacyjne możemy obliczyć kolejno rozpoczynając od obliczenia współczynnika cSzablon:Sup, który to piszemy: Szablon:CentrujWzór Gdy założymy stałość lSzablon:Sub, lSzablon:Sub,..,lSzablon:Sub przy każdej jego możliwości otrzymujemy ${}_{\frac{n}{r_p}}$ transformat Fouriera funkcji ${}_{f\left(\frac{2\pi \beta }{n}\right)}$, których każda posiada Szablon:Formuła operacji. Przy wykonaniu drugiej operacji względem Szablon:LinkWzór po wyznaczaniu współczynników cSzablon:Sup(lSzablon:Sub,..,lSzablon:Sub) do cSzablon:Sup(lSzablon:Sub,..,lSzablon:Sub,αSzablon:Sub) przejdźmy do drugiego kroku by policzyć następny współczynnik manipulacyjny: Szablon:CentrujWzór Gdy założymy stałość lSzablon:Sub, lSzablon:Sub,..,lSzablon:Sub przy każdej jego możliwości otrzymujemy ${}_{\frac{n}{r_{p-1}}}$ transformat Fouriera, których każda posiada Szablon:Formuła operacji. Po tym krokach otrzymujemy współczynniki manipulacyjny jako: Szablon:CentrujWzór W rezultacie otrzymujemy cSzablon:Sub według Szablon:LinkWzór w n(rSzablon:Sub+rSzablon:Sub+...+rSzablon:Sub) operacjach.

Metoda Cooleya-Tukeya

Tą metodę stosuje się gdy n jest całkowitą potęgą dwójki, tzn. zachodzi n=2Szablon:Sup. Obierzmy sobie liczbę β=2βSzablon:Sub, która jest liczbą parzystą, lub gdy β=2βSzablon:Sub+1, gdy β jest liczbą nieparzystą, wtedy wzór na współczynniki Fouriera cSzablon:Sub Szablon:LinkWzór piszemy: Szablon:CentrujWzór Jeśli odpowiednio oznaczymy liczbę k poprzez zmienną α wedle sposobu Szablon:Formuła, gdzie mamy kSzablon:Sub=0,1,..,n/2-1, α=0,1, zatem możemy teraz napisać tożsamość, wykorzystując przy tym fakt wSzablon:Sup=1 przy liczbie "w" zdefiniowaną według Szablon:LinkWzór: Szablon:CentrujWzór Wprowadźmy teraz dwie funkcje zależne od liczby kSzablon:Sub zdefiniowane: Szablon:ElastycznyWiersz W ten sposób wzór na nasz współczynnik cSzablon:Sub Szablon:LinkWzór, na podstawie tożsamości napisanej wzorami Szablon:LinkWzór i Szablon:LinkWzór, możemy napisać: Szablon:CentrujWzór Na podstawie definicji liczby k poprzez liczbę kSzablon:Sub wynika, że jeśli ${}_{k=0,1,..,\frac{n}{2}-1}$, wtedy mamy ${}_{k_1=k}$, bo α=0, a jeśli Szablon:Formuła, wtedy na pewno mamy Szablon:Formuła, bo α=1. Dla "n" będącego potęgą dwójki wymagana jest ilość operacji 2nlogSzablon:Subn dla szybkiej transformacji Fouriera.

Algorytm szybkiego mnożenia

Określmy ciąg współczynników Szablon:Formuła, które będą współczynnikami zespolonymi, a przez {wSzablon:Sup} dla k=0,1,..,n-1 niech będzie ciag pierwiastków z jedności. Zdefiniujmy macierz A[i,j]=wSzablon:Sup dla i,j=0,1,2,..,n-1, wtedy możemy określić wektor Szablon:Formuła, którego i-ty element jest: Szablon:CentrujWzór Bardzo łatwo można wykazać, że elementami odwrotnymi do macierzy o elementach A[i,j] jest macierz o elementach ${}_{A^{-1}[i,j]=\frac{1}{n}{w}^{-ijmodn}}$, wtedy możemy zdefiniować transformację odwrotną według schematu Szablon:Formuła: Szablon:CentrujWzór Transformatę Szablon:LinkWzór nazywamy dyskretną odwrotną transformatą Fouriera. Oczywiste jest, że zachodzi Szablon:Formuła. Obieżmy sobie ciąg dwóch wektorów pionowych Szablon:Formuła i Szablon:Formuła, to splotem wektorów Szablon:Formuła i Szablon:Formuła nazywamy wektor o 2n-1 współczynnikach $\overrightarrow{c}=[c_0,c_1,...,c_{2n-1}{]}^T$, które elementy tego wektora piszemy: Szablon:CentrujWzór Jak się ukazuje współczynniki cSzablon:Sub są identyczne ze współczynnikami iloczynu wielomianów P(x) oraz Q(x), które są stopnia n-1, których definicje: Szablon:ElastycznyWiersz Iloczyn wielomianu P(x) Szablon:LinkWzór i Q(x) Szablon:LinkWzór definiujemy jako splot tychże funkcji w postaci: Szablon:CentrujWzór Aby uzyskać wielomiany 2n-2 stopnia z P(x) i z Q(x), to w tych wielomianach współczynniki dla k<n są współczynnikami niezerowymi w ogólności, a dla k≥n współczynniki tychże wielomianów są równe tożsamościowo zeru. Współczynniki wielomianu P(x)Q(x) możemy policzyć: Szablon:CentrujWzór Standardowo uzyskanie cSzablon:Sub wymaga nSzablon:Sup operacji, ale jeśli rozłożymy liczbę n na czynniki pierwsze, tzn. n=rSzablon:SubrSzablon:Sub...rSzablon:Sub, to powyższa operacja wymaga n(rSzablon:Sub+rSzablon:Sub+...+rSzablon:Sub) operacji. Można wykazać, że dla wielomianu interpolacyjnego stopnia n przy n+1 więzach wymagana klasycznie ilość operacji jest nSzablon:Sup, a użycie szybkiej transformacji Fouriera wymaga Szablon:Formuła operacji.

Przybliżenie Padégo, czyli przybliżenie wielomianami wymiernymi

Jak się okazuje lepszą dokładność uzyskuje się przybliżając funkcję f(x) wielomianami wymiernymi, który piszemy przez iloraz wielomianu LSzablon:Sub(x) stopnia n-tego przez wielomian MSzablon:Sub stopnia k-tego: Szablon:CentrujWzór Wielomian wymierny Szablon:LinkWzór daje największą dokładność niż przybliżenie wielomianami N=n+k stopnia wielomianami danymi wzorami Taylora czy Maclaurina. Natomiast, gdy x jest równe zeru, to wielomian aproksymowany jest równy wielomianowi aproksymującemu Szablon:LinkWzór, które dla porządku dziennego piszemy poprzez wzór: Szablon:CentrujWzór Wielomiany LSzablon:Sub(x) i MSzablon:Sub(x) piszemy w postaci wzorów Maclaurina, czyli w postaci przybliżenia Taullora względem punktu zerowego. Szablon:ElastycznyWiersz Ponieważ wielomian MSzablon:Sub(x) dla x=0 powinien być nie równy zero, więc bSzablon:Sub≠0, więc przyjmijmy, że bSzablon:Sub=1. Funkcję f(x) możemy rozłożyć w szereg Maclaurina opisując go jako szereg potęgowy nieskończony, który piszemy: Szablon:CentrujWzór Mając na uwadze szereg LSzablon:Sub(x) Szablon:LinkWzór oraz szereg MSzablon:Sub(x) Szablon:LinkWzór, a także dokładne rozłożenie funkcji f(x) w szereg Maclaurina Szablon:LinkWzór, to możemy napisać błąd przybliżenia funkcji f(x) funkcją aproksymującą wymierną Szablon:LinkWzór: Szablon:CentrujWzór Chcemy, by zachodziło Szablon:Formuła i Szablon:Formuła dla m=0,1,2,..,k+n, to powinno być, że wszystkie wyrazy w liczniku Szablon:LinkWzór powinny być równe zero dla potęg mniejszych niż n+k+1, zatem licznik powyższego wyrażenia możemy zapisać: Szablon:CentrujWzór Z powyższych wniosków natychmiast otrzymujemy Szablon:Formuła dla r=0,1,2,..,n, ale też mamy bSzablon:Sub=0 dla j>k i cSzablon:Sub=0 dla j<0, także Szablon:Formuła dla s=0,1,2,..,k-1. Z analizy błędów dla otoczenia zerowego najmniejszy błąd się uzyskuje gdy n=k lub n=k+1, błąd rośnie gdy oddalamy się coraz dalej od punktu zerowego.

Przybliżenia szeregami Czebyszewa

Przybliżenie Padégo nie jest najlepsze, ponieważ błąd wielomianów wymiernych rośnie wraz z oddalaniem się od punktu zerowego, a na końcach przedziału błędy mogą być naprawdę duże w aproksymacji jednostajnej, podobnie jest z przybliżeniami Maclaurina, dlatego stosuje się szeregi Czebyszewa, który błąd liczenia zmiennej układa się równomiernie wzdłuż całego przedziału. Metodą przybliżenia funkcji f(x) przy pomocy wielomianów Czebyszewa jest zapisana jako: Szablon:CentrujWzór Funkcję f(x) będziemy przybliżać wielomianami TSzablon:Sub(x), którego definicja względem współczynników aSzablon:Sub i bSzablon:Sub jest: Szablon:CentrujWzór Błąd wybrania funkcji Szablon:LinkWzór aproksymującej funkcję aproksymowaną f(x), pisaną względem Szablon:LinkWzór, doprowadzając dwa ułamki wymierne do wspólnego mianownika, piszemy wzorem: Szablon:CentrujWzór Podobnie jak dla przybliżenia Padégo licznik wyrażenia Szablon:LinkWzór można napisać, że on jest równy pewnej kombinacji liniowych wielomianów Czebyszewa o wskaźnikach większych lub równych n+1. Szablon:CentrujWzór Wielomiany Czebyszewa spełniają tożsamość rekurencyjną słuszna na tychże wielomianów dla dowolnych wskaźników naturalnych "i" i "j" dla x mieszczącego się w przedziale (-1,1): Szablon:CentrujWzór Jeśli wykorzystamy Szablon:LinkWzór, wtedy lewą stronę równania Szablon:LinkWzór piszemy: Szablon:CentrujWzór Z obliczeń Szablon:LinkWzór i równości Szablon:LinkWzór otrzymujemy od razu trzy tożsamości na współczynniki aSzablon:Sub, dla r=0,1,2,..,∞: Szablon:ElastycznyWiersz Szablon:CentrujWzór