Zalety i wady metody Remeza

[Borneq]

Metoda Remeza optymalizuje wielomiany aproksymacyjne, które na przykład
powstały metodą Czebyszewa.
Zwykle w metodzie Czebyszewa już ekstrema różnic między wielomianem a
funkcją nie różnią się zbytnio między sobą.
Natomiast dużą zaletą metody Remeza jest to że można ją zmodyfikować aby
poszukiwała najlepiej dopasowanych wielomianów według relatywnych
różnić. Na przykład, mam funkcję exp(x) na przedziale [0,1], wtedy
między początkiem i końcem przedziału różnica wartości przekracza 2.7
raza, jeszcze bardziej na przedziale [-1,1]. Zależy nam, by różnica
aproksymacji była nie więcej niż pewna względna wartość.

Metoda Remeza jest dużo gorzej uwarunkowana niż metoda Czebyszewa. Przy
testach, metoda Czebyszewa traciła zwykle n bitów precyzji dla małych n,
gdzie n - stopień wielomianu, podczas gdy metoda Remeza traciła ponad
połowę precyzji.
(gdzie precyzja double = 53 bity)
W związku z tym Algorytm Remeza warto implementować (dla C) przy pomocy
mpfr a dla C++ w celu klarowności używać wrappera mpreal.

Czy najlepiej dopasowane wielomiany dobrze spełniają funkcję szybkiego
wyliczenia funkcji? Na przykład w porównaniu z szeregami ogólnymi? Na
pewno liczenie pierwiastka zwłaszcza kwadratowego jest bardzo szybkie,
gdy liczy się metodą Newtona.
Natomiast aproksymacja wielomianami wymaga wielomianów wysokich stopni,
choć to może zależeć od funkcji i przedziału. Zaleta podejścia
wielomianowego jest taka że nie potrzebują dzieleń.

[Borneq]

Post by Borneq
Czy najlepiej dopasowane wielomiany dobrze spełniają funkcję szybkiego
wyliczenia funkcji? Na przykład w porównaniu z szeregami ogólnymi? Na
pewno liczenie pierwiastka zwłaszcza kwadratowego jest bardzo szybkie,
gdy liczy się metodą Newtona.
Natomiast aproksymacja wielomianami wymaga wielomianów wysokich stopni,
choć to może zależeć od funkcji i przedziału. Zaleta podejścia
wielomianowego jest taka że nie potrzebują dzieleń.

Natomiast aby zobaczyć jak aproksymować funkcje niewymierne, najlepiej
jest zajrzeć do

https://github.com/gcc-mirror/gcc/tree/master/libquadmath/math

np. dla exp(x)

The basic design here is from
Abraham Ziv, "Fast Evaluation of Elementary Mathematical Functions
with Correctly Rounded Last Bit", ACM Trans. Math. Soft., 17 (3),
September 1991,
pp. 410-423.
We work with number pairs where the first number is the high part and
the second one is the low part. Arithmetic with the high part
numbers must
be exact, without any roundoff errors.
The input value, X, is written as
X = n * ln(2)_0 + arg1[t1]_0 + arg2[t2]_0 + x
- n * ln(2)_1 + arg1[t1]_1 + arg2[t2]_1 + xl
where:
- n is an integer, 16384 >= n >= -16495;
- ln(2)_0 is the first 93 bits of ln(2), and |ln(2)_0-ln(2)-ln(2)_1|
< 2^-205
- t1 is an integer, 89 >= t1 >= -89
- t2 is an integer, 65 >= t2 >= -65
- |arg1[t1]-t1/256.0| < 2^-53
- |arg2[t2]-t2/32768.0| < 2^-53
- x + xl is whatever is left, |x + xl| < 2^-16 + 2^-53
Then e^x is approximated as
e^x = 2^n_1 ( 2^n_0 e^(arg1[t1]_0 + arg1[t1]_1) e^(arg2[t2]_0 +
arg2[t2]_1)
+ 2^n_0 e^(arg1[t1]_0 + arg1[t1]_1) e^(arg2[t2]_0 + arg2[t2]_1)
* p (x + xl + n * ln(2)_1))
where:
- p(x) is a polynomial approximating e(x)-1
- e^(arg1[t1]_0 + arg1[t1]_1) is obtained from a table
- e^(arg2[t2]_0 + arg2[t2]_1) likewise
- n_1 + n_0 = n, so that |n_0| < -FLT128_MIN_EXP-1.
If it happens that n_1 == 0 (this is the usual case), that
multiplication
is omitted.

[J.F.]

Użytkownik "Borneq" napisał w wiadomości grup

Post by Borneq
Natomiast dużą zaletą metody Remeza jest to że można ją zmodyfikować
aby poszukiwała najlepiej dopasowanych wielomianów według relatywnych
różnić. Na przykład, mam funkcję exp(x) na przedziale [0,1], wtedy
między początkiem i końcem przedziału różnica wartości przekracza 2.7
raza, jeszcze bardziej na przedziale [-1,1]. Zależy nam, by różnica
aproksymacji była nie więcej niż pewna względna wartość.

exp(x) to bardzo zly przyklad, bo sie ladnie rozklada na szereg
wielomianowy.
Moze i stopien wysoki, ale obliczenia proste, dokladnosc duza i brak
niespodzianek na wybranym przedziale x.

Post by Borneq
Czy najlepiej dopasowane wielomiany dobrze spełniają funkcję
szybkiego wyliczenia funkcji? Na przykład w porównaniu z szeregami
ogólnymi? Na pewno liczenie pierwiastka zwłaszcza kwadratowego jest
bardzo szybkie, gdy liczy się metodą Newtona.

Bo pierwiastek ma kiepski rozklad w szereg.

Post by Borneq
Natomiast aproksymacja wielomianami wymaga wielomianów wysokich
stopni, choć to może zależeć od funkcji i przedziału. Zaleta
podejścia wielomianowego jest taka że nie potrzebują dzieleń.

A tu wspolczesne procesory mnoza szybko, a dziela wolno.

J.

[Borneq]

Jako (przybliżona) alternatywa metody Remaza może być dopasowanie
średnio "kwadratowe".
Dopasowanie takie kiedyś omawial tu Bartek:
https://groups.google.com/g/pl.sci.matematyka/c/G8k9brWnOH4/m/sQGnnydbAQAJ

dwie kwestie:
- o ile liczba razy badanych punktów ma przekraczać stopień wielomianu?
- niezupełnie o to chodzi, bardziej interesuje nas, maksymalny błąd a
nie średniokwadratowy. Czy dałoby radę zamiast tego zastosować sumowanie
błędów podniesione do wysokiej potęgi np. 16?
jak w przykładzie z całkami:
https://www.scirp.org/pdf/AM_2017052210475611.pdf
problem z potęgami > 2 jest taki, że dla 2 pochodna była liniowa i
dawało się obliczyć przez odwrócenie macierzy. Tutaj trzeba by jakoś
inaczej poszukiwać rozwiązania, jak?
Można by porównać czy metoda jest lepiej uwarunkowana niż Remeza, gdzie
wygląda na to, że po wyliczeniu miejsc ekstremów różnic rzędu <1e-12, do
wyrazów b eliminacji Gaussa podawane są nie różnice a wartości funkcji,
mała różnica w zaokrągleniach i może się rozprzestrzeniać błąd.

Do rozwiązanie układu równań liniowych można użyć np eliminacji Gaussa
do rozwiązania jednego równania nieliniowego można użyć metody Dekkera,
która nie potrzebuje pochodnych (chyba że chcemy zmodyfikować i szukać
ekstremów a nie zer) oraz znajduje zero pomiędzy punktami o różnym znaku
(problem dla parzystych zer)
A jak w przypadku całego układu równań nieliniowych? Metoda stycznych
jak Newtona zamienia się na metodę używającą jakobianów, a jak uogólnić
metodę siecznych na wiele wymiarów?

[J.F.]

Użytkownik "Borneq" napisał w wiadomości grup

Post by Borneq
Jako (przybliżona) alternatywa metody Remaza może być dopasowanie
średnio "kwadratowe".
https://groups.google.com/g/pl.sci.matematyka/c/G8k9brWnOH4/m/sQGnnydbAQAJ
- o ile liczba razy badanych punktów ma przekraczać stopień
wielomianu?

Wielomian stopnia N przechodzi przez N+1 punktow dokladnie, wiec jak
chcesz ustalic odchylki, to przydaloby sie sporo wiecej tych punktow.

Post by Borneq
- niezupełnie o to chodzi, bardziej interesuje nas, maksymalny błąd a
nie średniokwadratowy. Czy dałoby radę zamiast tego zastosować
sumowanie błędów podniesione do wysokiej potęgi np. 16?

Poniekad. Wysoka potega "podkresla" duze bledy, a sredniokwadratowy
... uzywany, bo ladnie sie upraszcza :-)


J.