It is well known that various real root isolation methods are based on computing, first, the bounds on the values of the positive real roots of a polynomial equation. For the univariate case such bounds are known for many years, i.e. Cauchy's bound, Lagrange-MacLaurin bound, Kioustelidis' bound to name a few. But are there any such bounds for the bivariate case?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
To bound the roots of a bi-variate system of polynomial equations you can use resultants.
As a simple example, look at the following set of equations: $$ x^2+y^2-4=0 \\ xy-1=0 $$ which correspond to the implicit curves (circle and hyperbola) in the figure, the roots correspond to the intersection points of the curves.
To get a bound pair $(x_{max}, y_{max})$ that bounds the absolute value of the roots we can compute the resultants eliminating $x$ and $y$ using the Sylvester matrix.
The Sylvester matrix for eliminating $x$ in this example is : $$ S_x = \left[ {\begin{array}{ccc} 1 & 0 & (y^2-4) \\ y & -1 & 0 \\ 0 & y & -1 \\ \end{array} } \right] $$
and the resultant (the determinant of the Sylvester matrix) is: $$ Res_x(y) = y^4 - 4y^2 + 1 $$
You can then use any univariate bound to bound the $y$-values of the roots. Using Cauchy's bound, for example, gives a bound of $|y_{root}| \leq 1+ \max\{4/1,1/1\} = 5$ (the actual maximal $y$-value among the roots of this example can easily be shown to be $\sqrt{2 + \sqrt{3}} = 1.93185..$).
In a similar manner (the example is symmetric): $$ Res_y(x) = x^4 - 4x^2 + 1 $$ and the bound on the $x$-values of the roots can be computed.
Alternatively, if you don't want to compute the whole resultant, you can use the results from this paper, which gives an upper bound $r_{max}$ on the maximal coefficient of the resultant. Combining this bound with a lower bound $l_{mn}$ on the highest-degree coefficient $r_{mn}$ of the resultant (where $m$ and $n$ are the degrees of the polynomials, and therefore $mn$ is the degree of the resultant), you can use Cauchy's bound. Namely, Cauchy's bound can be bound from above by $|y_{root}| \leq 1 + r_{max}/l_{mn}$.
In the system above, for example, the coefficients of the original polynomials are integers and therefore $r_{mn} \geq 1$, i.e., $l_{mn}=1$. Note that you can always have $r_{mn} \geq 1$ by dividing the original polynomials with the smallest (non-zero) coefficient. There are probably other more sophisticated ways to lower-bound this coefficient as well, depending on the input polynomials and/or the specific application.
To conclude our example, without computing the resultant explicitly:
By Equation(23) of the paper, the bound on the maximal coefficient of the resultant $Res_x$ is given by:
$$ r_{max} = \|Res_x(y)\|_\infty \leq (m_x+n_x)! (\max\{m_y,n_y\}+1)^{m_x+n_x-1} \|P\|_{\infty}^{n_x} \|Q\|_{\infty}^{m_x} $$
Where $P(x,y)$ is the first polynomial and $Q(x,y)$ is the second, $m_x = deg_x(P)$, $n_x = deg_x(Q)$ and $\|P\|_\infty$ is the maximal coefficient in the bi-variate polynomial.
In our example this gives: $$ m_x=2, m_y=2, \|P\|_\infty = 4 \\ n_x=1, n_y=1, \|Q\|_\infty = 1 \\ $$ Which gives an upper bound on the maximal coefficient of $Res_x(y)$: $$ r_{max} = \|Res_x(y)\|_\infty \leq (2+1)! (\max(2,1)+1)^{(2+1-1)} 4^1 1^2 = 216 $$
Combining Cauchy's bound with this bound (and remembering $r_{mn}$ is bounded from below by 1), we get $|y_{root}| \leq 1+ 216/1 = 217$.
As can be seen, there is a price to pay (in terms of the tightness of the bound) for not computing the resultant explicitly (recall that the computed resultant is $y^4-4y^2+1$, i.e., $r_{max}$ is 4).
