Problems

(A) Given B ⊂ IR^{n}, F : B → IR^{n}, determine

Zero(F, B) := {x ∈ B | F (x) = 0}.

(B) Given B ⊂ IR^{n}, f : B → IR, determine

Crit(f, B) := {x ∈ B | ∇f(x) = 0}. (C) Given B ⊂ IR^{n}, f : B → IR, determine

Mins(f, B) := {x ∈ B|f(x) ≤ f(y) ∀y ∈ B}

General Assumptions

• B ⊂ IR^{n}, n ≥ 2.

• F ∈ C^{k}(IR^{n}, R^{n}) with suitable k.

• Zero(F, B) finite, all zeros nondegenerate, i.e. det(DF (x)) ≠ 0 for x ∈ Zero(F, B).

• No zeros on the boundary of B. Denote the set of such functions by M^{∗}(B). Denote by M(B) the set of functions f : B → IR such that ∇f ∈ M^{∗}(B).

Solution by trajectory method

• Define implicitely a “locally 1-dimensional” set K(F) such that Zero(F, B) ⊂ K.

• Trace K numerically, stringing all the zeros encountered.

A general method for defining such sets K can be described as follows: Define an auxiliary function G : B → IR^{n} and consider the set

K(F; G) := {x ∈ B | F (x)∥G(x)},

where a∥b means a and b are linear dependend. Then obviously Zero(F) ⊂ K(F; B) and also Zero(G) ⊂ K(F; B).

Since F (x)∥G(x) means ∃λ, μ ∈ IR, λ^{2} + μ^{2} = 1 : λF (x) + μG(x) = 0, we have n + 1 conditions on n + 2 variables, so K(F, G) will generally be of dimension 1.

Example: Consider f ∈ M(IR^{n}), g(x) := ∥∇f(x)∥_{2}^{2}. Then

K(f; g) := {x ∈ IR^{n} | H_{f}(x)∇f(x)∥∇f(x)},

i.e. the set of points where the gradient is an eigenvector of the hessian matrix (the zero vector is also considered an eigenvector). I call these trajectories Schaback–trajectories. ◇

Example: Consider f ∈ M(IR^{n}), g(x) := v^{t}x with some vector v ∈ IR^{n} \ {0}. Then

K(f; g) := {x ∈ IR^{n} | ∇f(x)∥v}.

Similarly for F ∈ M^{∗}(IR^{n}), G(x) := v we get

K(F; G) := {x ∈ IR^{n} | F (x)∥v}.

These trajectories are called Newton trajectories for reasons, that will soon become apparent. ◇

Observe that for linear independend v, w ∈ IR^{n} and G_{1}(x) := v, G_{2}(x) := w we have

K(F, G_{1}) ∩ K(F, G_{2}) = Zero(F).

Bild malen

Thus:

• It is easy to define K but

• It is difficult to trace K

• because

• K may (and generally will) be disconnected.

The numerics needs a starting point for tracing in every connected component of K.

We will now, in short, discuss a possible scheme for connecting components of K. The idea behind this scheme is actually very general, but here we discuss only a very special case.

Suppose B ⊂ IR^{n} is convex, nonempty interior, f ∈ M(B) and f|_{∂(B)} = const. We consider Newton-trajectories

T_{v}(f, B) := {x ∈ B | ∇f(x) ∥ v}.

Definition 1 A point x ∈ B is a touching point of T_{v}(f, B), if ẋ(x)⊥v. Denote the set of these touching points by P (f, v). ◇ Theorem 1 Assumptions as mentioned above, v ∈ IR^{n} \ {0} and g : B → IR, x ↦ v^{t}x. Then the set

Z := T_{v}(f, B) ∪ ⋃_{x∈P (f,v)} g^{−1}g(x)

is connected ◇

Remarks

• If P (f, v) = ∅ then T_{v}(f, B) is connected.

• The sets g^{−1}g(x) are intersections of (n − 1)– dimensional affine hyperplanes in IR^{n} with the convex set B.

• If n = 2 we are done, because then Z is (generally) a 1-dimensional set.

• If n > 2 we must do something, because (n−1)-dimensional sets cannot be traced numerically!

Bild malen

We are not really interested in the sets g^{−1}g(x) but only in the intersection points g^{−1}g(x) ∩ T_{v}(f, B), because these intersection points define new starting points on a possibly new connected component of T_{v}(f, B).

But these intesection points are critical points of the function f|_{g^{−1}g(x)}.

Thus, for each touching point, we have to solve a problem of the same form as the original one, but of dimension n − 1.

Recursion thus finally leads to a locally 1–dimensional, connected set Ω(f, B) which contains all critical points of f.

(Actually Ω is not completely specified by the above construction. We need to say, which vector v_{i} we take to solve the problem in dimension i but the specification can easily be completed.)

However, Ω cannot be traced in general, because of one-way-streets. This might already have been suspected in view of the indentation argument.

Bild malen

However, on the basis of Ω one can define a directed Graph D, describing which critical points can be reached by starting from other critical points. D will be weakly connected, but only if D is strongly connected, all critical points can be reached by starting in any critical point.

Questions:

• How does the connective structure of D depend on f and the vectors v_{i} used in the subproblems?

• Under what circumstances is T_{v}(F, B) connected?

• How does one efficiently implement the numerical tracing of Newton trajectories and the dimensional recursion described above?

• What can be said about the topological and geometrical stucture of T_{v}(f, B). How do these structures vary with v?

• Under which conditions is T_{v}(f, B) a 1–dimensional manifold, where do bifurcations occur, when is the dimension of T_{v}(f, B) locally greater than one?

• … a countable number of further questions.

We now consider the geometrical and topological structure of Newton trajectories more closely. First, why are the sets

{x | F (x) ∥ v}

called Newton trajectories?

Newtons method for the determination of a local zero is

x_{n+1} = x_{n} + h_{n}(DF (x_{n}))^{−1}F (x_{n}),

with suitable stepsizes h_{i}. This equation can be considered to be an Euler approximation to the Newton differential equation (NDE):

x(t) = −(DF (x(t))^{−1}F (x(t)),

which can be written as

\frac{d}{dt}F (x(t)) + F (x(t)) = 0.

From this:

F (x(t)) := F (x(0))e^{−t},

where the integration is possible, and we see that on the trajectories of the NDE we have F (x(t))∥F (x(0)); this is the connection to the Newton trajectories defined previously.

Since the NDE is not defined on all of IR^{n} we instead consider the desingularized Newton differential equation (dNDE):

ẋ = −D̃F(x)F (x),

where Ã denotes the adjoint matrix of A, which satisfies ÃA = det(A)I.

Obviously the phase portraits of the NDE and the dNDE are the same, up to orientation, where both are defined.

Bild malen

Linearizing the dNDE in a zero x^{∗} of F (remember det(DF (x^{∗})) ≠ 0) one obtains locally

−D̃F(x)F (x) ≈ − det(DF (x^{∗}))(x − x^{∗}).

Thus the zeros of F are attractors or repellors for the trajectories of the dNDE if det(DF (x^{∗})) is respectively greater or less than zero.

The rhs of the dNDE is zero for x ∈ Zero(F) but also for points in which F (x) ≠ 0 but still D̃F(x)F (x) = 0. These points are called extraneous singularities of F and we denote the set of these points by ExS(F).

The structure of ExS(F) can be very complicated in general. It was studied under additional genericity assumptions notably by Jongen, Jonker and Twilt. One can show, for instance, that for F in a C^{∞}-generic subset of C^{∞}(IR^{n}, IR^{n}) the set ExS(F) is a closed stratified subset in IR^{n} of dimension ≤ n − 2.

There are many results on the local geometry of Newton trajectories and the Newton flow defined by the dNDE. Also global results under certain boundary conditions (notably by Smale), and for meromorphic Newton flows (notably by Jongen, Jonker and Twilt).

However, these results do not help us with our problem of determining all zeros of F. How can we attack that problem?

In 1972 Branin suggested the following approach: Follow a trajectory of the dNDE until you hit a zero of F, then reverse the sign on the rhs of the dNDE and continue on the “other side” of the zero.

Bild malen

He reported encuraging results for some test problems in which he found many or all zeros. This triggered intensive research in this direction in the 70th. However, no generally applicable results for the global problem emerged and research in this area appearently declined, until, at the beginning of the 80th, Jongen, Jonker and Twilt started their research on the structure of ExS(F) and the meromorphic case.

We now come back to Branins original idea and consider the question: How can Newton trajectories help in the determination of all zeros of a function F?

All early research was based on the study of the NDE or the dNDE — thus mainly analytical methods were used. Instead, we will base our study on the definition:

F_{V} (F) := {x | F (x) ∈ V^{⊥}},

with a 1-codimensional linear subspace V of IR^{n}.

This formulation demands at once a generalization, which proves to be useful: Definition 2 Let B ⊂ IR^{n}, F ∈ C(B, IR^{n}) and V ⊂ IR^{n} a linear subspace of codimension k. Then we call the set

F_{V} (F, B) := {x ∈ B | F (x) ∈ V^{⊥}}

a k–Newton-leaf (k-NL) for F.

The 0-NL for F is just the set Zero(F, B). A 1–NL is called a Newton trajectory and the n-NL is just B. ◇

Thus Branins idea was to trace a 1-Newton-leaf.

We make some observations:

(a) If V, W are linear subspaces of IR^{n} and if V ⊂ W then W^{⊥} ⊂ V^{⊥} and thus

F_{W}(F) ⊂ F_{V} (F).

(b) Zero(F) ⊂ F_{V} (F) for all subspaces V ⊂ IR^{n}.

(c) If V, W are linear subspaces of IR^{n}, then

(V + W)^{⊥} = V^{⊥} ∩ W^{⊥}

and thus

F_{V +W}(F) = F_{V} (F) ∩ F_{W}(F).

In view of (b): When is F_{V} (F) connected? If it is, an n-dimensional problem can be reduced to a k-dimensional problem!

Next we develop a different description for Newton leafs that in many cases is easier to work with, than with the original definition.

Let V be a k-codimensional subspace in IR^{n}. Let A be an (n − k) × n–matrix of rank n − k such that ker A = V^{⊥}. We say, such a matrix is assiciated with V. Now consider the map

F_{A} : IR^{n} → IR^{n−k}, x ↦ AF (x).

Then obviously

F_{V} (F, IR^{n}) = F_{A}^{−1}(0)

and

F_{V} (F, B) = F_{A}^{−1}(0) ∩ B.

Thus the Newton leaf F_{V} (F, IR^{n}) is a closed manifold of dimension k in IR^{n}, if for all x ∈ F_{V} (F, IR^{n}) we have

rank A · DF (x) = dim V = n − k.

We call a point x ∈ F_{V} (F, IR^{n}) for which this rank-relation does not hold an extraneous singularity of F_{V} (F, B). The set of these points is denoted by ExS_{V} (F, B).

If ExS_{V} (F, B) = ∅ we call F_{V} (F, B) a regular Newton leaf.

How can the points in ExS_{V} (F, B) be characterized? Lemma 1 Let B ⊂ IR^{n}, F ∈ M^{∗}(B, IR^{n}), and V a linear subspace of codimension k in IR^{n}. Let {v_{1},…, v_{k}} be a basis of V^{⊥}. Then x ∈ F_{V} (F, B) is an extraneous singularity of F_{V} (F, B) iff

rank[DF (x), v_{1},…, v_{k}] < n

or, equivalently,

ker(DF (x))^{t} ∩ V ≠ {0}.
◇

This characterization can be used to investigate the local geometry of the Newton leafs and the local phase portrait around an extraneous singularity of F_{V} (F, B). We will, however, not precede in this direction, since this question is of minder importance for our practical problem.

We now collect some observations about Newton leafs. First a simple theorem which we prove in order to show how the definitions are put to work. Call to sets A, B controversal if neither A ⊂ B nor B ⊂ A. Theorem 2 If two Newton leafs F_{V} (F), F_{W}(F) are controversal, then the corresponding tangent spaces in any point x ∉ F_{V +W}(F) are controversal. ◇

Proof: By assumption neither F_{V} (F) ⊂ F_{W}(F) nor F_{W}(F) ⊂ F_{V} (F). We must to show that for any point x ∉ ExS_{V +W}(F) we have:

ker A_{W}DF (x) ⊄ ker A_{V} DF (x)

and

ker A_{V} DF (x) ⊄ ker A_{W}DF (x),

where A_{W}, A_{V} are the corresponding associated matrices.

Suppose ker A_{W}DF (x) ⊂ ker A_{V} DF (x). Since by assumption x ∉ F_{V +W}(F) the two matrices

( \begin{matrix}A_{W}DF (x) \\ A_{V} DF (x) \end{matrix} ) and ( \begin{matrix}A_{W} \\ A_{V} \end{matrix} )

have the same rank and are thus equivalent. It follows that there are regular square matrices S and T such that

S ( \begin{matrix}A_{W}DF (x)T \\ A_{V} DF (x)T \end{matrix} ) = ( \begin{matrix}A_{W} \\ A_{V} \end{matrix} ) .

Suppose A_{W}z = 0, then also A_{W}DF (x)T z = 0. From ker A_{W}DF (x) ⊂ ker A_{V} DF (x) it follows that A_{V} DF (x)T z = 0, and thus also A_{V} z = 0. Thus the kernel of A_{W} is contained in the kernel of A_{V} and so F_{W}(F) ⊂ F_{V} (F). □

Note that Newton leafs are thus controversal in any nondegenerate zero of F (or any critical point of f).

From the implicit function theorem applied to A_{V} DF (x^{∗}) in a zero x^{∗} of F one deduces at once, that a Newton leaf approaching x^{∗} closely enough must pass through x^{∗}.

Also one easily sees, that a Newton trajectory, intersecting a k-Newton leaf in x ∉ Zero(F) must be wholly contained in this Newton leaf.

Call a connected set free with respect to f (or F) if it contains no critical point of f (no zero of F). Theorem 3 Suppose F ∈ M^{∗}(IR^{n}) and k > 0. Then any compact free component C of a k–Newton leaf of F in IR^{n}, which does not contain an extraneous singularity of F, posesses a continuous, nowhere vanishing tangential vectorfield. ◇

Such a vectorfield is given by the tangent vectors of the Newton trajectories on C.

Two zeros of F ∈ M^{∗}(B) which are adjacent along a single component of a nondegenerate Newton trajectory have different index. Similarly, for f ∈ M(B), two adjacent critical points have different quadratic index mod 2. Theorem 4 Let F ∈ M^{∗}(B) and 1 ≤ k ≤ n − 1. Then any compact component of any k-Newton leaf for F which does not intersect ∂B contains an even number of zeros of F. ◇

Observe that we do not make any assumptions on the extraneous singularities on the Newton leafs.

The proof is by induction and uses the above observation on the index of a zero and the Morse-Sard lemma.

Theorem 5 Let the boundary of the bounded open set U ⊂ IR^{n} be contained in a free component K of an (n − 1)-Newton leaf F_{V} (F, IR^{n}). Then

(i) Every component of U contains an even number of zeros of F.

(ii) Any component of U which contains a zero of F also contains an extraneous singularity of F.

(iii) If \overline{U} contains neither zeros nor extraneous singularities of F then there exists a continuous map U → U (\overline{U} → \overline{U} respectively) without fixed points.

◇

Corollary 6 Let F ∈ M(IR^{2}) and ExS(F) = ∅ then every compact component of a Newton trajectory contains at least two zeros of F. ◇

Question: What can be said about the topological structure of compact free Newton leafs in the case ExS(F) = ∅?

The optimum for application is a connected Newton trajectory. Then all zeros can be found by numerically tracing the single component. Techniques for connecting different components have been discussed at the beginning of my talk. Connected k-Newton leafs with k > n at least reduce the problem dimension.

We now consider the question when it is possible to connect all zeros by a net of Newton trajectories or, more generally, k-Newton leafs. Definition 3 Let B ⊂ IR^{n} and F ∈ M^{∗}(B, IR^{n}). The we define, for k = 0, 1,…, n graphs Γ^{k}(F, B). The vertices of Γ^{k}(F, B) are the zeros of F. Two vertices u, v in Γ^{k}(F, B) are connected by an edge iff u ≠ v and there exists a k–NL K of F such that u and v are contained in a single component of K. ◇

Observe that for 0 ≤ l ≤ k ≤ n the graph Γ^{l}(F, B) is a spanning subgraph of Γ^{k}(F, B).

The graph Γ^{1}(∇f, IR^{n}) is similar to the graph Γ(f) defined in an early paper by Jongen, Jonker and Twilt.

JJT proved that for Morsefunctions f : IR^{2} → IR and if ExS(f, IR^{2}) = ∅ then Γ(f) is a forest.

Furthermore, if f ∈ C^{∞}(IR^{n}IR), there are no extraneous singularities and no unbounded component of a Newton trajectory for f is free then Γ(f) is connected.

The first result holds only in IR^{2}. The main limitation however is the assumption that f has no extraneous singularities which in practise is seldom fulfilled.

We now consider generalizations which are more applicable in practise, namely

• restiction to a subset B in IR^{n},

• generalization to general Newton leafs and

• removing the restriction ExS(F) = ∅.

Simple examples show, that the assumption ExS(F) = ∅ cannot simply be removed. It must be substituted by something weaker.

Definition 4 Let B ⊂ IR^{n}, F ∈ M^{∗}(B). Then we say the condition C_{k}(B) is fulfilled if no k–NL for F contains more than at most one unbounded component. ◇

Observe that condition C_{k}(B) is satisfied if B is bounded. C_{1}(IR^{n}) holds for F = ∇f if f is bounded from below and the level sets

{x ∈ IR^{n} | f(x) ≤ α}

are compact and convex for all large enough α. Lemma 2 Suppose B ⊂ IR^{n} is closed, F ∈ M^{∗}(B) and z^{∗} ∈ Zero(F, B). Suppose further condition C_{k}(B) is satisfied. Then the set

R(z^{∗}) := ⋃_{V ∈G(k,n)} C_{z^{∗}}F_{V} (F, B)

is closed in B. ◇

If C_{k}(B) is not satisfied, then R(z^{∗}) will not be closed in general.

Bild malen

Theorem 7 Suppose B ⊂ IR^{n} is closed and connected, F ∈ M^{∗}(B), k > 0 and condition C_{k}(B) is satisfied. Then: If no component of any k–NL for F is free, then Γ^{k}(F, B) is connected. ◇

To prove this, one defines Γ to be the set of vertices of a connected component of the graph Γ^{k}(F, B) and considers the set

R := ⋃_{z^{∗}∈Γ} R(z^{∗}).

This set is closed by the above lemma. One then shows R = B. This means, any zero of F is contained in a component of a k-NL which also contains a pont from Γ. Thus all vertices from Γ^{k}(F, B) are also contained in Γ.

If condition C_{k}(B) is not satisfied one can in some cases use the following result: Theorem 8 If B ⊂ IR^{n} is open (!) and connected, F ∈ M^{∗}(B), k > 0, no unbounded component of a k-NL contains an extraneaous singularity and no component of any k–NL for F is free, then Γ^{k}(F, B) is connected. ◇

Bild malen

The condition B open can not simply be droped, because then some connecting components of Newton leafs could be blocked by a suitable structure of B.

Bild malen

The condition that no component of any k–NL for F is free is cumbersome. Could we get rid of it? Not easily because since in our theorems B is rather arbitrary one could in many cases cut off connecting leafs by a suitable modification of B without making B disconnected. Also, free (n − 1)–leafes separate B into two sets and no Newton trajectory can reach one from the other. So, if both contain zeros of F, Γ^{1}(F, B) cannot be connected.

Still, something can be said without supposing that no component of any k–NL for F is free. A set is bound if it contains a zero of F. Now define the sets:

bnd_{k}(F, B) := {x ∈ B |There exists a bound

k–NL component through x}

bnd_{k}^{∗}(F, B) := {x ∈ B |Every k–NL compo-

nent through x is bound} Then one can prove: Theorem 9 Let B ⊂ IR^{n} be closed and connected, F ∈ M^{∗}(B) and the condition C_{k}(B) be satisfied. Then:

(i) If bnd_{k}(F, B) is disconnected, then Γ^{k}(F, B) is disconnected too.

(ii) If bnd_{k}^{∗}(F, B) is connected, then Γ^{k}(F, B) is also connected.

◇

If k = 1 the gap in the above theorem can be closed, because then we obviously have the relation bnd_{1}(F, B) = bnd_{1}^{∗}(F, B): Theorem 10 Let B ⊂ IR^{n} be closed and connected, F ∈ M^{∗}(B) and the condition C_{1}(B) be satisfied. Then Γ^{1}(F, B) has as many connected components as bnd_{1}(F, B). Especially Γ^{1}(F, B) is connected iff bnd_{1}(F, B) is connected. ◇

For the application of these ideas to practical problems it would be nice to characterize those F for which all k–Newton leafs for a certain k are connected. Some experience with Newton trajectories can convince one, that this is just about never the case.

If k > 0 and there are no extraneous singularities and F ∈ M^{∗}(IR^{n}) one can show that all k–NL for F are connected iff condition C_{k}(IR^{n}) is satisfied and for n = 2 one obtains the following disappointing result: Theorem 11 Suppose F ∈ M^{∗}(IR^{2}) has at least 3 zeros and there are no extraneous singularities. Then there is a Newton trajectory T for F such that not all zeros are on one component of T . ◇

I do not know wether a similar result can be proved for higher dimensions. However, I suppose so.

We now consider the question under which conditions there exist connected Newton leafs. A first result, following from a global implicit function theorem is Theorem 12 Let F_{V} (F, IR^{n}) be a k-NL for F and let A be an (n − k) × k–matrix associated with V. If the (n − k) × (n − k)–matrix

A · (DF (x))(DF (x))^{t} · A^{t}

is uniformly positive definite on IR^{n}, then the Newton leaf F_{V} (F, IR^{n}) is connected. ◇

This condition is rather strong, but still applicable in some cases. If, for instance, some partial derivative ∂F_{i}/∂x_{j} can be uniformly bounded away from zero on all of IR^{n}, then the (n − 1)- NL F_{V} (F, IR^{n}) for V = ⟨e_{i}⟩ is connected and the search for the zeros of F can be restricted to a connected (n − 1)–Manifold in IR^{n}.

Global versions of the implicit function theorem can be derived from global inverse function theorems with the aid of Theorem 13 Suppose F : D ⊂ IR^{n} → IR^{k}, k < n and suppose there exists a map G : D → IR^{n−k} such that H := (F, G) : IR^{n} → IR^{n} is a global homeomorphism. Let x_{0} ∈ D. Then F^{−1}F (x_{0}) is connected if and only if H(D) ∩ {F (x_{0})} × IR^{n−k} is connected. ◇

But the conditions for connectedness of Newton leafs derived from global implicit function theorems are generally far to strong. Other techniques must be developed.

One can give simple examples in IR^{2} which show that even if Γ^{1}(F, IR^{2}) is a complete graph it is possible that no Newton trajectory for F is connected. However, one can prove: Theorem 14 Let B ⊂ IR^{n} be closed, F ∈ M^{∗}(B) and suppose no more than one component of any Newton trajectory for F intersects ∂B. Suppose F hat exactly 3 zeros in B and Γ^{1}(F, B) is connected. Then there is a component of a Newton trajectory for F which contains all three zeros. ◇

The condition is satisfied in case B convex, F = ∇f and f constant on the boundary ∂B of B, as considered at the beginning of my talk.

Questions:

• Under what conditions can one guarantee the existence of a connected k–Newton–leaf and how can such leafs be constructed?

• What can be said about the topological structure of compact free k–Newton–leafs?

• How can one describe the possible bifurcations in the structure of the Newton leafs for varying V ∈ G(k, n)?

• How can one put the geometrical and topological properties of the “foliations” of IR^{n} provided by Newton leafs into a totally geometric setting, i.e. only talking about settheoretic global properties of the leafs?

• How can the condition C_{k}(B) be characterized by a condition which can easily be checked in practice. This should have something to to with a generalized Palais-Smale condition.

• How can one efficiently build the condition x ∈ F_{V} (F) into a numerical zero-finding algorithm?

• What would the theory look like for compact manifolds? There are several possibilities for generalizations to this case.

• How can the meromorphic functions in the complex plane be characterized, for which there exists a connected Newton trajectory?

• How can the functions be characterized, for which no Newton leaf contains a free component? (Example: |p(x + iy)|^{2}.)

• How many more slides do I have?