Estimation of optimal backward perturbation bounds for the linear least squares problem

In this paper a method of estimating the optimal backward perturbation bound for the linear least squares problem is presented. In contrast with the optimal bound, which requires a singular value decomposition, this method is better suited for practical use on large problems since it requiresO(mn) operations. The method presented involves the computation of a strict lower bound for the spectral norm and a strict upper bound for the Frobenius norm which gives a gap in which the optimal bounds for the spectral and the Frobenius norm must be. Numerical tests are performed showing that this method produces an efficient estimate of the optimal backward perturbation bound.     

Distribution of zeta zeros and the oscillation of the error term of the prime number theorem

An 84-year-old classical result of Ingham states that a rather general zero-free region of the Riemann zeta function implies an upper bound for the absolute value of the remainder term of the prime number theorem. In 1950 Tur´an proved a partial conversion of the mentioned theorem of Ingham. Later the author proved sharper forms of both Ingham’s theorem and its conversion by Tur´an. The present work shows a very general theorem which describes the average and the maximal order of the error terms by a relatively simple function of the distribution of the zeta zeros. It is proved that the maximal term in the explicit formula of the remainder term coincides with high accuracy with the average and maximal order of the error term.     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

Stability Property in Bifunction-Set Optimization

This paper gives sufficient conditions for the lower and upper semicontinuities of the solution mapping of a model, called the parametric bifunction-set optimization problem, which provides a bridge between several parametric set optimization problems and parametric generalized vector Ky Fan inequality problems. Our main theorems, applied to the just mentioned problems, give some new or sharper results.     

Learning errors of linear programming support vector regression

In this paper, we give several results of learning errors for linear programming support vector regression. The corresponding theorems are proved in the reproducing kernel Hilbert space. With the covering number, the approximation property and the capacity of the reproducing kernel Hilbert space are measured. The obtained result (Theorem 2.1) shows that the learning error can be controlled by the sample error and regularization error. The mentioned sample error is summarized by the errors of learning regression function and regularizing function in the reproducing kernel Hilbert space. After estimating the generalization error of learning regression function (Theorem 2.2), the upper bound (Theorem 2.3) of the regularized learning algorithm associated with linear programming support vector regression is estimated.     

On the Meany inequality with applications to convergence analysis of several row-action iteration methods

The Meany inequality gives an upper bound in the Euclidean norm for a product of rank-one projection matrices. In this paper we further derive a lower bound related to this inequality. We discuss the internal relationship between the upper bounds given by the Meany inequality and by the inequality in Smith et al. (Bull Am Math Soc 83:1227–1270, 1977) in the finite dimensional real linear space. We also generalize the Meany inequality to the block case. In addition, by making use of the block Meany inequality, we improve existing results and establish new convergence theorems for row-action iteration schemes such as the block Kaczmarz and the Householder–Bauer methods used to solve large linear systems and least-squares problems.     

Preconditioning waveform relaxation iterations for differential systems

We discuss preconditioning and overlapping of waveform relaxation methods for sparse linear differential systems. It is demonstrated that these techniques significantly improve the speed of convergence of the waveform relaxation iterations resulting from application of various modes of block Gauss-Jacobi and block Gauss-Seidel methods to differential systems. Numerical results are presented for linear systems resulting from semi-discretization of the heat equation in one and two space variables. It turns out that overlapping is very effective for the system corresponding to the one-dimensional heat equation and preconditioning is very effective for the system corresponding to the two-dimensional case.The work of the second author was supported by the National Science Foundation under grant NSF DMS 92-08048.     

Liminf results on the increments of an (N,d)-Gaussian process

We establish some liminf theorems on the increments of a (N,d)-Gaussian process with the usual Euclidean norm, via estimating upper bounds of large deviation probabilities on the suprema of the (N,d)-Gaussian process. This revised version was published online in June 2006 with corrections to the Cover Date.     

一簇Lorenz映射的混沌行为的符号动力学分析

首先从符号动力学的角度论证了一簇Lorenz映射且有的混沌性质:稠密的周期轨道,周期的集合,拓扑熵,几乎所有(关于Lebesgue测度)的点的Lyapunov指数;并从揉序列的分析给出了该簇映射的拓扑熵的一个下界及Lyapunov指数的一个下界与上界,在很大程度上反应了Lorenz系统的复杂程度.其次仍从符号动力学的角度论证了更一般的Lorenz映射,通过设立参数空间,穷尽了Lorenz映射中函数为直线段的所有情况,并得出同前述Lorenz映射相似的且较为复杂的性质.     

Eigenvalue estimates for minimal surfaces in hyperbolic space

This paper gives an upper bound for the first eigenvalue of the universal cover of a complete, stable minimal surface in hyperbolic space, and a sharper one for least area disks.

     

Analysis of a subdomain‐based error estimator for finite element approximations of elliptic problems

In this article we analyze a subdomain residual error estimator for finite element approximations of elliptic problems. It is obtained by solving local problems on patches of elements in weighted spaces and provides an upper bound on the energy norm of the error when the local problems are solved in sufficiently enriched discrete spaces. A guaranteed lower bound on the error is also derived by a simple postprocess of the solutions to the local problems. Numerical tests show very good effectivity indices for both the upper and lower bounds and a strong reliability of this estimator even for coarse meshes. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 165–192, 2004     

Distribution function estimates by Wasserstein metric and Bernstein approximation for C-1 functions

The aim of the paper is to estimate the density functions or distribution functions measured by Wasserstein metric, a typical kind of statistical distances, which is usually required in the statistical learningBased on the classical Bernstein approximation, a scheme is presented.To get the error estimates of the scheme, the problem turns to estimating the L1 norm of the Bernstein approximation for monotone C-1functions, which was rarely discussed in the classical approximation theoryFinally, we get a probability estimate by the statistical distance.     

Error growth analysis via stability regions for discretizations of initial value problems

This paper deals with numerical methods for the solution of linear initial value problems. Two main theorems are presented on the stability of these methods. Both theorems give conditions guaranteeing a mild error growth, for one-step methods characterized by a rational function ϕ(z). The conditions are related to the stability regionS={z:z∈ℂ with |ϕ(z)|≤1}, and can be viewed as variants to the resolvent condition occurring in the reputed Kreiss matrix theorem. Stability estimates are presented in terms of the number of time stepsn and the dimensions of the space. The first theorem gives a stability estimate which implies that errors in the numerical process cannot grow faster than linearly withs orn. It improves previous results in the literature where various restrictions were imposed onS and ϕ(z), including ϕ′(z)≠0 forz∈σS andS be bounded. The new theorem is not subject to any of these restrictions. The second theorem gives a sharper stability result under additional assumptions regarding the differential equation. This result implies that errors cannot grow faster thann ^β, with fixed β<1. The theory is illustrated in the numerical solution of an initial-boundary value problem for a partial differential equation, where the error growth is measured in the maximum norm.     

Relaxation Time for the Discrete D/G/1 Queue

When queueing models are used for performance analysis of some stochastic system, it is usually assumed that the system is in steady-state. Whether or not this is a realistic assumption depends on the speed at which the system tends to its steady-state. A characterization of this speed is known in the queueing literature as relaxation time.The discrete D/G/1 queue has a wide range of applications. We derive relaxation time asymptotics for the discrete D/G/1 queue in a purely analytical way, mostly relying on the saddle point method. We present a simple and useful approximate upper bound which is sharp in case the load on the system is not very high. A sharpening of this upper bound, which involves the complementary error function, is then developed and this covers both the cases of low and high loads.For the discrete D/G/1 queue, the stationary waiting time distribution can be expressed in terms of infinite series that follow from Spitzer’s identity. These series involve convolutions of the probability distribution of a discrete random variable, which makes them suitable for computation. For practical purposes, though, the infinite series should be truncated. The relaxation time asymptotics can be applied to determine an appropriate truncation level based on a sharp estimate of the error caused by truncating.This revised version was published online in June 2005 with corrected coverdate     

Analysis of a new parareal algorithm based on waveform relaxation method for time-periodic problems

We present a new parallel algorithm for time-periodic problems by combining the waveform relaxation method and the parareal algorithm, which performs the parallelism both in sub-systems and in time. In the new algorithm, the waveform relaxation propagator is chosen as a new fine propagator instead of the classical fine propagator. And because of the characteristic of time-periodic problems, the new parareal waveform relaxation algorithm needs to solve a periodic coarse problem at the coarse level in each iteration. The new algorithm is proved to converge linearly at most. Then the theoretic parallel efficiency of the new algorithm is also considered. Numerical experiments confirm our analysis finally.     

A bilinear inequality

We establish an inequality for symmetric bilinear forms involving both the norm and the inner product of vectors. We use the inequality to convert known inequalities in real Hilbert spaces such as classical Hilbert's inequality to sharper inequalities.     

On the total curvature of curves in a Minkowski space

We consider simple closed curves in a Minkowski space. We give bounds of the total Minkowski curvature of the curve in terms of the total Euclidean curvature and of normal curvatures on the indicatrix (supposed to be a central symmetric hypersurface) of the Minkowski norm. Corollaries of this result provide analogues to Fenchel and Fary-Milnor theorems. We also give an upper bound of the Minkowski length of a simple closed curve contained in a Minkowski ball of radius R, in terms of the total Minkowski curvature and of normal curvatures on the indicatrix. Whenever the Minkowski space is Euclidean our results reduce to the classical ones.     

Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

The Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods are nonoverlapping spatial domain decomposition methods to solve evolution problems, while the parareal algorithm is in time parallel fashion. Based on the combinations of these space and time parallel strategies, we present and analyze two parareal algorithms based on the Dirichlet-Neumann and the Neumann-Neumann waveform relaxation method for the heat equation by choosing Dirichlet-Neumann/Neumann-Neumann waveform relaxation as two new kinds of fine propagators instead of the classical fine propagator. Both new proposed algorithms could be viewed as a space-time parallel algorithm, which increases the parallelism both in space and in time. We derive for the heat equation the convergence results for both algorithms in one spatial dimension. We also illustrate our theoretical results with numerical experiments finally.

     

On nonlinear difference and differential equations

A generalization of the logarithmic norm to nonlinear operators, the Dahlquist constant is introduced as a useful tool for the estimation and analysis of error propagation in general nonlinear first-order ODE's. It is a counterpart to the Lipschitz constant which has similar applications to difference equations. While Lipschitz constants can also be used for ODE's, estimates based on the Dahlquist constant always give sharper results.The analogy between difference and differential equations is investigated, and some existence and uniqueness results for nonlinear (algebraic) equations are given. We finally apply the formalism to the implicit Euler method, deriving a rigorous global error bound for stiff nonlinear problems.Dedicated to my teacher and friend, Professor Germund Dahlquist, on the occasion of his 60th birthday.     

Waveform relaxation for fractional sub-diffusion equations

Numerical Algorithms - We report a new kind of waveform relaxation (WR) method for general semi-linear fractional sub-diffusion equations, and analyze the upper bound for the iteration errors. It...