Extending the applicability of the Gauss–Newton method under average Lipschitz–type conditions

We extend the applicability of the Gauss–Newton method for solving singular systems of equations under the notions of average Lipschitz–type conditions introduced recently in Li et al. (J Complex 26(3):268–295, 2010). Using our idea of recurrent functions, we provide a tighter local as well as semilocal convergence analysis for the Gauss–Newton method than in Li et al. (J Complex 26(3):268–295, 2010) who recently extended and improved earlier results (Hu et al. J Comput Appl Math 219:110–122, 2008; Li et al. Comput Math Appl 47:1057–1067, 2004; Wang Math Comput 68(255):169–186, 1999). We also note that our results are obtained under weaker or the same hypotheses as in Li et al. (J Complex 26(3):268–295, 2010). Applications to some special cases of Kantorovich–type conditions are also provided in this study.     

Efficient three-step iterative methods with sixth order convergence for nonlinear equations

In this paper, we present two new three-step iterative methods for solving nonlinear equations with sixth convergence order. The new methods are obtained by composing known methods of third order of convergence with Newton’s method and using an adequate approximation for the derivative, that provides high order of convergence and reduces the required number of functional evaluations per step. The first method is obtained from Potra-Pták’s method and the second one, from Homeier’s method, both reaching an efficiency index of 1.5651. Our methods are comparable with the method of Parhi and Gupta (Appl Math Comput 203:50–55, 2008). Methods proposed by Kou and Li (Appl Math Comput 189:1816–1821, 2007), Wang et al. (Appl Math Comput 204:14–19, 2008) and Chun (Appl Math Comput 190:1432–1437, 2007) reach the same efficiency index, although they start from a fourth order method while we use third order methods and simpler arithmetics. We prove the convergence results and check them with several numerical tests that allow us to compare the convergence order, the computational cost and the efficiency order of our methods with those of the original methods.     

Two modified Dai-Yuan nonlinear conjugate gradient methods

In this paper, we propose two modified versions of the Dai-Yuan (DY) nonlinear conjugate gradient method. One is based on the MBFGS method (Li and Fukushima, J Comput Appl Math 129:15–35, 2001) and inherits all nice properties of the DY method. Moreover, this method converges globally for nonconvex functions even if the standard Armijo line search is used. The other is based on the ideas of Wei et al. (Appl Math Comput 183:1341–1350, 2006), Zhang et al. (Numer Math 104:561–572, 2006) and possesses good performance of the Hestenes-Stiefel method. Numerical results are also reported. This work was supported by the NSF foundation (10701018) of China.     

On the convergence of Newton-type methods under mild differentiability conditions

We introduce the new idea of recurrent functions to provide a new semilocal convergence analysis for Newton-type methods, under mild differentiability conditions. It turns out that our sufficient convergence conditions are weaker, and the error bounds are tighter than in earlier studies in some interesting cases (Chen, Ann Inst Stat Math 42:387–401, 1990; Chen, Numer Funct Anal Optim 10:37–48, 1989; Cianciaruso, Numer Funct Anal Optim 24:713–723, 2003; Cianciaruso, Nonlinear Funct Anal Appl 2009; Dennis 1971; Deuflhard 2004; Deuflhard, SIAM J Numer Anal 16:1–10, 1979; Gutiérrez, J Comput Appl Math 79:131–145, 1997; Hernández, J Optim Theory Appl 109:631–648, 2001; Hernández, J Comput Appl Math 115:245–254, 2000; Huang, J Comput Appl Math 47:211–217, 1993; Kantorovich 1982; Miel, Numer Math 33:391–396, 1979; Miel, Math Comput 34:185–202, 1980; Moret, Computing 33:65–73, 1984; Potra, Libertas Mathematica 5:71–84, 1985; Rheinboldt, SIAM J Numer Anal 5:42–63, 1968; Yamamoto, Numer Math 51: 545–557, 1987; Zabrejko, Numer Funct Anal Optim 9:671–684, 1987; Zinc̆ko 1963). Applications and numerical examples, involving a nonlinear integral equation of Chandrasekhar-type, and a differential equation are also provided in this study.     

Multi-step nonlinear conjugate gradient methods for unconstrained minimization

Conjugate gradient methods are appealing for large scale nonlinear optimization problems, because they avoid the storage of matrices. Recently, seeking fast convergence of these methods, Dai and Liao (Appl. Math. Optim. 43:87–101, 2001) proposed a conjugate gradient method based on the secant condition of quasi-Newton methods, and later Yabe and Takano (Comput. Optim. Appl. 28:203–225, 2004) proposed another conjugate gradient method based on the modified secant condition. In this paper, we make use of a multi-step secant condition given by Ford and Moghrabi (Optim. Methods Softw. 2:357–370, 1993; J. Comput. Appl. Math. 50:305–323, 1994) and propose two new conjugate gradient methods based on this condition. The methods are shown to be globally convergent under certain assumptions. Numerical results are reported.     

Error estimates for abstract linear–quadratic optimal control problems using proper orthogonal decomposition

In this paper we investigate POD discretizations of abstract linear–quadratic optimal control problems with control constraints. We apply the discrete technique developed by Hinze (Comput. Optim. Appl. 30:45–61, 2005) and prove error estimates for the corresponding discrete controls, where we combine error estimates for the state and the adjoint system from Kunisch and Volkwein (Numer. Math. 90:117–148, 2001; SIAM J. Numer. Anal. 40:492–515, 2002). Finally, we present numerical examples that illustrate the theoretical results.     

A Fréchet derivative-free cubically convergent method for set-valued maps

We introduce a new iterative method in order to approximate a locally unique solution of variational inclusions in Banach spaces. The method uses only divided differences operators of order one. An existence–convergence theorem and a radius of convergence are given under some conditions on divided difference operator and Lipschitz-like continuity property of set-valued mappings. Our method extends the recent work related to the resolution of nonlinear equation in Argyros (J Math Anal Appl 332:97–108, 2007) and has the following advantages: faster convergence to the solution than all the previous known ones in Argyros and Hilout (Appl Math Comput, 2008 in press), Hilout (J Math Anal Appl 339:53–761, 2008, Positivity 10:673–700, 2006), and we do not need to evaluate any Fréchet derivative. We provide also an improvement of the ratio of our algorithm under some center-conditions and less computational cost. Numerical examples are also provided.      

Analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms

This paper is devoted to the convergence and stability analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms. As soon as a nonlinear scheme can be written as a specific perturbation of a linear and convergent subdivision scheme, we show that if some contractivity properties are satisfied, then stability and convergence can be achieved. This approach is applied to various schemes, which give different new results. More precisely, we study uncentered Lagrange interpolatory linear schemes, WENO scheme (Liu et al., J Comput Phys 115:200–212, 1994), PPH and Power-P schemes (Amat and Liandrat, Appl Comput Harmon Anal 18(2):198–206, 2005; Serna and Marquina, J Comput Phys 194:632–658, 2004) and a nonlinear scheme using local spherical coordinates (Aspert et al., Comput Aided Geom Des 20:165–187, 2003). Finally, a stability proof is given for the multiresolution transform associated to a nonlinear scheme of Marinov et al. (2005).     

An FIO calculus for marine seismic imaging, II: Sobolev estimates

We establish sharp L ²-Sobolev estimates for classes of pseudodifferential operators with singular symbols [Guillemin and Uhlmann (Duke Math J 48:251–267, 1981), Melrose and Uhlmann (Commun Pure Appl Math 32:483–519, 1979)] whose non-pseudodifferential (Fourier integral operator) parts exhibit two-sided fold singularities. The operators considered include both singular integral operators along curves in \mathbb R²{\mathbb R^2} with simple inflection points and normal operators arising in linearized seismic imaging in the presence of fold caustics [Felea (Comm PDE 30:1717–1740, 2005), Felea and Greenleaf (Comm PDE 33:45–77, 2008), Nolan (SIAM J Appl Math 61:659–672, 2000)].     

On Ramanujan’s large argument formula for the Gamma function

The aim of this paper is to improve some approximation formulas of Ramanujan type discussed by E.A. Karatsuba [J. Comput. Appl. Math. 135 (2001), 225–240].     

Error estimates for the numerical approximation of Neumann control problems

We continue the discussion of error estimates for the numerical analysis of Neumann boundary control problems we started in Casas et al. (Comput. Optim. Appl. 31:193–219, 2005). In that paper piecewise constant functions were used to approximate the control and a convergence of order O(h) was obtained. Here, we use continuous piecewise linear functions to discretize the control and obtain the rates of convergence in L ²(Γ). Error estimates in the uniform norm are also obtained. We also discuss the approach suggested by Hinze (Comput. Optim. Appl. 30:45–61, 2005) as well as the improvement of the error estimates by making an extra assumption over the set of points corresponding to the active control constraints. Finally, numerical evidence of our estimates is provided. The authors were supported by Ministerio de Ciencia y Tecnología (Spain).     

On a class of secant-like methods for solving nonlinear equations

We provide a semilocal convergence analysis for a certain class of secant-like methods considered also in Argyros (J Math Anal Appl 298:374–397, 2004, 2007), Potra (Libertas Mathematica 5:71–84, 1985), in order to approximate a locally unique solution of an equation in a Banach space. Using a combination of Lipschitz and center-Lipschitz conditions for the computation of the upper bounds on the inverses of the linear operators involved, instead of only Lipschitz conditions (Potra, Libertas Mathematica 5:71–84, 1985), we provide an analysis with the following advantages over the work in Potra (Libertas Mathematica 5:71–84, 1985) which improved the works in Bosarge and Falb (J Optim Theory Appl 4:156–166, 1969, Numer Math 14:264–286, 1970), Dennis (SIAM J Numer Anal 6(3):493–507, 1969, 1971), Kornstaedt (1975), Larsonen (Ann Acad Sci Fenn, A 450:1–10, 1969), Potra (L’Analyse Numérique et la Théorie de l’Approximation 8(2):203–214, 1979, Aplikace Mathematiky 26:111–120, 1981, 1982, Libertas Mathematica 5:71–84, 1985), Potra and Pták (Math Scand 46:236–250, 1980, Numer Func Anal Optim 2(1):107–120, 1980), Schmidt (Period Math Hung 9(3):241–247, 1978), Schmidt and Schwetlick (Computing 3:215–226, 1968), Traub (1964), Wolfe (Numer Math 31:153–174, 1978): larger convergence domain; weaker sufficient convergence conditions, finer error bounds on the distances involved, and a more precise information on the location of the solution. Numerical examples further validating the results are also provided.     

Parametric approximation of isotropic and anisotropic elastic flow for closed and open curves

Deckelnick and Dziuk (Math. Comput. 78(266):645–671, 2009) proved a stability bound for a continuous-in-time semidiscrete parametric finite element approximation of the elastic flow of closed curves in \mathbbR^d, d 3 2{\mathbb{R}^d, d\geq2} . We extend these ideas in considering an alternative finite element approximation of the same flow that retains some of the features of the formulations in Barrett et al. (J Comput Phys 222(1): 441–462, 2007; SIAM J Sci Comput 31(1):225–253, 2008; IMA J Numer Anal 30(1):4–60, 2010), in particular an equidistribution mesh property. For this new approximation, we obtain also a stability bound for a continuous-in-time semidiscrete scheme. Apart from the isotropic situation, we also consider the case of an anisotropic elastic energy. In addition to the evolution of closed curves, we also consider the isotropic and anisotropic elastic flow of a single open curve in the plane and in higher codimension that satisfies various boundary conditions.     

Iterative methods based on the signum function approach for solving nonlinear equations

For finding a root of an equation f(x) = 0 on an interval (a, b), we develop an iterative method using the signum function and the trapezoidal rule for numerical integrations based on the recent work (Yun, Appl Math Comput 198:691–699, 2008). This method, so-called signum iteration method, depends only on the signum function sgn(f(x)){\rm{sgn}}\left(f(x)\right) independently of the behavior of f(x), and the error bound of the kth approximation is (b − a)/(2N ^k ), where N is the number of integration points for the trapezoidal rule in each iteration. In addition we suggest hybrid methods which combine the signum iteration method with usual methods such as Newton, Ostrowski and secant methods. In particular the hybrid method combined with the signum iteration and the secant method is a predictor-corrector type method (Noor and Ahmad, Appl Math Comput 180:167–172, 2006). The proposed methods result in the rapidly convergent approximations, without worry about choosing a proper initial guess. By some numerical examples we show the superiority of the presented methods over the existing iterative methods.     

Some remarks on the numerical computation of integrals on an unbounded interval

An account of the error and the convergence theory is given for Gauss–Laguerre and Gauss–Radau–Laguerre quadrature formulae. We develop also truncated models of the original Gauss rules to compute integrals extended over the positive real axis. Numerical examples confirming the theoretical results are given comparing these rules among themselves and with different quadrature formulae proposed by other authors (Evans, Int. J. Comput. Math. 82:721–730, 2005; Gautschi, BIT 31:438–446, 1991).      

The Chow Rings of Generalized Grassmannians

Based on the basis theorem of Bruhat–Chevalley (in Algebraic Groups and Their Generalizations: Classical Methods, Proceedings of Symposia in Pure Mathematics, vol. 56 (part 1), pp. 1–26, AMS, Providence, 1994) and the formula for multiplying Schubert classes obtained in (Duan, Invent. Math. 159:407–436, 2005) and programmed in (Duan and Zhao, Int. J. Algebra Comput. 16:1197–1210, 2006), we introduce a new method for computing the Chow rings of flag varieties (resp. the integral cohomology of homogeneous spaces).     

Variational discretization of Lavrentiev-regularized state constrained elliptic optimal control problems

In the present work, we apply a variational discretization proposed by the first author in (Comput. Optim. Appl. 30:45–61, 2005) to Lavrentiev-regularized state constrained elliptic control problems. We extend the results of (Comput. Optim. Appl. 33:187–208, 2006) and prove weak convergence of the adjoint states and multipliers of the regularized problems to their counterparts of the original problem. Further, we prove error estimates for finite element discretizations of the regularized problem and investigate the overall error imposed by the finite element discretization of the regularized problem compared to the continuous solution of the original problem. Finally we present numerical results which confirm our analytical findings.     

Truncated regularized Newton method for convex minimizations

Recently, Li et al. (Comput. Optim. Appl. 26:131–147, 2004) proposed a regularized Newton method for convex minimization problems. The method retains local quadratic convergence property without requirement of the singularity of the Hessian. In this paper, we develop a truncated regularized Newton method and show its global convergence. We also establish a local quadratic convergence theorem for the truncated method under the same conditions as those in Li et al. (Comput. Optim. Appl. 26:131–147, 2004). At last, we test the proposed method through numerical experiments and compare its performance with the regularized Newton method. The results show that the truncated method outperforms the regularized Newton method. The work was supported by the 973 project granted 2004CB719402 and the NSF project of China granted 10471036.     

m-Fold Hypergeometric Solutions of Linear Recurrence Equations Revisited

We present two algorithms to compute m-fold hypergeometric solutions of linear recurrence equations for the classical shift case and for the q-case, respectively. The first is an m-fold generalization and q-generalization of the algorithm by van Hoeij (Appl Algebra Eng Commun Comput 17:83–115, 2005; J. Pure Appl Algebra 139:109–131, 1998) for recurrence equations. The second is a combination of an improved version of the algorithms by Petkovšek (Discrete Math 180:3–22, 1998; J Symb Comput 14(2–3):243–264, 1992) for recurrence and q-recurrence equations and the m-fold algorithm from Petkovšek and Salvy (ISSAC 1993 Proceedings, pp 27–33, 1993) for recurrence equations. We will refer to the classical algorithms as van Hoeij or Petkovšek respectively. To formulate our ideas, we first need to introduce an adapted version of an m-fold Newton polygon and its characteristic polynomials for the classical case and q-case, and to prove the important properties in this case. Using the data from the Newton polygon, we are able to present efficient m-fold versions of the van Hoeij and Petkovšek algorithms for the classical shift case and for the q-case, respectively. Furthermore, we show how one can use the Newton polygon and our characteristic polynomials to conclude for which m ? \mathbbN{m\in \mathbb{N}} there might be an m-fold hypergeometric solution at all. Again by using the information obtained from the Newton polygon, the presentation of the q-Petkovšek algorithm can be simplified and streamlined. Finally, we give timings for the ‘classical’ q-Petkovšek, our q-van Hoeij and our modified q-Petkovšek algorithm on some classes of problems and we present a Maple implementation of the m-fold algorithms for the q-case.