Przejdź do treści

Optimal approximation of the 1/x function using Chebyshev polynomials and magic constants

W niniejszej pracy analizujemy niskokosztowe, dokładne przybliżenie funkcji przy użyciu wielomianów Czebyszewa pierwszego rodzaju, minimalizując liczbę elementarnych operacji w kodach komputerowych (w szczególności poprzez zastosowanie tzw. magicznych stałych). Wykazano, że iteracyjna metoda Newtona-Raphsona nie jest optymalna i zaproponowano nowe podejście. Dowodzimy, że optymalne wielomiany Czebyszewa mogą być rozkładane na czynniki w postaci wielomianów Czebyszewa niższego stopnia, co prowadzi do nowych – optymalnych – schematów iteracyjnych. Ponadto konstruujemy rodzinę nowych algorytmów poprzez podział rozważanego przedziału na podprzedziały, w których stosuje się różne magiczne stałe i czynniki multiplikatywne (w celu zwiększenia dokładności). Rozważania teoretyczne i dowody uzupełniono testami numerycznymi przeprowadzonymi na trzech typach procesorów mikrokontrolerowych.

Artykuł:

ACM Transactions on Mathematical Software

Autorzy z PW:

Leonid Moroz

Rok wydania: