0
$\begingroup$

Suppose that we have a bounded polynomial defined on $[0,1]$. I think because it is just polynomial, root finding algorithms would easily and without any instability find all its roots. Am I right? And what is the fastest and most stable root-finding algorithm for my problem?

Edit: I introduce my polynomial as: $$ f(x) = B_n(x) - x$$

$B_n(x)$ is a bernstein polynomial with positive and strictly increasing coefficients $a_k$:

$$B_n(x) = \sum_{k=1}^n \binom n ka_kx^k (1-x)^{n-k}$$

$$a_0=0 < a_1 < a_2 < ... < a_n=1$$

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ What exactly do you mean by bounded polynomial? $\endgroup$ Commented Dec 23, 2021 at 7:19
  • $\begingroup$ Are the coefficients integer, or real, or complex, or something else entirely… and do you want real roots, or complex roots etc? $\endgroup$ Commented Dec 23, 2021 at 9:02
  • $\begingroup$ Any polynomial can be transformed to a polynomial with all its real roots in $[0,1]$ and its absolute value there less than 1. So these restrictions don't change the difficulty of root finding. $\endgroup$ Commented Dec 23, 2021 at 9:03
  • 1
    $\begingroup$ The Sturm Theorem and Sturm sequences seem to do the job for you (for real roots of real polynomials). $\endgroup$ Commented Dec 23, 2021 at 9:57
  • 2
    $\begingroup$ If you know that the polynomial changes sign between 0 and 1, bisection will give the root fast enough in practice and it is very accurate. At the risk of non-convergence, Newton's method will be faster but it won't give you rigorous bounds. $\endgroup$ Commented Dec 23, 2021 at 11:12

1 Answer 1

Reset to default
2
$\begingroup$

Finding real roots is not going to be stable, even if you assume the polynomial to be monic and have bounds on where the interesting stuff happens. As an example, consider $(x^2 + \varepsilon)(x^2 - 2x + 1 - \varepsilon)$. If $\varepsilon < 0$, the only real root is at $0$, if $\varepsilon > 0$ the only real root is at $1$.

If you want a guarantee that the algorithm will converge to a root with bounds on the convergence speed, you'd need to either promise the existence of roots with odd multiplicty, or be willing to accept complex roots as solutions.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I already said that the polynomial has exactly one root. $\endgroup$ Commented Dec 23, 2021 at 15:16
  • 1
    $\begingroup$ @bitWise Please edit all relevant information into the question. If you know that there is a unique root, you can find it effectively. However, if you have a "good reason" for why there is a unique root it will be much easier to give a reasonable algorithm. $\endgroup$ Commented Dec 23, 2021 at 15:24
  • $\begingroup$ Thanks. I now understand what to do. $\endgroup$ Commented Dec 23, 2021 at 15:25

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.