Thesis (M.A.)--Boston University / PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you. / The problem discussed in this paper is that of finding a best approximation to a given real-valued function f(x) over a continuum by means of finding a best approximation over a discrete set of points. We are also seeking to find a numerical method of finding a best approximation over our discrete set of points. A best approximation is one which minimizes the maximum deviation of our approximation from our given function f(x). We first discuss the concept of linear programming. In this paper we are not so much concerned with the theory behind linear programming as we are with the method to solve a linear programming problem, namely the simplex method. We discuss the simplex method from the point of view of a programmer, noting how results are continually updated until an optimal solution to t he problem is found. The only theoretical aspect of linear programming which we discuss is the notion of duals and the relationship between the solution of a primal and a dual problem. This becomes very important later in the paper when we try to formulate a best a proximat ion problem as a linear programming problem. Next we discuss the theoretical aspects of best approximation over a continuum. We prove existence, uniqueness, and, most important for our purposes, characterization. Our approximating functions are assumed to form a Chebyschev set throughout this paper. Finally we discuss best approximation over a discrete set of points. We first prove that the characterization theorem holds for problems of this type. Now that we have a way to tell whether our approximation is the best that can be obtained, we turn our attention to the relationship between the best approximation problem over a continuum and a discrete set of points. We prove in a quite general context that the best approximation over a discrete set of points converges uniformly to the solution to the problem over the continuum. We then retrace our steps and establish similar results for the particular case of polynomial approximation. After this we try to find out about the rate at which this convergence takes place. In general this question has no answer for its depends on the smoothness of the functions involved; if, however, we assume the fun ctions satisfy a Holder condition we may obtain some bounds on the rate of convergence. Finally, we reformulate the best approximation problem, showing how it can be considered as a linear programming problem which we already have a means of solving. / 2999-01-01

No description available.

Boundary Approximation Method (BAM), or the Collocation Trefftz Method called in the literature, is the most efficient method to solve elliptic boundary value problems with singularities. There are several versions of BAM in practical computation, including the Numerical BAM, Symbolic BAM and their variants. It is known that the Symbolic BAM is much slower than Numerical counterpart. In this thesis, we improve the Symbolic BAM to become the fastest method among all versions of BAM. We prove several important lemmas to reduce the computing time, and a recursive procedure is found to expedite the evaluation of major integrals. Another drawback of the Symbolic BAM is its large condition number. We find a good and easy preconditioner to significantly reduce the condition number. The numerical experiments and comparison are also provided for the Motz problem, a prototype of Laplace boundary value problem with singularity, and the Schiff's Model, a prototype of biharmonic boundary value problem with singularity.

Thermal and fingering convection in a horizontal porous layer underlying a fluid layer was studied using linear stability analysis, experiment (for the thermal convection case only), and nonlinear simulation. For the thermal convection case, the linear analysis shows that when the fluid layer is thin, convection is largely confined to the porous layer. When the fluid layer thickness exceeds 15% of the porous layer thickness, convection is localized in the fluid layer and the critical wavelength is dramatically reduced. Experimental investigations were then conducted in a test box 24 cm x 12 cm x 4 cm high to substantiate the predictions. The ratio of the thickness of the fluid layer to that of the porous layer, d, varied from 0 to 1. The results were in good agreement with predictions. To investigate supercritical convection, a nonlinear computational study was carried out. It was found that for d ≤ 0.13, the Nusselt number increases sharply with the thermal Rayleigh number, whereas at larger values of d, the increase is more moderate. Heat transfer rates predicted for d = 0.1 and 0.2 are in good agreement with the experimental results. For salt-finger convection at R(m) ≤ 1, the critical value of the solute Rayleigh number R(sm) decreases as d increases; the convection is unicellular. For 5 ≤ R(m) ≤ 10, the critical R(sm) initially decreases with d, and then remains almost constant for larger values of d; multicellular convection prevails at high d. For 20 ≤ R(m) ≤ 50, the critical R(sm) first decreases and then increases as d increases from 0 to 0.1. When d > 0.1, the critical R(sm) decreases slowly with d and remains almost constant for d ≥ 0.4. In the nonlinear computations for R(m) = 1, periodic convection sets in at a value of R(sm) between ten and eleven times the critical value. For the case of R(m) = 50, an aperiodic oscillation occurs when R(sm) is between four and five times the critical value. For the superposed layer cases d = 1 and 0.5, the convection characteristics are similar to those of thermal convection when R(m) = 0.01. For R(m) = 1, it was found that the onset of salt-finger convection is oscillatory. For R(m) = 50, the nonlinear code failed to obtain satisfactory results.

No description available.

A Markov Decision Process (MDP) is a model employed to describe problems in which a decision must be made at each one of several stages, while receiving feedback from the environment. This type of model has been extensively studied in the operations research community and fundamental algorithms have been developed to solve associated problems. However, these algorithms are quite inefficient for very large problems, leading to a need for alternatives; since MDP problems are provably hard on compressed representations, one becomes content even with algorithms which may perform well at least on specific classes of problems. The class of problems we deal with in this thesis allows succinct representations for the MDP as a dynamic Bayes network, and for its solution as a weighted combination of basis functions. We develop novel algorithms for producing, improving, and calculating the error of approximate solutions for MDPs using a compressed representation. Specifically, we develop an efficient branch-and-bound algorithm for computing the Bellman error of the compact approximate solution regardless of its provenance. We introduce an efficient direct linear programming algorithm which, using incremental constraints generation, achieves run times significantly smaller than existing approximate algorithms without much loss of accuracy. We also show a novel direct linear programming algorithm which, instead of employing constraints generation, transforms the exponentially many constraints into a compact form more amenable for tractable solutions. In spite of its perceived importance, the efficient optimization of the Bellman error towards an approximate MDP solution has eluded current algorithms; to this end we propose a novel branch-and-bound approximate policy iteration algorithm which makes direct use of our branch-and-bound method for computing the Bellman error. We further investigate another procedure for obtaining an approximate solution based on the dual of the direct, approximate linear programming formulation for solving MDPs. To address both the loss of accuracy resulting from the direct, approximate linear program solution and the question of where basis functions come from we also develop a principled system able not only to produce the initial set of basis functions, but also able to augment it with new basis functions automatically generated such that the approximation error decreases according to the user's requirements and time limitations.

This thesis will address several problems in discrete optimization. These problems are considered hard to solve. However, good approximation algorithms for these problems may be helpful in approximating problems in computational biology and computer science. Given an undirected graph G=(V,E) and a family of subsets of vertices S, the minimum crossing spanning tree is a spanning tree where the maximum number of edges crossing any single set in S is minimized, where an edge crosses a set if it has exactly one endpoint in the set. This thesis will present two algorithms for special cases of minimum crossing spanning trees. The first algorithm is for the case where the sets of S are pairwise disjoint. It gives a spanning tree with the maximum crossing of a set being 2OPT+2, where OPT is the maximum crossing for a minimum crossing spanning tree. The second algorithm is for the case where the sets of S form a laminar family. Let b_i be a bound for each S_i in S. If there exists a spanning tree where each set S_i is crossed at most b_i times, the algorithm finds a spanning tree where each set S_i is crossed O(b_i log n) times. From this algorithm, one can get a spanning tree with maximum crossing O(OPT log n). Given an undirected graph G=(V,E), and a family of subsets of vertices S, the minimum crossing perfect matching is a perfect matching where the maximum number of edges crossing any set in S is minimized. A proof will be presented showing that finding a minimum crossing perfect matching is NP-hard, even when the graph is bipartite and the sets of S are pairwise disjoint.

We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks (Crown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, Max-Crown, in which realizing each desired adjacency yields a certain profit. We present the first O(1)-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APX-complete on bipartite graphs of bounded maximum degree.

A presentation of the Weierstrass approximation theorem and the Stone-Weierstrass theorem and a comparison of these two theorems are the objects of this thesis.

The purpose of this study was to investigate some theoretical approaches to the scattering of positive k-mesons by nucleons in an attempt to explain the experimental data. In this work the problem has been investigated by the technique of the weak coupling approximation.