1

I need a way to find a rational approximation of any radical expression (say, $\sqrt{1+\sqrt[3]{2}}$) in such a way that I know a bound on the error. Given a rational number, I think I can always use Newton's method to approximate its nth root within a known bound, so I imagine the way to approximate the whole expression is to build it up from its components - approximate $\sqrt[3]{2}$, then use the result to approximate the whole thing, in this example. But how do I account for the errors in the earlier calculations while doing the later ones? I'll need to be able to handle complex numbers too, which seems like it might pose additional complications.

edit - more information about the problem context: by "radical expression," I mean any element of the smallest set of complex numbers that is closed under the arithmetic operations and rational exponentiation. I have such a radical expression, $n$, and a set $S$ of some number of its conjugates, also given as radical expressions. I have to determine whether $n$ is equal to some element of $S$, which will be true iff there is some element of $S$ that is closer to $n$ than any two elements of $S$ are to each other.

Alex Kindel
  • 461
  • Instead of approximating each part, you can produce the minimal polynomial ($x^6 - 3 x^4 + 3 x^2 - 3$ in your example) and apply Newton's to it. –  Apr 28 '18 at 02:11
  • @deyore I do happen to have the minimal polynomials for the expressions on hand already, but how do I make sure I get the right root? – Alex Kindel Apr 28 '18 at 02:13
  • You need to bracket the root first. –  Apr 28 '18 at 02:15
  • It is always best to specify your problem as precisely as possible. Some problems allow strategies tailored to them that are more efficient than the approach for a more general problem. How general or specific is your problem? –  Apr 28 '18 at 02:18
  • @deyore My understanding is that bracketing is for finding where the roots of a function are. How does that help me determine which root corresponds to the expression I'm trying to approximate? – Alex Kindel Apr 28 '18 at 02:28
  • Convenient bracketing allows you to ensure some sufficient conditions for convergence, such that if you start from a point in the interval, the iteration will converge to the root in that interval. Like when you are approximating $\sqrt{2}$. How do you know that you are approximating $\sqrt{2}$ and not $-\sqrt{2}$? Perhaps you ensure that your sequence only takes positive values. That is a form of bracketing. The more complicated the root, the more complicated could be the bracketing. –  Apr 28 '18 at 02:35
  • @deyore I've updated the post with more context. – Alex Kindel Apr 28 '18 at 02:35
  • It still doesn't sound like you are giving all details of your problem. –  Apr 28 '18 at 02:38
  • @deyore I don't know what more I could say. This is for a program that simplifies algebraic expressions. I have to be able to find an approximation for any radical expression, because what I need to approximate depends on the user input. – Alex Kindel Apr 28 '18 at 02:48

1 Answers1

1

Compute the expression using interval arithmetic. The result will have lower and upper bounds on the value.

You may have to try different forms of the expression to get better bounds.

If your interval arithmetic package can use arbitrary precision, that helps.

marty cohen
  • 107,799
  • Would you mind working an example of how to operate on an interval under a root? I'm writing all the code myself, but I can handle integers with arbitrarily large numbers of digits, so I should be able to make that work. – Alex Kindel Apr 28 '18 at 02:58
  • Okay, I think I see - approximate the root of each end of the interval, which yields two new intervals, and the region the approximated value is guaranteed to fall in is the union of those new intervals with the original, right? – Alex Kindel Apr 28 '18 at 03:47
  • 1
    Don't write your own. Find an available package and use that. – marty cohen Apr 28 '18 at 15:15