Fast enclosure for all eigenvalues in generalized eigenvalue problems

A fast method for enclosing all eigenvalues in generalized eigenvalue problems Ax=λBx is proposed. Firstly a theorem for enclosing all eigenvalues, which is applicable even if A is not Hermitian and/or B is not Hermitian positive definite, is presented. Next a theorem for accelerating the enclosure is presented. The proposed method is established based on these theorems. Numerical examples show the performance and property of the proposed method. As an application of the proposed method, an efficient method for enclosing all eigenvalues in polynomial eigenvalue problems is also sketched.     

A novel cubically convergent iterative method for computing complex roots of nonlinear equations

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 x^k or k^x, 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.     

A divide-and-conquer method for the tridiagonal generalized eigenvalue problem

We introduce a divide-and-conquer method for the generalized eigenvalue problem Ax = λBx, where A and B are real symmetric tridiagonal matrices and B is positive-definite. It is a generalization of Cuppen's method for the standard eigenvalue problem, B = I, which is based on rank-one modifications. Our method is an alternative to a method developed by Borges and Gragg using restrictions and extensions.     

On the convergence of the modified overrelaxation method

The modified overrelaxation (MSOR) method is applied to a linear system Ax=b, where A has property A. We get bounds for the spectral radius of the iteration matrix of this method, and we achieve convergence conditions for the MSOR method when A is strictly diagonally dominant. We extend our conclusions to another kind of matrices—H,L,M or Stieltjes. In the last section we use the vectorial norms, getting convergence conditions for the MSOR method, when A is a block-H matrix. We also generalize a theorem of Robert's for this kind of matrices.     

Higher order numerical methods for solving fractional differential equations

In this paper we introduce higher order numerical methods for solving fractional differential equations. We use two approaches to this problem. The first approach is based on a direct discretisation of the fractional differential operator: we obtain a numerical method for solving a linear fractional differential equation with order 0<α<1. The order of convergence of the numerical method is O(h ^3?α ). Our second approach is based on discretisation of the integral form of the fractional differential equation and we obtain a fractional Adams-type method for a nonlinear fractional differential equation of any order α>0. The order of convergence of the numerical method is O(h ³) for α≥1 and O(h ^1+2α ) for 0<α≤1 for sufficiently smooth solutions. Numerical examples are given to show that the numerical results are consistent with the theoretical results.     

Local convergence of the method of pseudolinear equations for quasilinear elliptic boundary-value problems

A variant of the method of pseudolinear equations, an iterative method of solving quasilinear partial differential equations, is described for quasilinear elliptic boundary-value problems of the type -[p₁(u_x)]_x - [p₂(u_y)]_y = f on a bounded simply connected two-dimensional domain D. A theorem on local convergence in C^{2, λ}(D) of this variant, which has constant coefficients, is proved. Three other method of solving quasilinear elliptic boundary-value problems, namely. Newton's method, the Ka?anov method and a variant of the method of successive approximations that has constant coefficients, are briefly discussed. Results of a series of numerical experiments in a finite-difference setting of solving quasilinear Dirichlet problems of the above-mentioned type by the method of pseudolinear equations and these three methods are given. These results show that Newton's method converges for stronger nonlinearities than do the other methods, which, in order thereafter, are the Ka?anov method, the method of pseudolinear equations and, last, the method of successive approximations, which converges only for relatively weak nonlinearities. From fastest to slowest, the methods are: the method of successive approximations, the method of pseudolinear equations, Newton's method, the Ka?anov method.     

Computing the first eigenvalue of the p-Laplacian via the inverse power method

In this paper, we discuss a new method for computing the first Dirichlet eigenvalue of the p-Laplacian inspired by the inverse power method in finite dimensional linear algebra. The iterative technique is independent of the particular method used in solving the p-Laplacian equation and therefore can be made as efficient as the latter. The method is validated theoretically for any ball in Rn if p>1 and for any bounded domain in the particular case p=2. For p>2 the method is validated numerically for the square.     

Complete tree subset difference broadcast encryption scheme and its analysis

The subset difference (SD) method proposed by Naor, Naor and Lotspiech is the most popular broadcast encryption (BE) scheme. It is suitable for real-time applications like Pay-TV and has been suggested for use by the AACS standard for digital rights management in Blu-Ray and HD-DVD discs. The SD method assumes the number of users to be a power of two. We propose the complete tree subset difference (CTSD) method that allows the system to support an arbitrary number of users. In particular, it subsumes the SD method and all results proved for the CTSD method also hold for the SD method. Recurrences are obtained for the CTSD scheme to count the number, N(n, r, h), of possible ways r users in the system of n users can be revoked to result in a transmission overhead or header length of h. The recurrences lead to a polynomial time dynamic programming algorithm for computing N(n, r, h). Further, they provide bounds on the maximum possible header length. A probabilistic analysis is performed to obtain an O(r log n) time algorithm to compute the expected header length in the CTSD scheme. Further, for the SD scheme we obtain an explicit limiting upper bound on the expected header length.     

A non-uniform basis order for the discontinuous Galerkin method of the acoustic and elastic wave equations

Here, we solve the time-dependent acoustic and elastic wave equations using the discontinuous Galerkin method for spatial discretization and the low-storage Runge-Kutta and Crank-Nicolson methods for time integration. The aim of the present paper is to study how to choose the order of polynomial basis functions for each element in the computational mesh to obtain a predetermined relative error. In this work, the formula 2p+1≈κhk, which connects the polynomial basis order p, mesh parameter h, wave number k, and free parameter κ, is studied. The aim is to obtain a simple selection method for the order of the basis functions so that a relatively constant error level of the solution can be achieved. The method is examined using numerical experiments. The results of the experiments indicate that this method is a promising approach for approximating the degree of the basis functions for an arbitrarily sized element. However, in certain model problems we show the failure of the proposed selection scheme. In such a case, the method provides an initial basis for a more general p-adaptive discontinuous Galerkin method.     

Eigenvalues of Ax = λBx for real symmetric matrices A and B computed by reduction to a pseudosymmetric form and the HR process

The paper presents a method for solving the eigenvalue problem Ax = λBx, where A and B are real symmetric but not necessarily positive definite matrices, and B is nonsingular. The method reduces the general case into a form Cz = λz where C is a pseudosymmetric matrix. A further reduction of C produces a tridiagonal pseudosymmetric form to which the iterative HR process is applied. The tridiagonal pseudosymmetric form is invariant under the HR transformations. The amount of computation is significantly less than in treating the problem by a general method.     

A new fourth-order cubic spline method for second-order nonlinear two-point boundary-value problems

Bickley [5] had suggested the use of cubic splines for the solution of general linear two-point boundary-value problems. It is well known since then that this method gives only order h² uniformly convergent approximations. But cubic spline interpolation itself is a fourth-order process. We present a new fourth-order cubic spline method for second-order nonlinear two-point boundary-value problems: y″ = f(x, y, y′), a < x < b, α₀y(a) − α₀y′(a) = A, β₀y(b) + β₁y′(b) = B. We generate the solution at the nodal points by a fourth-order method and then use ‘conditions of continuity’ to obtain smoothed approximations for the second derivatives of the solution needed for the construction of the cubic spline solution. We show that our method provides order h⁴ uniformly convergent approximations over [a, b]. The fourth order of the presented method is demonstrated computationally by two examples.     

A posteriori error estimates for the coupling equations of scalar conservation laws

In this paper we prove a posteriori L ₂(L ₂) and L _∞(H ^?1) residual based error estimates for a finite element method for the one-dimensional time dependent coupling equations of two scalar conservation laws. The underlying discretization scheme is Characteristic Galerkin method which is the particular variant of the Streamline diffusion finite element method for δ=0. Our estimate contains certain strong stability factors related to the solution of an associated linearized dual problem combined with the Galerkin orthogonality of the finite element method. The stability factor measures the stability properties of the linearized dual problem. We compute the stability factors for some examples by solving the dual problem numerically.     

Lower bounding aggregation and direct computation for an infinite horizon one-reservoir model

We present a specialized policy iteration method for the computation of optimal and approximately optimal policies for a discrete-time model of a single reservoir whose discharges generate hydroelectric power. The model is described in (Lamond et al., 1995) and (Drouin et al., 1996), where the special structure of optimal policies is given and an approximate value iteration method is presented, using piecewise affine approximations of the optimal return functions. Here, we present a finite method for computing an optimal policy in O(n³) arithmetic operations, where n is the number of states in the associated Markov decision process, and a finite method for computing a lower bound on the optimal value function in O(m²n) where m is the number of nodes of the piecewise affine approximation.     

On the convergence rate and optimization of a numerical method with splitting of boundary conditions for the stokes system in a spherical layer in the axisymmetric case: Modification for thick layers

The convergence rate of a fast-converging second-order accurate iterative method with splitting of boundary conditions constructed by the authors for solving an axisymmetric Dirichlet boundary value problem for the Stokes system in a spherical gap is studied numerically. For R/r exceeding about 30, where r and R are the radii of the inner and outer boundary spheres, it is established that the convergence rate of the method is lower (and considerably lower for large R/r) than the convergence rate of its differential version. For this reason, a really simpler, more slowly converging modification of the original method is constructed on the differential level and a finite-element implementation of this modification is built. Numerical experiments have revealed that this modification has the same convergence rate as its differential counterpart for R/r of up to 5 × 10³. When the multigrid method is used to solve the split and auxiliary boundary value problems arising at iterations, the modification is more efficient than the original method starting from R/r ～ 30 and is considerably more efficient for large values of R/r. It is also established that the convergence rates of both methods depend little on the stretching coefficient η of circularly rectangular mesh cells in a range of η that is well sufficient for effective use of the multigrid method for arbitrary values of R/r smaller than ～ 5 × 10³.     

Projection methods for equations of the second kind

A class of projection methods, differing from the classical projection methods, is studied for the equation y = f + Ky, where K is a compact linear operator in a Banach space E, and f?E, In these methods K is approximated by a finite-rank operator K_n, which is constructed with the aid of certain projection operators, and which satisfies K_nz = Kz for all z belonging to a chosen subspace U_n ? E. Under certain conditions, it is shown that the convergence of the approximate solution is faster than that of any classical projection method based on the subspace U_n. In an example, U_n is taken to consist of piecewise constant functions, and the projections are so chosen that the method becomes equivalent to a single iteration of a classical method, the collocation method; in this case the error (in the supremum norm) is $\text{O(}\text{1}\text{n}{}^2\text{)}$, compared with $\text{O(}\text{1}\text{n}\text{)}$ for the collocation method.     

Analysis of a collocation method for integrating rapidly oscillatory functions

A collocation method for approximating integrals of rapidly oscillatory functions is analyzed. The method is efficient for integrals involving Bessel functions J_v(rx) with a large oscillation frequency parameter r, as well as for many other one- and multi-dimensional integrals of functions with rapid irregular oscillations. The analysis provides a convergence rate and it shows that the relative error of the method is even decreasing as the frequency of the oscillations increases.     

Variable multistep methods for delay differential equations

In this paper, variable stepsize multistep methods for delay differential equations of the type y(t) = f(t, y(t), y(t − τ)) are proposed. Error bounds for the global discretization error of variable stepsize multistep methods for delay differential equations are explicitly computed. It is proved that a variable multistep method which is a perturbation of strongly stable fixed step size method is convergent.     

Convergence of a continuation method under the Hölder condition of the first derivative

The aim of this paper is to describe a continuation method combining the Chebyshev’s method and the convex acceleration of Newton’s method to solve nonlinear equations in Banach spaces. The semilocal convergence analysis of the method is established using recurrence relations under the assumption that the first Fréchet derivative satisfies the Hölder continuity condition. This condition is milder than the usual Lipschitz condition. The computation of second Fréchet derivative is also avoided. Two real valued functions and a real sequence are used to establish a convergence criterion of R-order (1+p), where p∈(0,1] is the order of the Hölder condition. An existence and uniqueness theorem along with the closed form of error bounds is derived in terms of a real parameter α∈[0,1]. Two numerical examples are worked out to demonstrate the efficacy of our convergence analysis. For both the examples, the convergence conditions hold for the Chebyshev’s method (α=0). However, for the convex acceleration of Newton’s method (α=1), these convergence conditions hold for the first example but fail for the second example. For particular values of α, our method reduces to the Chebyshev’s method (α=0) and the convex acceleration of Newton’s method (α=1).     

A local convergence proof for the iterative aggregation method

The iterative aggregation method for the solution of a system of linear algebraic equations x = Ax + b, where A ≥ 0, b ≥ 0, s > 0, and s ′ A < s ′, is proved to be locally convergent. It is shown that the method can be considered a consistent nonstationary iterative method, where the iteration matrix depends on the current iterate, and that some norm of the iteration matrix is less than one in the vicinity of the solution.