Recurrence relations for a Newton-like method in Banach spaces

The convergence of iterative methods for solving nonlinear operator equations in Banach spaces is established from the convergence of majorizing sequences. An alternative approach is developed to establish this convergence by using recurrence relations. For example, the recurrence relations are used in establishing the convergence of Newton's method [L.B. Rall, Computational Solution of Nonlinear Operator Equations, Robert E. Krieger, New York, 1979] and the third order methods such as Halley's, Chebyshev's and super Halley's [V. Candela, A. Marquina, Recurrence relations for rational cubic methods I: the Halley method, Computing 44 (1990) 169–184; V. Candela, A. Marquina, Recurrence relations for rational cubic methods II: the Halley method, Computing 45 (1990) 355–367; J.A. Ezquerro, M.A. Hernández, Recurrence relations for Chebyshev-type methods, Appl. Math. Optim. 41 (2000) 227–236; J.M. Gutiérrez, M.A. Hernández, Third-order iterative methods for operators with bounded second derivative, J. Comput. Appl. Math. 82 (1997) 171–183; J.M. Gutiérrez, M.A. Hernández, Recurrence relations for the Super–Halley method, Comput. Math. Appl. 7(36) (1998) 1–8; M.A. Hernández, Chebyshev's approximation algorithms and applications, Comput. Math. Appl. 41 (2001) 433–445 [10]].     

On Halley iteration

This paper proposes some modified Halley iterations for finding the zeros of polynomials. We investigate the non-overshoot properties of the modified Halley iterations and other important properties that play key roles in solving symmetric eigenproblems. We also extend Halley iteration to systems of polynomial equations in several variables. Received March 20, 1996 / Revised version received December 5, 1997     

An algorithm for coarsening unstructured meshes

Summary. We develop and analyze a procedure for creating a hierarchical basis of continuous piecewise linear polynomials on an arbitrary, unstructured, nonuniform triangular mesh. Using these hierarchical basis functions, we are able to define and analyze corresponding iterative methods for solving the linear systems arising from finite element discretizations of elliptic partial differential equations. We show that such iterative methods perform as well as those developed for the usual case of structured, locally refined meshes. In particular, we show that the generalized condition numbers for such iterative methods are of order , where is the number of hierarchical basis levels. Received December 5, 1994     

Third-order iterative methods with applications to Hammerstein equations: A unified approach

The geometrical interpretation of a family of higher order iterative methods for solving nonlinear scalar equations was presented in [S. Amat, S. Busquier, J.M. Gutiérrez, Geometric constructions of iterative functions to solve nonlinear equations. J. Comput. Appl. Math. 157(1) (2003) 197-205]. This family includes, as particular cases, some of the most famous third-order iterative methods: Chebyshev methods, Halley methods, super-Halley methods, C-methods and Newton-type two-step methods. The aim of the present paper is to analyze the convergence of this family for equations defined between two Banach spaces by using a technique developed in [J.A. Ezquerro, M.A. Hernández, Halley’s method for operators with unbounded second derivative. Appl. Numer. Math. 57(3) (2007) 354-360]. This technique allows us to obtain a general semilocal convergence result for these methods, where the usual conditions on the second derivative are relaxed. On the other hand, the main practical difficulty related to the classical third-order iterative methods is the evaluation of bilinear operators, typically second-order Fréchet derivatives. However, in some cases, the second derivative is easy to evaluate. A clear example is provided by the approximation of Hammerstein equations, where it is diagonal by blocks. We finish the paper by applying our methods to some nonlinear integral equations of this type.     

On generalized successive overrelaxation methods for augmented linear systems

For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method. Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China     

A simply constructed third-order modifications of Newton's method

In this paper, we present a simple and easily applicable approach to construct some third-order modifications of Newton's method for solving nonlinear equations. It is shown by way of illustration that existing third-order methods can be employed to construct new third-order iterative methods. The proposed approach is applied to the classical Chebyshev–Halley methods to derive their second-derivative-free variants. Numerical examples are given to support that the methods thus obtained can compete with known third-order methods.     

Convergence of a generalized MSSOR method for augmented systems

Recently, Wu et al. [S.-L. Wu, T.-Z. Huang, X.-L. Zhao, A modified SSOR iterative method for augmented systems, J. Comput. Appl. Math. 228 (1) (2009) 424-433] introduced a modified SSOR (MSSOR) method for augmented systems. In this paper, we establish a generalized MSSOR (GMSSOR) method for solving the large sparse augmented systems of linear equations, which is the extension of the MSSOR method. Furthermore, the convergence of the GMSSOR method for augmented systems is analyzed and numerical experiments are carried out, which show that the GMSSOR method with appropriate parameters has a faster convergence rate than the MSSOR method with optimal parameters.     

Iterative refinement enhances the stability ofQR factorization methods for solving linear equations

Iterative refinement is a well-known technique for improving the quality of an approximate solution to a linear system. In the traditional usage residuals are computed in extended precision, but more recent work has shown that fixed precision is sufficient to yield benefits for stability. We extend existing results to show that fixed precision iterative refinement renders anarbitrary linear equations solver backward stable in a strong, componentwise sense, under suitable assumptions. Two particular applications involving theQR factorization are discussed in detail: solution of square linear systems and solution of least squares problems. In the former case we show that one step of iterative refinement suffices to produce a small componentwise relative backward error. Our results are weaker for the least squares problem, but again we find that iterative refinement improves a componentwise measure of backward stability. In particular, iterative refinement mitigates the effect of poor row scaling of the coefficient matrix, and so provides an alternative to the use of row interchanges in the HouseholderQR factorization. A further application of the results is described to fast methods for solving Vandermonde-like systems.     

Generalizations and modifications of the GMRES iterative method

For solving nonsymmetric linear systems, the well-known GMRES method is considered to be a stable method; however, the work per iteration increases as the number of iterations increases. We consider two new iterative methods GGMRES and MGMRES, which are a generalization and a modification of the GMRES method, respectively. Instead of using a minimization condition as in the derivation of GGMRES, we use a Galerkin condition to derive the MGMRES method. We also introduce another new iterative method, LAN/MGMRES, which is designed to combine the reliability of GMRES with the reduced work of a Lanczos-type method. A computer program has been written based on the use of the LAN/MGMRES algorithm for solving nonsymmetric linear systems arising from certain elliptic problems. Numerical tests are presented comparing this algorithm with some other commonly used iterative algorithms. These preliminary tests of the LAN/MGMRES algorithm show that it is comparable in terms of both the approximate number of iterations and the overall convergence behavior. This revised version was published online in June 2006 with corrections to the Cover Date.     

求解方程的一类迭代公式

Using the forms of Newton iterative function, the iterative function of Newton's method to handle the problem of multiple roots and the Halley iterative function, we give a class of iterative formulae for solving equations in one variable in this paper and show that their convergence order is at least quadratic. At last we employ our methods to solve some non-linear equations and compare them with Newton's method and Halley's method. Numerical results show that our iteration schemes are convergent if we choose two suitable parametric functions λ(x) and μ(x). Therefore, our iteration schemes are feasible and effective.     

Reguläre Zerlegungen und Berechnung des Spektralradius nichtnegativer Matrizen

Summary On the basis of a Rayleigh Quotient Iteration method in [10] and a Maximal Quotient Iteration method in [5, 8] two algorithms for solving special eigenvalue problems are developed. The characteristic properties of these methods lie in the application of iterative linear methods to solving systems of linear equations. The convergence properties are investigated. We apply the algorithms to the computation of the spectralradius of a nonnegative irreducible matrix.

     

Deflated GMRES for systems with multiple shifts and multiple right-hand sides

We consider solution of multiply shifted systems of nonsymmetric linear equations, possibly also with multiple right-hand sides. First, for a single right-hand side, the matrix is shifted by several multiples of the identity. Such problems arise in a number of applications, including lattice quantum chromodynamics where the matrices are complex and non-Hermitian. Some Krylov iterative methods such as GMRES and BiCGStab have been used to solve multiply shifted systems for about the cost of solving just one system. Restarted GMRES can be improved by deflating eigenvalues for matrices that have a few small eigenvalues. We show that a particular deflated method, GMRES-DR, can be applied to multiply shifted systems.In quantum chromodynamics, it is common to have multiple right-hand sides with multiple shifts for each right-hand side. We develop a method that efficiently solves the multiple right-hand sides by using a deflated version of GMRES and yet keeps costs for all of the multiply shifted systems close to those for one shift. An example is given showing this can be extremely effective with a quantum chromodynamics matrix.     

Convergence of nested classical iterative methods for linear systems

Summary Classical iterative methods for the solution of algebraic linear systems of equations proceed by solving at each step a simpler system of equations. When this system is itself solved by an (inner) iterative method, the global method is called a two-stage iterative method. If this process is repeated, then the resulting method is called a nested iterative method. We study the convergence of such methods and present conditions on the splittings corresponding to the iterative methods to guarantee convergence forany number of inner iterations. We also show that under the conditions presented, the spectral radii of the global iteration matrices decrease when the number of inner iterations increases. The proof uses a new comparison theorem for weak regular splittings. We extend our results to larger classes of iterative methods, which include iterative block Gauss-Seidel. We develop a theory for the concatenation of such iterative methods. This concatenation appears when different numbers of inner interations are performed at each outer step. We also analyze block methods, where different numbers of inner iterations are performed for different diagonal blocks.Dedicated to Richard S. Varga on the occasion of his sixtieth birthdayP.J. Lanzkron was supported by Exxon Foundation Educational grant 12663 and the UNISYS Corporation; D.J. Rose was supported by AT&T Bell Laboratories, the Microelectronic Center of North Carolina and the Office of Naval Research under contract number N00014-85-K-0487; D.B. Szyld was supported by the National Science Foundation grant DMS-8807338.     

On deflation and singular symmetric positive semi-definite matrices

For various applications, it is well-known that the deflated ICCG is an efficient method for solving linear systems with invertible coefficient matrix. We propose two equivalent variants of this deflated ICCG which can also solve linear systems with singular coefficient matrix, arising from discretization of the discontinuous Poisson equation with Neumann boundary conditions. It is demonstrated both theoretically and numerically that the resulting methods accelerate the convergence of the iterative process.     

Solving systems of fractional differential equations using differential transform method

This paper presents approximate analytical solutions for systems of fractional differential equations using the differential transform method. The fractional derivatives are described in the Caputo sense. The application of differential transform method, developed for differential equations of integer order, is extended to derive approximate analytical solutions of systems of fractional differential equations. The solutions of our model equations are calculated in the form of convergent series with easily computable components. Some examples are solved as illustrations, using symbolic computation. The numerical results show that the approach is easy to implement and accurate when applied to systems of fractional differential equations. The method introduces a promising tool for solving many linear and nonlinear fractional differential equations.     

Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation

We study inexact subspace iteration for solving generalized non-Hermitian eigenvalue problems with spectral transformation, with focus on a few strategies that help accelerate preconditioned iterative solution of the linear systems of equations arising in this context. We provide new insights into a special type of preconditioner with “tuning” that has been studied for this algorithm applied to standard eigenvalue problems. Specifically, we propose an alternative way to use the tuned preconditioner to achieve similar performance for generalized problems, and we show that these performance improvements can also be obtained by solving an inexpensive least squares problem. In addition, we show that the cost of iterative solution of the linear systems can be further reduced by using deflation of converged Schur vectors, special starting vectors constructed from previously solved linear systems, and iterative linear solvers with subspace recycling. The effectiveness of these techniques is demonstrated by numerical experiments.     

Comparison results on preconditioned SOR-type iterative method for Z-matrices linear systems

In this paper, we present some comparison theorems on preconditioned iterative method for solving Z-matrices linear systems, Comparison results show that the rate of convergence of the Gauss–Seidel-type method is faster than the rate of convergence of the SOR-type iterative method.     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

Smoothing iterative block methods for linear systems with multiple right-hand sides

In the present paper, we present smoothing procedures for iterative block methods for solving nonsymmetric linear systems of equations with multiple right-hand sides. These procedures generalize those known when solving one right-hand linear systems. We give some properties of these new methods and then, using these procedures we show connections between some known iterative block methods. Finally we give some numerical examples.     

A communication-less parallel algorithm for tridiagonal Toeplitz systems

Diagonally dominant tridiagonal Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Modern interest in numerical linear algebra is often focusing on solving classic problems in parallel. In McNally [Fast parallel algorithms for tri-diagonal symmetric Toeplitz systems, MCS Thesis, University of New Brunswick, Saint John, 1999], an m processor Split & Correct algorithm was presented for approximating the solution to a symmetric tridiagonal Toeplitz linear system of equations. Nemani [Perturbation methods for circulant-banded systems and their parallel implementation, Ph.D. Thesis, University of New Brunswick, Saint John, 2001] and McNally (2003) adapted the works of Rojo [A new method for solving symmetric circulant tri-diagonal system of linear equations, Comput. Math. Appl. 20 (1990) 61–67], Yan and Chung [A fast algorithm for solving special tri-diagonal systems, Computing 52 (1994) 203–211] and McNally et al. [A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Internat. J. Comput. Math. 75 (2000) 303–313] to the non-symmetric case. In this paper we present relevant background from these methods and then introduce an m processor scalable communication-less approximation algorithm for solving a diagonally dominant tridiagonal Toeplitz system of linear equations.