I detta papper introducerar vi en variant av Descartes-metoden för att isolera de verkliga rötterna av en kvadratfri polynom F(x) = n i=0 A i x i med godtyckliga reella koefficienter. Det antas att varje F-koefficient kan approximeras till varje angivet fel som är bundet. Vår algoritm använder bara ungefärlig aritmetik, men den är ändå certifierad, komplett och deterministisk. Vi ger ytterligare en gräns på komplexiteten av vår metod som uteslutande beror på geometrin av rötterna och inte på komplexiteten av koefficienterna av F. För specialfallet, där F är ett polynom av grad n med heltal koefficienter av maximal bitsize τ, vår bundet på bit komplexitet skriver som Õ(n 3 τ 2 ). Jämfört med komplexiteten i den klassiska Descartes metoden från Collins och Acritas (baserat på idéer som går tillbaka till Vincent), som använder exakt rationell aritmetik, utgör detta en förbättring med en faktor av n. Förbättringen beror främst på det faktum att den maximala precision som behövs för att isolera rötterna av F är med en faktor n lägre än den precision som krävs vid användning av exakt aritmetik.
Sagraloff REF gav en variant av Descartes metoden som, när den tillämpas på heltal polynomials, använder ungefärlig aritmetisk med en arbetsprecision av endast Õ(nτ ) bitar.
On the complexity of the Descartes method when using approximate arithmetic
{'venue': 'J. Symb. Comput.', 'journal': 'J. Symb. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}