1
$\begingroup$

I recently have been assigned a project to calculate the roots of a cubic polynomial. However, the issue is that the roots could be very big, but also extremely small. I've been trying to use bisection method to find the first root, and thus I start from +/- realmax. The problem I'm having is using Matlab's realmax. I've noticed that realmax does not give us good decimal accuracy. Is there any way to get the wide range that realmax covers with bisection while still giving us good decimal accuracy?

$\endgroup$

migrated from cs.stackexchange.com Mar 1 '15 at 13:14

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ So you can't just use roots – or must you write your own root-finding methods for the assignment? $\endgroup$ – horchler Mar 1 '15 at 18:09
  • $\begingroup$ What do you mean by "decimal accuracy"? Is it large error in roots, or that the function value at the roots is large? Depending on the polynomial you cannot expect the polynomial to vanish, or be "small" in absolute sense, at the numerical roots. $\endgroup$ – Kirill Mar 2 '15 at 4:21
  • $\begingroup$ If you want more significant digits you can use vpa. $\endgroup$ – fibonatic Mar 2 '15 at 14:52
2
$\begingroup$

Correctly implemented bisection method cannot just fail to find a root, so it is probably an implementation issue.

First, it's possible that you stop bisection too early (how exactly have you implemented it?). If you start with an interval $\pm M\approx 10^{300}$, then you'll need $\log_2 (2M/\mathrm{tol})\approx 1000$ iterations before convergence. So it's possible you have accidentally put a limit somewhere on the number of bisections that stops convergence "artificially".

Second, there is a much better way to pick a bound. According to wikipedia, an upper bound on the magnitude of (complex) roots of the polynomial $a_0+a_1x+a_2x^2+a_3x^3$ is $$ M = \max\left(1, \frac{|a_0|+|a_1|+|a_2|}{|a_3|}\right), $$ so a real root of the cubic can be found in $[-M,M]$. There is a number of other bounds there as well. Often one takes a slightly larger bound, like $1.01M$, to avoid corner cases. Since in your case you know the coefficients, this bound is much easier to work with than realmax, which is a very conservative upper bound.

$\endgroup$
4
$\begingroup$

Unless you have a polynomial in multiple variables, finding the roots of a cubic polynomial is pretty simple: there is an explicit formula in terms of the coefficients of your polynomial.

$\endgroup$
  • 3
    $\begingroup$ But be aware of numerical problems when evaluating these explicit formulas. $\endgroup$ – GertVdE Mar 2 '15 at 7:10
2
$\begingroup$

MATLAB uses double precision by default which gives about 16 digits. Do you mean that you want some absolute precision (for example, accurate within 0.01)? If you have numbers near realmax (~1e308) and you want precision of 0.01 you will need numbers that give about 310 digits of precision which will require about 1 kilobit of memory (21024 ~ 1e309) to store the mantissa of your number. This will obviously be much slower to work with than 64-bit double precision numbers. I'm not sure how feasible this will be, but unless you can come up with another solution you could look into arbitrary precision arithmetic. There is an existing MATLAB toolbox that might work for you: http://www.advanpix.com

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.