指标-2微分-代数系统的连续扩展Runge-Kutta迭代方法

1引言微分-代数系统包括具有约束条件的微分方程和奇异隐式微分方程,在实际应用中,如:约束力学系统、流体动力学、化学反应动力学、电子网络模拟、控制工程和机器人技术等领域就产生了诸多问题需要求解．近年来,微分-代数系统已极大地引起了许多工程师和数学工作者的关注,开展了众多相关问题的探讨,提出了许多新的算法理论[1-3]．在本文中我们对指标-2的微分-代数方程利用Runge-Kutta方法进行时间的离散和动力学迭代,研究离散迭代系统的收敛性．     

A note on the convergence of an inertial version of a diagonal hybrid projection-point algorithm

In this note, an inertial and relaxed version of a diagonal hybrid projection-proximal point algorithm is considered, in order to find the minimum of a function f approximated by a sequence of functions (in general, smoother than f or taking into account some constraints of the problem). Two convergence theorems are proved under different kind of assumptions, which allows to apply the method in various cases.     

Optimal convergence for the finite element method in Campanato spaces

We prove a priori estimates and optimal error estimates for linear finite element approximations of elliptic systems in divergence form with continuous coefficients in Campanato spaces. The proofs rely on discrete analogues of the Campanato inequalities for the solution of the system, which locally measure the decay of the energy. As an application of our results we derive -estimates and give a new proof of the well-known -results of Rannacher and Scott.

     

A note on the efficient implementation of Hamiltonian BVMs

We discuss the efficient implementation of Hamiltonian BVMs (HBVMs), a recently introduced class of energy preserving methods for canonical Hamiltonian systems (see Brugnano et al. [8] and references therein), also sketching their blended formulation. We also discuss the case of separable problems, for which the structure of the problem can be exploited to gain efficiency.     

A family of ELLAM schemes for advection-diffusion-reaction equations and their convergence analyses

A family of ELLAM (Eulerian–Lagrangian localized adjoint method) schemes is developed and analyzed for linear advection-diffusion-reaction transport partial differential equations with any combination of inflow and outflow Dirichlet, Neumann, or flux boundary conditions. The formulation uses space-time finite elements, with edges oriented along Lagrangian flow paths, in a time–stepping procedure, where space-time test functions are chosen to satisfy a local adjoint condition. This allows Eulerian–Lagrangian concepts to be applied in a systematic mass-conservative manner, yielding numerical schemes defined at each discrete time level. Optimal-order error estimates and superconvergence results are derived. Numerical experiments are performed to verify the theoretical estimates. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 739–780, 1998     

On the convergence of higher-order orthogonal iteration

The higher-order orthogonal iteration (HOOI) has been popularly used for finding a best low-multilinear rank approximation of a tensor. However, its convergence is still an open question. In this paper, we first analyse a greedy HOOI, which updates each factor matrix by selecting from the best candidates one that is closest to the current iterate. Assuming the existence of a block-nondegenerate cluster point, we establish its global iterate sequence convergence through the so-called Kurdyka–?ojasiewicz property. In addition, we show that if the starting point is sufficiently close to any block-nondegenerate globally optimal solution, the greedy HOOI produces an iterate sequence convergent to a globally optimal solution. Relating the iterate sequence by the original HOOI to that by the greedy HOOI, we then show that the original HOOI has global convergence on the multilinear subspace sequence and thus positively address the open question.     

Parallel iteration across the steps of high-order Runge-Kutta methods for nonstiff initial value problems

For the parallel integration of nonstiff initial value problems (IVPs), three main approaches can be distinguished: approaches based on “parallelism across the problem”, on “parallelism across the method” and on “parallelism across the steps”. The first type of parallelism does not require special integration methods and can be exploited within any available IVP solver. The method-parallelism approach received much attention, particularly within the class of explicit Runge-Kutta methods originating from fixed point iteration of implicit Runge-Kutta methods of Gaussian type. The construction and implementation on a parallel machine of such methods is extremely simple. Since the computational work per processor is modest with respect to the number of data to be exchanged between the various processors, this type of parallelism is most suitable for shared memory systems. The required number of processors is roughly half the order of the generating Runge-Kutta method and the speed-up with respect to a good sequential IVP solver is about a factor 2. The third type of parallelism (step-parallelism) can be achieved in any IVP solver based on predictor-corrector iteration and requires the processors to communicate after each full iteration. If the iterations have sufficient computational volume, then the step-parallel approach may be suitable for implementation on distributed memory systems. Most step-parallel methods proposed so far employ a large number of processors, but lack the property of robustness, due to a poor convergence behaviour in the iteration process. Hence, the effective speed-up is rather poor. The dynamic step-parallel iteration process proposed in the present paper is less massively parallel, but turns out to be sufficiently robust to achieve speed-up factors up to 15.     

On the convergence of policy iteration for controlled diffusions

The convergence of an approximation scheme known as policy iteration has been demonstrated for controlled diffusions by Fleming, Puterman, and Bismut. In this paper, we show that this approximation scheme is equivalent to the Newton-Kantorovich iteration for solving the optimality equation and exploit this equivalence to obtain a new proof of convergence. Estimates of the rate of convergence of this procedure are also obtained.This research was partially supported by NRC Grant No. A-3609.     

On the convergence of the iteration sequence in primal-dual interior-point methods

Recently, numerous research efforts, most of them concerned with superlinear convergence of the duality gap sequence to zero in the Kojima—Mizuno—Yoshise primal-dual interior-point method for linear programming, have as a primary assumption the convergence of the iteration sequence. Yet, except for the case of nondegeneracy (uniqueness of solution), the convergence of the iteration sequence has been an important open question now for some time. In this work we demonstrate that for general problems, under slightly stronger assumptions than those needed for superlinear convergence of the duality gap sequence (except of course the assumption that the iteration sequence converges), the iteration sequence converges. Hence, we have not only established convergence of the iteration sequence for an important class of problems, but have demonstrated that the assumption that the iteration sequence converges is redundant in many of the above mentioned works.This research was supported in part by NSF Coop. Agr. No. CCR-8809615. A part of this research was performed in June, 1991 while the second and the third authors were at Rice University as visiting members of the Center for Research in Parallel Computation.Corresponding author. Research supported in part by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Research supported in part by NSF DMS-9102761 and DOE DE-FG05-91ER25100.Research supported in part by NSF DDM-8922636.     

Increasing efficiency of inverse iteration

Inverse iteration is simple but not very efficient method for computing few eigenvalues with minimal absolute values and corresponding eigenvectors of a symmetric matrix. The idea is to increase its efficiency by technique similar to multigrid methods used for solving linear systems. This approach is not new, but until now multigrid was mostly used for solving linear system which appear in Rayleigh quotient iteration, inverse iteration and related iterative methods. Instead of choosing appropriate coordinates (grids), our algorithm performs inverse iteration on a sequence of subspaces with decreasing dimensions (multispace). Block Lanczos method is used for the selection of a smaller subspace. This will produce a banded matrix, which makes inverse iteration even faster in the smaller dimensions.      

A K-step look-ahead analysis of value iteration algorithms for Markov decision processes

We introduce and analyze a general look-ahead approach for Value Iteration Algorithms used in solving both discounted and undiscounted Markov decision processes. This approach, based on the value-oriented concept interwoven with multiple adaptive relaxation factors, leads to accelerating procedures which perform better than the separate use of either the concept of value oriented or of relaxation. Evaluation and computational considerations of this method are discussed, practical guidelines for implementation are suggested and the suitability of enhancing the method by incorporating Phase 0, Action Elimination procedures and Parallel Processing is indicated. The method was successfully applied to several real problems. We present some numerical results which support the superiority of the developed approach, particularly for undiscounted cases, over other Value Iteration variants.     

Hansen Patrick迭代的局部收敛性

讨论了Hansen-Patrick迭代的局部特征关系式,引入函数T（t),利用逐步归纳技巧,证明了在α为一定条件下Hansen-Patrick迭代过程对方程f(z)=0零点的局部收敛性。     

A note on the convergence of the MSMAOR method for linear complementarity problems

Modulus‐based splitting, as well as multisplitting iteration methods, for linear complementarity problems are developed by Zhong‐Zhi Bai. In related papers (see Bai, Z.‐Z., Zhang, L.‐L.: Modulus‐Based Synchronous Multisplitting Iteration Methods for Linear Complementarity Problems. Numerical Linear Algebra with Applications 20 (2013) 425–439, and the references cited therein), the problem of convergence for two‐parameter relaxation methods (accelerated overrelaxation‐type methods) is analyzed under the assumption that one parameter is greater than the other. Here, we will show how we can avoid this assumption and, consequently, improve the convergence area. Copyright © 2013 John Wiley & Sons, Ltd.     

Lower bound for the convergence rate of nonstationary Jacobi-like iteration

Stationary and nonstationary Jacobi-like iterative processes for solving systems of linear algebraic equations are examined. For a system whose coefficient matrix A is an H-matrix, it is shown that the convergence rate of any Jacobi-like process is at least as high as that of the point Jacobi method as applied to a system with 〈A〉 as the coefficient matrix, where 〈A〉 is a comparison matrix of A.     

A convergence analysis of an inexact Newton-Landweber iteration method for nonlinear problem

In this paper, we study the convergence and the convergence rates of an inexact Newton–Landweber iteration method for solving nonlinear inverse problems in Banach spaces. Opposed to the traditional methods, we analyze an inexact Newton–Landweber iteration depending on the Hölder continuity of the inverse mapping when the data are not contaminated by noise. With the namely Hölder-type stability and the Lipschitz continuity of DF, we prove convergence and monotonicity of the residuals defined by the sequence induced by the iteration. Finally, we discuss the convergence rates.     

Abstract estimates of the rate of convergence for optimal control problems

A method for solving optimal control problems with general elliptic operators is presented and analyzed. Especially, estimates of the rate of convergence for the control problems with the proposed approach are derived independently of the underlying approximation method. Some numerical experiments with the proposed method are included.     

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.     

Accelerating the convergence of value iteration by using partial transition functions

This work proposes an algorithm that makes use of partial information to improve the convergence properties of the value iteration algorithm in terms of the overall computational complexity. The algorithm iterates on a series of increasingly refined approximate models that converges to the true model according to an optimal linear rate, which coincides with the convergence rate of the original value iteration algorithm. The paper investigates the properties of the proposed algorithm and features a series of switchover queue examples which illustrates the efficacy of the method.     

The necessary and sufficient condition for the convergence of Ishikawa iteration on an arbitrary interval

As an important iteration, the Mann and Ishikawa iteration has extensive application in fixed point theory. In 1991, David Borwein and Jonathan Borwein proved the convergence of the Mann iteration on a closed bounded interval in their paper. In this paper, we will extend their result to an arbitrary interval and to the Ishikawa iteration, indicating the necessary and sufficient condition for the convergence of Ishikawa iteration of continuous functions on an arbitrary interval.