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.     

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.     

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.     

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

Small-amplitude limit cycles of Liénard systems

This paper is concerned with the study of second order differential equations of Liénard type: (A) $$\ddot x + f(x)\dot x + g(x) = 0$$ where f and g are polynomials. The equation (A) can also be written as a system of the form (B) $$\dot x = y - F(x),\dot y = - g(x),$$ , where \(F(x) = \mathop \smallint \limits_0^x f(\xi )d\xi \) . The results described here are mainly concerned with small amplitude limit cycles; that is, limit cycles which may be bifurcated from the origin on perturbation of the coefficients of F and g. The problem is to estimate the maximum number of limit cycles which various classes of systems of the form (B) can have; this is a special case of the second part of Hilbert’s sixteenth problem. Most of the calculations have been carried out on a computer using the REDUCE symbolic manipulation package.     

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.     

A combinatorial method for the generation of normally distributed random numbers

The proposed method generates standard normal variablesx. In 84.27% of all cases sampling from the centre \((|x| \leqslant \sqrt 2 )\) of the normal distribution is carried out using a variant ofJ. v. Neumann's algorithm for the generation of exponentially distributed random numbers. For sampling from the tails \((|x| > \sqrt 2 )\) the same method byJ. v. Neumann is combined with an acceptance-rejection approach ofG. Marsaglia.     

Fault tolerance of hypercubes and folded hypercubes

Let \(G = (V,E)\) be a connected graph. The conditional edge connectivity \(\lambda _\delta ^k(G)\) is the cardinality of the minimum edge cuts, if any, whose deletion disconnects \(G\) and each component of \(G - F\) has \(\delta \ge k\) . We assume that \(F \subseteq E\) is an edge set, \(F\) is called edge extra-cut, if \(G - F\) is not connected and each component of \(G - F\) has more than \(k\) vertices. The edge extraconnectivity \(\lambda _\mathrm{e}^k(G)\) is the cardinality of the minimum edge extra-cuts. In this paper, we study the conditional edge connectivity and edge extraconnectivity of hypercubes and folded hypercubes.     

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.     

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

Klassische Runge-Kutta-Nyström-Formeln mit Schrittweiten-Kontrolle für Differentialgleichungen\ddot x = f(t,x,\dot x)

New explicit Runge-Kutta-Nyström formulas for general second-order differential equations \(\ddot x = f(t,x,\dot x)\) are presented. The formulas include a stepsize control, based on a complete coverage of the leading term of the local truncation error inx. Examples show — for the same accuracy — a saving on computer time of 25% to more than 50% when comparing the new formulas with our earlier Runge-Kutta formulas for first-order differential equations. An illustrative example is presented.     

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.     

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.     

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.     

A new method for automatical computation of error bounds for the set of all solutions of nonlinear boundary value problems

We consider nonlinear boundary value problems with arbitrarily many solutionsuεC ² [a, b]. In this paper an Algorithm will be established for a priori bounds \(\bar u,\bar d \in C[a,b]\) with the following properties:

1. For every solutionu of the nonlinear problem we obtain $$\bar u(x) \leqslant u(x) \leqslant \bar u(x), - \bar d(x) \leqslant u'(x) \leqslant \bar d(x)$$ for any,xε[a, b].
2. The bounds \(\bar u\) and % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGabmizayaara% aaaa!36EE!\[\bar d\] are defined by the use of the functions exp, sin and cos.
3. We use neither the knowledge of solutions nor the number of solutions.

     

A note on the complexity of program evaluation

A simple problem concerning evaluation of programs is shown to be nonelementary recursive. The problem is the following: Given an input-free programP (i.e. all variables are initially 0) without nested loops using only instructions of the formx ← 1, x ← x + y, \(x \leftarrow x\dot - y\) ,do x... end, doesP output 0? This problem has time complexity \(2^{2^{ {\mathinner{\mkern2mu\raise1pt\hbox{.}\mkern2mu \raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}} ^2 } } \) }cn-levels for some constantc. Other results are presented which show how the complexity of the 0-evaluation problem changes when the nonlooping instructions are varied. For example, it is shown that 0-evaluation is PSPACE-complete even for the case when the nonlooping instructions are onlyx ← x + 1,if x = 0then y ←y \(y \leftarrow y\dot - 1\) .     

Problemi al contorno per equazioni del tipoy″=f(x,y) trattati come equazioni integrali con metodi alle differenze finite di elevata accuratezza

This work faces the problem of the numerical treatment on digital computers of boundary value problems of the type: $$y'' = f(x,y); y(a) = A,y(b) = B$$ through the reduction into the equivalent integral equation: $$y(x) = \mathop \smallint \limits_a^b g_K (x,\xi )[K^2 y(\xi ) - f(\xi ,y(\xi ))]d\xi $$ whereg _K (x,ξ) is the Green function associated to the differential operator \(\frac{{d^2 }}{{dx^2 }} - K^2 \) . I have extended to this problem a discrete analogue of higher accuracy introduced in [1] with reference to a boundary value problem analised under a differential point of view: this extention costitutes the original part of the work. The above problem is analysed with reference to the discretization error and the convergence of the discrete analogue solution algorithm; the actnal numerical treatment of a few systems follows.     

Greedy routing in small-world networks with power-law degrees

In this paper we study decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variant of J. Kleinberg’s grid-based small-world model in which (1) the number of long-range edges of each node is not fixed, but is drawn from a power-law probability distribution with exponent parameter \(\alpha \ge 0\) and constant mean, and (2) the long-range edges are considered to be bidirectional for the purposes of routing. This model is motivated by empirical observations indicating that several real networks have degrees that follow a power-law distribution. The measured power-law exponent \(\alpha \) for these networks is often in the range between 2 and 3. For the small-world model we consider, we show that when \(2 < \alpha < 3\) the standard greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the grid, finishes in an expected number of \(O(\log ^{\alpha -1} n\cdot \log \log n)\) steps, for any source–target pair. This is asymptotically smaller than the \(O(\log ^2 n)\) steps needed in Kleinberg’s original model with the same average degree, and approaches \(O(\log n)\) as \(\alpha \) approaches 2. Further, we show that when \(0\le \alpha < 2\) or \(\alpha \ge 3\) the expected number of steps is \(O(\log ^2 n)\) , while for \(\alpha = 2\) it is \(O(\log ^{4/3} n)\) . We complement these results with lower bounds that match the upper bounds within at most a \(\log \log n\) factor.     

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