BiCGstab(l) and other hybrid Bi-CG methods

It is well-known that Bi-CG can be adapted so that the operations withA ^T can be avoided, and hybrid methods can be constructed in which it is attempted to further improve the convergence behaviour. Examples of this are CGS, Bi-CGSTAB, and the more general BiCGstab(l) method. In this paper it is shown that BiCGstab(l) can be implemented in different ways. Each of the suggested approaches has its own advantages and disadvantages. Our implementations allow for combinations of Bi-CG with arbitrary polynomial methods. The choice for a specific implementation can also be made for reasons of numerical stability. This aspect receives much attention. Various effects have been illustrated by numerical examples.     

Variants of the groupwise update strategy for short-recurrence Krylov subspace methods

Krylov subspace methods often use short-recurrences for updating approximations and the corresponding residuals. In the bi-conjugate gradient (Bi-CG) type methods, rounding errors arising from the matrix–vector multiplications used in the recursion formulas influence the convergence speed and the maximum attainable accuracy of the approximate solutions. The strategy of a groupwise update has been proposed for improving the convergence of the Bi-CG type methods in finite-precision arithmetic. In the present paper, we analyze the influence of rounding errors on the convergence properties when using alternative recursion formulas, such as those used in the bi-conjugate residual (Bi-CR) method, which are different from those used in the Bi-CG type methods. We also propose variants of a groupwise update strategy for improving the convergence speed and the accuracy of the approximate solutions. Numerical experiments demonstrate the effectiveness of the proposed method.     

Approximate Newton Methods for Nonsmooth Equations

We develop general approximate Newton methods for solving Lipschitz continuous equations by replacing the iteration matrix with a consistently approximated Jacobian, thereby reducing the computation in the generalized Newton method. Locally superlinear convergence results are presented under moderate assumptions. To construct a consistently approximated Jacobian, we introduce two main methods: the classic difference approximation method and the -generalized Jacobian method. The former can be applied to problems with specific structures, while the latter is expected to work well for general problems. Numerical tests show that the two methods are efficient. Finally, a norm-reducing technique for the global convergence of the generalized Newton method is briefly discussed.     

An extension of the conjugate residual method to nonsymmetric linear systems

The Conjugate Gradient (CG) method and the Conjugate Residual (CR) method are Krylov subspace methods for solving symmetric (positive definite) linear systems. To solve nonsymmetric linear systems, the Bi-Conjugate Gradient (Bi-CG) method has been proposed as an extension of CG. Bi-CG has attractive short-term recurrences, and it is the basis for the successful variants such as Bi-CGSTAB. In this paper, we extend CR to nonsymmetric linear systems with the aim of finding an alternative basic solver. Numerical experiments show that the resulting algorithm with short-term recurrences often gives smoother convergence behavior than Bi-CG. Hence, it may take the place of Bi-CG for the successful variants.     

On the variational convergence of non-coercive quadratic integral functionals and semicontinuity problems

In this paper we give some results about convergence of non coercive quadratic integral functionals by examining the behaviour of coefficients. We apply our results to semicontinuity problems and we illustrate them by some examples.AMS Subject Classification: 40A10, 49J45.     

On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form

In this paper, we will compare the convergence properties of three basic reduction methods, by placing them in a general framework. It covers the reduction to tridiagonal, semiseparable and semiseparable plus diagonal form. These reductions are often used as the first step in the computation of the eigenvalues and/or eigenvectors of arbitrary matrices. In this way, the calculation of the eigenvalues using, for example, the QR-algorithm reduces in complexity. First we will investigate the convergence properties of these three reduction algorithms. It will be shown that for the partially reduced matrices at step k of any of these reduction algorithms, the lower right k × k (already reduced) sub-block will have the Lanczos–Ritz values, w.r.t. a certain starting vector. It will also be shown that the reductions to semiseparable and to semiseparable plus diagonal form have an extra convergence behavior a special type of subspace iteration is performed on the lower right k × k submatrix, which contains these Ritz-values. Secondly we look in more detail at the behavior of the involved subspace iteration. It will be shown that the reduction method can be interpreted as a nested type of multi-shift iteration. Theoretical results will be presented, making it possible to predict the convergence behavior of these reduction algorithms. Also a theoretical bound on the convergence rate is presented. Finally we illustrate by means of numerical examples, how it is possible to tune the convergence behavior such that it can become a powerful tool for certain applications.     

求非线性方程组和优化问题全部解的胞腔方法

求非线性方程组和优化问题全部解的胞腔方法张讲社，游兆永，徐宗本（西安交通大学数学系）ＡＣＥＬＬＭＥＴＨＯＤＦＯＲＦＩＮＤＩＮＧＡＬＬＳＯＬＵＴＩＯＮＳＯＦＮＯＮＬＩＮＥＡＲＥＱＵＡＴＩＯＮＳＡＮＤＯＰＴＩＭＩＺＡＴＩＯＮＰＲＯＢＬＥＭＳ￥ＺｈａｎｇＪ...     

Strong Laws and Summability for φ-Mixing Sequences of Random Variables

In this note the almost sure convergence of stationary, -mixing sequences of random variables according to summability methods is linked to the fulfillment of a certain integrability condition generalizing and extending the results for i.i.d. sequences. Furthermore we give via Baum-Katz type results an estimate for the rate of convergence in these laws.     

Newton’s method’s basin of attraction for sign-changing solutions of concave and convex nonlinearities

In this paper, we will illustrate and visualize the chaotic behavior for solving the sign-changing solutions of concave-convex nonlinearities. We propose contractor iteration algorithm and bifurcation method to improve the computation speed and avoid local convergence of Newton-Raphson method. By this method, sign-changing numerical solutions will be computed and visualized in various domains.     

影响阻尼牛顿法收敛性的两个重要参数

对阻尼牛顿算法作了适当的改进,证明了新算法的收敛性.基于新算法,运用计算机代数系统Matlab,研究了迭代次数k,参数对(μ,λ)与初值x0三者间的依赖关系,研究了病态问题在新算法下趋于稳定的渐变(瞬变)过程.数值结果表明:(1)阻尼牛顿迭代中,参数对(μ,λ)与迭代次数k间存在特有的非线性关系;(2)适当的参数对(μ,λ)与阻尼因子α的共同作用能够在迭代中大幅度地降低病态问题的Jacobi阵的条件数,使病态问题逐渐趋于稳定,从而改变原问题的收敛性与收敛速度.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

Two CSCS-based iteration methods for solving absolute value equations

Recently, two families of HSS-based iteration methods are constructed for solving the system of absolute value equations (AVEs), which is a class of non-differentiable NP-hard problems. In this study, we establish the Picard-CSCS iteration method and the nonlinear CSCS-like iteration method for AVEs involving the Toeplitz matrix. Then, we analyze the convergence of the Picard-CSCS iteration method for solving AVEs. By using the theory about nonsmooth analysis, we particularly prove the convergence of the nonlinear CSCS-like iteration solver for AVEs. The advantage of these methods is that they do not require the storage of coefficient matrices at all, and the sub-system of linear equations can be solved efficiently via the fast Fourier transforms (FFTs). Therefore, computational cost and storage can be saved in practical implementations. Numerical examples including numerical solutions of nonlinear fractional diffusion equations are reported to show the effectiveness of the proposed methods in comparison with some existing methods.     

Schrodinger方程的变分迭代解法

该文以Ｓｃｈｒｏｄｉｎｇｅｒ方程为例,分析变分迭代法的一些基本特点．在该方法中引进了一广义拉氏乘子构造了一迭代格式,拉氏乘子可由变分理论最佳识别．由于在识别拉氏乘子是应用了限制变分的概念,所以只能通过迭代才能得到收敛解．为了加快收敛速度,可以在初始近似引入待定常数,而待定常数又可用各种方式最佳识别．文中初步分析了该方法的收敛性,对于Ｓｃｈｒｏｄｉｎｇｅｒ方程,其一阶近似即可得到Ｊｏｓｔ解．     

Convergence Analysis of the Dirichlet-Neumann Iteration for Finite Element Discretizations

We analyze the convergence rate of the Dirichlet-Neumann iteration for the fully discretized unsteady transmission problem. Specifically, we consider the coupling of two linear heat equations on two identical non overlapping domains with jumps in the material coefficients across these. In this context, we derive the iteration matrix of the coupled problem. In the 1D case, the spectral radius of the iteration matrix tends to the ratio of heat conductivities in the semidiscrete spatial limit, but to the ratio of the products of density and specific heat capacity in the semidiscrete temporal one. This explains the fast convergence previously observed for cases with strong jumps in the material coefficients. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Matrix approaches to approximate solutions of variational inequalities in Hilbert spaces

A matrix approach to approximating solutions of variational inequalities in Hilbert spaces is introduced. This approach uses two matrices: one for iteration process and the other for regularization. Ergodicity and convergence (both weak and strong) are studied. Our methods combine new or well-known iterative methods (such as the original Mann’s method) with regularized processes involved regular matrices in the sense of Toeplitz.     

On inexact Newton methods based on doubling iteration scheme for non‐symmetric algebraic Riccati equations

Newton iteration method can be used to find the minimal non‐negative solution of a certain class of non‐symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non‐symmetric algebraic Riccati equations. Copyright © 2010 John Wiley & Sons, Ltd.     

Waveform relaxation methods for implicit differential equations

We apply a Runge-Kutta-based waveform relaxation method to initial-value problems for implicit differential equations. In the implementation of such methods, a sequence of nonlinear systems has to be solved iteratively in each step of the integration process. The size of these systems increases linearly with the number of stages of the underlying Runge-Kutta method, resulting in high linear algebra costs in the iterative process for high-order Runge-Kutta methods. In our earlier investigations of iterative solvers for implicit initial-value problems, we designed an iteration method in which the linear algebra costs are almost independent of the number of stages when implemented on a parallel computer system. In this paper, we use this parallel iteration process in the Runge-Kutta waveform relaxation method. In particular, we analyse the convergence of the method. The theoretical results are illustrated by a few numerical examples.     

A boundary element method for the Dirichlet eigenvalue problem of the Laplace operator

The solution of eigenvalue problems for partial differential operators by using boundary integral equation methods usually involves some Newton potentials which may be resolved by using a multiple reciprocity approach. Here we propose an alternative approach which is in some sense equivalent to the above. Instead of a linear eigenvalue problem for the partial differential operator we consider a nonlinear eigenvalue problem for an associated boundary integral operator. This nonlinear eigenvalue problem can be solved by using some appropriate iterative scheme, here we will consider a Newton scheme. We will discuss the convergence and the boundary element discretization of this algorithm, and give some numerical results.     

On HSS-based iteration methods for weakly nonlinear systems

Based on separable property of the linear and the nonlinear terms and on the Hermitian and skew-Hermitian splitting of the coefficient matrix, we present the Picard-HSS and the nonlinear HSS-like iteration methods for solving a class of large scale systems of weakly nonlinear equations. The advantage of these methods over the Newton and the Newton-HSS iteration methods is that they do not require explicit construction and accurate computation of the Jacobian matrix, and only need to solve linear sub-systems of constant coefficient matrices. Hence, computational workloads and computer memory may be saved in actual implementations. Under suitable conditions, we establish local convergence theorems for both Picard-HSS and nonlinear HSS-like iteration methods. Numerical implementations show that both Picard-HSS and nonlinear HSS-like iteration methods are feasible, effective, and robust nonlinear solvers for this class of large scale systems of weakly nonlinear equations.     

A coupling of FEM-BEM for a kind of Signorini contact problem

In this paper, we consider a kind of coupled nonlinear problem with Signorini contact conditions. To solve this problem, we discuss a new coupling of finite element and boundary element by adding an auxiliary circle. We first derive an asymptotic error estimate of the approximation to the coupled FEM-BEM variational inequality. Then we design an iterative method for solving the coupled system, in which only three standard subproblems without involving any boundary integral equation are solved. It will be shown that the convergence speed of this iteration method is independent of the mesh size.