Numerical evaluation of a solution of a special mixed-type differential-difference equation

The function * $$f(t) = \frac{{e^{ - \alpha \gamma } }}{\pi }\int\limits_0^\infty {\cos t \xi e^{\alpha Ci(\xi )} \frac{{d\xi }}{{\xi ^\alpha }},t \in R,\alpha > 0} $$ [Ci(x)=cosine integral, γ=Euler's constant] is studied and numerically evaluated;f is a solution to the following mixed type differential-difference equation arising in applied probability: ** $$tf'(t) = (\alpha - 1)f(t) - \frac{\alpha }{2}[f(t - 1) + f(t + 1)]$$ satisfying the conditions: i) $$f(t) \geqslant 0,t \in R$$ , ii) $$f(t) = f( - t),t \in R$$ , iii) $$\int\limits_{ - \infty }^{ + \infty } {f(\xi )d\xi = 1} $$ . Besides the direct numerical evaluation of (*) and the derivation of the asymptotic behaviour off(t) fort→0 andt→∞, two different iterative procedures for the solution of (**) under the conditions (i) to (iii) are considered and their results are compared with the corresponding values in (*). Finally a Monte Carlo method to evaluatef(t) is considered.     

The exact region of stability for MacCormack scheme

Let the two dimensional scalar advection equation be given by $$\frac{{\partial u}}{{\partial t}} = \hat a\frac{{\partial u}}{{\partial x}} + \hat b\frac{{\partial u}}{{\partial y}}.$$ We prove that the stability region of the MacCormack scheme for this equation isexactly given by $$\left( {\hat a\frac{{\Delta _t }}{{\Delta _x }}} \right)^{2/3} + \left( {\hat b\frac{{\Delta _t }}{{\Delta _x }}} \right)^{2/3} \leqslant 1$$ where Δ _t , Δ _x and Δ _y are the grid distances. It is interesting to note that the stability region is identical to the one for Lax-Wendroff scheme proved by Turkel.     

Generalizzazione di un metodo alle differenze finite per una classe di problemi al contorno di tipo ellittico

In a previous paper the numerical solution of a particular boundary-value problem for the «weakly linear» equation $$\Delta \left[ {u(P)} \right] = f(P,u)$$ was obtained and the convergence of a suitable finite-difference scheme was proved. This paper is concerned with the more general equation $$L\left[ {u(P)} \right] = f(P,u)$$ where $$L \equiv - \left[ {a\frac{\partial }{{\partial x^2 }} + c\frac{\partial }{{\partial y^2 }} + d\frac{\partial }{{\partial x}} + e\frac{\partial }{{\partial y}}} \right]$$ ; the solution is obtained using the same finite-difference scheme as in the previous paper, and sufficient condition for its convergence are given for this new case     

Sulle formule di quadratura di Tschebyscheff

For the Tschebyscheff quadrature formula: $$\int\limits_{ - 1}^1 {\left( {1 - x^2 } \right)^{\lambda - 1/2} f(x) dx} = K_n \sum\limits_{k = 1}^n {f(x_{n,k} )} + R_n (f), \lambda > 0$$ it is shown that the degre,N, of exactness is bounded by: $$N \leqslant C(\lambda )n^{1/(2\lambda + 1)} $$ whereC(λ) is a convenient function of λ. For λ=1 the complete solution of Tschebyscheff's problem is given.     

On the evaluation of one-dimensional Cauchy principal value integrals by rules based on cubic spline interpolation

In this note we consider the numerical evaluation of one dimensional Cauchy principal value integrals of the form $$\rlap{--} \smallint _a^b \frac{{k(x)f(x)}}{{x - \lambda }}dx, a< \lambda< b,$$ by rules obtained by “subtracting out” the singularity and then applying product quadratures based on cubic spline interpolation at equally spaced nodes. Convergence results are established for Hölder continuous functions of order, μ, 0<μ≤1, and asymptotic rates are obtained for functionsf≠C ^k [a, b],k=1, 2, 3 or 4. Some comparisons with other methods and numerical examples are also given.     

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.     

Una osservazione sulla stabilita secondo dahlquist

In this paper we prove that Dahlquist’s definition of stability is adegnate for the differential system $$\frac{{dy}}{{dx}} = Ay,$$ isn×n constant matrix with Jordan form not diagonal, but with characteristic roots equal to zero.     

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.     

Modifikationen des Pollard-Algorithmus

The factorization algorithm of Pollard generates a sequence in ? _n by $$x_0 : = 2;x_{i + 1} : = x_i^2 - 1(\bmod n),i = 1,2,3,...$$ wheren denotes the integer to be factored. The algorithm finds an factorp ofn within \(0\left( {\sqrt p } \right)\) macrosteps (=multiplications/divisions in ? _n ) on average. An empirical analysis of the Pollard algorithm using modified sequences $$x_{i + 1} = b \cdot x_i^\alpha + c(\bmod n),i = 1,2,...$$ withx ₀,b,c,α∈? and α≥2 shows, that a factorp ofn under the assumption gcd (α,p-1)≠1 now is found within $$0\left( {\sqrt {\frac{p}{{ged(\alpha ,p - 1}}} } \right)$$ macrosteps on average.     

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.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

On the convergence rate of SOR: A worst case estimate

LetA be any real symmetric positive definiten×n matrix, and κ(A) its spectral condition number. It is shown that the optimal convergence rate $$\rho _{SOR}^* = \mathop {\min }\limits_{0< \omega< 2} \rho (M_{SOR,\omega } )$$ of the successive overrelaxation (SOR) method satisfies $$\rho _{SOR}^* \leqslant 1 - \frac{1}{{\alpha _n \kappa (A)}}, \alpha _n \approx \log n.$$ This worst case estimate is asymptotically sharp asn→∞. The corresponding examples are given by certain Toeplitz matrices.     

One-step splitting methods for semi-discrete parabolic equations

The main purpose of the paper is to discuss splitting methods for parabolic equations via the method of lines. Firstly, we deal with the formulation of these methods for autonomous semi-discrete equations $$\frac{{dy}}{{dt}} = f(y),{\rm E}f{\rm E}non - linear,$$ f satisfying a linear splitting relation \(f(y) = \sum\limits_{i = 1}^k {f_i (y)} \) . A class of one-step integration formulas is defined, which is shown to contain all known splitting methods, provided the functionsf _i are defined appropriately. For a number of methods stability results are given. Secondly, attention is paid to alternating direction methods for problems with an arbitrary non-linear coupling between space derivatives.     

Lower bounds for polynomial evaluation and interpolation problems

We show that there is a set of pointsp ₁,p ₂,...,p _n such that any arithmetic circuit of depthd for polynomial evaluation (or interpolation) at these points has size $$\Omega \left( {\frac{{n\log n}}{{\log (2 + d/\log n}}} \right).$$ Moreover, for circuits of sub-logarithmic depthd, we obtain a lower bound of Ω(dn ^1+1/d ) on its size.     

Monte-Carlo-Methoden zur numerischen Quadratur auf Gruppen

Complex-valued functions — defined on compact, metric, abelian Groups —, which may be expanded in absolute convergent Fourier series are considered. For such functions Monte-Carlo-methods for the numerical computation of Integrals are given. For the remainderR _N in the integration formula the following estimate is given: $$R_{N_1 } = 0 \left( {\frac{{\log ^{1 + \varepsilon } N_i }}{{N_i }}} \right)$$ for a suitable sequence (N _i (ε)). This part of this paper is a generalisation of a paper ofZinterhof andSchmidt (see [9]). For functions, for which even the sum of theu-th power of the Fourier coefficients is convergent (u≤1/2), integration formulas are given, with the following estimate of the remainder: $$R_N = 0 \left( {\frac{1}{{N^t }}} \right) (t positiv, integer)$$ It is shown that theO-estimate of the remainder can not be essentially improved for any group. The second part of this paper gives an application of the integration formula for the numerical treatment of Fredholm's integral equation.     

A new PAC bound for intersection-closed concept classes

For hyper-rectangles in $\mathbb{R}^{d}$ Auer (1997) proved a PAC bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ , where $\varepsilon$ and $\delta$ are the accuracy and confidence parameters. It is still an open question whether one can obtain the same bound for intersection-closed concept classes of VC-dimension $d$ in general. We present a step towards a solution of this problem showing on one hand a new PAC bound of $O(\frac{1}{\varepsilon}(d\log d + \log \frac{1}{\delta}))$ for arbitrary intersection-closed concept classes, complementing the well-known bounds $O(\frac{1}{\varepsilon}(\log \frac{1}{\delta}+d\log \frac{1}{\varepsilon}))$ and $O(\frac{d}{\varepsilon}\log \frac{1}{\delta})$ of Blumer et al. and (1989) and Haussler, Littlestone and Warmuth (1994). Our bound is established using the closure algorithm, that generates as its hypothesis the intersection of all concepts that are consistent with the positive training examples. On the other hand, we show that many intersection-closed concept classes including e.g. maximum intersection-closed classes satisfy an additional combinatorial property that allows a proof of the optimal bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ . For such improved bounds the choice of the learning algorithm is crucial, as there are consistent learning algorithms that need $\Omega(\frac{1}{\varepsilon}(d\log\frac{1}{\varepsilon} +\log\frac{1}{\delta}))$ examples to learn some particular maximum intersection-closed concept classes.     

Node bisectors of Cayley graphs

A node bisector of a graph Γ is a subset Ω of the nodes of Γ such that Γ may be expressed as the disjoint union $$\Gamma = \Omega _1 \dot \cup \Omega \dot \cup \Omega _2 ,$$ , where $\left| {\Omega _1 } \right| \geqslant \frac{1}{3}\left| \Gamma \right|,\Omega _2 \geqslant \frac{1}{3}\left| \Gamma \right|$ , and where any path from Ω₁ to Ω₂ must pass through Ω. Suppose Γ is the Cayley graph of an abelian groupG with respect to a generating set of cardinalityr, regarded as an undirected graph. Then we show that Γ has a node bisector of order at mostc¦G ^1-1/r wherec is a constant depending only onr. We show that the exponent in this result is the best possible.     

Effective Randomness of Unions and Intersections

We investigate the ??-randomness of unions and intersections of random sets under various notions of randomness corresponding to different probability measures. For example, the union of two relatively Martin-Löf random sets is not Martin-Löf random but is random with respect to the Bernoulli measure $\lambda_{\frac{3}{4}}$ under which any number belongs to the set with probability $\frac{3}{4}$ . Conversely, any $\lambda_{\frac{3}{4}}$ random set is the union of two Martin-Löf random sets. Unions and intersections of random closed sets are also studied.     

Zur Charakterisierung und Berechnung von symmetrischen Kubaturformeln

The paper is concerned with the characterization and calculation of symmetric cubature formulae of degree 2k?1 for two-dimensional product-functionals. The number of knots of the cubature formulae satisfies the following relation: $$\frac{{k(k + 1)}}{2} + \left[ {\frac{k}{2}} \right] \leqslant r \leqslant \frac{{k(k + 1)}}{2} + \left[ {\frac{k}{2}} \right] + 1.$$ The systems of non-linear equations involved are either solved exactly or all solutions are computed with any precision using a program-package for symbolic and algebraic calculations.