Newton's method for sections on Riemannian manifolds: Generalized covariant -theory

One kind of the L-average Lipschitz condition is introduced to covariant derivatives of sections on Riemannian manifolds. A convergence criterion of Newton's method and the radii of the uniqueness balls of the singular points for sections on Riemannian manifolds, which is independent of the curvatures, are established under the assumption that the covariant derivatives of the sections satisfy this kind of the L-average Lipschitz condition. Some applications to special cases including Kantorovich's condition and the γ-condition as well as Smale's α-theory are provided. In particular, the result due to Ferreira and Svaiter [Kantorovich's Theorem on Newton's method in Riemannian manifolds, J. Complexity 18 (2002) 304–329] is extended while the results due to Dedieu Priouret, Malajovich [Newton's method on Riemannian manifolds: covariant alpha theory, IMA J. Numer. Anal. 23 (2003) 395–419] are improved significantly. Moreover, the corresponding results due to Alvarez, Bolter, Munier [A unifying local convergence result for Newton's method in Riemannian manifolds, Found. Comput. Math. to appear] for vector fields and mappings on Riemannian manifolds are also extended.     

Convergence behavior of Gauss–Newton’s method and extensions of the Smale point estimate theory

The notions of Lipschitz conditions with L$L$ average are introduced to the study of convergence analysis of Gauss–Newton’s method for singular systems of equations. Unified convergence criteria ensuring the convergence of Gauss–Newton’s method for one kind of singular systems of equations with constant rank derivatives are established and unified estimates of radii of convergence balls are also obtained. Applications to some special cases such as the Kantorovich type conditions, γ$\gamma$-conditions and the Smale point estimate theory are provided and some important known results are extended and/or improved.     

Convergence of Newton’s Method for Sections on Riemannian Manifolds

The present paper is concerned with the convergence problems of Newton’s method and the uniqueness problems of singular points for sections on Riemannian manifolds. Suppose that the covariant derivative of the sections satisfies the generalized Lipschitz condition. The convergence balls of Newton’s method and the uniqueness balls of singular points are estimated. Some applications to special cases, which include the Kantorovich’s condition and the γ-condition, as well as the Smale’s γ-theory for sections on Riemannian manifolds, are given. In particular, the estimates here are completely independent of the sectional curvature of the underlying Riemannian manifold and improve significantly the corresponding ones due to Dedieu, Priouret and Malajovich (IMA J. Numer. Anal. 23:395–419, 2003), as well as the ones in Li and Wang (Sci. China Ser. A. 48(11):1465–1478, 2005).     

A Unifying Local Convergence Result for Newton's Method in Riemannian Manifolds

We consider the problem of finding a singularity of a differentiable vector field X defined on a complete Riemannian manifold. We prove a unified result for theexistence and local uniqueness of the solution, and for the local convergence of a Riemannian version of Newton's method. Our approach relies on Kantorovich's majorant principle: under suitable conditions, we construct an auxiliary scalar equation φ(r) = 0 which dominates the original equation X(p) = 0 in the sense that the Riemannian-Newton method for the latter inherits several features of the real Newton method applied to the former. The majorant φ is derived from an adequate radial parametrization of a Lipschitz-type continuity property of the covariant derivative of X, a technique inspired by the previous work of Zabrejko and Nguen on Newton's method in Banach spaces. We show how different specializations of the main result recover Riemannian versions of Kantorovich's theorem and Smale's α-theorem, and, at least partially, the Euclidean self-concordant theory of Nesterov and Nemirovskii. In the specific case of analytic vector fields, we improve recent developments inthis area by Dedieu et al. . Some Riemannian techniques used here were previously introduced by Ferreira and Svaiter in the context of Kantorovich's theorem for vector fields with Lipschitz continuous covariant derivatives.     

Second-Derivative-Free Variant of the Chebyshev Method for Nonlinear Equations

In this paper, we introduce a numerical method for nonlinear equations, based on the Chebyshev third-order method, in which the second-derivative operator is replaced by a finite difference between first derivatives. We prove a semilocal convergence theorem which guarantees local convergence with R-order three under conditions similar to those of the Newton-Kantorovich theorem, assuming the Lipschitz continuity of the second derivative. In a subsequent theorem, the latter condition is replaced by the weaker assumption of Lipschitz continuity of the first derivative.     

Newton iterations in implicit time-stepping scheme for differential linear complementarity systems

We propose a generalized Newton method for solving the system of nonlinear equations with linear complementarity constraints in the implicit or semi-implicit time-stepping scheme for differential linear complementarity systems (DLCS). We choose a specific solution from the solution set of the linear complementarity constraints to define a locally Lipschitz continuous right-hand-side function in the differential equation. Moreover, we present a simple formula to compute an element in the Clarke generalized Jacobian of the solution function. We show that the implicit or semi-implicit time-stepping scheme using the generalized Newton method can be applied to a class of DLCS including the nondegenerate matrix DLCS and hidden Z-matrix DLCS, and has a superlinear convergence rate. To illustrate our approach, we show that choosing the least-element solution from the solution set of the Z-matrix linear complementarity constraints can define a Lipschitz continuous right-hand-side function with a computable Lipschitz constant. The Lipschitz constant helps us to choose the step size of the time-stepping scheme and guarantee the convergence.     

延迟微分方程隐式Euler方法的收敛性

本文讨论了用隐式Euler方法求解一类延迟量满足Lipschitz条件且Lipschitz常数小于1的非线性变延迟微分方程初值问题的收敛性.获得了带线性插值的隐式Euler方法的收敛性结果.     

Newton's method under mild differentiability conditions with error analysis

Summary The concept of majorizing sequences introduced by Rheinboldt (SIAM J.N.A. 1968) is used to prove convergence for Newton's method for operator equations of the formT f= when the operator satisfied the condition that the Fréchet derivative is Hölder continuous.A detailed analysis of computational errors is given for Newton's method applied to operators with Hölder continuous derivatives. This analysis is shown to reduce the analysis of Lancaster (Num. Math. 1968) when the operator has a continuous second derivative.The above analysis is applied to an example of a second order differential equation.The author is grateful to National Research Council of Canada and National Defency Research Board of Canada for financial support.     

Product integration methods for solving a system of nonlinear Volterra integral equations

In this paper the technique of subtracting out singularities is used to derive explicit and implicit product Euler schemes with order one convergence and a product trapezoidal scheme with order two convergence for a system of Volterra integral equations with a weakly singular kernel. The convergence proofs of the numerical schemes are presented; these are nonstandard since the nonlinear function involved in the integral equation system does not satisfy a global Lipschitz condition.     

Global convergence of some differential equation algorithms for solving equations involving positive variables

This paper describes some sufficient conditions for global convergence in five differential equation algorithms for solving systems of non-linear algebraic equations involving positive variables. The algorithms are continuous time versions of a modified steepest descent method, Newton's method, a modified Newton's method and two algorithms using the transpose of the Jacobian in place of the inverse of the Jacobian in Newton's method. It is shown that under a set of mildly restrictive conditions the Jacobian transpose algorithm has qualitatively the same convergence as Newton's method.     

Numerical Solutions of Stochastic Differential Delay Equations with Jumps

Abstract

In this article, we investigate the strong convergence of the Euler–Maruyama method and stochastic theta method for stochastic differential delay equations with jumps. Under a global Lipschitz condition, we not only prove the strong convergence, but also obtain the rate of convergence. We show strong convergence under a local Lipschitz condition and a linear growth condition. Moreover, it is the first time that we obtain the rate of the strong convergence under a local Lipschitz condition and a linear growth condition, i.e., if the local Lipschitz constants for balls of radius R are supposed to grow not faster than log R.     

Application of a 14-point averaging operator in the grid method

The Dirichlet problem for Laplace’s equation in a rectangular parallelepiped is solved by applying the grid method. A 14-point averaging operator is used to specify the grid equations on the entire grid introduced in the parallelepiped. Given boundary values that are continuous on the parallelepiped edges and have first derivatives satisfying the Lipschitz condition on each parallelepiped face, the resulting discrete solution of the Dirichlet problem converges uniformly and quadratically with respect to the mesh size. Assuming that the boundary values on the faces have fourth derivatives satisfying the Hölder condition and the second derivatives on the edges obey an additional compatibility condition implied by Laplace’s equation, the discrete solution has uniform and quartic convergence with respect to the mesh size. The convergence of the method is also analyzed in certain cases when the boundary values are of intermediate smoothness.     

An efficient Levenberg–Marquardt method with a new LM parameter for systems of nonlinear equations

A modified Levenberg–Marquardt method for solving singular systems of nonlinear equations was proposed by Fan [J Comput Appl Math. 2003;21;625–636]. Using trust region techniques, the global and quadratic convergence of the method were proved. In this paper, to improve this method, we decide to introduce a new Levenberg–Marquardt parameter while also incorporate a new nonmonotone technique to this method. The global and quadratic convergence of the new method is proved under the local error bound condition. Numerical results show the new algorithm is efficient and promising.     

Gauss-Newton法的收敛球与解的唯一性球

0　引　言本文研究非线性最小二乘问题min F( x)∶ =12 f( x) Tf ( x) ( EP)的 Gauss-Newton法的局部收敛性 ,其中 f:Rn→ Rm是 Frechet可微的 ,m≥ n.非线性最小二乘问题在数据拟合 ,参数估计和函数逼近等方面有广泛的应用 .在工程应用中也起到很大作用 ,例如在神经网络中 ,对小波问题 ,FP网络等方面的数据 (图形 )传输 ,数据 (图形 )压缩等方面有极其重要的理论和实际意义 .目前 ,求解最小二乘问题的最基本的方法之一是 Gauss-Newton法 [1 ]xn+1 =xn -[f′( xn) Tf′( x) ] - 1 f′( xn) Tf( xn) . ( GN)就我们所知 ,目前关于 Gau…     

Strong convergence of split-step backward Euler method for stochastic differential equations with non-smooth drift

In this paper, we are concerned with the numerical approximation of stochastic differential equations with discontinuous/nondifferentiable drifts. We show that under one-sided Lipschitz and general growth conditions on the drift and global Lipschitz condition on the diffusion, a variant of the implicit Euler method known as the split-step backward Euler (SSBE) method converges with strong order of one half to the true solution. Our analysis relies on the framework developed in [D. J. Higham, X. Mao and A. M. Stuart, Strong convergence of Euler-type methods for nonlinear stochastic differential equations, SIAM Journal on Numerical Analysis, 40 (2002) 1041-1063] and exploits the relationship which exists between explicit and implicit Euler methods to establish the convergence rate results.     

Further Improvements in High Gain Observer Design for Systems with Structured Nonlinearities

Due to their simple implementation based on a constant gain matrix, high gain observers are very common in practical applications. We consider systems whose dynamics can be decomposed into a linear and a nonlinear part, where the nonlinear part meets some Lipschitz condition. In many cases there exists a finite bound on the maximum feasible Lipschitz constant for which the error dynamics can be stabilized. Necessary and in some sense sufficient conditions for this maximum Lipschitz constant are given in [1]. These results has been improved in [2,3] by taking the structure of the linear part into account. Having a system with one single nonlinearity, the results given in [2,3] are strict. If multiple nonlinearities occur, even this approach tends to be to conservative. In this case, one could additionally take the internal structure of the nonlinearities into account which leads to a larger set of systems for which convergence of the observer error can be guaranteed. Our new approach is based on an approximation of the structured singular value [4] which yields existence conditions in terms of linear matrix inequalities (LMIs). These LMIs may as well be used for the numerical computation of the observer gain. We demonstrate the advantage of our method on an example. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Strong Convergence of the Euler-Maruyama Method for Nonlinear Stochastic Volterra Integral Equations with Time-Dependent Delay

We consider a nonlinear stochastic Volterra integral equation with time-dependent delay and the corresponding Euler-Maruyama method in this paper. Strong convergence rate (at fixed point) of the corresponding Euler-Maruyama method is obtained when coefficients $f$ and $g$ both satisfy local Lipschitz and linear growth conditions. An example is provided to interpret our conclusions. Our result generalizes and improves the conclusion in [J. Gao, H. Liang, S. Ma, Strong convergence of the semi-implicit Euler method for nonlinear stochastic Volterra integral equations with constant delay, Appl. Math. Comput., 348 (2019) 385-398.]     

On the Convergence of Formal Solutions of a System of Partial Differential Equations

We study a version of the classical problem on the convergence of formal solutions of systems of partial differential equations. A necessary and sufficient condition for the convergence of a given formal solution (found by any method) is proved. This convergence criterion applies to systems of partial differential equations (possibly, nonlinear) solved for the highest-order derivatives or, which is most important, “almost solved for the highest-order derivatives.”     

Semilocal convergence analysis for the modified Newton-HSS method under the Hölder condition

The present paper is concerned with theoretical properties of the modified Newton-HSS method for large sparse non-Hermitian positive definite systems of nonlinear equations. Assuming that the nonlinear operator satisfies the Hölder continuity condition, a new semilocal convergence theorem for the modified Newton-HSS method is established. The Hölder continuity condition is milder than the usual Lipschitz condition. The semilocal convergence theorem is established by using the majorizing principle, which is based on the concept of majorizing sequence given by Kantorovich. Two real valued functions and two real sequences are used to establish the convergence criterion. Furthermore, a numerical example is given to show application of our theorem.     

Two differential equation systems for equality-constrained optimization

This paper presents two differential systems, involving first and second order derivatives of problem functions, respectively, for solving equality-constrained optimization problems. Local minimizers to the optimization problems are proved to be asymptotically stable equilibrium points of the two differential systems. First, the Euler discrete schemes with constant stepsizes for the two differential systems are presented and their convergence theorems are demonstrated. Second, we construct algorithms in which directions are computed by these two systems and the stepsizes are generated by Armijo line search to solve the original equality-constrained optimization problem. The constructed algorithms and the Runge–Kutta method are employed to solve the Euler discrete schemes and the differential equation systems, respectively. We prove that the discrete scheme based on the differential equation system with the second order information has the locally quadratic convergence rate under the local Lipschitz condition. The numerical results given here show that Runge–Kutta method has better stability and higher precision and the numerical method based on the differential equation system with the second information is faster than the other one.