Unique continuous selections for metric projections of C(X) onto finite-dimensional vector subspaces, II

Best approximation in C(X) by elements of a Chebyshev subspace is governed by Haar's theorem, the de la Vallée Poussin estimates, the alternation theorem, the Remez algorithm, and Mairhuber's theorem. J. Blatter (1990, J. Approx. Theory 61, 194–221) considered best approximation in C(X) by elements of a subspace whose metric projection has a unique continuous selection and extended Haar's theorem and Mairhuber's theorem to this situation. In the present paper we so extend the de la Vallée Poussin estimates, the alternation theorem, and the Remez algorithm.     

Iterated hard-thresholding for linear inverse problems with sparsity constraints

We describe an iterative algorithm for the minimization of Tikhonov type functionals which involve sparsity constraints in form of ℓ^p -penalties which have been proposed recently for the regularization of ill-posed problems. In contrast to the well-known algorithm considered by Daubechies, Defrise and De Mol, it uses hard instead of soft thresholding. This hard thresholding algorithm is based on the generalized conditional gradient method. General results on the convergence of the generalized conditional gradient method enable us to prove strong convergence of the iterates. Furthermore we are able to establish convergence rates of O (n^–1/2) and O (λⁿ) for p = 1 and 1 < p ≤ 2 respectively. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Strong Convergence Theorem for Multiple Sets Split Feasibility Problems in Banach Spaces

The purpose of this article is to study the iterative approximation of solution to multiple sets split feasibility problems in p-uniformly convex real Banach spaces that are also uniformly smooth. We propose an iterative algorithm for solving multiple sets split feasibility problems and prove a strong convergence theorem of the sequence generated by our algorithm under some appropriate conditions in p-uniformly convex real Banach spaces that are also uniformly smooth.     

Convergence of the point vortex method for the 3-D euler equations

We prove consistency, stability, and convergence of a point vortex approximation to the 3-D incompressible Euler equations with smooth solutions. The 3-D algorithm we consider here is similar to the corresponding 3-D vortex blob algorithm introduced by Beale and Majda; see [3]. We first show that the discretization error is second-order accurate. Then we show that the method is stable in l^p norm for the particle trajectories and in w^?1.p norm for discrete vorticity. Consequently, the method converges up to any time for which the Euler equations have a smooth solution. One immediate application of our convergence result is that the vortex filament method without smoothing also converges.     

Stable enrichment and local preconditioning in the particle-partition of unity method

This paper is concerned with the stability and approximation properties of enriched meshfree and generalized finite element methods. In particular we focus on the particle-partition of unity method (PPUM) yet the presented results hold for any partition of unity based enrichment scheme. The goal of our enrichment scheme is to recover the optimal convergence rate of the uniform h-version independent of the regularity of the solution. Hence, we employ enrichment not only for modeling purposes but rather to improve the approximation properties of the numerical scheme. To this end we enrich our PPUM function space in an enrichment zone hierarchically near the singularities of the solution. This initial enrichment however can lead to a severe ill-conditioning and can compromise the stability of the discretization. To overcome the ill-conditioning of the enriched shape functions we present an appropriate local preconditioner which yields a stable and well-conditioned basis independent of the employed initial enrichment. The construction of this preconditioner is of linear complexity with respect to the number of discretization points. We obtain optimal error bounds for an enriched PPUM discretization with local preconditioning that are independent of the regularity of the solution globally and within the employed enrichment zone we observe a kind of super-convergence. The results of our numerical experiments clearly show that our enriched PPUM with local preconditioning recovers the optimal convergence rate of O(h ^p ) of the uniform h-version globally. For the considered model problems from linear elastic fracture mechanics we obtain an improved convergence rate of O(h ^p+δ ) with d 3 \frac12{\delta\geq\frac{1}{2}} for p = 1. The convergence rate of our multilevel solver is essentially the same for a purely polynomial approximation and an enriched approximation.     

Approximation and interpolation on complex algebraic varieties in pseudoconvex domains

This paper investigates the twin problems of approximation and interpolation employing weighted integral representation formulas of Berndtsson-Andersson. These interpolation techniques are applied to extend local rational approximation estimates from complex algebraic complete intersection varietyX, of pure dimensionn, into a strictly pseudoconvex semi-local domainD in the ambient space ℂ ^N withN=n+p, p>0. We also use weighted intergral representation formulas to provide criteria for both Montessus-type convergence and convergence in logarithmic capacity of diagnonal rational sequences. The logarithmic capacity we use is carefully defined via Siciak’sL-family of extremal plurisubharmonic functions. This author is grateful to the NSA for partial support during the period of this research.     

On approximation methods for the solution of one dimensional singular integral equations

In the present paper we give a survey on some new result obtained in the last few years in the theory of approximation methods for one dimensional singular equations (among others to the methods of collocation and of mechanical quadratures). Conditions for convergence and stability of these methods in the spaces L ^p (1<p<∞) and H ^α (=Lip_α)(0<α<1) are formulated and their rate of convergence is determined. simultaneously here for the first time the necessitgy of the conditions for the convergence of the methods mentioned above is investigated. In the first section a general and uniform methods for the treatment of projection methods for linear operator equations in Banach spaces in presented. The Core of this methods with unbounded projectors which is closely connected with a far-reaching generalization of the stability concept of S.G. Mikhlin.     

On the convergence of an algorithm for discreteL p approximation

Summary The convergence properties of an algorithm for discreteL _p approximation (1p<2) that has been considered by several authors are studied. In particular, it is shown that for 1<p<2 the method converges (with a suitably close starting value) to the best approximation at a geometric rate with asymptotic convergence constant 2-p. A similar result holds forp=1 if the best approximation is unique. However, in this case the convergence constant depends on the function to be approximated.     

Generalized p-Center problems: Complexity results and approximation algorithms

In an earlier paper, two alternative p-Center problems, where the centers serving costumers must be chosen so that exactly one node from each of p prespecified disjoint pairs of nodes is selected, were shown to be NP-complete. This paper considers a generalized version of these problems, in which the nodes from which the p servers are to be selected are partitioned into k sets and the number of servers selected from each set must be within a prespecified range. We refer to these problems as the ‘Set’ p-Center problems. We establish that the triangle inequality (Δ-inequality) versions of these problems, in which the edge weights are assumed to satisfy the triangle inequality, are also NP-complete. We also provide a polynomial time approximation algorithm for the two Δ-inequality Set p-Center problems that is optimal for one of the problems in the sense that no algorithm with polynomial running time can provide a better constant factor performance guarantee, unless P = NP. For the special case ‘alternative’ p-Center problems, which we refer to as the ‘Pair’ p-Center problems, we extend the previous results in several ways. For example, the results mentioned above for the Set p-Center problems also apply to the Pair p-Center problems. Furthermore, we establish and exploit a correspondence between satisfiability and the dominating set type of problems that naturally arise when considering the decision versions of the Pair p-Center problems.     

New models for locating a moving service facility

In this paper we analyze a new location problem which is a generalization of the well-known single facility location model. This extension consists of introducing a general objective function and replacing fixed locations by trajectories. We prove that the problem is well-stated and solvable. A Weiszfeld type algorithm is proposed to solve this generalized dynamic single facility location problem on L ^p spaces of functions, with p ∈(1,2]. We prove global convergence of our algorithm once we have assumed that the set of demand functions and the initial step function belong to a subspace of L ^p called Sobolev space. Finally, examples are included illustrating the application of the model to generalized regression analysis and the convergence of the proposed algorithm. The examples also show that the pointwise extension of the algorithm does not have to converge to an optimal solution of the considered problem while the proposed algorithm does.     

Nonlinear approximation by renormalized trigonometric system

We study the convergence of greedy algorithmwith regard to renormalized trigonometric system. Necessary and sufficient conditions are found for system’s normalization to guarantee almost everywhere convergence, and convergence in L ^p (T) for 1 < p < ∞ of the greedy algorithm, where T is the unit torus. Also the non existence is proved for normalization which guarantees convergence almost everywhere for functions from L ¹(T), or uniform convergence for continuous functions.     

Einige Stabilitätsungleichungen für gewöhnliche Differenzengleichungen in nichtkompakter Form

Summary For finite difference equations in noncompact form approximating ordinary boundary value problems some stability inequalities are proved inl ^p -spaces using Spijker-norms. As applications the convergence of the discrete Green's function and the possibility of lower order approximation near the boundary are treated.

     

Marcinkiewicz–Zygmund Inequalities and Polynomial Approximation from Scattered Data on SO(3)

We consider scattered data approximation problems on SO(3). To this end, we construct a new operator for polynomial approximation on the rotation group. This operator reproduces Wigner-D functions up to a given degree and has uniformly bounded L ^p -operator norm for all 1 ≤ p ≤ ∞. The operator provides a polynomial approximation with the same approximation degree of the best polynomial approximation. Moreover, the operator together with a Markov type inequality for Wigner-D functions enables us to derive scattered data L ^p -Marcinkiewicz–Zygmund inequalities for these functions for all 1 ≤ p ≤ ∞. As a major application of such inequalities, we consider the stability of the weighted least squares approximation problem on SO(3).     

Singular solutions of the Poisson equation at edges of three‐dimensional domains and their treatment with a predictor–corrector finite element method

Solutions of boundary value problems in three‐dimensional domains with edges may exhibit singularities which are known to influence both the accuracy of the finite element solutions and the rate of convergence in the error estimates. This paper considers boundary value problems for the Poisson equation on typical domains Ω ? ?³ with edge singularities and presents, on the one hand, explicit computational formulas for the flux intensity functions. On the other hand, it proposes and analyzes a nonconforming finite element method on regular meshes for the efficient treatment of the singularities. The novelty of the present method is the use of the explicit formulas for the flux intensity functions in defining a postprocessing procedure in the finite element approximation of the solution. A priori error estimates in H¹(Ω) show that the present algorithm exhibits the same rate of convergence as it is known for problems with regular solutions.     

The hp-Version of the Boundary Element Method in ℝ3 The Basic Approximation Results

This paper deals with the basic approximation properties of the h–p version of the boundary element method (BEM) in ℝ³. We extend the results on the exponential convergence of the h–p version of the boundary element method on geometric meshes from problems in polygonal domains to problems in polyhedral domains. In 2D elliptic boundary value problems the solutions have only corner singularities whereas in 3D problems they contain additional edge and corner-edge singularities. The solutions of the corresponding boundary integral equations inherit those singularities. The detailed investigations in our analysis take care of the various types of those singularities. While edge singularities can be analysed using standard one-dimensional approximation results the corner-edge singularities demand a new analysis. © 1997 by B. G. Teubner Stuttgart–John Wiley & Sons Ltd.     

Local convergence in a generalized Fermat-Weber problem

In the Fermat-Weber problem, the location of a source point in ^N is sought which minimizes the sum of weighted Euclidean distances to a set of destinations. A classical iterative algorithm known as the Weiszfeld procedure is used to find the optimal location. Kuhn proves global convergence except for a denumerable set of starting points, while Katz provides local convergence results for this algorithm. In this paper, we consider a generalized version of the Fermat-Weber problem, where distances are measured by anl _p norm and the parameterp takes on a value in the closed interval [1, 2]. This permits the choice of a continuum of distance measures from rectangular (p=1) to Euclidean (p=2). An extended version of the Weiszfeld procedure is presented and local convergence results obtained for the generalized problem. Linear asymptotic convergence rates are typically observed. However, in special cases where the optimal solution occurs at a singular point of the iteration functions, this rate can vary from sublinear to quadratic. It is also shown that for sufficiently large values ofp exceeding 2, convergence of the Weiszfeld algorithm will not occur in general.     

Convergence of Some Greedy Algorithms in Banach Spaces

We consider some theoretical greedy algorithms for approximation in Banach spaces with respect to a general dictionary. We prove convergence of the algorithms for Banach spaces which satisfy certain smoothness assumptions. We compare the algorithms and their rates of convergence when the Banach space is L_p(\mathbbT^d)L_p(\mathbb{T}^d) ($1相似文献   

Global minimization of a generalized convex multiplicative function

This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.     

Iterative Convex Quadratic Approximation for Global Optimization in Protein Docking

An algorithm for finding an approximate global minimum of a funnel shaped function with many local minima is described. It is applied to compute the minimum energy docking position of a ligand with respect to a protein molecule. The method is based on the iterative use of a convex, general quadratic approximation that underestimates a set of local minima, where the error in the approximation is minimized in the L¹ norm. The quadratic approximation is used to generate a reduced domain, which is assumed to contain the global minimum of the funnel shaped function. Additional local minima are computed in this reduced domain, and an improved approximation is computed. This process is iterated until a convergence tolerance is satisfied. The algorithm has been applied to find the global minimum of the energy function generated by the Docking Mesh Evaluator program. Results for three different protein docking examples are presented. Each of these energy functions has thousands of local minima. Convergence of the algorithm to an approximate global minimum is shown for all three examples.     

The p-version of the boundary element method for hypersingular operators on piecewise plane open surfaces

Summary. We prove an optimal a priori error estimate for the p-version of the boundary element method with hypersingular operators on piecewise plane open surfaces. The solutions of problems on open surfaces typically exhibit a singular behavior at the edges and corners of the surface which prevent an approximation analysis in H¹. We analyze the approximation by polynomials of typical singular functions in fractional order Sobolev spaces thus giving, as an application, the optimal rate of convergence of the p-version of the boundary element method. This paper extends the results of [C. Schwab, M. Suri, The optimal p-version approximation of singularities on polyhedra in the boundary element method, SIAM J. Numer. Anal., 33 (1996), pp. 729–759] who only considered closed surfaces where the solution is in H¹.Mathematics Subject Classification (2000): 41A10, 65N15, 65N38Financed by the FONDAP Program in Applied Mathematics, Chile.Supported by the FONDAP Program in Applied Mathematics and Fondecyt project no. 1010220, both Chile.