Vi introducerar en ny metod för att isolera de verkliga rötterna av en fyrkantig-fri polynom F = n i=0 A i x i med verkliga koefficienter. Det antas att varje F-koefficient kan approximeras till varje angivet fel som är bundet. Den metod som presenteras är exakt, fullständig och deterministisk. På grund av dess likheter med Descartes-metoden anser vi också att den är praktisk och enkel att genomföra. Jämfört med tidigare tillvägagångssätt uppnår vår nya metod betydligt bättre komplexitet. Det visas vidare att hårdheten hos isoleringen av de verkliga rötterna till F uteslutande bestäms av rötternas geometri och inte av koefficienternas komplexitet eller storlek. För specialfallet där F har heltalskoefficienter av maximal bitstorlek τ, vår bundna på bit komplexitet skriver som Õ(n 3 τ 2 ) som förbättrar de bästa gränserna kända för befintliga praktiska algoritmer med en faktor av n = deg F. Den avgörande idén bakom den nya metoden är att köra en ungefärlig version av Descartes metoden, där, i varje delsektion steg, vi bara överväga approximationer av de mellanliggande resultaten till en viss precision. Vi ger en övre gräns på maximal precision som behövs för att isolera rötterna av F. För heltal polynomials, är detta bundet med en faktor n lägre än den precision som behövs när man använder exakt aritmetisk förklara den förbättrade bundet på bit komplexitet.
För heltal polynomials, Sagraloff REF gav en variant av Descartes metoden som använder ungefärlig aritmetisk med en arbetsprecision av endast Õ(nτ ) bitar.
On the Complexity of Real Root Isolation
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}