The collocation method for the numerical approximation of the periodic solutions of functional differential equations

A collocation method with trigonometric trial functions is presented form-order non-linear functional differential equations with periodicity boundary conditions. In general, uniform approximation of an isolated solution and of its firstm?1 derivatives is achieved, while them-derivative is approximated in mean square. In some special cases we have also the uniform approximation of them-derivative. The solution of then-th non-linear collocation equation may be approximated by Newton's iteration with an arbitrary starting point belonging to a suitable neighbourhood of an isolated solution, for alln>n ₀ withn ₀ large enough.     

Algebraic approach to the interval linear static identification,tolerance, and control problems,or one more application of kaucher arithmetic

In this paper, theidentification problem, thetolerance problem, and thecontrol problem are treated for the interval linear equation Ax=b. These problems require computing an inner approximation of theunited solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, of thetolerable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, and of thecontrollable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?b ∈ b)(Ax ∈b)} respectively. Analgebraic approach to their solution is developed in which the initial problem is replaced by that of finding analgebraic solution of some auxiliary interval linear system in Kaucher extended interval arithmetic. The algebraic approach is proved almost always to give inclusion-maximal inner interval estimates of the solutionsets considered. We investigate basic properties of the algebraic solutions to the interval linear systems and propose a number of numerical methods to compute them. In particular, we present the simple and fastsubdifferential Newton method, prove its convergence and discuss numerical experiments.     

Oscillation and nonoscillation for second-order linear difference equations

New oscillation and nonoscillation theorems are obtained for the second-order linear difference equation Δ²x_n−1 + p_nx_n = 0, where if p_n^∞_n=1 is a real sequence with p_n ≥ 0.     

ε-Optimality for bicriteria programs and its application to minimum cost flows

A subsetS?X of feasible solutions of a multicriteria optimization problem is called ε-optimal w.r.t. a vector-valued functionf:X→Y \( \subseteq \) ? ^K if for allx∈X there is a solutionz _x∈S so thatf _k(z _x)≤(1+ε)f _k (x) for allk=1,...,K. For a given accuracy ε>0, a pseudopolynomial approximation algorithm for bicriteria linear programming using the lower and upper approximation of the optimal value function is given. Numerical results for the bicriteria minimum cost flow problem on NETGEN-generated examples are presented.     

Application of the complex model to liquid metal-salt systems

The complex model developed by Hoch and Arpshofen is used to describe the phase diagram of several alkali halide-alkali metal systems. In the first approximation, Δ_m^ex = ΔH_m = n(x ? xⁿ)w where n is the size of the complex (number of atoms), W is the interaction parameter, and x is the atom fraction of the compoennt with the lower binding capcacity. In several systems the complete form of the above equation is applied, including deviation from ramdomness and vibrational entropy contributions.If the liquid is single-phase, the data are calculated from the liquidus line. If a miscibility gap exists in the liquid, it is used to calculate the parameters.The model requires only two constants (n and W), and thus can be used to calculate phase diagrams, where relatively little information is available. As an example, the calculation of the U-UO₂, Th-ThO₂ phase diagram is outlined.     

Higher-order polynomial approximation

A new approach to polynomial higher-order approximation (smoothing) based on the basic elements method (BEM) is proposed. A BEM polynomial of degree n is defined by four basic elements specified on a three-point grid: x ₀ + α < x ₀ < x ₀ + β, αβ <0. Formulas for the calculation of coefficients of the polynomial model of order 12 were derived. These formulas depend on the interval length, continuous parameters α and β, and the values of f ^(m)(x ₀+ν), ν = α, β, 0, m = 0,3. The application of higher-degree BEM polynomials in piecewise-polynomial approximation and smoothing improves the stability and accuracy of calculations when the grid step is increased and reduces the computational complexity of the algorithms.     

Monotone Einschließung von Inversen positiver Elemente durch Verfahren vom Schulz-Typ

The conditional iterationx _n+1 =sup (x _n ,x _n +x _n (e?ax _n )),y _n?1 =inf (y _n ,x _n +y _n (e?ax _n )) generating sequences (x _n ) and (y _n ) is considered in partially ordered spaces. Under certain conditions it is shown, that the inversea ^?1 of a positive elementa≧0 is monotonously enclosed in the sensex _n ≦x _n+1 ≦a ^?1 ≦y _n+1 ≦y _n and that (x _n ) and (y _n ) converge toa ^?1 quadratically.     

A quadratically convergent method for computing simple singular roots and its application to determining simple bifurcation points

We present an efficient method for computing roots of mappings on ? ⁿ in the case where the Jacobian has the rankn?1 at the root. For the accurate determination of such a rootx*∈? ⁿ an auxiliary system ofn equations inn+1 variables is constructed which possesses (x ^*, 1) as a turning point. This turning point can be computed by direct methods. We use an adapted method which requires only the solution of (n+1)-dimensional systems of linear equations and the evaluation of one Jacobian and 5 function values per step. This techniques is successfully applied to compute simple bifurcation points by means of a suitable system of nonlinear equations which has the properties mentioned above.     

Minimierung des Rechenaufwandes bei Globalisierungen spezieller Iterationsverfahren vom Typ Minimales Residuum

Local iteration methods for the solution of nonlinear operator equationsT(x)=0 can be “globalized” by the method of embedding. This means that the initial valuex ₀ need not be in the neighbourhood of a solution \(\bar x\) . We restrict ourselves to a stepwise calculation — see [17] — where one solves the chain of problems:T(x, s _i )=0, 0=s ₀<s ₁<...<s _N =1 by a local iteration method with the solutionx _i?1 ofT(x, s _i?1)=0 used as initial vector forT(x, s _i )=0. In this paper we examine methods of minimal-residue-type. Results on the minimization of the whole effort by selection of an “optimal” step width can be obtained. Furthermore, a global convergence acceleration can be reached by suitable adaption of (linear) interpolation on the step width. The reslts obtained can be transferred without difficulties to any other local iteration method which is based on the principle contraction.     

A comparison of point and ball iterations in the contractive mapping case

In applications, one of the basic problems is to solve the fixed point equationx=Tx withT a contractive mapping. Two theorems which can be implemented computationally to verify the existence of a solutionx ^* to the equation and to obtain a convergent approximate solution sequence {x _n } are the classical Banach contraction mapping theorem and the newly established global convergence theorem of the ball algorithms in You, Xu and Liu [16]. These two theorems are compared on the basis of sensitivity, precision, computational complexity and efficiency. The comparison shows that except for computational complexity, the latter theorem is of far greater sensivity, precision and computational efficiency. This conclusion is supported by a number of numerical examples.     

Numerische Lösung von Anfangswertaufgaben gewöhnlicher Differentialgleichungen n-ter Ordnung

In the present paper a new method is given for the numerical treatment of the initial problemsy ⁽ⁿ⁾=f(x,y,y′, ...,y ^(n?1),y ⁽ⁱ⁾ (x _o )=y _o ⁽ⁱ⁾ , i=0, 1, ...,n?1. This method is an one-step process of order four. For a class of linear differential equations the exact solution is obtained. Moreover some numerical results are presented.     

A pipelined computer architecture for unified elementary function evaluation

A pipelined computer architecture for rapid consecutive evaluation of several elementary functions (x/y, √x, sin x, cos, x, e^x, ln x, …) using basic CORDIC algorithms is proposed. Continued products iterations of the form (1 + σ_im 2^?k) allow linking n-identical ALU structures to permit n different function evaluations. New algorithms for sin^?1, cos^?1, cot^?1, sinh^?1, cosh^?1 and x^v are developed. Lastly, a new functional efficiency is defined for pipeline architectures which compares favorably to iterative arrays.Index terms—Digital Arithmetic, Pipeline, Unified Elementary Functions, Iterative Algorithms, CORDIC     

A linear-time algorithm for linearL 1 approximation of points

In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL ₁ norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n ³) naive algorithm can be easily obtained based on some simple characteristics of an optimumL ₁ solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL ₁ approximation of many points in practice. The complexity ofL ₁ linear approximation of a piecewise linear function is also touched upon.     

Existence of nonoscillatory solutions of higher-order neutral delay difference equations with variable coefficients

In this paper, we consider the following higher-order neutral delay difference equations with positive and negative coefficients: Δ^m(x_n + cx_n−k) + p_nx_n−r − q_nx_n−l = 0, n≥n₀, where c ϵ R, m ⩾ 1, k ⩾ 1, r, l ⩾ 0 are integers, and {p_n}^∞_n=n0 and {q_n}_n=n0^∞ are sequences of nonnegative real numbers. We obtain the global results (with respect to c) which are some sufficient conditions for the existences of nonoscillatory solutions.     

Efficient uncertainty quantification with the polynomial chaos method for stiff systems

The polynomial chaos (PC) method has been widely adopted as a computationally feasible approach for uncertainty quantification (UQ). Most studies to date have focused on non-stiff systems. When stiff systems are considered, implicit numerical integration requires the solution of a non-linear system of equations at every time step. Using the Galerkin approach the size of the system state increases from n to S × n, where S is the number of PC basis functions. Solving such systems with full linear algebra causes the computational cost to increase from O(n³) to O(S³n³). The S³-fold increase can make the computation prohibitive. This paper explores computationally efficient UQ techniques for stiff systems using the PC Galerkin, collocation, and collocation least-squares (LS) formulations. In the Galerkin approach, we propose a modification in the implicit time stepping process using an approximation of the Jacobian matrix to reduce the computational cost. The numerical results show a run time reduction with no negative impact on accuracy. In the stochastic collocation formulation, we propose a least-squares approach based on collocation at a low-discrepancy set of points. Numerical experiments illustrate that the collocation least-squares approach for UQ has similar accuracy with the Galerkin approach, is more efficient, and does not require any modification of the original code.     

Analysis of a simple factorization algorithm

The probability that the k^th largest prime factor of a number n is at most n^x is shown to approach a limit F_k(x) as n → ∞. Several interesting properties of F_k(x) are explored, and numerical tables are given. These results are applied to the analysis of an algorithm commonly used to find all prime factors of a given number. The average number of digits in the k^th largest prime factor of a random m-digit number is shown to be asymptotically equivalent to the average length of the k^th longest cycle in a permutation on m objects.     

Ein kubisch konvergentes Einschließungsverfahren zur Inversion positiver Elemente

The iteration $$y_{n + 1} = \sup (y_n ,x_n + x_n (e - ax_n )),x_{n + 1} = \inf (x_n ,x_n + y_{n + 1} (e - ax_n ))$$ generating sequences (x _n ) and (y _n ) is considered in normed, partially ordered rings. Under certain conditions it is shown, that the inversea ^?1 of an elementa≧0 is monotonously enclosed and that both sequences converge toa ^?1 with the order three.     

Numerical differentiation of implicitly defined space curves

In this note we develop a simple finite differencing device to calculate approximations of derivativesx′(0),x″(0),x ⁽³⁾(0), … of regular solution curvesx: ? ?s →x(s) ∈ ? ⁿ of nonlinear systems of equationsg(x)=0,g∈C ^k (? ^{n + 1}, ? ⁿ ) without having to compute points on the solution arcx(s). The derivative vectorsx′(0),x″(0),x ⁽³⁾(0),… can be used in the numerical approximation of the solution setg ^?1(0) in two ways. On one hand they can be applied to construct higher order predictors to be used in predictor-corrector branch following procedures. On the other they serve as order determining basis functions in the Reduced Basis Method. The performance of the differencing method is demonstrated by some numerical examples.     

On Approximating Polygonal Curves in Two and Three Dimensions

Given a polygonal curve P =[p₁, p₂, . . . , p_n], the polygonal approximation problem considered calls for determining a new curve P′ = [p′₁, p′₂, . . . , p′_m] such that (i) m is significantly smaller than n, (ii) the vertices of P′ are an ordered subset of the vertices of P, and (iii) any line segment [p′_A, p′_{A + 1} of P′ that substitutes a chain [p_B, . . . , p_C] in P is such that for all i where B ≤ i ≤ C, the approximation error of p_i with respect to [p′_A, p′_{A + 1}], according to some specified criterion and metric, is less than a predetermined error tolerance. Using the parallel-strip error criterion, we study the following problems for a curve P in R^d, where d = 2, 3: (i) minimize m for a given error tolerance and (ii) given m, find the curve P′ that has the minimum approximation error over all curves that have at most m vertices. These problems are called the min-# and min-ϵ problems, respectively. For R² and with any one of the L₁, L₂, or L_∞ distance metrics, we give algorithms to solve the min-# problem in O(n²) time and the min-ϵ problem in O(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_∞ metrics are used then the min-# problem can be solved in O(n²) time and the min-ϵ problem can be solved in O(n³) time. If distances are computed using the L₂ metric then the min-# and min-ϵ problems can be solved in O(n³) and O(n³ log n) time, respectively. All of our algorithms exhibit O(n²) space complexity. Finally, we show that if it is not essential to minimize m, simple modifications of our algorithms afford a reduction by a factor of n for both time and space.     

Square Difference Labeling of Some Graphs

The paper considers some methods to construct square difference labeling of cactus cycle C _m ⁽ⁿ⁾ of single-point connection of n copies of cycle C_m and n copies of path P₂ of single-point connection of n copies of cycle C_m and path P_n+1 as well as disjoint union of single-point connection of n copies of cycle C_m with path P_n.