The nonexistence of spurious solutions to discrete, two-point boundary value problems

We investigate difference equations which arise as discrete approximations to two-point boundary value problems for systems of second-order, ordinary differential equations. We formulate conditions under which all solutions to the discrete problem satisfy certain a priori bounds which axe independent of the step-size. As a result, the nonexistence of spurious solutions are guaranteed. Some existence and convergence theorems for solutions to the discrete problem are also presented. (C) 2002 Elsevier Science Ltd. All rights reserved.

Théorèmes d'existence pour des systèmes d'équations différentielles et d'équations aux échelles de temps.

Nous présentons dans cette thèse des théorèmes d’existence pour des systèmes d’équations différentielles non-linéaires d’ordre trois, pour des systèmes d’équa- tions et d’inclusions aux échelles de temps non-linéaires d’ordre un et pour des systèmes d’équations aux échelles de temps non-linéaires d’ordre deux sous cer- taines conditions aux limites. Dans le chapitre trois, nous introduirons une notion de tube-solution pour obtenir des théorèmes d’existence pour des systèmes d’équations différentielles du troisième ordre. Cette nouvelle notion généralise aux systèmes les notions de sous- et sur-solutions pour le problème aux limites de l’équation différentielle du troisième ordre étudiée dans [34]. Dans la dernière section de ce chapitre, nous traitons les systèmes d’ordre trois lorsque f est soumise à une condition de crois- sance de type Wintner-Nagumo. Pour admettre l’existence de solutions d’un tel système, nous aurons recours à la théorie des inclusions différentielles. Ce résultat d’existence généralise de diverses façons un théorème de Grossinho et Minhós [34]. Le chapitre suivant porte sur l’existence de solutions pour deux types de sys- tèmes d’équations aux échelles de temps du premier ordre. Les résultats d’exis- tence pour ces deux problèmes ont été obtenus grâce à des notions de tube-solution adaptées à ces systèmes. Le premier théorème généralise entre autre aux systèmes et à une échelle de temps quelconque, un résultat obtenu pour des équations aux différences finies par Mawhin et Bereanu [9]. Ce résultat permet également d’obte- nir l’existence de solutions pour de nouveaux systèmes dont on ne pouvait obtenir l’existence en utilisant le résultat de Dai et Tisdell [17]. Le deuxième théorème de ce chapitre généralise quant à lui, sous certaines conditions, des résultats de [60]. Le chapitre cinq aborde un nouveau théorème d’existence pour un système d’in- clusions aux échelles de temps du premier ordre. Selon nos recherches, aucun résultat avant celui-ci ne traitait de l’existence de solutions pour des systèmes d’inclusions de ce type. Ainsi, ce chapitre ouvre de nouvelles possibilités dans le domaine des inclusions aux échelles de temps. Notre résultat a été obtenu encore une fois à l’aide d’une hypothèse de tube-solution adaptée au problème. Au chapitre six, nous traitons l’existence de solutions pour des systèmes d’équations aux échelles de temps d’ordre deux. Le premier théorème d’existence que nous obtenons généralise les résultats de [36] étant donné que l’hypothèse que ces auteurs utilisent pour faire la majoration a priori est un cas particulier de notre hypothèse de tube-solution pour ce type de systèmes. Notons également que notre définition de tube-solution généralise aux systèmes les notions de sous- et sur-solutions introduites pour les équations d’ordre deux par [4] et [55]. Ainsi, nous généralisons également des résultats obtenus pour des équations aux échelles de temps d’ordre deux. Finalement, nous proposons un nouveau résultat d’exis- tence pour un système dont le membre droit des équations dépend de la ∆-dérivée de la fonction.

Existence of multiple solutions for finite difference approximations to second-order boundary value problems

Error condition detected We consider discrete two-point boundary value problems of the form D-2 y(k+1) = f (kh, y(k), D y(k)), for k = 1,...,n - 1, (0,0) = G((y(0),y(n));(Dy-1,Dy-n)), where Dy-k = (y(k) - Yk-I)/h and h = 1/n. This arises as a finite difference approximation to y" = f(x,y,y'), x is an element of [0,1], (0,0) = G((y(0),y(1));(y'(0),y'(1))). We assume that f and G = (g(0), g(1)) are continuous and fully nonlinear, that there exist pairs of strict lower and strict upper solutions for the continuous problem, and that f and G satisfy additional assumptions that are known to yield a priori bounds on, and to guarantee the existence of solutions of the continuous problem. Under these assumptions we show that there are at least three distinct solutions of the discrete approximation which approximate solutions to the continuous problem as the grid size, h, goes to 0. (C) 2003 Elsevier Science Ltd. All rights reserved.

On the existence of solutions to boundary value problems on time scales

This work formulates existence theorems for solutions to two-point boundary value problems on time scales. The methods used include maximum principles, a priori bounds and topological degree theory.

Boundary value problems for systems of difference equations associated with systems of second-order ordinary differential equations

We study difference equations which arise as discrete approximations to two-point boundary value problems for systems of second-order ordinary differential equations. We formulate conditions which guarantee a priori bounds on first differences of solutions to the discretized problem. We establish existence results for solutions to the discretized boundary value problems subject to nonlinear boundary conditions. We apply our results to show that solutions to the discrete problem converge to solutions of the continuous problem in an aggregate sense. (C) 2002 Elsevier Science Ltd. All rights reserved.

Difference equations associated with fully nonlinear boundary value problems for second order ordinary differential equations

We study the continuous problem y"=f(x,y,y'), xc[0,1], 0=G((y(0),y(1)),(y'(0), y'(1))), and its discrete approximation (y(k+1)-2y(k)+y(k-1))/h(2) =f(t(k), y(k), v(k)), k = 1,..., n-1, 0 = G((y(0), y(n)), (v(1), v(n))), where f and G = (g(0), g(1)) are continuous and fully nonlinear, h = 1/n, v(k) = (y(k) - y(k-1))/h, for k =1,..., n, and t(k) = kh, for k = 0,...,n. We assume there exist strict lower and strict upper solutions and impose additional conditions on f and G which are known to yield a priori bounds on, and to guarantee the existence of solutions of the continuous problem. We show that the discrete approximation also has solutions which approximate solutions of the continuous problem and converge to the solution of the continuous problem when it is unique, as the grid size goes to 0. Homotopy methods can be used to compute the solution of the discrete approximation. Our results were motivated by those of Gaines.

Difference equations in Banach spaces

Difference equations which discretely approximate boundary value problems for second-order ordinary differential equations are analysed. It is well known that the existence of solutions to the continuous problem does not necessarily imply existence of solutions to the discrete problem and, even if solutions to the discrete problem are guaranteed, they may be unrelated and inapplicable to the continuous problem. Analogues to theorems for the continuous problem regarding a priori bounds and existence of solutions are formulated for the discrete problem. Solutions to the discrete problem are shown to converge to solutions of the continuous problem in an aggregate sense. An example which arises in the study of the finite deflections of an elastic string under a transverse load is investigated. The earlier results are applied to show the existence of a solution; the sufficient estimates on the step size are presented. (C) 2003 Elsevier Science Ltd. All rights reserved.

Aggregation in the generalized transportation problem

Aggregation disaggregation is used to reduce the analysis of a large generalized transportation problem to a smaller one. Bounds for the actual difference between the aggregated objective and the original optimal value are used to quantify the error due to aggregation and estimate the quality of the aggregation. The bounds can be calculated either before optimization of the aggregated problem (a priori) or after (a posteriori). Both types of the bounds are derived and numerically compared. A computational experiment was designed to (a) study the correlation between the bounds and the actual error and (b) quantify the difference of the error bounds from the actual error. The experiment shows a significant correlation between some a priori bounds, the a posteriori bounds and the actual error. These preliminary results indicate that calculating the a priori error bound is a useful strategy to select the appropriate aggregation level, since the a priori bound varies in the same way that the actual error does. After the aggregated problem has been selected and optimized, the a posteriori bound provides a good quantitative measure for the error due to aggregation.

Adaptation Strategies for Discontinuous Galerkin Spectral Element Methods by means of Truncation Error Estimations

In this work a p-adaptation (modification of the polynomial order) strategy based on the minimization of the truncation error is developed for high order discontinuous Galerkin methods. The truncation error is approximated by means of a truncation error estimation procedure and enables the identification of mesh regions that require adaptation. Three truncation error estimation approaches are developed and termed a posteriori, quasi-a priori and quasi-a priori corrected. Fine solutions, which are obtained by enriching the polynomial order, are required to solve the numerical problem with adequate accuracy. For the three truncation error estimation methods the former needs time converged solutions, while the last two rely on non-converged solutions, which lead to faster computations. Based on these truncation error estimation methods, algorithms for mesh adaptation were designed and tested. Firstly, an isotropic adaptation approach is presented, which leads to equally distributed polynomial orders in different coordinate directions. This first implementation is improved by incorporating a method to extrapolate the truncation error. This results in a significant reduction of computational cost. Secondly, the employed high order method permits the spatial decoupling of the estimated errors and enables anisotropic p-adaptation. The incorporation of anisotropic features leads to meshes with different polynomial orders in the different coordinate directions such that flow-features related to the geometry are resolved in a better manner. These adaptations result in a significant reduction of degrees of freedom and computational cost, while the amount of improvement depends on the test-case. Finally, this anisotropic approach is extended by using error extrapolation which leads to an even higher reduction in computational cost. These strategies are verified and compared in terms of accuracy and computational cost for the Euler and the compressible Navier-Stokes equations. The main result is that the two quasi-a priori methods achieve a significant reduction in computational cost when compared to a uniform polynomial enrichment. Namely, for a viscous boundary layer flow, we obtain a speedup of a factor of 6.6 and 7.6 for the quasi-a priori and quasi-a priori corrected approaches, respectively. RESUMEN En este trabajo se ha desarrollado una estrategia de adaptación-p (modificación del orden polinómico) para métodos Galerkin discontinuo de alto orden basada en la minimización del error de truncación. El error de truncación se estima utilizando el método tau-estimation. El estimador permite la identificación de zonas de la malla que requieren adaptación. Se distinguen tres técnicas de estimación: a posteriori, quasi a priori y quasi a priori con correción. Todas las estrategias requieren una solución obtenida en una malla fina, la cual es obtenida aumentando de manera uniforme el orden polinómico. Sin embargo, mientras que el primero requiere que esta solución esté convergida temporalmente, el resto utiliza soluciones no convergidas, lo que se traduce en un menor coste computacional. En este trabajo se han diseñado y probado algoritmos de adaptación de malla basados en métodos tau-estimation. En primer lugar, se presenta un algoritmo de adaptacin isótropo, que conduce a discretizaciones con el mismo orden polinómico en todas las direcciones espaciales. Esta primera implementación se mejora incluyendo un método para extrapolar el error de truncación. Esto resulta en una reducción significativa del coste computacional. En segundo lugar, el método de alto orden permite el desacoplamiento espacial de los errores estimados, permitiendo la adaptación anisotropica. Las mallas obtenidas mediante esta técnica tienen distintos órdenes polinómicos en cada una de las direcciones espaciales. La malla final tiene una distribución óptima de órdenes polinómicos, los cuales guardan relación con las características del flujo que, a su vez, depenen de la geometría. Estas técnicas de adaptación reducen de manera significativa los grados de libertad y el coste computacional. Por último, esta aproximación anisotropica se extiende usando extrapolación del error de truncación, lo que conlleva un coste computational aún menor. Las estrategias se verifican y se comparan en téminors de precisión y coste computacional utilizando las ecuaciones de Euler y Navier Stokes. Los dos métodos quasi a priori consiguen una reducción significativa del coste computacional en comparación con aumento uniforme del orden polinómico. En concreto, para una capa límite viscosa, obtenemos una mejora en tiempo de computación de 6.6 y 7.6 respectivamente, para las aproximaciones quasi-a priori y quasi-a priori con corrección.

Maximum Principle and Its Application for the Time-Fractional Diffusion Equations

MSC 2010: 26A33, 33E12, 35B45, 35B50, 35K99, 45K05 Dedicated to Professor Rudolf Gorenflo on the occasion of his 80th anniversary

On the suboptimality of the p-version interior penalty discontinuous Galerkin method

We address the question of the rates of convergence of the p-version interior penalty discontinuous Galerkin method (p-IPDG) for second order elliptic problems with non-homogeneous Dirichlet boundary conditions. It is known that the p-IPDG method admits slightly suboptimal a-priori bounds with respect to the polynomial degree (in the Hilbertian Sobolev space setting). An example for which the suboptimal rate of convergence with respect to the polynomial degree is both proven theoretically and validated in practice through numerical experiments is presented. Moreover, the performance of p- IPDG on the related problem of p-approximation of corner singularities is assessed both theoretically and numerically, witnessing an almost doubling of the convergence rate of the p-IPDG method.

On statistical bounds of heuristic solutions to location problems

Solutions to combinatorial optimization problems, such as problems of locating facilities, frequently rely on heuristics to minimize the objective function. The optimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. Pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small, almost dormant, branch of the literature suggests using statistical principles to estimate the minimum and its bounds as a tool to decide upon stopping and evaluating the quality of the solution. In this paper we examine the functioning of statistical bounds obtained from four different estimators by using simulated annealing on p-median test problems taken from Beasley’s OR-library. We find the Weibull estimator and the 2nd order Jackknife estimator preferable and the requirement of sample size to be about 10 being much less than the current recommendation. However, reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality and we give a simple statistic useful for checking the quality. We end the paper with an illustration on using statistical bounds in a problem of locating some 70 distribution centers of the Swedish Post in one Swedish region. 

Lower bounds on blow up solutions of the three-dimensional Navier-Stokes equations in homogeneous Sobolev spaces

Suppose that u(t) is a solution of the three-dimensional Navier-Stokes equations, either on the whole space or with periodic boundary conditions, that has a singularity at time T. In this paper we show that the norm of u(T - t) in the homogeneous Sobolev space (H)over dot(s) must be bounded below by c(s)t(-(2s-1)/4) for 1/2 < s < 5/2 (s not equal 3/2), where c(s) is an absolute constant depending only on s; and by c(s)parallel to u(0)parallel to((5-2s)/5)(L2)t(-2s/5) for s > 5/2. (The result for 1/2 < s < 3/2 follows from well-known lower bounds on blowup in Lp spaces.) We show in particular that the local existence time in (H)over dot(s)(R-3) depends only on the (H)over dot(s)-norm for 1/2 < s < 5/2, s not equal 3/2. (C) 2012 American Institute of Physics. [http://dx.doi.org/10.1063/1.4762841]

GRASP and statistical bounds for heuristic solutions to combinatorial problems

The quality of a heuristic solution to a NP-hard combinatorial problem is hard to assess. A few studies have advocated and tested statistical bounds as a method for assessment. These studies indicate that statistical bounds are superior to the more widely known and used deterministic bounds. However, the previous studies have been limited to a few metaheuristics and combinatorial problems and, hence, the general performance of statistical bounds in combinatorial optimization remains an open question. This work complements the existing literature on statistical bounds by testing them on the metaheuristic Greedy Randomized Adaptive Search Procedures (GRASP) and four combinatorial problems. Our findings confirm previous results that statistical bounds are reliable for the p-median problem, while we note that they also seem reliable for the set covering problem. For the quadratic assignment problem, the statistical bounds has previously been found reliable when obtained from the Genetic algorithm whereas in this work they found less reliable. Finally, we provide statistical bounds to four 2-path network design problem instances for which the optimum is currently unknown.

The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm

This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided.