Teoria aproksymacji - Approximation theory

W matematyce , teoria aproksymacji zajmuje się, jak funkcjonuje najlepiej można aproksymować z prostszych funkcji iz ilościowego charakteryzowania tych błędów wprowadzonych w ten sposób. Pamiętaj, że to, co oznacza najlepszy i prostszy, będzie zależeć od aplikacji.

Ściśle powiązanym tematem jest aproksymacja funkcji przez uogólnione szeregi Fouriera , czyli aproksymacje oparte na sumowaniu szeregu wyrazów opartych na wielomianach ortogonalnych .

Jednym ze szczególnie interesujących problemów jest aproksymacja funkcji w komputerowej bibliotece matematycznej za pomocą operacji, które można wykonać na komputerze lub kalkulatorze (np. dodawanie i mnożenie), tak aby wynik był jak najbardziej zbliżony do rzeczywistej funkcji. Odbywa się to zwykle za pomocą przybliżeń wielomianowych lub wymiernych (stosunek wielomianów).

Celem jest, aby przybliżenie było jak najbliższe rzeczywistej funkcji, zwykle z dokładnością zbliżoną do arytmetyki zmiennoprzecinkowej komputera . Osiąga się to za pomocą wielomianu wysokiego stopnia i/lub zawężenia dziedziny, w której wielomian ma przybliżać funkcję. Często można zawęzić dziedzinę, stosując różne formuły dodawania lub skalowania dla aproksymowanej funkcji. Nowoczesne biblioteki matematyczne często redukują domenę do wielu małych segmentów i używają wielomianu niskiego stopnia dla każdego segmentu.

Błąd między wielomianem optymalnym a log(x) (kolor czerwony) oraz aproksymacją Czebyszewa i log(x) (kolor niebieski) w przedziale [2, 4]. Podziały pionowe to ^10-5 . Maksymalny błąd wielomianu optymalnego wynosi 6,07 × 10 ^-5 .

Błąd między wielomianem optymalnym a exp(x) (czerwony) oraz aproksymacją Czebyszewa i exp(x) (niebieski) w przedziale [-1, 1]. Podziały pionowe to ^10-4 . Maksymalny błąd wielomianu optymalnego wynosi 5,47 × 10 ^-4 .

Optymalne wielomiany

Po wybraniu dziedziny (zwykle przedziału) i stopnia wielomianu, sam wielomian jest wybierany w taki sposób, aby zminimalizować błąd najgorszego przypadku. Oznacza to, że celem jest zminimalizowanie maksymalnej wartości , gdzie P ( x ) jest przybliżonym wielomianem, f ( x ) jest rzeczywistą funkcją, a x zmienia się w wybranym przedziale. Dla grzecznych funkcji, istnieje takie N th -degree wielomian, który doprowadzi do krzywej błędu, który oscyluje tam iz powrotem pomiędzy i łącznie N +2 razy, dając błąd najgorszy przypadek . Widać, że istnieje wielomian N- tego stopnia, który może interpolować N +1 punktów na krzywej. Taki wielomian jest zawsze optymalny. Możliwe jest wykonanie wymyślonych funkcji f ( x ), dla których taki wielomian nie istnieje, ale w praktyce występują one rzadko. ${\ Displaystyle \ mid P (x)-f (x) \ mid}$ $+\varepsilon$ $-\varepsilon$ $\varepsilon$

Na przykład wykresy pokazane po prawej pokazują błąd w aproksymacji log(x) i exp(x) dla N = 4. Czerwone krzywe, dla wielomianu optymalnego, to level , to znaczy oscylują pomiędzy i dokładnie. Zauważ, że w każdym przypadku liczba ekstremów wynosi N +2, czyli 6. Dwa ekstrema znajdują się w punktach końcowych przedziału, na lewej i prawej krawędzi wykresu. $+\varepsilon$ $-\varepsilon$

Błąd P ( x ) − f ( x ) dla wielomianu poziomu (czerwony) i dla rzekomo lepszego wielomianu (niebieski)

Aby udowodnić, że jest to ogólnie prawdziwe, załóżmy, że P jest wielomianem stopnia N o opisanej własności, to znaczy powoduje powstanie funkcji błędu, która ma ekstrema N + 2 o naprzemiennych znakach i równych wartościach. Czerwony wykres po prawej pokazuje, jak ta funkcja błędu może wyglądać dla N = 4. Załóżmy, że Q ( x ) (którego funkcja błędu jest pokazana na niebiesko po prawej stronie) jest innym wielomianem N- stopni, który jest lepszym przybliżeniem f niż P . W szczególności, Q jest bliższe f niż P dla każdej wartości x _i, gdzie występuje ekstremum P − f , więc

{\ Displaystyle | Q (x_ {i}) - f (x_ {i}) | < | P (x_ {i}) - f (x_ {i}) |.}

Gdy maksimum P − f występuje w x _i , wtedy

{\ Displaystyle Q (x_ {i}) - f (x_ {i}) \ leq | Q (x_ {i}) - f (x_ {i}) | < | P (x_ {i}) - f (x_ {i})|=P(x_{i})-f(x_{i}),}

A gdy minimum P − f występuje w x _i , wtedy

{\ Displaystyle f (x_ {i}) - Q (x_ {i}) \ leq | Q (x_ {i}) - f (x_ {i}) | < | P (x_ {i}) - f (x_ {i})|=f(x_{i})-P(x_{i}).}

Tak więc, jak widać na wykresie, [ P ( x ) - f ( x )] - [ Q ( x ) - f ( x )] musi zmieniać znak dla N + 2 wartości x _i . Jednak [ P ( x ) - f ( x )] - [ P ( x ) - f ( x )] zmniejsza się do P ( x ) - P ( x ), który jest wielomianem stopnia N . Funkcja ta zmienia znak co najmniej N +1 razy, więc zgodnie z twierdzeniem o wartości pośredniej ma N +1 zer, co jest niemożliwe dla wielomianu stopnia N .

Przybliżenie Czebyszewa

Wielomiany bardzo zbliżone do optymalnego można uzyskać, rozszerzając daną funkcję o wielomiany Czebyszewa, a następnie odcinając rozwinięcie w pożądanym stopniu. Jest to podobne do analizy Fouriera funkcji, przy użyciu wielomianów Czebyszewa zamiast zwykłych funkcji trygonometrycznych.

Jeśli obliczy się współczynniki w rozwinięciu Czebyszewa dla funkcji:

{\ Displaystyle f (x) \ sim \ suma _ {i = 0} ^ {\ infty} c_ {i} T_ {i} (x)}

a następnie odcina serii po okresie, dostaje się N p -degree aproksymującego wielomianu f ( x ). $T_{N}$

Powodem, dla którego ten wielomian jest prawie optymalny, jest to, że dla funkcji o szybko zbieżnych szeregach potęgowych, jeśli szereg zostanie odcięty po pewnym członie, całkowity błąd wynikający z odcięcia jest bliski pierwszemu członowi po odcięciu. Oznacza to, że pierwszy termin po odcięciu dominuje we wszystkich późniejszych terminach. To samo dotyczy rozwinięcia w postaci wielomianów wyboczenia. Jeśli rozszerzenie Czebyszewa zostanie odcięte po , błąd przyjmie postać bliską wielokrotności . Wielomiany Czebyszewa mają tę właściwość, że są poziome – oscylują między +1 a -1 w przedziale [-1, 1]. ma ekstrema na poziomie N +2. Oznacza to, że błąd między f ( x ) i jego rozwinięciem Czebyszewa do jest bliski funkcji poziomu z ekstremami N +2, a więc jest bliski optymalnemu wielomianowi N- tego stopnia. $T_{N}$ ${\ Displaystyle T_ {N + 1}}$ ${\ Displaystyle T_ {N + 1}}$ $T_{N}$

Na powyższych wykresach zauważ, że niebieska funkcja błędu jest czasami lepsza (wewnątrz) funkcji czerwonej, ale czasami gorsza, co oznacza, że nie jest to optymalny wielomian. Rozbieżność jest mniej poważna dla funkcji exp, która ma niezwykle szybko zbieżne szeregi potęgowe, niż dla funkcji log.

Przybliżenie Czebyszewa jest podstawą kwadratury Clenshawa-Curtisa , techniki całkowania numerycznego .

Algorytm Remeza

Algorytm Remez (czasami pisane Remes) stosuje się do wytwarzania optymalnego wielomianu P ( x ) zbliżoną do danej funkcji f ( x ) w zadanym przedziale. Jest to algorytm iteracyjny zbieżny do wielomianu z funkcją błędu z ekstremami poziomu N +2. Z powyższego twierdzenia wynika, że wielomian jest optymalny.

Algorytm Remeza wykorzystuje fakt, że można skonstruować wielomian N- tego stopnia, który prowadzi do poziomu i naprzemiennych wartości błędów, przy założeniu N +2 punktów testowych.

Mając N +2 punkty testowe , , ... (gdzie i są przypuszczalnie punktami końcowymi przedziału aproksymacji), równania te muszą zostać rozwiązane: $x_{1}$ $x_{2}$ ${\ Displaystyle x_ {N + 2}}$ $x_{1}$ ${\ Displaystyle x_ {N + 2}}$

{\ Displaystyle {\ zacząć {wyrównany} P (x_ {1}) -f (x_ {1}) i = + \ varepsilon \ \ P (x_ {2}) - f (x_ {2}) & = - \ varepsilon \\P(x_{3})-f(x_{3})&=+\varepsilon \\&\ \ \vdots \\P(x_{N+2})-f(x_{N+2} )&=\pm \varepsilon .\end{wyrównany}}}

Prawa strona naprzemiennie w znaku.

To jest,

{\zaczynać{wyrównany}P_{0}+P_{1}x_{1}+P_{2}x_{1}^{2}+P_{3}x_{1}^{3}+\ kropki +P_{N}x_{1}^{N}-f(x_{1})&=+\varepsilon \\P_{0}+P_{1}x_{2}+P_{2}x_{2 }^{2}+P_{3}x_{2}^{3}+\dots +P_{N}x_{2}^{N}-f(x_{2})&=-\varepsilon \\& \ \ \vdots \end{wyrównane}}

Ponieważ , ..., zostały dane, wszystkie ich uprawnienia są znane, a , ..., są również znane. Oznacza to, że powyższe równania są tylko N +2 równań liniowych w N + 2 zmiennych , , ..., , i . Mając punkty testowe , ... , można rozwiązać ten układ , aby otrzymać wielomian P i liczbę . $x_{1}$ ${\ Displaystyle x_ {N + 2}}$ $f(x_{1})$ ${\ Displaystyle f (x_ {N + 2})}$ $P_{0}$ $P_{1}$ ${\ Displaystyle P_ {N}}$ $\varepsilon$ $x_{1}$ ${\ Displaystyle x_ {N + 2}}$ $\varepsilon$

Poniższy wykres pokazuje przykład tego, tworząc wielomian czwartego stopnia aproksymujący [−1, 1]. Punkty testowe zostały ustawione na -1, -0,7, -0,1, +0,4, +0,9 i 1. Te wartości są pokazane na zielono. Wynikowa wartość to 4,43 × 10 ^-4 ${\ Displaystyle e ^ {x}}$ $\varepsilon$

Błąd wielomianu wytworzonej w pierwszym etapie algorytmu Remez'S, aproksymujących e ^x w przedziale [1, 1]. Podziały pionowe to ^10-4 .

Zauważ, że wykres błędu rzeczywiście przyjmuje wartości w sześciu punktach testowych, w tym w punktach końcowych, ale te punkty nie są ekstremami. Gdyby cztery wewnętrzne punkty testowe były ekstremami (to znaczy funkcja P ( x ) f ( x ) miała tam maksima lub minima), wielomian byłby optymalny. ${\ Displaystyle \ pm \ varepsilon}$

Drugi krok algorytmu Remeza polega na przesunięciu punktów testowych do przybliżonych miejsc, w których funkcja błędu miała swoje rzeczywiste lokalne maksima lub minima. Na przykład patrząc na wykres można stwierdzić, że punkt przy -0,1 powinien znajdować się przy -0,28. Sposobem na zrobienie tego w algorytmie jest użycie pojedynczej rundy metody Newtona . Ponieważ zna się pierwszą i drugą pochodną P ( x ) − f ( x ) , można w przybliżeniu obliczyć, jak daleko musi zostać przesunięty punkt testowy, aby pochodna wyszła zero.

Obliczanie pochodnych wielomianu jest proste. Trzeba też umieć obliczyć pierwszą i drugą pochodną f ( x ). Algorytm Remeza wymaga umiejętności obliczania , , oraz bardzo wysokiej precyzji. Cały algorytm musi być wykonany z większą precyzją niż pożądana precyzja wyniku. $f(x)\,$ $f'(x)\,$ $f''(x)\,$

Po przesunięciu punktów testowych część równania liniowego jest powtarzana, otrzymując nowy wielomian, a metoda Newtona jest ponownie używana do ponownego przesunięcia punktów testowych. Ta sekwencja jest kontynuowana, aż wynik zbiegnie się z pożądaną dokładnością. Algorytm zbiega się bardzo szybko. Zbieżność jest kwadratowa dla dobrze zachowanych funkcji — jeśli punkty testowe mieszczą się w zakresie prawidłowego wyniku, po następnej rundzie będą się mieścić w przybliżeniu w zakresie prawidłowego wyniku. ${\ Displaystyle 10 ^ {-15}}$ ${\ Displaystyle 10 ^ {-30}}$

Algorytm Remeza zwykle rozpoczyna się od wybrania ekstremów wielomianu Czebyszewa jako punktów początkowych, ponieważ ostateczna funkcja błędu będzie podobna do tego wielomianu. ${\ Displaystyle T_ {N + 1}}$

Główne czasopisma

Zobacz też

Bibliografia

NI Achiezer (Akhiezer) , Teoria aproksymacji, przekład Charles J. Hyman Frederick Ungar Publishing Co., Nowy Jork 1956 x+307 s.
AF Timan, Teoria aproksymacji funkcji zmiennej rzeczywistej , 1963 ISBN 0-486-67830-X
C. Hastings, Jr. Przybliżenia dla komputerów cyfrowych . Wydawnictwo Uniwersytetu Princeton, 1955.
JF Hart, EW Cheney , CL Lawson, HJ Maehly, CK Mesztenyi, JR Rice , HC Thacher Jr., C. Witzgall, Przybliżenia komputerowe . Wiley, 1968, lib. Kong. 67-23326.
L. Fox i IB Parker. „Wielomiany Czebyszewa w analizie numerycznej”. Oxford University Press, Londyn, 1968.
Prasa, WH ; Teukolski SA ; Vetterling, WT; Flannery, BP (2007), "Sekcja 5.8. Przybliżenie Czebyszewa" , Przepisy numeryczne: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
WJ Cody Jr., W. Waite, Podręcznik oprogramowania dla funkcji podstawowych . Prentice-Hall, 1980, ISBN 0-13-822064-6 .
E. Remes [Remez] , "Sur le calcul effectif des polynomes d'aproksymacji de Tschebyscheff". 1934 CR Acad. Nauka. , Paryż, 199 , 337-340.
KG. Steffens, „Historia teorii aproksymacji: od Eulera do Bernsteina”, Birkhauser, Boston 2006 ISBN 0-8176-4353-2 .
T. Erdélyi , „Rozszerzenia twierdzenia Blocha-Polyi o liczbie różnych zer rzeczywistych wielomianów”, Journal de théorie des nombres de Bordeaux 20 (2008), 281-287.
T. Erdélyi, „Nierówność Remeza dla kombinacji liniowych przesuniętych Gaussów”, Matematyka. Proc. Camb. Phil. Soc. 146 (2009), 523-530.
LN Trefethen , „Teoria aproksymacji i praktyka aproksymacji”, SIAM 2013. [1]

Languages

In other projects