Construction of Solutions and L^1-error Estimates of Viscous Methods for Scalar Conservation Laws with Boundary

This paper is concerned with an initial boundary value problem for strictly convex conservation laws whose weak entropy solution is in the piecewise smooth solution class consisting of finitely many discontinuities. By the structure of the weak entropy solution of the corresponding initial value problem and the boundary entropy condition developed by Bardos-Leroux Nedelec, we give a construction method to the weak entropy solution of the initial boundary value problem. Compared with the initial value problem, the weak entropy solution of the initial boundary value problem includes the following new interaction type： an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary. According to the structure and some global estimates of the weak entropy solution, we derive the global L^1-error estimate for viscous methods to this initial boundary value problem by using the matching travelling wave solutions method. If the inviscid solution includes the interaction that an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary, or the inviscid solution includes some shock wave which is tangent to the boundary, then the error of the viscosity solution to the inviscid solution is bounded by O（ε^1/2） in L^1-norm; otherwise, as in the initial value problem, the L^1-error bound is O（ε｜ In ε｜）.     

Semidiscrete and asymptotic approximations for the nonstationary radiative–conductive heat transfer problem in a periodic system of grey heat shields

We consider semidiscrete and asymptotic approximations to a solution to the nonstationary nonlinear initial-boundary-value problem governing the radiative–conductive heat transfer in a periodic system consisting of n grey parallel plate heat shields of width ε = 1/n, separated by vacuum interlayers. We study properties of special semidiscrete and homogenized problems whose solutions approximate the solution to the problem under consideration. We establish the unique solvability of the problem and deduce a priori estimates for the solutions. We obtain error estimates of order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) and O(ε) for semidiscrete approximations and error estimates of order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) and O(ε ^3/4) for asymptotic approximations. Bibliography: 9 titles.     

Almost global wellposedness of the 2-D full water wave problem

We consider the problem of global in time existence and uniqueness of solutions of the 2-D infinite depth full water wave equation. It is known that this equation has a solution for a time period [0,T/ε] for initial data of the form ε Ψ, where T depends only on Ψ. In this paper, we show that for such data there exists a unique solution for a time period [0,e ^T/ε ]. This is achieved by better understandings of the nature of the nonlinearity of the full water wave equation. Financial support provided in part by NSF grant DMS-0400643.     

Approximation of singularly perturbed parabolic equations in unbounded domains subject to piecewise smooth boundary conditions in the case of solutions that grow at infinity

The initial-boundary value problem in a domain on a straight line that is unbounded in x is considered for a singularly perturbed reaction-diffusion parabolic equation. The higher order derivative in the equation is multiplied by a parameter ɛ², where ɛ ∈ (0, 1]. The right-hand side of the equation and the initial function grow unboundedly as x → ∞ at a rate of O(x ²). This causes the unbounded growth of the solution at infinity at a rate of O(Ψ(x)), where Ψ(x) = x ² + 1. The initialboundary function is piecewise smooth. When ɛ is small, a boundary and interior layers appear, respectively, in a neighborhood of the lateral part of the boundary and in a neighborhood of the characteristics of the reduced equation passing through the discontinuity points of the initial function. In the problem under examination, the error of the grid solution grows unboundedly in the maximum norm as x → ∞ even for smooth solutions when ɛ is fixed. In this paper, the proximity of solutions of the initial-boundary value problem and its grid approximations is considered in the weighted maximum norm ∥·∥ ^w with the weighting function Ψ⁻¹(x); in this norm, the solution of the initial-boundary value problem is ɛ-uniformly bounded. Using the method of special grids that condense in a neighborhood of the boundary layer or in neighborhoods of the boundary and interior layers, special finite difference schemes are constructed and studied that converge ɛ-uniformly in the weighted norm. It is shown that the convergence rate considerably depends on the type of nonsmoothness in the initial-boundary conditions. Grid approximations of the Cauchy problem with the right-hand side and the initial function growing as O(Ψ(x)) that converge ɛ-uniformly in the weighted norm are also considered.     

Rank-two update algorithms for the minimum volume enclosing ellipsoid problem

We consider the problem of computing a (1+ε)-approximation to the minimum volume enclosing ellipsoid (MVEE) of a given set of m points in R ⁿ . Based on the idea of sequential minimal optimization (SMO) method, we develop a rank-two update algorithm. This algorithm computes an approximate solution to the dual optimization formulation of the MVEE problem, which updates only two weights of the dual variable at each iteration. We establish that this algorithm computes a (1+ε)-approximation to MVEE in O(mn ³/ε) operations and returns a core set of size O(n ²/ε) for ε∈(0,1). In addition, we give an extension of this rank-two update algorithm. Computational experiments show the proposed algorithms are very efficient for solving large-scale problem with a high accuracy.     

Homogenization of the diffusion equation with nonlinear flux condition on the interior boundary of a perforated domain — the influence of the scaling on the nonlinearity in the effective sink-source term

In this paper, we study the asymptotic behavior of solutions u _ε of the initial boundary value problem for parabolic equations in domains W_e ì \mathbbRⁿ {\Omega_\varepsilon } \subset {\mathbb{R}^n} , n ≥ 3, perforated periodically by balls with radius of critical size ε ^α , α = n/(n − 2), and distributed with period ε. On the boundary of the balls a nonlinear third boundary condition is imposed. The weak convergence of the solutions u _ε to the solution of an effective equation is given. Furthermore, an improved approximation for the gradient of the microscopic solutions is constructed, and a corrector result with respect to the energy norm is proved.     

A theorem of the Phragmén-Lindelöf type for solutions of an evolution equation of the second order with respect to time variable

We consider a solution u(x, t) of the general linear evolution equation of the second order with respect to time variable given on the ball Π(T) = {(x,t): xε R ⁿ, t ε [0, T]} and study the dependence of the behavior of this solution on the behavior of the functions at infinity. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 5, pp. 724–731, May, 1998.     

Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces

For a real square-free multivariate polynomial F, we treat the general problem of finding real solutions of the equation F=0, provided that the real solution set {F=0}_ℝ is compact. We allow that the equation F=0 may have singular real solutions. We are going to decide whether this equation has a non-singular real solution and, if this is the case, we exhibit one for each generically smooth connected component of {F=0}_ℝ. We design a family of elimination algorithms of intrinsic complexity which solves this problem. In the worst case, the complexity of our algorithms does not exceed the already known extrinsic complexity bound of (nd) ^O(n) for the elimination problem under consideration, where n is the number of indeterminates of F and d its (positive) degree. In the case that the real variety defined by F is smooth, there already exist algorithms of intrinsic complexity that solve our problem. However, these algorithms cannot be used in case when F=0 admits F-singular real solutions.     

Complex ordering and stochastic oscillations in a class of reaction-diffusion systems with small diffusion

Summary We consider four models of partial differential equations obtained by applying a generalization of the method of normal forms to two-component reaction-diffusion systems with small diffusionu _t=εDu _xx+(A+εA ₁)u+F(u),u ∈ ℝ². These equations (quasinormal forms) describe the behaviour of solutions of the original equation forε → 0. One of the quasinormal forms is the well-known complex Ginzburg-Landau equation. The properties of attractors of the other three equations are considered. Two of these equations have an interesting feature that may be called asensitivity to small parameters: they contain a new parameterϑ(ε)=−(aε ^−1/2 mod 1) that influences the behaviour of solutions, but changes infinitely many times whenε → 0. This does not create problems in numerical analysis of quasinormal forms, but makes numerical study of the original problem involvingε almost impossible.     

On a Global Complexity Bound of the Levenberg-Marquardt Method

In this paper, we investigate a global complexity bound of the Levenberg-Marquardt method (LMM) for the nonlinear least squares problem. The global complexity bound for an iterative method solving unconstrained minimization of φ is an upper bound to the number of iterations required to get an approximate solution, such that ‖∇φ(x)‖≤ε. We show that the global complexity bound of the LMM is O(ε ⁻²).     

The problem of thermo-chemical formation of a composite material. Properties of solutions and homogenization

We study a problem with rapidly oscillating coefficients which arises in describing the process of thermo-chemical formation of a composite material. We homogenize this problem and study the existence and uniqueness of solutions to the original and homogenized problems, as well as properties of the solutions. We estimate an error in homogenization with order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) in the energy norm and with order O(ε) in the L ^∞-norm. Bibliography: 10 titles.     

On the asymptotic expansion of the solution of the plane Stokes problem in a perforated domain

This article deals with the asymptotic behavior as ε → 0 of the solution {u _ɛ, p _ɛ} of the plane Stokes problem in a perforated domain. The limit problem is constructed and estimates for the speed of convergence are obtained. It is shown that the speed of convergence is of order O(ε ^3/2). __________ Translated from Trudy Seminara imeni I. G. Petrovskogo, No. 25, pp. 3–20, 2005.     

Asymptotic modelling of conductive thin sheets

We derive and analyse models which reduce conducting sheets of a small thickness ε in two dimensions to an interface and approximate their shielding behaviour by conditions on this interface. For this we consider a model problem with a conductivity scaled reciprocal to the thickness ε, which leads to a nontrivial limit solution for ε → 0. The functions of the expansion are defined hierarchically, i.e. order by order. Our analysis shows that for smooth sheets the models are well defined for any order and have optimal convergence meaning that the H ¹-modelling error for an expansion with N terms is bounded by O(ε ^N+1) in the exterior of the sheet and by O(ε ^N+1/2) in its interior. We explicitly specify the models of order zero, one and two. Numerical experiments for sheets with varying curvature validate the theoretical results.     

Asymptotic analysis of a parabolic semilinear problem with nonlinear boundary multiphase interactions in a perforated domain

We consider a parabolic semilinear problem with rapidly oscillating coefficients in a domain Ω_ε that is ε-periodically perforated by small holes of size O\mathcal {O}(ε). The holes are divided into two ε-periodical sets depending on the boundary interaction at their surfaces, and two different nonlinear Robin boundary conditions σ_ε(u _ε) + εκ _m (u _ε) = εg ^(m) _ε, m = 1, 2, are imposed on the boundaries of holes. We study the asymptotics as ε → 0 and establish a convergence theorem without using extension operators. An asymptotic approximation of the solution and the corresponding error estimate are also obtained. Bibliography: 60 titles. Illustrations: 1 figure.     

Sufficient conditions on the existence of trapped modes in problems of the linear theory of surface waves

An asymptotic model is found for the Neumann problem for the second-order differential equation with piecewise constant coefficients in a composite domain Ω∪ω, which are small, of order ε, in the subdomain ω. Namely, a domain Ω(ε) with a singular perturbed boundary is constructed, the solution for which provides a two-term asymptotic, that is, of increased accuracy O(ε²| log ε|^3/2), approximation to the restriction to Ω of the solution of the original problem. As opposed to other singularly perturbed problems, in the case of contrasting stiffness, the modeling requires the construction of a contour ∂Ω(ε) with ledges, i.e., with boundary fragments of curvature O(ε⁻¹). Bibliography: 33 titles.     

Integer knapsack problems with set-up weights

The Integer Knapsack Problem with Set-up Weights (IKPSW) is a generalization of the classical Integer Knapsack Problem (IKP), where each item type has a set-up weight that is added to the knapsack if any copies of the item type are in the knapsack solution. The k-item IKPSW (kIKPSW) is also considered, where a cardinality constraint imposes a value k on the total number of items in the knapsack solution. IKPSW and kIKPSW have applications in the area of aviation security. This paper provides dynamic programming algorithms for each problem that produce optimal solutions in pseudo-polynomial time. Moreover, four heuristics are presented that provide approximate solutions to IKPSW and kIKPSW. For each problem, a Greedy heuristic is presented that produces solutions within a factor of 1/2 of the optimal solution value, and a fully polynomial time approximation scheme (FPTAS) is presented that produces solutions within a factor of ε of the optimal solution value. The FPTAS for IKPSW has time and space requirements of O(nlog n+n/ε ²+1/ε ³) and O(1/ε ²), respectively, and the FPTAS for kIKPSW has time and space requirements of O(kn ²/ε ³) and O(k/ε ²), respectively.     

Two-phase Stefan problem with vanishing specific heat

The unique solvability of the two-phase Stefan problem with a small parameter ε ∈ [0; ε ₀] at the time derivative in the heat equations is proved. The solution is obtained on a certain time interval [0; t ₀] independent of ε. The solution of the Stefan problem is compared with the solution to the Hele–Shaw problem corresponding to the case ε = 0. The solutions of both problems are not assumed to coincide at the initial moment of time. Bibliography: 18 titles. Dedicated to Vsevolod Alekseevich Solonnikov on the occasion of his jubilee Published in Zapiski Nauchnykh Seminarov POMI, Vol. 362, 2008, pp. 337–363.     

Homogenization of the parabolic cauchy problem in the Sobolev class H<Superscript>1</Superscript>(R<Superscript>d</Superscript>)

Homogenization in the small period limit for the solution ue of the Cauchy problem for a parabolic equation in R^d is studied. The coefficients are assumed to be periodic in R^d with respect to the lattice ɛG. As ɛ → 0, the solution u ɛ converges in L2(R^d) to the solution u0 of the effective problem with constant coefficients. The solution u ɛis approximated in the norm of the Sobolev space H ¹(R^d) with error O( ɛ); this approximation is uniform with respect to the L2-norm of the initial data and contains a corrector term of order ɛ. The dependence of the constant in the error estimate on time t is given. Also, an approximation in H ¹(R^d) for the solution of the Cauchy problem for a nonhomogeneous parabolic equation is obtained.     

Representing a Functional Curve by Curves with Fewer Peaks

In this paper, we study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Representing a function (or its curve) by certain classes of structurally simpler functions (or their curves) is a basic mathematical problem. Problems of this kind also find applications in applied areas such as intensity-modulated radiation therapy (IMRT). Let f\bf f be an input piecewise linear functional curve of size n. We consider several variations of the problems. (1) Uphill–downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing (uphill) and one nonincreasing (downhill), such that their sum exactly or approximately represents f\bf f. (2) Unimodal representation (UR): Find a set of unimodal (single-peak) curves such that their sum exactly or approximately represents f\bf f. (3) Fewer-peak representation (FPR): Find a piecewise linear curve with at most k peaks that exactly or approximately represents f\bf f. Furthermore, for each problem, we consider two versions. For the UDPR problem, we study its feasibility version: Given ε>0, determine whether there is a feasible UDPR solution for f\bf f with an approximation error ε; its min-ε version: Compute the minimum approximation error ε ^∗ such that there is a feasible UDPR solution for f\bf f with error ε ^∗. For the UR problem, we study its min-k version: Given ε>0, find a feasible solution with the minimum number k ^∗ of unimodal curves for f\bf f with an error ε; its min-ε version: given k>0, compute the minimum error ε ^∗ such that there is a feasible solution with at most k unimodal curves for f\bf f with error ε ^∗. For the FPR problem, we study its min-k version: Given ε>0, find one feasible curve with the minimum number k ^∗ of peaks for f\bf f with an error ε; its min-ε version: given k≥0, compute the minimum error ε ^∗ such that there is a feasible curve with at most k peaks for f\bf f with error ε ^∗. Little work has been done previously on solving these functional curve representation problems. We solve all the problems (except the UR min-ε version) in optimal O(n) time, and the UR min-ε version in O(n+mlog m) time, where m<n is the number of peaks of f\bf f. Our algorithms are based on new geometric observations and interesting techniques.     

Improved approximations of the solution and derivatives to a singularly perturbed reaction-diffusion equation based on the solution decomposition method

In the case of the Dirichlet problem for a singularly perturbed ordinary differential reaction-diffusion equation, a new approach is used to the construction of finite difference schemes such that their solutions and their normalized first- and second-order derivatives converge in the maximum norm uniformly with respect to a perturbation parameter ɛ ∈(0, 1]; the normalized derivatives are ɛ-uniformly bounded. The key idea of this approach to the construction of ɛ-uniformly convergent finite difference schemes is the use of uniform grids for solving grid subproblems for the regular and singular components of the grid solution. Based on the asymptotic construction technique, a scheme of the solution decomposition method is constructed such that its solution and its normalized first- and second-order derivatives converge ɛ-uniformly at the rate of O(N ⁻²ln² N), where N + 1 is the number of points in the uniform grids. Using the Richardson technique, an improved scheme of the solution decomposition method is constructed such that its solution and its normalized first and second derivatives converge ɛ-uniformly in the maximum norm at the same rate of O(N ⁻⁴ln⁴ N).