Metody numeryczne fizyki/Aproksymacja

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 a₀, a₁,...,a_n, które występują w funkcji aproksymującej:

$F(x)=a_{0}\varphi _{0}(x)+a_{1}\varphi _{1}(x)+...+a_{m}\varphi _{n}(x)\;$

(2.1)

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

$F(x)={{a_{0}\varphi _{0}(x)+a_{1}\varphi _{1}(x)+...+a_{m}\varphi _{n}(x)} \over {b_{0}\psi _{0}(x)+b_{1}\psi _{1}(x)+...+b_{m}\psi _{n}(x)}}\;$

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

$||f||_{2}=\left(\int _{a}^{b}|f(x)|^{2}dx\right)^{{1} \over {2}}\;$

(2.3)

$||f||_{2,w}=\left(\int _{a}^{b}w(x)|f(x)|^{2}dx\right)^{{1} \over {2}}\;$

(2.4)

Wprowadzenie do aproksymacji średniokwadratowej

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

$||F(x)-f(x)||=\int _{a}^{b}w(x)[F(x)-f(x)]^{2}dx\;$

(2.5)

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

$||F(x)-f(x)||=\sum _{i=1}^{n}w(x_{i})[F(x_{i})-f(x_{i})]^{2}\;$

(2.6)

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

$||F(x)-f(x)||=\sup _{x\in \langle a,b\rangle }|F(x)-f(x)|\;$

(2.7)

Omówienie aproksymacji średniokwadratowej

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

$H(a_{0},a_{1},..,a_{m})=\sum _{j=1}^{n}w(x_{j})\left[f(x_{j})-\sum _{i=0}^{m}a_{i}\varphi _{i}(x_{j})\right]^{2}\;$

(2.8)

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

${{\partial H} \over {\partial a_{k}}}=0{\mbox{, }}k=0,1,2,..,m\;$

(2.9)

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

${{\partial H} \over {\partial a_{k}}}=-2\sum _{j=0}^{n}w(x_{j})\left[f(x_{j})-\sum _{i=0}^{m}a_{i}\varphi _{i}(x_{j})\right]\varphi _{k}(x_{j})=0\;$

(2.10)

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

$\mathbf {D} ={\begin{bmatrix}\varphi _{0}(x_{0})&\cdots &\varphi _{m}(x_{0})\\\varphi _{0}(x_{1})&\cdots &\varphi _{m}(x_{1})\\\cdots \\\cdots &\cdots &\cdots \\\varphi _{0}(x_{n})&\cdots &\varphi _{m}(x_{n})\\\end{bmatrix}}\;$

(2.11)

$\mathbf {A} ={\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{m}\end{bmatrix}}\;$

(2.12)

$\mathbf {f} ={\begin{bmatrix}f(x_{0})\\f(x_{1})\\\vdots \\f(x_{n})\end{bmatrix}}\;$

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

$\mathbf {D} ^{T}\mathbf {D} \mathbf {A} =\mathbf {D} ^{T}\mathbf {f} \Rightarrow \mathbf {D} \mathbf {A} =\mathbf {f} \;$

(2.14)

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

Omówienie aproksymacji wielomianowej

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

$\sum _{j=0}^{n}\left[f(x_{j})-\sum _{i=1}^{m}a_{i}x_{j}^{i}\right]x_{j}^{k}=0\Rightarrow \sum _{j=0}^{n}f(x_{j})x_{j}^{k}=\sum _{i=0}^{m}a_{i}\sum _{j=0}^{n}x_{j}^{i+k}\;$

(2.15)

Jeśli wprowadzimy następujące oznaczenia:

$g_{ik}=\sum _{j=0}^{n}x_{j}^{ik+k}\;$

(2.16)

$\rho _{k}=\sum _{j=0}^{n}f(x_{j})x_{j}^{k}\;$

(2.17)

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

$\sum _{i=0}^{m}a_{i}g_{ik}=\rho _{k}{\mbox{ gdzie: }}k=0,1,2,...m\;$

(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 a_i, 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:

$\sum _{i=0}^{n}f(x_{i})g(x_{i})=0\;$

(2.19)

$\sum _{i=0}^{n}[f(x_{i})]^{2}>0\;$

(2.20)

$\sum _{i=0}^{n}[g(x_{i})]^{2}>0\;$

(2.21)

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

$q={{x-x_{0}} \over {h}}\;$

(2.22)

Teraz wprowadźmy teraz funkcję $F_{i}^{(n)}(q)\;$, które są wzajemnie ortogonalne, które spełniają warunek ortoganalności (2.19) dla j≠k:

$\sum _{i=0}^{n}F_{j}^{(n)}(q)F_{k}^{(n)}(q)=0\;$

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

$F_{k}^{(n)}(q)=a_{0}+a_{1}q+a_{2}q(q-1)+a_{3}q(q-1)(q-2)+...+a_{k}q(q-1)...(q-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:

$q^{[k]}=q(q-1)...(q-k+1)\;$

(2.25)

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

$F_{k}^{(n)}=a_{0}+a_{1}q^{[2]}+...+a_{k}q^{[k]}\;$

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

${\hat {F}}_{k}^{(n)}(0)=1\;$

(2.27)

${\hat {F}}_{k}^{(n)}(q)=1+b_{1}q^{[1]}+...+b_{k}q^{[k]}\;$

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

${\hat {F}}_{k}^{(n)}(q)=\sum _{s=0}^{k}(-1)^{s}{k \choose s}{k+s \choose s}{{q^{[s]}} \over {n^{[s]}}}\;$

(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 x₀, x₁,...,x_n. Wzór aproksymacyjny, który jest oparty na wielomianach Grama (2.29) jest odpowiednikiem wzoru (2.1), piszemy:

$y_{m}=\sum _{k=0}^{m}{{c_{k}} \over {s_{k}}}{\hat {F}}_{k}^{(n)}(q)=\sum _{k=0}^{m}{{c_{k}} \over {s_{k}}}{\hat {F}}_{k}^{(n)}\left({{x-x_{0}} \over {h}}\right)\;$

(2.30)

Jeśli weźniemy $m\leq n\;$, to stałe s_k i c_k piszemy:

$s_{k}=\sum _{i=0}^{n}[{\hat {F}}_{k}^{(n)}(q)]^{2}\;$

(2.31)

$c_{k}=\sum _{i=0}^{n}y_{i}{\hat {F}}^{(n)}(x_{i})\;$

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

$\varphi _{j+1}=(x-\alpha _{j+1})\varphi _{j}(x)-\beta _{j}\varphi _{j-1}(x){\mbox{ dla }}j=0,1,..\;$

(2.33)

$\varphi _{0}(x)=1\;$

(2.34)

$\varphi _{-1}(x)=0\;$

(2.35)

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

$\beta _{j}={{\sum _{i=0}^{n}\varphi _{j}^{2}(x_{j})} \over {\sum _{i=1}^{n}\varphi _{j-1}^{2}(x_{i})}}\;$

(2.36)

$\alpha _{j+1}={{\sum _{i=0}^{n}x_{i}\varphi _{j}^{2}(x_{i})} \over {\sum _{j=0}^{n}\varphi _{j}^{2}(x)}}\;$

(2.37)

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

$(\varphi _{2},\varphi _{1})=\sum _{i=0}^{n}(x_{i}-\alpha _{2})\varphi _{1}^{2}(x_{i})=\sum _{i=0}^{n}x_{i}\varphi _{1}^{2}(x_{i})-\alpha _{2}\sum _{i=0}^{n}\varphi _{1}^{2}(x_{i})=\;$
$=\sum _{i=0}^{n}x_{i}\varphi _{1}^{2}(x_{i})-\left({{\sum _{i=0}^{n}x_{i}\varphi _{1}^{2}(x_{i})} \over {\sum _{j=0}^{n}\varphi _{1}^{2}(x)}}\right)\sum _{i=0}^{n}\varphi _{1}^{2}(x_{i})=0\;$

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

$(\varphi _{j+1},\varphi _{j})=\sum _{i=1}^{n}(x_{i}-\alpha _{j+1})\varphi _{i}=\sum _{i=1}^{n}x_{i}\varphi _{i}-{{\sum _{i=0}^{n}x_{i}\varphi _{j}^{2}(x_{i})} \over {\sum _{j=0}^{n}\varphi _{j}^{2}(x)}}\sum _{i=0}^{n}\varphi _{j}^{2}(x_{i})=0\;$

(2.39)

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

$(\varphi _{j+1},\varphi _{j-1})=((x-\alpha _{j+1})\varphi _{j}(x)-\beta _{j}\varphi _{j-1}(x),\varphi _{j-1})=\beta _{j}(\varphi _{j-1},\varphi _{j-1})=\;$
$=\beta _{j}((x-\alpha _{j-1})\varphi _{j-2}(x)-\beta _{j-2}\varphi _{j-3}(x),\varphi _{j-1})=0\;$

(2.40)

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

$y_{m}(x)=\sum _{k=0}^{m}b_{k}\varphi _{k}(x)\;$

(2.41)

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

$b_{k}={{C_{k}} \over {S_{k}}}\;$

(2.42)

$C_{k}=\sum _{i=0}^{n}y_{i}\varphi _{k}(x_{i})\;$

(2.43)

$S_{k}=\sum _{i=0}^{n}\varphi _{k}^{2}(x_{i})\;$

(2.44)

Średniokwadratowa aproksymacja funkcji ciągłych

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:

$H_{n}=\int _{a}^{b}[P(x)-f(x)]^{2}dx=\int _{a}^{b}\left[\sum _{i=0}^{n}a_{i}\varphi _{i}(x)-f(x)\right]^{2}dx\;$

(2.45)

Aby wyznaczyć najmniejszą wartość funkcji H_n należy policzyć wszystkie pochodne tejże funkcji aproksymacyjnej względem współczynników a₀, a₁,...,a_n, 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:

$Q_{n}(x)={{a_{0}} \over {2}}+\sum _{k=1}^{n}(a_{k}\cos kx+b_{k}\sin kx)\;$

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

$x_{i}={{\pi j} \over {L}}{\mbox{ dla }}j=0,1,2,..,2L-1\;$

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

$\sum _{j=0}^{2L-1}\cos kx_{j}+i\sum _{i=0}^{2L-1}\sin kx_{j}=\sum _{j=1}^{2L-1}e^{ikx_{i}}=\sum _{j=1}^{2L-1}e^{i{{kj\pi } \over {L}}}={{1-e^{i{{kj\pi } \over {L}}2L}} \over {1-e^{i{{kj\pi } \over {L}}}}}=\;$
${{1-\cos(2\pi kj)-i\sin(2\pi kj)} \over {1-e^{i{{kj\pi } \over {L}}}}}=0$

(2.48)

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

$\sum _{j=0}^{2L-1}\sin mx_{i}\cdot \sin kx_{i}={{1} \over {2}}\sum _{j=0}^{2L-1}\left[\cos(m-k)x_{i}-\cos(m+l)x_{i}\right]={\begin{cases}0&{\mbox{ dla }}m\neq k\\L&{\mbox{ dla }}m=k\neq 0\\0&{\mbox{ dla }}m=k=0\end{cases}}\;$

(2.49)

$\sum _{i=0}^{2L-1}\cos mx_{i}\cdot \cos kx_{i}={{1} \over {2}}|\sum _{j=0}^{2L-1}\left[\cos(m-k)x_{i}+\cos(m+l)x_{i}\right]={\begin{cases}0&{\mbox{ dla }}m\neq k\\L&{\mbox{ dla }}m=k\neq 0\\2L&{\mbox{ dla }}m=k=0\end{cases}}\;$

(2.50)

$\sum _{i=0}^{2L-1}\cos kx_{i}\sin kx_{i}={{1} \over {2}}\sum _{i=0}^{2L-1}\left[\sin(k+m)x_{i}+\sin(k-m)x_{i}\right]=0\;$

(2.51)

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

$y_{n}(x_{j})={{1} \over {2}}a_{0}+\sum _{k=1}^{n}\left(a_{k}\cos kx_{j}+b_{k}\sin kx_{j}\right){\mbox{ dla }}n<L\;$

(2.52)

Aby wyznaczyć współczynniki wielomianu a_j i b_j 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:

$I=\sum _{i=0}^{2L-1}\left[f(x_{i})-y_{n}(x_{i})\right]^{2}\;$

(2.53)

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

$a_{k}={{1} \over {L}}\sum _{i=0}^{2L-1}f(x_{i})\cos kx_{i}={{1} \over {L}}\sum _{i=0}^{2L-1}f(x_{i})\cos \left({{\pi ki} \over {L}}\right)\;$

(2.54)

$b_{k}={{1} \over {L}}\sum _{i=0}^{2L-1}f(x_{i})\sin kx_{i}={{1} \over {L}}\sum _{i=0}^{2L-1}f(x_{i})\sin \left({{\pi ki} \over {L}}\right)\;$

(2.55)

Funkcje sklejane i aproksymacja za pomocą niej

Omówimy tutaj aproksymację średnio-kwadratową dla węzłów aproksymacji jednakowo oddalonych x_i=a+ih przy $_{h={{b-a} \over {n}}}\;$ dla funkcji sklejanych trzeciego stopnia, zatem funkcja aproksymacyjna można przestawić jako kombinację liniową funkcji trzeciego stopnia $\Phi _{i}^{3}(x)\;$ określonych w przedziale:

$s(x)=\sum _{i=-1}^{n+1}c_{i}\Phi _{i}^{3}(x){\mbox{ gdzie:}}x\leq x\leq b\;$

(2.56)

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

$I=\int _{a}^{b}\left[f(x)-\sum _{i=-1}^{n=1}c_{i}\Phi _{i}^{3}(x)\right]^{2}dx\;$

(2.57)

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

$\sum _{i=-1}^{n+1}c_{i}\int _{a}^{b}\Phi _{i}^{3}(x)\Phi _{j}^{3}(x)dx=\int _{a}^{b}f(x)\Phi _{j}^{3}(x)dx\;$

(2.58)

Jeśli wprowadzimy następujące oznaczenie, która jest całką na przedziale od a do b na iloczynie funkcji $\Phi _{j}^{3}\;$ i $\Phi _{i}^{3}\;$, 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:

$\sum _{i=-1}^{n+1}c_{i}a_{ij}={{1} \over {h}}\int _{a}^{b}f(x)\Phi _{j}^{3}(x)dx\;$

(2.59)

$a_{ij}={{1} \over {h}}\int _{a}^{b}\Phi _{i}^{3}(x)\Phi _{j}^{3}(x)dx\;$

(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 c_i, 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(x_i) równą jeden:

$I=\sum _{k=0}^{m}\left[f(x_{i})-\sum _{i=-1}^{n+1}c_{i}\Phi ^{3}(x_{i})\right]^{2}\;$

(2.61)

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

$\sum _{i=-1}^{n+1}b_{ij}c_{i}=\sum _{k=0}^{n}f(x_{i})\Phi _{j}^{3}(x_{i})\;$

(2.62)

$b_{ij}=\sum _{k=0}^{n}\phi _{i}^{3}(x_{k})\phi _{j}^{3}(x_{k})\;$

(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 c_i, które jednoznacznie są określone.

Aproksymacja jednostajna przy pomocy wielomianów

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

$W_{n}(x)=a_{0}+a_{1}x+a_{2}x^{2}+...+a_{n}x^{n}\;$

(2.64)

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

$E_{n}=\sup _{x\in \langle a,b\rangle }|f(x)-W_{n}(x)|\;$

(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

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

$x_{0}-\delta <a<b<x_{0}+\delta \;$

(2.66)

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

$W_{n}(x)=f(x_{0})+{{f^{'}(x_{0})} \over {1!}}(x-x_{0})+{{f^{''}(x_{0})} \over {2!}}(x-x_{0})^{2}+...+{{f^{(n+1)}} \over {n!}}(x-x_{0})^{n}\;$

(2.67)

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

$f(x)-W_{n}(x)={{f^{(n+1)(c)}} \over {(n-1)!}}(x-x_{0})^{n+1}\;$

(2.68)

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

$|f(x)-W_{n}(x)|\leq {{M_{n+1}} \over {(n-1)!}}\delta ^{n+1}\;$

(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

Każdą funkcję określoną w n różnych punktach określonych na "n" punktach $_{x_{\beta }={{2\pi \beta } \over {n}}{\mbox{, }}\beta =0,1...,n-1}\;$ możemy przybliżać wielomianami trygonometrycznymi:

$F(x)=\sum _{k=0}^{n-1}c_{k}e^{ikx}\;$

(2.70)

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

$F(x)={{a_{0}} \over {2}}+\sum _{k=1}^{m}\left(a_{k}\cos kx+b_{k}\sin kx\right)+{{1} \over {2}}a_{m+1}\cos(m+1)x\;$

(2.71)

• gdzie θ=1, mamy: $m={{n-2} \over {2}}\;$ dla n parzystych.
• gdzie θ=0, mamy $m={{n-1} \over {2}}\;$ 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:

$F(x)=\sum _{k=0}^{2m+2}c_{k}e^{ikx}=\sum _{i=0}^{m}c_{k}e^{ikx}+\sum _{i=m+1}^{2m+2}c_{i}e^{ikx}=\sum _{k=0}^{m}c_{k}e^{ikx}+\sum _{k=0}^{m+1}c_{2m+2-k}e^{i(2m+2-k)x}=\;$
$=\sum _{k=0}^{m}c_{k}e^{ikx_{\beta }}+\sum _{k=0}^{m+1}c_{2m+2-k}e^{i(2m+2)x_{\beta }}e^{-ikx_{\beta }}=\;$
$\sum _{k=0}^{m}\left(c_{k}e^{ikx_{\beta }}+c_{2m+2-i}e^{-ikx_{\beta }}\right)+c_{m+1}e^{i(m+1)x_{\beta }}\;$

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

$F(x)=\sum _{k=0}^{2m+1}c_{k}e^{ikx}=\sum _{k=0}^{m}c_{k}e^{ikx}+\sum _{k=m}^{2m+1}c_{k}e^{ikx}=\sum _{k=0}^{m}c_{k}e^{ikx}+\sum _{k=0}^{2m+1-k}c_{k}e^{i(2m+1-k)x}=\;$
$=\sum _{k=0}^{m}c_{k}e^{ikx_{\beta }}+\sum _{k=0}^{m}c_{2m+i-k}e^{i(2m+1)kx_{\beta }}e^{-ikx}=\sum _{i=0}^{m}\left(c_{k}e^{ikx}+c_{2m+1-i}e^{-ikx}\right)\;$

(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 c_k występujące we wzorze (2.70) i współczynniki a_k i b_k występujące we wzorze:

$c_{k}={{1} \over {n}}\sum _{\beta }^{n-1}f(x_{\beta })e^{-ikx_{\beta }}\;$

(2.74)

$a_{k}={{1} \over {2n}}\sum _{\beta =0}^{n-1}f(x_{\beta })\cos kx_{\beta }\;$

(2.75)

$b_{k}={{1} \over {2n}}\sum _{\beta }^{n-1}f(x_{\beta })\sin kx_{\beta }\;$

(2.76)

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

Wyliczanie współczynników c_k

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

$w=e^{-{{2\pi i} \over {n}}}{\mbox{, }}k=0,1,..n-1\;$

(2.77)

$a_{\beta }={{1} \over {n}}f\left({{2\pi \beta } \over {n}}\right)\;$

(2.78)

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

$c_{k}=\sum _{\beta =0}^{n-1}a_{\beta }w^{k\beta }\;$

(2.79)

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

$n=r_{1}r_{2}...r_{p}\;$

(2.80)

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

$n_{v}=r_{v+1}\cdot r_{v+2}\cdot ...\cdot r_{p}=\prod _{i=v+1}^{p}r_{i}\;$

(2.81)

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

$n=r_{1}r_{2}...r_{v}n_{v}\;$

(2.82)

Każdą liczbę k w przedziału $k\in \langle 0;n-1\rangle \;$, którą tą liczbę definiujemy jako sumę liczb zdefiniowanej w punkcie n_v(2.80) pomnożonej przez $_{0\leq \alpha _{i}\leq r_{i}-1}\;$, możemy zapisać:

$k=\alpha _{1}n_{1}+\alpha _{2}n_{2}+...\alpha _{p-1}n_{p-1}+\alpha _{p}n_{p}\Rightarrow k=\alpha _{1}(r_{2}r_{3}...r_{p})+\alpha _{2}(r_{3}...r_{p})+...\alpha _{p-1}r_{p-1}+\alpha _{p}\cdot 1\;$

(2.83)

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

$\alpha _{i}\in \left\{0,1,2,...,r_{i}-1\right\}\;$

(2.84)

Każdy ułamek ${{\beta } \over {n}}\;$ mający jednoznaczny zapis dla dowolnej liczby naturalnej $\beta \in \langle 0;n-1\rangle \;$, po wykorzystaniu tożsamości (2.81), który zachodzi dla $0\leq l_{i}\leq r_{i}-1\;$, możemy zapisać w postaci:

${{\beta } \over {n}}={{l_{1}} \over {n_{0}}}+{{l_{2}} \over {n_{2}}}+...+{{l_{p}} \over {n_{p-1}}}\Rightarrow {{\beta } \over {n}}={{l_{1}} \over {r_{1}...r_{p}}}+{{l_{2}} \over {r-2..r_{p}}}+{{r_{p-1}} \over {r_{p-1}r_{p}}}+{{l_{p}} \over {r_{p}}}\;$

(2.85)

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

$l_{i}=\in \left\{0,1,2,..,r_{i}-1\right\}\;$

(2.86)

Dodatkowo oznaczmy liczbę naturalną k_v i ułamek ${{\beta _{v}} \over {n_{v}}}\;$, które są zdefiniowane przy pomocy liczby α_i (2.84) i l_i (2.86), wiedząc, że zachodzi k_v<n_v, dla zmienności wskaźnika dolnego v od 0 do p (p=0,1,..p).

$k_{v}=\sum _{i=v+1}^{p}\alpha _{i}n_{i}\;$

(2.87)

${{\beta _{v}} \over {n_{v}}}=\sum _{i=v}^{p-1}{{l_{i+1}} \over {n_{i}}}\;$

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

${{k\beta } \over {n}}=\left(\sum _{i=1}^{p}\alpha _{i}n_{i}\right)\left(\sum _{v=0}^{p-1}{{l_{v+1}} \over {n_{v}}}\right)=\sum _{v=0}^{p-1}{{l_{v+1}} \over {n_{v}}}\left(\sum _{i=v+1}^{p}\alpha _{i}n_{i}\right)+M=\sum _{v=0}^{p-1}{{l_{v+1}k_{v}} \over {n_{v}}}+M\;$

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

$w^{k\beta }=e^{-2\pi i{{k\beta } \over {n}}}=e^{-2\pi i\left(\sum _{v=0}^{p-1}{{l_{v+1}} \over {n_{v}}}+M\right)}=\prod _{v=0}^{p-1}e^{-2\pi i{{l_{v+1}k_{v}} \over {n_{v}}}-M2\pi i}=\prod _{v=0}^{p-1}e^{-2\pi i{{l_{v+1}k_{v}} \over {n_{v}}}}=\prod _{v=0}^{p-1}w_{v}^{l_{v+1}k_{v}}\;$

(2.90)

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

$c_{k}=c(l_{1},l_{2},..,l_{p})=\sum _{l_{1}=0}^{r_{1}-1}\sum _{l_{2}=0}^{r_{2}-1}...\sum _{l_{p}=0}^{r_{p}-1}c^{(0)}(l_{1},l_{2},,..,l_{p})w_{0}^{k_{0}l_{1}}w_{1}^{k_{1}l_{2}}\cdot ...\cdot w_{p-1}^{k_{p-1}l_{v}}\;$

(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⁽¹⁾, który to piszemy:

$c^{(1)}(l_{1},l_{2},l;..,l_{p-1},\alpha _{p})=\sum _{l_{p}=0}^{r_{p}-1}c^{(0)}(l_{1},l_{2},..l_{p})w_{p-1}^{k_{p-1}l_{p}}\;$

(2.92)

Gdy założymy stałość l₁, l₂,..,l_p-1 przy każdej jego możliwości otrzymujemy $_{{n} \over {r_{p}}}\;$ transformat Fouriera funkcji $_{f\left({{2\pi \beta } \over {n}}\right)}\;$, których każda posiada $r_{p}^{2}\;$ operacji. Przy wykonaniu drugiej operacji względem (2.92) po wyznaczaniu współczynników c⁽⁰⁾(l₁,..,l_p) do c⁽¹⁾(l₁,..,l_p-1,α_p) przejdźmy do drugiego kroku by policzyć następny współczynnik manipulacyjny:

$c^{(2)}(l_{1},l_{2},..,l_{p-2},\alpha _{p-1},\alpha _{p})=\sum _{l_{p}=0}^{r_{p-1}}c^{(0)}(l_{1},l_{2},..,\alpha _{p})w_{p-2}^{k_{p-2}l_{p-2}}\;$

(2.93)

Gdy założymy stałość l₁, l₂,..,l_p-1 przy każdej jego możliwości otrzymujemy $_{{n} \over {r_{p-1}}}\;$ transformat Fouriera, których każda posiada $r_{p-1}^{2}\;$ operacji. Po tym krokach otrzymujemy współczynniki manipulacyjny jako:

$c_{k}=c^{(p)}(\alpha _{1},\alpha _{2},..,\alpha _{p})=\sum _{l_{1}=0}^{r_{1}-1}c^{(p-1)}(l_{1},\alpha _{2},..,\alpha _{n})w_{0}^{k_{0}l_{1}}\;$

(2.94)

W rezultacie otrzymujemy c_k według (2.94) w n(r₁+r₂+...+r_p) operacjach.

Metoda Cooleya-Tukeya

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

$c_{k}=\sum _{\beta _{1}=0}^{{{n} \over {2}}-1}a_{2\beta _{1}}(w^{2})^{k\beta _{1}}+\sum _{\beta _{1}=0}^{{{n} \over {2}}-1}a_{2\beta _{1}+1}w^{k(2\beta _{1}+1)}=\sum _{\beta _{1}=0}^{{{n} \over {2}}-1}a_{2\beta _{1}}(w^{2})^{k\beta _{1}}+\sum _{\beta _{1}=0}^{{{n} \over {2}}-1}a_{2\beta _{1}+1}(w^{2})^{2k\beta _{1}}w^{k}\;$

(2.95)

Jeśli odpowiednio oznaczymy liczbę k poprzez zmienną α wedle sposobu $k={{n} \over {2}}\alpha +k_{1}\;$, gdzie mamy k₁=0,1,..,n/2-1, α=0,1, zatem możemy teraz napisać tożsamość, wykorzystując przy tym fakt wⁿ=1 przy liczbie "w" zdefiniowaną według (2.77):

$(w^{2})^{k\beta _{1}}=(w^{2})^{\left(\alpha {{n} \over {2}}+k_{1}\right)\beta _{1}}=(w^{2})^{{\alpha n\beta _{1}} \over {2}}(w^{2})^{k_{1}\beta _{1}}=(w^{n})^{\alpha \beta _{1}}(w^{2})^{k_{1}\beta _{1}}=(w^{2})^{k_{1}\beta _{1}}\;$

(2.96)

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

$\xi (k_{1})=\sum _{\beta _{1}=0}^{{{n} \over {2}}-1}a_{2\beta _{1}}(w^{2})^{k_{1}\beta _{1}}\;$

(2.97)

$\eta (k_{1})=\sum _{\beta _{1}=0}^{{{n} \over {2}}-1}a_{2\beta _{1}+1}(w^{2})^{k_{1}\beta _{1}}\;$

(2.98)

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

$c_{k}=\xi (k_{1})+w^{k}\eta (k_{1})\;$

(2.99)

Na podstawie definicji liczby k poprzez liczbę k₁ wynika, że jeśli $_{k=0,1,..,{{n} \over {2}}-1}\;$, wtedy mamy $_{k_{1}=k}\;$, bo α=0, a jeśli $k={{n} \over {2}},..,n-1\;$, wtedy na pewno mamy $k_{1}=k-{{n} \over {2}}\;$, bo α=1. Dla "n" będącego potęgą dwójki wymagana jest ilość operacji 2nlog₂n dla szybkiej transformacji Fouriera.

Algorytm szybkiego mnożenia

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

$f_{i}=\sum _{k=0}^{n-1}a_{k}w^{(k\cdot i)(\operatorname {mod} n)}{\mbox{, }}i=0,1,..,n-1\;$

(2.100)

Bardzo łatwo można wykazać, że elementami odwrotnymi do macierzy o elementach A[i,j] jest macierz o elementach $_{A^{-1}[i,j]={{1} \over {n}}w^{-ij\mod n}}\;$, wtedy możemy zdefiniować transformację odwrotną według schematu ${\mathcal {F}}^{-1}({\vec {a}})={\hat {A}}^{-1}\cdot {\vec {a}}\;$:

$f_{i}^{-1}={{1} \over {n}}\sum _{i=0}^{n-1}a_{k}w^{-(ki)(\operatorname {mod} n)}\;$

(2.101)

Transformatę (2.101) nazywamy dyskretną odwrotną transformatą Fouriera. Oczywiste jest, że zachodzi ${\vec {a}}={\mathcal {F}}^{-1}({\vec {a}}){\mathcal {F}}({\vec {a}})\;$. Obieżmy sobie ciąg dwóch wektorów pionowych ${\vec {a}}=[a_{0},a_{1},..,a_{n-1}]^{T}\;$ i ${\vec {b}}=[b_{0},b_{1},..,b_{n-1}]^{T}\;$, to splotem wektorów ${\vec {a}}\;$ i ${\vec {b}}\;$ nazywamy wektor o 2n-1 współczynnikach ${\vec {c}}=[c_{0},c_{1},...,c_{2n-1}]^{T}\;$, które elementy tego wektora piszemy:

$c_{i}=\sum _{j=0}^{n-1}a_{j}b_{i-j}{\mbox{, }}a_{k}=b_{k}=0{\mbox{ dla }}k<0{\mbox{ lub }}k\geq n{\mbox{, }}c_{2n-1}=0\;$

(2.102)

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

$P(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\;$

(2.103)

$Q(x)=\sum _{i=0}^{n-1}b_{i}x^{i}\;$

(2.104)

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

$P(x)Q(x)=\sum _{i=0}^{2n-2}x^{i}\sum _{j=0}^{2n-2}a_{j}b_{i-j}=\sum _{i=0}^{2n-2}\sum _{j=0}^{2n-2}a_{j}b_{i-j}x^{i}\;$

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

${\vec {a}}*{\vec {b}}={\mathcal {F}}^{-1}\left({\mathcal {F}}(a)\cdot {\mathcal {F}}(b)\right)\;$

(2.106)

Standardowo uzyskanie c_K wymaga n² operacji, ale jeśli rozłożymy liczbę n na czynniki pierwsze, tzn. n=r₁r₂...r_p, to powyższa operacja wymaga n(r₁+r₂+...+r_P) operacji. Można wykazać, że dla wielomianu interpolacyjnego stopnia n przy n+1 więzach wymagana klasycznie ilość operacji jest n², a użycie szybkiej transformacji Fouriera wymaga $nlog_{2}^{2}n\;$ 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 L_n(x) stopnia n-tego przez wielomian M_k stopnia k-tego:

$R_{n,k}(x)={{L_{n}(x)} \over {M_{k}(x)}}\;$

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

$f(0)={{L_{n}(0)} \over {M_{k}(0)}}\;$

(2.108)

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

$L_{n}(x)=a_{0}+a_{1}x+a_{2}x^{2}+...+a_{n}x^{n}\;$

(2.109)

$M_{k}(x)=b_{0}+b_{1}x+b_{2}x^{2}+...+b_{n}x^{k}\;$

(2.110)

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

$f(x)=\sum _{i=0}^{\infty }c_{i}x^{i}\;$

(2.111)

Mając na uwadze szereg L_n(x) (2.109) oraz szereg M_k(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):

$f(x)-{{L_{n}(x)} \over {M_{k}(x)}}={{f(x)M_{k}(x)-L_{n}(x)} \over {M_{k}(x)}}={{\left(\sum _{i=0}^{\infty }c_{i}x^{i}\right)\left(\sum _{i=0}^{k}b_{i}x^{i}\right)-\sum _{i=0}^{n}a_{i}x^{i}} \over {\sum _{i=0}^{k}b_{i}x^{i}}}\;$

(2.112)

Chcemy, by zachodziło $f(0)-R_{n,k}(0)=0\;$ i $f^{(m)}(0)-R_{n,k}^{(m)}(0)=0\;$ 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ć:

$\left(\sum _{i=0}^{\infty }c_{i}x^{i}\right)\left(\sum _{i=0}^{k}b_{i}x^{i}\right)-\sum _{i=0}^{n}a_{i}x^{i}=\sum _{i=n+k+1}^{\infty }d_{i}x^{i}\;$

(2.113)

Z powyższych wniosków natychmiast otrzymujemy $a_{r}=\sum _{j=0}^{r}c_{r-j}b_{j}\;$ dla r=0,1,2,..,n, ale też mamy b_j=0 dla j>k i c_j=0 dla j<0, także $\sum _{j=0}^{k}c_{n+k-s-j}b_{j}=0\;$ 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:

$f(x)\simeq {{1} \over {2}}a_{0}+\sum _{j=1}^{n}c_{j}T_{j}(x){\mbox{, gdzie: }}c_{i}={{2} \over {\pi }}\int _{-1}^{1}{{f(x)T_{j}(x)} \over {\sqrt {1-x^{2}}}}dx\;$

(2.114)

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

$T_{n,k}(x)={{\sum _{i=0}^{n}a_{i}T_{i}(x)} \over {\sum _{i=0}^{k}b_{i}T_{i}(x)}}\;$

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

$f(x)-T_{n,k}={{\left[{{1} \over {2}}c_{0}+\sum _{i=1}^{\infty }c_{j}T_{j}(x)\right]\sum _{j=0}^{k}b_{i}T_{i}(x)-\sum _{i=0}^{n}a_{i}T_{i}(x)} \over {\sum _{i=0}^{k}b_{i}T_{i}(x)}}\;$

(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.

$\left[{{1} \over {2}}c_{0}+\sum _{i=1}^{\infty }c_{j}T_{j}(x)\right]\sum _{j=0}^{k}b_{i}T_{i}(x)-\sum _{i=0}^{n}a_{i}T_{i}(x)=\sum _{j=n+k+1}^{\infty }h_{j}T_{j}(x)\;$

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

$T_{i+j}(x)+T_{|i-j|}(x)=2T_{i}(x)T_{j}(x)\;$

(2.118)

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

$\left[{{1} \over {2}}c_{0}+\sum _{i=1}^{\infty }c_{j}T_{j}(x)\right]\sum _{j=0}^{k}b_{i}T_{i}(x)-\sum _{i=0}^{n}a_{i}T_{i}(x)=\;$
$={{1} \over {2}}c_{0}\sum _{i=0}^{k}b_{i}T_{j}(x)+{{1} \over {2}}\sum _{j=1}^{\infty }\sum _{s=0}^{k}c_{j}b_{s}\left(T_{j+s}(x)+T_{|j-s|}(x)\right)-\sum _{i=0}^{n}a_{i}T_{i}(x)=\;$
$={{1} \over {2}}c_{0}\sum _{i=0}^{k}b_{i}T_{j}(x)+{{1} \over {2}}\left(\sum _{s=0}^{k}\sum _{\overset {r=1}{\underset {r\neq s}{}}}^{\infty }c_{|r-s|}b_{s}T_{r}(x)+\sum _{s=0}^{k}\sum _{r=0}^{\infty }c_{r+s}b_{s}T_{r}(x)\right)-\sum _{i=0}^{n}a_{i}T_{i}(x)=\;$
$={{1} \over {2}}\sum _{r=1}^{\infty }\left(\sum _{s=0}^{k}c_{|r-s|}b_{s}+\sum _{s=0}^{k}c_{r+s}b_{s}\right)T_{r}(x)+{{1} \over {2}}T_{0}\sum _{i=0}^{k}b_{i}c_{i}-\sum _{i=0}^{n}a_{i}T_{i}(x)=$
$={{1} \over {2}}\sum _{r=1}^{\infty }\left[\sum _{s=0}^{k}b_{s}\left(c_{|r-s|}+c_{r+s}\right)\right]T_{r}(x)+{{1} \over {2}}T_{0}\sum _{i=0}^{k}b_{i}c_{i}-\sum _{i=0}^{n}a_{i}T_{i}(x)$

(2.119)

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

$a_{0}={{1} \over {2}}\sum _{i=0}^{k}b_{i}c_{i}\;$

(2.120)

$a_{r}={{1} \over {2}}\sum _{s=0}^{k}b_{s}\left(c_{|r-s|}+c_{r+s}\right){\mbox{ dla }}r=1,2,..,n+k\;$

(2.121)

$a_{r}=0{\mbox{ dla }}r>n\;$

(2.122)