Approximating Fixed Points of Weakly Contracting Mappings

We consider the problem of approximating fixed points of contractive functions whose contraction factor is close to 1. In a previous paper (1993, K. Sikorski et al., J. Complexity9, 181–200), we proved that for the absolute error criterion, the upper bound on the number of function evaluations to compute ε-approximations is O(n³(ln(1/ε)+ln(1/(1−q))+ln n)) in the worst case, where 0<q<1 is the contraction factor in the Euclidean norm and n is the dimension of the problem. This upper bound is achieved by the circumscribed ellipsoid (CE) algorithm combined with a dimensional deflation process. In this paper we present an inscribed ellipsoid (IE) algorithm that enjoys O(n(ln(1/ε)+ln(1/(1−q)))) bound. For q close to 1, the IE algorithm thus runs in many fewer iterations than the simple iteration method, that requires ⌈ln(1/ε)/ln(1/q)⌉ function evaluations. Our analysis also implies that: (1) The dimensional deflation procedure in the CE algorithm is not necessary and that the resulting “plain” CE algorithm enjoys O(n²(log(1/ε)+log(1/(1−q)))) upper bound on the number of function evaluations. (2) The IE algorithm solves the problem in the residual sense, i.e., computes x such that 6f(x)−x6⩽δ, with O(n ln(1/δ)) function evaluations for every q⩽1.     

Uniform approximation by some Hermite interpolating splines

In this paper some upper bound for the error ∥ s-f ∥_∞ is given, where f ε C¹[a,b], but s is a so-called Hermite spline interpolant (HSI) of degree 2q ?1 such that f(x_i) = s(x_i), f′(rmx_i) = s′(x_i), s^(j) (x_i) = 0 (i = 0, 1, …, n; j = 2, 3, …, q ?1; n > 0, q > 0) and the knots x_i are such that a = x₀ < x₁ < … < x_n = b. Necessary and sufficient conditions for the existence of convex HSI are given and upper error bound for approximation of the function fε C¹[a, b] by convex HSI is also given.     

Homogenization of a nonstationary model equation of electrodynamics

In L ₂(?₃;?₃), we consider a self-adjoint operator ? _ε , ε > 0, generated by the differential expression curl η(x/ε)^?1 curl??ν(x/ε) div. Here the matrix function η(x) with real entries and the real function ν(x) are periodic with respect to some lattice, are positive definite, and are bounded. We study the behavior of the operators cos(τ? _ε ^1/2 ) and ? _ε ^?1/2 sin(τ? _ε ^1/2 ) for τ ∈ ? and small ε. It is shown that these operators converge to cos(τ(?⁰)^1/2) and (?₀)^?1/2 sin(τ(?₀)^1/2), respectively, in the norm of the operators acting from the Sobolev space H ^s (with a suitable s) to ?₂. Here ?⁰ is an effective operator with constant coefficients. Error estimates are obtained and the sharpness of the result with respect to the type of operator norm is studied. The results are used for homogenizing the Cauchy problem for the model hyperbolic equation ? _τ ² v _ε = ?? _ε v _ε , div v _ε = 0, appearing in electrodynamics. We study the application to a nonstationary Maxwell system for the case in which the magnetic permeability is equal to 1 and the dielectric permittivity is given by the matrix η(x/ε).     

What Is the Complexity of Stieltjes Integration?

We study the complexity of approximating the Stieltjes integral ∫¹₀ f(x) dg(x) for functions f having r continuous derivatives and functions g whose sth derivative has bounded variation. Let r(n) denote the nth minimal error attainable by approximations using at most n evaluations of f and g, and let comp(ε) denote the ε-complexity (the minimal cost of computing an ε-approximation). We show that r(n)≍n^{−min{r, s+1}} and that comp(ε)≍ε^{−1/min{r, s+1}}. We also present an algorithm that computes an ε-approximation at nearly minimal cost.     

Continuous approximation of random function

Modifying the methods of Lee [J. Math. Anal. Appl.61 (1977), 1–6], we show that each μ-measurable mapping f on a normal space T into a separable linear metric space E is almost continuous, where μ is a Radon probability measure. It is shown that for every ε > 0 there exists a compact subset K_ε ? T with μ(K_ε) > 1 ? ε and an elementary function g(t) = ∑ⁿ_{i = 1}h_i(t) x_i such that μ(t?K_ε; f(t) ≠ g(t)) < ε, where x_i?E and h_i(t) are real bounded continuous functions with disjoint supports.     

On singular perturbations of superlinear elliptic systems

We study the existence, multiplicity and shape of positive solutions of the system −ε²Δu+V(x)u=K(x)g(v), −ε²Δv+V(x)v=H(x)f(u) in RN, as ε→0. The functions f and g are power-like nonlinearities with superlinear and subcritical growth at infinity, and V, H, K are positive and locally Hölder continuous.     

The Exponent of Discrepancy Is at Least 1.0669

LetP⊂[0, 1]^dbe ann-point set and letw: P→[0, ∞) be a weight function withw(P)=∑_z∈P w(z)=1. TheL₂-discrepancy of the weighted set (P, w) is defined as theL₂-average ofD(x)=vol(B_x)−w(P∩B_x) overx∈[0, 1]^d, where vol(B_x) is the volume of thed-dimensional intervalB_x=∏^d_k=1 [0, x_k). The exponent of discrepancyp* is defined as the infimum of numberspsuch that for all dimensionsd⩾1 and allε>0 there exists a weighted set of at mostKε^−ppoints in [0, 1]^dwithL₂-discrepancy at mostε, whereK=K(p) is a suitable number independent ofεandd. Wasilkowski and Woźniakowski proved thatp*⩽1.4779, by combining known bounds for the error of numerical integration and using their relation toL₂-discrepancy. In this note we observe that a careful treatment of a classical lower- bound proof of Roth yieldsp*⩾1.04882, and by a slight modification of the proof we getp*⩾1.0669. Determiningp* exactly seems to be quite a difficult problem.     

The distance trisector curve

Given points p and q in the plane, we are interested in separating them by two curves C₁ and C₂ such that every point of C₁ has equal distance to p and to C₂, and every point of C₂ has equal distance to C₁ and to q. We show by elementary geometric means that such C₁ and C₂ exist and are unique. Moreover, for p=(0,1) and q=(0,−1), C₁ is the graph of a function , C₂ is the graph of −f, and f is convex and analytic (i.e., given by a convergent power series at a neighborhood of every point). We conjecture that f is not expressible by elementary functions and, in particular, not algebraic. We provide an algorithm that, given x∈R and ε>0, computes an approximation to f(x) with error at most ε in time polynomial in . The separation of two points by two “trisector” curves considered here is a special (two-point) case of a new kind of Voronoi diagram, which we call the zone diagram and which we investigate in a companion paper.     

The singular limit of the Allen-Cahn equation and the FitzHugh-Nagumo system

We consider an Allen-Cahn type equation of the form ut=Δu+ε⁻²fε(x,t,u), where ε is a small parameter and fε(x,t,u)=f(u)−εgε(x,t,u) a bistable nonlinearity associated with a double-well potential whose well-depths can be slightly unbalanced. Given a rather general initial data u₀ that is independent of ε, we perform a rigorous analysis of both the generation and the motion of interface. More precisely we show that the solution develops a steep transition layer within the time scale of order ε²|lnε|, and that the layer obeys the law of motion that coincides with the formal asymptotic limit within an error margin of order ε. This is an optimal estimate that has not been known before for solutions with general initial data, even in the case where gε≡0.Next we consider systems of reaction-diffusion equations of the form

     

A recursive algorithm for the infinity-norm fixed point problem

We present the PFix algorithm for the fixed point problem f(x)=x on a nonempty domain [a,b], where d1, , and f is a Lipschitz continuous function with respect to the infinity norm, with constant q1. The computed approximation satisfies the residual criterion , where >0. In general, the algorithm requires no more than ∑_i=1^dsⁱ function component evaluations, where s≡max(1,log₂(||b−a||_∞/))+1. This upper bound has order as →0. For the domain [0,1]^d with <0.5 we prove a stronger result, i.e., an upper bound on the number of function component evaluations is , where r≡log₂(1/). This bound approaches as r→∞ (→0) and as d→∞. We show that when q<1 the algorithm can also compute an approximation satisfying the absolute criterion , where x^* is the unique fixed point of f. The complexity in this case resembles the complexity of the residual criterion problem, but with tolerance (1−q) instead of . We show that when q>1 the absolute criterion problem has infinite worst-case complexity when information consists of function evaluations. Finally, we report several numerical tests in which the actual number of evaluations is usually much smaller than the upper complexity bound.     

Gauges of Baire class one functions

Let K be a compact metric space and be a bounded Baire class one function. We proved that for any ε>0 there exists an upper semicontinuous positive function δ of f with finite oscillation index and |f(x)−f(y)|<ε whenever d(x,y)<min{δ(x),δ(y)}.     

Newton Polygons of L Functions Associated with Exponential Sums of Polynomials of Degree Four over Finite Fields

Let F_q be the finite field of q elements with characteristic p and F_q^m its extension of degree m. Fix a nontrivial additive character Ψ of F_p. If f(x₁,…, x_n)∈F_q[x₁,…, x_n] is a polynomial, then one forms the exponential sum S_m(f)=∑_{(x1,…,xn)∈(Fq^m)ⁿ}Ψ(Tr_Fq^m/Fp(f(x₁,…,x_n))). The corresponding L functions are defined by L(f, t)=exp(∑^∞_m=0S_m(f)t^m/m). In this paper, we apply Dwork's method to determine the Newton polygon for the L function L(f(x), t) associated with one variable polynomial f(x) when deg f(x)=4. As an application, we also give an affirmative answer to Wan's conjecture for the case deg f(x)=4.     

A Note on the Complexity of Solving Poisson's Equation for Spaces of Bounded Mixed Derivatives

We study the complexity of solving the d-dimensional Poisson equation on ]0, 1[^d. We restrict ourselves to cases where the solution u lies in some space of functions of bounded mixed derivatives (with respect to the L_∞- or the L₂-norm) up to ∂^2d/∏^d_j=1 ∂x²_j. An upper bound for the complexity of computing a solution of some prescribed accuracy ε with respect to the energy norm is given, which is proportional to ε⁻¹. We show this result in a constructive manner by proposing a finite element method in a special sparse grid space, which is obtained by an a priori grid optimization process based on the energy norm. Thus, the result of this paper is twofold: First, from a theoretical point of view concerning the complexity of solving elliptic PDEs, a strong tractability result of the order O(ε⁻¹) is given, and, second, we provide a practically usable hierarchical basis finite element method of this complexity O(ε⁻¹), i.e., without logarithmic terms growing exponentially in d, at least for our sparse grid setting with its underlying smoothness requirements.     

On analytic equivalence of functions at infinity

In this paper we define the relation of analytic equivalence of functions at infinity. We prove that if the ?ojasiewicz exponent at infinity of the gradient of a polynomial f∈R[x₁,…,xn] is greater or equal to k−1, then there exists ε>0 such that for every polynomial P∈R[x₁,…,xn] of degree less or equal to k, whose coefficients of monomials of degree k are less or equal ε, the polynomials f and f+P are analytically equivalent at infinity.     

An Erd?s-Ko-Rado theorem for partial permutations

Let [n] denote the set of positive integers {1,2,…,n}. An r-partial permutation of [n] is a pair (A,f) where A⊆[n], |A|=r and f:A→[n] is an injective map. A set A of r-partial permutations is intersecting if for any (A,f), (B,g)∈A, there exists x∈A∩B such that f(x)=g(x). We prove that for any intersecting family A of r-partial permutations, we have .It seems rather hard to characterize the case of equality. For 8?r?n-3, we show that equality holds if and only if there exist x₀ and ε₀ such that A consists of all (A,f) for which x₀∈A and f(x₀)=ε₀.     

Boundary layer solutions to problems with infinite-dimensional singular and regular perturbations

We prove existence, local uniqueness and asymptotic estimates for boundary layer solutions to singularly perturbed equations of the type (ε²(x)u^′′(x))=f(x,u(x))+g(x,u(x),ε(x)u^′(x)), 0<x<1, with Dirichlet and Neumann boundary conditions. Here the functions ε and g are small and, hence, regarded as singular and regular functional perturbation parameters. The main tool of the proofs is a generalization (to Banach space bundles) of an implicit function theorem of R. Magnus.     

Special Functions on the Sphere with Applications to Minimal Surfaces

A function which is homogeneous in x, y, z of degree n and satisfies V_xx + V_yy + V_zz = 0 is called a spherical harmonic. In polar coordinates, the spherical harmonics take the form rⁿf_n, where f_n is a spherical surface harmonic of degree n. On a sphere, f_n satisfies ▵ f_n + n(n + 1)f_n = 0, where ▵ is the spherical Laplacian. Bounded spherical surface harmonics are well studied, but in certain instances, unbounded spherical surface harmonics may be of interest. For example, if X is a parameterization of a minimal surface and n is the corresponding unit normal, it is known that the support function, w = X · n, satisfies ▵w + 2w = 0 on a branched covering of a sphere with some points removed. While simple in form, the boundary value problem for the support function has a very rich solution set. We illustrate this by using spherical harmonics of degree one to construct a number of classical genus-zero minimal surfaces such as the catenoid, the helicoid, Enneper's surface, and Hennenberg's surface, and Riemann's family of singly periodic genus-one minimal surfaces.     

Hitting time of a moving boundary for a diffusion

We obtain asymptotic estimates for the quantity r = log P[T_f[rang]t] as t → ∞ where T_f = inf\s{s : |X(s)|[rang]f(s)\s} and X is a real diffusion in natural scale with generator a(x) d²(·)/dx² and the ‘boundary’ f(s) is an increasing function. We impose regular variation on a and f and the result is expressed as r = ∫^t₀ λ₁ (f(s) ds(1 + o(1)) where λ₁(f) is the smallest eigenvalue for the process killed at ±f.