Metody numeryczne fizyki/Aproksymacja

Metody numeryczne fizyki
Metody numeryczne fizyki
Aproksymacja

Licencja
Autor: Mirosław Makowiecki
Absolwent UMCS Fizyki Komputerowej Uniwersytetu Marii Curie-Skłodowskiej w Lublinie
Email: miroslaw(kropka)makowiecki(małpa)gmail(kropka)pl
Dotyczy: książki, do której należy ta strona, oraz w niej zawartych stron i w nich podstron, a także w nich kolumn, wraz z zawartościami.
Użytkownika książki, do której należy ta strona, oraz w niej zawartych stron i w nich podstron, a także w nich kolumn, wraz z zawartościami nie zwalnia z odpowiedzialności prawnoautorskiej nieprzeczytanie warunków licencjonowania.
Umowa prawna: Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń.
Autor tej książki dołożył wszelką staranność, aby informacje zawarte w książce były poprawne i najwyższej jakości, jednakże nie udzielana jest żadna gwarancja, czy też rękojma. Autor nie jest odpowiedzialny za wykorzystanie informacji zawarte w książce, nawet jeśli wywołaby jakąś szkodę, straty w zyskach, zastoju w prowadzeniu firmy, przedsiębiorstwa lub spółki bądź utraty informacji, niezależnie czy autor (a nawet Wikibooks) został powiadomiony o możliwości wystąpienie szkód. Informacje zawarte w książce mogą być wykorzystane tylko na własną odpowiedzialność.


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 a0, a1,...,an, które występują w funkcji aproksymującej:

(2.1)

Aproksymacja dana wzorem (2.1) nazywamy aproksymacją liniową. A maszynach cyfrowych, często ogromną rolę odgrywa aproksymacja wymierna, którą to piszemy:

(2.2)

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:

(2.3)
(2.4)

Wprowadzenie do aproksymacji średniokwadratowej edytuj

W aproksymacji średniokwadratowej dla funkcji f(x) określonej w przedziale ⟨a,b⟩ poszukujemy minimum całki:

(2.5)

lub na zbiorze dyskretnym zamiast całki (2.5) poszukujemy minimum sumy:

(2.6)

Wprowadzenie aproksymacji jednostajnej edytuj

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⟩:

(2.7)

Omówienie aproksymacji średniokwadratowej edytuj

Poszukujemy funkcji aproksymującej, której to piszemy przy pomocy funkcji bazowej φi(x) i współczynników ai, przy czym te współczynniki są tak określone, by (2.5) przyjmowało wartość minimalną, przy funkcji wagowej w(xj) większej od zera, wtedy napiśmy taką funkcję H przy naszych współczynnikach ai:

(2.8)

Aby funkcja względem współczynników ai , czyli według (2.8) przyjmowała wartość ekstremalną, to wtedy musi zachodzić, że pochodna funkcji H (2.8) względem współczynników ak powinna być równa zero:

(2.9)

Jeśli do warunku na ekstremalną wartość funkcji H, czyli (2.9), względem współczynników ak wstawimy definicje funkcji H (2.8), otrzymujemy:

(2.10)

Równość (2.10) sugeruje, że można zdefiniować macierze:

(2.11)
(2.12)
(2.13)

Mając zdefiniowane macierze (2.11), (2.12) i (2.13) możemy napisać równość (2.10) w postaci macierzowej przy nieosobliwej macierzy D:

(2.14)

W wyniku aproksymacji średnio-kwadratowej otrzymujemy na podstawie (2.14), że iloczyn macierzy D (zdefiniowanej przy pomocy funkcji φi(xj)) przez wektor A (zdefiniowanej przy pomocy współczynników aproksymacji ai) jest równa wektorowi f (zdefiniowanej przy pomocy wartości funkcji f(xj) dla j=0,1,..,m).

Omówienie aproksymacji wielomianowej edytuj

Przyjmijmy jako funkcje bazowe ciąg jednomianów xi, dla i=0,1,2,..,m, do której zastosujemy warunek (2.10) i zmienimy w nim kolejność sumowania, otrzymujemy:

(2.15)

Jeśli wprowadzimy następujące oznaczenia:

(2.16)
(2.17)

To otrzymamy równość na podstawie oznaczeń (2.16) i (2.17) i wejściowej równości (2.15):

(2.18)

Jak wiadomo układ równań określonych wzorem (2.18) jest układem Cramera o wyznaczniku głównym nie równym zero i stąd możemy wyznaczyć współczynniki ai, 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 edytuj

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:

(2.19)
(2.20)
(2.21)

Wprowadźmy teraz zmienną q, która jest ilorazem różnicy starej zmiennej x i zmiennej x0 przez odstęp h, który to opisuje punkty jednakowo oddalone:

(2.22)

Teraz wprowadźmy teraz funkcję , które są wzajemnie ortogonalne, które spełniają warunek ortoganalności (2.19) dla j≠k:

(2.23)

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:

(2.24)

Wielomian (2.24) możemy zapisać w sposób ogólny przy w prowadzeniu oznaczenia q[k], 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:

(2.25)

Wzór (2.24) przy pomocy oznaczenia q[k], który jest zdefiniowany w punkcie (2.25), możemy przepisać do postaci:

(2.26)

Ciąg funkcji (2.26), który to możemy napisać dla k=0,1,...,m, której kolejne elementy są wielomianami ortogonalnymi, piszemy je jako:

(2.27)
(2.28)

Można udowodnić po stosunkowo prostych obliczeniach, że wielomiany (2.28), które są zapisane k=0,1,2,...,m, są ortogonalne do siebie, gdy one zapisane są na w sposób:

(2.29)

Wzór (2.29) nazywamy wielomianami Grama, które są określone dla k=0,1,2,3,..m dla n+1 równoległych węzłów x0, x1,...,xn. Wzór aproksymacyjny, który jest oparty na wielomianach Grama (2.29) jest odpowiednikiem wzoru (2.1), piszemy:

(2.30)

Jeśli weźniemy , to stałe sk i ck piszemy:

(2.31)
(2.32)

Gdy punkty nie są równoodległe do siebie, to objeżmy sobie pewien ciąg wielomianów φi, i udowodnimy za pomocą indukcji matematyczne, że ten obrany wielomian jest ortogonalny, który to zapisujemy iteracyjnie w postaci:

(2.33)
(2.34)
(2.35)

W której to stałe βj i αj+1 możemy określić wzorami:

(2.36)
(2.37)

Sprawdźmy, czy wielomian φ2 jest wielomianem ortogonalnym z wielomianem φ1 jako pierwszy krok twierdzenia o indukcji matematycznej:


(2.38)

Następnym krokiem jest wykazanie, czy wielomian (2.33) w następnym założeniu indukcyjnym jest wielomianem ortogonalnym do pozostałych wielomianów, zatem na podstawie tego możemy powiedzieć:

(2.39)

A także wykażemy dla zupełności wykładu, czy wielomian φj+1(x) jest ortogonalny z wielomianem φj-1:


(2.40)

Możemy zbudować teraz wielomian ym(x), który to jest odpowiednikiem wielomianu aproksymującego daną funkcję f(x), czyli wielomianu (2.30), który to piszemy:

(2.41)

Piszemy stałą bk występujących w punkcie (2.41), którą zapiszemy przy pomocy ilorazu funkcji Ck i funkcji Sk:

(2.42)
(2.43)
(2.44)

Średniokwadratowa aproksymacja funkcji ciągłych edytuj

Weźmy teraz funkcję aproksymacyjną P(x), którą podobnie będziemy definiować jak w punkcie (2.1), 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:

(2.45)

Aby wyznaczyć najmniejszą wartość funkcji Hn należy policzyć wszystkie pochodne tejże funkcji aproksymacyjnej względem współczynników a0, a1,...,an, 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 edytuj

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:

(2.46)

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:

(2.47)

Najpierw musimy udowodnić tożsamość matematyczną korzystając z definicji liczby zespolonej w postaci eksponentu (MMF-8.4) i (MMF-8.2), które to wykorzystamy do liczenia wyrażenia poniżej wykorzystując, że węzły aproksymacji są przestawione według (2.47), na tej podstawie dla k≠ 0 możemy napisać:


(2.48)

Następnym krokiem jest wykorzystanie tożsamości policzonej w trzech punktach poniżej:

(2.49)
(2.50)
(2.51)

Wielomian trygonometryczny (2.46) możemy zapisać używając, że xi jest zdefiniowane sposobem (2.47), zatem możemy podać ten nasz wielomian:

(2.52)

Aby wyznaczyć współczynniki wielomianu aj i bj należy wykorzystać warunki ortogonalności (2.49), (2.50) i (2.51), a także będziemy korzystać z aproksymacji średnio-kwadratowej (2.6) dla funkcji f(x) określonej na dyskretnej ilości zmiennych:

(2.53)

Zatem na podstawie (2.53) te nasze współczynniki ak i bk 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 (2.52):

(2.54)
(2.55)

Funkcje sklejane i aproksymacja za pomocą niej edytuj

Omówimy tutaj aproksymację średnio-kwadratową dla węzłów aproksymacji jednakowo oddalonych xi=a+ih przy dla funkcji sklejanych trzeciego stopnia, zatem funkcja aproksymacyjna można przestawić jako kombinację liniową funkcji trzeciego stopnia określonych w przedziale:

(2.56)

Będziemy teraz rozważać aproksymację średnio-kwadratową funkcji ciągłej f(x), której norma poniżej przyjmuje wartość najmniejszą:

(2.57)

Funkcja (2.56) jest funkcją parametrów ck, 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ć:

(2.58)

Jeśli wprowadzimy następujące oznaczenie, która jest całką na przedziale od a do b na iloczynie funkcji i , i ta cała całka jest podzielona przez liczbę h, zatem zapis równań (2.58) piszemy wzorami dla i=-1,0,1,..,n+1:

(2.59)
(2.60)

Jeśli wyznacznik główny tego rozwinięcia (2.59), czyli określonej przez elementy (2.60), jest nierówny zero, to mamy wtedy określone elementy ci, 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ą (2.53) piszemy przy wadzie w(xi) równą jeden:

(2.61)

Aby funkcja (2.61) przyjmowała wartość najmniejszą, należy policzyć jego pierwszą pochodną względem współczynników ci i przyrównać tą pochodną do zera, zatem na podstawie tego otrzymujemy układ równań na współczynniki ci przy definicji elementów macierzy bij podanych w tym samej linijce:

(2.62)
(2.63)

Jeśli wyznacznik główny tego rozwinięcia (2.62), czyli określonej przez elementy (2.63) jest nierówny zero, to mamy wtedy określone elementy ci, które jednoznacznie są określone.

Aproksymacja jednostajna przy pomocy wielomianów edytuj

Każdą funkcję możemy aproksymować wielomianami dowolnego stopnia (2.1). 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ą:

(2.64)

Stopień wielomianu (2.64) jest taki, żeby wyrażenie zapisane poniżej miało najmniejszą wartość w przedziale <a,b>:

(2.65)

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 edytuj

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 x0 o promieniu zbieżności δ, co można powiedzieć:

(2.66)

Rozwinięcie funkcji f(x) w szereg Taylora z dokładności do n-tego stopnia piszemy wzorem w otoczeniu punktu x0:

(2.67)

Różnica funkcji aproksymującej Wn i funkcji aproksymowanej Wn(x) jest wyrażona wzorem znanej z analizy matematycznej, którą to piszemy:

(2.68)

Jeśli maksymalną wartość n+1 pochodnej funkcji f(x) na rozważanym przedziale określimy przez Mn+1, to według aproksymacji jednostajnej na podstawie (2.67) możemy powiedzieć, że zachodzi:

(2.69)

Za pomocą funkcji (2.67) możemy policzyć dowolne przybliżenie funkcji dla dowolnego przybliżenia, który zależy od stopnia aproksymującej funkcji.

Naprawdę szybka transformacja Fouriera edytuj

Każdą funkcję określoną w n różnych punktach określonych na "n" punktach możemy przybliżać wielomianami trygonometrycznymi:

(2.70)

Można udowodnić, że wzór (2.70) jest równoważny wzorowi:

(2.71)
  • gdzie θ=1, mamy: dla n parzystych.
  • gdzie θ=0, mamy dla n nieparzystych.

Udowodnijmy przejście od wzoru (2.70) do wzoru (2.71) dla n parzystego i nieparzystego. Dla n parzystego wzór (2.70) przepisujemy następująco:



(2.72)

Jak można dalej udowodnić, że otrzymany końcowy wzór (2.72) jest równoważny wzorowi, które po krótkich perypetiach otrzymujemy (2.71) dla n parzystego. Rozpatrzmy teraz przypadek końcowy, gdy n jest nieparzyste, zatem w takim razie równość (2.70) możemy zapisać w sposób:


(2.73)

Jak można dalej udowodnić, że otrzymany końcowy wzór (2.73) jest równoważna wzorowi, które po krótkich perypetiach otrzymujemy (2.70) dla n nieparzystego. Za pomocą aproksymacji średnio-kwadratowej możemy policzyć współczynniki ck występujące we wzorze (2.70) i współczynniki ak i bk występujące we wzorze:

(2.74)
(2.75)
(2.76)

Naszym celem jest wyznaczenie współczynników (2.70) mając ciąg wartości xβ.

Wyliczanie współczynników ck edytuj

Jest to metoda polegająca, która nosi nazwę szybkiej transformacji Fouriera. Wprowadźmy teraz nasze obliczenia wprowadzając oznaczenia:

(2.77)
(2.78)

Wzór (2.74) zapisujemy przy pomocy oznaczeń (2.77) i (2.78):

(2.79)

Każdą liczbę naturalną możemy rozłożyć na czynniki różne od jedności, co są iloczynami liczb ri, którego wskaźnik jest od liczby i=1 do liczby p, co liczbę n możemy zapisać:

(2.80)

Wprowadźmy teraz oznaczenie liczby nβ, które to mamy napisać dla v=0,1,..p-1, która jest iloczynem liczby ri, które to "i" jest od v+1 do p, co można powiedzieć:

(2.81)

Z równości (2.81) dla np możemy przyjąć, że np=1. Wzór (2.80) na podstawie (2.81) piszemy następującą tożsamością, która jest iloczynem liczb ri od i=1 do v przez czynnik nv:

(2.82)

Każdą liczbę k w przedziału , którą tą liczbę definiujemy jako sumę liczb zdefiniowanej w punkcie nv(2.80) pomnożonej przez , możemy zapisać:

(2.83)

Współczynniki αi są elementami pewnego zbioru, który to posiada elementy jako liczby naturalne od 0 do ri, co matematycznie:

(2.84)

Każdy ułamek mający jednoznaczny zapis dla dowolnej liczby naturalnej , po wykorzystaniu tożsamości (2.81), który zachodzi dla , możemy zapisać w postaci:

(2.85)

Współczynniki li, która jest elementem pewnego wzoru, który to zbiór posiada elementy z liczby naturalnej od 0 do ri, co matematycznie to własność naszej liczby piszemy:

(2.86)

Dodatkowo oznaczmy liczbę naturalną kv i ułamek , które są zdefiniowane przy pomocy liczby αi (2.84) i li (2.86), wiedząc, że zachodzi kv<nv, dla zmienności wskaźnika dolnego v od 0 do p (p=0,1,..p).

(2.87)
(2.88)

Napiszmy teraz wyraz, który jest iloczynem liczby k i β podzielonej przez liczbę n, zatem w takim razie korzystając z (2.82) i (2.84) możemy napisać równość, którą to piszemy mając na uwadze stałą całkowitą M występująca w obliczeniach poniżej:

(2.89)

Mając już obliczenia przeprowadzone w punkcie (2.89) i definicji zmiennej w (2.77) podniesionej do potęgi o wykładniku kβ, wtedy możemy zapisać to wyrażenie w postaci:

(2.90)

Wzór (2.79), który przedstawia wzór na współczynniki ck, które są współczynnikami rozwinięcia (2.70), piszemy wzorem:

(2.91)

Człony c(k) występujące we wzorze (2.91) są to człony, które nazywamy współczynnikami manipulacyjnymi. Ze wzoru (2.91) współczynniki manipulacyjne możemy obliczyć kolejno rozpoczynając od obliczenia współczynnika c(1), który to piszemy:

(2.92)

Gdy założymy stałość l1, l2,..,lp-1 przy każdej jego możliwości otrzymujemy transformat Fouriera funkcji , których każda posiada operacji. Przy wykonaniu drugiej operacji względem (2.92) po wyznaczaniu współczynników c(0)(l1,..,lp) do c(1)(l1,..,lp-1p) przejdźmy do drugiego kroku by policzyć następny współczynnik manipulacyjny:

(2.93)

Gdy założymy stałość l1, l2,..,lp-1 przy każdej jego możliwości otrzymujemy transformat Fouriera, których każda posiada operacji. Po tym krokach otrzymujemy współczynniki manipulacyjny jako:

(2.94)

W rezultacie otrzymujemy ck według (2.94) w n(r1+r2+...+rp) operacjach.

Metoda Cooleya-Tukeya edytuj

Tą metodę stosuje się gdy n jest całkowitą potęgą dwójki, tzn. zachodzi n=2p. Obierzmy sobie liczbę β=2β1, która jest liczbą parzystą, lub gdy β=2β1+1, gdy β jest liczbą nieparzystą, wtedy wzór na współczynniki Fouriera ck (2.73) piszemy:

(2.95)

Jeśli odpowiednio oznaczymy liczbę k poprzez zmienną α wedle sposobu , gdzie mamy k1=0,1,..,n/2-1, α=0,1, zatem możemy teraz napisać tożsamość, wykorzystując przy tym fakt wn=1 przy liczbie "w" zdefiniowaną według (2.77):

(2.96)

Wprowadźmy teraz dwie funkcje zależne od liczby k1 zdefiniowane:

(2.97)
(2.98)

W ten sposób wzór na nasz współczynnik ck (2.95), na podstawie tożsamości napisanej wzorami (2.97) i (2.98), możemy napisać:

(2.99)

Na podstawie definicji liczby k poprzez liczbę k1 wynika, że jeśli , wtedy mamy , bo α=0, a jeśli , wtedy na pewno mamy , bo α=1. Dla "n" będącego potęgą dwójki wymagana jest ilość operacji 2nlog2n dla szybkiej transformacji Fouriera.

Algorytm szybkiego mnożenia edytuj

Określmy ciąg współczynników , które będą współczynnikami zespolonymi, a przez {wk} dla k=0,1,..,n-1 niech będzie ciag pierwiastków z jedności. Zdefiniujmy macierz A[i,j]=wij(mod n) dla i,j=0,1,2,..,n-1, wtedy możemy określić wektor , którego i-ty element jest:

(2.100)

Bardzo łatwo można wykazać, że elementami odwrotnymi do macierzy o elementach A[i,j] jest macierz o elementach , wtedy możemy zdefiniować transformację odwrotną według schematu :

(2.101)

Transformatę (2.101) nazywamy dyskretną odwrotną transformatą Fouriera. Oczywiste jest, że zachodzi . Obieżmy sobie ciąg dwóch wektorów pionowych i , to splotem wektorów i nazywamy wektor o 2n-1 współczynnikach , które elementy tego wektora piszemy:

(2.102)

Jak się ukazuje współczynniki ck są identyczne ze współczynnikami iloczynu wielomianów P(x) oraz Q(x), które są stopnia n-1, których definicje:

(2.103)
(2.104)

Iloczyn wielomianu P(x) (2.103) i Q(x) (2.104) definiujemy jako splot tychże funkcji w postaci:

(2.105)

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ć:

(2.106)

Standardowo uzyskanie cK wymaga n2 operacji, ale jeśli rozłożymy liczbę n na czynniki pierwsze, tzn. n=r1r2...rp, to powyższa operacja wymaga n(r1+r2+...+rP) operacji. Można wykazać, że dla wielomianu interpolacyjnego stopnia n przy n+1 więzach wymagana klasycznie ilość operacji jest n2, a użycie szybkiej transformacji Fouriera wymaga operacji.

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

Jak się okazuje lepszą dokładność uzyskuje się przybliżając funkcję f(x) wielomianami wymiernymi, który piszemy przez iloraz wielomianu Ln(x) stopnia n-tego przez wielomian Mk stopnia k-tego:

(2.107)

Wielomian wymierny (2.107) 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 (2.107), które dla porządku dziennego piszemy poprzez wzór:

(2.108)

Wielomiany Ln(x) i Mm(x) piszemy w postaci wzorów Maclaurina, czyli w postaci przybliżenia Taullora względem punktu zerowego.

(2.109)
(2.110)

Ponieważ wielomian Mk(x) dla x=0 powinien być nie równy zero, więc b0≠0, więc przyjmijmy, że b0=1. Funkcję f(x) możemy rozłożyć w szereg Maclaurina opisując go jako szereg potęgowy nieskończony, który piszemy:

(2.111)

Mając na uwadze szereg Ln(x) (2.109) oraz szereg Mk(x) (2.110), a także dokładne rozłożenie funkcji f(x) w szereg Maclaurina (2.111), to możemy napisać błąd przybliżenia funkcji f(x) funkcją aproksymującą wymierną (2.107):

(2.112)

Chcemy, by zachodziło i dla m=0,1,2,..,k+n, to powinno być, że wszystkie wyrazy w liczniku (2.112) powinny być równe zero dla potęg mniejszych niż n+k+1, zatem licznik powyższego wyrażenia możemy zapisać:

(2.113)

Z powyższych wniosków natychmiast otrzymujemy dla r=0,1,2,..,n, ale też mamy bj=0 dla j>k i cj=0 dla j<0, także 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 edytuj

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:

(2.114)

Funkcję f(x) będziemy przybliżać wielomianami Tn,k(x), którego definicja względem współczynników ai i bi jest:

(2.115)

Błąd wybrania funkcji (2.115) aproksymującej funkcję aproksymowaną f(x), pisaną względem (2.114), doprowadzając dwa ułamki wymierne do wspólnego mianownika, piszemy wzorem:

(2.116)

Podobnie jak dla przybliżenia Padégo licznik wyrażenia (2.116) można napisać, że on jest równy pewnej kombinacji liniowych wielomianów Czebyszewa o wskaźnikach większych lub równych n+1.

(2.117)

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):

(2.118)

Jeśli wykorzystamy (2.118), wtedy lewą stronę równania (2.117) piszemy:





(2.119)

Z obliczeń (2.119) i równości (2.117) otrzymujemy od razu trzy tożsamości na współczynniki ar, dla r=0,1,2,..,∞:

(2.120)
(2.121)
(2.122)