Error bounds for Newton's iterates derived from the Kantorovich theorem

Summary In this paper, it is shown that the upper and lower bounds of the errors in the Newton iterates recently obtained by Potra-Pták [11] and Miel [7], with the use of nondiscrete induction and majorizing sequence, respectively, follow immediately from the Kantorovich theorem and the Kantorovich recurrence relations. It is also shown that the upper and lower bounds of Miel are finer than those of Potra-Pták.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041     

Sharp error bounds for Newton's process

Summary The method of nondiscrete mathematical induction is applied to the Newton process. The method yields a very simple proof of the convergence and sharp apriori estimates; it also gives aposteriori bounds which are, in general, better than those given in [1].     

A convergence theorem for Newton-like methods in Banach spaces

Summary A convergence theorem for Newton-like methods in Banach spaces is given, which improves results of Rheinboldt [27], Dennis [4], Miel [15, 16] and Moret [18] and includes as a special case an updated (affine-invariant [6]) version of the Kantorovich theorem for the Newton method given in previous papers [35, 36]. Error bounds obtained in [34] are also improved. This paper unifies the study of finding sharp error bounds for Newton-like methods under Kantorovich type assumptions.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 and by the Ministry of Education, Japan     

Comparison of Brown's and Newton's method in the monotone case

Summary In many cases when Newton's method, applied to a nonlinear sytemF(x)=0, produces a monotonically decreasing sequence of iterates, Brown's method converges monotonically, too. We compare the iterates of Brown's and Newton's method in these monotone cases with respect to the natural partial ordering. It turns out that in most of the cases arising in applications Brown's method then produces better iterates than Newton's method.     

Newton's method for gradient equations based upon the fixed point map: Convergence and complexity study

Summary An approximate Newton method, based upon the fixed point mapT, is introduced for scalar gradient equations. Although the exact Newton method coincides for such scalar equations with the standard iteration, the structure of the fixed point map provides a way of defining anR-quadratically convergent finite element iteration in the spirit of the Kantorovich theory. The loss of derivatives phenomenon, typically experienced in approximate Newton methods, is thereby avoided. It is found that two grid parameters are sssential,h and . The latter is used to calculate the approximate residual, and is isolated as a fractional step; it is equivalent to the approximation ofT. The former is used to calculate the Newton increment, and this is equivalent to the approximation ofT. The complexity of the finite element computation for the Newton increment is shown to be of optimal order, via the Vitukin inequality relating metric entropy andn-widths.Research supported by National Science Foundation grant DMS-8721742     

Enlargement procedure for resolution of singularities at simple singular solutions of nonlinear equations

Summary A solution of a nonlinear equation in Hilbert spaces is said to be a simple singular solution if the Fréchet derivative at the solution has one-dimensional kernel and cokernel. In this paper we present the enlargement procedure for resolution of singularities at simple singular solutions of nonlinear equations. Once singularities are resolved, we can compute accurately the singular solution by Newton's method. Conditions for which the procedure terminates in finite steps are given. In particular, if the equation defined in ⁿ is analytic and the simple singular solution is geometrically isolated, the procedure stops in finite steps, and we obtain the enlarged problem with an isolated solution. Numerical examples are given.This research is partially supported by Grant-in-Aid for Encouragment of Young Scientist No. 60740119, the Ministry of EducationDedicated to Professor Seiiti Huzino on his 60th birthday     

On optimal global error bounds obtained by scaled local error estimates

Summary In the second section a general method of obtaining optimal global error bounds by scaling local error estimates is developed. It is reduced to the solution of a fixpoint problem. In Sect. 3 we show more concrete error estimates reflecting a singularity of order . It is shown that under general circumstances an optimal global error bound is achieved by an (asymptotically) geometric mesh for the local error estimates. In the fourth section we specialize this to the best approximation ofg(x)x by piecewise polynomials with variable knots and degrees having a total numberN of parameters. This generalizes the result of R. DeVore and the author forg(x)=1. In the last section this problem is studied for the functione ^–x on (0, ). The exact asymptotic behaviour of the approximation withN parameters is determined toe ^qoN , whereq _o=0.895486 ....     

Zur Konvergenz des SSOR-Verfahrens für nichtlineare Gleichungssysteme

Zusammenfassung In der vorliegenden Arbeit wird für die Konvergenz des symmetrischen Relaxationsverfahrens (SSOR-Verfahren) bei Anwendung auf eine Klassenichtlinearer Gleichungssysteme die globale Konvergenz bewiesen. Diese Gleichungssysteme treten z.B. bei der Diskretisierung nichtlinearer partieller Differentialgleichungen auf.

---

Convergence of the SSOR-method for nonlinear systems of simultaneous equations

Summary In this paper we prove the convergence of the symmetric successive overrelaxation method if it is applied to certain nonlinear systems of simultaneous equations. These equations are obtained, for example, by discretizing nonlinear elliptic partial differential equations.

Herrn Helmut Brakhage, Kaiserslautern, anläßlich seines sechzigsten Geburtstages am 8. 7. 1986 gewidmet     

Regular splittings and monotone iteration functions

Summary In this paper we introduce the set of so-called monotone iteration functions (MI-functions) belonging to a given function. We prove necessary and sufficient conditions in order that a given MI-function is (in a precisely defined sense) at least as fast as a second one.Regular splittings of a function which were initially introduced for linear functions by R.S. Varga in 1960 are generating MI-functions in a natural manner.For linear functions every MI-function is generated by a regular splitting. For nonlinear functions, however, this is generally not the case.     

A class of root finding methods

A one-parameter family of iterative methods is presented for finding the roots of transcendental equations. For a class of entire functions this family is shown to converge monotonically and globally. We also establish that for simple roots, when a model parameterh is sufficiently small, the convergence is at a linear rate with orderh ².This work is supported in part by NSERC Grant No. 079-6016.     

Liapunov functions and error bounds for approximate solutions of ordinary differential equations

Summary It is shown that Liapunov functions may be used to obtain error bounds for approximate solutions of systems of ordinary differential equations. These error bounds may reflect the behaviour of the error more accurately than other bounds.     

Truncation error bounds for limit-periodic continued fractionsK(a n /1) with lima n =0

Summary Truncation error bounds are developed for continued fractionsK(a _n /1) where |a _n |1/4 for alln sufficiently large. The bounds are particularly suited (some are shown to be best) for the limit-periodic case when lima _n =0. Among the principal results is the following: If |a _n |/n ^p for alln sufficiently large (with constants >0,p>0), then |f–f _m |C[D/(m+2)] ^p(m+2) for allm sufficiently large (for some constantsC>0,D>0). Heref denotes the limit (assumed finite) ofK(a _n /1) andf _m denotes itsmth approximant. Applications are given for continued fraction expansions of ratios of Kummer functions₁ F ₁ and of ratios of hypergeometric functions₀ F ₁. It is shown thatp=1 for₁ F ₁ andp=2 for₀ F ₁, wherep is the parameter determining the rate of convergence. Numerical examples indicate that the error bounds are indeed sharp.Research supported in part by the National Science Foundation under Grant MCS-8202230 and DMS-8401717     

Realistic error bounds for a simple eigenvalue and its associated eigenvector

Summary An algorithm is described which, given an approximate simple eigenvalue and a corresponding approximate eigenvector, provides rigorous error bounds for improved versions of them. No information is required on the rest of the eigenvalues, which may indeed correspond to non-linear elementary divisors. A second algorithm is described which gives more accurate improved versions than the first but provides only error estimates rather than rigorous bounds. Both algorithms extend immediately to the generalized eigenvalue problem.Dedicated to A.S. Householder on his 75th birthday     

Thirteen ways to estimate global error

Summary Various techniques that have been proposed for estimating the accumulated discretization error in the numerical solution of differential equations, particularly ordinary differential equations, are classified, described, and compared. For most of the schemes either an outline of an error analysis is given which explains why the scheme works or a weakness of the scheme is illustrated.This research is partially supported by NSF Grant No. MCS-8107046     

A projected Newton method for minimization problems with nonlinear inequality constraints

Summary Recently developed projected Newton methods for minimization problems in polyhedrons and Cartesian products of Euclidean balls are extended here to general convex feasible sets defined by finitely many smooth nonlinear inequalities. Iterate sequences generated by this scheme are shown to be locally superlinearly convergent to nonsingular extremals , and more specifically, to local minimizers satisfying the standard second order Kuhn-Tucker sufficient conditions; moreover, all such convergent iterate sequences eventually enter and remain within the smooth manifold defined by the active constraints at . Implementation issues are considered for large scale specially structured nonlinear programs, and in particular, for multistage discrete-time optimal control problems; in the latter case, overall per iteration computational costs will typically increase only linearly with the number of stages. Sample calculations are presented for nonlinear programs in a right circular cylinder in ³.Investigation supported by NSF Research Grant #DMS-85-03746     

A note on Halley's method

Summary We introduce the degree of logarithmic convexity which provides a measure of the convexity of a function at each point. Making use of this concept we obtain a new theorem of global convergence for Halley's method.     

A least squares method for finding the preisach hysteresis operator from measurements

Summary A finite element like least squares method is introduced for determining the density function in the Preisach hysteresis model from overdeterined measured data. It is shown that the least squares error depends on the quality of the data and the best approximations to the analytic density. For consistent data criteria are given for convergence of the approximate density and Preisach operator with increasing measurements.Dedicated to Günther Hämmerlin on the occasion of his 60th birthday     

A particle method for first-order symmetric systems

Summary We present and study a conservative particle method of approximation of linear hyperbolic and parabolic systems. This method is based on an extensive use of cut-off functions. We prove its convergence inL ² at the order as soon as the cut-off function belongs toW ^m+1.1.Dedicated to Professor Joachim Nitsche on the occasion of his 60th birthday     

A consturction of monotonically convergent sequences from successive approximations in certain Banach spaces

Summary LetA: XX (whereX=C ^q [a, b] orL ^p [a, b]) be a contraction having the fixed pointf. In this note, using ideas from [1–8], we obtain a modified successive approximation sequence which approximatesf and which has certain properties regarding monotonicity too.     

On the convergence and divergence of Bairstow's method

Summary Necessary and sufficient condition of algebraic character is given for the invertibility of the Jacobian matrix in Bairstow's method. This leads to a sufficient condition for local quadratic convergence. Results also yield the rank of the Jacobian, when it is singular. In the second part of the paper we give several examples for two step cyclization and more complicated kind of divergence. Some of the polynomials in divergence examples are proved to be irreducible over the field of rational numbers.