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.     

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.     

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.     

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.     

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

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

A parametric algorithm for semigroup computation on mesh with buses

In this paper, we present a new parametric parallel algorithm for semigroup computation on mesh with reconfigurable buses (MRB). Givenn operands, our parallel algorithm can be performed in $O(2^{(2c^2 + 3c)/(4c + 1)} n^{1/(8c + 2)} )$ , time on a $2^{(c^2 - c)/(8c + 2)} n^{(5c + 1)/(8c + 2)} \times 2^{(c - c^2 )/(8c + 2)} n^{(3c + 1)/(8c + 2)} $ MRB ofn processors, where $0 \leqslant c \leqslant O(\sqrt {\log _2 n} )$ . Specifically, whenc=0, it takes $O(\sqrt n )$ time on the $\sqrt n \times \sqrt n $ MRB and is equal to the result on the mesh-connected computers; whenc=1, it takesO(n ^1/10) time on then ^3/5×n ^2/5 MRB and is equal to the previous result on the mesh-connected computers with segmented multiple buses; whenc=2, it takesO(n ^1/18) time on the 2^1/9 n ^11/18×2^(?1/9) n ^7/18 MRB; when $O(\sqrt {\log _2 n} )$ , it takesO(log₂ n) time and is equal to the previous result on the MRB. Consequently, our results can be viewed as a unification of some best known results on different parallel computational models.     

On reducing factorization to the discrete logarithm problem modulo a composite

The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a ^x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n.     

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.     

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

On the variance of gaussian quadrature formulae in the ultraspherical case

For ultraspherical weight functions ω_λ(x)=(1–x²)^λ–1/2, we prove asymptotic bounds and inequalities for the variance Var(Q _n ^G ) of the respective Gaussian quadrature formulae Q _n ^G . A consequence for a large class of more general weight functions ω and the respective Gaussian formulae is the following asymptotic result, $$\mathop {lim}\limits_{n \to \infty } n \cdot Var\left( {Q_n^G } \right) = \pi \int_{ - 1}^1 {\omega ^2 \left( x \right)\sqrt {1 - x^2 } dx.} $$      

Exact controllability of a Rayleigh beam with a single boundary control

We prove exact boundary controllability for the Rayleigh beam equation ${\varphi_{tt} -\alpha\varphi_{ttxx} + A\varphi_{xxxx} = 0, 0 < x < l, t > 0}$ with a single boundary control active at one end of the beam. We consider all combinations of clamped and hinged boundary conditions with the control applied to either the moment ${\varphi_{xx}(l, t)}$ or the rotation angle ${\varphi_{x}(l, t)}$ at an end of the beam. In each case, exact controllability is obtained on the space of optimal regularity for L ²(0, T) controls for ${T > 2l\sqrt{\frac{\alpha}{A}}}$ . In certain cases, e.g., the clamped case, the optimal regularity space involves a quotient in the velocity component. In other cases, where the regularity for the observed problem is below the energy level, a quotient space may arise in solutions of the observed problem.     

Quantum random walk polynomial and quantum random walk measure

In the paper, we introduce a quantum random walk polynomial (QRWP) that can be defined as a polynomial $\{P_{n}(x)\}$ , which is orthogonal with respect to a quantum random walk measure (QRWM) on $[-1, 1]$ , such that the parameters $\alpha _{n},\omega _{n}$ are in the recurrence relations $$\begin{aligned} P_{n+1}(x)= (x - \alpha _{n})P_{n}(x) - \omega _{n}P_{n-1}(x) \end{aligned}$$ and satisfy $\alpha _{n}\in \mathfrak {R},\omega _{n}> 0$ . We firstly obtain some results of QRWP and QRWM, in which case the correspondence between measures and orthogonal polynomial sequences is one-to-one. It shows that any measure with respect to which a quantum random walk polynomial sequence is orthogonal is a quantum random walk measure. We next collect some properties of QRWM; moreover, we extend Karlin and McGregor’s representation formula for the transition probabilities of a quantum random walk (QRW) in the interacting Fock space, which is a parallel result with the CGMV method. Using these findings, we finally obtain some applications for QRWM, which are of interest in the study of quantum random walk, highlighting the role played by QRWP and QRWM.     

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} $$

     

Pseudorandom generators for combinatorial checkerboards

We define a combinatorial checkerboard to be a function f : {1, . . . , m} ^d → {1,?1} of the form ${f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)}$ for some functions f _i : {1, . . . , m} → {1,?1}. This is a variant of combinatorial rectangles, which can be defined in the same way but using {0, 1} instead of {1,?1}. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case m = 2. We construct a pseudorandom generator that ${\epsilon}$ -fools all combinatorial checkerboards with seed length ${O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2} \frac{1}{\epsilon}\bigr)}$ . Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length ${O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)}$ . Our seed length is better except when ${\frac{1}{\epsilon}\geq d^{\omega(\log d)}}$ .     

On the Number of t-Ary Trees with a Given Path Length

We show that the number of t-ary trees with path length equal to p is $\exp({{(\alpha {p}/{\log p})}(1+o(1))}),$ where $\alpha=h(t^{-1})t\log t$ and $h(x)={-}x\log x {-}(1{-}x)\log (1{-}x).$ Besides its intrinsic combinatorial interest, the question recently arose in the context of information theory, where the number of t-ary trees with path length p estimates the number of universal types, or, equivalently, the number of different possible Lempel-Ziv '78 dictionaries for sequences of length p over an alphabet of size t.     

D-Separation and computation of probability distributions in Bayesian networks

Consider a family ${(X_i)_{i \in I}}$ of random variables endowed with the structure of a Bayesian network, and a subset S of I. This paper examines the problem of computing the probability distribution of the subfamily ${(X_{a})_{a \in S}}$ (respectively the probability distribution of ${ (X_{b})_{b \in {\bar{S}}}}$ , where ${{\bar{S}} = I - S}$ , conditional on ${(X_{a})_{a \in S}}$ ). This paper presents some theoretical results that makes it possible to compute joint and conditional probabilities over a subset of variables by computing over separate components. In other words, it is demonstrated that it is possible to decompose this task into several parallel computations, each related to a subset of S (respectively of ${{\bar{S}}}$ ); these partial results are then put together as a final product. In computing the probability distribution over ${(X_a)_{a \in S}}$ , this procedure results in the production of a structure of level two Bayesian network structure for S.     

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