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.     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.     

A diffusion equation in transparent media

In this paper we study the homogeneous relativistic heat equation (HRHE) obtained as asymptotic limit of the so-called relativistic heat equation (RHE) when the kinematic viscosity ν → ∞. These equations were introduced in the theory of radiation hydrodynamics to guarantee a bounded speed of propagation of radiating energy. We shall prove that this is indeed true, and we shall construct some explicit solutions of the HRHE exhibiting fronts propagating at light speed.     

Construction of Newton-like iteration methods for solving nonlinear equations

In this paper, we present a simple, and yet powerful and easily applicable scheme in constructing the Newton-like iteration formulae for the computation of the solutions of nonlinear equations. The new scheme is based on the homotopy analysis method applied to equations in general form equivalent to the nonlinear equations. It provides a tool to develop new Newton-like iteration methods or to improve the existing iteration methods which contains the well-known Newton iteration formula in logic; those all improve the Newton method. The orders of convergence and corresponding error equations of the obtained iteration formulae are derived analytically or with the help of Maple. Some numerical tests are given to support the theory developed in this paper.     

The exponential function rational expansion method and exact solutions to nonlinear lattice equations system

We propose an exponential function rational expansion method for solving exact traveling wave solutions to nonlinear differential-difference equations system. By this method, we obtain some exact traveling wave solutions to the relativistic Toda lattice equations system and discuss the significance of these solutions. Finally, we give an open problem.     

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.     

关于具优势对称部分的不定线性代数方程组的分裂极小残量算法

１．引 言 考虑大型稀疏线性代数方程组 为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销，Ｋｒｙｌｏｖ子空间迭代算法［１，１６，２３］及其预处理变型［６，８，１３，１８，１９］通常是求解（１）的有效而实用的方法．当系数矩阵对称正定时，共轭梯度法（ＣＧ（     

Risk-averse dynamic programming for Markov decision processes

We introduce the concept of a Markov risk measure and we use it to formulate risk-averse control problems for two Markov decision models: a finite horizon model and a discounted infinite horizon model. For both models we derive risk-averse dynamic programming equations and a value iteration method. For the infinite horizon problem we develop a risk-averse policy iteration method and we prove its convergence. We also propose a version of the Newton method to solve a nonsmooth equation arising in the policy iteration method and we prove its global convergence. Finally, we discuss relations to min–max Markov decision models.     

On the convergence of He's variational iteration method

In this work we will consider He's variational iteration method for solving second-order initial value problems. We will discuss the use of this approach for solving several important partial differential equations. This method is based on the use of Lagrange multipliers for identification of optimal value of a parameter in a functional. This procedure is a powerful tool for solving the large amount of problems. Using the variational iteration method, it is possible to find the exact solution or an approximate solution of the problem. This technique provides a sequence of functions which converges to the exact solution of the problem. Our emphasis will be on the convergence of the variational iteration method. In the current paper this scheme will be investigated in details and efficiency of the approach will be shown by applying the procedure on several interesting and important models.     

Asynchronous multisplitting iteration with different weighting schemes

The multisplitting iteration method was presented by O’Leary and White [5] for solving large sparse linear systems on parallel multiprocessor system. In this paper, we further set up an asynchronous variant for the multisplitting iteration method with different weighting schemes studied by White [8]. Moreover, we establish a general convergence criterion for asynchronous iteration framework, and then prove the convergence of the new asynchronous multisplitting iteration method with different weighting schemes by making use of this general criterion.     

A class of two‐stage iterative methods for systems of weakly nonlinear equations

The discretizations of many differential equations by the finite difference or the finite element methods can often result in a class of system of weakly nonlinear equations. In this paper, by applying the two-tage iteration technique and in accordance with the special properties of this weakly nonlinear system, we first propose a general two-tage iterative method through the two-tage splitting of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a two-tage AOR method, which particularly uses the AOR iteration as the inner iteration and is substantially a relaxed variant of the afore-presented method. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only B-differentiable. When the system matrix is either a monotone matrix or an H-matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new two-tage iteration methods, and investigate the influence of the matrix splittings as well as the relaxation parameters on the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for solving the system of weakly nonlinear equations. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Variational iteration technique for solving nonlinear equations

In this paper, we use the variational iteration technique to suggest some new iterative methods for solving nonlinear equations f(x)=0. We also discuss the convergence criteria of these new iterative methods. Comparison with other similar methods is also given. These new methods can be considered as an alternative to the Newton method. We also give several examples to illustrate the efficiency of these methods. This technique can be used to suggest a wide class of new iterative methods for solving system of nonlinear equations.     

Local existence and non-relativistic limits of shock solutions to a multidimensional piston problem for the relativistic Euler equations

The multidimensional piston problem is a special initial-boundary value problem. The boundary conditions are given in two conical surfaces: one is the boundary of the piston, and the other is the shock whose location is to be determined later. In this paper, we are concerned with spherically symmetric piston problem for the relativistic Euler equations. A local shock front solution with the state equation p = a ² ρ, a is a constant and has been established by the Newton iteration. To overcome the difficulty caused by the free boundary, we introduce a coordinate transformation to fix it and employ the linear iteration scheme to establish a sequence of approximate solutions to the auxiliary problems by iteration. In each step, the value of the solution of the previous problem is taken as the data to determine the solution of the next problem. We obtain the existence of the original problem by establishing the convergence of these sequences. Meanwhile, we establish the convergence of the local solution as c → ∞ to the corresponding solution of the classical non-relativistic Euler equations.     

Modified method of splitting with respect to physical processes for solving radiation gas dynamics equations

An approach based on a modified splitting method is proposed for solving the radiation gas dynamics equations in the multigroup kinetic approximation. The idea of the approach is that the original system of equations is split using the thermal radiation transfer equation rather than the energy equation. As a result, analytical methods can be used to solve integrodifferential equations and problems can be computed in the multigroup kinetic approximation without iteration with respect to the collision integral or matrix inversion. Moreover, the approach can naturally be extended to multidimensional problems. A high-order accurate difference scheme is constructed using an approximate Godunov solver for the Riemann problem in two-temperature gas dynamics.     

Inexact non-interior continuation method for solving large-scale monotone SDCP

For exact Newton method for solving monotone semidefinite complementarity problems (SDCP), one needs to exactly solve a linear system of equations at each iteration. For problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a new inexact smoothing/continuation algorithm for solution of large-scale monotone SDCP. At each iteration the corresponding linear system of equations is solved only approximately. Under mild assumptions, the algorithm is shown to be both globally and superlinearly convergent.     

An almost fourth order uniformly convergent domain decomposition method for a coupled system of singularly perturbed reaction-diffusion equations

We consider a system of M(≥2) singularly perturbed equations of reaction-diffusion type coupled through the reaction term. A high order Schwarz domain decomposition method is developed to solve the system numerically. The method splits the original domain into three overlapping subdomains. On two boundary layer subdomains we use a compact fourth order difference scheme on a uniform mesh while on the interior subdomain we use a hybrid scheme on a uniform mesh. We prove that the method is almost fourth order ε-uniformly convergent. Furthermore, we prove that when ε is small, one iteration is sufficient to get almost fourth order ε-uniform convergence. Numerical experiments are performed to support the theoretical results.     

A Smoothing Newton Method for Semi-Infinite Programming

This paper is concerned with numerical methods for solving a semi-infinite programming problem. We reformulate the equations and nonlinear complementarity conditions of the first order optimality condition of the problem into a system of semismooth equations. By using a perturbed Fischer–Burmeister function, we develop a smoothing Newton method for solving this system of semismooth equations. An advantage of the proposed method is that at each iteration, only a system of linear equations is solved. We prove that under standard assumptions, the iterate sequence generated by the smoothing Newton method converges superlinearly/quadratically.     

Experiments in numerical methods for a problem in combustion modeling

In this paper, we have shown that the numerical method of lines can be used effectively to solve time dependent combustion models in one spatial dimension. By the numerical method of lines (NMOL), we mean the reduction of a system of partial differential equations to a system of ordinary differential equations (ODE's), followed by the solution of this ODE system with an appropriate ODE solver. We used finite differences for the spatial discretization and a variant of the GEAR package for the ODE's.We have presented various solution methods of interest for the nonlinear algebraic system in this setting; that is, in the corrector iteration section of the GEAR package applied to combustion models. These methods include Newton/block SOR (SOR denotes successive over-relaxation), block SOR/Newton, Newton/block-diagonal Jacobian, Newton/kinetics-only Jacobian, and Newton/block symmetric SOR. These methods have in common their lack of frequent use in ODE software and their eady applicability to partial differential equations in more than one spatial dimension.Finally, we have given the results of numerical tests, run on the CDC-7600 and Cray-1 computers. By so doing, we indicate the more promising nonlinear system solvers for the NMOL solution of combustion models.     

Goldstein线搜索下Levenberg-Marquardt方法的全局收敛性

给出在Goldstein线搜索条件下求解非线性方程的Levenberg-Marquardt方法, 在较为温和的条件下证明了该方法的全局收敛性, 并且利用该方法对广义互补问题进行了求解分析.