首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
《Journal of Complexity》1999,15(2):200-213
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(n3(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(n2(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.  相似文献   

2.
In this paper some upper bound for the error ∥ s-f is given, where f ε C1[a,b], but s is a so-called Hermite spline interpolant (HSI) of degree 2q ?1 such that f(xi) = s(xi), f′(rmxi) = s′(xi), s(j) (xi) = 0 (i = 0, 1, …, n; j = 2, 3, …, q ?1; n > 0, q > 0) and the knots xi are such that a = x0 < x1 < … < xn = b. Necessary and sufficient conditions for the existence of convex HSI are given and upper error bound for approximation of the function fε C1[a, b] by convex HSI is also given.  相似文献   

3.
In L 2(?3;?3), 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(τ(?0)1/2) and (?0)?1/2 sin(τ(?0)1/2), respectively, in the norm of the operators acting from the Sobolev space H s (with a suitable s) to ?2. Here ?0 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 ? τ 2 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/ε).  相似文献   

4.
《Journal of Complexity》2000,16(2):377-389
We study the complexity of approximating the Stieltjes integral ∫10 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{rs+1} and that comp(ε)≍ε−1/min{rs+1}. We also present an algorithm that computes an ε-approximation at nearly minimal cost.  相似文献   

5.
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) = ∑ni = 1hi(t) xi such that μ(t?Kε; f(t) ≠ g(t)) < ε, where xi?E and hi(t) are real bounded continuous functions with disjoint supports.  相似文献   

6.
We study the existence, multiplicity and shape of positive solutions of the system −ε2Δu+V(x)u=K(x)g(v), −ε2Δ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.  相似文献   

7.
《Journal of Complexity》1998,14(4):448-453
LetP⊂[0, 1]dbe ann-point set and letw: P→[0, ∞) be a weight function withw(P)=∑zP w(z)=1. TheL2-discrepancy of the weighted set (P, w) is defined as theL2-average ofD(x)=vol(Bx)−w(PBx) overx∈[0, 1]d, where vol(Bx) is the volume of thed-dimensional intervalBx=∏dk=1 [0, xk). 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 mostppoints in [0, 1]dwithL2-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 toL2-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.  相似文献   

8.
Given points p and q in the plane, we are interested in separating them by two curves C1 and C2 such that every point of C1 has equal distance to p and to C2, and every point of C2 has equal distance to C1 and to q. We show by elementary geometric means that such C1 and C2 exist and are unique. Moreover, for p=(0,1) and q=(0,−1), C1 is the graph of a function , C2 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 xR 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.  相似文献   

9.
10.
We consider an Allen-Cahn type equation of the form utu+ε−2fε(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 u0 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 ε2|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
  相似文献   

11.
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=1dsi function component evaluations, where s≡max(1,log2(||ba||/))+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≡log2(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.  相似文献   

12.
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)}.  相似文献   

13.
14.
Let Fq be the finite field of q elements with characteristic p and Fqm its extension of degree m. Fix a nontrivial additive character Ψ of Fp. If f(x1,…, xn)∈Fq[x1,…, xn] is a polynomial, then one forms the exponential sum Sm(f)=∑(x1,…,xn)∈(Fqm)nΨ(TrFqm/Fp(f(x1,…,xn))). The corresponding L functions are defined by L(f, t)=exp(∑m=0Sm(f)tm/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.  相似文献   

15.
《Journal of Complexity》1999,15(2):167-199
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 L2-norm) up to ∂2d/∏dj=1 x2j. 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 ε−1. 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(ε−1) is given, and, second, we provide a practically usable hierarchical basis finite element method of this complexity O(ε−1), i.e., without logarithmic terms growing exponentially in d, at least for our sparse grid setting with its underlying smoothness requirements.  相似文献   

16.
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 fR[x1,…,xn] is greater or equal to k−1, then there exists ε>0 such that for every polynomial PR[x1,…,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.  相似文献   

17.
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 xAB 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 x0 and ε0 such that A consists of all (A,f) for which x0A and f(x0)=ε0.  相似文献   

18.
We prove existence, local uniqueness and asymptotic estimates for boundary layer solutions to singularly perturbed equations of the type (ε2(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.  相似文献   

19.
A function which is homogeneous in x, y, z of degree n and satisfies Vxx + Vyy + Vzz = 0 is called a spherical harmonic. In polar coordinates, the spherical harmonics take the form rnfn, where fn is a spherical surface harmonic of degree n. On a sphere, fn satisfies ▵ fn + n(n + 1)fn = 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.  相似文献   

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

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号