Stabilization of algebraic multilevel iteration methods; additive methods

There exist two main versions of preconditioners of algebraic multilevel type, the additive and the multiplicative methods. They correspond to preconditioners in block diagonal and block matrix factorized form, respectively. Both can be defined and analysed as recursive two-by-two block methods. Although the analytical framework for such methods is simple, for many finite element approximations it still permits the derivation of the strongest results, such as optimal, or nearly optimal, rate of convergence and optimal, or nearly optimal order of computational complexity, when proper recursive global orderings of node points have been used or when they are applied for hierarchical basis function finite element methods for elliptic self-adjoint equations and stabilized in a certain way. This holds for general elliptic problems of second order, independent of the regularity of the problem, including independence of discontinuities of coefficients between elements and of anisotropy. Important ingredients in the methods are a proper balance of the size of the coarse mesh to the finest mesh and a proper solver on the coarse mesh. This paper presents in a survey form the basic results of such methods and considers in particular additive methods. This method has excellent parallelization properties. This revised version was published online in June 2006 with corrections to the Cover Date.     

多步Runge-Kutta方法关于一类多延迟系统的GPk-稳定性

本文多步Ｒｕｎｇｅ－Ｋｕｔｔａ方法关于延迟微分方程系统的渐近稳定性,在本文中我们证明了在适当条件下常微多步Ｒｕｎｇｅ－Ｋｕｔｔａ方法的Ａ－稳定性等价于相应求解多延迟微分方程系统的ＧＰｋ－稳定性。     

多步Runge-Kutta方法关于一类多延迟系统的GP_k-稳定性(英文)

本文涉及多步 Runge-Kutta方法关于多延迟微分方程系统的渐近稳定性 .在本文中我们证明了在适当条件下常微多步 Runge-Kutta方法的 A-稳定性等价于相应求解多延迟微分方程系统的GPk-稳定性 .     

Non-linear stability of a general class of differential equation methods

For a class of methods sufficiently general as to include linear multistep and Runge-Kutta methods as special cases, a concept known as algebraic stability is defined. This property is based on a non-linear test problem and extends existing results on Runge-Kutta methods and on linear multistep and one-leg methods. The algebraic stability properties of a number of particular methods in these families are studied and a generalization is made which enables estimates of error growth to be provided for certain classes of methods.     

On two classes of nonstandard parabolic problems

In this paper the authors continue an investigation of nonstandard parabolic problems. This investigation was motivated by one of the suggested methods for stabilizing ill posed problems for evolution equations. Two different methods are employed—methods which in a sense complement one another.     

一类适用于非凸函数的非单调共轭梯度法

This paper discusses the global convergence of a class of nonmonotone conjugate gradient methods (NM methods) for nonconvex object functions. This class of methods includes the nonmonotone counterpart of modified Polak-Ribiere method and modified Hestenes-Stiefel method as special cases.     

Construction of two-step Runge-Kutta methods of high order for ordinary differential equations

The construction of two-step Runge-Kutta methods of order p and stage order q=p with stability polynomial given in advance is described. This polynomial is chosen to have a large interval of absolute stability for explicit methods and to be A-stable and L-stable for implicit methods. After satisfying the order and stage order conditions the remaining free parameters are computed by minimizing the sum of squares of the difference between the stability function of the method and a given polynomial at a sufficiently large number of points in the complex plane. This revised version was published online in August 2006 with corrections to the Cover Date.     

On Lanczos Based Methods for the Regularization of Discrete Ill-Posed Problems

We study hybrid methods for the solution of linear ill-posed problems. Hybrid methods are based on he Lanczos process, which yields a sequence of small bidiagonal systems approximating the original ill-posed problem. In a second step, some additional regularization, typically the truncated SVD, is used to stabilize the iteration. We investigate two different hybrid methods and interpret these schemes as well-known projection methods, namely least-squares projection and the dual least-squares method. Numerical results are provided to illustrate the potential of these methods. This gives interesting insight in to the behavior of hybrid methods in practice.This revised version was published online in October 2005 with corrections to the Cover Date.     

Asymptotic behavior of multistep runge-kutta methods for systems of delay differential equations

1. IntroductionIn order to assess the asymptotic behavior of numerical methods for DDEs, much attention has been given in the literature to the scalar case (cL [1-6]). UP to now) only partialresults (of. [7-10]) have dealt with the delay systemswhere y(t) = (yi(t), so(t),' ) yp(t))" E Cd, which is unknown for t > 0, L and M areconstat complex p x Hmatrices, T > 0 is a constat delay and W(t) 6 CP is a specifiedinitial function.In [111, C.J. Zhang and S.Z. Zhou made an investigation on…     

A simple extension of boosting for asymmetric mislabeled data

This letter provides a simple extension of boosting methods for binary data where the probability of mislabeling depends on the label of an example. Loss functions are derived from the statistical perspective, which is based on likelihood analysis. Our proposed methods can be interpreted as a correction of the decision boundary of observed labels. This interpretation partially relates to cost-sensitive learning, a classification method for the case in which the ratio of two labels in a dataset is skewed. Numerical experiments show that the proposed methods work well for asymmetric mislabeled data even when the probabilities of mislabeling may not be precisely specified.     

A review of formal orthogonality in Lanczos-based methods

Krylov subspace methods and their variants are presently the favorite iterative methods for solving a system of linear equations. Although it is a purely linear algebra problem, it can be tackled by the theory of formal orthogonal polynomials. This theory helps to understand the origin of the algorithms for the implementation of Krylov subspace methods and, moreover, the use of formal orthogonal polynomials brings a major simplification in the treatment of some numerical problems related to these algorithms. This paper reviews this approach in the case of Lanczos method and its variants, the novelty being the introduction of a preconditioner.     

Analysis of third-order methods for secular equations

Third-order numerical methods are analyzed for secular equations. These equations arise in several matrix problems and numerical linear algebra applications. A closer look at an existing method shows that it can be considered as a classical method for an equivalent problem. This not only leads to other third-order methods, it also provides the means for a unifying convergence analysis of these methods and for their comparisons. Finally, we consider approximated versions of the aforementioned methods.

     

Exploiting structure in the construction of DIMSIMs

We describe the structure of the nonlinear system for the coefficients of diagonally implicit multistage integration methods for ordinary differential equations. This structure is then utilized in the search for methods of high order and stage order with a given stability function. New methods were obtained by solving the nonlinear systems by state-of-the-art software based on least squares minimization.     

A three-parameter family of nonlinear conjugate gradient methods

In this paper, we propose a three-parameter family of conjugate gradient methods for unconstrained optimization. The three-parameter family of methods not only includes the already existing six practical nonlinear conjugate gradient methods, but subsumes some other families of nonlinear conjugate gradient methods as its subfamilies. With Powell's restart criterion, the three-parameter family of methods with the strong Wolfe line search is shown to ensure the descent property of each search direction. Some general convergence results are also established for the three-parameter family of methods. This paper can also be regarded as a brief review on nonlinear conjugate gradient methods.

     

Families of High-Order Composition Methods

We propose a new rule of thumb for designing high-order composition methods for ODEs: instead of minimizing (some norm of) the principal error coefficients, simply set all the outer stages equal. This rule automatically produces families of minimum error 4th order and corrected 6th order methods, and very good standard 6th order methods, parameterized by the number of stages. Intriguingly, the most accurate methods (evaluated with the total work held fixed) have a very large number of stages.     

数值求解NDDEs系统的单支方法的非线性稳定性

该文探讨了单支方法关于一类中立型延迟微分方程（ＮＤＤＥｓ）系统的整体稳定性和渐近稳定性．在适当的条件下，获得了单支方法关于ＮＤＤＥｓ系统的一些新的非线性稳定性判据．     

一类求解常微分方程数值解的块方法

本文讨论了一类并行计算常微分方程初值问题的带有高阶导数的块隐式混合单步方法，这种方法可以在Ｋ台处理机上并行进行数值计算，本文对方法的一般性质及收敛性进行了讨论，得知该方法的阶数为２ｌ＋１，并且指出当ｌ＝１，２时，方法是Ａ－稳定的，最后给出了一个数值例子。     

空间中的时滞积分微分方程数值方法及其牛顿迭代解的存在唯一性

该文分析了扩展的一般线性方法关于Banach 空间中一类时滞积分微分方程数值解的可解性, 给出了其方法的解的存在唯一性判据, 并探讨了其Newton迭代解的性态. 所获结果可应用于扩展的Runge-Kutta方法和扩展的线性多步方法等.     

Some computational methods for systems of nonlinear equations and systems of polynomial equations

This paper gives a brief survey and assessment of computational methods for finding solutions to systems of nonlinear equations and systems of polynomial equations. Starting from methods which converge locally and which find one solution, we progress to methods which are globally convergent and find an a priori determinable number of solutions. We will concentrate on simplicial algorithms and homotopy methods. Enhancements of published methods are included and further developments are discussed.     

Stability of spline approximation methods for multidimensional pseudodifferential operators

The present paper provides stability considerations of spline approximation methods for multidimensional singular operators. This paper should be regarded as a first step in establishing spline approximation methods for pseudodifferential operators on manifolds.