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.

     

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.     

The method of interlineation of vector functions \vec{w} (x, y, z, t) on a system of vertical straight lines and its application in crosshole seismic tomography

The authors propose a method to construct interlineation operators for vector functions $ \vec{w} $ (x, y, z, t) on a system of arbitrarily located vertical straight lines. The method allows calculating the vector $ \vec{w} $ at each point (x, y, z) between straight lines Γ _k for any instant of time t ≥ 0. They are proposed to be used to construct a crosshole accelerometer to model Earth’s crust on the basis of seismic sounding data $ {{\vec{w}}_k}\left( {z,t} \right),\,k=\overline{1,M} $ , about the vector of acceleration $ \vec{w} $ (x, y, z, t) received by accelerometers at each chink Γ _k .     

Compact Numerical Quadrature Formulas for Hypersingular Integrals and Integral Equations

In the first part of this work, we derive compact numerical quadrature formulas for finite-range integrals $I[f]=\int^{b}_{a}f(x)\,dx$ , where f(x)=g(x)|x?t| ^?? , ?? being real. Depending on the value of ??, these integrals are defined either in the regular sense or in the sense of Hadamard finite part. Assuming that g??C ^??[a,b], or g??C ^??(a,b) but can have arbitrary algebraic singularities at x=a and/or x=b, and letting h=(b?a)/n, n an integer, we derive asymptotic expansions for ${T}^{*}_{n}[f]=h\sum_{1\leq j\leq n-1,\ x_{j}\neq t}f(x_{j})$ , where x _j =a+jh and t??{x ₁,??,x _n?1}. These asymptotic expansions are based on some recent generalizations of the Euler?CMaclaurin expansion due to the author (A.?Sidi, Euler?CMaclaurin expansions for integrals with arbitrary algebraic endpoint singularities, in Math. Comput., 2012), and are used to construct our quadrature formulas, whose accuracies are then increased at will by applying to them the Richardson extrapolation process. We pay particular attention to the case in which ??=?2 and f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ , which arises in the context of periodic hypersingular integral equations. For this case, we propose the remarkably simple and compact quadrature formula $\widehat{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)-\pi^{2} g(t)h^{-1}$ , and show that $\widehat{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, and that it is exact for a class of singular integrals involving trigonometric polynomials of degree at most n. We show how $\widehat{Q}_{n}[f]$ can be used for solving hypersingular integral equations in an efficient manner. In the second part of this work, we derive the Euler?CMaclaurin expansion for integrals $I[f]=\int^{b}_{a} f(x)dx$ , where f(x)=g(x)(x?t) ^?? , with g(x) as before and ??=?1,?3,?5,??, from which suitable quadrature formulas can be obtained. We revisit the case of ??=?1, for which the known quadrature formula $\widetilde{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)$ satisfies $\widetilde{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, when f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ . We show that this formula too is exact for a class of singular integrals involving trigonometric polynomials of degree at most n?1. We provide numerical examples involving periodic integrands that confirm the theoretical results.     

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

Linear differential and difference systems: EGδ- and EGσ- eliminations

Systems of linear ordinary differential and difference equations of the form $A_r (x)\xi ^r y(x) + \ldots + A_1 (x)\xi y(x) + A_0 (x)y(x) = 0,\xi \in \left\{ {\frac{d} {{dx}},E} \right\}$ , where E is the shift operator, Ey(x) = y(x + 1), are considered. The coefficients A _i (x), i = 0, ..., r, are square matrices of order m, and their entries are polynomials in x over a number field K, with A _r (x) and A ₀(x) being nonzero matrices. The equations are assumed to be independent over K[x, ξ]. For any system S of this form, algorithms EG_δ (in the differential case) and EG_σ (in the difference case) construct, in particular, the l-embracing system $\bar S$ of the same form. The determinant of the leading matrix $\bar A_r (x)$ of this system is a nonzero polynomial, and the set of solutions of system $\bar S$ contains all solutions of system S. (Algorithm EG_δ provides also a number of additional possibilities.) Examples of problems that can be solved with the help of EG_δ and EG_σ are given. The package EG implementing the proposed algorithms in Maple is described.     

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

L 2-Error bounds for approximate solutions of elliptic partial differential equations with Dirichlet-boundary conditions

New a posteriori (computable) upper bounds for theL ₂-norms, both ofD(u?v) and ofu?v are proposed, whereu is the exact solution of the boundary value problem $$Au: = - D(pDu) + qu = f, x \in G and u = 0,x \in \partial G$$ andv any approximation of it (D is here the vector of partial derivatives with respect to the components ofx). It is shown that the new error bounds are better than the classical one, which is proportional to ‖Av?f‖, in many cases. This happens, e. g., ifq has some zero point inG, as in the case of a Poisson equation.     

Modeling of subjective judgments made by a researcher-modeler about the model of the research object

Methods are considered for the mathematic modeling of incomplete and unreliable knowledge about the model M(x) of the research object expressed in the form of subjective judgments made by the researcher-modeler (r-m) about the possible values of the unknown parameter x ∈ X defining the model. The mathematical model of subjective judgments is defined as the space (X, P(X), $Pl^{\tilde x} $ , $Bel^{\tilde x} $ ), in which the indeterminate element (i.el.) $\tilde x$ characterizes (as an undefined propositional variable) the subjective judgments made by the r-m about the validity of each value x ∈ X by the values of measures such as the plausibility $Pl^{\tilde x} $ of the equality $\tilde x$ = x, and belief $Bel^{\tilde x} $ in the inequality $\tilde x$ ≠ x. If there are observational data on the subject, available to the r-m he can use them to construct an empirical estimate of the i.el. $\tilde x$ and an empirical model (X, P(X), $Pl^{\tilde x} $ , $Bel^{\tilde x} $ ) of the subjective judgments about possible values of x ∈ X.     

Error bound for product quadrature rules inL 1-weighted norm

The authors study the error of the product quadrature rules to compute the integral $\int_{ - 1}^1 {f\left( x \right) u\left( x \right)dx} $ . Estimates inL ₁-weighted norm are established whenu is a weight with algebraic and/or logarithmic singularities and the quadrature points are classical Jacobi zeros. Upper bounds for the generalized functions of second kind 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.     

The Laplace method for Gaussian measures and integrals in Banach spaces

We prove results on tight asymptotics of probabilities and integrals of the form $P_A (uD)andJ_u (D) = \int\limits_D {f(x)\exp \{ - u^2 F(x)\} dP_A (ux)} $ , where P _A is a Gaussian measure in an infinite-dimensional Banach space B, D = {x ∈ B: Q(x) ≥ 0} is a Borel set in B, Q and F are continuous functions which are smooth in neighborhoods of minimum points of the rate function, f is a continuous real-valued function, and u→∞ is a large parameter.     

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

Derandomized Parallel Repetition Theorems for Free Games

Raz’s parallel repetition theorem (SIAM J Comput 27(3):763–803, 1998) together with improvements of Holenstein (STOC, pp 411–419, 2007) shows that for any two-prover one-round game with value at most ${1- \epsilon}$ 1 - ? (for ${\epsilon \leq 1/2}$ ? ≤ 1 / 2 ), the value of the game repeated n times in parallel on independent inputs is at most ${(1- \epsilon)^{\Omega(\frac{\epsilon^2 n}{\ell})}}$ ( 1 - ? ) Ω ( ? 2 n ? ) , where ? is the answer length of the game. For free games (which are games in which the inputs to the two players are uniform and independent), the constant 2 can be replaced with 1 by a result of Barak et al. (APPROX-RANDOM, pp 352–365, 2009). Consequently, ${n=O(\frac{t \ell}{\epsilon})}$ n = O ( t ? ? ) repetitions suffice to reduce the value of a free game from ${1- \epsilon}$ 1 - ? to ${(1- \epsilon)^t}$ ( 1 - ? ) t , and denoting the input length of the game by m, it follows that ${nm=O(\frac{t \ell m}{\epsilon})}$ n m = O ( t ? m ? ) random bits can be used to prepare n independent inputs for the parallel repetition game. In this paper, we prove a derandomized version of the parallel repetition theorem for free games and show that O(t(m + ?)) random bits can be used to generate correlated inputs, such that the value of the parallel repetition game on these inputs has the same behavior. That is, it is possible to reduce the value from ${1- \epsilon}$ 1 - ? to ${(1- \epsilon)^t}$ ( 1 - ? ) t while only multiplying the randomness complexity by O(t) when m = O(?). Our technique uses strong extractors to “derandomize” a lemma of Raz and can be also used to derandomize a parallel repetition theorem of Parnafes et al. (STOC, pp 363–372, 1997) for communication games in the special case that the game is free.     

Non-classicalH 1 projection and Galerkin methods for non-linear parabolic integro-differential equations

In this paper the Galerkin method is analyzed for the following nonlinear integro-differential equation of parabolic type: $$c(u)u_t = \nabla \cdot \{ a(u)\nabla u + \int_0^t {b(x, t, r, u(x, r))} \nabla u(x, r) dr\} + f (u)$$ Optimal L ² error estimates for Crank-Nicolson and extrapolated Crank-Nicolson approximations are derived by using a non-classicalH ¹ projection associated with the above equation. Both schemes result in procedures which are second order correct in time, but the latter requires the solution of a linear algebraic system only once per time step.     

Approximating Node-Connectivity Augmentation Problems

We consider the (undirected) Node Connectivity Augmentation (NCA) problem: given a graph J=(V,E _J ) and connectivity requirements $\{r(u,v): u,v \in V\}$ , find a minimum size set I of new edges (any edge is allowed) such that the graph J∪I contains r(u,v) internally-disjoint uv-paths, for all u,v∈V. In Rooted NCA there is s∈V such that r(u,v)>0 implies u=s or v=s. For large values of k=max? _u,v∈V r(u,v), NCA is at least as hard to approximate as Label-Cover and thus it is unlikely to admit an approximation ratio polylogarithmic in k. Rooted NCA is at least as hard to approximate as Hitting-Set. The previously best approximation ratios for the problem were O(kln?n) for NCA and O(ln?n) for Rooted NCA. In this paper we give an approximation algorithm with ratios O(kln?² k) for NCA and O(ln?² k) for Rooted NCA. This is the first approximation algorithm with ratio independent of?n, and thus is a constant for any fixed k. Our algorithm is based on the following new structural result which is of independent interest. If $\mathcal{D}$ is a set of node pairs in a graph?J, then the maximum degree in the hypergraph formed by the inclusion minimal tight sets separating at least one pair in $\mathcal{D}$ is O(? ²), where ? is the maximum connectivity in J of a pair in $\mathcal{D}$ .     

Association Fields via Cuspless Sub-Riemannian Geodesics in SE(2)

To model association fields that underly perceptional organization (gestalt) in psychophysics we consider the problem P _curve of minimizing $\int _{0}^{\ell} \sqrt{\xi^{2} +\kappa^{2}(s)} {\rm d}s $ for a planar curve having fixed initial and final positions and directions. Here κ(s) is the curvature of the curve with free total length ?. This problem comes from a model of geometry of vision due to Petitot (in J. Physiol. Paris 97:265–309, 2003; Math. Inf. Sci. Humaines 145:5–101, 1999), and Citti & Sarti (in J. Math. Imaging Vis. 24(3):307–326, 2006). In previous work we proved that the range $\mathcal{R} \subset\mathrm{SE}(2)$ of the exponential map of the underlying geometric problem formulated on SE(2) consists of precisely those end-conditions (x _fin,y _fin,θ _fin) that can be connected by a globally minimizing geodesic starting at the origin (x _in,y _in,θ _in)=(0,0,0). From the applied imaging point of view it is relevant to analyze the sub-Riemannian geodesics and $\mathcal{R}$ in detail. In this article we

• show that $\mathcal{R}$ is contained in half space x≥0 and (0,y _fin)≠(0,0) is reached with angle π,
• show that the boundary $\partial\mathcal{R}$ consists of endpoints of minimizers either starting or ending in a cusp,
• analyze and plot the cones of reachable angles θ _fin per spatial endpoint (x _fin,y _fin),
• relate the endings of association fields to $\partial\mathcal {R}$ and compute the length towards a cusp,
• analyze the exponential map both with the common arc-length parametrization t in the sub-Riemannian manifold $(\mathrm{SE}(2),\mathrm{Ker}(-\sin\theta{\rm d}x +\cos\theta {\rm d}y), \mathcal{G}_{\xi}:=\xi^{2}(\cos\theta{\rm d}x+ \sin\theta {\rm d}y) \otimes(\cos\theta{\rm d}x+ \sin\theta{\rm d}y) + {\rm d}\theta \otimes{\rm d}\theta)$ and with spatial arc-length parametrization s in the plane $\mathbb{R}^{2}$ . Surprisingly, s-parametrization simplifies the exponential map, the curvature formulas, the cusp-surface, and the boundary value problem,
• present a novel efficient algorithm solving the boundary value problem,
• show that sub-Riemannian geodesics solve Petitot’s circle bundle model (cf. Petitot in J. Physiol. Paris 97:265–309, [2003]),
• show a clear similarity with association field lines and sub-Riemannian geodesics.

     

Exact asymptotics of large deviations of stationary Ornstein-Uhlenbeck processes for L p-functionals, p > 0

We prove a general result on the exact asymptotics of the probability $P\left\{ {\int\limits_0^1 {\left| {\eta _\gamma (t)} \right|^p dt > u^p } } \right\}$ as u → ∞, where p > 0, for a stationary Ornstein-Uhlenbeck process η _γ(t), i.e., a Gaussian Markov process with zero mean and with the covariance function Eη_γ(t)η_γ(s), t, s ∈ ?, γ > 0. We use the Laplace method for Gaussian measures in Banach spaces. Evaluation of constants is reduced to solving an extreme value problem for the rate function and studying the spectrum of a second-order differential operator of the Sturm-Liouville type. For p = 1 and p = 2, explicit formulas for the asymptotics are given.     

Symbolic solution of nonhomogeneous linear ordinary differential equations in terms of power series

For a nonhomogeneous linear ordinary differential equation Ly(x) = f(x) with polynomial coefficients and a holonomic right-hand side, a set of points x = a is found where a power series solution $y(x) = \sum\nolimits_{n = 0}^\infty {c_n (x - a)} ^n $ with hypergeometric coefficients exists (starting from some number, the ratio c _{n + 1}/c _n is a rational function of n).