Quantitative theorems on approximation by Bernstein-Stancu operators

In 1972 D. D. Stancu introduced a generalization \(L_{mp} ^{< \alpha \beta \gamma > }\) of the classical Bernstein operators given by the formula $$L_{mp}< \alpha \beta \gamma > (f,x) = \sum\limits_{k = 0}^{m + p} {\left( {\begin{array}{*{20}c} {m + p} \\ k \\ \end{array} } \right)} \frac{{x^{(k, - \alpha )} \cdot (1 - x)^{(m + p - k, - \alpha )} }}{{1^{(m + p, - \alpha )} }}f\left( {\frac{{k + \beta }}{{m + \gamma }}} \right)$$ . Special cases of these operators had been investigated before by quite a number of authors and have been under investigation since then. The aim of the present paper is to prove general results for all positiveL _mp ^<αβγ> 's as far as direct theorems involving different kinds of moduli of continuity are concerned. When applied to special cases considered previously, all our corollaries of the general theorems will be as good as or yield improvements of the known results. All estimates involving the second order modulus of continuity are new.     

On the computation of Tricomi's ψ function

Two methods for calculating Tricomi's confluent hypergeometric function are discussed. Both methods are based on recurrence relations. The first method converges like $$\exp ( - \alpha |\lambda |^{1/3} n^{2/3} )for some \alpha > 0$$ and the second like $$\exp ( - \beta |\lambda |^{1/2} n^{1/2} )for some \beta > 0.$$ Several examples are presented.     

Formule di quadratura «chiuse» di tipo gaussiano: Tabulzione dei nodi e dei coefficienti

The coefficientsA _hi and the nodesx _mi for «closed” Gaussian-type quadrature formulae $$\int\limits_{ - 1}^1 {f(x)dx = \sum\limits_{h = 0}^{2_8 } {\sum\limits_{i = 0}^{m + 1} {A_{hi} f^{(h)} (x_{mi} ) + R\left[ {f(x)} \right]} } } $$ withx _m0 =?1,x _{m, m+1} =1 andR[f(x)]=0 iff(x) is a polinomial of degree at most2m(s+1)+2(2s+1)?1, have been tabulated for the cases: $$\left\{ \begin{gathered} s = 1,2 \hfill \\ m = 2,3,4,5 \hfill \\ \end{gathered} \right.$$ .     

On some weight functions admitting (0, 2) quadrature formulae with a high algebraic degree of precision

The purpose of this paper is to find a class of weight functions μ for which there exist quadrature formulae of the form (1) $$\int_{ - 1}^1 {\mu (x) f(x) dx \approx \sum\limits_{k = 1}^n {(a_k f(x_k ) + b_k f''(x_k ))} }$$ , which are precise for every polynomial of degree 2n.     

The construction of cubature formulae for a family of integrals: A bifurcation problem

Cubature formulae of degree 11 with minimal numbers of knots for the integral $$\int\limits_{ - 1}^1 { \int\limits_{ - 1}^1 {(1 - x^2 )^\alpha } } (1 - y^2 )^\alpha f(x,y) dxdy \alpha > - 1$$ which are invariant under rotation over an angle π/2 are determined by a system of 18 nonlinear equations in 18 unknowns. We start with a known solution for this system for α=0. By varying α smoothly, the knots and weights of the cubature formula vary smoothly except in the singular solutions such as turning points and bifurcation points where new solutions branches arise. We use for this purpose the program AUTO. We obtain surprisingly many branches of cubature formulae.     

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

Quadrature rules for Prandtl's integral equation

In this paper we construct an interpolatory quadrature formula of the type $$\mathop {\rlap{--} \smallint }\limits_{ - 1}^1 \frac{{f'(x)}}{{y - x}}dx \approx \sum\limits_{i = 1}^n {w_{ni} (y)f(x_{ni} )} ,$$ wheref(x)=(1?x)^α(1+x)^β f _o(x), α, β>0, and {x _ni} are then zeros of then-th degree Chebyshev polynomial of the first kind,T _n (x). We also give a convergence result and examine the behavior of the quantity \( \sum\limits_{i = 1}^n {|w_{ni} (y)|} \) asn→∞.     

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.     

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.     

The addition of bounded quantification and partial functions to a computational logic and its theorem prover

We describe an extension to our quantifier-free computational logic to provide the expressive power and convenience of bounded quantifiers and partial functions. By quantifier we mean a formal construct which introduces a bound or indicial variable whose scope is some subexpression of the quantifier expression. A familiar quantifier is the Σ operator which sums the values of an expression over some range of values on the bound variable. Our method is to represent expressions of the logic as objects in the logic, to define an interpreter for such expressions as a function in the logic, and then define quantifiers as ‘mapping functions’. The novelty of our approach lies in the formalization of the interpreter and its interaction with the underlying logic. Our method has several advantages over other formal systems that provide quantifiers and partial functions in a logical setting. The most important advantage is that proofs not involving quantification or partial recursive functions are not complicated by such notions as ‘capturing’, ‘bottom’, or ‘continuity’. Naturally enough, our formalization of the partial functions is nonconstructive. The theorem prover for the logic has been modified to support these new features. We describe the modifications. The system has proved many theorems that could not previously be stated in our logic. Among them are:

? classic quantifier manipulation theorems, such as $$\sum\limits_{{\text{l}} = 0}^{\text{n}} {{\text{g}}({\text{l}}) + {\text{h(l) = }}} \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{g}}({\text{l}})} + \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{h(l)}};} $$

? elementary theorems involving quantifiers, such as the Binomial Theorem: $$(a + b)^{\text{n}} = \sum\limits_{{\text{l = }}0}^{\text{n}} {\left( {_{\text{i}}^{\text{n}} } \right)} \user2{ }{\text{a}}^{\text{l}} {\text{b}}^{{\text{n - l}}} ;$$

? elementary theorems about ‘mapping functions’ such as: $$(FOLDR\user2{ }'PLUS\user2{ O L) = }\sum\limits_{{\text{i}} \in {\text{L}}}^{} {{\text{i}};} $$

? termination properties of many partial recursive functions such as the fact that an application of the partial function described by $$\begin{gathered} (LEN X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F ({\rm E}QUAL X NIL) \hfill \\ {\rm O} \hfill \\ (ADD1 (LEN (CDR X)))) \hfill \\ \end{gathered} $$ terminates if and only if the argument ends in NIL;

? theorems about functions satisfying unusual recurrence equations such as the 91-function and the following list reverse function: $$\begin{gathered} (RV X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F (AND (LISTP X) (LISTP (CDR X))) \hfill \\ (CONS (CAR (RV (CDR X))) \hfill \\ (RV (CONS (CAR X) \hfill \\ (RV (CDR (RV (CDR X))))))) \hfill \\ X). \hfill \\ \end{gathered} $$

     

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.     

Characterization of the peak value behavior of the Hilbert transform of bounded bandlimited signals

The peak value of a signal is a characteristic that has to be controlled in many applications. In this paper we analyze the peak value of the Hilbert transform for the space $\mathcal{B}_\pi ^\infty $ of bounded bandlimited signals. It is known that for this space the Hilbert transform cannot be calculated by the common principal value integral, because there are signals for which it diverges everywhere. Although the classical definition fails for $\mathcal{B}_\pi ^\infty $ , there is a more general definition of the Hilbert transform, which is based on the abstract H ¹-BMO(?) duality. It was recently shown in [1] that, in addition to this abstract definition, there exists an explicit formula for calculating the Hilbert transform. Based on this formula we study properties of the Hilbert transform for the space $\mathcal{B}_\pi ^\infty $ of bounded bandlimited signals. We analyze its asymptotic growth behavior, and thereby solve the peak value problem of the Hilbert transform for this space. Further, we obtain results for the growth behavior of the Hilbert transform for the subspace $\mathcal{B}_{\pi ,0}^\infty $ of bounded bandlimited signals that vanish at infinity. By studying the properties of the Hilbert transform, we continue the work [2].     

Alcuni problemi relativi alle formule di quadratura del tipo di tchebycheff

In this paper we study quadrature formulas of the form $$\int\limits_{ - 1}^1 {(1 - x)^a (1 + x)^\beta f(x)dx = \sum\limits_{i = 0}^{r - 1} {[A_i f^{(i)} ( - 1) + B_i f^{(i)} (1)] + K_n (\alpha ,\beta ;r)\sum\limits_{i = 1}^n {f(x_{n,i} ),} } } $$ (α>?1, β>?1), with realA _i ,B _i ,K _n and real nodesx _n,i in (?1,1), valid for prolynomials of degree ≤2n+2r?1. In the first part we prove that there is validity for polynomials exactly of degree2n+2r?1 if and only if α=β=?1/2 andr=0 orr=1. In the second part we consider the problem of the existence of the formula $$\int\limits_{ - 1}^1 {(1 - x^2 )^{\lambda - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} f(x)dx = A_n f( - 1) + B_n f(1) + C\sum\limits_{i = 1}^n {f(x_{n,i} )} }$$ for polynomials of degree ≤n+2. Some numerical results are given when λ=1/2.     

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.     

Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.     

A transformation of series

The transformation (*) $$\sum\limits_{\nu = 0}^\infty {t_\nu z^\nu \to } \sum\limits_{\nu = 0}^\infty {\left\{ {\sum\limits_{\tau = 0}^{h - 1} {z^\tau } \Delta ^\nu t_{h\nu + \tau } + \frac{{z^h }}{{1 - z}}\Delta ^\nu t_{h(\nu + 1)} } \right\}} \left( {\frac{{z^{h + 1} }}{{1 - z}}} \right)^\nu$$ whereh≥0 is an integer and Δ operates upon the coefficients {t _v } of the series being transformed, is derived. Whenh=0, the above transformation is the generalised Euler transformation, of which (*) is itself a generalisation. Based upon the assumption that \(t_\nu = \int\limits_0^1 {\varrho ^\nu d\sigma (\varrho ) } (\nu = 0, 1,...)\) , where σ(?) is bounded and non-decreasing for 0≤?≤1 and subject to further restrictions, a convergence theory of (*) is given. Furthermore, the question as to when (*) functions as a convergence acceleration transformation is investigated. Also the optimal valne ofh to be taken is derived. A simple algorithm for constructing the partial sums of (*) is devised. Numerical illustrations relating to the case in whicht _v =(v+1) ^?1 (v=0,1,...) are given.     

Branching Time Logics \mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha } with Operations Until and Since Based on Bundles of Integer Numbers, Logical Consecutions, Deciding Algorithms

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤α≤ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem.     

Sul grado di precisione di formule di quadratura del tipo di tchebycheff

In this paper we study quadrature formulas of the types (1) $$\int\limits_{ - 1}^1 {(1 - x^2 )^{\lambda - 1/2} f(x)dx = C_n^{ (\lambda )} \sum\limits_{i = 1}^n f (x_{n,i} ) + R_n \left[ f \right]} ,$$ (2) $$\int\limits_{ - 1}^1 {(1 - x^2 )^{\lambda - 1/2} f(x)dx = A_n^{ (\lambda )} \left[ {f\left( { - 1} \right) + f\left( 1 \right)} \right] + K_n^{ (\lambda )} \sum\limits_{i = 1}^n f (\bar x_{n,i} ) + \bar R_n \left[ f \right]} ,$$ with 0<λ<1, and we obtain inequalities for the degreeN of their polynomial exactness. By using such inequalities, the non-existence of (1), with λ=1/2,N=n+1 ifn is even andN=n ifn is odd, is directly proved forn=8 andn≥10. For the same value λ=1/2 andN=n+3 ifn is evenN=n+2 ifn is odd, the formula (2) does not exist forn≥12. Some intermediary results regarding the first zero and the corresponding Christoffel number of ultraspherical polynomialP _n ^(λ) (x) are also obtained.     

Numerical solutions of AXB = C for mirrorsymmetric matrix X under a specified submatrix constraint

Mirrorsymmetric matrices, which are the iteraction matrices of mirrorsymmetric structures, have important application in studying odd/even-mode decomposition of symmetric multiconductor transmission lines (MTL). In this paper we present an efficient algorithm for minimizing ${\|AXB-C\|}$ where ${\|\cdot\|}$ is the Frobenius norm, ${A\in \mathbb{R}^{m\times n}}$ , ${B\in \mathbb{R}^{n\times s}}$ , ${C\in \mathbb{R}^{m\times s}}$ and ${X\in \mathbb{R}^{n\times n}}$ is mirrorsymmetric with a specified central submatrix [x _ij ] _{r≤i, j≤n-r} . Our algorithm produces a suitable X such that AXB = C in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.