Vi introducerar en ny algoritm betecknad DSC 2 för att isolera de verkliga rötterna av en univariat kvadratfri polynomial f med heltalskoefficienter. Algoritmen iterativt delar upp ett initialt intervall som är känt för att innehålla alla verkliga rötter av f. Den viktigaste nyheten i vår strategi är att vi kombinerar Descartes' Rule of Signs och Newton iteration. Mer exakt, i stället för att använda en fast uppdelning strategi såsom bisektion i varje iteration, en Newton steg baserat på antalet tecken variationer för en faktisk intervall beaktas, och, endast om Newton steg misslyckas, vi faller tillbaka till bisektion. Enligt detta synsätt visar vår analys att vi för de flesta iterationer kan uppnå en quadratisk konvergens mot de verkliga rötterna. När det gäller komplexitet, vår metod inducerar en rekursion träd av nästan optimal storlek O(n · log(nτ)), där n betecknar graden av polynom och τ bitstorlek av dess koefficienter. Den senare bunden utgör en förbättring genom en faktor av τ på alla befintliga uppdelningsmetoder för uppgiften att isolera de verkliga rötterna. Dessutom ger vi lite komplexitet analys som visar att DSC 2 behöver endast Õ(n 3 τ) bit operationer 1 för att isolera alla verkliga rötter av f. Detta matchar den mest bundna kända för detta grundläggande problem. Men i jämförelse med de mycket mer involverade algoritmer av Pan och Schönhage (för uppgiften att isolera alla komplexa rötter) som uppnår samma bit komplexitet, DSC 2 fokuserar på verklig rotisolering, är mycket lätt att komma åt och lätt att genomföra.
Sagraloff REF visade hur man genomkorsar sådana kedjor mer effektivt genom att kombinera Descartes' rule of Signs, bisektion och Newton iteration.
When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}