共查询到20条相似文献,搜索用时 15 毫秒
1.
The domination numbers of cylindrical grid graphs 总被引:1,自引:0,他引:1
Mrinal Nandi 《Applied mathematics and computation》2011,217(10):4879-4889
Let γ(Pm □ Cn) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs Pm, the path of length m, m ? 2 and the graph Cn, the cycle of length n, n ? 3. In this paper, methods to find the domination numbers of graphs of the form Pm □ Cn with n ? 3 and m = 2, 3 and 4 are proposed. Moreover, bounds on domination numbers of the graphs P5 □ Cn, n ? 3 are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs. 相似文献
2.
This paper develops a gradient based and a least squares based iterative algorithms for solving matrix equation AXB + CXTD = F. The basic idea is to decompose the matrix equation (system) under consideration into two subsystems by applying the hierarchical identification principle and to derive the iterative algorithms by extending the iterative methods for solving Ax = b and AXB = F. The analysis shows that when the matrix equation has a unique solution (under the sense of least squares), the iterative solution converges to the exact solution for any initial values. A numerical example verifies the proposed theorems. 相似文献
3.
In this paper we consider a problem of preemptive scheduling of multiprocessor tasks on dedicated processors in order to minimize the sum of completion times. Using a standard notation, our problem can be denoted as P ∣ fixj, pmtn ∣ ∑Cj. We give a polynomial-time algorithm to solve P ∣ fixj, G = {P4, dart}-free, pmtn ∣ ∑Cj problem. This result generalizes the following problems: P2 ∣ fixj, pmtn ∣ ∑Cj, P ∣ ∣fixj∣ ∈ {1, m}, pmtn ∣ ∑Cj and P4 ∣ fixj = 2, pmtn ∣ ∑Cj. 相似文献
4.
Jovana D?uni? Miodrag S. Petkovi?Ljiljana D. Petkovi? 《Applied mathematics and computation》2011,217(19):7612-7619
Using an interactive approach which combines symbolic computation and Taylor’s series, a wide family of three-point iterative methods for solving nonlinear equations is constructed. These methods use two suitable parametric functions at the second and third step and reach the eighth order of convergence consuming only four function evaluations per iteration. This means that the proposed family supports the Kung-Traub hypothesis (1974) on the upper bound 2m of the order of multipoint methods based on m + 1 function evaluations, providing very high computational efficiency. Different methods are obtained by taking specific parametric functions. The presented numerical examples demonstrate exceptional convergence speed with only few function evaluations. 相似文献
5.
Hou-Biao Li Ting-Zhu HuangYong Zhang Xing-Ping LiuTong-Xiang Gu 《Applied mathematics and computation》2011,218(2):260-270
Recently, a Newton’s iterative method is attracting more and more attention from various fields of science and engineering. This method is generally quadratically convergent. In this paper, some Chebyshev-type methods with the third order convergence are analyzed in detail and used to compute approximate inverse preconditioners for solving the linear system Ax = b. Theoretic analysis and numerical experiments show that Chebyshev’s method is more effective than Newton’s one in the case of constructing approximate inverse preconditioners. 相似文献
6.
In this paper, the nonlinear matrix equation X + A∗XqA = Q (q > 0) is investigated. Some necessary and sufficient conditions for existence of Hermitian positive definite solutions of the nonlinear matrix equations are derived. An effective iterative method to obtain the positive definite solution is presented. Some numerical results are given to illustrate the effectiveness of the iterative methods. 相似文献
7.
Heng-you Lan Yi-shun CuiYu Fu 《Communications in Nonlinear Science & Numerical Simulation》2012,17(4):1844-1851
In this paper, we consider and study a class of general nonlinear operator inclusion couples involving (A, η, m)-resolvent operators and relaxed cocoercive type operators in Hilbert spaces. We also construct a new perturbed iterative algorithm framework with errors and investigate variational graph convergence analysis for this algorithm framework in the context of solving the nonlinear operator inclusion couple along with some results on the resolvent operator corresponding to (A, η, m)-maximal monotonicity. The obtained results improve and generalize some well known results in recent literatures. 相似文献
8.
Jing Cai 《Applied mathematics and computation》2010,217(1):117-4466
Nonlinear matrix equation Xs + A∗X−tA = Q, where A, Q are n × n complex matrices with Q Hermitian positive definite, has widely applied background. In this paper, we consider the Hermitian positive definite solutions of this matrix equation with two cases: s ? 1, 0 < t ? 1 and 0 < s ? 1, t ? 1. We derive necessary conditions and sufficient conditions for the existence of Hermitian positive definite solutions for the matrix equation and obtain some properties of the solutions. We also propose iterative methods for obtaining the extremal Hermitian positive definite solution of the matrix equation. Finally, we give some numerical examples to show the efficiency of the proposed iterative methods. 相似文献
9.
Xi LiNan-jing Huang 《Applied mathematics and computation》2011,217(22):9053-9061
In this paper, a concept of graph convergence concerned with the H(·, ·)-accretive operator is introduced in Banach spaces and some equivalence theorems between of graph-convergence and resolvent operator convergence for the H(·, ·)-accretive operator sequence are proved. As an application, a perturbed algorithm for solving a class of variational inclusions involving the H(·, ·)-accretive operator is constructed. Under some suitable conditions, the existence of the solution for the variational inclusions and the convergence of iterative sequence generated by the perturbed algorithm are also given. 相似文献
10.
Yuan-Ming Wang 《Applied mathematics and computation》2010,217(5):2251-2259
The aim of this paper is to investigate the existence of iterative solutions for a class of 2nth-order nonlinear multi-point boundary value problems. The multi-point boundary condition under consideration includes various commonly discussed boundary conditions, such as three- or four-point boundary condition, (n + 2)-point boundary condition and 2(n − m)-point boundary condition. The existence problem is based on the method of upper and lower solutions and its associated monotone iterative technique. A monotone iteration is developed so that the iterative sequence converges monotonically to a maximal solution or a minimal solution, depending on whether the initial iteration is an upper solution or a lower solution. Two examples are presented to illustrate the results. 相似文献
11.
There is a vast literature on finding simple roots of nonlinear equations by iterative methods. These methods can be classified by order, by the information used or by efficiency. There are very few optimal methods, that is methods of order 2m requiring m + 1 function evaluations per iteration. Here we give a general way to construct such methods by using inverse interpolation and any optimal two-point method. The presented optimal multipoint methods are tested on numerical examples and compared to existing methods of the same order of convergence. 相似文献
12.
Yabo Chen 《Applied mathematics and computation》2010,217(1):230-236
A new matrix based iterative method is presented to compute common symmetric solution or common symmetric least-squares solution of the pair of matrix equations AXB = E and CXD = F. By this iterative method, for any initial matrix X0, a solution X∗ can be obtained within finite iteration steps if exact arithmetic was used, and the solution X∗ with the minimum Frobenius norm can be obtained by choosing a special kind of initial matrix. In addition, the unique nearest common symmetric solution or common symmetric least-squares solution to given matrix in Frobenius norm can be obtained by first finding the minimum Frobenius norm common symmetric solution or common symmetric least-squares solution of the new pair of matrix equations. The given numerical examples show that the matrix based iterative method proposed in this paper has faster convergence than the iterative methods proposed in [1] and [2] to solve the same problems. 相似文献
13.
Maria Adam 《Applied mathematics and computation》2011,217(9):4699-4709
For an n × n normal matrix A, whose numerical range NR[A] is a k-polygon (k ? n), an n × (k − 1) isometry matrix P is constructed by a unit vector υ∈Cn, and NR[P∗AP] is inscribed to NR[A]. In this paper, using the notations of NR[P∗AP] and some properties from projective geometry, an n × n diagonal matrix B and an n × (k − 2) isometry matrix Q are proposed such that NR[P∗AP] and NR[Q∗BQ] have as common support lines the edges of the k-polygon and share the same boundary points with the polygon. It is proved that the boundary of NR[P∗AP] is a differentiable curve and the boundary of the numerical range of a 3 × 3 matrix P∗AP is an ellipse, when the polygon is a quadrilateral. 相似文献
14.
A fast and simple iterative method with cubic convergent is proposed for the determination of the real and complex roots of any function F(x) = 0. The idea is based upon passing a defined function G(x) tangent to F(x) at an arbitrary starting point. Choosing G(x) in the form of xk or kx, where k is obtained for the best correlation with the function F(x), gives an added freedom, which in contrast to all existing methods, accelerates the convergence. Also, this new method can find complex roots just by a real initial guess. This is in contrast to many other methods like the famous Newton method that needs complex initial guesses for finding complex roots. The proposed method is compared to some new and famous methods like Newton method and a modern solver that is fsolve command in MATLAB. The results show the effectiveness and robustness of this new method as compared to other methods. 相似文献
15.
The two dimensional diffusion equation of the form is considered in this paper. We try a bi-cubic spline function of the form as its solution. The initial coefficients Ci,j(0) are computed simply by applying a collocation method; Ci,j = f(xi, yj) where f(x, y) = u(x, y, 0) is the given initial condition. Then the coefficients Ci,j(t) are computed by X(t) = etQX(0) where X(t) = (C0,1, C0,1, C0,2, … , C0,N, C1,0, … , CN,N) is a one dimensional array and the square matrix Q is derived from applying the Galerkin’s method to the diffusion equation. Note that this expression provides a solution that is not necessarily separable in space coordinates x, y. The results of sample calculations for a few example problems along with the calculation results of approximation errors for a problem with known analytical solution are included. 相似文献
16.
We consider a bin packing problem where the number of different object weights is fixed to C. We analyze a simple approximate approach and show that it leads to an asymptotically exact polynomial algorithm with absolute error 0 if C = 2, at most 1 if 1 < C ? 6, and at most 1 + ⌊(C − 1)/3⌋ if C > 6. A consequence of our analysis is a new upper bound on the gap between the optimal value of the problem at hand and the round-up of the optimal value of the linear relaxation of its Gilmore–Gomory formulation. 相似文献
17.
Fengxia Zhang Ying LiWenbin Guo Jianli Zhao 《Applied mathematics and computation》2011,217(24):10049-10057
In this article we give some formulas for the maximal and minimal ranks of the submatrices in a least squares solution X to AXB = C. From these formulas, we derive necessary and sufficient conditions for the submatrices to be zero and other special forms, respectively. Finally, some Hermitian properties for least squares solution to matrix equation AXB = C are derived. 相似文献
18.
Numerical methods of finding the roots of a system of non-linear algebraic equations are treated in this paper. This paper attempts to give an answer to the selection of the most efficient method in a complex problem of Celestial Dynamics, the so-called ring problem of (N + 1) bodies. We apply Newton and Broyden’s method to these problems and we investigate, by means of their use, the planar equilibrium points, the five equilibrium zones, which are symbolized by A1, A2, B, C2, and C1 (by order of appearance from the center O to the periphery of the imaginary circle on which the primaries lie) [T.J. Kalvouridis, A planar case of the N + 1 body problem: the ring problem. Astrophys. Space Sci. 260 (3) (1999) 309-325], and the attracting regions of the system. The efficiency of these methods is studied through a comparative process. The obtained results are demonstrated in figures and are discussed. 相似文献
19.
Extended one-step schemes of exponential type are introduced for solving singularly perturbed Volterra integro-differential problems. These schemes are of order (m + 1), m = 0, 1, 2, …, when the perturbation parameter, ε, is fixed. These schemes have the property that if ε is of order h they reduced to first order of accuracy and optimal when ε → 0. Stability analysis of these schemes are presented. Numerical results and comparisons with other schemes are presented. 相似文献
20.
Muhammad Aslam Noor Farooq Ahmed Shah 《Journal of Applied Mathematics and Computing》2009,31(1-2):247-254
In this paper, we use the variational iteration technique to suggest some new iterative methods for solving nonlinear equations f(x)=0. We also discuss the convergence criteria of these new iterative methods. Comparison with other similar methods is also given. These new methods can be considered as an alternative to the Newton method. We also give several examples to illustrate the efficiency of these methods. This technique can be used to suggest a wide class of new iterative methods for solving system of nonlinear equations. 相似文献