śledzenie pierwiastka kwadratowego z ruchomej wartości

Question

Mam pętlę sterowania działającą z wysoką częstotliwością i trzeba obliczyć pierwiastek kwadratowy każdego cyklu. Typowe pierwiastki kwadratowe działają dobrze, ale zajmują zbyt wiele czasu. Ponieważ wartość, którą biorę pierwiastek kwadratowy nie zmienia się zbytnio w każdym cyklu, chciałbym znaleźć iteracyjny pierwiastek kwadratowy, który zbiegnie się, a następnie prześledzi poprawny wynik. W ten sposób mogę wykonać pojedynczą iterację za każdym razem, a nie za wiele.

Problem polega na tym, że wszystkie powtarzające się pierwiastki kwadratowe, które widziałem, prawdopodobnie zawiodą, gdy dane wejściowe ulegną zmianie. W szczególności wygląda na to, że pojawią się problemy, gdy wejście zmieni się na zero, a następnie ponownie wzrośnie - metody nie lubią zaczynać od zgadywania zerowego.

Mój zakres wejściowy wynosi 0-4.5 i potrzebuję precyzji około 0,01, więc użycie inkrementu/dekrementacji o wartości 0,01 może potrwać zbyt długo - chcę, aby w większości zbiegał się z 10 cyklami lub mniej.

FYI Używam stałego punktu 16/32bit, wejście to 16bit q12. Jest na mikrokontrolerze, więc nie jestem zainteresowany wykorzystaniem 1K do tabeli odnośników. Kod jest również generowany z modelu Simulink, a jego funkcje wyszukiwania tabel są dość pełne narzutów.

Czy jest to dobre rozwiązanie?

Answer 1

Możesz użyć jednego ujęcia metody Halleya. Ma sześcienny konwergencji, a zatem powinno być dość precyzyjne, jeżeli wartość przenosi się nieznacznie:

x_{n+1} = x_n * (x_n^2 + 3Q)/(3 x_n^2 + Q) 

ta zbiega cubcially do sqrt(Q).

referencyjny: http://www.mathpath.org/Algor/squareroot/algor.square.root.halley.htm

Answer 2

Zakres 0-4.5 jest dość mały. Z dokładnością do 0,01, to tylko 450 możliwych obliczeń. Można je obliczyć w czasie kompilacji jako stałe i po prostu sprawdzić w czasie wykonywania.

Answer 3

Proponuję użyć tabeli odnośników, jeśli znasz zaawansowane zakresy, z którymi masz do czynienia. Wygeneruj tablicę lub tabelę mieszania (w zależności od języka, w którym pracujesz) do poziomu precyzji, którego potrzebujesz i odnosisz się do tego, kiedy potrzebujesz swoich korzeni.

Answer 4

Próbowałem drugi rozkaz Taylora ekspansję na sqrt(x) i udać się następujący wynik

jeśli y=sqrt(x) i wiesz y_c = sqrt(x_c) już wówczas:

t = x-3*x_c; 
y = (12*x_c*x_c-t*t)/(8*y_c*y_c*y_c); 

Im większy x jest lepsze przybliżenie. W najgorszym przypadku z x_c=0.01 i x=0.02 wynik wychodzi 0.1375 vs rzeczywisty wynik sqrt(0.02)=0.1414 lub różnica 0.0039, która jest pod 0.01.

Przetestowałem kod za pomocą C# i zobaczyłem stabilne przyspieszenie 33% vs Math.Sqrt().