共查询到20条相似文献,搜索用时 31 毫秒
1.
Snorre H. Christiansen 《Calcolo》2009,46(3):211-220
Given a sequence of Galerkin spaces X
h
of square-integrable vector fields, we state necessary and sufficient conditions on X
h
under which it is true that for any two sequences of vector fields u
h
,u
h
′∈X
h
converging weakly in L2 and such that u
h
is discrete divergence free and curl u
h
′ is precompact in H−1, the scalar product u
h
⋅u′
h
converges in the sense of distributions to the right limit. The conditions are related to super-approximation and discrete
compactness results for mixed finite elements, and are satisfied for Nédélec’s edge elements. We also provide examples of
sequences of discrete divergence free edge element vector fields converging weakly to 0 in L2 but whose divergence is not precompact in H
loc
−1.
相似文献
2.
We present in this paper an analysis of a semi-Lagrangian second order Backward Difference Formula combined with hp-finite
element method to calculate the numerical solution of convection diffusion equations in ℝ2. Using mesh dependent norms, we prove that the a priori error estimate has two components: one corresponds to the approximation
of the exact solution along the characteristic curves, which is
O(Dt2+hm+1(1+\frac\mathopen|logh|Dt))O(\Delta t^{2}+h^{m+1}(1+\frac{\mathopen{|}\log h|}{\Delta t})); and the second, which is O(Dtp+|| [(u)\vec]-[(u)\vec]h||L¥)O(\Delta t^{p}+\| \vec{u}-\vec{u}_{h}\|_{L^{\infty}}), represents the error committed in the calculation of the characteristic curves. Here, m is the degree of the polynomials in the finite element space, [(u)\vec]\vec{u} is the velocity vector, [(u)\vec]h\vec{u}_{h} is the finite element approximation of [(u)\vec]\vec{u} and p denotes the order of the method employed to calculate the characteristics curves. Numerical examples support the validity
of our estimates. 相似文献
3.
A non-smooth data error estimate with respect to theL
2 norm is shown for a semidiscrete Galerkin-Petrov method for a parabolic problem in one space dimension. If the trial and
test spaces consist of piecewise polynomials of degreer−1 inC
k
anr+1 inC
k+2
, respectively, with test functions satisfying boundary conditions, then the error norm is bounded byCh
r
t
−r/2
fort positive, whereh is the maximum mesh size. 相似文献
4.
We consider the symmetric formulation of the interior penalty discontinuous Galerkin finite element method for the numerical
solution of the biharmonic equation with Dirichlet boundary conditions in a bounded polyhedral domain in
. For a shape-regular family of meshes consisting of parallelepipeds, we derive hp-version a priori bounds on the global error measured in the L2 norm and in broken Sobolev norms. Using these, we obtain hp-version bounds on the error in linear functionals of the solution. The bounds are optimal with respect to the mesh size h and suboptimal with respect to the degree of the piecewise polynomial approximation p. The theoretical results are confirmed by numerical experiments, and some practical applications in Poisson–Kirchhoff thin
plate theory are presented. 相似文献
5.
As a first step to developing mathematical support for finite element approximation to the large eddies in fluid motion we
consider herein the Stokes problem. We show that the local average of the usual approximate flow field u
h
over radius δ provides a very accurate approximation to the flow structures of O(δ) or greater. The extra accuracy appears for quadratic or higher velocity elements and degrades to the usual finite element
accuracy as the averaging radius δ→h (the local meshwidth). We give both a priori and a posteriori error estimates incorporating this effect.
Received December 3, 1999; revised October 16, 2000 相似文献
6.
Zhi-Zhong Chen 《Algorithmica》2008,51(1):1-23
The Degree-
Δ
Closest Phylogenetic
k
th Root Problem (ΔCPR
k
) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E
⊕{{u,v} : u,v are leaves of T and d
T
(u,v)≤k}|, is minimized, where d
T
(u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization
problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for Δ
CPR
2 for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR
3, and a polynomial-time approximation scheme for the maximization version of Δ
CPR
k
for any fixed Δ and k. 相似文献
7.
Jean-François Aujol Guy Gilboa Tony Chan Stanley Osher 《International Journal of Computer Vision》2006,67(1):111-136
This paper explores various aspects of the image decomposition problem using modern variational techniques. We aim at splitting
an original image f into two components u and ρ, where u holds the geometrical information and ρ holds the textural information. The focus of this paper is to study different energy
terms and functional spaces that suit various types of textures. Our modeling uses the total-variation energy for extracting
the structural part and one of four of the following norms for the textural part: L2, G, L1 and a new tunable norm, suggested here for the first time, based on Gabor functions. Apart from the broad perspective and
our suggestions when each model should be used, the paper contains three specific novelties: first we show that the correlation
graph between u and ρ may serve as an efficient tool to select the splitting parameter, second we propose a new fast algorithm to solve the
TV − L1 minimization problem, and third we introduce the theory and design tools for the TV-Gabor model.
First online version published in February, 2006 相似文献
8.
This paper develops and analyzes finite element Galerkin and spectral Galerkin methods for approximating viscosity solutions
of the fully nonlinear Monge-Ampère equation det (D
2
u
0)=f (>0) based on the vanishing moment method which was developed by the authors in Feng and Neilan (J. Sci. Comput. 38:74–98,
2009) and Feng (Convergence of the vanishing moment method for the Monge-Ampère equation, submitted). In this approach, the Monge-Ampère
equation is approximated by the fourth order quasilinear equation −εΔ2
u
ε
+det D
2
u
ε
=f accompanied by appropriate boundary conditions. This new approach enables us to construct convergent Galerkin numerical methods
for the fully nonlinear Monge-Ampère equation (and other fully nonlinear second order partial differential equations), a task
which has been impracticable before. In this paper, we first develop some finite element and spectral Galerkin methods for
approximating the solution u
ε
of the regularized problem. We then derive optimal order error estimates for the proposed numerical methods. In particular,
we track explicitly the dependence of the error bounds on the parameter ε, for the error ue-uehu^{\varepsilon}-u^{\varepsilon}_{h}. Due to the strong nonlinearity of the underlying equation, the standard error estimate technique, which has been widely
used for error analysis of finite element approximations of nonlinear problems, does not work here. To overcome the difficulty,
we employ a fixed point technique which strongly makes use of the stability property of the linearized problem and its finite
element approximations. Finally, using the Argyris finite element method as an example, we present a detailed numerical study
of the rates of convergence in terms of powers of ε for the error u0-uheu^{0}-u_{h}^{\varepsilon}, and numerically examine what is the “best” mesh size h in relation to ε in order to achieve these rates. 相似文献
9.
Nabil R. Nassif 《Calcolo》1975,12(1):51-61
A Galerkin procedure is used to obtain a semi-discretization for parabolic equations such as the heat equationu
t
=t
xx
. The time variable being left continuous, the higher order approximation thus obtained for the space variable is then matched
by a higher order discretization of the system of ordinary differential equations that results. Specifically we choose the
Padé (2,2), and show how complex factorization it can be practically used. Moreover we prove that the operation count is 0
(h
−2) as compared to 0(h
−3) with the classical Crank-Nicolson. Numerical calculations are available.
This work was supported by the Office of Naval Research, and the Lebanese Council for Scientific Research. 相似文献
10.
In this article, a priori error bounds are derived for an hp-local discontinuous Galerkin (LDG) approximation to a parabolic integro-differential equation. It is shown that error estimates
in L
2-norm of the gradient as well as of the potential are optimal in the discretizing parameter h and suboptimal in the degree of polynomial p. Due to the presence of the integral term, an introduction of an expanded mixed type Ritz-Volterra projection helps us to
achieve optimal estimates. Further, it is observed that a negative norm estimate of the gradient plays a crucial role in our
convergence analysis. As in the elliptic case, similar results on order of convergence are established for the semidiscrete
method after suitably modifying the numerical fluxes. The optimality of these theoretical results is tested in a series of
numerical experiments on two dimensional domains. 相似文献
11.
The paper deals with a numerical analysis of the incomplete interior penalty Galerkin (IIPG) method applied to one dimensional
Poisson problem. Based on a particular choice of the interior penalty parameter σ (order of O(h
−1)), we derive the optimal error estimate in the L
2-norm for odd degrees of polynomial approximation for locally quasi-uniform meshes. Moreover, we show that only the mentioned
choice of the penalty parameter leads to optimal orders of convergence. Finally, presented numerical experiments verify the
theoretical results. 相似文献
12.
A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P
1=〈u
1,u
2,…,u
n
〉 and P
2=〈v
1,v
2,…,v
n
〉 of G are said to be independent if u
1=v
1, u
n
=v
n
, and u
i
≠v
i
for all 1<i<n; and both are full-independent if u
i
≠v
i
for all 1≤i≤n. Moreover, P
1 and P
2 are independent starting at
u
1, if u
1=v
1 and u
i
≠v
i
for all 1<i≤n. A set of Hamiltonian paths {P
1,P
2,…,P
k
} of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at
u
1) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting
at u
1). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Q
n
is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q
n
. In this paper, we show the following results:
相似文献
1. | When |F|≤n−4, Q n −F−{x,y} remains Hamiltonian-laceable, where x and y are any two vertices from different partite sets and n≥4. |
2. | When |F|≤n−2, Q n −F contains (n−|F|−1)-pairwise full-independent Hamiltonian paths between n−|F|−1 pairs of adjacent vertices, where n≥2. |
3. | When |F|≤n−2, Q n −F contains (n−|F|−1)-pairwise independent Hamiltonian paths starting at any vertex v in a partite set to n−|F|−1 distinct vertices in the other partite set, where n≥2. |
4. | When 1≤|F|≤n−2, Q n −F contains (n−|F|−1)-pairwise independent Hamiltonian paths between any two vertices from different partite sets, where n≥3. |
13.
Emiko Ishiwata 《Computing》2000,64(3):207-222
In this paper, we extend the recent results of H. Brunner in BIT (1997) for the DDE y′(t)= by(qt), y(0)=1 and the DVIE y(t)=1+∫0
t
by(qs)ds with proportional delay qt, 0<q≤1, to the neutral functional-differential equation (NFDE):
and the delay Volterra integro-differential equation (DVIDE) :
with proportional delays p
i
t and q
i
t, 0<p
i
,q
i
≤1 and complex numbers a,b
i
and c
i
.
We analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods at the first mesh point t=h for the collocation solution v(t) of the NFDE and the `iterated collocation solution u
it
(t)' of the DVIDE to the solution y(t), and investigate the existence of the collocation polynomials M
m
(t) of v(th) or M^
m
(t) of u
it
(th), t∈[0,1] such that the rational approximant v(h) or u
it
(h) is the (m,m)-Padé approximant to y(h) and satisfies |v(h)−y(h)|=O(h
2
m
+1). If they exist, then we actually give the conditions of M
m
(t) and M^
m
(t), respectively.
Received September 17, 1998; revised September 30, 1999 相似文献
14.
Pablo Groisman 《Computing》2006,76(3-4):325-352
The equation u
t
=Δu+u
p
with homogeneous Dirichlet boundary conditions has solutions with blow-up if p>1. An adaptive time-step procedure is given to reproduce the asymptotic behavior of the solutions in the numerical approximations.
We prove that the numerical methods reproduce the blow-up cases, the blow-up rate and the blow-up time. We also localize the
numerical blow-up set. 相似文献
15.
Range images provide important sources of information in many three-dimensional robot vision problems such as navigation and object recognition. Many physical factors, however, introduce noise to the discrete measurements in range images, identifying the need to reassess the error distribution in samples taken from real range images. This paper suggests the use of the L
p
norms to yield reliable estimates of location and regression coefficients. This particular approach is compared against two commonly used approaches: Equally Weighted Least Squares, which minimizes the L2 norm; and the Chebychev approximation, which minimizes the L
1 norm. The problem is a weighted least squares case where the weights are derived from the chosen parameter, p, and its ability to yield a variety of location estimates spanning from the sample mean to the sample median. These two estimates have a wide application in image processing that includes noise removal. This paper will show the problems associated with these two techniques, and suggest experimental solutions to minimize them. A specific operating range is determined in which the L
p
norms perform well and a regression module is used in conjunction with a region-growing segmentation algorithm to provide a reliable partition of range images. 相似文献
16.
Jae-Hun Jung 《Journal of scientific computing》2009,39(1):49-66
The solution of differential equations with singular source terms contains the local jump discontinuity in general and its
spectral approximation is oscillatory due to the Gibbs phenomenon. To minimize the Gibbs oscillations near the local jump
discontinuity and improve convergence, the regularization of the approximation is needed. In this note, a simple derivative
of the discrete Heaviside function H
c
(x) on the collocation points is used for the approximation of singular source terms δ(x−c) or δ
(n)(x−c) without any regularization. The direct projection of H
c
(x) yields highly oscillatory approximations of δ(x−c) and δ
(n)(x−c). In this note, however, it is shown that the direct projection approach can yield a non-oscillatory approximation of the
solution and the error can also decay uniformly for certain types of differential equations. For some differential equations,
spectral accuracy is also recovered. This method is limited to certain types of equations but can be applied when the given
equation has some nice properties. Numerical examples for elliptic and hyperbolic equations are provided.
The current address: Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA. 相似文献
17.
An optimal choice ofu for approximating thed
th
derivative,d=1,2, of a real valued function of a real variable by a difference quotient of the formh
−d
∑
i=1
n
w
i
f(x+u
i
h) is given. Ifd=1 andn is odd, or ifd=2 andn is even, this choiceu turns out to be surprisingly asymmetric. 相似文献
18.
I. I. Lyashko S. I. Lyashko S. A. Voitsekhovskii 《Cybernetics and Systems Analysis》2000,36(1):108-117
A combination of both fictitious domain and net methods is used for solution of optimal-control problems for elliptic systems.
The proposed difference scheme has an order of accuracy ofO(h
1/2) in the net norm L2.
Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 138–146, January–February, 2000. 相似文献
19.
For high order interpolations at both end points of two rational Bézier curves, we introduce the concept of C(v,u)-continuity and give a matrix expression of a necessary and sufficient condition for satisfying it. Then we propose three new algorithms, in a unified approach, for the degree reduction of Bézier curves, approximating rational Bézier curves by Bézier curves and the degree reduction of rational Bézier curves respectively; all are in L2 norm and C(v,u)-continuity is satisfied. The algorithms for the first and second problems can get the best approximation results, and for the third one, resorting to the steepest descent method in numerical optimization obtains a series of degree reduced curves iteratively with decreasing approximation errors. Compared to some well-known algorithms for the degree reduction of rational Bézier curves, such as the uniformizing weights algorithm, canceling the best linear common divisor algorithm and shifted Chebyshev polynomials algorithm, the new one presented here can give a better approximation error, do multiple degrees of reduction at a time and preserve high order interpolations at both end points. 相似文献
20.
We consider a finite element approximation of a phase field model for the evolution of voids by surface diffusion in an electrically
conducting solid. The phase field equations are given by the nonlinear degenerate parabolic system
subject to an initial condition u
0(⋅)∈[−1,1] on u and flux boundary conditions on all three equations. Here γ∈ℝ>0, α∈ℝ≥0, Ψ is a non-smooth double well potential, and c(u):=1+u, b(u):=1−u
2 are degenerate coefficients. On extending existing results for the simplified two dimensional phase field model, we show
stability bounds for our approximation and prove convergence, and hence existence of a solution to this nonlinear degenerate
parabolic system in three space dimensions. Furthermore, a new iterative scheme for solving the resulting nonlinear discrete
system is introduced and some numerical experiments are presented.
L. Baňas was supported by the EPSRC grant EP/C548973/1. 相似文献