Efficient Verification of the Topological Index of Real

Solutions to Algebraic Systems

by

    Jianwei Dian, dian@louisiana.edu

and

  R. Baker Kearfott, rbk@louisiana.edu

Department of Mathematics, University of Louisiana at Lafayette

Here, we will briefly describe the background and state our main results. These results include both new results for functions in real space and new results for functions in complex space.

The General Problem

Use the notation

x = {(x_{1}, x_{2}, …, x_{n})^{T} ∈ ℝ^{n}
|\underline{x}_{i} ≤ x_{i} ≤ \overline{x}_{i}, 1 ≤ i ≤ n\},

A fundamental problem is then

Given F : x → ℝ^{n} and x ∈ 𝕀ℝ^{n}, rigorously verify:

• there exists a unique x^{∗} ∈ x such that F (x^{∗}) = 0,

(1)

Computer arithmetic can be used to verify the assertion in Problem (1), with the aid of interval extensions and computational fixed point theorems.

Underlying Mathematics

The Nonsingular Case

• Classical fixed point theory implies existence.

– Contraction Mapping Theorem

– Brouwer Fixed Point Theorem

– Miranda’s Theorem

• Regularity (non-singularity) implies uniqueness.

• Fundamental property of interval arithmetic allows computational existence and uniqueness.

The Nonsingular Case

Traditional Interval Newton Methods Assumptions (roughly stated):

1. The Jacobi matrix F′(x^{∗}) is nonsingular.

2. x^{∗} is near the center of x.

3. The component widths of x are small.

4. N(F; x, x̌) is the image of x under an appropriate, preconditioned interval Newton method, with x̌ the center of x.

Then:

1. The preconditioned F′(x) is approximately the identity matrix.

2. Thus, N(F; x, x̌) ⊂ x. This proves that there is a unique solution of F (x) = 0 in x.

Singularities

When the Jacobi matrix F′(x^{∗}) is singular, computations as above cannot possibly prove existence and uniqueness.

Example 1 Take

f_{1}(x_{1}, x_{2}) = x_{1}^{2} − x_{2},
f_{2}(x_{1}, x_{2}) = x_{1}^{2} + x_{2},

and x = (x_{1}, x_{2})^{T} = ([−0.1, 0.1], [−0.1, 0.3])^{T}.

For such systems, the best that a preconditioner can do is reduce the Jacobi matrix to approximately the form

( \begin{matrix}∗ & 0 & … & 0 & \overbrace{∗ … ∗}^{n - rank} \\ 0 & ∗ & 0 … & 0 & ∗ … ∗ \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & … & 0 & ∗ & ∗ … ∗ \\ 0 & … & 0 & 0 & 0 … 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & … & 0 & 0 & 0 … 0 \end{matrix} ) .

Singularities

Verification of at Least One Solution

1. The topological degree (to be explained shortly) may be computed over x.

2. If the topological degree is non-zero, there is at least one solution of F (x) = 0 in x.

3. No conclusion can be reached if the topological degree is zero.

Singularities

Verification of the Exact Multiplicity

1. If F : ℂ^{n} → ℂ^{n}, then the topological degree of F over x gives the exact number of solutions, counting multiplicities.

2. If F : ℝ^{n} → ℝ^{n}, and F can be extended analytically into ℂ^{n}, then computations can verify existence of an exact solution or solutions (with multiplicity computed by the algorithm) within a small region of complex space containing x.

The Topological Degree

Some Properties

• If F : x ⊂ ℝ^{n} → ℝ^{n}, F′(x^{∗}) ≠ 0 wherever F (x^{∗}) = 0, x^{∗} ∈ x, and F (x) ≠ 0 when x ∈ ∂x, then the degree d(F, x, 0) is the number of x^{∗} ∈ x, F (x^{∗}) = 0 with det(F′(x^{∗})) > 0, minus the number of such x^{∗} ∈ x with det(F′(x^{∗})) < 0.

• d(F, x, 0) is a continuous function of F, and is defined even if det(F′(x^{∗})) = 0, as long as there are no solutions to F (x) = 0 on ∂x.

• If F is extended to ℂ^{n} and is thought of as mapping ℝ^{2n} to ℝ^{2n}, and x is embedded in a box z ∈ ℂ^{2n}, then d(F, z, 0) is equal to the exact number of z ∈ z, F (z) = 0, counting multiplicities.

An Example

f_{1}(x, y) = x^{2} − y^{2} − ϵ^{2}
f_{2}(x, y) = 2xy,

• If ϵ ≠ 0, then F has solutions at (x, y) = (ϵ, 0) and (x, y) = (−ϵ, 0). Since det(F′(x)) = 4(x^{2} + y^{2}) = 4ϵ^{2} at each of these solutions, d(F, z, 0) = 2, where

z = {(x, y) | x ∈ [−0.1, 0.1], y ∈ [−δ, δ]}

for any δ > 0.

• If ϵ = 0, then d(F, z, 0) is still equal to 2, even though the Jacobi matrix vanishes at the only solution (x, y) = (0, 0).

How is it Computed?

• d(F, x, 0) depends only on values of F on ∂x.

• Define

F_{¬k}(x) = (f_{1}(x), …, f_{k−1}(x),
f_{k+1}(x), …, f_{n}(x)),

and select s ∈ {−1, 1}. Then d(F, x, 0) is equal to the number of zeros of F_{¬k} on ∂x with positive orientation at which sgn(f_{k}) = s, minus the number of zeros of F_{¬k} on ∂x with negative orientation at which sgn(f_{k}) = s.

• The orientation is computed by computing the sign of the determinant of the Jacobian of F_{¬k} and by taking account of which face.

Computation of the Degree

[figure: f_{1}(x) = 0; f_{2} > 0; f_{2} > 0; f_{1} = x_{1}^{2} − x_{2}^{2}; f_{2} = 2x_{1}x_{2}]

Real Degree April, 2000 UL AMS–11

The Complex Case

Notation for our result

• Suppose the rank defect of the preconditioned matrix is 1.

• Define

α_{k} ≡ \frac{∂f_{k}}{∂x_{n}}(x̌),  1 ≤ k ≤ n − 1,
α_{n} ≡ −1,
Δ_{1} ≡ |\frac{∂F}{∂x_{1} … ∂x_{n}}(x̌)| ,
Δ_{d} ≡ n ; ∑ ; k_{1},...,k_{d}=1 \frac{∂^{d}f_{n}}{∂x_{k_{1}} … ∂x_{k_{d}}}(x̌)α_{k_{1}} … α_{k_{d}}
for d ≥ 2.

• Assume Δ_{k} = 0 for k ≤ d and Δ_{d} ≠ 0.

• x̌ is near a point x^{∗} with f(x^{∗}) = 0, x̌ ∈ x, and x^{∗} ∈ x, and there are no solutions of f(x) = 0 on the boundary ∂x.

The Complex Case

• If

– The first n − 1 components of the preconditioned F are nearly linear, the last component is nearly a degree d form, and x is sufficiently small, and

– we are considering the complex extension of F and a sufficiently small box z ∈ 𝕀ℂ^{n} containing the real box x,

then d(F, z, 0) = d.

• \underline{New}: We have designed an algorithm that verifies the degree is equal to d in O (n^{3}) time, with only two searches, in only one variable.

• With a similar algorithm for d = 2, we have verified d = 2 for over 300 equations and unknowns, for discretizations of nonlinear eigenvalue problems.

Real Degree April, 2000 UL AMS–13

Singular Systems

The Real Case

• If the approximation assumptions hold and

– if d is odd, then d(F, x, 0) = sgn(Δ_{d}) = ±1;

– if d is even, then d(F, x, 0) = 0.

• Verification that d(F, x, 0) = ±1 when d is odd is done with an algorithm similar to the complex setting, but more efficiently, with half the number of variables.