Convergence behaviour of inexact Newton methods

In this paper we investigate local convergence properties of inexact Newton and Newton-like methods for systems of nonlinear equations. Processes with modified relative residual control are considered, and new sufficient conditions for linear convergence in an arbitrary vector norm are provided. For a special case the results are affine invariant.

     

The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

A Relation Between the Weighted Logarithmic Norm of a Matrix and the Lyapunov Equation

In this note, we define a weighted logarithmic norm for any matrix. In the case when a stable matrix A is considered, we obtain the relationship between the maximal eigenvalue of a symmetric positive definite matrix H which is a solution of the Lyapunov equation and the weight H logarithmic norm of A. It can be seen that the weighted logarithmic norm of A is always a negative value in this case. Several examples illustrate the relationship.     

On block minimal residual methods

In the present work, we give some new results for block minimal residual methods when applied to multiple linear systems. Using the Schur complement, we develop new expressions for the approximation obtained, for the corresponding residual and for the Frobenius residual norm. These results could be used to derive new convergence properties for the block minimal residual methods.     

A posteriori error estimates for finite element approximations to the wave equation with discontinuous coefficients

We derive residual‐based a posteriori error estimates of finite element method for linear wave equation with discontinuous coefficients in a two‐dimensional convex polygonal domain. A posteriori error estimates for both the space‐discrete case and for implicit fully discrete scheme are discussed in L^∞(L²) norm. The main ingredients used in deriving a posteriori estimates are new Clément type interpolation estimates in conjunction with appropriate adaption of the elliptic reconstruction technique of continuous and discrete solutions. We use only an energy argument to establish a posteriori error estimates with optimal order convergence in the L^∞(L²) norm.     

A complete representation theorem for G-martingales

In this article, we establish a complete representation theorem for G-martingales. Unlike the existing results in the literature, we provide the existence and uniqueness of the second-order term, which corresponds to the second-order derivative in Markovian case. The main ingredient of the article is a new norm for that second-order term, which is based on an operator introduced by Song.     

A Concentration Theorem for the Heat Equation

 We compare the solution of to the solution of the same equation where f is replaced by a “concentrated” source . As a result we derive some estimates on the solution in spatial norm, locally uniformly in t, with respect to the norm of for any integer . In the case we obtain a critical inequality relating the norm of to an exponential norm of u. (Received 1 September 2000; in revised form 17 January 2001)     

Least squares and approximate equidistribution in multidimensions

In this article it is shown that, under a natural condition, least squares minimization of the residual of the divergence of a vector field is equivalent to that of a least squares measure of equidistribution of the residual. More specifically, consider the conservation law div f = 0, when the vector field f is approximated by a conforming piecewise differentiable function F on a partition of a polygonal region Ω into triangles. Then, we show that, if F has a prescribed flux across the outer boundary ∂Ω of Ω, minimization of the l₂ norm of the average residual of div F over all internal parameters of the partition (including nodal positions as well as solution amplitudes) is equivalent to minimization of the l₂ norm of the differences in the average residuals of F , taken over all pairs of triangles of the partition. The result is of importance in the approximate solution of conservation laws, where alignment of the mesh is often of considerable benefit in deriving extra accuracy. The property is readily extended to systems of conservation laws. Moreover it holds for the average vorticity residual of F over a triangle as well as for l₂‐type norms combining both the divergence and the vorticity (as in the case of the Cauchy‐Riemann equations). © 1999 Wiley & Sons. Inc. Numer Methods Partial Differential Eq 15:605–615, 1999     

On the stability of the collocation method for the double layer operator on polyhedral domains in R3

We develop a new method to give estimates for the double layer operator on cones in R³. Here we use weighted norms which are equivalent to the usual L^∞‐norm. This result includes the weighted norms which were constructed by Wendland and Kral for the case of rectangular cones. If all vertices in a polyhedral domain (resp. their corresponding cones) allow the construction of a weighted norm, such that the double layer operator has norm smaller than one half, we can prove the stability of the collocation method with piecewise constant trial functions.     

Growth behavior of a class of merit functions for the nonlinear complementarity problem

When the nonlinear complementarity problem is reformulated as that of finding the zero of a self-mapping, the norm of the selfmapping serves naturally as a merit function for the problem. We study the growth behavior of such a merit function. In particular, we show that, for the linear complementarity problem, whether the merit function is coercive is intimately related to whether the underlying matrix is aP-matrix or a nondegenerate matrix or anR _o-matrix. We also show that, for the more popular choices of the merit function, the merit function is bounded below by the norm of the natural residual raised to a positive integral power. Thus, if the norm of the natural residual has positive order of growth, then so does the merit function.This work was partially supported by the National Science Foundation Grant No. CCR-93-11621.The author thanks Dr. Christian Kanzow for his many helpful comments on a preliminary version of this paper. He also thanks the referees for their helpful suggestions.     

A Posteriori Error Estimators and Adaptivity for Finite Element Approximation of the Non-Homogeneous Dirichlet Problem

Techniques are developed for a posteriori error analysis of the non-homogeneous Dirichlet problem for the Laplacian giving computable error bounds for the error measured in the energy norm. The techniques are based on the equilibrated residual method that has proved to be reliable and accurate for the treatment of problems with homogeneous Dirichlet data. It is shown how the equilibrated residual method must be modified to include the practically important case of non-homogeneous Dirichlet data. Explicit and implicit a posteriori error estimators are derived and shown to be efficient and reliable. Numerical examples are provided illustrating the theory.     

How residual bounds for restarted GMRES describe the real behaviour

Given a system of linear equations Ax=b with a nonsingular matrix A, new bounds for the norm of the residual vector are presented and shown by example. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

基于Lanczos双A-正交的一种修正的QMR算法

本文研究了基于Lanczos双正交过程的拟极小残量法(QMR).将QMR算法中的Lanczos双正交过程用Lanczos双A-正交过程代替,利用该算法得到的近似解与最后一个基向量的线性组合来作为新的近似解,使新近似解的残差范数满足一个一维极小化问题,从而得到一种基于Lanczos双A-正交的修正的QMR算法.数值试验表明,对于某些大型线性稀疏方程组,新算法比QMR算法收敛快得多.     

A posteriori error estimates of edge residual type of finite element method for nonmonotone quasi‐linear elliptic problems

In this article, we study the edge residual‐based a posteriori error estimates of conforming linear finite element method for nonmonotone quasi‐linear elliptic problems. It is proven that edge residuals dominate a posteriori error estimates. Up to higher order perturbations, edge residuals can act as a posteriori error estimators. The global reliability and local efficiency bounds are established both in H ¹‐norm and L ²‐norm. Numerical experiments are provided to illustrate the performance of the proposed error estimators. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 813–837, 2014     

Convergence properties of some block Krylov subspace methods for multiple linear systems

In the present paper, we give some convergence results of the global minimal residual methods and the global orthogonal residual methods for multiple linear systems. Using the Schur complement formulae and a new matrix product, we give expressions of the approximate solutions and the corresponding residuals. We also derive some useful relations between the norm of the residuals.     

Entropy gain and the Choi-Jamiolkowski correspondence for infinite-dimensional quantum evolutions

We consider the entropy gain for infinite-dimensional evolutions and show that unlike in the finitedimensional case, there are many channels with positive minimal entropy gain. We obtain a new lower bound and compute the minimal entropy gain for a broad class of bosonic Gaussian channels. We mathematically formulate the Choi-Jamiolkowski (CJ) correspondence between channels and states in the infinite-dimensional case in a form close to the form used in quantum information theory. In particular, we obtain an explicit expression for the CJ operator defining a general nondegenerate bosonic Gaussian channel and compute its norm.     

The Bernstein–Orlicz norm and deviation inequalities

We introduce two new concepts designed for the study of empirical processes. First, we introduce a new Orlicz norm which we call the Bernstein–Orlicz norm. This new norm interpolates sub-Gaussian and sub-exponential tail behavior. In particular, we show how this norm can be used to simplify the derivation of deviation inequalities for suprema of collections of random variables. Secondly, we introduce chaining and generic chaining along a tree. These simplify the well-known concepts of chaining and generic chaining. The supremum of the empirical process is then studied as a special case. We show that chaining along a tree can be done using entropy with bracketing. Finally, we establish a deviation inequality for the empirical process for the unbounded case.     

Some results about GMRES in the singular case

In this paper, we study the Generalized Minimal Residual (GMRES) method for solving singular linear systems, particularly when the necessary and sufficient condition to obtain a Krylov solution is not satisfied. Thanks to some new results which may be applied in exact arithmetic or in finite precision, we analyze the convergence of GMRES and restarted GMRES. These formulas can also be used in the case when the systems are nonsingular. In particular, it allows us to understand what is often referred to as stagnation of the residual norm of GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

New results on the convergence of the conjugate gradient method

This paper is concerned with proving theoretical results related to the convergence of the conjugate gradient (CG) method for solving positive definite symmetric linear systems. Considering the inverse of the projection of the inverse of the matrix, new relations for ratios of the A‐norm of the error and the norm of the residual are provided, starting from some earlier results of Sadok (Numer. Algorithms 2005; 40 :201–216). The proofs of our results rely on the well‐known correspondence between the CG method and the Lanczos algorithm. Copyright © 2008 John Wiley & Sons, Ltd.     

TheC M -embedded problem and optimality conditions

In this paper theC _M -embedded problem which is also called the design centering problem in other papers will be described, and new optimality conditions and some results associated with optimality conditions will be presented. These results hold for general non-convex regions. To a certain extent they provide the possibility to develop search techniques. It should be pointed out that, in this paper, the only case where the Minkowski norm is just the Euclidean norm is treated.