Interval newton krawczyk and polynomial root isolation

By [F8], the monic gcd is constructed by Euclidean division over $\mathbb{Q}$, and the divisions terminate: each nonzero remainder has smaller nonnegative integer degree than the divisor by [F2]. The same argument defines $p_k$; if $\mathrm{deg}{p}_{k-1}>0$, then $p_{k-1}^{\mathrm{\prime }}\mathrm{\ne }0$ and has smaller degree by [F3] and characteristic zero, so $\mathrm{deg}{p}_k<\mathrm{deg}{p}_{k-1}$. Thus $p_d=1$, and each $s_k=p_{k-1}\mathrm{/}{p}_k$ is a polynomial.

By [F4], repeated application of [F5] factors $f$ over $\mathbb{C}$: $f(x)={\prod }_{\alpha }(x-\alpha {)}^{m_{\alpha }}$, where the finite list contains each distinct root once and $m_{\alpha }\ge 1$. The induction is finite because each division by $x-\alpha$ lowers degree by one by [F6].

Fix a current polynomial $p$ in the gcd chain and a root $\alpha$ of multiplicity $m>0$, so $p=(x-\alpha {)}^{m}u$ with $u(\alpha )\mathrm{\ne }0$. The product rule [F3] gives $p^{\mathrm{\prime }}=(x-\alpha {)}^{m-1}(mu+(x-\alpha )u^{\mathrm{\prime }})$, whose parenthesized factor is nonzero at $\alpha$ because the field has characteristic zero. Hence the gcd of $p$ and $p^{\mathrm{\prime }}$ has multiplicity exactly $m-1$ at $\alpha$; a root absent from $p$ is absent from their gcd. By [F9] for the field extension $\mathbb{Q}\subseteq \mathbb{C}$, the monic gcd computed over $\mathbb{Q}$ is exactly the monic gcd over $\mathbb{C}$. Thus this root-multiplicity computation applies to each $p_k$.

Induction on $k$ now shows that the multiplicity of $\alpha$ in $p_k$ is $\max (m_{\alpha }-k,0)$. Therefore $\alpha$ occurs once in $s_k=p_{k-1}\mathrm{/}{p}_k$ exactly when $k\le m_{\alpha }$, and it occurs in $s_k\mathrm{/}{s}_{k+1}$ exactly when $k=m_{\alpha }$. This root factorization proves $s_{k+1}$ divides $s_k$ over $\mathbb{C}[x]$; division over $\mathbb{Q}[x]$ has the same zero remainder, so $q_k=s_k\mathrm{/}{s}_{k+1}$ lies in $\mathbb{Q}[x]$.

Each complex root of $f$ occurs in exactly one $q_k$, with exponent one there and exponent $k$ in $q_k^k$. The factorization in step 1.2 therefore gives $f={\prod }_{k=1}^d{q}_k^k$; it also proves that each $q_k$ is squarefree and that distinct $q_k$ have no common root, hence are pairwise coprime. The degree-zero case has $f=1$ and an empty root list.

The degrees of nonzero Euclidean remainders strictly decrease by [F1], so the sequence terminates. Changing each Euclidean remainder by a minus sign changes neither common divisors nor termination. Thus [F6] and the stated gcd $1$ make the last nonzero remainder a nonzero constant $c$. Backward substitution in the division equations gives $A,B\in \mathbb{Q}[x]$ with $A{P}_0+B{P}_1=c$; dividing by $c$ gives a Bezout identity with right side $1$.

Between zeros of the sequence, every polynomial keeps its sign: a sign change would give a zero by [F3] and [F4]. Each term has finitely many zeros by [F5], so it suffices to compute how $V$ changes when a real point crosses a zero of one or more sequence terms.

No two consecutive terms can vanish at the same real $c$. By step 1.1 there are $A,B\in \mathbb{Q}[x]$ with $A{P}_0+B{P}_1=1$; evaluating at $c$ rules out a common zero of $P_0,P_1$ even over $\mathbb{C}$. For $1\le j<s$, the recurrence $P_{j-1}=Q_j{P}_j-P_{j+1}$ propagates simultaneous zeros of $P_j,P_{j+1}$ backward to $P_0,P_1$.

Suppose $P_j(c)=0$ for an internal index $1\le j<s$. The no-adjacent-zero property in [step 2.1] makes $P_{j-1}(c)$ and $P_{j+1}(c)$ nonzero, and the recurrence gives $P_{j-1}(c)=-P_{j+1}(c)$. They have opposite signs. On either side of $c$, the signs of these neighbors are fixed; after zero entries are deleted, the adjacent nonzero neighbors of each internal zero contribute exactly one sign change. If several internal terms vanish at $c$, their indices are nonconsecutive, so these adjacent-pair contributions may share an endpoint but remain distinct terms in the total variation. Thus internal zeros do not change $V$.

If $P_0(c)=0$, then squarefreeness gives $P_1(c)=P_0^{\mathrm{\prime }}(c)\mathrm{\ne }0$. Factor $P_0(x)=(x-c)u(x)$ by [F5]; the product rule gives $u(c)=P_1(c)$, so near $c$ the sign of $P_0(x)P_1(x)$ is the sign of $x-c$. Thus the initial pair contributes one sign change just to the left and none just to the right. Any simultaneous internal zeros contribute no net change by [step 3.1], so $V$ decreases by exactly one as $c$ is crossed from left to right.

The endpoints are not roots of $P$ by hypothesis. As one moves from $a$ to $b$, $V$ is constant except at the finitely many roots of sequence terms; by [step 3.1] internal zeros do not change it and by [step 4.1] each distinct root of $P$ lowers it by one. Therefore $V(a)-V(b)$ is exactly the number of distinct roots in $(a,b)$.

If $P(z)=0$ and $\mathrm{\mid }z\mathrm{\mid }>1+H$, then $\mathrm{\mid }{a}_d\mathrm{\mid }\mathrm{\mid }z{\mathrm{\mid }}^d\le H{\sum }_{j=0}^{d-1}\mathrm{\mid }z{\mathrm{\mid }}^j<H\mathrm{\mid }z{\mathrm{\mid }}^d\mathrm{/}(\mathrm{\mid }z\mathrm{\mid }-1)<\mathrm{\mid }z{\mathrm{\mid }}^d\le \mathrm{\mid }{a}_d\mathrm{\mid }\mathrm{\mid }z{\mathrm{\mid }}^d$, because $\mathrm{\mid }{a}_d\mathrm{\mid }\ge 1$ and $\mathrm{\mid }z\mathrm{\mid }-1>H$. This contradiction proves $\mathrm{\mid }z\mathrm{\mid }\le R$ for every root.

Let ${\alpha }_1,\dots ,{\alpha }_d$ be the distinct roots from [F1] and set $D=a_d^{2d-2}{\prod }_{i<j}({\alpha }_i-{\alpha }_j{)}^2$. Form the coefficient map $\mathrm{\Phi }(u,v)=uP+v{P}^{\mathrm{\prime }}$ from pairs with $\mathrm{deg}u\le d-2$, $\mathrm{deg}v\le d-1$ to polynomials of degree at most $2d-2$. Its square coefficient matrix $S$ has integer entries, so $\det S$ is an integer-coefficient polynomial in $a_d,\dots ,a_0$.

Divide each output polynomial by $P$ and record its quotient and remainder. In coefficient order from highest degree down, the map $(q,r)\mapsto qP+r$ has triangular diagonal consisting of $d-1$ copies of $a_d$ and $d$ copies of $1$, so the inverse coordinate change has determinant $\pm a_d^{-(d-1)}$. Under this change, $\mathrm{\Phi }$ has block form $\left(\begin{array}{cc}I& \ast \\ 0& M\end{array}\right)$, where $M$ is multiplication by $P^{\mathrm{\prime }}$ on $\mathbb{C}[x]\mathrm{/}(P)$. Hence $\det S=\pm a_d^{d-1}\det M$.

For each $i$ define $L_i(x)={\prod }_{j\mathrm{\ne }i}(x-{\alpha }_j)\mathrm{/}({\alpha }_i-{\alpha }_j)$. These degree-$(d-1)$ polynomials satisfy $L_i({\alpha }_j)=1$ when $i=j$ and $0$ otherwise. For every degree-$<d$ representative $q$, the difference $q-{\sum }_{i}q({\alpha }_i)L_i$ has degree $<d$ and vanishes at all $d$ distinct roots; [F7] and [F9] force this difference to be zero. Thus evaluation is an isomorphism $\mathbb{C}[x]\mathrm{/}(P)\to {\mathbb{C}}^d$. It conjugates $M$ to the diagonal matrix with entries $P^{\mathrm{\prime }}({\alpha }_i)$, so [F4] gives $\det M={\prod }_i{P}^{\mathrm{\prime }}({\alpha }_i)$. By [F2], $P^{\mathrm{\prime }}({\alpha }_i)=a_d{\prod }_{j\mathrm{\ne }i}({\alpha }_i-{\alpha }_j)$; pairing the two factors for each $i<j$ yields $\det S=\pm a_d^{2d-1}{\prod }_{i<j}({\alpha }_i-{\alpha }_j{)}^2=\pm a_{d}D$.

Set the variable $a_d$ to zero in the integer-coefficient polynomial $\det S$. Then $\mathrm{deg}P\le d-1$ and $\mathrm{deg}{P}^{\mathrm{\prime }}\le d-2$, so every $uP+v{P}^{\mathrm{\prime }}$ has degree at most $2d-3$; the coefficient map misses the $x^{2d-2}$ coordinate and its determinant is zero. Therefore the constant term in $a_d$ of $\det S$ is zero, so $a_d$ divides $\det S$ as an integer-coefficient polynomial. At the given integer coefficients, $\det S\mathrm{/}{a}_d$ is an integer, and [step 3.1] shows that $D$ is an integer up to sign.

Squarefreeness makes every root distinct, so every factor in $D$ is nonzero and $\mathrm{\mid }D\mathrm{\mid }\ge 1$.

Let $\delta ={\min }_{i<j}\mathrm{\mid }{\alpha }_i-{\alpha }_j\mathrm{\mid }$ and choose a pair attaining it. Every other pairwise distance is at most $2R$ by [step 1.1] and the triangle inequality [F5]. Thus $1\le \mathrm{\mid }D\mathrm{\mid }\le H^{2d-2}{\delta }^2(2R{)}^{d(d-1)-2}$. Rearranging gives $\delta \ge H^{-(d-1)}(2R{)}^{-(d(d-1)-2)\mathrm{/}2}=\sigma (P)$.

Clearing denominators and dividing by the nonzero integer content preserves every root and its multiplicity. By [F1], the active squarefree product has exactly the distinct roots of $p$, and its factors assign each such root its unique multiplicity label.

If the initial squarefree polynomial has degree at least two, the coefficient-height bound in [F3] places every root strictly inside $(-B,B)$ because $B=H+2>H+1$. In degree one, write $S(x)=a_{1}x+a_0$ with nonzero integer $a_1$. Its unique root is $-a_0\mathrm{/}{a}_1$, whose absolute value is at most $\mathrm{\mid }{a}_0\mathrm{\mid }\le H<B$ since $\mathrm{\mid }{a}_1\mathrm{\mid }\ge 1$. Thus the initial endpoints are nonroots in either case. Bisection endpoints are midpoints tested exactly: a root midpoint is recorded and removed before its open halves are queued, while a nonroot midpoint leaves both endpoints nonroots for the active product.

In each queued interval with nonroot endpoints, [F2] makes the computed variation difference exactly its number of active roots. A zero count safely discards the interval. A count of one gives an isolating interval; the Sturm counts of the pairwise coprime $Q_k$ identify exactly one factor and hence the multiplicity label. If a midpoint is a root, exact division by $x-m$ removes it from that factor and the singleton record carries its multiplicity; otherwise the two open halves partition the parent interval. If removal leaves a nonzero constant active product, it has no remaining roots; the immediate complete-return branch safely clears the root-free queue without requesting another Sturm sequence.

Whenever an interval has at least two distinct active roots, their separation [F3] forces its width to be at least $\sigma$. At bisection depth $n$ the width is $2B(1\mathrm{/}2{)}^n$. Since $(1\mathrm{/}2{)}^n\to 0$ by [F4], some finite depth has width below $\sigma \mathrm{/}4$; such an interval cannot still contain two roots, so each branch stops with count zero or one. The branching factor is at most two and the depth is bounded, so the entire queue tree is finite. For degree one, the initial Sturm count is already zero or one. An earlier constant-active-product branch terminates immediately and cannot prolong the queue tree.

At each split, the roots in the parent are partitioned between the open children and, when the midpoint is a root, its exact singleton; a nonroot midpoint contributes no root. Every discarded interval is root-free, and every one-root interval is emitted once. The finite tree therefore accounts for every real root exactly once with the correct multiplicity.

Let $J=\{j:a_j<b_j\}$ and $m=\mathrm{\mid }J\mathrm{\mid }$. If $m=0$, $X$ is a singleton, so its sole point is fixed. If $m>0$, deleting the fixed coordinates identifies $X$ with a box $X_J$ whose side lengths are positive. The coordinatewise affine map $T:[-1,1{]}^m\to X_J$, with $T(u{)}_j=(a_j+b_j)\mathrm{/}2+(b_j-a_j)u_j\mathrm{/}2$, is a homeomorphism. Reinserting the fixed coordinate values defines $\iota :X_J\to X$, and projection onto the free coordinates defines ${\pi }_J:X\to X_J$; since the fixed output coordinates of $f$ equal their singleton values, $f_J={\pi }_J\circ f\circ \iota$ is a continuous self-map of $X_J$.

Define $\mathrm{\parallel }u{\mathrm{\parallel }}_2=({\sum }_j\mathrm{\mid }{u}_j{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$ and $\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }}={\max }_j\mathrm{\mid }{u}_j\mathrm{\mid }$, let $D^m=\{u:\mathrm{\parallel }u{\mathrm{\parallel }}_2\le 1\}$, and put $C_m=[-1,1{]}^m$. For $u\mathrm{\ne }0$ set $h(u)=(\mathrm{\parallel }u{\mathrm{\parallel }}_2\mathrm{/}\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }})u$, and set $h(0)=0$. Then $\mathrm{\parallel }h(u){\mathrm{\parallel }}_{\mathrm{\infty }}=\mathrm{\parallel }u{\mathrm{\parallel }}_2\le 1$. For $y\mathrm{\ne }0$ in $C_m$, set $h^{-1}(y)=(\mathrm{\parallel }y{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}\mathrm{\parallel }y{\mathrm{\parallel }}_2)y$, and set $h^{-1}(0)=0$. For $u\mathrm{\ne }0$, $\mathrm{\parallel }h(u){\mathrm{\parallel }}_2=\mathrm{\parallel }u{\mathrm{\parallel }}_2^2\mathrm{/}\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }}$ and $\mathrm{\parallel }h(u){\mathrm{\parallel }}_{\mathrm{\infty }}=\mathrm{\parallel }u{\mathrm{\parallel }}_2$, so substituting in $h^{-1}$ gives $h^{-1}(h(u))=u$; the same norm calculation gives $h(h^{-1}(y))=y$ for $y\mathrm{\ne }0$. Both maps are continuous away from zero. For any vector $v$, one coordinate attains $\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}$, so $\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}^2\le {\sum }_j\mathrm{\mid }{v}_j{\mathrm{\mid }}^2$; each of the $m$ summands is at most $\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}^2$, so $\mathrm{\parallel }v{\mathrm{\parallel }}_2^2\le m\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}^2$. Taking nonnegative square roots gives $\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }v{\mathrm{\parallel }}_2\le \sqrt{m}\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}$. Therefore for nonzero $u$, $\mathrm{\parallel }h(u){\mathrm{\parallel }}_2=\mathrm{\parallel }u{\mathrm{\parallel }}_2^2\mathrm{/}\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }}\le \sqrt{m}\mathrm{\parallel }u{\mathrm{\parallel }}_2$, and for nonzero $y$, $\mathrm{\parallel }{h}^{-1}(y){\mathrm{\parallel }}_2=\mathrm{\parallel }y{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }y{\mathrm{\parallel }}_2$. These inequalities also hold at zero and show both maps are continuous there. Thus $h$ is a homeomorphism $D^m\to C_m$.

For $m>0$, $T\circ h$ is a homeomorphism from $D^m$ to $X_J$. The conjugate map $g=(T\circ h{)}^{-1}\circ f_J\circ (T\circ h):D^m\to D^m$ is continuous. By [F1], $g$ has a fixed point; mapping it back gives a fixed point of $f_J$, and applying $\iota$ gives a fixed point of $f$ in $X$.

For intervals $X=[a,b]$ and $Y=[c,d]$, addition and subtraction have exact endpoint ranges $[a+c,b+d]$ and $[a-d,b-c]$. For multiplication, the function $xy$ is affine in either variable with the other fixed, so its extrema on the rectangle $X\times Y$ occur at one of the four corners. If $0\mathrm{\notin }Y$, reciprocal is monotone on $Y$, and division is multiplication by the exact reciprocal interval; squaring has lower endpoint $0$ when $0\in X$ and otherwise its endpoint minimum, with endpoint maximum in both cases.

Each exact lower and upper endpoint in step 1.1 is expanded outward by the downward and upward roundings in [F1]; [F2] puts the exact endpoint between those rounded values. Thus every finite interval-operation result contains its exact operation range. If an endpoint overflows or a domain restriction fails, the operation reports a non-finite status and the Statement asserts no finite enclosure.

Order the nodes of the finite acyclic graph topologically. Input and constant values lie in their supplied intervals by the enclosure hypotheses. Inductively, if an operation node has predecessor values in their computed intervals, step 2.1 shows that its exact output belongs to the computed output interval. Shared nodes reuse the same value by [F3], so the induction applies also to correlated intermediate values. It reaches every node and therefore the root, for every admissible assignment.

Use coordinate indices $0\le i,j<n$, as for the Jacobian. Fix a row index $i$ and define ${\varphi }_i(t)=F_i(y+t(x-y))$ on $[0,1]$. For $0\le t\le 1$ and every coordinate $j$, both $x_j,y_j\in [a_j,b_j]$ imply $(1-t)y_j+t{x}_j\in [a_j,b_j]$. Thus the product box $X$ is convex and the segment stays in $X\subset U$. By [F1], $F_i$ is continuous there; by [F2] and [F3], ${\varphi }_i$ is differentiable on $(0,1)$ with ${\varphi }_i^{\mathrm{\prime }}(t)={\sum }_{j=0}^{n-1}{\mathrm{\partial }}_j{F}_i(y+t(x-y))(x_j-y_j)$.

Apply [F4] to ${\varphi }_i$ to obtain $t_i\in (0,1)$ with $F_i(x)-F_i(y)={\sum }_{j=0}^{n-1}{\mathrm{\partial }}_j{F}_i(z_i)(x_j-y_j)$, where $z_i=y+t_i(x-y)\in X$.

For each of the finitely many rows choose the point $z_i$ from step 2.1 and form $A$ whose $i$th row is $\mathrm{\nabla }{F}_i(z_i)$. By [F5], every entry $A_{ij}$ lies in $J_{ij}(X)$, so $A\in \mathcal{J}(X)$; the row identities in step 2.1 give $F(x)-F(y)=A(x-y)$. This uses only finite choice.

If $r\in X$ is a root and $r=m$, then $0=f(m)\in F_m$, so $m\in N$. If $r\mathrm{\ne }m$, the mean value theorem on the segment between $m$ and $r$ gives $\xi \in X$ with $f(m)=f^{\mathrm{\prime }}(\xi )(m-r)$. Since $f^{\mathrm{\prime }}(\xi )\in D$ and $f(m)\in F_m$, interval enclosure [F1] gives $r=m-f(m)\mathrm{/}{f}^{\mathrm{\prime }}(\xi )\in N$. Hence every root in $X$ lies in $N\cap X$, and an empty intersection excludes all roots.

If $0\mathrm{\notin }{E}_f(X)$ and the range enclosure is valid, no $x\in X$ can satisfy $f(x)=0$, because $f(X)\subseteq E_f(X)$.

Suppose $N\subset \mathrm{int}X$. Since $0\mathrm{\notin }D$ and $D$ is an interval, every value of $f^{\mathrm{\prime }}$ on $X$ has one fixed strict sign. Let ${\xi }_a\in (a,m)$ and ${\xi }_b\in (m,b)$ be the mean-value points for $[a,m]$ and $[m,b]$, and put $d_a=f^{\mathrm{\prime }}({\xi }_a)$ and $d_b=f^{\mathrm{\prime }}({\xi }_b)$. The exact Newton points $n_a=m-f(m)\mathrm{/}{d}_a$ and $n_b=m-f(m)\mathrm{/}{d}_b$ lie in $N$, so $a<n_a$ and $n_b<b$.

At each strict interval update, every root of the current interval belongs to $N\cap I$ by step 1.1, so induction shows that no root of the original box is lost. If the current interval is a singleton $\{x\}$ and the algorithm returns "unique-root", then $E_f(\{x\})=\{0\}$ implies $f(x)=0$; root preservation shows this is the only root of the original box.

If $d_a,d_b>0$, the inequality $a<n_a$ gives $f(a)=f(m)-d_a(m-a)<0$, and $n_b<b$ gives $f(b)=f(m)+d_b(b-m)>0$. If $d_a,d_b<0$, multiplying the same inequalities by the negative derivatives reverses them and gives $f(a)>0>f(b)$. In either case [F3] supplies a root in $(a,b)$.