An effective iterative method for computing real and complex roots of systems of nonlinear equations

A simple and flexible iterative method is proposed to determine the real or complex roots of any system of nonlinear equations F(x)=0. The idea is based on passing defined functions G_j(x_j),j=1,…,n tangent to F_i(x_j),i,j=1,…,n at an arbitrary starting point. Choosing G_j(x_j) in the form of or or any other reversible function compatible to F_i(x_j), where k is obtained for the best correlation with the function F_i(x_j), gives an added freedom, which in contrast with all existing methods, accelerates the convergence.The method that was first proposed for computing the roots of any single function is now adopted for a system of nonlinear equations. This method is compared to some classical and famous methods such as Newton’s method and Newton-Simpson’s method. The results show the effectiveness and robustness of this new method.     

A perturbed version of an inexact generalized Newton method for solving nonsmooth equations

In this paper, we present the combination of the inexact Newton method and the generalized Newton method for solving nonsmooth equations F(x)?=?0, characterizing the local convergence in terms of the perturbations and residuals. We assume that both iteration matrices taken from the B-differential and vectors F(x ^(k)) are perturbed at each step. Some results are motivated by the approach of C?tina? regarding to smooth equations. We study the conditions, which determine admissible magnitude of perturbations to preserve the convergence of method. Finally, the utility of these results is considered based on some variant of the perturbed inexact generalized Newton method for solving some general optimization problems.     

Krull’s theory for the double gamma function

The Barnes’ G-function G(x) = 1/Γ₂, satisfies the functional equation logG(x + 1) − logG(x) = logΓ(x). We complement W. Krull’s work in Bemerkungen zur Differenzengleichung g(x + 1) − g(x) = φ(x), Math. Nachrichten 1 (1948), 365-376 with additional results that yield a different characterization of the function G, new expansions and sharp bounds for G on x > 0 in terms of Gamma and Digamma functions, a new expansion for the Gamma function and summation formulae with Polygamma functions.     

Compositions of Polynomials with Coefficients in a Given Field

Let F ⊂ K be fields of characteristic 0, and let K[x] denote the ring of polynomials with coefficients in K. Let p(x) = ∑_k = 0ⁿa_kx^k ∈ K[x], a_n ≠ 0. For p ∈ K[x]\F[x], define D_F(p), the F deficit of p, to equal n − max{0 ≤ k ≤ n : a_k∉F}. For p ∈ F[x], define D_F(p) = n. Let p(x) = ∑_k = 0ⁿa_kx^k and let q(x) = ∑_j = 0^mb_jx^j, with a_n ≠ 0, b_m ≠ 0, a_n, b_m ∈ F, b_j∉F for some j ≥ 1. Suppose that p ∈ K[x], q ∈ K[x]\F[x], p, not constant. Our main result is that p ° q ∉ F[x] and D_F(p ° q) = D_F(q). With only the assumption that a_nb_m ∈ F, we prove the inequality D_F(p ° q) ≥ D_F(q). This inequality also holds if F and K are only rings. Similar results are proven for fields of finite characteristic with the additional assumption that the characteristic of the field does not divide the degree of p. Finally we extend our results to polynomials in two variables and compositions of the form p(q(x, y)), where p is a polynomial in one variable.     

Solving nonlinear equations by a new derivative free iterative method

We develop a new simple iteration formula, which does not require any derivatives of f(x), for solving a nonlinear equation f(x) = 0. It is proved that the convergence order of the new method is quadratic. Furthermore, the new method can approximate complex roots. By several numerical examples we show that the presented method will give desirable approximation to the root without a particularly good initial approximation and be efficient for all cases, regardless of the behavior of f(x).     

A smoothing self-adaptive Levenberg-Marquardt algorithm for solving system of nonlinear inequalities

In this paper, we consider the smoothing self-adaptive Levenberg-Marquardt algorithm for the system of nonlinear inequalities. By constructing a new smoothing function, the problem is approximated via a family of parameterized smooth equations H(x) = 0. A smoothing self-adaptive Levenberg-Marquardt algorithm is proposed for solving the system of nonlinear inequalities based on the new smoothing function. The Levenberg-Marquardt parameter μ_k is chosen as the product of μ_k = ∥H^k∥^δ with δ ∈ (0, 2] being a positive constant. We will show that if ∥H^k∥^δ provides a local error bound, which is weaker than the non-singularity, the proposed method converges superlinearly to the solution for δ ∈ (0, 1), while quadratically for δ ∈ [1, 2]. Numerical results show that the new method performs very well for system of inequalities.     

Recursive constructions of -polynomials over

This paper presents procedures for constructing irreducible polynomials over GF(2^s) with linearly independent roots (or normal polynomials or N-polynomials). For a suitably chosen initial N-polynomial F₀(x)GF(2^s) of degree n, polynomials F_k(x)GF(2^s) of degrees n2^k are constructed by iteratively applying the transformation x→x+x^-1, and their roots are shown to form a normal basis of GF(2^sn2k) over GF(2^s). In addition, the sequences are shown to be trace compatible, i.e., the trace map T_{GF(2^sn2k+1)/GF(2^sn2k)} fromGF(2^sn2k+1) onto GF(2^sn2k) maps the roots of F_k+1(x) onto those of F_k(x).     

Global existence of real roots and random Newton flow algorithm for nonlinear system of equations

To solve nonlinear system of equation, F(x) = 0, a continuous Newton flow x _t (t) = V (x) = ?(DF(x))^?1 F(x), x(0) = x ⁰ and its mathematical properties, such as the central field, global existence and uniqueness of real roots and the structure of the singular surface, are studied. We concisely introduce random Newton flow algorithm (NFA) for finding all roots, based on discrete Newton flow x ^j+1 = x ^j + hV (x ^j ) with random initial value x ⁰ and h ∈ (0, 1], and three computable quantities, g _j , d _j and K _j . The numerical experiments with dimension n = 300 are provided.     

A new off-step high order approximation for the solution of three-space dimensional nonlinear wave equations

In this paper, we propose a new high accuracy numerical method of O(k² + k²h² + h⁴) based on off-step discretization for the solution of 3-space dimensional non-linear wave equation of the form u_tt = A(x,y,z,t)u_xx + B(x,y,z,t)u_yy + C(x,y,z,t)u_zz + g(x,y,z,t,u,u_x,u_y,u_z,u_t), 0 < x,y,z < 1,t > 0 subject to given appropriate initial and Dirichlet boundary conditions, where k > 0 and h > 0 are mesh sizes in time and space directions respectively. We use only seven evaluations of the function g as compared to nine evaluations of the same function discussed in  and . We describe the derivation procedure in details of the algorithm. The proposed numerical algorithm is directly applicable to wave equation in polar coordinates and we do not require any fictitious points to discretize the differential equation. The proposed method when applied to a telegraphic equation is also shown to be unconditionally stable. Comparative numerical results are provided to justify the usefulness of the proposed method.     

Fractal oscillations of self-adjoint and damped linear differential equations of second-order

For a prescribed real number s ∈ [1, 2), we give some sufficient conditions on the coefficients p(x) and q(x) such that every solution y = y(x), y ∈ C²((0, T]) of the linear differential equation (p(x)y′)′ + q(x)y = 0 on (0, T], is bounded and fractal oscillatory near x = 0 with the fractal dimension equal to s. This means that y oscillates near x = 0 and the fractal (box-counting) dimension of the graph Γ(y) of y is equal to s as well as the s dimensional upper Minkowski content (generalized length) of Γ(y) is finite and strictly positive. It verifies that y admits similar kind of the fractal geometric asymptotic behaviour near x = 0 like the chirp function y_ch(x) = a(x)S(φ(x)), which often occurs in the time-frequency analysis and its various applications. Furthermore, this kind of oscillations is established for the Bessel, chirp and other types of damped linear differential equations given in the form y″ + (μ/x)y′ + g(x)y = 0, x ∈ (0, T]. In order to prove the main results, we state a new criterion for fractal oscillations near x = 0 of real continuous functions which essentially improves related one presented in [1].     

An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems

We discuss local convergence of Newton’s method to a singular solution x ^* of the nonlinear equations F(x) =  0, for $F:{\mathbb{R}}^n \rightarrow {\mathbb{R}}^n$ . It is shown that an existing proof of Griewank, concerning linear convergence to a singular solution x ^* from a starlike domain around x ^* for F twice Lipschitz continuously differentiable and x ^* satisfying a particular regularity condition, can be adapted to the case in which F′ is only strongly semismooth at the solution. Further, Newton’s method can be accelerated to produce fast linear convergence to a singular solution by overrelaxing every second Newton step. These results are applied to a nonlinear-equations reformulation of the nonlinear complementarity problem (NCP) whose derivative is strongly semismooth when the function f arising in the NCP is sufficiently smooth. Conditions on f are derived that ensure that the appropriate regularity conditions are satisfied for the nonlinear-equations reformulation of the NCP at x ^*.     

On the roots of independence polynomials of almost all very well-covered graphs

If s_k denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G^*. Under certain conditions, any well-covered graph equals G^* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G^*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G^*;x) different from -1, which appears as a root of multiplicity α(G^*)-α(G) for I(G^*;x). We also prove that the real roots of I(G^*;x) are in [-1,-1/2α(G^*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.     

On a semi-smooth Newton method and its globalization

This paper addresses the globalization of the semi-smooth Newton method for non-smooth equations F(x)  =  0 in with applications to complementarity and discretized ℓ¹-regularization problems. Assuming semi-smoothness it is shown that super-linearly convergent Newton methods can be globalized, if appropriate descent directions are used for the merit function |F(x)|². Special attention is paid to directions obtained from the primal-dual active set strategy. K. Ito’s research was partially supported by the Army Research Office under DAAD19-02-1-039.     

On polyvectors of vector spaces and hyperplanes of projective Grassmannians

We investigate relationships between polyvectors of a vector space V, alternating multilinear forms on V, hyperplanes of projective Grassmannians and regular spreads of projective spaces. Suppose V is an n-dimensional vector space over a field F and that A_n-1,k(F) is the Grassmannian of the (k − 1)-dimensional subspaces of PG(V) (1  ? k ? n − 1). With each hyperplane H of A_n-1,k(F), we associate an (n − k)-vector of V (i.e., a vector of ∧^n−kV) which we will call a representative vector of H. One of the problems which we consider is the isomorphism problem of hyperplanes of A_n-1,k(F), i.e., how isomorphism of hyperplanes can be recognized in terms of their representative vectors. Special attention is paid here to the case n = 2k and to those isomorphisms which arise from dualities of PG(V). We also prove that with each regular spread of the projective space PG(2k-1,F), there is associated some class of isomorphic hyperplanes of the Grassmannian A_2k-1,k(F), and we study some properties of these hyperplanes. The above investigations allow us to obtain a new proof for the classification, up to equivalence, of the trivectors of a 6-dimensional vector space over an arbitrary field F, and to obtain a classification, up to isomorphism, of all hyperplanes of A_5,3(F).     

A globally convergent inexact Newton method with a new choice for the forcing term

In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s _k of the Newton’s system J(x _k )s=−F(x _k ) is found. This means that s _k must satisfy a condition like ‖F(x _k )+J(x _k )s _k ‖≤η _k ‖F(x _k )‖ for a forcing term η _k ∈[0,1). Possible choices for η _k have already been presented. In this work, a new choice for η _k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas. Supported by FAPESP, CNPq, PRONEX-Optimization.     

The 2-extendability of 5-connected graphs on surfaces with large representativity

A graph with at least 2k+2 vertices is said to be k-extendable if any independent set of k edges in it extends to a perfect matching. We shall show that every 5-connected graph G of even order embedded on a closed surface F², except the sphere, is 2-extendable if ρ(G)?7−2χ(F²), where ρ(G) stands for the representativity of G on F² and χ(F²) for the Euler characteristic of F².     

On the length of a finite group and of its 2-generator subgroups

The nonsoluble length λ(G) of a finite group G is defined as the minimum number of nonsoluble factors in a normal series of G each of whose quotients either is soluble or is a direct product of nonabelian simple groups. The generalized Fitting height of a finite group G is the least number h = h* (G) such that F* _h (G) = G, where F* ₁ (G) = F* (G) is the generalized Fitting subgroup, and F* _i+1(G) is the inverse image of F* (G/F*_i (G)). In the present paper we prove that if λ(J) ≤ k for every 2-generator subgroup J of G, then λ(G) ≤ k. It is conjectured that if h* (J) ≤ k for every 2-generator subgroup J, then h* (G) ≤ k. We prove that if h* (〈x, x^g 〉) ≤ k for allx, g ∈ G such that 〈x, x^g 〉 is soluble, then h* (G) is k-bounded.     

The strong chromatic index of a class of graphs

The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ^′(G)≤6. Let H₀ be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H₀ and d(x)+d(y)≤5 for any edge xy of G then sχ^′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.     

Rank procedures for some two-population multivariate extended classification problems

Given independent samples from three multivariate populations with cumulative distribution functions F⁽¹⁾(x), F⁽²⁾(x), and F⁽⁰⁾(x) = θF⁽¹⁾(x) + (1 ? θ)F⁽²⁾(x), where 0 ≤ θ ≤ 1 is unknown, the three-action problem involving decision as to whether the value of θ is high, low, or intermediate, is considered. A class of consistent procedures based on the relative spacing of three sample averages of linearly compounded rank scores is formulated. The asymptotic operating characteristics of the procedures when F⁽¹⁾ and F⁽²⁾ come close together are studied and the best choice of the compounding coefficients in terms of these considered. The consequence of using estimates of the best coefficients on the asymptotic operating characteristics is also examined.     

Two linear equations in formal power series

The equations [gradφ(x)]^TF(x)=h(x) and F(ψ(x))–ψ(x) are considered. They arise in the stability theory of differential and difference equations. The scalar function h(x) is a given, and the function ψ(x) an unknown, formal power series in the n indeterminates x=(x₁,…,x_n)^T, and h(0)=ψ=0; the elements of the n×n matrix F(x) are also formal power series in x, F(0)=0. It is shown that the solvability of both equations depends on the eigenvalues of the Jacobian F_x(0).