On Newton-type methods with cubic convergence

Recently, there has been some progress on Newton-type methods with cubic convergence that do not require the computation of second derivatives. Weerakoon and Fernando (Appl. Math. Lett. 13 (2000) 87) derived the Newton method and a cubically convergent variant by rectangular and trapezoidal approximations to Newton's theorem, while Frontini and Sormani (J. Comput. Appl. Math. 156 (2003) 345; 140 (2003) 419 derived further cubically convergent variants by using different approximations to Newton's theorem. Homeier (J. Comput. Appl. Math. 157 (2003) 227; 169 (2004) 161) independently derived one of the latter variants and extended it to the multivariate case. Here, we show that one can modify the Werrakoon–Fernando approach by using Newton's theorem for the inverse function and derive a new class of cubically convergent Newton-type methods.     

Third-order modification of Newton's method

In this paper, we present a new modification of Newton's method for solving non-linear equations. Analysis of convergence shows that the new method is cubically convergent. Numerical examples show that the new method can compete with the classical Newton's method.     

The Cost of Kuhn's Algorithm and Complexity Theory

A comparison by Wang and Xu between S. Samle's cost estimation for Newton's method and that of the author's for Kuhn's algorithm, both aiming at the zero finding of complex polynomials, showed improvements the advantage of the latter in finding zeros and approximate zeros. In this paper, important on the above work are made. Furthermore, a probabilistic estimation of the monotonicity of Kuhn's algorithm is obtained.     

On a Newton-Moser type method

We prove that a variant of Moser's iterative method for solving nonlinear equations is quadratically convergent and give error bounds. We estimate the amount of arithmetic for the method and compare it to Newton's method. Finally we use the method to solve a problem with small divisors.     

A globally convergent algorithm for determining approximate real zeros of a class of functions

BIT Numerical Mathematics - It is shown that Newton's method can be used to define a globally convergent algorithm for approximating real zeros of a certain class of functions. Included in this...     

Quadratic Convergence of Newton's Method for Convex Interpolation and Smoothing

Abstract. In this paper, we prove that Newton's method for convex best interpolation is locally quadratically convergent, giving an answer to a question of Irvine, Marin, and Smith [7] and strengthening a result of Andersson and Elfving [1] and our previous work [5]. A damped Newton-type method is presented which has global quadratic convergence. Analogous results are obtained for the convex smoothing problem. Numerical examples are presented.     

Free vibration analysis of a structural system with a pair of irrational nonlinearities

An alternative method of deriving accurate and simple analytical approximate solutions to a structural dynamical system governed by a pair of strong irrational restoring forces is presented. This system can be used to represent mathematical models in various engineering problems. Prior to solving the problem, a rational approximation of the nonlinear restoring force function is applied to achieve a convergent truncation. Analytical solutions are then obtained using the combination of the harmonic balance method and Newton's method. This approach shows that lower-order analytical procedures can yield highly accurate and exact solutions that are difficult to obtain with an analytical expression.     

Leap-frogging Newton's method

Using Newton's method as an intermediate step, we introduce an iterative method that approximates numerically the solution of f (x) = 0. The method is essentially a leap-frog Newton's method. The order of convergence of the proposed method at a simple root is cubic and the computational efficiency in general is less, but close to that of Newton's method. Like Newton's method, the new method requires only function and first derivative evaluations. The method can easily be implemented on computer algebra systems where high machine precision is available.     

Regularized Versions of Continuous Newton's Method and Continuous Modified Newton's Method Under General Source Conditions

Regularized versions of continuous analogues of Newton's method and modified Newton's method for obtaining approximate solutions to a nonlinear ill-posed operator equation of the form F(u) = f, where F is a monotone operator defined from a Hilbert space H into itself, have been studied in the literature. For such methods, error estimates are available only under Hölder-type source conditions on the solution. In this paper, presenting the background materials systematically, we derive error estimates under a general source condition. For the special case of the regularized modified Newton's method under a Hölder-type source condition, we also carry out error analysis by replacing the monotonicity of F by a weaker assumption. This analysis facilitates inclusion of certain examples of parameter identification problems, which was not possible otherwise. Moreover, an a priori stopping rule is considered when we have a noisy data f _δ instead of f. This rule yields not only convergence of the regularized approximations to the exact solution as the noise level δ tends to zero but also provides convergence rates that are optimal under the source conditions considered.     

Kepler equation and accelerated Newton method

We study the efficiency of the accelerated Newton method (Garlach, SIAM Rev. 36 (1994) 272–276) for several orders of convergence versus Danby's method for the resolution of Kepler's equation; we find that the cited method of order three is competitive with Danby's method and the classical Newton's method. We also generalize the accelerated Newton method for the resolution of system of algebraic equations, obtaining a formula of order three and a proof of its convergence; its application to several examples shows that its efficiency is greater than Newton's method.     

Globally convergent inexact generalized Newton's methods for nonsmooth equations

In this paper, motivated by the Martinez and Qi methods (J. Comput. Appl. Math. 60 (1995) 127), we propose one type of globally convergent inexact generalized Newton's methods to solve nonsmooth equations in which the functions are nondifferentiable, but are Lipschitz continuous. The methods make the norm of the functions decreasing. These methods are implementable and globally convergent. We also prove that the algorithms have superlinear convergence rates under some mild conditions.     

How concept images affect students’ interpretations of Newton's method

Knowing when students have the prerequisite knowledge to be able to read and understand a mathematical text is a perennial concern for instructors. Using text describing Newton's method and Vinner's notion of concept image, we exemplify how prerequisite knowledge influences understanding. Through clinical interviews with first-semester calculus students, we determined how evoked concept images of tangent lines and roots contributed to students’ interpretation and application of Newton's method. Results show that some students’ concept images of root and tangent line developed throughout the interview process, and most students were able to adequately interpret the text on Newton's method. However, students with insufficient concept images of tangent line and students who were unwilling or unable to modify their concept images of tangent line after reading the text were not successful in interpreting Newton's method.     

Newton iterations without inverting the Derivative

We describe an iteration procedure in a Banach space which is quadratically convergent like Newton's method. In fact, it is a modification of the latter. The inverted derivatives are replaced by so-called contractors which are constructed recursively. Moreover, this method is extended to a scale of Banach spaces. It turns out that the rate of convergence remains quadratic, even if the norms of the contractors are increasing exponentially. A hard implicit function theorem results. In particular, this theorem can be applied to prove existence of quasiperiodic solutions for the Lorenz model of stationary convection.     

CONVERGENCE OF NEWTON＇S METHOD FOR A MINIMIZATION PROBLEM IN IMPULSE NOISE REMOVAL

Recently, two-phase schemes for removing salt-and-pepper and random-valued impulse noise are proposed in [6, 7]. The first phase uses decision-based median filters to locate those pixels which are likely to be corrupted by noise (noise candidates). In the second phase, these noise candidates are restored using a detail-preserving regularization method which allows edges and noise-free pixels to be preserved. As shown in [18], this phase is equivalent to solving a one-dimensional nonlinear equation for each noise candidate.One can solve these equations by using Newton‘s method. However, because of the edgepreserving term, the domain of convergence of Newton‘s method will be very narrow. In this paper, we determine the initial guesses for these equations such that Newton‘s method will always converge.     

Majorizing Sequences for Nonlinear Fredholm–Hammerstein Integral Equations

We use the method of majorizing sequences to study the applicability of Newton's method to solve nonlinear Fredholm–Hammerstein integral equations. For this, we use center convergence conditions on points different from the starting point of Newton's method, which is the point usually used by other authors until now when center conditions are required. In addition, the theoretical significance of the method is used to draw conclusions about the existence and uniqueness of solutions and about the region in which they are located. As a result, we modify the domain of starting points for Newton's method.     

A modified Newton direction for unconstrained optimization

In this article, a modification on Newton's direction for solving problems of unconstrained optimization is presented. As it is known, a major disadvantage of Newton's method is its slowness or non-convergence for the initial point not being close to optima's neighbourhood. The proposed method generally guarantees the decrement of the norm of the gradient or the value of the objective function at every iteration, contributing to the efficiency of Newton's method. The quadratic convergence of the proposed iterative scheme and the enlargement of the radius of convergence area are proved. The proposed algorithm has been implemented and tested on several well-known test functions.     

Use of Halley's Method in the Nonlinear Finite Element Analysis

Halley's method is a higher order iteration method for the solution of nonlinear systems of equations. Unlike Newton's method, which converges quadratically in the vicinity of the solution, Halley's method can exhibit a cubic order of convergence. The equations of Halley's method for multiple dimensions are derived using Padé approximants and inverse one-point interpolation, as proposed by Cuyt. The investigation of the performance of Halley's method concentrates on eight-node volume elements for nonlinear deformations using Staint Venant-Kirchhoff's constitutive law, as well as a geometric linear theory of von Mises plasticity. The comparison with Newton's method reveals the sensibility of Halley's method, in view of the radius of attraction but also demonstrates the advantages of Halley's method considering simulation costs and the order of convergence. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the convergence of Newton's method for a class of nonsmooth operators

We provide an analog of the Newton–Kantorovich theorem for a certain class of nonsmooth operators. This class includes smooth operators as well as nonsmooth reformulations of variational inequalities. It turns out that under weaker hypotheses we can provide under the same computational cost over earlier works [S.M. Robinson, Newton's method for a class of nonsmooth functions, Set-Valued Anal. 2 (1994) 291–305] a semilocal convergence analysis with the following advantages: finer error bounds on the distances involved and a more precise information on the location of the solution. In the local case not examined in [S.M. Robinson, Newton's method for a class of nonsmooth functions, Set-Valued Anal. 2 (1994) 291–305] we can show how to enlarge the radius of convergence and also obtain finer error estimates. Numerical examples are also provided to show that in the semilocal case our results can apply where others [S.M. Robinson, Newton's method for a class of nonsmooth functions, Set-Valued Anal. 2 (1994) 291–305] fail, whereas in the local case we can obtain a larger radius of convergence than before [S.M. Robinson, Newton's method for a class of nonsmooth functions, Set-Valued Anal. 2 (1994) 291–305].     

On a one-dimensional optimization problem derived from the efficiency analysis of Newton-PCG-like algorithms

The Newton-PCG (preconditioned conjugate gradient) like algorithms are usually very efficient. However, their efficiency is mainly supported by the numerical experiments. Recently, a new kind of Newton-PCG-like algorithms is derived in (J. Optim. Theory Appl. 105 (2000) 97; Superiority analysis on truncated Newton method with preconditioned conjugate gradient technique for optimization, in preparation) by the efficiency analysis. It is proved from the theoretical point of view that their efficiency is superior to that of Newton's method for the special cases where Newton's method converges with precise Q-order 2 and α(⩾2), respectively. In the process of extending such kind of algorithms to the more general case where Newton's method has no fixed convergence order, the first is to get the solutions to the one-dimensional optimization problems with many different parameter values of α. If these problems were solved by numerical method one by one, the computation cost would reduce the efficiency of the Newton-PCG algorithm, and therefore is unacceptable. In this paper, we overcome the difficulty by deriving an analytic expression of the solution to the one-dimensional optimization problem with respect to the parameter α.