We prove convergence of the Adomian Decomposition Method (ADM) by using the Cauchy-Kovalevskaya theorem for differential equations with analytic vector fields, and obtain a new result on the convergence rate of the ADM. Picard's iterative method is considered for the same class of equations in comparison with the decomposition method. We outline some substantial differences between the two methods and show that the decomposition method converges faster than the Picard method. Several nonlinear differential equations are considered for illustrative purposes and the numerical approximations of their solutions are obtained using MATLAB. The numerical results show how the decomposition method is more effective than the standard ODE solvers. Moreover, we prove convergence of the ADM for the partial differential equations and apply it to the cubic nonlinear Schrodinger equation with a localized potential. / Thesis / Master of Science (MSc)

Abstract Broadband single-carrier modulated signals experience severe multipath distortion when propagating through the physical medium. Correcting the distortion with channel equalization is the foremost task of the detector. Prior information about the transmitted signals in the form of channel decoder feedback can significantly enhance equalization accuracy. An algorithm that iteratively performs channel decoding and equalization with prior information is generally denoted a turbo equalizer. This thesis focuses on turbo equalization with prior information using the principle of interference cancellation followed by minimum mean squared error (MMSE) filtering. Receiver algorithms, receiver convergence, and coding and modulation in the context of MMSE turbo equalization are studied. Computationally efficient versions of the receiver algorithm through approximate time-average filtering, matched filtering, square-root time-variant filtering and frequency-domain filtering are studied. The frequency-domain turbo equalizer (FDTE) is found to exhibit both superior convergence and low computational complexity among the compared equalizer algorithms. Multi-dimensional extrinsic information transfer (EXIT) charts are introduced for the purpose of tracking the convergence of the turbo equalization of layered MIMO transmissions. Generic properties of the equalizer EXIT functions defining the equalizer convergence are analyzed. The principles for detector ordering, maximum sum-rate code design and maximum rate symmetric design are derived from the properties of the multidimensional EXIT functions. Semi-analytical EXIT charts are developed for the convergence analysis of the FDTE. The effects of channel parameters and the channel code are analyzed with semi-analytical methods. A new approach for the design of irregular low-density parity-check (LDPC) codes using a convergence outage principle is proposed. A performance gain is demonstrated in a single-input multiple output (SIMO) channel over non-optimized regular LDPC codes and irregular LDPC codes optimized for the AWGN channel. The outage convergence based design, which takes advantage of the semi-analytical convergence analysis method, is also extended to layered MIMO transmissions. Quadrature amplitude modulation using multilevel bit-interleaved coded modulation (MLBICM) is studied as an alternative to regular bit-interleaved coded modulation (BICM) for highly bandwidth-efficient transmission in MMSE turbo equalized systems. A linear bit-to-symbol mapping is introduced that enables the use of a computationally efficient MMSE turbo equalizer at the receiver. The proposed coded modulation is compared with BICM in channel measurement data based simulations and found to exhibit superior robustness against changes in spatial channel parameters. An automatic repeat request (ARQ) configuration using one ARQ controller for each equally performing group of code levels is proposed. The configuration takes advantage of the unequal error protection (UEP) property of the coded modulation. The semi-analytical convergence analysis is extended to the multilevel modulated case and applied in a channel measurement based convergence evaluation. The construction of the MLBICM is found to have an inherently better convergence behavior than BICM. Finally, the outage convergence based channel code design is extended to the layered MIMO multilevel signalling case.

>Magister Scientiae - MSc / With the development of technology seen in the last few decades, numerous solvers have been developed to provide adequate solutions to the problems that model different aspects of science and engineering. Quite often, these solvers are tailor-made for specific classes of problems. Therefore, more of such must be developed to accompany the growing need for mathematical models that help in the understanding of the contemporary world. This thesis treats two point boundary value singularly perturbed problems. The solution to this type of problem undergoes steep changes in narrow regions (called boundary or internal layer regions) thus rendering the classical numerical procedures inappropriate. To this end, robust numerical methods such as finite difference methods, in particular fitted mesh and fitted operator methods have extensively been used. While the former consists of transforming the continuous problem into a discrete one on a non-uniform mesh, the latter involves a special discretisation of the problem on a uniform mesh and are known to be more accurate. Both classes of methods are suitably designed to accommodate the rapid change(s) in the solution. Quite often, finite difference methods on piece-wise uniform meshes (of Shishkin-type) are adopted. However, methods based on such non-uniform meshes, though layer-resolving, are not easily extendable to higher dimensions. This work aims at investigating the possibility of capitalising on the advantages of both fitted mesh and fitted operator methods. Theoretical results are confirmed by extensive numerical simulations.

The presented thesis is focused on the GMRES convergence analysis. The basic principles of CG, MINRES and GMRES are briefly explained. The thesis summarizes some known convergence results of these methods. The known characterizations of the matrices and the right hand sides gen- erating the same Krylov residual spaces are summarized. Connections and the differences between the different points of view on GMRES convergence analysis are shown. We expect that if the convergence curve of GMRES applied to the nonnormal matrix and the right hand side seems to be de- termined by the eigenvalues of the matrix then exists a matrix that is close to normal and has the same spectrum as the matrix and for the right hand side has the same GMRES convergence curve (We assume that the initial approximation 0 = 0). Several numerical experiments are done to examine this assumption. This thesis describes an unpublished result of Gérard Meu- rant which is the formula for the norm of the -th error of GMRES applied to the matrix and right hand side and its derivation. The upper estimate of the -th GMRES error is derived. This estimate is minimized via spectrum.

This dissertation presents a new framework for the development and analysis of blind adaptive algorithms. An adaptive algorithm is said to be 'blind' if it does not require a known training sequence. The main focus is on application of these algorithms to adaptive antenna arrays in mobile radio communications. Adaptive antenna arrays can reduce the effects of cochannel interference, multipath fading, and background noise as compared to more conventional antenna systems. For these reasons, the use of adaptive antennas in wireless communication has received a great deal of attention in the literature. There are several reasons why the study of blind adaptive algorithms is important. First, it is common practice to switch to a blind mode once the training sequence has been processed in order to track a changing environment. Furthermore, the use of a blind algorithm can completely eliminate the need for a training sequence. This is desirable since the use of a training sequence reduces the number of bits available for transmitting information. The analysis framework introduced here is shown to include the well-known Constant Modulus Algorithm (CMA) and decision directed algorithm (DDA). New results on the behavior of the CMA and DDA are presented here, including analytic results on the convergence rate. Previous results have relied on Monte Carlo simulation. This framework is also used to propose a new class of blind adaptive algorithms that offer the potential for improved convergence rate. / Ph. D.

Thesis (PhD (Mathematics))--University of Stellenbosch, 2010. / Contains bibliography. / ENGLISH ABSTRACT: See full text for summary. / AFRIKAANSE OPSOMMING: Sien volteks vir opsomming

<div>Multi-model inference covers a wide range of modern statistical applications such as variable selection, model confidence set, model averaging and variable importance.</div><div>The performance of multi-model inference depends on the availability of candidate models, whose quality has been rarely studied in literature. In this dissertation, we study genetic algorithm (GA) in order to obtain high-quality candidate models. Inspired by the process of natural selection, GA performs genetic operations such as selection, crossover and mutation iteratively to update a collection of potential solutions (models) until convergence. The convergence properties are studied based on the Markov chain theory and used to design an adaptive termination criterion that vastly reduces the computational cost. In addition, a new schema theory is established to characterize how the current model set is improved through evolutionary process. Extensive numerical experiments are carried out to verify our theory and demonstrate the empirical power of GA, and new findings are obtained for two real data examples. </div>

Philosophiae Doctor - PhD / Numerical approximations of multiscale problems of important applications in ecology are investigated. One of the class of models considered in this work are singularly perturbed (slow-fast) predator-prey systems which are characterized by the presence of a very small positive parameter representing the separation of time-scales between the fast and slow dynamics. Solution of such problems involve multiple scale phenomenon characterized by repeated switching of slow and fast motions, referred to as relaxationoscillations, which are typically challenging to approximate numerically. Granted with a priori knowledge, various time-stepping methods are developed within the framework of partitioning the full problem into fast and slow components, and then numerically treating each component differently according to their time-scales. Nonlinearities that arise as a result of the application of the implicit parts of such schemes are treated by using iterative algorithms, which are known for their superlinear convergence, such as the Jacobian-Free Newton-Krylov (JFNK) and the Anderson’s Acceleration (AA) fixed point methods.

The thesis treats model reduction for linear time-varying systems. Time-varying models appear in many fields, including power systems, chemical engineering, aeronautics, and computational science. They can also be used for approximation of time-invariant nonlinear models. Model reduction is a topic that deals with simplification of complex models. This is important since it facilitates analysis and synthesis of controllers. The thesis consists of two parts. The first part provides an introduction to the topics of time-varying systems and model reduction. Here, notation, standard results, examples, and some results from the second part of the thesis are presented. The second part of the thesis consists of four papers. In the first paper, we study the balanced truncation method for linear time-varying state-space models. We derive error bounds for the simplified models. These bounds are generalizations of well-known time-invariant results, derived with other methods. In the second paper, we apply balanced truncation to a high-order model of a diesel exhaust catalyst. Furthermore, we discuss practical issues of balanced truncation and approximative discretization. In the third paper, we look at frequency-domain analysis of linear time-periodic impulse-response models. By decomposing the models into Taylor and Fourier series, we can analyze convergence properties of different truncated representations. In the fourth paper, we use the frequency-domain representation developed in the third paper, the harmonic transfer function, to generalize Bode's sensitivity integral. This result quantifies limitations for feedback control of linear time-periodic systems. / QC 20120206

Several recent engineering applications in multi-agent systems, communication networks, and machine learning deal with decision problems that can be formulated as optimization problems. For many of these problems, new constraints limit the usefulness of traditional optimization algorithms. In some cases, the problem size is much larger than what can be conveniently dealt with using standard solvers. In other cases, the problems have to be solved in a distributed manner by several decision-makers with limited computational and communication resources. By exploiting problem structure, however, it is possible to design computationally efficient algorithms that satisfy the implementation requirements of these emerging applications. In this thesis, we study a variety of techniques for improving the convergence times of optimization algorithms for large-scale systems. In the first part of the thesis, we focus on multi-step first-order methods. These methods add memory to the classical gradient method and account for past iterates when computing the next one. The result is a computationally lightweight acceleration technique that can yield significant improvements over gradient descent. In particular, we focus on the Heavy-ball method introduced by Polyak. Previous studies have quantified the performance improvements over the gradient through a local convergence analysis of twice continuously differentiable objective functions. However, the convergence properties of the method on more general convex cost functions has not been known. The first contribution of this thesis is a global convergence analysis of the Heavy- ball method for a variety of convex problems whose objective functions are strongly convex and have Lipschitz continuous gradient. The second contribution is to tailor the Heavy- ball method to network optimization problems. In such problems, a collection of decision- makers collaborate to find the decision vector that minimizes the total system cost. We derive the optimal step-sizes for the Heavy-ball method in this scenario, and show how the optimal convergence times depend on the individual cost functions and the structure of the underlying interaction graph. We present three engineering applications where our algorithm significantly outperform the tailor-made state-of-the-art algorithms. In the second part of the thesis, we consider the Alternating Direction Method of Multipliers (ADMM), an alternative powerful method for solving structured optimization problems. The method has recently attracted a large interest from several engineering communities. Despite its popularity, its optimal parameters have been unknown. The third contribution of this thesis is to derive optimal parameters for the ADMM algorithm when applied to quadratic programming problems. Our derivations quantify how the Hessian of the cost functions and constraint matrices affect the convergence times. By exploiting this information, we develop a preconditioning technique that allows to accelerate the performance even further. Numerical studies of model-predictive control problems illustrate significant performance benefits of a well-tuned ADMM algorithm. The fourth and final contribution of the thesis is to extend our results on optimal scaling and parameter tuning of the ADMM method to a distributed setting. We derive optimal algorithm parameters and suggest heuristic methods that can be executed by individual agents using local information. The resulting algorithm is applied to distributed averaging problem and shown to yield substantial performance improvements over the state-of-the-art algorithms. / <p>QC 20150327</p>