Linear deviations of the classes\tilde W_p^\alpha and approximations in spaces of multipliers

We consider the problem of the asymptotically best linear method of approximation in the metric of L_s[?π, π] of the set \(\tilde W_p^\alpha (1)\) of periodic functions with a bounded in L_p[?π, π] fractional derivative, by functions from \(\tilde W_p^\beta (M)\) ,β >α, for sufficiently large M, and the problem about the best approximation in L_s[?π, π] of the operator of differentiation on \(\tilde W_p^\alpha (1)\) by continuous linear operators whose norm (as operators from L_r[?π, π] into L_q[?π, π])does not exceed M. These problems are reduced to the approximation of an individual element in the space of multipliers, and this allows us to obtain estimates that are exact in the sense of the order.     

Error estimates for the numerical solution of a time-periodic linear parabolic problem

In this paper we consider the numerical solution of a time-periodic linear parabolic problem. We derive optimal order error estimates inL ₂() for approximate solutions obtained by discretizing in space by a Galerkin finite-element method and in time by single-step finite difference methods, using known estimates for the associated initial value problem. We generalize this approach and obtain error estimates for more general discretization methods in the norm of a Banach spaceB L ₂(), e.g.,B=H ₀ ¹ () orL (). Finally, we consider some computational aspects and give a numerical example.     

The cycle structure of two rows in a random Latin square

Let L be chosen uniformly at random from among the latin squares of order n ≥ 4 and let r,s be arbitrary distinct rows of L. We study the distribution of σ_r,s, the permutation of the symbols of L which maps r to s. We show that for any constant c > 0, the following events hold with probability 1 ‐ o(1) as n → ∞: (i) σ_r,s has more than (log n)^1?c cycles, (ii) σ_r,s has fewer than 9 cycles, (iii) L has fewer than n^5/2 intercalates (latin subsquares of order 2). We also show that the probability that σ_r,s is an even permutation lies in an interval and the probability that it has a single cycle lies in [2n^‐2,2n^‐2/3]. Indeed, we show that almost all derangements have similar probability (within a factor of n^3/2) of occurring as σ_r,s as they do if chosen uniformly at random from among all derangements of {1,2,…,n}. We conjecture that σ_r,s shares the asymptotic distribution of a random derangement. Finally, we give computational data on the cycle structure of latin squares of orders n ≤ 11. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Estimates for Approximation Characteristics of the Besov Classes B r p,θ of Periodic Functions of Many Variables in the Space Lq. I

We obtain order estimates for the approximation of the classes B _r ^p, of periodic functions of many variables in the space L _q by using operators of orthogonal projection and linear operators satisfying certain conditions.     

Inequalities for polynomial splines

We establish exact estimates for the variation on a period of the derivative s ^(r)(t) of a periodic polynomial spline s(t) of degree r and defect 1 with respect to a fixed partition of [0, 2π) under the condition that , where X=C or L ₁     

Nonlinear trigonometric approximations of multivariate function classes

Order-sharp estimates are established for the best N-term approximations of functions from Nikol’skii–Besov type classes B_pq^sm(T^k) with respect to the multiple trigonometric system T^(k) in the metric of L_r(T^k) for a number of relations between the parameters s, p, q, r, and m (s = (s₁,..., s_n) ∈ R₊ⁿ, 1 ≤ p, q, r ≤ ∞, m = (m₁,..., m_n) ∈ Nⁿ, k = m₁ +... + m_n). Constructive methods of nonlinear trigonometric approximation—variants of the so-called greedy algorithms—are used in the proofs of upper estimates.     

Estimations de l'erreur d'approximation par splines d'interpolation et d'ajustement d'ordre (m,s)

Résumé On montre la convergence des splines d'ajustement d'ordre (m, s) et on établit des estimations de l'erreur d'approximation par splines d'interpolation et d'ajustement d'ordre (m, s) pour des fonctions appartenant à l'espace de SobolevH ^m+s (). Ces résultats prolongent ceux de J. Duchon.

---

Approximation error estimates for interpolating and smoothing (m, s)-splines

Summary For functions belonging to the sobolev spaceH ^m+s (), convergence of smoothing (m, s)-splines is proved and approximation error estimates for interpolating and smoothing (m, s)-splines are established. This is a contribution to the (m, s)-spline theory of J. Duchon.

     

The Heat Equaton with General Periodic Boundary Conditions

In this paper we address the well posedness of the linear heat equation under general periodic boundary conditions in several settings depending on the properties of the initial data. We develop an L ^q theory not based on separation of variables and use techniques based on uniform spaces. We also allow less directions of periodicity than the dimension of the problem. We obtain smoothing estimates on the solutions. Also, based on symmetry arguments, we handle Dirichlet or Neumann boundary conditions in some faces of the unit cell.     

On a Jackson-Type Inequality in the Approximation of a Function by Linear Summation Methods in the Space L 2

We prove a statement on exact inequalities between the deviations of functions from their linear methods (in the metric of L ₂) with multipliers defined by a continuous function and majorants determined as the scalar product of the squared modulus of continuity (of order r) in L ₂ for the lth derivative of the function and a certain weight function . We obtain several corollaries of the general theorem.     

Residual Smoothing Techniques: Do They Improve the Limiting Accuracy of Iterative Solvers?

Many iterative methods for solving linear systems, in particular the biconjugate gradient (BiCG) method and its squared version CGS (or BiCGS), produce often residuals whose norms decrease far from monotonously, but fluctuate rather strongly. Large intermediate residuals are known to reduce the ultimately attainable accuracy of the method, unless special measures are taken to counteract this effect. One measure that has been suggested is residual smoothing: by application of simple recurrences, the iterates x _n and the corresponding residuals r _n : b – Ax _n are replaced by smoothed iterates y _n and corresponding residuals s _n : b– Ay _n. We address the question whether the smoothed residuals can ultimately become markedly smaller than the primary ones. To investigate this, we present a roundoff error analysis of the smoothing algorithms. It shows that the ultimately attainable accuracy of the smoothed iterates, measured in the norm of the corresponding residuals, is, in general, not higher than that of the primary iterates. Nevertheless, smoothing can be used to produce certain residuals, most notably those of the minimum residual method, with higher attainable accuracy than by other frequently used algorithms.     

Regularity of the Schrödinger equation for the harmonic oscillator

We consider the Schrödinger equation for the harmonic oscillator i ? _t u=Hu, where H=?Δ+|x|², with initial data in the Hermite–Sobolev space H ^?s/2 L ²(? ⁿ ). We obtain smoothing and maximal estimates and apply these to perturbations of the equation and almost everywhere convergence problems.     

Accurate estimates of deviations of spline approximations to classes of differentiable functions

We derive the approximation on [0, 1] of functionsf(x) by interpolating spline-functions s_r(f; x) of degree 2r+1 and defect r+1 (r=1, 2,...). Exact estimates for ¦f(x)–s_r(f; x) ¦ and f(x)–s_r(f; x)|_c on the class W^mH for m=1, r=1, 2, ..., and m=2, 3, r=1 for the case of convex (t),are derived.Translated from Matematicheskie Zametki, Vol. 9, No. 5, pp. 483–494, May, 1971.     

On the optimal approximation of bounded linear functionals in Hilbert spaces of analytic functions

Optimal numerical approximation of bounded linear functionals by weighted sums in Hilbert spaces of functions analytic in a circleK _r , in a circular annulusK _r1,r2 and in an ellipseE _r is investigated by Davis' method on the common algebraic background for diagonalising the normal equation matrix. The weights and error functional norms for optimal rules with nodes located angle-equidistant on the concentric circleK _s or on the confocal ellipseE _s and in the interval [–1,1] for an arbitrary bounded linear functional are given explicitly. They are expressed in terms of a complete orthonormal system in the Hilbert space.     

Fully discrete approximations of parabolic boundary-value problems with nonsmooth boundary data

We study a numerical scheme for the approximation of parabolic boundary-value problems with nonsmooth boundary data. This fully discrete scheme requires no boundary constraints on the approximating elements. Our principal result is the derivation of optimal convergence estimates in L_p[0,T; L₂()] norms for boundary data in L_p[0, T; L₂()], 1p . For the same algorithms, we also show that the convergence remains optimal even in higher norms. The techniques employed are based on the theory of analytic semigroups combined with singular integrals.This paper was written in 1990, when the author was in the Department of Mathematical Sciences, University of Cincinnati. A preliminary version of this research was presented at the SIAM Annual Meeting in July 1989.     

On Smoothness Properties and Approximability of Optimal Control Functions

The theory of discretization methods to control problems and their convergence under strong stable optimality conditions in recent years has been thoroughly investigated by several authors. A particularly interesting question is to ask for a natural smoothness category for the optimal controls as functions of time.In several papers, Hager and Dontchev considered Riemann integrable controls. This smoothness class is characterized by global, averaged criteria. In contrast, we consider strictly local properties of the solution function. As a first step, we introduce tools for the analysis of L elements at a point. Using afterwards Robinson's strong regularity theory, under appropriate first and second order optimality conditions we obtain structural as well as certain pseudo-Lipschitz properties with respect to the time variable for the control.Consequences for the behavior of discrete solution approximations are discussed in the concluding section with respect to L as well as L ₂ topologies.     

Vector subdivision schemes in (Lp(?s))r(1?p?∞) spaces

The purpose of this paper is to investigate the refinement equations of the form

The block grade of a block Krylov space

The aim of the paper is to compile and compare basic theoretical facts on Krylov subspaces and block Krylov subspaces. Many Krylov (sub)space methods for solving a linear system Ax=b have the property that in exact computer arithmetic the true solution is found after ν iterations, where ν is the dimension of the largest Krylov subspace generated by A from r₀, the residual of the initial approximation x₀. This dimension is called the grade of r₀ with respect to A. Though the structure of block Krylov subspaces is more complicated than that of ordinary Krylov subspaces, we introduce here a block grade for which an analogous statement holds when block Krylov space methods are applied to linear systems with multiple, say s, right-hand sides. In this case, the s initial residuals are bundled into a matrix R₀ with s columns. The possibility of linear dependence among columns of the block Krylov matrix , which in practical algorithms calls for the deletion (or, deflation) of some columns, requires extra care. Relations between grade and block grade are also established, as well as relations to the corresponding notions of a minimal polynomial and its companion matrix.     

Free-knot Splines Approximation of s-monotone Functions

Let I be a finite interval and r,sN. Given a set M, of functions defined on I, denote by ₊ ^s M the subset of all functions yM such that the s-difference ^s y() is nonnegative on I, >0. Further, denote by ₊ ^s W _p ^r , the class of functions x on I with the seminorm x ^(r)L _p 1, such that ^s x0, >0. Let M _n (h _k ):={ _i=1 ⁿ c _i h _k (w _i t– _i )c _i ,w _i , _i R, be a single hidden layer perceptron univariate model with n units in the hidden layer, and activation functions h _k (t)=t ₊ ^k , tR, kN ₀. We give two-sided estimates both of the best unconstrained approximation E( ₊ ^s W _p ^r ,M _n (h _k ))L _q , k=r–1,r, s=0,1,...,r+1, and of the best s-monotonicity preserving approximation E( ₊ ^s W _p ^r , ₊ ^s M _n (h _k ))L _q , k=r–1,r, s=0,1,...,r+1. The most significant results are contained in theorem 2.2.     

An infeasible-interior-point algorithm using projections onto a convex set

We present a new class of primal-dual infeasible-interior-point methods for solving linear programs. Unlike other infeasible-interior-point algorithms, the iterates generated by our methods lie in general position in the positive orthant of ² and are not restricted to some linear manifold. Our methods comprise the following features: At each step, a projection is used to recenter the variables to the domainx _i s _i . The projections are separable into two-dimensional orthogonal projections on a convex set, and thus they are seasy to implement. The use of orthogonal projections allows that a full Newton step can be taken at each iteration, even if the result violates the nonnegativity condition. We prove that a short step version of our method converges in polynomial time.Research performed while visiting the Institut für Angewandte Mathematik, University of Würzburg, D-87074 Würzburg, Germany, as a Research Fellow of the Alexander von Humboldt Foundation.