Verallgemeinerte Ausgleichsformeln und relativ optimale Formeln in Hilberträumen

A linear discretisation formula (1) for the approximation of a given linear functionalF over a Hilbert spaceH is called a ρ-optimal formula for ρ≧0, if it minimizes \(\left\| {F - \tilde F} \right\|_{H*} \) under the sidecondition \(r(\tilde F) \leqq \rho \) among all formulas \(\tilde F\) of type (1). Herein \(r(\tilde F)\) , is a suitably chosen parameter of the numerical instability of \(\tilde F\) (see (3)). \(\tilde F\) is called relative-optimal if \(\tilde F\) is ρ-optimal for \(r(\tilde F) \leqq \rho \) . For very general classes of HilbertspacesH _ε, ε>0, of analytic functions (whose regions of regularity cover, the hole complex plane for ε→0) we investigate asymptotic properties of relative-optimal formulas: as a main result it is shown that they converge (for ε→0) to the well-known least-square approximate formulas of to a generalized type of least square formulas.     

Converging multistep methods for initial value problems involving multivalued maps

Every consistent and strongly stable multistep method of stepnumberk yields a solution, of the setvalued initial value problem \(\dot y \in F(t,y),y(t_0 ) = y_0 \) . The setF(t, z) is assumed to be nonvoid, convex and closed. Upper semicontinuity of F with respect to both variables is not required everywhere. If the initial value problem is uniquely solvable, the solutions of the multistep method will converge to the solution of the continuous problem. These results carry over to functional differential equations \(\dot y \in F(t,M_t y)\) of Volterra type and to discontinuous problems \(\dot y(t) = f(t,M_t y)\) in the sense of A.F. Filippov. A difference method is applied to the discontinuous delay equation \(\ddot x(t) + 2D\dot x(t) + \omega ^2 x(t) = = - \operatorname{sgn} (x(t - \tau ) + \dot x(t - \tau ))\) . In the limit τ→0 we obtain results for the problem \(\ddot x + 2D\dot x + \omega ^2 x = = - \operatorname{sgn} (x + \dot x)\) which cannot be solved classically everywhere.     

Ableitungsfreie Abschätzungen bei trigonometrischer Interpolation und Konjugierten-Bestimmung

Letf be 2 π-periodic,T _v its trigonometric interpolation polynomial, \(\bar f\) and \(\bar T_T \) the conjugates off andT _T, respectively. In this note the maximum norms ‖f-T _T‖, \(\parallel f - \bar T_T \parallel \) ‖f′?T _′‖ and \(\parallel \bar f' - \bar T'_T \parallel \) are estimated by the Fourier coefficients off. Iff is analytic on Φ results by Kress [2], [3] are obtained.     

Tree acceptors and grammar forms

The following generalization of a well-known result in tree acceptors is established. For each context-free grammarG and tree acceptor \(\mathfrak{A}\) there exists a strict interpretationG′ ofG and a yield-preserving projection π′ from the trees over the alphabet ofG′ into the trees over the alphabet ofG such that \(\pi '(D_{G'} ) = D_G \cap T(\mathfrak{A})\) ,D _G andD _G′ being the derivation trees ofG′ andG respectively and \(T(\mathfrak{A})\) the trees accepted by \(\mathfrak{A}\) . Moreover, ifG is unambiguous, then (a)G′ can be chosen unambiguous, and (b) there is an unambiguous strict interpretationG″ ofG such thatL(G″)=L(G)?L(G′).     

Numerical determination of Cauchy principal value integrals

A quadrature rule for numerical evaluation of Cauchy principal value integrals of the type \(\int\limits_{ - 1}^1 {f(x)/(x - a) dx} \) where ?1<a<1 andf(x) possesses complex singularities near to the path of integration has been formulated. An analysis of the error has been provided.     

Properties of interval operators

In this paper we give some properties of interval operatorsF which guarantee the convergence of the interval sequence {X _k} defined byX _k+1:=F(X_k)∩X_k to a unique fixed interval \(\hat X\) . This interval \(\hat X\) encloses the “zero-set”X ^* of a function strip \(G(x): = [g(x),\bar g(x)]\) . for some known interval operators we investigate under which assumptions these properties are valid.     

Fast reversible coding and indexing of colorations

Given a non-branched tree withn vertices. Then, by ann-g-coloration we understand a partition of the set of vertices into no more thang classes, such that adjacent vertices belong to different classes. Supposed the set \(\mathfrak{S}\) of alln-g-colorations (for givenn andg) is lexicographically ordered, here are given two algorithms: the first directly determines (without using the set proper) the ordinal number of an arbitrary element of \(\mathfrak{S}\) ; the other directly generates an element of \(\mathfrak{S}\) from its given ordinal number.     

Über eine Methode zur Lösung eines linearen Gleichungssystems

In the paper a direct method for the solution of a system of linear equations with a square, regular matrix ofn-th order is given. The method solves this system in \(\frac{{3 - \sqrt 2 }}{6}n^3 + O(n^2 )\) multiplications. By the recursive application of this method the number of multiplications is decreasing to \(\frac{{n^3 }}{6} + O(n^2 )\) . The results of numerical experiments and their comparison with Gauß-elimination are also given.     

Projecting CLPR constraints

The presentation of constraints in a usable form is an essential aspect of Constraint Logic Programming (CLP) systems. It is needed both in the output of constraints, as well as in the production of an internal representation of constraints for meta-level manipulation. Typically, only a small subset \(\tilde x\) of the variables in constraints is of interest, and so an informal statement of the problem at hand is: given a conjunction \(c(\tilde x,\tilde y)\) of constraints, express the projection \(\exists \tilde y c(\tilde x,\tilde y)\) ofc onto \(\tilde x\) in the simplest form. In this paper, we consider the constraints of the CLP(R) system and describe the essential features of its projection module. One main part focuses on the well-known problem of projection inlinear arithmetic constraints. We start with a classical algorithm and augment it with a procedure for eliminating redundant constraints generated by the algorithm. A second part discusses projection of the other object-level constraints: equations over trees and nonlinear equations. The final part deals with producing a manipulable form of the constraints, which complicates the projection problem.     

Global structure of families of multivariable linear systems with an application to identification

The identification problem for linear stochastic systems may be stated roughly as follows: given observations on two stochastic processes which are the input and output of some unknown linear system, determine some estimate of the parameters of the system. A set of candidate linear systems which contains the “true” system is introduced, and probabilistic assumptions on the two stochastic processes turn the identification problem into the deterministic problem of minimizing some objective function over this candidate model set. If this set is a manifold, the existence of globally convergent identification algorithms hinges on the critical point behavior of the objective functions which it carries. By way of Morse Theory, the critical point behavior of objective functions on a manifold has implications with regard to the topology of the manifold. This paper analyzes the topology and critical point behavior of objective functions on a specific manifold of linear systems which appears frequently as the candidate model set in identification problems. This manifold is the set Σ of allm-input,p-output linear systems of fixed McMillan degree with real or complex coefficients. Over this manifold sits the principal bundle \(\tilde \Sigma\) of minimal realizations of systems in Σ It is shown that there exist three natural analytic metrics on the associated vector bundle. It is also shown that, in the real case, the first Stiefel-Whitney class of the bundle \(\tilde \Sigma\) has min(m, p)-1 nonvanishing powers; the same conclusion is drawn about the first Chern class of \(\tilde \Sigma\) in the complex case. These results, which follow from Morse Theory and some elementary homotopy and homology theory, imply that the category of the bundle \(\tilde \Sigma\) is at least min(m, p), and hence that the Lusternik-Schnirelmann category of Σ is at least min(m, p). It follows that canonical forms (i.e. sections of \(\tilde \Sigma\) ) may exist only when min(m, p) = 1 and that any objective function on Σ with compact sublevel sets has at least min(m, p) critical points. In particular, there exist on Σ no globally convergent gradient algorithms when min(m, p) > 1.     

Richardson Extrapolation on Some Recent Numerical Quadrature Formulas for Singular and Hypersingular Integrals and Its Study of Stability

Recently, we derived some new numerical quadrature formulas of trapezoidal rule type for the integrals \(I^{(1)}[g]=\int ^b_a \frac{g(x)}{x-t}\,dx\) and \(I^{(2)}[g]=\int ^b_a \frac{g(x)}{(x-t)^2}\,dx\) . These integrals are not defined in the regular sense; \(I^{(1)}[g]\) is defined in the sense of Cauchy Principal Value while \(I^{(2)}[g]\) is defined in the sense of Hadamard Finite Part. With \(h=(b-a)/n, \,n=1,2,\ldots \) , and \(t=a+kh\) for some \(k\in \{1,\ldots ,n-1\}, \,t\) being fixed, the numerical quadrature formulas \({Q}^{(1)}_n[g]\) for \(I^{(1)}[g]\) and \(Q^{(2)}_n[g]\) for \(I^{(2)}[g]\) are $$\begin{aligned} {Q}^{(1)}_n[g]=h\sum ^n_{j=1}f(a+jh-h/2),\quad f(x)=\frac{g(x)}{x-t}, \end{aligned}$$ and $$\begin{aligned} Q^{(2)}_n[g]=h\sum ^n_{j=1}f(a+jh-h/2)-\pi ^2g(t)h^{-1},\quad f(x)=\frac{g(x)}{(x-t)^2}. \end{aligned}$$ We provided a complete analysis of the errors in these formulas under the assumption that \(g\in C^\infty [a,b]\) . We actually show that $$\begin{aligned} I^{(k)}[g]-{Q}^{(k)}_n[g]\sim \sum ^\infty _{i=1} c^{(k)}_ih^{2i}\quad \text {as}\,n \rightarrow \infty , \end{aligned}$$ the constants \(c^{(k)}_i\) being independent of \(h\) . In this work, we apply the Richardson extrapolation to \({Q}^{(k)}_n[g]\) to obtain approximations of very high accuracy to \(I^{(k)}[g]\) . We also give a thorough analysis of convergence and numerical stability (in finite-precision arithmetic) for them. In our study of stability, we show that errors committed when computing the function \(g(x)\) , which form the main source of errors in the rest of the computation, propagate in a relatively mild fashion into the extrapolation table, and we quantify their rate of propagation. We confirm our conclusions via numerical examples.     

Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

Solving visibility and separability problems on a mesh-of-processors

In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms:

- AnO( \(\sqrt N\) time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in anN-vertex polygon, possibly with holes.

-O( \(\sqrt N\) ) time algorithms for computing on a Mesh-of-Processors of sizeN the set of all points on the boundary of anN-vertex polygonP which are visible in a given directiond as well as the visibility hull ofP for a given directiond.

- AnO( \(\sqrt N\) ) time algorithm for detecting on a Mesh-of-Processors of size 2N whether twoN-vertex polygons are separable in a given direction and anO( \(\sqrt {MN}\) ) time algorithm for detecting on a Mesh-of-Processors of sizeMN whetherM N-vertex polygons are sequentially separable in a given direction.

All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.     

Universal regular control for generic semilinear systems

We consider discrete-time projective semilinear control systems \(\xi _{t+1} = A(u_t) \cdot \xi _t\) , where the states \(\xi _t\) are in projective space \(\mathbb {R}\hbox {P}^{d-1}\) , inputs \(u_t\) are in a manifold \(\mathcal {U}\) of arbitrary finite dimension, and \(A :\mathcal {U}\rightarrow \hbox {GL}(d,\mathbb {R})\) is a differentiable mapping. An input sequence \((u_0,\ldots ,u_{N-1})\) is called universally regular if for any initial state \(\xi _0 \in \mathbb {R}\hbox {P}^{d-1}\) , the derivative of the time- \(N\) state with respect to the inputs is onto. In this paper, we deal with the universal regularity of constant input sequences \((u_0, \ldots , u_0)\) . Our main result states that generically in the space of such systems, for sufficiently large \(N\) , all constant inputs of length \(N\) are universally regular, with the exception of a discrete set. More precisely, the conclusion holds for a \(C^2\) -open and \(C^\infty \) -dense set of maps \(A\) , and \(N\) only depends on \(d\) and on the dimension of \(\mathcal {U}\) . We also show that the inputs on that discrete set are nearly universally regular; indeed, there is a unique non-regular initial state, and its corank is 1. In order to establish the result, we study the spaces of bilinear control systems. We show that the codimension of the set of systems for which the zero input is not universally regular coincides with the dimension of the control space. The proof is based on careful matrix analysis and some elementary algebraic geometry. Then the main result follows by applying standard transversality theorems.     

Bounds and domains of existence for hyperbolic initial value problems

Nonlinear hyperbolic initial value problems in plane regions are considered. By a discretization method which makes use of certain structure properties of the solutions \(\bar u\) , a finite dimensional technique is constructed which provides pointwise bounds for \(\bar u\) . At the same time, realistic informations on the domain of existence of \(\bar u\) can be obtained. The method's high degree of accuracy is shown by numerical examples.     

The Rank-Width of Edge-Coloured Graphs

A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${\mathbb{F}}^{*}$ -graphs— $\mathbb {F}$ -coloured graphs where each edge has exactly one colour from $\mathbb{F}\setminus \{0\},\ \mathbb{F}$ a field—and named respectively $\mathbb{F}$ -rank-width and $\mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $\mathbb{F}^{*}$ -graphs and prove that $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width are characterised by a list of $\mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $\mathbb{F}$ is finite). An algorithm that decides in time O(n ³) whether an $\mathbb{F}^{*}$ -graph with n vertices has $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $\mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs.     

Rounds in Combinatorial Search

A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.