A new method of secant-like for nonlinear equations

In this paper, a new method for solving nonlinear equations f(x) = 0 is presented. In many literatures the derivatives are used, but the new method does not use the derivatives. Like the method of secant, the first derivative is replaced with a finite difference in this new method. The new method converges not only faster than the method of secant but also Newton’s method. The fact that the new method’s convergence order is 2.618 is proved, and numerical results show that the new method is efficient.     

A GLOBAL-LOCAL FINITE ELEMENT METHOD IN SPACE-TIME FOR A HYPERBOLIC PROBLEM

ABSTRACT

A finite element method for solving the wave equation with couples boundary conditions is presented. In this approach finite elements are applied globally with respect to space and simultaneously but locally with respect to time. This gives rise to a single-step method in time. The method is a practical and economic one and the numerical results obtained compare favourably with the available analytic solution.     

A Barzilai-Borwein conjugate gradient method

The linear conjugate gradient method is an optimal method for convex quadratic minimization due to the Krylov subspace minimization property. The proposition of limited-memory BFGS method and Barzilai-Borwein gradient method, however, heavily restricted the use of conjugate gradient method for large-scale nonlinear optimization. This is, to the great extent, due to the requirement of a relatively exact line search at each iteration and the loss of conjugacy property of the search directions in various occasions. On the contrary, the limited-memory BFGS method and the Barzilai-Bowein gradient method share the so-called asymptotical one stepsize per line-search property, namely, the trial stepsize in the method will asymptotically be accepted by the line search when the iteration is close to the solution. This paper will focus on the analysis of the subspace minimization conjugate gradient method by Yuan and Stoer (1995). Specifically, if choosing the parameter in the method by combining the Barzilai-Borwein idea, we will be able to provide some efficient Barzilai-Borwein conjugate gradient (BBCG) methods. The initial numerical experiments show that one of the variants, BBCG3, is specially efficient among many others without line searches. This variant of the BBCG method might enjoy the asymptotical one stepsize per line-search property and become a strong candidate for large-scale nonlinear optimization.     

A Modified L-Shaped Method

This paper presents a modified version of the L-shaped method (Refs. 1–5), used to solve two-stage stochastic linear programs with fixed recourse, by employing the implicit LX method and the implicit LP method (Refs. 6–9) of the ABS class of methods. By exploiting the properties and special structure of the ABS class and applying these to the simplex method, the number of arithmetic operations is greatly decreased.     

解变分不等式问题的混合方法

By using Fukushima‘s differentiable merit function,Taji,Fukushima and Ibaraki have given a globally convergent modified Newton method for the strongly monotone variational inequality problem and proved their method to be quadratically convergent under certain assumptions in 1993. In this paper a hybrid method for the variational inequality problem under the assumptions that the mapping F is continuously differentiable and its Jacobian matrix F(x) is positive definite for all x∈S rather than strongly monotone and that the set S is nonempty, polyhedral,closed and convex is proposed. Armijo-type line search and trust region strategies as well as Fukushima‘s differentiable merit function are incorporated into the method. It is then shown that the method is well defined and globally convergent and that,under the same assumptions as those of Taji et al. ,the method reduces to the basic Newton method and hence the rate of convergence is quadratic. Computational experiences show the efficiency of the proposed method.     

A Shamanskii-like Levenberg-Marquardt method for nonlinear equations

In this paper, we propose a Shamanskii-like Levenberg-Marquardt method for nonlinear equations. At every iteration, not only a LM step but also m?1 approximate LM steps are computed, where m is a positive integer. Under the local error bound condition which is weaker than nonsingularity, we show the Shamanskii-like LM method converges with Q-order m+1. The trust region technique is also introduced to guarantee the global convergence of the method. Since the Jacobian evaluation and matrix factorization are done after every m computations of the step, the overall cost of the Shamanskii-like LM method is usually much less than that of the general LM method (the m=1 case).     

A nonsmooth version of Newton's method

Newton's method for solving a nonlinear equation of several variables is extended to a nonsmooth case by using the generalized Jacobian instead of the derivative. This extension includes the B-derivative version of Newton's method as a special case. Convergence theorems are proved under the condition of semismoothness. It is shown that the gradient function of the augmented Lagrangian forC ²-nonlinear programming is semismooth. Thus, the extended Newton's method can be used in the augmented Lagrangian method for solving nonlinear programs.This author's work is supported in part by the Australian Research Council.This author's work is supported in part by the National Science Foundation under grant DDM-8721709.     

A practical method for solving large-scale TRS

We present a nearly-exact method for the large scale trust region subproblem (TRS) based on the properties of the minimal-memory BFGS method. Our study is concentrated in the case where the initial BFGS matrix can be any scaled identity matrix. The proposed method is a variant of the Moré–Sorensen method that exploits the eigenstructure of the approximate Hessian B, and incorporates both the standard and the hard case. The eigenvalues of B are expressed analytically, and consequently a direction of negative curvature can be computed immediately by performing a sequence of inner products and vector summations. Thus, the hard case is handled easily while the Cholesky factorization is completely avoided. An extensive numerical study is presented, for covering all the possible cases arising in the TRS with respect to the eigenstructure of B. Our numerical experiments confirm that the method is suitable for very large scale problems.     

A bias corrected nonparametric regression estimator

In this article, we propose a new method of bias reduction in nonparametric regression estimation. The proposed new estimator has asymptotic bias order h⁴, where h is a smoothing parameter, in contrast to the usual bias order h² for the local linear regression. In addition, the proposed estimator has the same order of the asymptotic variance as the local linear regression. Our proposed method is closely related to the bias reduction method for kernel density estimation proposed by Chung and Lindsay (2011). However, our method is not a direct extension of their density estimate, but a totally new one based on the bias cancelation result of their proof.     

A quadrature-based approach to improving the collocation method

Summary The collocation method is a popular method for the approximate solution of boundary integral equations, but typically does not achieve the high order of convergence reached by the Galerkin method in appropriate negative norms. In this paper a quadrature-based method for improving upon the collocation method is proposed, and developed in detail for a particular case. That case involves operators with even symbol (such as the logarithmic potential) operating on 1-periodic functions; a smooth-spline trial space of odd degree, with constant mesh spacingh=1/n; and a quadrature rule with 2n points (where ann-point quadrature rule would be equivalent to the collocation method). In this setting it is shown that a special quadrature rule (which depends on the degree of the splines and the order of the operator) can yield a maximum order of convergence two powers ofh higher than the collocation method.     

A Finite-element Front-tracking Enthalpy Method for Stefan Problems

A finite-element front-tracking method, which avoids explicittreatment of the jump condition on the phase boundary, is proposed.This method is based on the discretization of a weak enthalpyformulation with isoparametric space—time finite elements.A one-dimensional two-phase problem and a two-dimensional one-phaseproblem are solved by this method. Then the method is appliedto a generalized Stefan problem—the spot-welding problemand extended to the alloy-solidification problem. Numerical experiments show that this method is convergent andunconditionally stable and that second-order convergence canbe expected if the biquadratic elements are used for one-dimensionalproblems. The effectiveness of this method is, in particular,shown in solving the last two problems.     

A cubically convergent Newton-type method under weak conditions

Under weak conditions, we present an iteration formula to improve Newton's method for solving nonlinear equations. The method is free from second derivatives, permitting f^′(x)=0 in some points and per iteration it requires two evaluations of the given function and one evaluation of its derivative. Analysis of convergence demonstrates that the new method is cubically convergent. Some numerical examples illustrate that the algorithm is more efficient and performs better than classical Newton's method.     

A generalized successive overrelaxation method for least squares problems

In this paper a new iterative method is given for solving large sparse least squares problems and computing the minimum norm solution to underdetermined consistent linear systems. The new scheme is called the generalized successive overrelaxation (GSOR) method and is shown to be convergent ifA is full column rank. The GSOR method involves a parameter ρ and an auxiliary matrixP. One can choose matrix P so that the GSOR method only involves matrix and vector operations; therefore the GSOR method is suitable for parallel computations. Besides, the GSOR method can be combined with preconditioning techniques, and therefore can be expected to be more effective. This author's work was supported by Natural Science Foundation of Liaoning Province, China.     

A note on an SOR-like method for augmented systems

Golub et al. (2001, BIT, 41, 71–85) gave a generalizedsuccessive over-relaxation method for the augmented systems.In this paper, the connection between the SOR-like method andthe preconditioned conjugate gradient (PCG) method for the augmentedsystems is investigated. It is shown that the PCG method isat least as accurate (fast) as the SOR-like method. Numericalexamples demonstrate that the PCG method is much faster thanthe SOR-like method.     

A Variant of the Inverted Lanczos Method

In this note we study a variant of the inverted Lanczos method which computes eigenvalue approximates of a symmetric matrix A as Ritz values of A from a Krylov space of A ^–1. The method turns out to be slightly faster than the Lanczos method at least as long as reorthogonalization is not required. The method is applied to the problem of determining the smallest eigenvalue of a symmetric Toeplitz matrix. It is accelerated taking advantage of symmetry properties of the correspond ng eigenvector.This revised version was published online in October 2005 with corrections to the Cover Date.     

A fast Poisson solver

Summary A direct method is developed for the discrete solution of Poisson's equation on a rectangle. The algorithm proposed is of the class of marching methods. The idea is to generalize the classical Cramer's method using Chebyshev matrix polynomials formalism. This results in the solution ofN independent diagonal system of linear equations in the eigenvector coordinate system. An elementary transformation to the original coordinate system is then carried out.     

A space decomposition method for parabolic equations

A convergence proof is given for an abstract parabolic equation using general space decomposition techniques. The space decomposition technique may be a domain decomposition method, a multilevel method, or a multigrid method. It is shown that if the Euler or Crank–Nicolson scheme is used for the parabolic equation, then by suitably choosing the space decomposition, only O(| log τ |) steps of iteration at each time level are needed, where τ is the time-step size. Applications to overlapping domain decomposition and to a two-level method are given for a second-order parabolic equation. The analysis shows that only a one-element overlap is needed. Discussions about iterative and noniterative methods for parabolic equations are presented. A method that combines the two approaches and utilizes some of the good properties of the two approaches is tested numerically. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 27–46, 1998     

A new smoothing quasi-Newton method for nonlinear complementarity problems

A new smoothing quasi-Newton method for nonlinear complementarity problems is presented. The method is a generalization of Thomas’ method for smooth nonlinear systems and has similar properties as Broyden's method. Local convergence is analyzed for a strictly complementary solution as well as for a degenerate solution. Presented numerical results demonstrate quite similar behavior of Thomas’ and Broyden's methods.     

A method for proving polynomial enumeration formulas

We present an elementary method for proving enumeration formulas which are polynomials in certain parameters if others are fixed and factorize into distinct linear factors over Z. Roughly speaking the idea is to prove such formulas by “explaining” their zeros using an appropriate combinatorial extension of the objects under consideration to negative integer parameters. We apply this method to prove a new refinement of the Bender-Knuth (ex-)Conjecture, which easily implies the Bender-Knuth (ex-)Conjecture itself. This is probably the most elementary way to prove this result currently known. Furthermore we adapt our method to q-polynomials, which allows us to derive generating function results as well. Finally we use this method to give another proof for the enumeration of semistandard tableaux of a fixed shape which differs from our proof of the Bender-Knuth (ex-)Conjecture in that it is a multivariate application of our method.