This thesis investigates the numerical treatment of nonlinear eigenvalue problems. These problems are defined by the condition $T(lambda) v = boldsymbol{0}$, with $T: C to C^{n times n}$, where we seek to compute the scalar-vector pairs, $lambda in C$ and nonzero $ v in C^{n}$. The first contribution of this work connects recent contour integration methods to the theory and practice of system identification. This observation leads us to explore rational interpolation for system realization, producing a Loewner matrix contour integration technique. The second development of this work studies the application of rational interpolation to the function $T(z)^{-1}$, where we use the poles of this interpolant to approximate the eigenvalues of $T$. We then expand this idea to several iterative methods, where at each step the approximate eigenvalues are taken as new interpolation points. We show that the case where one interpolation point is used is theoretically equivalent to Newton's method for a particular scalar function. / Master of Science / This thesis investigates the numerical treatment of nonlinear eigenvalue problems. The solutions to these problems often reveal characteristics of an underlying physical system. One popular methodology for handling these problems uses contour integrals to compute a set of the solutions. The first contribution of this work connects these contour integration methods to the theory and practice of system identification. This leads us to explore other techniques for system identification, resulting in a new method. Another common methodology approximates the nonlinear problem directly. The second development of this work studies the application of rational interpolation for this purpose. We then use this idea to form several iterative methods, where at each step the approximate solutions are taken to be new interpolation points. We show that the case where one interpolation point is used is theoretically equivalent to Newton’s method for a particular scalar function.

Diss. Uppsala : Univ., 2002.

Differential equations arise frequently in modeling of physical systems, often resulting in linear eigenvalue problems. However, when dealing with large physical domains, solving such problems can be computationally expensive. This thesis examines an alternative approach to solving these problems, which involves utilizing absorbing boundary conditions and a Dirichlet-to-Neumann maps to transform the large sparse linear eigenvalue problem into a smaller nonlinear eigenvalue problem (NEP). The NEP is then solved using augmented Newton’s method. The specific equation investigated in this thesis is the two-dimensional Helmholtz equation, defined on the interval (x, y) ∈ [0, 10] × [0, 1], with the absorbing boundary condition introduced at x = 1. The results show a significant reduction in computational time when using this method compared to the original linear problem, making it a valuable tool for solving large linear eigenvalue problems. Another result is that the NEP does not affect the computational error compared to solving the linear problem, which further supports the NEP as an attractive alternative method.

Dynamical systems are a commonly used and studied tool for simulation, optimization and design. In many applications such as inverse problem, optimal control, shape optimization and uncertainty quantification, those systems typically depend on a parameter. The need for high fidelity in the modeling stage leads to large-scale parametric dynamical systems. Since these models need to be simulated for a variety of parameter values, the computational burden they incur becomes increasingly difficult. To address these issues, parametric reduced models have encountered increased popularity in recent years. We are interested in constructing parametric reduced models that represent the full-order system accurately over a range of parameters. First, we define a global joint error mea- sure in the frequency and parameter domain to assess the accuracy of the reduced model. Then, by assuming a rational form for the reduced model with poles both in the frequency and parameter domain, we derive necessary conditions for an optimal parametric reduced model in this joint error measure. Similar to the nonparametric case, Hermite interpolation conditions at the reflected images of the poles characterize the optimal parametric approxi- mant. This result extends the well-known interpolatory H2 optimality conditions by Meier and Luenberger to the parametric case. We also develop a numerical algorithm to construct locally optimal reduced models. The theory and algorithm are data-driven, in the sense that only function evaluations of the parametric transfer function are required, not access to the internal dynamics of the full model. While this first framework operates on the continuous function level, assuming repeated transfer function evaluations are available, in some cases merely frequency samples might be given without an option to re-evaluate the transfer function at desired points; in other words, the function samples in parameter and frequency are fixed. In this case, we construct a parametric reduced model that minimizes a discretized least-squares error in the finite set of measurements. Towards this goal, we extend Vector Fitting (VF) to the parametric case, solving a global least-squares problem in both frequency and parameter. The output of this approach might lead to a moderate size reduced model. In this case, we perform a post- processing step to reduce the output of the parametric VF approach using H2 optimal model reduction for a special parametrization. The final model inherits the parametric dependence of the intermediate model, but is of smaller order. A special case of a parameter in a dynamical system is a delay in the model equation, e.g., arising from a feedback loop, reaction time, delayed response and various other physical phenomena. Modeling such a delay comes with several challenges for the mathematical formulation, analysis, and solution. We address the issue of transient behavior for scalar delay equations. Besides the choice of an appropriate measure, we analyze the impact of the coefficients of the delay equation on the finite time growth, which can be arbitrary large purely by the influence of the delay. / Ph. D.

This work addresses two primary topics related to vibrations in structures. The first topic is the use of a spatially distributed sensor network for localization of vibration events. I use a received signal strength (RSS) framework that presumes exponential energy decay with distance to the source. I derive the Cramér-Rao bound (CRB) for this parameter estimation problem, with the unknown parameters being source location, source intensity, and the energy dissipation rate. In this framework, I show that the CRB matches the variance of maximum likelihood estimators (MLEs) in more computationally expensive Monte Carlo trials. I also compare the CRB to the results of physical experiments to test the power of the CRB to predict spatial areas where MLEs show practical evidence of being ill-conditioned. Supported by this evidence, I recommend the CRB as a simple measure of localization accuracy, which may be used to optimize sensor layouts before installation. I demonstrate how this numerical optimization may be performed for some regions of interest with simple geometries. The second topic investigates modal vibrations of multi-body structures built from simple one-dimensional elements, with networks of elastic strings as the primary example. I introduce a method of using a nonlinear eigenvalue problem (NLEVP) to express boundary conditions of the vibrating elements so that the (infinitely many) eigenvalues of the full structure are the eigenvalues of the finite-dimensional NLEVP. The mode shapes of the structure can then be recovered in analytic form (not as a discretization) from the corresponding eigenvectors of the NLEVP. I show some advantages of this method over dynamic stiffness matrices, which is another NLEVP framework for modal analysis. In numerical experiments, I test several contour integration solvers for NLEVPs on sample problems generated from string networks. / Doctor of Philosophy / This work deals with two primary topics related to vibrations in structures. The first topic is the use of vibration sensors to detect movement or impact and to estimate the location of the detected event. Sensors that are close to the event will record a larger amount of energy than the sensors that are farther away, so comparing the signals of several sensors can approximately establish the event location. In this way, vibration sensors might be used to monitor activity in a building without the use of intrusive cameras. The accuracy of location estimates can be greatly affected by the relative positions of the sensors and the event. Generally, location estimates tend to be most accurate if the sensors closely surround the event, and less accurate if the event is outside of the sensor zone. These principles are useful, but not precise. Given a framework for how event energy and noise are picked up by the sensors, the Cramér-Rao bound (CRB) is a formula for the achievable accuracy of location estimates. I demonstrate that the CRB is usefully similar to the location estimate accuracy from experimental data collected from a volunteer walking through a sensor-rigged hallway. I then show how CRB computations may be used to find an optimal arrangement of sensors. The match between the CRB and the accuracy of the experiments suggests that the sensor layout that optimizes the CRB will also provide accurate location estimates in a real building. The other main topic is how the vibrations of a structure can be understood through the structure's natural vibration frequencies and corresponding vibration shapes, called the "modes" of the structure. I connect vibration modes to the abstract framework of "nonlinear eigenvalue problems" (NLEVPs). An NLEVP is a square matrix-valued function for which one wants to find the inputs that make the matrix singular. But these singular matrices are usually isolated---% distributed among the infinitely many matrices of the NLEVP in places that are difficult to predict. After discussing NLEVPs in general and some methods for solving them, I show how the vibration modes of certain structures can be represented by the solutions of NLEVPs. The structures I analyze are multi-body structures that are made of simple interconnected pieces, such as elastic strings strung together into a spider web. Once a multi-body structure has been cast into the NLEVP form, an NLEVP solver can be used to find the vibration modes. Finally, I demonstrate that this method can be computationally faster than many traditional modal analysis techniques.

Consider an under-determined system of nonlinear equations F(x)=0, F:R^m→R^n, where F is continuously differentiable and m > n. This system appears in a variety of applications, including parameter-dependent systems, dynamical systems with periodic solutions, and nonlinear eigenvalue problems. Robust, efficient numerical methods are often required for the solution of this system. Newton's method is an iterative scheme for solving the nonlinear system of equations F(x)=0, F:R^n→R^n. Simple to implement and theoretically sound, it is not, however, often practical in its pure form. Inexact Newton methods and globalized inexact Newton methods are computationally efficient variations of Newton's method commonly used on large-scale problems. Frequently, these variations are more robust than Newton's method. Trust region methods, thought of here as globalized exact Newton methods, are not as computationally efficient in the large-scale case, yet notably more robust than Newton's method in practice. The normal flow method is a generalization of Newton's method for solving the system F:R^m→R^n, m > n. Easy to implement, this method has a simple and useful local convergence theory; however, in its pure form, it is not well suited for solving large-scale problems. This dissertation presents new methods that improve the efficiency and robustness of the normal flow method in the large-scale case. These are developed in direct analogy with inexact-Newton, globalized inexact-Newton, and trust-region methods, with particular consideration of the associated convergence theory. Included are selected problems of interest simulated in MATLAB.

<p>Predmet istraživanja u doktorskoj disertaciji je metoda za konstrukciju<br />lokalizacionih skupova za spektar i pseudospektar nelinearnih problema<br />karakterističnih korena bazirana na Geršgorinovoj teoremi i njenim<br />generalizacijama koja koristi osobine poznatih podklasa H-matrica.<br />Navedena tvrđenja i primeri rasvetljavaju odnose između navedenih<br />lokalizacionih skupova, što je posebno značajno za primenu u praksi.<br />Sadržaj ovog rada time predstavlja polaznu tačku za dublja istraživanja na<br />temu konstrukcije lokalizacionih skupova za spektar i pseudospektar<br />nelinearnih problema karakterističnih korena Geršgorinovog tipa.</p> / <p>The subject of research in the doctoral dissertation is a method for constructing<br />spectra and pseudospectra localization sets for nonlinear eigenvalue problems<br />based on Ger&scaron;gorin theorem and its generalizations, that uses the properties of<br />well-known subclasses of H-matrices. Theorems and examples given in this<br />paper are showing relations between stated localization sets, which is very<br />important for practical applications. Therefore, the content of this paper represent<br />the starting point for deeper explorations on the subject of constructing spectra<br />and pseudospectra localization sets for Ger&scaron;gorin type nonlinear eigenvalue<br />problems.</p>

L'Algèbre tropicale peut être considérée comme un domaine relativement nouveau en mathématiques. Elle apparait dans plusieurs domaines telles que l'optimisation, la synchronisation de la production et du transport, les systèmes à événements discrets, le contrôle optimal, la recherche opérationnelle, etc. La première partie de ce manuscrit est consacrée a l'étude des applications de l'algèbre tropicale à l'analyse numérique matricielle. Nous considérons tout d'abord le problème classique de l'estimation des racines d'un polynôme univarié. Nous prouvons plusieurs nouvelles bornes pour la valeur absolue des racines d'un polynôme en exploitant les méthodes tropicales. Ces résultats sont particulièrement utiles lorsque l'on considère des polynômes dont les coefficients ont des ordres de grandeur différents. Nous examinons ensuite le problème du calcul des valeurs propres d'une matrice polynomiale. Ici, nous introduisons une technique de mise à l'échelle générale, basée sur l'algèbre tropicale, qui s'applique en particulier à la forme compagnon. Cette mise à l'échelle est basée sur la construction d'une fonction polynomiale tropicale auxiliaire, ne dépendant que de la norme des matrices. Les raciness (les points de non-différentiabilité) de ce polynôme tropical fournissent une pré-estimation de la valeur absolue des valeurs propres. Ceci se justifie en particulier par un nouveau résultat montrant que sous certaines hypothèses faites sur le conditionnement, il existe un groupe de valeurs propres bornées en norme. L'ordre de grandeur de ces bornes est fourni par la plus grande racine du polynôme tropical auxiliaire. Un résultat similaire est valable pour un groupe de petites valeurs propres. Nous montrons expérimentalement que cette mise à l'échelle améliore la stabilité numérique, en particulier dans des situations où les données ont des ordres de grandeur différents. Nous étudions également le problème du calcul des valeurs propres tropicales (les points de non-différentiabilité du polynôme caractéristique) d'une matrice polynômiale tropicale. Du point de vue combinatoire, ce problème est équivalent à trouver une fonction de couplage: la valeur d'un couplage de poids maximum dans un graphe biparti dont les arcs sont valués par des fonctions convexes et linéaires par morceaux. Nous avons développé un algorithme qui calcule ces valeurs propres tropicales en temps polynomial. Dans la deuxième partie de cette thèse, nous nous intéressons à la résolution de problèmes d'affectation optimale de très grande taille, pour lesquels les algorithms séquentiels classiques ne sont pas efficaces. Nous proposons une nouvelle approche qui exploite le lien entre le problème d'affectation optimale et le problème de maximisation d'entropie. Cette approche conduit à un algorithme de prétraitement pour le problème d'affectation optimale qui est basé sur une méthode itérative qui élimine les entrées n'appartenant pas à une affectation optimale. Nous considérons deux variantes itératives de l'algorithme de prétraitement, l'une utilise la méthode Sinkhorn et l'autre utilise la méthode de Newton. Cet algorithme de prétraitement ramène le problème initial à un problème beaucoup plus petit en termes de besoins en mémoire. Nous introduisons également une nouvelle méthode itérative basée sur une modification de l'algorithme Sinkhorn, dans lequel un paramètre de déformation est lentement augmenté. Nous prouvons que cette méthode itérative(itération de Sinkhorn déformée) converge vers une matrice dont les entrées non nulles sont exactement celles qui appartiennent aux permutations optimales. Une estimation du taux de convergence est également présentée.

No description available.

El análisis y el control de las vibraciones cobra especial importancia en muchas ramas de la ingeniería, en especial la ingeniería mecánica, civil, aeronáutica y automovilística. Tal es así que prácticamente se identi¿ca como un área independiente dentro del análisis dinámico de estructuras. Desde los comienzos de esta teoría, las fuerzas disipativas o de amortiguamiento han sido uno de los fenómenos más difíciles de modelizar. El modelo viscoso, por su sencillez y versatilidad ha sido y sigue siendo el gran paradigma de los modelos de amortiguamiento. Sin embargo, como consecuencia de la aparición de materiales con memoria se introdujo el fenómeno de la viscoelasticidad; Esta, si bien está también 'íntimamente ligada ' a la velocidad de la respuesta, necesito de la introducción de las denominadas funciones hereditarias, que permiten poner a las fuerzas disipativas como función no solo de la velocidad instantánea sino de la historia de velocidades desde el comienzo del movimiento, de ahí el termino memoria. De forma natural, el avance teórico introducido en el modelo supone también una complicación computacional, pues donde antes teníamos un sistema lineal de ecuaciones diferenciales ahora tenemos un sistema de ecuaciones integro-diferenciales. El análisis de las vibraciones libres de los sistemas con amortiguamiento viscoelástico conduce a un problema nolineal de autovalores donde la característica principal es una matriz de amortiguamiento que depende de la frecuencia de excitación. El estudio de la solución de autovalores y autovectores de este problema es importante si se desean conocer los modos de vibración de la estructura o si se pretende obtener la respuesta en el dominio de la frecuencia del sistema. El objetivo fundamental de esta Tesis Doctoral es doble: Por un lado, profundizar en el conocimiento del problema de autovalores de sistemas viscoelásticos proponiendo para ello nuevos métodos numéricos de resolución. Por otro, desarrollar un nuevo modelo viscoso que, bajo ciertas condiciones, reproduzca la respuesta del modelo viscoelástico con su¿ciente aproximación. La Tesis se divide en ocho capítulos, de ellos el cuerpo principal se encuentra en los seis centrales (Capítulos 2 a 7. Todos ellos son artículos de investigación que, o bien han sido publicados, o bien están en proceso de revisión en revistas contenidas en el Journal Citation Reports (JCR). Por esta razón, todos los capítulos conservan la estructura intrínseca de un artículo, incluidas una introducción y una bibliografía en cada uno. Los cuatro primeros capítulos (Capítulos 2 a 5) se centran en el estudio del problema no lineal de autovalores. Se proponen dos metodologías de resolución: la primera es un procedimiento iterativo basado en el esquema del punto-¿jo y desarrollado para sistemas proporcionales o ligeramente no-proporcionales (aquellos en los que los modos se presentan desacoplados o casi desacoplados). La segunda metodología (presentada en dos capítulos diferentes), denominada paramétrica, permite obtener soluciones casi-analíticas de los autovalores, tanto para sistemas de un grado de libertad como para sistemas de múltiples grados de libertad y dentro de 'estos, para sistemas proporcionales y no proporcionales. El estudio del problema de autovalores se completa con un capítulo dedicado a los autovalores reales, también denominados autovalores no viscosos. En 'él se demuestra una nueva caracterización maten ática que deben cumplir dichos autovalores y que permite proponer un nuevo concepto: el conjunto no-viscoso. Los dos 'últimos capítulos (Capítulos 6 y 7) analizan el Modelo Viscoso Equivalente como propuesta para la modelización de la respuesta de sistemas viscoelásticos. El análisis se realiza desde el dominio de la frecuencia estudiando la función de transferencia. En una primera etapa (pen último capítulo), de naturaleza más maten ática, se demuestra que la función de transferencia exacta de un modelo viscoelástico se puede expresar como suma de una función de transferencia propia de un modelo viscoso más un término denominado residual, directamente dependiente del nivel de amortiguamiento inducido y del acoplamiento modal (noproporcionalidad de la matriz de amortiguamiento). En una segunda etapa ('ultimo capítulo), se desarrolla una aplicación para estructuras reales formadas por entramados planos de elementos 1D amortiguados con capas de material visco elástico. Este tipo de estructuras ha permitido usar una variante mejorada del método paramétrico para la obtención de los autovalores, de forma que en este 'ultimo capítulo ha servido como nexo de unión de las metodologías más importantes desarrolladas en la Tesis. / Lázaro Navarro, M. (2013). The Eigenvalue Problem in Linear Viscoelastic Structures: New Numerical Approaches and the Equivalent Viscous Model [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/30062 / TESIS