Perturbation analysis for the positive definite solution of the nonlinear matrix equation X-\sum_{i=1}^{m} A_{i}^{*}X^{-1}A_{i}=Q

Consider the perturbation analysis for positive definite solution of the nonlinear matrix equation $X-\sum_{i=1}^{m}A_{i}^{*}X^{-1}A_{i}=Q$ which arises in an optimal interpolation problem. Two perturbation bounds for the unique positive definite solution are obtained, and an explicit expression of the condition number for the unique positive definite solution is derived. The theoretical results are illustrated by several numerical examples.     

Approximation of solution operators of elliptic partial differential equations by {\mathcal{H}}- and {\mathcal{H}^2}-matrices

We investigate the problem of computing the inverses of stiffness matrices resulting from the finite element discretization of elliptic partial differential equations. Since the solution operators are non-local, the inverse matrices will in general be dense, therefore representing them by standard techniques will require prohibitively large amounts of storage. In the field of integral equations, a successful technique for handling dense matrices efficiently is to use a data-sparse representation like the popular multipole method. In this paper we prove that this approach can be generalized to cover inverse matrices corresponding to partial differential equations by switching to data-sparse ${\mathcal{H}}$ - and ${\mathcal{H}^2}$ -matrices. The key results are existence proofs for local low-rank approximations of the solution operator and its discrete counterpart, which give rise to error estimates for ${\mathcal{H}}$ - and ${\mathcal{H}^2}$ -matrix approximations of the entire matrices.     

Analysis of a continuous finite element method for H(\mathrm{curl},\mathrm{div})-elliptic interface problem

In this paper, we develop a continuous finite element method for the curlcurl-grad div vector second-order elliptic problem in a three-dimensional polyhedral domain occupied by discontinuous nonhomogeneous anisotropic materials. In spite of the fact that the curlcurl-grad div interface problem is closely related to the elliptic interface problem of vector Laplace operator type, the continuous finite element discretization of the standard variational problem of the former generally fails to give a correct solution even in the case of homogeneous media whenever the physical domain has reentrant corners and edges. To discretize the curlcurl-grad div interface problem by the continuous finite element method, we apply an element-local $L^2$ projector to the curl operator and a pseudo-local $L^2$ projector to the div operator, where the continuous Lagrange linear element enriched by suitable element and face bubbles may be employed. It is shown that the finite element problem retains the same coercivity property as the continuous problem. An error estimate $\mathcal{O }(h^r)$ in an energy norm is obtained between the analytical solution and the continuous finite element solution, where the analytical solution is in $\prod _{l=1}^L (H^r(\Omega _l))^3$ for some $r\in (1/2,1]$ due to the domain boundary reentrant corners and edges (e.g., nonconvex polyhedron) and due to the interfaces between the different material domains in $\Omega =\bigcup _{l=1}^L \Omega _l$ .     

Regularization and iterative methods for monotone inverse variational inequalities

We consider the monotone inverse variational inequality: find $x\in H$ such that $$\begin{aligned} f(x)\in \Omega , \quad \left\langle \tilde{f}-f(x),x\right\rangle \ge 0, \quad \forall \tilde{f}\in \Omega , \end{aligned}$$ where $\Omega $ is a nonempty closed convex subset of a real Hilbert space $H$ and $f:H\rightarrow H$ is a monotone mapping. A general regularization method for monotone inverse variational inequalities is shown, where the regularizer is a Lipschitz continuous and strongly monotone mapping. Moreover, we also introduce an iterative method as discretization of the regularization method. We prove that both regularized solution and an iterative method converge strongly to a solution of the inverse variational inequality.     

New upper bounds on the smallest size of a complete arc in a finite Desarguesian projective plane

In the projective planes PG(2, q), more than 1230 new small complete arcs are obtained for ${q \leq 13627}$ and ${q \in G}$ where G is a set of 38 values in the range 13687,..., 45893; also, ${2^{18} \in G}$ . This implies new upper bounds on the smallest size t ₂(2, q) of a complete arc in PG(2, q). From the new bounds it follows that $$t_{2}(2, q) < 4.5\sqrt{q} \, {\rm for} \, q \leq 2647$$ and q = 2659,2663,2683,2693,2753,2801. Also, $$t_{2}(2, q) < 4.8\sqrt{q} \, {\rm for} \, q \leq 5419$$ and q = 5441,5443,5449,5471,5477,5479,5483,5501,5521. Moreover, $$t_{2}(2, q) < 5\sqrt{q} \, {\rm for} \, q \leq 9497$$ and q = 9539,9587,9613,9623,9649,9689,9923,9973. Finally, $$t_{2}(2, q) <5 .15\sqrt{q} \, {\rm for} \, q \leq 13627$$ and q = 13687,13697,13711,14009. Using the new arcs it is shown that $$t_{2}(2, q) < \sqrt{q}\ln^{0.73}q {\rm for} 109 \leq q \leq 13627\, {\rm and}\, q \in G.$$ Also, as q grows, the positive difference ${\sqrt{q}\ln^{0.73} q-\overline{t}_{2}(2, q)}$ has a tendency to increase whereas the ratio ${\overline{t}_{2}(2, q)/(\sqrt{q}\ln^{0.73} q)}$ tends to decrease. Here ${\overline{t}_{2}(2, q)}$ is the smallest known size of a complete arc in PG(2,q). These properties allow us to conjecture that the estimate ${t_{2}(2,q) < \sqrt{q}\ln ^{0.73}q}$ holds for all ${q \geq 109.}$ The new upper bounds are obtained by finding new small complete arcs in PG(2,q) with the help of a computer search using randomized greedy algorithms. Finally, new forms of the upper bound on t ₂(2,q) are proposed.     

Bounding S(t) and S_1(t) on the Riemann hypothesis

Let $\pi S(t)$ denote the argument of the Riemann zeta-function, $\zeta (s)$ , at the point $s=\frac{1}{2}+it$ . Assuming the Riemann hypothesis, we present two proofs of the bound $$\begin{aligned} |S(t)| \le \left(\frac{1}{4} + o(1) \right)\frac{\log t}{\log \log t} \end{aligned}$$ for large $t$ . This improves a result of Goldston and Gonek by a factor of 2. The first method consists of bounding the auxiliary function $S_1(t) = \int _0^{t} S(u) \> \text{ d}u$ using extremal functions constructed by Carneiro, Littmann and Vaaler. We then relate the size of $S(t)$ to the size of the functions $S_1(t\pm h)-S_1(t)$ when $h\asymp 1/\log \log t$ . The alternative approach bounds $S(t)$ directly, relying on the solution of the Beurling–Selberg extremal problem for the odd function $f(x) = \arctan \left(\frac{1}{x}\right) - \frac{x}{1 + x^2}$ . This draws upon recent work by Carneiro and Littmann.     

First-order algorithm with {\mathcal{O}({\rm ln}(1{/}\epsilon))} convergence for {\epsilon}-equilibrium in two-person zero-sum games

We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x \in Q_1}\max_{y \in Q_2} {x}^{\rm T}{Ay} = \max_{y \in Q_2} \min_{x \in Q_1} {x}^{\rm T}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an ${\epsilon}$ -equilibrium to this min-max problem in ${\mathcal {O}\left(\frac{\|A\|}{\delta(A)} \, {\rm ln}(1{/}\epsilon)\right)}$ first-order iterations, where δ(A) is a certain condition measure of the matrix A. This improves upon the previous first-order methods which required ${\mathcal {O}(1{/}\epsilon)}$ iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm’s dependence on ${\epsilon}$ . Unlike interior-point methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior first-order methods. Our scheme supplements Nesterov’s method with an outer loop that lowers the target ${\epsilon}$ between iterations (this target affects the amount of smoothing in the inner loop). Computational experiments both in matrix games and sequential games show that a significant speed improvement is obtained in practice as well, and the relative speed improvement increases with the desired accuracy (as suggested by the complexity bounds).     

Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization

This paper is concerned with a class of ellipsoidal sets (ellipsoids and elliptic cylinders) in ${\mathbb{R}^m}$ which are determined by a freely chosen m × m positive semidefinite matrix. All ellipsoidal sets in this class are similar to each other through a parallel transformation and a scaling around their centers by a constant factor. Based on the basic idea of lifting, we first present a conceptual min-max problem to determine an ellipsoidal set with the smallest size in this class which encloses a given subset of ${\mathbb{R}^m}$ . Then we derive a numerically tractable enclosing ellipsoidal set of a given semialgebraic subset of ${\mathbb{R}^m}$ as a convex relaxation of the min-max problem in the lifting space. A main feature of the proposed method is that it is designed to incorporate into existing SDP relaxations with exploiting sparsity for various optimization problems to compute error bounds of their optimal solutions. We discuss how we adapt the method to a standard SDP relaxation for quadratic optimization problems and a sparse variant of Lasserre’s hierarchy SDP relaxation for polynomial optimization problems. Some numerical results on the sensor network localization problem and polynomial optimization problems are also presented.     

Perturbation analysis for Moore-Penrose inverse of closed operators on Hilbert spaces

In this paper, we investigate the perturbation for the Moore-Penrose inverse of closed operators on Hilbert spaces. By virtue of a new inner product defined on H, we give the expression of the Moore-Penrose inverse $\bar{T}^{\dag}$ and the upper bounds of $\|\bar{T}^{\dag}\|$ and $\|\bar{T}^{\dag}-T^{\dag}\|$ . These results obtained in this paper extend and improve many related results in this area.     

Lower and upper bounds of Dirichlet eigenvalues for totally characteristic degenerate elliptic operators

Let λkbe the k-th Dirichlet eigenvalue of totally characteristic degenerate elliptic operator-ΔB defined on a stretched cone B0 ■ [0,1) × X with boundary on {x1 = 0}. More precisely,ΔB=(x1αx1)2+ α2x2+ + α2xnis also called the cone Laplacian. In this paper,by using Mellin-Fourier transform,we prove thatλk Cnk2 n for any k 1,where Cn=(nn+2)(2π)2(|B0|Bn)-2n,which gives the lower bounds of the Dirchlet eigenvalues of-ΔB. On the other hand,by using the Rayleigh-Ritz inequality,we deduce the upper bounds ofλk,i.e.,λk+1 1 +4n k2/nλ1. Combining the lower and upper bounds of λk,we can easily obtain the lower bound for the first Dirichlet eigenvalue λ1 Cn(1 +4n)-12n2.     

Regularity of semi-stable solutions to fourth order nonlinear eigenvalue problems on general domains

We examine the fourth order problem $\Delta ^2 u = \lambda f(u) $ in $ \Omega $ with $ \Delta u = u =0 $ on $ {\partial \Omega }$ , where $ \lambda > 0$ is a parameter, $ \Omega $ is a bounded domain in $\mathbb{R }^N$ and where $f$ is one of the following nonlinearities: $ f(u)=e^u$ , $ f(u)=(1+u)^p $ or $ f(u)= \frac{1}{(1-u)^p}$ where $ p>1$ . We show the extremal solution is smooth, provided $$\begin{aligned} N < 2 + 4 \sqrt{2} + 4 \sqrt{ 2 - \sqrt{2}} \approx 10.718 \text{ when} f(u)=e^u, \end{aligned}$$ and $$\begin{aligned} N < \frac{4p}{p-1} + \frac{4(p+1)}{p-1} \left( \sqrt{ \frac{2p}{p+1}} + \sqrt{ \frac{2p}{p+1} - \sqrt{ \frac{2p}{p+1}}} - \frac{1}{2} \right) \end{aligned}$$ when $ f(u)=(u+1)^p$ . New results are also obtained in the case where $ f(u)=(1-u)^{-p}$ . These are substantial improvements to various results on critical dimensions obtained recently by various authors. To do that, we derive a new stability inequality satisfied by minimal solutions of the above equation, which is more amenable to estimates as it allows a method of proof reminiscent of the second order case.     

An error estimate for the finite difference approximation to degenerate convection–diffusion equations

We consider semi-discrete first-order finite difference schemes for a nonlinear degenerate convection?Cdiffusion equations in one space dimension, and prove an L ¹ error estimate. Precisely, we show that the ${L^1_{\rm{loc}}}$ difference between the approximate solution and the unique entropy solution converges at a rate ${\mathcal{O}(\Delta x^{1/11})}$ , where ${\Delta x}$ is the spatial mesh size. If the diffusion is linear, we get the convergence rate ${\mathcal{O}(\Delta x^{1/2})}$ , the point being that the ${\mathcal{O}}$ is independent of the size of the diffusion.     

Error bounds for Gauss-type quadratures with Bernstein–Szegő weights

The paper is concerned with the derivation of error bounds for Gauss-type quadratures with Bernstein?Szeg? weights, $${\int\limits_{-1}^{1}}f(t)w(t)\, dt=G_{n}[f]+R_{n}(f),\quad G_{n}[f]=\sum\limits_{\nu=1}^{n}\lambda_{\nu} f(\tau_{\nu}) \quad(n\in\textbf{N}),$$ where f is an analytic function inside an elliptical contour \(\mathcal{E}_{\rho}\) with foci at \(\mp 1\) and sum of semi-axes \(\rho > 1\) , and w is a nonnegative and integrable weight function of Bernstein?Szeg? type. The derivation of effective bounds on \(|R_{n}(f)|\) is possible if good estimates of \(\max_{z\in\mathcal{E}_{\rho}}|K_{n}(z)|\) are available, especially if one knows the location of the extremal point \(\eta\in\mathcal{E}_{\rho}\) at which \(|K_{n}|\) attains its maximum. In such a case, instead of looking for upper bounds on \(\max_{z\in\mathcal{E}_{\rho}}|K_{n}(z)|\) , one can simply try to calculate \(|K_{n}(\eta,w)|\) . In the case under consideration, i.e. when $$w(t)= \frac{(1-t^{2})^{-1/2}}{\beta(\beta-2\alpha)\,t^{2} +2\delta(\beta-\alpha)\,t+\alpha^{2}+\delta^{2}},\quad t\in(-1,1),$$ for some \(\alpha,\beta,\delta\) , which satisfy \(0<\alpha<\beta,\ \beta\ne 2\alpha,\vert\delta\vert<\beta-\alpha\) , the location on the elliptical contours where the modulus of the kernel attains its maximum value is investigated. This leads to effective bounds on \(|R_{n}(f)|\) . The quality of the derived bounds is analyzed by a comparison with other error bounds proposed in the literature for the same class of integrands.     

A stabilized multi-level method for non-singular finite volume solutions of the stationary 3D Navier–Stokes equations

This paper proposes and analyzes a stabilized multi-level finite volume method (FVM) for solving the stationary 3D Navier?CStokes equations by using the lowest equal-order finite element pair without relying on any solution uniqueness condition. This multi-level stabilized FVM consists of solving the nonlinear problem on the coarsest mesh and then performing one Newton correction step on each subsequent mesh, thus only solving a large linear system. An optimal convergence rate for the finite volume approximations of nonsingular solutions is first obtained with the same order as that for the usual finite element solution by using a relationship between the stabilized FVM and a stabilized finite element method. Then the multi-level finite volume approximate solution is shown to have a convergence rate of the same order as that of the stabilized finite volume solution of the stationary Navier?CStokes equations on a fine mesh with an appropriate choice of the mesh size: ${ h_{j} ~ h_{j-1}^{2}, j = 1,\ldots, J}$ . Finally, numerical results presented validate our theoretical findings.     

Morrey-type regularity of solutions to parabolic problems with discontinuous data

We consider regular oblique derivative problem in cylinder Q _T ?=????× (0, T), ${\Omega\subset {\mathbb R}^n}$ for uniformly parabolic operator ${{{\mathfrak P}}=D_t- \sum_{i,j=1}^n a^{ij}(x)D_{ij}}$ with VMO principal coefficients. Its unique strong solvability is proved in Manuscr. Math. 203?C220 (2000), when ${{{\mathfrak P}}u\in L^p(Q_T)}$ , ${p\in(1,\infty)}$ . Our aim is to show that the solution belongs to the generalized Sobolev?CMorrey space ${W^{2,1}_{p,\omega}(Q_T)}$ , when ${{{\mathfrak P}}u\in L^{p,\omega} (Q_T)}$ , ${p\in (1, \infty)}$ , ${\omega(x,r):\,{\mathbb R}^{n+1}_+\to {\mathbb R}_+}$ . For this goal an a priori estimate is obtained relying on explicit representation formula for the solution. Analogous result holds also for the Cauchy?CDirichlet problem.     

Strong convergence of a splitting projection method for the sum of maximal monotone operators

In this paper, a projective-splitting method is proposed for finding a zero of the sum of $n$ maximal monotone operators over a real Hilbert space $\mathcal{H }$ . Without the condition that either $\mathcal{H }$ is finite dimensional or the sum of $n$ operators is maximal monotone, we prove that the sequence generated by the proposed method is strongly convergent to an extended solution for the problem, which is closest to the initial point. The main results presented in this paper generalize and improve some recent results in this topic.     

The Pólya–Chebotarev problem and inverse polynomial images

Consider the problem, usually called the Pólya–Chebotarev problem, of finding a continuum in the complex plane including some given points such that the logarithmic capacity of this continuum is minimal. We prove that each connected inverse image ${\mathcal {T}}_{n}^{-1} ([-1,1])$ of a polynomial  ${\mathcal {T}}_{n}$ is always the solution of a certain Pólya–Chebotarev problem. By solving a nonlinear system of equations for the zeros of ${\mathcal {T}}_{n}^{2}-1$ , we are able to construct polynomials ${\mathcal {T}}_{n}$ with a connected inverse image.     

The long time error analysis in the second order difference type method of an evolutionary integral equation with completely monotonic kernel

We study convergence of the numerical methods in which the second order difference type method is combined with order two convolution quadrature for approximating the integral term of the evolutionary integral equation $$ u^{\prime}(t)+\int_{0}^{t}\beta(t-s)\,A\,u\,(s)\;ds \, =\,0 ,~~~~ t>0,~~u(0)=u_{0}, $$ which arises in the theory of linear viscoelasticity. Here A is a positive self-adjoint densely defined linear operator in a real Hilbert space H and \(\beta (t)\) is completely monotonic and locally integrable, but not constant. We establish the convergence properties of the discretization in time in the \(l_{t}^{1}(0,\infty ;\,H)\) or \(l_{t}^{\infty }(0,\infty ;\,H)\) norm.     

Bounds for codes and designs in complex subspaces

We introduce the concepts of complex Grassmannian codes and designs. Let $\mathcal{G}_{m,n}$ denote the set of m-dimensional subspaces of ? ⁿ : then a code is a finite subset of $\mathcal{G}_{m,n}$ in which few distances occur, while a design is a finite subset of $\mathcal{G}_{m,n}$ that polynomially approximates the entire set. Using Delsarte’s linear programming techniques, we find upper bounds for the size of a code and lower bounds for the size of a design, and we show that association schemes can occur when the bounds are tight. These results are motivated by the bounds for real subspaces recently found by Bachoc, Bannai, Coulangeon and Nebe, and the bounds generalize those of Delsarte, Goethals and Seidel for codes and designs on the complex unit sphere.     

On the solutions of a singular elliptic equation concentrating on two orthogonal spheres

Let \({A=\{x\in \mathbb{R}^{2m}: 0 < a < |x| < b\}}\) be an annulus. We consider the following singularly perturbed elliptic problem on A $$\left\{\begin{array}{lll}-\varepsilon ^2{\Delta u} + |x|^{\eta}u =|x|^{\eta}u^p, \quad {\rm in} A,\\ u > 0, \quad \quad \quad \quad \quad \quad \quad {\rm in} A, \\ u=0, \quad \quad \quad \quad \quad \quad \quad {\rm on}\partial A,\end{array}\right. $$ where \({1 < p < \frac{m+3}{m-1}}\) . We shall prove the existence of a positive solution \({u_\epsilon }\) which concentrates on two different orthogonal spheres of dimension (m?1) as \({\varepsilon \to 0}\) . We achieve this by studying a reduced problem on an annular domain in \({\mathbb{R}^{m+1}}\) and analysing the profile of a two point concentrating solution in this domain.