Wydaje się, że istnieje wiele randomizowanych algorytmów do testowania tożsamości wielomianowej, sprawdzających, czy dany wielomian ma wartość zero. Czy są jakieś wyniki algorytmów, które dokonują pewnego rodzaju oszacowania wielomianów w określonym zestawie punktów? Może to być na przykład przybliżenie, dla jakiej części tych punktów wielomian ocenia się na zero, lub przybliżenie średniej wartości wielomianu w tych punktach? Zestaw punktów może być specyficzny dla algorytmu.
Odpowiedzi:
Nie do końca to, o co prosiłeś, ale twoje pytanie było trochę otwarte, więc może cię to zainteresuje.
Dla specyficznego problemu szacowania nieskończonych wielomianów (funkcji generujących) , o pochodzeniu kombinatorycznym, opublikowano niedawno artykuł „ Algorytmy dla struktur kombinatorycznych: dobrze ugruntowane systemy i iteracje Newtona ”Pivoteau, Salvy i Soria. Myślę, że (choć mogę się nieco nie zgadzać) pokazuje, że przybliżenia można obliczyć w złożoności, która jest kwadratowa z wymaganą precyzją. Zbiór punktów jest promieniem zbieżności, aw szczególności osobliwości funkcji generującej.