주어진 다항식이 0인지 여부를 확인하여 다항식 아이덴티티 테스트를위한 많은 무작위 알고리즘이있는 것 같습니다. 특정 포인트 집합에 대해 다항식을 추정하는 알고리즘의 결과가 있습니까? 예를 들어, 다항식이 0으로 평가되는 이러한 점의 일부에 대한 근사치 또는 이러한 점에 대한 다항식의 평균값에 근사 할 수 있습니까? 포인트 세트는 알고리즘에 따라 달라질 수 있습니다.
답변
실제로 당신이 요구 한 것은 아니지만, 귀하의 질문은 약간 공개되어 있으므로 관심이 있으실 것입니다.
무한 다항식 (함수 생성) 추정의 특정 문제에 대해 , 조합 원점을 가진 , 최근에 출판 된 논문 ” 조합 구조를위한 알고리즘 : 잘 구축 된 시스템” 피보 토, 살비와 소리아의 ” 뉴턴 반복 “. 필자는 (약간 벗어난 것일 수도 있지만) 근사값은 필요한 정밀도에서 2 차적인 복잡도로 계산 될 수 있음을 보여줍니다. 점들의 집합은 수렴 반경, 특히 생성 함수의 특이점입니다.
A(z)=∑n=0∞anzn