A uniparametric family of three-step eighth-order multipoint iterative methods for simple roots

A uniparametric family of three-step eighth-order multipoint iterative methods requiring only a first derivative are proposed in this paper to find simple roots of nonlinear equations. Development and convergence analysis on the proposed methods is described along with numerical experiments including comparison with existing methods.     

On Newton-type methods for multiple roots with cubic convergence

We introduce two families of Newton-type methods for multiple roots with cubic convergence. A further Newton-type method for multiple roots with cubic convergence is presented that is related to quadrature. We also provide numerical tests that show that these new methods are competitive to other known methods for multiple roots.     

Unrestricted algorithms for reciprocals and square roots

Algorithms are presented for the computation of reciprocals of nonzero real numbers and square roots of positive numbers. There are no restrictions on the range of the numbers or on the precision that may be demanded in the results.     

Constructing higher-order methods for obtaining the multiple roots of nonlinear equations

This paper concentrates on iterative methods for obtaining the multiple roots of nonlinear equations. Using the computer algebra system Mathematica, we construct an iterative scheme and discuss the conditions to obtain fourth-order methods from it. All the presented fourth-order methods require one-function and two-derivative evaluation per iteration, and are optimal higher-order iterative methods for obtaining multiple roots. We present some special methods from the iterative scheme, including some known already. Numerical examples are also given to show their performance.     

New higher order methods for solving nonlinear equations with multiple roots

For a nonlinear equation f(x)=0 having a multiple root we consider Steffensen’s transformation, T. Using the transformation, say, F_q(x)=T^qf(x) for integer q≥2, repeatedly, we develop higher order iterative methods which require neither derivatives of f(x) nor the multiplicity of the root. It is proved that the convergence order of the proposed iterative method is 1+2^q−2 for any equation having a multiple root of multiplicity m≥2. The efficiency of the new method is shown by the results for some numerical examples.     

A derivative free iterative method for finding multiple roots of nonlinear equations

For an equation f(x)=0 having a multiple root of multiplicity m>1 unknown, we propose a transformation which converts the multiple root to a simple root of H(x)=0. The transformed function H(x) of f(x) with a small >0 has appropriate properties in applying a derivative free iterative method to find the root. Moreover, there is no need to choose a proper initial approximation. We show that the proposed method is superior to the existing methods by several numerical examples.     

H-Splittings and two-stage iterative methods

Summary Convergence of two-stage iterative methods for the solution of linear systems is studied. Convergence of the non-stationary method is shown if the number of inner iterations becomes sufficiently large. TheR ₁-factor of the two-stage method is related to the spectral radius of the iteration matrix of the outer splitting. Convergence is further studied for splittings ofH-matrices. These matrices are not necessarily monotone. Conditions on the splittings are given so that the two-stage method is convergent for any number of inner iterations.This work was supported in part by a Temple University Summer Research Fellowship.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

Derivative free iterative methods with memory of arbitrary high convergence order

In this article we present three derivative free iterative methods with memory to solve nonlinear equations. With the process developed, we can obtain n-step derivative free iterative methods with memory of arbitrary high order. Numerical examples are provided to show that the new methods have an equal or superior performance, on smooth and nonsmooth equations, compared to classical iterative methods as Steffensen’s and Newton’s methods and other derivative free methods with and without memory with high order of convergence.     

Majorizing sequences for iterative methods

We provide convergence results for very general majorizing sequences of iterative methods. Using our new concept of recurrent functions, we unify the semilocal convergence analysis of Newton-type methods (NTM) under more general Lipschitz-type conditions. We present two very general majorizing sequences and we extend the applicability of (NTM) using the same information before Chen and Yamamoto (1989) [13], Deuflhard (2004) [16], Kantorovich and Akilov (1982) [19], Miel (1979) [20], Miel (1980) [21] and Rheinboldt (1968) [30]. Applications, special cases and examples are also provided in this study to justify the theoretical results of our new approach.     

On multiple roots in Descartes’ Rule and their distance to roots of higher derivatives

If an open interval I contains a k  -fold root α$\alpha$ of a real polynomial f, then, after transforming I   to (0,∞)$(0,\infty )$, Descartes’ Rule of Signs counts exactly k roots of f in I, provided I is such that Descartes’ Rule counts no roots of the kth derivative of f. We give a simple proof using the Bernstein basis.     

Semismooth Newton and Newton iterative methods for HJB equation

In this paper, some semismooth methods are considered to solve a nonsmooth equation which can arise from a discrete version of the well-known Hamilton-Jacobi-Bellman equation. By using the slant differentiability introduced by Chen, Nashed and Qi in 2000, a semismooth Newton method is proposed. The method is proved to have monotone convergence by suitably choosing the initial iterative point and local superlinear convergence rate. Moreover, an inexact version of the proposed method is introduced, which reduces the cost of computations and still preserves nice convergence properties. Some numerical results are also reported.     

Breakdowns and stagnation in iterative methods

One of the disadvantages of Krylov subspace iterative methods is the possibility of breakdown. This occurs when it is impossible to get the next approximation of the solution to the linear system of equationsAu=f. There are two different situations: lucky breakdown, when we have found the solution and hard breakdown, when the next Krylov subspace cannot be generated and/or the next approximate solution (iterate) cannot be computed. We show that some breakdowns depend on the chosen method of generating the basis vectors. Another undesirable feature of the iterative methods is stagnation. This occurs when the error does not change for several iterative steps. We investigate when iterative methods can stagnate and describe conditions which characterize stagnation. We show that in some cases stagnation can imply breakdown.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

Three-step iterative methods with eighth-order convergence for solving nonlinear equations

A family of eighth-order iterative methods for the solution of nonlinear equations is presented. The new family of eighth-order methods is based on King’s fourth-order methods and the family of sixth-order iteration methods developed by Chun et al. Per iteration the new methods require three evaluations of the function and one evaluation of its first derivative. Therefore this family of methods has the efficiency index which equals 1.682. Kung and Traub conjectured that a multipoint iteration without memory based on n$n$ evaluations could achieve optimal convergence order 2ⁿ⁻¹$2^{n-1}$. Thus we provide a new example which agrees with the conjecture of Kung–Traub for n=4$n=4$. Numerical comparisons are made to show the performance of the presented methods.     

Block iterative solvers for higher order finite volume methods

Recently, new higher order finite volume methods (FVM) were introduced in [Z. Cai, J. Douglas, M. Park, Development and analysis of higher order finite volume methods over rectangles for elliptic equations, Adv. Comput. Math. 19 (2003) 3-33], where the linear system derived by the hybridization with Lagrange multiplier satisfying the flux consistency condition is reduced to a linear system for a pressure variable by an appropriate quadrature rule. We study the convergence of an iterative solver for this linear system. The conjugate gradient (CG) method is a natural choice to solve the system, but it seems slow, possibly due to the non-diagonal dominance of the system. In this paper, we propose block iterative methods with a reordering scheme to solve the linear system derived by the higher order FVM and prove their convergence. With a proper ordering, each block subproblem can be solved by fast methods such as the multigrid (MG) method. The numerical experiments show that these block iterative methods are much faster than CG.     

Convergence theorems for block splitting iterative methods for linear systems

In this paper, we will present the block splitting iterative methods with general weighting matrices for solving linear systems of algebraic equations Ax=b$\mathit{Ax}=b$ when the coefficient matrix A is symmetric positive definite of block form, and establish the convergence theories with respect to the general weighting matrices but special splittings. Finally, a numerical example shows the advantage of this method.     

Perturbation results for nearly uncoupled Markov chains with applications to iterative methods

Summary The standard perturbation theory for linear equations states that nearly uncoupled Markov chains (NUMCs) are very sensitive to small changes in the elements. Indeed, some algorithms, such as standard Gaussian elimination, will obtain poor results for such problems. A structured perturbation theory is given that shows that NUMCs usually lead to well conditioned problems. It is shown that with appropriate stopping, criteria, iterative aggregation/disaggregation algorithms will achieve these structured error bounds. A variant of Gaussian elimination due to Grassman, Taksar and Heyman was recently shown by O'Cinneide to achieve such bounds.Supported by the National Science Foundation under grant CCR-9000526 and its renewal, grant CCR-9201692. This research was done in part, during the author's visit to the Institute for Mathematics and its Applications, 514 Vincent Hall, 206 Church St. S.E., University of Minnesota, Minneapolis, MN 55455, USA     

New choices of preconditioning matrices for generalized inexact parameterized iterative methods

For large sparse saddle point problems, Chen and Jiang recently studied a class of generalized inexact parameterized iterative methods (see [F. Chen, Y.-L. Jiang, A generalization of the inexact parameterized Uzawa methods for saddle point problems, Appl. Math. Comput. 206 (2008) 765-771]). In this paper, the methods are modified and some choices of preconditioning matrices are given. These preconditioning matrices have advantages in solving large sparse linear system. Numerical experiments of a model Stokes problem are presented.     

Galerkin methods for nonlinear Sobolev equations

Summary We study Galerkin approximations to the solution of nonlinear Sobolev equations with homogeneous Dirichlet boundary condition in two spatial dimensions and derive optimalL ² error estimates for the continuous Crank — Nicolson and Extrapolated Crank — Nicolson approximations.