An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

On some convergence results for FDM with irregular mesh

The proof of convergence of the finite difference method with arbitrary irregular meshes for some class of elliptic problems is presented. By the use of the truncation error technique and stability analysis it was showed that $\text{max}{}_{\mathrm{i}}\text{¦u}{}^{\mathrm{i}}\text{? u}{}_{\mathrm{h}}{}^{\mathrm{i}}\text{¦? Ch}$, i.e., the solution u_h converges linearly with the size of the star. Correctness of this theorem was also confirmed by numerical tests.     

The complexity of a multiprocessor task assignment problem without deadlines

We construct a sequence of monotone Boolean functions h_n :{0, 1}ⁿ→{0, 1}ⁿ, such that the monotone complexity of h_n is of order $\text{n}{}^2\text{log n}$. This result includes the largest known lower bound of this kind. Previously there were an $\text{Ω(n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{)}$ bound for the Boolean matrix product, an $\text{Ω(n}{}^{\mathrm{<mtext>5</mtext><mtext>3</mtext>}}\text{)}$ bound for Boolean sums and an $\text{Ω(}\text{n}{}^2\text{log}{}^2\text{n}\text{)}$ bound by the author for the same functions h_n. This new lower bound is proved by new methods which probably will turn out to be useful also for other problems.     

Unbounded solutions of quasi-linear difference equations

We study positive increasing solutions of the nonlinear difference equation $\text{δ(a}{}_{\mathrm{n}}\text{φ}{}_{\mathrm{p}}\text{(δχ}{}_{\mathrm{n}}\text{))=b}{}_{\mathrm{n}}\text{f(χ}{}_{\mathrm{n+1}}\text{,}\text{φ}{}_{\mathrm{p}}\text{(u)=|u|}{}^{\mathrm{p-2}}\text{u,}\text{p>1}$ where {a_n}, {b_n} are positive real sequences for n ≥ 1, fR → R is continuous with uf(u) > 0 for u ≠ 0. A full characterization of limit behavior of all these solutions in terms of a_n, b_n is established. Examples, showing the essential role of used hypotheses, are also included. The tools used are the Schauder fixed-point theorem and a comparison method based on the reciprocity principle.     

Curved finite element methods for the solution of singular integral equations on surfaces in R3

We have shown in [1]that the singular integral equation (1.2) on a closed surface Γ of R³ admits a unique solution q and is variational and coercive in the Hilbert space $\text{H}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}$(Γ). In this paper, with the help of curved finite elements, we introduce an approximate surface Γ_h, and an approximate problem on Γ_h, whose solution is q_h. Then we study the error of approximation |q ? q_h| in some Hubert spaces and also the associated error |u ? u_h| of the potential.     

Matrix equations over rings

The main purpose of this work is to establish necessary conditions and sufficient conditions for the existence of a solution of matrix equations whose coefficient matrices have elements belonging to the ring $\text{R=}\text{C}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}$ of polynomials in n variables with complex coefficients and the ring $\text{R=}\text{R}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}{}^{\mathrm{n}}$ of rational functions a(z₁,z₂,…z_n)b(z₁,z₂,…,z_n)^?1 with real coefficients and b(z₁,z₂,…,z_n)≠0 for all (z₁,z₂,…,z_n) in Rⁿ. Results obtained are useful in multidimensional systems theory and elsewhere.     

Mathematical foundations of Bézier's technique

Bezier's method is one of the most famous in computational geometry. In his book Numerical control Bezier gives excellent expositions of the mathematical foundations of this method. In this paper a new expression of the functions {f_n,i(u)}

$\text{f}{}_{\mathrm{n,i}}\text{(u)=1?}\text{Σ}\text{p=0}\text{i?1}\text{C}{}^{\mathrm{p}}{}_{\mathrm{n}}\text{u}{}^{\mathrm{p}}\text{(1?u)}{}^{\mathrm{n?p}}\text{(i=1,2,…,n)}$

is obtained.Using this formula, we have not only derived some properties of the functions {f_n,i(u)} (for instance $\text{f}{}_{\mathrm{n,n}}\text{(u) < f}{}_{\mathrm{n,n?1}}\text{(u)<...<f}{}_{\mathrm{n,1}}\text{(u)}\text{u}\text{? [0, 1]}$ and functions {f_n,i(u)} increase strictly at [0, 1] etc) but also simplified systematically all the mathematical discussions about Bezier's method.Finally we have proved the plotting theorem completely by matrix calculation.     

An accurate algorithm for computing the eigenvalues of a polygonal membrane

For a polygonal domain Ω, we consider the eigenvalue problem Δu + λu = 0 in Ω, u = 0 on the boundary of Ω. Ω is decomposed into subdomains Ω₁, Ω₂,...; on each $\text{Ω}{}_{\mathrm{i}}$, u is approximated by a linear combination of functions which satisfy the equation Δu + Δu = 0 and continuity conditions are imposed at the boundaries of the subdomains. We propose a non-conventional method based on the use of a Rayleigh quotient. We present numerical examples and a proof of the exponential convergence of the algorithm.     

Existence of multiple solutions for second-order discrete boundary value problems

We give conditions on ƒ involving pairs of discrete lower and discrete upper solutions which lead to the existence of at least three solutions of the discrete two-point boundary value problem $\text{y}{}_{\mathrm{<mtext>k</mtext><mtext>+1</mtext>}}\text{− 2y}{}_{\mathrm{k}}\text{+ y}{}_{\mathrm{<mtext>k</mtext><mtext>-1</mtext>}}\text{+ ƒ(k,y}{}_{\mathrm{k}}\text{,v}{}_{\mathrm{k}}\text{) = 0, for k = 1,…, n − 1, y}{}_0\text{= 0 = y}{}_{\mathrm{n}}$, where ƒ is continuous and v_k = y_k − y_k−1, for k = 1,…,n. In the special case $\text{ƒ(k,t,p) = ƒ(t) ≥ 0}$, we give growth conditions on ƒ and apply our general result to show the existence of three positive solutions. We give an example showing this latter result is sharp. Our results extend those of Avery and Peterson and are in the spirit of our results for the continuous analogue.     

Numerical conformal mapping of exterior domains

The work of the present paper is closely related to the two numerical procedures described in [11], for determining approximàtions to the function which maps conformally a bounded simply-connected domain $\text{Ω}{}_{\mathrm{I}}$, with boundary ?Ω, onto the unit disc. Here we consider the use of these procedures for the solution of the corresponding exterior problem, i.e. the problem of determining approximations to the mapping function which maps conformally the exterior domain $\text{Ω =}\text{compl}\text{(Ω}{}_{\mathrm{I}}\text{∪ ?Ω)}$ onto the unit disc.     

Solution errors in finite element analysis

The development of the finite element method so far indicates that it is a discretization technique especially suited for positive definite, self-adjoint, elliptic systems, or systems with such components. The application of the method leads to the discretized equations in the form of $\text{u}\text{?}\text{=}\text{f(u)}$, where u lists the response of the discretized system at n preselected points called nodes. Instead of explicit expressions, vector function f and its Jacobian f,_u are available only numerically for a numerically given u. The solution of $\text{u}\text{?}\text{=}\text{f(u)}$ is usually a digital computer. Due to finiteness of the computer wordlength, the numerical solution $\text{u}{}_{\mathrm{c}}$ is in general different from u. Let $\text{u}\text{(}\text{x}\text{, t)}$ denote the actual response of the system in continuum at points corresponding to those of u. In the literature. $\text{u}\text{(}\text{x}\text{, t)-}\text{u}$ is called the discretization errors, $\text{u}\text{-}\text{u}{}_{\mathrm{c}}$ the round-off errors, and the s is. $\text{u}\text{(}\text{x}\text{, t)-}\text{u}{}_{\mathrm{c}}$ is called the solution errors. In this paper, a state-of-the-art survey is given on the identification, growth, relative magnitudes, estimation, and control of the components of the solution errors.     

On the stability of convolution feedback systems with dynamical feedback

This paper considers distributed n-inputn-output convolution feedback systems characterized by $\text{y = G}{}_1\text{1e}$, $\text{z = G}{}_2\text{1y}$ and e = u ? z, where the forward path transfer function $\text{G}\text{?}{}_1$ and the feedback path transfer function $\text{G}\text{?}{}_2$ both contain a real single unstable pole at different locations. Theorem 1 gives necessary and sufficient conditions for both input-error and input-output stability. In addition to usual conditions that guarantee input-error stability a new condition is found which results in the fact that input-error stability will guarantee input-output stability. These conditions require to investigate only the open-loop characteristics. A basic device is the consideration of the residues of different transfer functions at the open-loop unstable poles. An example is given.     

Improving loops and vanishing variables in long transportation problems

In this paper the following two results are presented: (1)A method which determines the optimal values of certain variables during the iterative solution process. The closer the current primal feasible solution is to the optimal solution, the greater the number of variables which may be determined. (2) For each current feasible solution (X_ij) of the given m × n transportation problem A, a feasible solution ($\text{X}\text{?}{}_{\mathrm{ij}}$) of an auxiliary m × m(m ?1) transportation problem $\text{A}\text{?}$ is constructed. Problem $\text{A}\text{?}$ is shown to be equivalent to an m(m ? 1) × m(m ? 1) assignment problem with two admissible cells per column. The optimally of (X_ij) is shown to imply the optimality of ($\text{X}\text{?}{}_{\mathrm{ij}}$) and conversely. The best “improving loops” (including the improving loops used in MODI) of $\text{A}\text{?}$ are shown to be the best “improving loops” of A as well.     

Asymptotic properties of minimax trees and game-searching procedures

The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods.If the terminal positions are assigned a WIN-LOSS status with the probabilities P₀ and 1 ? P₀, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P₀ is higher or lower than some fixed-point probability $\text{P1(d)}$. When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value $\text{v1}$, which is the $\text{(1 ? P1)-}\text{fractile}$ of the terminal distribution.Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions if positions if $\text{P}{}_0\text{≠ P1}$ and $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions if $\text{P}{}_0\text{= P1}$, the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.     

The decentralized stabilization and control of a class of unknown non-linear time-varying systems

The following problem is considered in this paper. Suppose a system S consists of a set of arbitrary interconnected subsystems S_i, i = 1, 2, …, Ω; is it possible to stabilize and satisfactorily control the whole system S by using only local controllers about the individual subsystems without a knowledge of the manner of the actual interconnections of the whole system? Sufficient conditions are obtained for such a result to hold true; in particular it is shown that a system S consisting of a number of subsystems S_i connected in an arbitrary way between themselves with finite gains: $\text{S}{}_{\mathrm{i}}\text{:}\text{x}\text{?}{}_{\mathrm{i}}\text{=}\text{A}{}_{\mathrm{i}}\text{(}\text{x}{}_{\mathrm{i}}\text{, t)}\text{x}{}_{\mathrm{i}}\text{+}\text{b}{}_{\mathrm{i}}\text{(}\text{x}{}_{\mathrm{i}}\text{, t)u}{}_{\mathrm{i}}\text{, y}{}_{\mathrm{i}}\text{=}\text{c}\text{′}{}_{\mathrm{i}}\text{(}\text{x}{}_{\mathrm{i}}\text{, t)}\text{x}{}_{\mathrm{i}}$ where A_i and b_i have a particular structure, may be satisfactorily controlled by applying only local controllers C_i about the individual subsystems: C_i: u_i = K′_i(?)x_i where K_i is a constant gain matrix with the scalar ? appearing as a parameter, provided ? is large enough.     

computer aided intuition in abstract algebra

Two examples are given in which the computer was used to supplement intuition in abstract algebra. In the first example, the computer was used to search Cayley tables of 4 element groupoids to find those which are 5-associative but not 4-associative. (n-associative means that the product of any n elements is independent of the way the factors are grouped by parentheses.) The computer generated examples suggested the existence of n element groupoids which are (2^n?2+1)-associative but not (2^n-2)-associative, for each integer n≧4.In the second example, the computer counted the numbers g₂(m) of invertible 2×2 matrices with entries chosen from the ring Z_mof integers, for m = 2, 3, 4,…, 18. The insight gained from these results led to a proof that there are

invertible n×n matrices over Z_m.Some applications to graduate and undergraduate instruction are indicated.     

An iterative method for determining the current-potential curves of a spherical probe in a slightly ionized continuum plasma with 5 ⩽ ρp ⩽ 50, yp < 7

A desk analogue computer has been used to draw normalized curves for positive and negative particle concentrations $\text{(n}{}_{\mathrm{+}}\text{,n}{}_{\mathrm{?}}\text{)}$ and potential $\text{(y)}$ vs the distance from a spherical probe surface for a slightly ionized continuum plasma. The governing equations are three simultaneous differential equations leading to a two-point boundary condition problem. An iterative analogue method has been developed which enables the positive and negative particle currents $\text{(J}{}_{\mathrm{+}}\text{,J}{}_{\mathrm{?}}\text{)}$ to the probe, for particular $\text{y}{}_{\mathrm{p}}\text{< 7}$ and $\text{ρ}{}_{\mathrm{p}}\text{< 50}$, to be found to a numerical accuracy of about 1 digit in the second decimal place.