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.     

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.     

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.     

The structure of nonsingular polynomial matrices

LetK be a field and letL ∈ K ^{n × n [z]} be nonsingular. The matrixL can be decomposed as \(L(z) = \hat Q(z)(Rz + S)\hat P(z)\) so that the finite and (suitably defined) infinite elementary divisors ofL are the same as those ofRz + S, and \(\hat Q(z)\) and \(\hat P(z)^T\) are polynomial matrices which have a constant right inverse. If $$Rz + S = \left( {\begin{array}{*{20}c} {zI - A} & 0 \\ 0 & {I - zN} \\ \end{array} } \right)$$ andK is algebraically closed, then the columns of \(\hat Q\) and \(\hat P^T\) consist of eigenvectors and generalized eigenvectors of shift operators associated withL.     

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.     

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.     

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.     

Aspects of insertion in random trees

A method formulated by Yao and used by Brown has yielded bounds on the fraction of nodes with specified properties in trees bult by a sequence of random internal nodes in a random tree built by binary search and insertion, and show that in such a tree about bounds better than those now known. We then apply these methods to weight-balanced trees and to a type of “weakly balanced” trees. We determine the distribution of the weight-balance factors of the internal nodes in a random tree built by binary search and insertion and show that in such a tree about 72% of all internal nodes have weight balance factors lying between \(1 - \sqrt 2 /2\) and \(\sqrt 2 /2\) .     

Ü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.     

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.     

Konvergenz von quadratischen Interpolations- und Flächenabgleichssplines

The purpose of this paper is to show that for continuous functions the related quadratic splines converge without any assumption on the spline grid. The points of the interpolatory grid can be chosen between the corresponding points of the spline grid with a division ratio from \(\frac{{\sqrt 2 }}{2}\) to \(1 - \frac{{\sqrt 2 }}{2}\) . In the case of continuously differentiable functions the division ratio can even be taken between 0 and 1; in addition, the order of convergence is increased. For twice differentiable functions the full order of convergence is obtained. Analogous results about the convergence of histo splines are proved.     

Parallel computation of disease transforms

Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time \(\mathcal{O}\) (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple \(\mathcal{O}\) (logn) algorithm for the distance transform with respect to theL ₁-metric, an \(\mathcal{O}\) (log² n) algorithm for the transform with respect to theL _∞-metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL _k -metric and takes time \(\mathcal{O}\) (log³ n).     

Interval methods that are guaranteed to underestimate (and the resulting new justification of Kaucher arithmetic)

One of the main objectives of interval computations is, given the functionf(x ₁, ...,x _n ), andn intervals $\bar x_1 ,...,\bar x_n$ , to compute the range $\bar y = f(\bar x_1 ,...,\bar x_n )$ . Traditional methods of interval arithmetic compute anenclosure $Y \supseteq \bar y$ for the desired interval $\bar y$ , an enclosure that is often an overestimation. It is desirable to know how close this enclosure is to the desired range interval. For that purpose, we develop a new interval formalism that produces not only the enclosure, but also theinner estimate for the desired range $\bar y$ , i.e., an interval y such that $y \subseteq \bar y$ . The formulas for this new method turn out to be similar to the formulas of Kaucher arithmetic. Thus, we get a new justification for Kaucher arithmetic.     

Frequency capping in online advertising

We study the following online problem. There are n advertisers. Each advertiser \(a_i\) has a total demand \(d_i\) and a value \(v_i\) for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated with a user, and each advertiser \(a_i\) is willing to accept no more than \(f_i\) units associated with any single user (the value \(f_i\) is called the frequency cap of advertiser \(a_i\) ). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic \(3/4\) -competitiveness upper bound, which holds even when all frequency caps are \(1\) , and all advertisers share identical values and demands. A competitive ratio approaching \(1-1/e\) can be achieved via a reduction to a different model considered by Goel and Mehta (WINE ‘07: Workshop on Internet and Network, Economics: 335–340, 2007). Our main contribution is analyzing two \(3/4\) -competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal integral demand to frequency cap ratios. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the ratio of \(1-1/e\) .     

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′).     

Growth rates for persistently excited linear systems

We consider a family of linear control systems \(\dot{x}=Ax+\alpha Bu\) on \(\mathbb {R}^d\) , where \(\alpha \) belongs to a given class of persistently exciting signals. We seek maximal \(\alpha \) -uniform stabilization and destabilization by means of linear feedbacks \(u=Kx\) . We extend previous results obtained for bidimensional single-input linear control systems to the general case as follows: if there exists at least one \(K\) such that the Lie algebra generated by \(A\) and \(BK\) is equal to the set of all \(d\times d\) matrices, then the maximal rate of convergence of \((A,B)\) is equal to the maximal rate of divergence of \((-A,-B)\) . We also provide more precise results in the general single-input case, where the above result is obtained under the simpler assumption of controllability of the pair \((A,B)\) .     

Deriving length two path centered surface area for the arrangement graph: a generating function approach

We discuss the notion of \(H\) -centered surface area of a graph \(G\) , where \(H\) is a subgraph of \(G\) , i.e., the number of vertices in \(G\) at a certain distance from \(H\) , and focus on the special case when \(H\) is a length two path to derive an explicit formula for the length two path centered surface area of the general and scalable arrangement graph, following a generating function approach.