On the convergence of inexact Newton methods for discrete-time algebraic Riccati equations

In this paper, we present a convergence analysis of the inexact Newton method for solving Discrete-time algebraic Riccati equations (DAREs) for large and sparse systems. The inexact Newton method requires, at each iteration, the solution of a symmetric Stein matrix equation. These linear matrix equations are solved approximatively by the alternating directions implicit (ADI) or Smith?s methods. We give some new matrix identities that will allow us to derive new theoretical convergence results for the obtained inexact Newton sequences. We show that under some necessary conditions the approximate solutions satisfy some desired properties such as the d-stability. The theoretical results developed in this paper are an extension to the discrete case of the analysis performed by Feitzinger et al. (2009) [8] for the continuous-time algebraic Riccati equations. In the last section, we give some numerical experiments.     

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.     

Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control

We consider the numerical solution of the generalized Lyapunov and Stein equations in \(\mathbb {R}^{n}\), arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n³) computational complexity per iteration and an O(n²) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n⁶) complexity or the slower modified Newton’s methods of O(n³) complexity. The convergence and error analysis will be considered and numerical examples provided.     

Numerical experience with the truncated Newton method for unconstrained optimization

The truncated Newton algorithm was devised by Dembo and Steihaug (Ref. 1) for solving large sparse unconstrained optimization problems. When far from a minimum, an accurate solution to the Newton equations may not be justified. Dembo's method solves these equations by the conjugate direction method, but truncates the iteration when a required degree of accuracy has been obtained. We present favorable numerical results obtained with the algorithm and compare them with existing codes for large-scale optimization.     

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.     

A Positivity-preserving Finite Element Method for Quantum Drift-diffusion Model

In this paper, we propose a positivity-preserving finite element method for solving the three-dimensional quantum drift-diffusion model. The model consists of five nonlinear elliptic equations, and two of them describe quantum corrections for quasi-Fermi levels. We propose an interpolated-exponential finite element (IEFE) method for solving the two quantum-correction equations. The IEFE method always yields positive carrier densities and preserves the positivity of second-order differential operators in the Newton linearization of quantum-correction equations. Moreover, we solve the two continuity equations with the edge-averaged finite element (EAFE) method to reduce numerical oscillations of quasi-Fermi levels. The Poisson equation of electrical potential is solved with standard Lagrangian finite elements. We prove the existence of solution to the nonlinear discrete problem by using a fixed-point iteration and solving the minimum problem of a new discrete functional. A Newton method is proposed to solve the nonlinear discrete problem. Numerical experiments for a three-dimensional nano-scale FinFET device show that the Newton method is robust for source-to-gate bias voltages up to 9V and source-to-drain bias voltages up to 10V.     

Radial basis collocation method and quasi‐Newton iteration for nonlinear elliptic problems

This work presents a radial basis collocation method combined with the quasi‐Newton iteration method for solving semilinear elliptic partial differential equations. The main result in this study is that there exists an exponential convergence rate in the radial basis collocation discretization and a superlinear convergence rate in the quasi‐Newton iteration of the nonlinear partial differential equations. In this work, the numerical error associated with the employed quadrature rule is considered. It is shown that the errors in Sobolev norms for linear elliptic partial differential equations using radial basis collocation method are bounded by the truncation error of the RBF. The combined errors due to radial basis approximation, quadrature rules, and quasi‐Newton and Newton iterations are also presented. This result can be extended to finite element or finite difference method combined with any iteration methods discussed in this work. The numerical example demonstrates a good agreement between numerical results and analytical predictions. The numerical results also show that although the convergence rate of order 1.62 of the quasi‐Newton iteration scheme is slightly slower than rate of order 2 in the Newton iteration scheme, the former is more stable and less sensitive to the initial guess. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

Numerical solution of integral equations in Chebyshev series

In this paper we discuss the Chebyshev series method with Newton iterations for the numerical solution of nonlinear integral equations. An existence theorem for nonlinear integral equations is given using a functional analytic approach. A method to compute and error bound to an approximate solution is discussed on the basis of the theorem.     

Multistep approximation algorithms: Improved convergence rates through postconditioning with smoothing kernels

We show how certain widely used multistep approximation algorithms can be interpreted as instances of an approximate Newton method. It was shown in an earlier paper by the second author that the convergence rates of approximate Newton methods (in the context of the numerical solution of PDEs) suffer from a “loss of derivatives”, and that the subsequent linear rate of convergence can be improved to be superlinear using an adaptation of Nash–Moser iteration for numerical analysis purposes; the essence of the adaptation being a splitting of the inversion and the smoothing into two separate steps. We show how these ideas apply to scattered data approximation as well as the numerical solution of partial differential equations. We investigate the use of several radial kernels for the smoothing operation. In our numerical examples we use radial basis functions also in the inversion step. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

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

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

The use of approximate factorization in stiff ODE solvers

We consider implicit integration methods for the numerical solution of stiff initial-value problems. In applying such methods, the implicit relations are usually solved by Newton iteration. However, it often happens that in subintervals of the integration interval the problem is nonstiff or mildly stiff with respect to the stepsize. In these nonstiff subintervals, we do not need the (expensive) Newton iteration process. This motivated us to look for an iteration process that converges in mildly stiff situations and is less costly than Newton iteration. The process we have in mind uses modified Newton iteration as the outer iteration process and a linear solver for solving the linear Newton systems as an inner iteration process. This linear solver is based on an approximate factorization of the Newton system matrix by splitting this matrix into its lower and upper triangular part. The purpose of this paper is to combine fixed point iteration, approximate factorization iteration and Newton iteration into one iteration process for use in initial-value problems where the degree of stiffness is changing during the integration.     

Global Linear and Quadratic One-step Smoothing Newton Method for P 0-LCP

We propose a new smoothing Newton method for solving the P ₀-matrix linear complementarity problem (P ₀-LCP) based on CHKS smoothing function. Our algorithm solves only one linear system of equations and performs only one line search per iteration. It is shown to converge to a P ₀-LCP solution globally linearly and locally quadratically without the strict complementarity assumption at the solution. To the best of author's knowledge, this is the first one-step smoothing Newton method to possess both global linear and local quadratic convergence. Preliminary numerical results indicate that the proposed algorithm is promising.     

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.     

An improved numerical method for balanced truncation for symmetric second-order systems

We consider balanced truncation model order reduction for symmetric second-order systems. The occurring large-scale generalized and structured Lyapunov equations are solved with a specially adapted low-rank alternating directions implicit (ADI) type method. Stopping criteria for this iteration are investigated, and a new result concerning the Lyapunov residual within the low-rank ADI method is established. We also propose a goal-oriented stopping criterion which tries to incorporate the balanced truncation approach already during the ADI iteration. The model reduction approach using the ADI method with different stopping criteria is evaluated on several test systems.     

A Newton iteration process for inverse eigenvalue problems

Summary We suppose an inverse eigenvalue problem which includes the classical additive and multiplicative inverse eigenvalue problems as special cases. For the numerical solution of this problem we propose a Newton iteration process and compare it with a known method. Finally we apply it to a numerical example.     

Effective Chorin–Temam algebraic splitting schemes for the steady Navier–stokes equations

This paper continues some recent work on the numerical solution of the steady incompressible Navier–Stokes equations. We present a new method, similar to the one presented in Rebholz et al., but with superior convergence and numerical properties. The method is efficient as it allows one to solve the same symmetric positive‐definite system for the pressure at each iteration, allowing for the simple preconditioning and the reuse of preconditioners. We also demonstrate how one can replace the Schur complement system with a diagonal matrix inversion while maintaining accuracy and convergence, at a small fraction of the numerical cost. Convergence is analyzed for Newton and Picard‐type algorithms, as well as for the Schur complement approximation.     

Some iterative methods for the largest positive definite solution to a class of nonlinear matrix equation

In this paper, we propose some inversion-free iteration methods for finding the largest positive definite solution of a class of nonlinear matrix equation. Then, we consider the properties of the solution for this nonlinear matrix equation. Also, we establish Newton’s iteration method for finding the largest positive definite solution and prove its quadratic convergence. Furthermore, we derive the semi-local convergence of the Newton’s iteration method. Finally, some numerical examples are presented to illustrate the effectiveness of the theoretical results and the behavior of the considered methods.