To see the other types of publications on this topic, follow the link: Newton algorithms.
Dissertations / Theses on the topic 'Newton algorithms'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Newton algorithms.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Wei, Ermin. "Distributed Newton-type algorithms for network resource allocation." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/60822.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (p. 99-101).<br>Most of today's communication networks are large-scale and comprise of agents with local information and heterogeneous preferences, making centralized control and coordination impractical. This motivated much interest in developing and studying distributed algorithms for network resource allocation problems, such as Internet routing, data collection and processing in sensor networks, and cross-layer communication network design. Existing works on network resource allocation problems rely on using dual decomposition and first-order (gradient or subgradient) methods, which involve simple computations and can be implemented in a distributed manner, yet suffer from slow rate of convergence. Second-order methods are faster, but their direct implementation requires computation intensive matrix inversion operations, which couple information across the network, hence cannot be implemented in a decentralized way. This thesis develops and analyzes Newton-type (second-order) distributed methods for network resource allocation problems. In particular, we focus on two general formulations: Network Utility Maximization (NUM), and network flow cost minimization problems. For NUM problems, we develop a distributed Newton-type fast converging algorithm using the properties of self-concordant utility functions. Our algorithm utilizes novel matrix splitting techniques, which enable both primal and dual Newton steps to be computed using iterative schemes in a decentralized manner with limited information exchange. Moreover, the step-size used in our method can be obtained via an iterative consensus-based averaging scheme. We show that even when the Newton direction and the step-size in our method are computed within some error (due to finite truncation of the iterative schemes), the resulting objective function value still converges superlinearly to an explicitly characterized error neighborhood. Simulation results demonstrate significant convergence rate improvement of our algorithm relative to the existing subgradient methods based on dual decomposition. The second part of the thesis presents a distributed approach based on a Newtontype method for solving network flow cost minimization problems. The key component of our method is to represent the dual Newton direction as the limit of an iterative procedure involving the graph Laplacian, which can be implemented based only on local information. Using standard Lipschitz conditions, we provide analysis for the convergence properties of our algorithm and show that the method converges superlinearly to an explicitly characterized error neighborhood, even when the iterative schemes used for computing the Newton direction and the stepsize are truncated. We also present some simulation results to illustrate the significant performance gains of this method over the subgradient methods currently used.<br>by Ermin Wei.<br>S.M.
2
Saadallah, A. F. "A new approach to quasi-Newton methods for minimization." Thesis, University of Essex, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.380374.
Full text
3
Klemes, Marek Carleton University Dissertation Engineering Electronics. "Fast robust Quasi-Newton adaptive algorithms for general array processing." Ottawa, 1996.
Find full text
4
Ghandhari, R. A. "On the use of function values to improve quasi-Newton methods." Thesis, University of Essex, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.328658.
Full text
5
Harrison, Anthony Westbrook. "Algorithms for Computing the Lattice Size." Kent State University / OhioLINK, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=kent1529781033957183.
Full text
6
Sassi, Carlos Alberto. "Sobre o desempenho de métodos Quase-Newton e aplicações." [s.n.], 2010. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306041.
Full textAbstract:
Orientador: Maria Aparecida Diniz Ehrhardt<br>Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica<br>Made available in DSpace on 2018-08-16T22:41:08Z (GMT). No. of bitstreams: 1
Sassi_Carlos_M.pdf: 2431422 bytes, checksum: 7e2d7456777a9a43cc62a5524d3fca93 (MD5)
Previous issue date: 2010<br>Resumo: Iniciamos este trabalho com o estudo de equações não lineares, transcendentais de uma única variável, com o objetivo principal de abordar sistemas de equações não lineares, analisar os métodos, algoritmos e realizar testes computacionais, embasados na plataforma MatLab "The Language of Technical computer - R2008a - version 7.6.0.324_. Os algoritmos tratados se referem ao método de Newton, métodos Quase-Newton, método Secante e aplicações, com enfoque na H-equação de Chandrasekhar. Estudamos aspectos de convergência de cada um destes métodos que puderam ser analisados na prática, a partir dos experimentos numéricos realizados<br>Abstract: This work begins with the study of nonlinear and transcendental equations, with only one variable, which has the main purpose to study systems of nonlinear equations, methods and algoritms, in order to accomplish computational tests using MatLab Codes "The Language of Technical computer - R2008a - version 7.6.0.324". These algoritms were concerned to Newton's method, Quasi-Newton method, Secant method, and the main application was the Chandrasekhar H-Equation. Convergence studies for these methods were analysed with the applied numerical methods<br>Mestrado<br>Matematica<br>Mestre em Matemática
7
Gaujoux, Renaud Gilles. "Resolução de sistema KKT por metodo de tipo Newton não diferenciavel." [s.n.], 2005. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306442.
Full textAbstract:
Orientador: Roberto Andreani<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica<br>Made available in DSpace on 2018-08-04T05:03:19Z (GMT). No. of bitstreams: 1
Gaujoux_RenaudGilles_M.pdf: 1743739 bytes, checksum: a3548a59bc983f4398cb0136c62c1d6a (MD5)
Previous issue date: 2005<br>Resumo: Esta dissertação trata da aplicação de um método de tipo Newton generalizado aos sistemas KKT. Graças às funções chamadas de NCP, o sistema KKT pode ser reformulado como uma equação do tipo H(z) = O, onde H é uma função semi-suave. Nos preliminares teóricos apresentamos os conceitos importantes para a análise desse tipo de sistema quando a função involvida não é diferenciável. Trata-se de subdiferencial, semi-suavidade, semi-derivada. Então, usando um ponto de vista global, descrevemos de uma vez só as diferentes generalizações do método de Newton, apresentando as condições suficientes de convergência local. Uma versão globalizada do método é também detalhada. Com o fim de aplicar o algoritmo à reformulação semi-suave do sistema KKT, estudamos as propriedades da função H, primeiro independentemente da função NCP usada. Então analisamos o caso de três funções NCP particulares: a função do Mínimo, a função de Fischer-Burmeister, a função de Fischer-Burmeister Penalizada. Apresentamos os resultados de testes numéricos que comparam o desempenho do algoritmo quando usa as diferentes funções NCP acima<br>Abstract: This work deals with the use of generalized Newton type method to solve KKT systems. By the mean of so called NCP functions, any KKT system can be writen as an equation of type H(z) = O, where H is a semismooth function. In a teorical preliminaries part, we present some key notions for the analysis of such a type of system, whose the involved function is not differentiable. It deals with subdifferential, semismoothness, semiderivative. Then, tackling the problem with a very general point of view, we make a unified description of different generalizations of N ewton method, giving sufficient local convergence conditions. More over, we detail a possible globalization of such methods. In order to use this global algorithm to solve semismooth form of KKT systems, we study some of the H function's properties, first without specifying any underlying NCP function, and then in the case of three known NCP functions: the minimum function, the Fischer-Burmeister function and the penalized Fischer-Burmeister function. Finally, we give the results of numerical tests, which compare the algorithm's performance for each of these three NCP functions<br>Mestrado<br>Matematica Aplicada<br>Mestre em Matemática Aplicada
8
Woodgate, K. G. "Optimization over positive semi-definite symmetric matrices with application to Quasi-Newton algorithms." Thesis, Imperial College London, 1987. http://hdl.handle.net/10044/1/46914.
Full text
9
Zanjácomo, Paulo Régis. "On weighted paths for nonlinear semidefinite complementarity problems and newton methods for semidefinite programming." Diss., Georgia Institute of Technology, 1998. http://hdl.handle.net/1853/21680.
Full text
10
Hüeber, Stefan. "Discretization techniques and efficient algorithms for contact problems." [S.l. : s.n.], 2008. http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-36087.
Full text
11
Abbas, Boushra. "Méthode de Newton régularisée pour les inclusions monotones structurées : étude des dynamiques et algorithmes associés." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS250/document.
Full textAbstract:
Cette thèse est consacrée à la recherche des zéros d'un opérateur maximal monotone structuré, à l'aide de systèmes dynamiques dissipatifs continus et discrets. Les solutions sont obtenues comme limites des trajectoires lorsque le temps t tend vers l'infini. On s'intéressera principalement aux dynamiques obtenues par régularisation de type Levenberg-Marquardt de la méthode de Newton. On décrira aussi les approches basées sur des dynamiques voisines.Dans un cadre Hilbertien, on s'intéresse à la recherche des zéros de l'opérateur maximal monotone structuré M = A + B, où A est un opérateur maximal monotone général et B est un opérateur monotone Lipschitzien. Nous introduisons des dynamiques continues et discrètes de type Newton régularisé faisant intervenir d'une façon séparée les résolvantes de l'opérateur A (implicites), et des évaluations de B (explicites). A l'aide de la représentation de Minty de l'opérateur A comme une variété Lipschitzienne, nous reformulons ces dynamiques sous une forme relevant du théorème de Cauchy-Lipschitz. Nous nous intéressons au cas particulier où A est le sous différentiel d'une fonction convexe, semi-continue inférieurement, et propre, et B est le gradient d'une fonction convexe, différentiable. Nous étudions le comportement asymptotique des trajectoires. Lorsque le terme de régularisation ne tend pas trop vite vers zéro, et en s'appuyant sur une analyse asymptotique de type Lyapunov, nous montrons la convergence des trajectoires. Par ailleurs, nous montrons la dépendance Lipschitzienne des trajectoires par rapport au terme de régularisation.Puis nous élargissons notre étude en considérant différentes classes de systèmes dynamiques visant à résoudre les inclusions monotones gouvernées par un opérateur maximal monotone structuré M = $partialPhi$+ B, où $partialPhi$ désigne le sous différentiel d'une fonction convexe, semicontinue inférieurement, et propre, et B est un opérateur monotone cocoercif. En s'appuyant sur une analyse asymptotique de type Lyapunov, nous étudions le comportement asymptotique des trajectoires de ces systèmes. La discrétisation temporelle de ces dynamiques fournit desalgorithmes forward-backward (certains nouveaux ).Finalement, nous nous intéressons à l'étude du comportement asymptotique des trajectoires de systèmes dynamiques de type Newton régularisé, dans lesquels on introduit un terme supplémentaire de viscosité évanescente de type Tikhonov. On obtient ainsi la sélection asymptotique d'une solution de norme minimale<br>This thesis is devoted to finding zeroes of structured maximal monotone operators, by using discrete and continuous dissipative dynamical systems. The solutions are obtained as the limits of trajectories when the time t tends towards infinity.We pay special attention to the dynamics that are obtained by Levenberg-Marquardt regularization of Newton's method. We also revisit the approaches based on some related dynamical systems.In a Hilbert framework, we are interested in finding zeroes of a structured maximal monotone operator M = A + B, where A is a general maximal monotone operator, and B is monotone and locally Lipschitz continuous. We introduce discrete and continuous dynamical systems which are linked to Newton's method. They involve separately B and the resolvents of A, and are designed to splitting methods. Based on the Minty representation of A as a Lipschitz manifold, we show that these dynamics can be formulated as differential systems, which are relevant to the Cauchy-Lipschitz theorem. We focus on the particular case where A is the subdifferential of a convex lower semicontinuous proper function, and B is the gradient of a convex, continuously differentiable function. We study the asymptotic behavior of trajectories. When the regularization parameter does not tend to zero too rapidly, and by using Lyapunov asymptotic analysis, we show the convergence of trajectories. Besides, we show the Lipschitz continuous dependence of the solution with respect to the regularization term.Then we extend our study by considering various classes of dynamical systems which aim at solving inclusions governed by structured monotone operators M = $partialPhi$+ B, where $partialPhi$ is the subdifferential of a convex lower semicontinuous function, and B is a monotone cocoercive operator. By a Lyapunov analysis, we show the convergence properties of the orbits of these systems. The time discretization of these dynamics gives various forward-backward splittingmethods (some new).Finally, we focus on the study of the asymptotic behavior of trajectories of the regularized Newton dynamics, in which we introduce an additional vanishing Tikhonov-like viscosity term.We thus obtain the asymptotic selection of the solution of minimal norm
12
Bokka, Naveen. "Comparison of Power Flow Algorithms for inclusion in On-line Power Systems Operation Tools." ScholarWorks@UNO, 2010. http://scholarworks.uno.edu/td/1237.
Full textAbstract:
The goal of this thesis is to develop a new, fast, adaptive load flow algorithm that "automatically alternates" numerical methods including Newton-Raphson method, Gauss-Seidel method and Gauss method for a load flow run to achieve less run time. Unlike the proposed method, the traditional load flow analysis uses only one numerical method at a time. This adaptive algorithm performs all the computation for finding the bus voltage angles and magnitudes, real and reactive powers for the given generation and load values, while keeping track of the proximity to convergence of a solution. This work focuses on finding the algorithm that uses multiple numerical techniques, rather than investigating programming techniques and programming languages. The convergence time is compared with those from using each of the numerical techniques. The proposed method is implemented on the IEEE 39-bus system with different contingencies and the solutions obtained are verified with PowerWorld Simulator, a commercial software for load flow analysis.
13
Chao, Tung-yo. "The numerical modelling of rockbolts in geomechanics by finite element methods." Thesis, Brunel University, 1999. http://bura.brunel.ac.uk/handle/2438/5137.
Full textAbstract:
In tunnel excavation, the use of rockbolts has long been a popular means of reinforcement in rock masses to prevent the rock opening from caving in. The idea has evolved from the earliest form of rockbolt made of wood to the more up-to-date form of pre-tensioned or grouted steel rockbolts. A major breakthrough in the design of rockbolt models was made by Aydan (1989). This rockbolt element was modelled in coupled form, with one sub-element representing the steel bolt, and the other sub-element the grout. This representation was necessary to model the complex action in the continuous rock mass near the joint. In elasticity problems, the large displacement formulation of a beam element is derived from the fundamental theory, and the bending phenomenon of a thin rod is analysed by the finite element discretizations of the bar elements and the beam elements. Experiments show that the deformation characteristics of the latter representation resemble a more realistic life behaviour. Based on this finding, this thesis proposes a modification to Aydan's two-dimensional rockbolt element, with the beam elements discretising the steel bolt. The different mechanical responses of a perfectly elastic rockbolt are considered, and the large displacement formulation of the new rockbolt element is derived by combining those of Aydan's rockbolt element and the beam element. The mechanics of the Aydan element and the new rockbolt element are described, and their performances are compared in an identical situation. It is found that in the two two-dimensional examples used in this thesis, the modified element ensures the continuity of curvature of the rockbolt, and in general, can act as support across a discontinuity or joint between rock masses well. In conjunction with the displacement method in the finite element procedures, a conventional iteration solution procedure is first described to solve the nonlinear incremental stiffness equation. However, it is found that this procedure is cumbersome, and requires a large amount of comptutations. Some limited storage quasi-Newton minimization algorithms are considered as an alternative.
14
Lewis, Andrew. "Parallel Optimisation Algorithms for Continuous, Non-Linear Numerical solutions." Thesis, Griffith University, 2004. http://hdl.handle.net/10072/367382.
Full textAbstract:
In computational science and engineering there are growing numbers of increasingly sophisticated, rigorous and realistic numerical simulations of physical systems. Detailed knowledge of a particular area of enquiry is expressed in mathematical terms, realised in computer programs and run on increasingly powerful computer systems. The use of such simulations is now commonplace in a growing collection of industrial design areas. Often, users of these models want to understand their behaviour in response to a variety of input stimuli, bounded by various operational parameters. Commonplace in the engineering design process is the need to find the combination of design parameters that minimise (or maximise) some design objective. Optimisation programs seek to apply mathematical techniques and heuristics to guide a computer in choosing trial parameter sets itself in an attempt to satisfy the expressed design objective.
The more realistic the numerical simulations become, the more demanding of computational resources they become. Many of them consume hours, or days, of computing time on supercomputers to deliver a single trial solution. Optimisation algorithms invariably require the model be run more than once, often many times. In the absence of any means to reduce the computational cost of a single run any further, there can be two responses to this dilemma: 1. reduce the number of model evaluations required by the optimisation algorithm, or 2. reduce the time the whole collection of model evaluations takes by running as many as possible at the same time. The research in this thesis is directed toward developing methods that use the approach of parallel computing to reduce total optimisation time by exploiting concurrency within the optimisation algorithms developed. For generality it assumes the numerical simulations to which it may be applied will have real-valued parameters, i.e. they are continuous, and that they may be non-linear in nature. The following contributions are described: 1. The idea of developing a set of 'sandbox' case studies for effective testing of optimisation algorithms is presented and established as a feasible alternative to the use of artificial test functions. An initial set of problems with varying characteristics is also presented. 2. A parallel implementation of the quasi-Newton gradient method with BFGS update and its efficacy in comparison to a corresponding sequential algorithm and widely-used method of simulated annealing is demonstrated. 3. The use of a method of parallel line search with the Nelder-Mead simplex algorithm and its advantages compared to the original algorithm, in speed and reliability, are clearly shown. 4. New direct search methods, the Reducing Set Concurrent Simplex (RSCS) algorithm with line searching variants, are presented, and their superior performance compared to a variety of direct search methods demonstrated. 5. A novel Evolutionary Programming algorithm using concepts of self-organised criticality, EPSOC, is presented, and demonstrated to be superior in performance to a wide variety of gradient, direct search and stochastic methods on a set of test cases drawn from real-world problems. Evidence is presented of its potential for multi-objective optimisation using a novel implementation with multiple, 'virtual' archives. 6. Methods of preconditioning optimisation problems to reduce the total time taken to achieve an optimal result are presented. Temporal preconditioning, based on the time behaviour of the numerical simulations, is demonstrated to yield substantial speedup. 7. Some conclusions have been drawn on the applicability of specific optimisation methods to different classes of real-world problems. All of the methods described are implemented in the framework of a general-purpose optimisation toolset, Nimrod/O, to provide a sound basis for future work, easy adoption across a wide range of engineering design problems and potential commercial application.<br>Thesis (PhD Doctorate)<br>Doctor of Philosophy (PhD)<br>School of Computing and Information Technology<br>Full Text
15
Clausner, André. "Anwendung von Line-Search-Strategien zur Formoptimierung und Parameteridentifikation." Master's thesis, Universitätsbibliothek Chemnitz, 2013. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-114858.
Full textAbstract:
Die kontinuierliche Weiterentwicklung und Verbesserung technischer Prozesse erfolgt heute auf der Basis stochastischer und deterministischer Optimierungsstrategien in Kombination mit der numerischen Simulation dieser Abläufe. Da die FE-Simulation von Umformvorgängen in der Regel sehr zeitintensiv ist, bietet sich für die Optimierung solcher Prozesse der Einsatz deterministischer Methoden an, da hier weniger Optimierungsschritte und somit auch weniger FE-Simulationen notwendig sind. Eine wichtige Anforderung an solche Optimierungsverfahren ist globale Konvergenz zu lokalen Minima, da die optimalen Parametersätze nicht immer näherungsweise bekannt sind. Die zwei wichtigsten Strategien zum Ausdehnen des beschränkten Konvergenzradius der natürlichen Optimierungsverfahren (newtonschrittbasierte Verfahren und Gradientenverfahren) sind die Line-Search-Strategie und die Trust-Region-Strategie. Die Grundlagen der Line-Search-Strategie werden aufgearbeitet und die wichtigsten Teilalgorithmen implementiert. Danach wird dieses Verfahren auf eine effiziente Kombination der Teilalgorithmen und Verfahrensparameter hin untersucht. Im Anschluss wird die Leistung eines Optimierungsverfahrens mit Line-Search-Strategie verglichen mit der eines ebenfalls implementierten Optimierungsverfahrens mit skalierter Trust-Region-Strategie. Die Tests werden nach Einfügen der implementierten Verfahren in das Programm SPC-Opt anhand der Lösung eines Quadratmittelproblems aus der Materialparameteridentifikation sowie der Formoptimierung eines Umformwerkzeugs vorgenommen.
16
Nilsson, Max. "Performance Comparison of Localization Algorithms for UWB Measurements with Closely Spaced Anchors." Thesis, Luleå tekniska universitet, Rymdteknik, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-70996.
Full textAbstract:
Tracking objects or people in an indoor environment has a wide variety of uses in many different areas, similarly to positioning systems outdoors. Indoor positioning systems operate in a very different environment however, having to deal with obstructions while also having high accuracy. A common solution for indoor positioning systems is to have three or more stationary anchor antennas spread out around the perimeter of the area that is to be monitored. The position of a tag antenna moving in range of the anchors can then be found using trilateration. One downside of such a setup is that the anchors must be setup in advance, meaning that rapid deployment to new areas of such a system may be impractical. This thesis aims to investigate the possibility of using a different setup, where three anchors are placed close together, so as to fit in a small hand-held device. This would allow the system to be used without any prior setup of anchors, making rapid deployment into new areas more feasible. The measurements done by the antennas for use in trilateration will always contain noise, and as such algorithms have had to be developed in order to obtain an approximation of the position of a tag in the presence of noise. These algorithms have been developed with the setup of three spaced out anchors in mind, and may not be sufficiently accurate when the anchors are spaced very closely together. To investigate the feasibility of such a setup, this thesis tested four different algorithms with the proposed setup, to see its impact on the performance of the algorithms. The algorithms tested are the Weighted Block Newton, Weighted Clipped Block Newton, Linear Least Squares and Non-Linear Least Squares algorithms. The Linear Least Squares algorithm was also run with measurements that were first run through a simple Kalman filter. Previous studies have used the algorithms to find an estimated position of the tag and compared their efficiency using the positional error of the estimate. This thesis will also use the positional estimates to determine the angular position of the estimate in relation to the anchors, and use that to compare the algorithms. Measurements were done using DWM1001 Ultra Wideband (UWB) antennas, and four different cases were tested. In case 1 the anchors and tag were 10 meters apart in line-of-sight, case two were the same as case 1 but with a person standing between the tag and the anchors. In case 3 the tag was moved behind a wall with an adjacent open door, and in case 4 the tag was in the same place as in case 3 but the door was closed. The Linear Least Squares algorithm using the filtered measurements was found to be the most effective in all cases, with a maximum angular error of less than 5$^\circ$ in the worst case. The worst case here was case 2, showing that the influence of a human body has a strong effect on the UWB signal, causing large errors in the estimates of the other algorithms. The presence of a wall in between the anchors and tag was found to have a minimal impact on the angular error, while having a larger effect on the spatial error. Further studies regarding the effects of the human body on UWB signals may be necessary to determine the feasibility of handheld applications, as well as the effect of the tag and/or the anchors moving on the efficiency of the algorithms.
17
Mishchenko, Kateryna. "Numerical Algorithms for Optimization Problems in Genetical Analysis." Doctoral thesis, Västerås : Scool of education, Culture and Communication, Mälardalen University, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-650.
Full text
18
Johansson, Sven. "Active Control of Propeller-Induced Noise in Aircraft : Algorithms & Methods." Doctoral thesis, Karlskrona, Ronneby : Blekinge Institute of Technology, 2000. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-00171.
Full textAbstract:
In the last decade acoustic noise has become more and more regarded as a problem. In cars, boats, trains and aircraft, low-frequency noise reduces comfort. Lightweight materials and more powerful engines are used in high-speed vehicles, resulting in a general increase in interior noise levels. Low-frequency noise is annoying and during periods of long exposure it causes fatigue and discomfort. The masking effect which low-frequency noise has on speech reduces speech intelligibility. Low-frequency noise is sought to be attenuated in a wide range of applications in order to improve comfort and speech intelligibility. The use of conventional passive methods to attenuate low-frequency noise is often impractical since considerable bulk and weight are required; in transportation large weight is associated with high fuel consumption. In order to overcome the problems of ineffective passive suppression of low-frequency noise, the technique of active noise control has become of considerable interest. The fundamental principle of active noise control is based on secondary sources producing ``anti-noise.'' Destructive interference between the generated and the primary sound fields results in noise attenuation. Active noise control systems significantly increase the capacity for attenuating low-frequency noise without major increase in volume and weight. This doctoral dissertation deals with the topic of active noise control within the passenger cabin in aircraft, and within headsets. The work focuses on methods, controller structures and adaptive algorithms for attenuating tonal low-frequency noise produced by synchronized or moderately synchronized propellers generating beating sound fields. The control algorithm is a central part of an active noise control system. A multiple-reference feedforward controller based on the novel actuator-individual normalized Filtered-X Least-Mean-Squares algorithm is introduced, yielding significant attenuation of such period noise. This algorithm is of the LMS-type, and owing to the novel normalization it can also be regarded as a Newton-type algorithm. The new algorithm combines low computational complexity with high performance. For that reason the algorithm is suitable for use in systems with a large number of control sources and control sensors in order to reduce the computional power required by the control system. The computational power of the DSP hardware is limited, and therefore algorithms with high computational complexity allow fewer control sources and sensors to be used, often with reduced noise attenuation as a result. In applications, such as controlling aircraft cabin noise, where a large multiple-channel system is needed to control the relative complex interior sound field, it is of great importance to keep down the computational complexity of the algorithm so that a large number of loudspeakers and microphones can be used. The dissertation presents theoretical work, off-line computer experiments and practical real-time experiments using the actuator-individual normalized algorithm. The computer experiments are principally based on real-life cabin noise data recorded during flight in a twin-engine propeller aircraft and in a helicopter. The practical experiments were carried out in a full-scale fuselage section from a propeller aircraft.<br>Buller i vår dagliga miljö kan ha en negativ inverkan på vår hälsa. I många sammanhang, i tex bilar, båtar och flygplan, förekommer lågfrekvent buller. Lågfrekvent buller är oftast inte skadligt för hörseln, men kan vara tröttande och försvåra konversationen mellan personer som vistas i en utsatt miljö. En dämpning av bullernivån medför en förbättrad taluppfattbarhet samt en komfortökning. Att dämpa lågfrekvent buller med traditionella passiva metoder, tex absorbenter och reflektorer, är oftast ineffektivt. Det krävs stora, skrymmande absorbenter för att dämpa denna typ av buller samt tunga skiljeväggar för att förhindra att bullret transmitteras vidare från ett utrymme till ett annat. Metoder som är mera lämpade vid dämpning av lågfrekvent buller är de aktiva. De aktiva metoderna baseras på att en vågrörelse som ligger i motfas med en annan överlagras och de släcker ut varandra. Bullerdämpningen erhålls genom att ett ljudfält genereras som är lika starkt som bullret men i motfas med detta. De aktiva bullerdämpningsmetoderna medför en effektiv dämpning av lågfrekvent buller samtidigt som volymen, tex hos bilkupen eller båt/flygplanskabinen ej påverkas nämnvärt. Dessutom kan fordonets/farkostens vikt reduceras vilket är tacksamt för bränsleförbrukningen. I de flesta tillämpningar varierar bullrets karaktär, dvs styrka och frekvensinnehåll. För att följa dessa variationer krävs ett adaptivt (självinställande) reglersystem som styr genereringen av motljudet. I propellerflygplan är de dominerande frekvenserna i kabinbullret relaterat till propellrarnas varvtal, man känner alltså till frekvenserna som skall dämpas. Man utnyttjar en varvtalssignal för att generera signaler, så kallade referenssignaler, med de frekvenser som skall dämpas. Dessa bearbetas av ett reglersystem som generar signaler till högtalarna som i sin tur generar motljudet. För att ställa in högtalarsignalerna så att en effektiv dämpning erhålls, används mikrofoner utplacerade i kabinen som mäter bullret. För att åstadkomma en effektiv bullerdämpning i ett rum, tex i en flygplanskabin, behövs flera högtalare och mikrofoner, vilket kräver ett avancerat reglersystem. I doktorsavhandlingen ''Active Control of Propeller-Induced Noise in Aircraft'' behandlas olika metoder för att reducera kabinbuller härrörande från propellrarna. Här presenteras olika strukturer på reglersystem samt beräkningsalgoritmer för att ställa in systemet. För stora system där många högtalare och mikrofoner används, samt flera frekvenser skall dämpas, är det viktigt att systemet inte behöver för stor beräkningskapacitet för att generera motljudet. Metoderna som behandlas ger en effektiv dämpning till låg beräkningskostnad. Delar av materialet som presenteras i avhandlingen har ingått i ett EU-projekt med inriktning mot bullerundertryckning i propellerflygplan. I projektet har flera europeiska flygplanstillverkare deltagit. Avhandlingen behandlar även aktiv bullerdämpning i headset, som används av helikopterpiloter. I denna tillämpning har aktiv bullerdämpning används för att öka taluppfattbarheten.
19
Clausner, André. "Möglichkeiten zur Steuerung von Trust-Region Verfahren im Rahmen der Parameteridentifikation." Thesis, Universitätsbibliothek Chemnitz, 2013. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-114847.
Full textAbstract:
Zur Simulation technischer Prozesse ist eine hinreichend genaue Beschreibung des Materialverhaltens notwendig. Die hierfür häufig verwendeten phänomenologischen Ansätze, wie im vorliegenden Fall die HILLsche Fließbedingung, enthalten materialspezifische Parameter, welche nicht direkt messbar sind. Die Identifikation dieser Materialparameter erfolgt in der Regel durch Minimierung eines Fehlerquadratfunktionals, welches Differenzen von Messwerten und zugehörigen numerisch berechneten Vergleichswerten enthält. In diesem Zusammenhang haben sich zur Lösung dieser Minimierungsaufgabe die Trust-Region Verfahren als gut geeignet herausgestellt. Die Aufgabe besteht darin, die verschiedenen Möglichkeiten zur Steuerung eines Trust-Region Verfahrens, im Hinblick auf die Eignung für das vorliegende Identifikationsproblem, zu untersuchen. Dazu werden die Quadratmittelprobleme und deren Lösungsverfahren überblicksmäßig betrachtet. Danach wird näher auf die Trust-Region Verfahren eingegangen, wobei sich im Weiteren auf Verfahren mit positiv definiten Ansätzen für die Hesse-Matrix, den Levenberg-Marquardt Verfahren, beschränkt wird. Danach wird ein solcher Levenberg-Marquardt Algorithmus in verschiedenen Ausführungen implementiert und an dem vorliegenden Identifikationsproblem getestet. Als Ergebnis stellt sich eine gute Kombination aus verschiedenen Teilalgorithmen des Levenberg-Marquardt Algorithmus mit einer hohen Konvergenzgeschwindigkeit heraus, welche für das vorliegende Problem gut geeignet ist.
20
Savas, Berkant. "Algorithms in data mining using matrix and tensor methods." Doctoral thesis, Linköpings universitet, Beräkningsvetenskap, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-11597.
Full textAbstract:
In many fields of science, engineering, and economics large amounts of data are stored and there is a need to analyze these data in order to extract information for various purposes. Data mining is a general concept involving different tools for performing this kind of analysis. The development of mathematical models and efficient algorithms is of key importance. In this thesis we discuss algorithms for the reduced rank regression problem and algorithms for the computation of the best multilinear rank approximation of tensors. The first two papers deal with the reduced rank regression problem, which is encountered in the field of state-space subspace system identification. More specifically the problem is \[ \min_{\rank(X) = k} \det (B - X A)(B - X A)\tp, \] where $A$ and $B$ are given matrices and we want to find $X$ under a certain rank condition that minimizes the determinant. This problem is not properly stated since it involves implicit assumptions on $A$ and $B$ so that $(B - X A)(B - X A)\tp$ is never singular. This deficiency of the determinant criterion is fixed by generalizing the minimization criterion to rank reduction and volume minimization of the objective matrix. The volume of a matrix is defined as the product of its nonzero singular values. We give an algorithm that solves the generalized problem and identify properties of the input and output signals causing a singular objective matrix. Classification problems occur in many applications. The task is to determine the label or class of an unknown object. The third paper concerns with classification of handwritten digits in the context of tensors or multidimensional data arrays. Tensor and multilinear algebra is an area that attracts more and more attention because of the multidimensional structure of the collected data in various applications. Two classification algorithms are given based on the higher order singular value decomposition (HOSVD). The main algorithm makes a data reduction using HOSVD of 98--99 \% prior the construction of the class models. The models are computed as a set of orthonormal bases spanning the dominant subspaces for the different classes. An unknown digit is expressed as a linear combination of the basis vectors. The resulting algorithm achieves 5\% in classification error with fairly low amount of computations. The remaining two papers discuss computational methods for the best multilinear rank approximation problem \[ \min_{\cB} \| \cA - \cB\| \] where $\cA$ is a given tensor and we seek the best low multilinear rank approximation tensor $\cB$. This is a generalization of the best low rank matrix approximation problem. It is well known that for matrices the solution is given by truncating the singular values in the singular value decomposition (SVD) of the matrix. But for tensors in general the truncated HOSVD does not give an optimal approximation. For example, a third order tensor $\cB \in \RR^{I \x J \x K}$ with rank$(\cB) = (r_1,r_2,r_3)$ can be written as the product \[ \cB = \tml{X,Y,Z}{\cC}, \qquad b_{ijk}=\sum_{\lambda,\mu,\nu} x_{i\lambda} y_{j\mu} z_{k\nu} c_{\lambda\mu\nu}, \] where $\cC \in \RR^{r_1 \x r_2 \x r_3}$ and $X \in \RR^{I \times r_1}$, $Y \in \RR^{J \times r_2}$, and $Z \in \RR^{K \times r_3}$ are matrices of full column rank. Since it is no restriction to assume that $X$, $Y$, and $Z$ have orthonormal columns and due to these constraints, the approximation problem can be considered as a nonlinear optimization problem defined on a product of Grassmann manifolds. We introduce novel techniques for multilinear algebraic manipulations enabling means for theoretical analysis and algorithmic implementation. These techniques are used to solve the approximation problem using Newton and Quasi-Newton methods specifically adapted to operate on products of Grassmann manifolds. The presented algorithms are suited for small, large and sparse problems and, when applied on difficult problems, they clearly outperform alternating least squares methods, which are standard in the field.
21
Marin, Manuel. "GPU-enhanced power flow analysis." Thesis, Perpignan, 2015. http://www.theses.fr/2015PERP0041.
Full textAbstract:
Cette thèse propose un large éventail d'approches afin d'améliorer différents aspects de l'analyse des flux de puissance avec comme fils conducteur l'utilisation du processeurs graphiques (GPU). Si les GPU ont rapidement prouvés leurs efficacités sur des applications régulières pour lesquelles le parallélisme de données était facilement exploitable, il en est tout autrement pour les applications dites irrégulières. Ceci est précisément le cas de la plupart des algorithmes d'analyse de flux de puissance. Pour ce travail, nous nous inscrivons dans cette problématique d'optimisation de l'analyse de flux de puissance à l'aide de coprocesseur de type GPU. L'intérêt est double. Il étend le domaine d'application des GPU à une nouvelle classe de problème et/ou d'algorithme en proposant des solutions originales. Il permet aussi à l'analyse des flux de puissance de rester pertinent dans un contexte de changements continus dans les systèmes énergétiques, et ainsi d'en faciliter leur évolution. Nos principales contributions liées à la programmation sur GPU sont: (i) l'analyse des différentes méthodes de parcours d'arbre pour apporter une réponse au problème de la régularité par rapport à l'équilibrage de charge ; (ii) l'analyse de l'impact du format de représentation sur la performance des implémentations d'arithmétique floue. Nos contributions à l'analyse des flux de puissance sont les suivantes: (ii) une nouvelle méthode pour l'évaluation de l'incertitude dans l'analyse des flux de puissance ; (ii) une nouvelle méthode de point fixe pour l'analyse des flux de puissance, problème que l'on qualifie d'intrinsèquement parallèle<br>This thesis addresses the utilization of Graphics Processing Units (GPUs) for improving the Power Flow (PF) analysis of modern power systems. Currently, GPUs are challenged by applications exhibiting an irregular computational pattern, as is the case of most known methods for PF analysis. At the same time, the PF analysis needs to be improved in order to cope with new requirements of efficiency and accuracy coming from the Smart Grid concept. The relevance of GPU-enhanced PF analysis is twofold. On one hand, it expands the application domain of GPU to a new class of problems. On the other hand, it consistently increases the computational capacity available for power system operation and design. The present work attempts to achieve that in two complementary ways: (i) by developing novel GPU programming strategies for available PF algorithms, and (ii) by proposing novel PF analysis methods that can exploit the numerous features present in GPU architectures. Specific contributions on GPU computing include: (i) a comparison of two programming paradigms, namely regularity and load-balancing, for implementing the so-called treefix operations; (ii) a study of the impact of the representation format over performance and accuracy, for fuzzy interval algebraic operations; and (iii) the utilization of architecture-specific design, as a novel strategy to improve performance scalability of applications. Contributions on PF analysis include: (i) the design and evaluation of a novel method for the uncertainty assessment, based on the fuzzy interval approach; and (ii) the development of an intrinsically parallel method for PF analysis, which is not affected by the Amdahl's law
22
Altoumaimi, Rasha Talal. "Nonlinear Least-Square Curve Fitting of Power-Exponential Functions: Description and comparison of different fitting methods." Thesis, Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-38606.
Full textAbstract:
This thesis examines how to find the best fit to a series of data points when curve fitting using power-exponential models. We describe the different numerical methods such as the Gauss-Newton and Levenberg-Marquardt methods to compare them for solving non-linear least squares of curve fitting using different power-exponential functions. In addition, we show the results of numerical experiments that illustrate the effectiveness of this approach.Furthermore, we show its application to the practical problems by using different sets of data such as death rates and rocket-triggered lightning return strokes based on the transmission line model.
23
Maciel, Osenildo Marques. "Algoritmos Quase-Newton para otimização multiobjetivo." Universidade Federal do Amazonas, 2016. http://tede.ufam.edu.br/handle/tede/5627.
Full textAbstract:
Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-22T18:10:23Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Osenildo M. Maciel.pdf: 1271016 bytes, checksum: d18538c8482aeb9b2cf836dcf47cab90 (MD5)<br>Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-22T18:10:36Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Osenildo M. Maciel.pdf: 1271016 bytes, checksum: d18538c8482aeb9b2cf836dcf47cab90 (MD5)<br>Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-22T18:10:51Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Osenildo M. Maciel.pdf: 1271016 bytes, checksum: d18538c8482aeb9b2cf836dcf47cab90 (MD5)<br>Made available in DSpace on 2017-03-22T18:10:51Z (GMT). No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Osenildo M. Maciel.pdf: 1271016 bytes, checksum: d18538c8482aeb9b2cf836dcf47cab90 (MD5)
Previous issue date: 2016-08-12<br>FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas<br>In this work, characterization are presented solutions for unconstrained multiobjective
optimization for the cases of convex and non-convex function. The theoretical foundation
of the convex case discusses a local solution obtained by solving a convex problem and
some additional assumptions. For nonconvex case we show that the algorithm have a global
convergence, in which the theoretical foundations ensure that curvature condition is obtained.<br>Neste trabalho, apresentam-se caracterizações de soluções para Otimização Multiobjetivo
Irrestrita para os casos de funções convexas e não convexas. A fundamentação teórica do
caso convexo discorre sobre uma solução local, obtida através da resolução de um problema
convexo e algumas hipóteses adicionais. Para o caso não convexo, mostramos que o algoritmo
tem convergência global, no qual os fundamentos teóricos asseguram que a condição de
curvatura é obtida
24
Kostka, Filip. "Umělá neuronová síť pro modelování polí uvnitř automobilu." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2014. http://www.nusl.cz/ntk/nusl-220578.
Full textAbstract:
The project deals with artificial neural networks. After designing and debugging the test data set and the training sample set, we created a multilayer perceptron network in the Neural NetworkToolbox (NNT) of Matlab. When creating networks, we used different training algorithms and algorithms improving the generalization of the network. When creating a radial basis network, we did not use the NNT, but a specific source code in Matlab was written. Functionality of neural networks was tested on simple training and testing patterns. Realistic training data were obtained by the simulation of twelve monoconic antennas operating in the frequency range from 2 to 6 GHz. Antennas were located inside a mathematical model of Octavia II. Using CST simulations, electromagnetic fields in a car were obtained. Trained networks are described by regressive characteristics andthe mean square error of training. Algorithms improving generalization are applied on the created and trained networks. The performance of individual networks is mutually compared.
25
Silva, Isaac Dayan Bastos da. "An?lise e compara??o entre algoritmos de percola??o." Universidade Federal do Rio Grande do Norte, 2008. http://repositorio.ufrn.br:8080/jspui/handle/123456789/17000.
Full textAbstract:
Made available in DSpace on 2014-12-17T15:26:35Z (GMT). No. of bitstreams: 1
IsaacDBS.pdf: 539336 bytes, checksum: ac9f1f2543159f0c009f0242077b1d5c (MD5)
Previous issue date: 2008-07-25<br>In this work, we study and compare two percolation algorithms, one of then elaborated by Elias, and the other one by Newman and Ziff, using theorical tools of algorithms complexity and another algorithm that makes an experimental comparation. This work is divided in three chapters. The first one approaches some necessary definitions and theorems to a more formal mathematical study of percolation. The second presents technics that were used for the estimative calculation of the algorithms complexity, are they: worse case, better case e average case. We use the technique of the worse case to estimate the complexity of both algorithms and thus we can compare them. The last chapter shows several characteristics of each one of the algorithms and through the theoretical estimate of the complexity and the comparison between the execution time of the most important part of each one, we can compare these important algorithms that simulate the percolation.<br>Nesta disserta??o estudamos e comparamos dois algoritmos de percola??o, um elaborado por Elias e o outro por Newman e Ziff, utilizando ferramentas te?ricas da complexidade de algoritmos e um algoritmo que efetuou uma compara??o experimental. Dividimos este trabalho em tr?s cap?tulos. O primeiro aborda algumas defini??es e teoremas necess?rios a um estudo matem?tico mais formal da percola??o. O segundo apresenta t?cnicas utilizadas para o c?lculo estimativo de complexidade de algoritmos, sejam elas: pior caso, melhor caso e caso m?dio. Utilizamos a t?cnica do pior caso para estimar a complexidade de ambos algoritmos e assim podermos compar?-los. O ?ltimo cap?tulo mostra diversas caracter?sticas de cada um dos algoritmos e atrav?s da estima- tiva te?rica da complexidade e da compara??o entre os tempos de execu??o da parte mais importante de cada um, conseguimos comparar esses importantes algoritmos que simulam a percola??o
26
FURTADO, Vagner Guidotti. "Circuitos divisores Newton-Raphson e Goldschmidt otimizados para filtro adaptativo NLMS aplicado no cancelamento de interferência." Universidade Catolica de Pelotas, 2017. http://tede.ucpel.edu.br:8080/jspui/handle/jspui/693.
Full textAbstract:
Submitted by Cristiane Chim (cristiane.chim@ucpel.edu.br) on 2018-05-08T17:34:22Z
No. of bitstreams: 1
Vagner Guidotti Furtado (1).pdf: 2942442 bytes, checksum: a43c18ecb28456284d4b6c622f11210d (MD5)<br>Made available in DSpace on 2018-05-08T17:34:22Z (GMT). No. of bitstreams: 1
Vagner Guidotti Furtado (1).pdf: 2942442 bytes, checksum: a43c18ecb28456284d4b6c622f11210d (MD5)
Previous issue date: 2017-12-07<br>The division operation in digital systems has its relevance because it is a necessary
function in several applications, such as general purpose processors, digital signal processors
and microcontrollers. The digital divider circuit is of great architectural complexity and may
occupy a considerable area in the design of an integrated circuit, and as a consequence may
have a great influence on the static and dynamic power dissipation of the circuit as a whole. In
relation to the application of dividing circuits in circuits of the Digital Signal Processing
(DSP) area, adaptive filters have a particular appeal, especially when using algorithms that
perform a normalization in the input signals. In view of the above, this work focuses on the
proposition of algorithms, techniques for reducing energy consumption and logical area,
proposition and implementation of efficient dividing circuit architectures for use in adaptive
filters. The Newton-Raphson and Goldschmidt iterative dividing circuits both operating at
fixed-point were specifically addressed. The results of the synthesis of the implemented
architectures of the divisors with the proposed algorithms and techniques showed
considerable reduction of power and logical area of the circuits. In particular, the dividing
circuits were applied in adaptive filter architectures based on the NLMS (Normalized least
Mean Square) algorithm, seeking to add to these filters, characteristics of good convergence
speed, combined with the improvement in energy efficiency. The adaptive filters
implemented are used in the case study of harmonic cancellation on electrocardiogram
signals<br>A operação de divisão em sistemas digitais tem sua relevância por se tratar de uma
função necessária em diversas aplicações, tais como processadores de propósito geral,
processadores digitais de sinais e microcontroladores. O circuito divisor digital é de grande
complexidade arquitetural, podendo ocupar uma área considerável no projeto de um circuito
integrado, e por consequência pode ter uma grande influência na dissipação de potência
estática e dinâmica do circuito como um todo. Em relação à aplicação de circuitos divisores
em circuitos da área DSP (Digital Signal Processing), os filtros adaptativos têm um particular
apelo, principalmente quando são utilizados algoritmos que realizam uma normalização nos
sinais de entrada. Diante do exposto, este trabalho foca na proposição de algoritmos, técnicas
de redução de consumo de energia e área lógica, proposição e implementação de arquiteturas
de circuitos divisores eficientes para utilização em filtros adaptativos. Foram abordados em
específico os circuitos divisores iterativos Newton-Raphson e Goldschmidt ambos operando
em ponto-fixo. Os resultados da síntese das arquiteturas implementadas dos divisores com os
algoritmos e técnicas propostas mostraram considerável redução de potência e área lógica dos
circuitos. Em particular, os circuitos divisores foram aplicados em arquiteturas de filtros
adaptativos baseadas no algoritmo NLMS (Normalized least Mean Square), buscando agregar
a esses filtros, características de boa velocidade de convergência, aliada à melhoria na
eficiência energética. Os filtros adaptativos implementados são utilizados no estudo de caso
de cancelamento de harmônicas em sinais de eletrocardiograma (ECG)
27
Margotti, Fábio Junior. "Métodos tipo Newton inexatos para problemas inversos." reponame:Repositório Institucional da UFSC, 2012. http://repositorio.ufsc.br/xmlui/handle/123456789/95234.
Full textAbstract:
Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas, Programa de Pós-Graduação em Matemática e Computação Científica, Florianópolis, 2011<br>Made available in DSpace on 2012-10-25T22:52:46Z (GMT). No. of bitstreams: 1
291662.pdf: 1027652 bytes, checksum: 9e51b4ba7a328f2f1b06375a27637852 (MD5)<br>Essa dissertação se dedica ao estudo de dois algoritmos do tipo Newton inexatos, usados para a obtenção de soluções regularizadas de problemas inversos não lineares e mal postos. O estudo abrange as propriedades de convergência e estabilidade das soluções computadas pelos algoritmos iterativos em questão, além de estabelecer e analisar taxas de convergência mediante condições de fonte assumidas. Uma implementação numérica de identificação de parâmetro num problema elíptico é feita ao final do trabalho e dá o suporte necessário para a verificação dos resultados teóricos.
28
Munnae, Jomkwun. "Uncalibrated robotic visual servo tracking for large residual problems." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/37219.
Full textAbstract:
In visually guided control of a robot, a large residual problem occurs when the robot configuration is not in the neighborhood of the target acquisition configuration. Most existing uncalibrated visual servoing algorithms use quasi-Gauss-Newton methods which are effective for small residual problems. The solution used in this study switches between a full quasi-Newton method for large residual case and the quasi-Gauss-Newton methods for the small case. Visual servoing to handle large residual problems for tracking a moving target has not previously appeared in the literature.
For large residual problems various Hessian approximations are introduced including an approximation of the entire Hessian matrix, the dynamic BFGS (DBFGS) algorithm, and two distinct approximations of the residual term, the modified BFGS (MBFGS) algorithm and the dynamic full Newton method with BFGS (DFN-BFGS) algorithm. Due to the fact that the quasi-Gauss-Newton method has the advantage of fast convergence, the quasi-Gauss-Newton step is used as the iteration is sufficiently near the desired solution. A switching algorithm combines a full quasi-Newton method and a quasi-Gauss-Newton method. Switching occurs if the image error norm is less than the switching criterion, which is heuristically selected.
An adaptive forgetting factor called the dynamic adaptive forgetting factor (DAFF) is presented. The DAFF method is a heuristic scheme to determine the forgetting factor value based on the image error norm. Compared to other existing adaptive forgetting factor schemes, the DAFF method yields the best performance for both convergence time and the RMS error.
Simulation results verify validity of the proposed switching algorithms with the DAFF method for large residual problems. The switching MBFGS algorithm with the DAFF method significantly improves tracking performance in the presence of noise. This work is the first successfully developed model independent, vision-guided control for large residual with capability to stably track a moving target with a robot.
29
Bocanegra, Silvana. "Algoritmos de Newton-Krylov precondicionados para métodos de pontos interiores." Universidade Federal de Minas Gerais, 2005. http://hdl.handle.net/1843/RVMR-6JTN72.
Full textAbstract:
Interior point methods have been widely used to solve large-scale linear programming problems. The bulk of the work in these methods is computing the search direction by solving one or more linear systems. The most commom approach in interior point solvers uses Cholesky sparse factorization to solve these systems. In some problems this factorization becomes prohibitive due to storage and time limitations. Iterative approaches are more interesting in these situations. Since these systems are ill-conditioned, it is crucial to develop ecient econditioners. However it is dicult to find a preconditioning strategy that produces good performance of iterative methods over the entire course of the interior point iterations. We are proposing a hybrid approach to solve these systems. The preconditioned conjugate gradient method works in two phases. During phase I it uses a kind of incomplete Cholesky preconditioner such that fill-in can be controlled in terms of available memory. As the optimal solution of the problem is approached, the linear systems become highly ill-conditioned and the method changes to phase II. In this phase a preconditioner based on the LU factorization is found to work better near a solution of the LP problem. Thenumerical experiments reveal that the iterative hybrid approach works better than Cholesky factorization on some classes of large-scale problems.<br>Métodos de pontos interiores têm sido amplamente usados na solução de problemas de programação linear de grande porte. A cada iteração destes métodos é necessário resolver um sistema de equações lineares para calcular a direção de Newton. Esta é a tarefa que demanda a maior parte do tempo de processamento e deve ser feita de forma eficiente. A abordagem mais utilizada em métodos de pontos interiores implementa a fatoração de Cholesky, no entanto, esta fatoração pode ser densa em algumas classes de problemas. Nestes casos, o uso de métodos iterativos torna-se mais interessante, desde que sejam aplicados com precondicionadores eficientes. Devido a dificuldade de encontrar estratégias de precondicionamento que apresentam bons resultados durante todas as iterações de pontos interiores estamos propondo uma abordagem iterativa híbrida para resolver estes sistemas. O método do gradiente conjugado é precondicionado nas iterações iniciais (fase I) usando um tipo de fatoração incompleta de Cholesky na qual o preenchimento pode ser controlado em termos da memória disponível e nas últimas iterações (fase II) usando um precondicionador baseado na fatoração LU que apresenta melhores resultados nas proximidades da solução ótima. A troca de fases ocorre quando a fatoração controlada de Cholesky começa a perder eficiência tornando lenta a convergência pelo método do gradiente conjugado. Experimentos numéricos revelam que a abordagem híbrida apresenta desempenho superior quando comparada a abordagem direta na solução de algumas classes de problemas de programação linear de grande porte.
30
Liu, Qi. "CIRCE a new software to predict the steady state equilibrium of chemical reactions." Thesis, Compiègne, 2018. http://www.theses.fr/2018COMP2455/document.
Full textAbstract:
L'objectif de cette thèse est de développer un nouveau code pour prédire l'équilibre final d'un processus chimique complexe impliquant beaucoup de produits, plusieurs phases et plusieurs processus chimiques. Des méthodes numériques ont été développées au cours des dernières décennies pour prédire les équilibres chimiques finaux en utilisant le principe de minimisation de l'enthalpie libre du système. La plupart des méthodes utilisent la méthode des « multiplicateurs de Lagrange » et résolvent les équations en employant une approximation du problème de Lagrange et en utilisant un algorithme de convergence pas à pas de type Newton-Raphson. Les équations mathématiques correspondantes restent cependant fortement non linéaires, de sorte que la résolution, notamment de systèmes multiphasiques, peut être très aléatoire. Une méthode alternative de recherche du minimum de l’énergie de Gibbs (MCGE) est développée dans ce travail, basée sur une technique de Monte-Carlo associée à une technique de Pivot de Gauss pour sélectionner des vecteurs composition satisfaisant la conservation des atomes. L'enthalpie libre est calculée pour chaque vecteur et le minimum est recherché de manière très simple. Cette méthode ne présente a priori pas de limite d’application (y compris pour las mélanges multiphasiques) et l’équation permettant de calculer l’énergie de Gibbs n’a pas à être discrétisée. Il est en outre montré que la précision des prédictions dépend assez significativement des valeurs thermodynamiques d’entrée telles l'énergie de formation des produits et les paramètres d'interaction moléculaire. La valeur absolue de ces paramètres n'a pas autant d’importance que la précision de leur évolution en fonction des paramètres du process (pression, température, ...). Ainsi, une méthode d'estimation cohérente est requise. Pour cela, la théorie de la « contribution de groupe » est utilisée (ceux de UNIFAC) et a été étendue en dehors du domaine d'interaction moléculaire traditionnel, par exemple pour prédire l'énergie de formation d’enthalpie libre, la chaleur spécifique... Enfin, l'influence du choix de la liste finale des produits est discutée. On montre que la prédictibilité dépend du choix initial de la liste de produits et notamment de son exhaustivité. Une technique basée sur le travail de Brignole et Gani est proposée pour engendrer automatiquement la liste des produits stable possibles. Ces techniques ont été programmées dans un nouveau code : CIRCE. Les travaux de Brignole et de Gani sont mis en œuvre sur la base de la composition atomique des réactifs pour prédire toutes les molécules « réalisables ». La théorie de la « contribution du groupe » est mise en œuvre pour le calcul des propriétés de paramètres thermodynamiques. La méthode MCGE est enfin utilisée pour trouver le minimum absolu de la fonction d'enthalpie libre. Le code semble plus polyvalent que les codes traditionnels (CEA, ASPEN, ...) mais il est plus coûteux en termes de temps de calcul. Il peut aussi être plus prédictif. Des exemples de génie des procédés illustrent l'étendue des applications potentielles en génie chimique<br>The objective of this work is to develop a new code to predict the final equilibrium of a complex chemical process with many species/reactions and several phases. Numerical methods were developed in the last decades to predict final chemical equilibria using the principle of minimizing the Gibbs free energy of the system. Most of them use the “Lagrange Multipliers” method and solve the resulting system of equations under the form of an approximate step by step convergence technique. Notwithstanding the potential complexity of the thermodynamic formulation of the “Gibbs problem,” the resulting mathematical formulation is always strongly non-linear so that solving multiphase systems may be very tricky and having the difficult to reach the absolute minimum. An alternative resolution method (MCGE) is developed in this work based on a Monte Carlo technique associated to a Gaussian elimination method to map the composition domain while satisfying the atom balance. The Gibbs energy is calculated at each point of the composition domain and the absolute minimum can be deduced very simply. In theory, the technique is not limited, the Gibbs function needs not be discretised and multiphase problem can be handled easily. It is further shown that the accuracy of the predictions depends to a significant extent on the “coherence” of the input thermodynamic data such the formation Gibbs energy of the species and molecular interaction parameters. The absolute value of such parameters does not matter as much as their evolution as function of the process parameters (pressure, temperature, …). So, a self-consistent estimation method is required. To achieve this, the group contribution theory is used (UNIFAC descriptors) and extended somewhat outside the traditional molecular interaction domain, for instance to predict the Gibbs energy of formation of the species, the specific heat capacity… Lastly the influence of the choice of the final list of products is discussed. It is shown that the relevancy of the prediction depends to a large extent on this initial choice. A first technique is proposed, based on Brignole and Gani‘s work, to avoid omitting species and another one to select, in this list, the products likely to appear given the process conditions. These techniques were programmed in a new code name CIRCE. Brignole and Gani-‘s method is implemented on the basis of the atomic composition of the reactants to predict all “realisable” molecules. The extended group contribution theory is implemented to calculate the thermodynamic parameters. The MCGE method is used to find the absolute minimum of the Gibbs energy function. The code seems to be more versatile than the traditional ones (CEA, ASPEN…) but more expensive in calculation costs. It can also be more predictive. Examples are shown illustrating the breadth of potential applications in chemical engineering
31
Chèze, Guillaume. "Des méthodes symboliques-numériques et exactes pour la factorisation absolue des polynômes en deux variables." Nice, 2004. http://www.theses.fr/2004NICE4092.
Full textAbstract:
Cette thèse porte sur les algorithmes de factorisation absolue. Elle débute par un état de l'art (avant notre travail) puis présente nos contributions. Celles-ci sont organisées en deux parties. La première partie correspond à l'étude symbolique-numérique. Nous donnons une méthode permettant d'obtenir une factorisation absolue exacte à partir d'une factorisation absolue approchée. Ensuite cette méthode est utilisée pour obtenir un algorithme de factorisation absolue. Cet algorithme reprend des idées développées par A. Galligo, D. Rupprecht, et, M. An Hoeij. Grâce à l'utilisation de l'algorithme LLL, notre algorithme permet d'obtenir la factorisation absolue de polynômes de grands degrés (supérieur à 100) jusqu'ici impossible. La deuxième partie présente deux algorithmes symboliques. Le premier est l'adaptation de la technique ``remonter-recombiner'' à l'algorithme de S. Gao. Nous obtenons ainsi un algorithme de factorisation absolue ayant une meilleure complexité que celui de S. Gao. Le deuxième est un algorithme, de type Las Vegas, qui nous permet de tester l'irréductibilité absolue d'un polynôme à coefficients entiers. L'approche proposée tire profit du calcul modulaire et de l'information contenu dans le polytope de Newton<br>This thesis is about absolute factorization algorithms. The first chapter is a survey on this topic, and then we describe our contributions. They are divided in two parts. The first part corresponds to the symbolic-numeric study. We give a method which allows us to get an exact absolute factorization from an approximate one. Next, this method is used to get an absolute polynomial factorization algorithm. This algorithm uses ideas developped by A. Galligo, D. Rupprecht, and M. Van Hoeij. Thanks to the LLL algorithm, it allows us to get the absolute factorization for polynomials with big degree (bigger than 100). It was impossible before. In the second part, we give two algorithms. The first one adapt a "lifting and recombination'' scheme to the Gao's algorithm. We get then a new algorithm with a better complexity than the Gao's one. The second one is a Las Vegas algorithm. It is an absolute irreducibility test for polynomials with integer coefficients. This algorithm use modular computations, and the shape of the Newton's polytope
32
Safeea, Mohammad. "Des robots manipulateurs collaboratifs sûrs." Thesis, Paris, HESAM, 2020. http://www.theses.fr/2020HESAE036.
Full textAbstract:
Les manipulateurs industriels collaboratifs ouvrent une nouvelle ère dans la fabrication flexible, où les robots et les humains sont capables de coexister et de travailler ensemble. Cependant, divers défis persistent pour parvenir à une collaboration complète entre les robots et les humains en milieu industriel. Dans cette thèse, deux défis principaux - la sécurité et la collaboration - sont abordés pour atteindre cet objectif. Concernant la sécurité, la thèse présente une méthode d'évitement des collisions en temps réel qui permet au robot d'ajuster les chemins générés hors ligne pour une tâche industrielle, tout en évitant les collisions avec les humains à proximité. En outre, la thèse a présenté une nouvelle méthode pour effectuer un mouvement d'évitement de collision réactif, en utilisant la méthode de Newton du second ordre qui offre divers avantages par rapport aux méthodes traditionnelles utilisées dans la littérature. Sur la collaboration, la thèse présente un mode de guidage manuel précis comme alternative au mode de guidage actuel pour effectuer des opérations de positionnement précis de l'effecteur terminal du robot d’une manière simple et intuitive. La thèse présente également de nouvelles contributions à la formulation mathématique de la dynamique des robots, y compris un algorithme récursif pour calculer la matrice de masse des robots sériels avec un coût minimal du second ordre et un algorithme récursif pour calculer efficacement les symboles de Christoffel. Tous les algorithmes présentés sont validés soit en simulation, soit dans un scénario réel<br>Collaborative industrial manipulators are ushering a new era in flexible manufacturing, where robots and humans are allowed to coexist and work side by side. However, various challenges still persist in achieving full human robot collaboration on the factory floor. In this thesis two main challenges - safety and collaboration - for achieving that goal are addressed. On safety, the thesis presents a real-time collision avoidance method which allows the robot to adjust the offline generated paths of the industrial task in real-time for avoiding collisions with humans nearby. In addition, the thesis presented a new method for performing the reactive collision avoidance motion using second order Newton method which offers various advantages over the traditional methods in the literature. On collaboration, the thesis presents the precision hand-guiding as an alternative to the teach-pendant for performing precise positioning operations of the robot’s end-effector in a simple and intuitive manner. The thesis also presents new contributions into the mathematical formulation of robot dynamics, including a recursive algorithm for calculating the mass matrix of serially linked robots with a minimal second order cost, and a recursive algorithm for calculating Christoffel symbols efficiently. All the presented algorithms are validated either in simulation or in a real-world scenario
33
Segalat, Philippe. "Méthodes de points intérieurs et de quasi-Newton." Limoges, 2002. http://www.theses.fr/2002LIMO0041.
Full textAbstract:
Cette thèse s' intéresse à des méthodes de ponts intérieurs et de quasi-Newton en optimisation non linéaire et à leurs mises en oeuvre. On présente le code NOPTIQ utilisant les formules de BFGS à mémoire limitée pour résoudre des problèmes de grande taille. L' originalité de cette approche est l' emploi de ces formules dans le cadre des méthodes de points intérieurs. L' espace mémoire et le coût en opérations du calcul d' une itération sont alors faibles. Le code NOPTIQ est robuste et a des performances comparables avec les codes de références 1-BFGS-B et LANCELOT. On présente aussi un algorithme non réalisable utilisant les méthodes précédentes pour résoudre un problème non linéaire avec contraintes d' inégalité et contraintes d' égalité linéaire. L' idée est de pénaliser le problème à l' aide de variables de décalage et d' une variante de la méthode big-M. La convergence q-superlinéaire des itérés internes et la convergence globale des itérés externes sont démontrées<br>This thesis is interested in interior point and quasi-Newton methods in nonlinear optimization and with their implementation. One presents the code NOPTIQ using the limited memory BFGS formulas to solve large scale problems. The originality of this approach is the use of these formulas within the framework of interior point methods. The storage requirement and the computing cost of one iteration are then low. One shows that NOPTIQ is robust and that its performance are comparable with the reference codes 1-BFGS-B and LANCELOT. One presents also an infeasible algorithm using the preceding methods to solve a nonlinear problem with inequality constraints and linear equality constraints. The idea to penalize the problem using shift variables and a variant of the big-M method of linear programming. The q-superlinear convergence of the inner iterates and the global convergence of outer iterates are shown
34
Heidt, David Charles. "A detailed derivation of a Newton-Raphson based harmonic power flow." Ohio University / OhioLINK, 1994. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1177098558.
Full text
35
SEGALAT, Philippe. "Méthodes de Points Intérieurs et de quasi-Newton." Phd thesis, Université de Limoges, 2002. http://tel.archives-ouvertes.fr/tel-00005478.
Full textAbstract:
Cette thèse s'intéresse à des méthodes de points intérieurs et de quasi-Newton en optimisation non linéaire et à leurs mises en oeuvre. On présente le code NOPTIQ utilisant les formules de BFGS à mémoire limitée pour résoudre des problèmes de grande taille. L'originalité de cette approche est l'emploi de ces formules dans le cadre des méthodes de points intérieurs. L'espace mémoire et le coût en opérations du calcul d'une itération sont alors faibles. Le code NOPTIQ est robuste et a des performances comparables avec les codes de références l-BFGS-B et LANCELOT. On présente aussi un algorithme non réalisable utilisant les méthodes précédentes pour résoudre un problème non linéaire avec contraintes d'inégalité et contraintes d'égalité linéaire. L'idée est de pénaliser le problème à l'aide de variables de décalage et d'une variante de la méthode big-M. La convergence q-superlinéaire des itérés internes et la convergence globale des itérés externes sont démontrées.
36
Böhm, Josef. "Linking Geometry, Algebra and Calculus with GeoGebra." Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-79488.
Full textAbstract:
GeoGebra is a free, open-source, and multi-platform software that combines dynamic geometry, algebra and calculus in one easy-to-use package. Students from middle-school to university can use it in classrooms and at home. In this workshop, we will introduce the
features of GeoGebra with a special focus on not very common applications of a dynamic geometry program. We will inform about plans for developing training and research networks
connected to GeoGebra. We can expect that at the time of the conference a spreadsheet will be integrated into GeoGebra which offers new ways teaching mathematics using the interplay between the
features of a spreadsheet and the objects of dynamic geometry.
37
Nejat, Amir. "A higher-order accurate unstructured finite volume Newton-Krylov algorithm for inviscid compressible flows." Thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/30969.
Full textAbstract:
A fast implicit (Newton-Krylov) finite volume algorithm is developed for higher-order unstructured
(cell-centered) steady-state computation of inviscid compressible flows (Euler
equations). The matrix-free General Minimal Residual (GMRES) algorithm is used for solving
the linear system arising from implicit discretization of the governing equations, avoiding
expensive and complicated explicit computation of the higher-order Jacobian matrix. An
Incomplete Lower-Upper factorization technique is employed as the preconditioning strategy
and a first-order Jacobian as a preconditioning matrix. The solution process is divided
into two phases: start-up and Newton iterations. In the start-up phase an approximate
solution of the fluid flow is computed which includes most of the physical characteristics
of the steady-state flow. A defect correction procedure is proposed for the start-up phase
consisting of multiple implicit pre-iterations. At the end of the start-up phase (when the
linearization of the flow field is accurate enough for steady-state solution) the solution is
switched to the Newton phase, taking an infinite time step and recovering a semi-quadratic
convergence rate (for most of the cases). A proper limiter implementation for higher-order
discretization is discussed and a new formula for limiting the higher-order terms of the
reconstruction polynomial is introduced. The issue of mesh refinement in accuracy measurement
for unstructured meshes is revisited. A straightforward methodology is applied for
accuracy assessment of the higher-order unstructured approach based on total pressure loss,
drag measurement, and direct solution error calculation. The accuracy, fast convergence
and robustness of the proposed higher-order unstructured Newton-Krylov solver for different
speed regimes are demonstrated via several test cases for the 2nd, 3rd and 4th-order
discretization. Solutions of different orders of accuracy are compared in detail through several
investigations. The possibility of reducing the computational cost required for a given
level of accuracy using high-order discretization is demonstrated.<br>Applied Science, Faculty of<br>Mechanical Engineering, Department of<br>Graduate
38
Howe, Melendres Amoro. "A quasi-Newton algorithm for continuous minimax with applications to risk management in finance." Thesis, Imperial College London, 1994. http://hdl.handle.net/10044/1/11772.
Full text
39
Mendez, Cruz Gilberto Amado. "Algoritmos paralelos iterativos do tipo quasi-Newton para a minimização de funções multivariadas." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 1997. http://hdl.handle.net/10183/126491.
Full textAbstract:
O objetivo deste trabalho é apresentar e descrever a teoria e implementação paralela. em PVM, de dois algoritmos iterativos do tipo quasi-Newton - Newton-GNIRES e Broyden- para a solução de equações não lineares F= O, onde a função F: Rn -t Rn é de classe C1 e seu Jacobiano J( x) é esparso. Uma ilustração e comparação destes métodos com suas versões sequenciais é obtida ao aplicá-los a dois probJemas específicos.<br>The objective of this work is to introduce anel describe the theory anel implementation on PVM, of two quase-Newton iterative algorithms - NewtonGA1RES e Broyden - for the resolution of nonlinear equations F = O, where a function F : Rn --+ Rn is of class C1 and its Jacobian J(x) is sparse. An ilustration and comparison of these methods with their serial versions is obtained as they apply to two especific problems.
40
Buchanan, Aeron Morgan. "Tracking non-rigid objects in video." Thesis, University of Oxford, 2008. http://ora.ox.ac.uk/objects/uuid:82efb277-abc9-4725-9506-5d114a83bd96.
Full textAbstract:
Video is a sequence of 2D images of the 3D world generated by a camera. As the camera moves relative to the real scene and elements of that scene themselves move, correlated frame-to-frame changes in the video images are induced. Humans easily identify such changes as scene motion and can readily assess attempts to quantify it. For a machine, the identification of the 2D frame-to-frame motion is difficult. This problem is addressed by the computer vision process of tracking. Tracking underpins the solution to the problem of augmenting general video sequences with artificial imagery, a staple task in the visual effects industry. The problem is difficult because tracking in general video sequences is complicated by the presence of non-rigid motion, repeated texture and arbitrary occlusions. Existing methods provide solutions that rely on imposing limitations on the scenes that can be processed or that rely on human artistry and hard work. I introduce new paradigms, frameworks and algorithms for overcoming the challenges of processing general video and thus provide solutions that fill the gap between the `automated' and `manual' approaches. The work is easily sectioned into three parts, which can be considered separately or taken together for dealing with video without limitations. The initial focus is on directly addressing practical issues of human interaction in the tracking process: a new solution is developed by explicitly incorporating the user into an interactive algorithm. It is a novel tracking system based on fast full-frame patch searching and high-speed optimal track determination. This approach makes only minimal assumptions about motion and appearance, making it suitable for the widest variety of input video. I detail an implementation of the new system using k-d trees and dynamic programming. The second distinct contribution is an important extension to tracking algorithms in general. It can be noted that existing tracking algorithms occupy a spectrum in their use of global motion information. Local methods are easily confused by occlusions, repeated texture and image noise. Global motion models offer strong predictions to see through these difficulties and have been used in restricted circumstances, but are defeated by scenes containing independently moving objects or modest levels of non-rigid motion. I present a well principled way of combining local and global models to improve tracking, especially in these highly problematic cases. By viewing rank-constrained tracking as a probabilistic model of 2D tracks instead of 3D motion, I show how one can obtain a robust motion prior that can be easily incorporated in any existing tracking algorithm. The development of the global motion prior is based on rank-constrained factorization of measurement matrices. A common difficulty comes from the frequent occurrence of occlusions in video, which means that the relevant matrices are often not complete due to missing data. This defeats standard factorization algorithms. To fully explain and understand the algorithmic complexities of factorization in this practical context, I present a common notation for the direct comparison of existing algorithms and propose a new family of hybrid approaches that combine the superb initial performance of alternation methods with the convergence power of the Newton algorithm. Together, these investigations provide a wide-ranging, yet coherent exploration of tracking non-rigid objects in video.
41
Ruggiero, Márcia Aparecida Gomes 1956. "Metodos quase - Newton para resolução de sistemas não lineares esparsos e de grande porte." [s.n.], 1990. http://repositorio.unicamp.br/jspui/handle/REPOSIP/260907.
Full textAbstract:
Orientador: Jose Mario Martinez<br>Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica<br>Made available in DSpace on 2018-07-13T21:54:34Z (GMT). No. of bitstreams: 1
Ruggiero_MarciaAparecidaGomes_D.pdf: 5439513 bytes, checksum: 7a885b7a3c93d3d8741a336bc054a8fc (MD5)
Previous issue date: 1990<br>Resumo: O objetivo deste trabalho é o estudo e a análise do desempenho computacional do método de Newton e oito métodos tipo quase-Newton quando aplicados a resolução de sistemas não lineares esparsos, e de grande porte. Por razões de estabilidade numérica optamos pela fatoração LU com estratégia de pivoteamento parcial para resolver os sistemas lineares; através de uma manipulação simbólica sobre a estrutura original da matriz, Jacobiana, obtém-se uma estrutura. estática de dados sobre a qual são realizadas as operações algébricas necessárias para a fatoração LU. Incorporamos aos algoritmos locais uma estratégia de globalização tolerante com o objetivo de prevenir divergência quando a aproximação inicial é ruim. Introduzimos novos métodos e novas implementações de métodos já conhecidos para problemas de grande porte. Desenvolvemos o pacote Rouxinol que possibilitou a comparação numérica entre os vários métodos implementados<br>Abstract: Not informed.<br>Doutorado<br>Doutor em Engenharia Elétrica
42
Morad, Farhad. "Non-linear Curve Fitting." Thesis, Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-43600.
Full textAbstract:
The work done in this thesis is to examine various methods for curve fitting. Linear least squares and non-linear least squares will be described and compared, and the Newton method, Gauss--Newton method and Levenberg--Marquardt method will be applied to example problems.<br>Syftet med denna uppsats är att beskriva och använda olika metoder för kurvanpassning, det vill säga att passa matematiska funktioner till data. De metoder som undersöks är Newtons metod, Gauss--Newton metoden och Levenberg--Marquardt metoden. Även skillnaden mellan linjär minsta kvadrat anpassning och olinjär minsta kvadrat anpassning. Till sist tillämpas Newton, Gauss Newton och Levenberg--Marquardt metoderna på olika exempel.
43
Guterres, Marcelo Xavier. "Avaliação dos algoritmos de Picard-Krylov e Newton-Krylov na solução da equação de Richards." Universidade do Estado do Rio de Janeiro, 2013. http://www.bdtd.uerj.br/tde_busca/arquivo.php?codArquivo=6749.
Full textAbstract:
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>A engenharia geotécnica é uma das grandes áreas da engenharia civil que estuda a
interação entre as construções realizadas pelo homem ou de fenômenos naturais com o ambiente
geológico, que na grande maioria das vezes trata-se de solos parcialmente saturados.
Neste sentido, o desempenho de obras como estabilização, contenção de barragens, muros
de contenção, fundações e estradas estão condicionados a uma correta predição do fluxo de
água no interior dos solos. Porém, como a área das regiões a serem estudas com relação à
predição do fluxo de água são comumente da ordem de quilômetros quadrados, as soluções
dos modelos matemáticos exigem malhas computacionais de grandes proporções, ocasionando
sérias limitações associadas aos requisitos de memória computacional e tempo de
processamento. A fim de contornar estas limitações, métodos numéricos eficientes devem
ser empregados na solução do problema em análise. Portanto, métodos iterativos para
solução de sistemas não lineares e lineares esparsos de grande porte devem ser utilizados
neste tipo de aplicação. Em suma, visto a relevância do tema, esta pesquisa aproximou
uma solução para a equação diferencial parcial de Richards pelo método dos volumes finitos
em duas dimensões, empregando o método de Picard e Newton com maior eficiência
computacional. Para tanto, foram utilizadas técnicas iterativas de resolução de sistemas
lineares baseados no espaço de Krylov com matrizes pré-condicionadoras com a biblioteca
numérica Portable, Extensible Toolkit for Scientific Computation (PETSc). Os resultados
indicam que quando se resolve a equação de Richards considerando-se o método de
PICARD-KRYLOV, não importando o modelo de avaliação do solo, a melhor combinação
para resolução dos sistemas lineares é o método dos gradientes biconjugados estabilizado
mais o pré-condicionador SOR. Por outro lado, quando se utiliza as equações de van
Genuchten deve ser optar pela combinação do método dos gradientes conjugados em conjunto
com pré-condicionador SOR. Quando se adota o método de NEWTON-KRYLOV,
o método gradientes biconjugados estabilizado é o mais eficiente na resolução do sistema
linear do passo de Newton, com relação ao pré-condicionador deve-se dar preferência ao
bloco Jacobi. Por fim, há evidências que apontam que o método PICARD-KRYLOV
pode ser mais vantajoso que o método de NEWTON-KRYLOV, quando empregados na
resolução da equação diferencial parcial de Richards.<br>Geotechnical Engineering is the area of Civil Engineering that studies the interaction
between constructions carried out by man or natural phenomena with geological
environment, which most of times is partially saturated soil. In this sense, work developing
as stabilization, dam containing, retaining walls, foundations and highways are conditioned
to a right prediction of water flow into the soil. However, considering the water flow,
the studied region areas are commonly on the order of square kilometers, mathematical
models solutions require computational meshes of large proportions, causing serious limitations
linked to computational memory requirements and processing time. In order to
overcome these limitations, efficient numerical methods must be used in the solution of
the considered problem. Hence iterative methods for solving nonlinear and large sparse
linear systems must be used in this type of application. In short, this study approached
a solution to the Richard partial differential equation by the two dimensions finite volume
method, bringing Picard and Newton method with greater efficiency. Linear system
resolution iterative techniques based on Krylov space with pre-conditioners matrix were
used. Portable Extensible Toolkit for Scientific Computation (PETSc) numerical library
was a tool used during the task. The results indicate when a Richards equation is solved
considering thr PICARD-KRYLOV method, no matter the soil evaluation model, the
best combination for solving linear systems is the stabilized double gradient method and
the SOR preconditioning. On the other hand, when the van Genuchten equations are
used the gradients methods with the SOR preconditioning must be chosen. Adopting
the NEWTON-KRYLOV method, the stabilized double gradient method is more efficient
in soling Newton linear system, in relation to the preconditioning it must be giving
preference to the Jacob block. Finally, there are strong indications that the PICARDKRYLOV
method can be more effective than the NEWTON-KRYLOV one, when used
for solving Richards partial differential equation.
44
Nouet, Christophe. "Réduction de l'ordre des systèmes continus, linéaires, via un processus d'orthogonalisation et un algorithme de gauss newton." Brest, 1994. http://www.theses.fr/1994BRES2040.
Full textAbstract:
Nous avons développé une méthode d'approximation des signaux et systèmes à temps continu, optimale au sens des moindres carres. À partir de la seule connaissance de la transformée de Laplace rationnelle ou irrationnelle de la réponse, par exemple impulsionnelle ou indicielle d'un système initial, nous déterminons le meilleur modèle approche dont la réponse, soit la plus proche possible de celle du modèle original. Nous exprimons toujours le modèle approche sous forme d'une transformée de Laplace rationnelle. La qualité de l'approximation est mesurée à l'aide du critère d'erreur quadratique. La méthode élaborée, comme toute technique optimale, nécessite la mise en place d'un processus itératif d'optimisation. La première phase utilisant des équations linéaires, calcule le meilleur numérateur pour un dénominateur donné. La seconde permettant d'ajuster progressivement le dénominateur fait intervenir des équations non linéaires que nous linéarisons par un processus de type gauss-newton. Grâce a une technique d'orthogonalisation des fonctions d'approximation basée sur l'utilisation des tableaux de Routh, nous évitons la résolution des systèmes linéaires et par conséquent le calcul et l'inversion de matrices souvent mal conditionnées. La meilleure solution minimisant le critère d'erreur quadratique est obtenue par une expression explicite, dans laquelle ne figurent plus que des matrices d'orthogonalisation dont nous avons proposé une détermination originale. Pour cette nouvelle approche de l'approximation, la gestion spécifique des pôles réels ou complexes, simples ou multiples, est évitée. Tous les paramètres étant réels, les calculs s'effectuent en arithmétique réelle. De plus, dans le cas de fonctions de transfert rationnelles, l'optimisation est réalisée sans le calcul des pôles. La possibilité d'imposer des contraintes linéaires de type Egalite est une propriété intéressante de la méthode. Nous proposons de plus des techniques performantes pour le calcul des divers produits scalaires nécessaires a la mise en œuvre de notre méthode de réduction. La technique développée est applicable à l'étude de systèmes et à la simulation. Son application aux systèmes mimo ainsi que l'utilisation de contraintes de type inégalité pourraient être envisagées
45
Stewart, Alistair Mark. "Efficient algorithms for infinite-state recursive stochastic models and Newton's method." Thesis, University of Edinburgh, 2015. http://hdl.handle.net/1842/10001.
Full textAbstract:
Some well-studied infinite-state stochastic models give rise to systems of nonlinear equations. These systems of equations have solutions that are probabilities, generally probabilities of termination in the model. We are interested in finding efficient, preferably polynomial time, algorithms for calculating probabilities associated with these models. The chief tool we use to solve systems of polynomial equations will be Newton’s method as suggested by [EY09]. The main contribution of this thesis is to the analysis of this and related algorithms. We give polynomial-time algorithms for calculating probabilities for broad classes of models for which none were known before. Stochastic models that give rise to such systems of equations include such classic and heavily-studied models as Multi-type Branching Processes, Stochastic Context- Free Grammars(SCFGs) and Quasi Birth-Death Processes. We also consider models that give rise to infinite-state Markov Decision Processes (MDPs) by giving algorithms for approximating optimal probabilities and finding policies that give probabilities close to the optimal probability, in several classes of infinite-state MDPs. Our algorithms for analysing infinite-state MDPs rely on a non-trivial generalization of Newton’s method that works for the max/min polynomial systems that arise as Bellman optimality equations in these models. For SCFGs, which are used in statistical natural language processing, in addition to approximating termination probabilities, we analyse algorithms for approximating the probability that a grammar produces a given string, or produces a string in a given regular language. In most cases, we show that we can calculate an approximation to the relevant probability in time polynomial in the size of the model and the number of bits of desired precision. We also consider more general systems of monotone polynomial equations. For such systems we cannot give a polynomial-time algorithm, which pre-existing hardness results render unlikely, but we can still give an algorithm with a complexity upper bound which is exponential only in some parameters that are likely to be bounded for the monotone polynomial equations that arise for many interesting stochastic models.
46
Pettersson, Stefan. "Implementation and evaluation of a polynomial-based division algorithm." Thesis, Linköping University, Department of Electrical Engineering, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-1900.
Full textAbstract:
<p>In comparison to other basic arithmetic operations, such as addition, subtraction and multiplication,division is far more complex and expensive. Many division algorithms, except for lookup tables, rely on recursion with usually complex operations in the loop. Even if the cost in terms of area and computational complexity sometimes can be made low, the latency is usually high anyway, due to the number of iterations required. Therefore, in order to find a faster method and a method that provides better precision, a non-recursive polynomial-based algorithm was developed by the Department of Electrical Engineering at Linköping University. </p><p>After having performed high-level modelling in Matlab, promising results were achieved for up to 32 bits of accuracy. However, since the cost model did not take in account other factors that are important when implementing in hardware, the question remained whether the division algorithm was also competitive in practice or not. Therefore, in order to investigate that, this thesis work was initiated. </p><p>This report describes the hardware implementation, the optimization and the evaluation of this division algorithm, regarding latency and hardware cost for numbers with different precisions. In addition to this algorithm, the common Newton-Raphson algorithm has also been implemented, to serve as a reference.</p>
47
Dolák, Martin. "Nelineární regrese v programu R." Master's thesis, Vysoká škola ekonomická v Praze, 2015. http://www.nusl.cz/ntk/nusl-193088.
Full textAbstract:
This thesis deals with solutions of nonlinear regression problems using R programming language. The introductory theoretical part is devoted to familiarization with the principles of solving nonlinear regression models and of their applications in the program R. In both, theoretical and practical part, the most famous and used differentiator algorithms are presented, particularly the Gauss-Newton's and of the steepest descent method, for estimating the parameters of nonlinear regression. Further, in the practical part, there are some demo solutions of particular tasks using nonlinear regression methods. Overall, a large number of graphs processed by the author is used in this thesis for better comprehension.
48
Fijany, Amir. "Algorithmes et architectures parallèles en robotique." Paris 11, 1988. http://www.theses.fr/1988PA112258.
Full textAbstract:
La simulation et le contrôle des mouvements d'un robot manipulateur nécessitent la résolution des problèmes cinématiques et dynamiques. Une capacité de calcul insuffisante a toujours constitué l'obstacle majeur de la simulation et du contrôle en temps réel des mouvements d'un robot manipulateur. Il est unanimement reconnu que l'utilisation d'architectures informatiques parallèles est un facteur clé pour surmonter cet obstacle. L'objectif de ce travail est de déduire les caractéristiques essentielles puis de mettre en oeuvre une architecture hautement parallèle qui procure les améliorations significatives et décisives pour calculer les modèles dynamiques et cinématiques. Pour atteindre cet objectif, nous avons tout d’abord effectué une étude algorithmique puis développé des algorithmes parallèles appropriés et efficaces. Les caractéristiques des architectures informatiques pour la mise en oeuvre de ces algorithmes sont ensuite déterminées en étudiant les propriétés communes des algorithmes. Cette approche a permis d'étudier et de mettre en oeuvre une architecture (MlMD-SlMD) hautement parallèle. Cette architecture a permis d'obtenir une réduction significative du temps de calcul des différents problèmes. Pour un robot à six degrés de liberté, le temps de calcul du modèle dynamique inverse est de 187 micro second tandis que le modèle cinématique et son inverse sont calculés en 75 micro secondes.
49
Guo, Chaomei. "Amélioration des propriétés de convergence des algorithmes de simulation des circuits non linéaires microondes." Limoges, 1995. http://www.theses.fr/1995LIMO0024.
Full textAbstract:
Ce travail propose une etude des methodes d'analyse numerique dans le domaine des circuits non lineaires microondes, basee sur l'amelioration des proprietes de convergence des algorithmes. La principale methode classique de la resolution des equations d'equilibrage harmonique est presentee. Elle est suivie par les descriptions des methodes abs, quasi-newton et de relaxation. Les methodes de type abs sont des methodes iteratives de resolution dont les proprietes de convergence peuvent apporter une amelioration du temps de calcul global. A partir de l'application d'equilibrage harmonique, il est montre que la convergence pres de la solution n'est pas assuree. Les methodes quasi-newton evitent de calculer des derivees partielles pour construire le jacobien en le remplacant par une approximation. Elles laissent envisager une reduction du cout de calcul. Cependant, le gain obtenu par rapport a la methode de newton-raphson reste faible, de l'ordre de 2. Les methodes de relaxation, quant a elles, utilisent les iterations non lineaires lineaires qui peuvent remplacer la resolution exacte de l'equation de recurrence par une resolution approchee. Il est possible de realiser une diminution du cout de calcul a condition que le jacobien soit diagonalement dominant, ce qui n'est pas toujours le cas
50
Maldonado, Angela Mabel. "Sobre o algoritmo de Newman -O'Brien para geração de p-grupos." [s.n.], 1994. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306214.
Full textAbstract:
Orientador: Norai Romeu Rocco<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica<br>Made available in DSpace on 2018-07-19T14:11:03Z (GMT). No. of bitstreams: 1
Maldonado_AngelaMabel_M.pdf: 3014977 bytes, checksum: 729fd219615f4c01f74c43e795ecb40c (MD5)
Previous issue date: 1994<br>Resumo: O propósito deste trabalho é estudar os aspectos teóricos e certos detalhes da implementação do Algoritmo para geração de p-grupos desenvolvido por M.F. Newman e E.A. O'Brien. A implementação deste algoritmo permite o cálculo de certas extensões particulares de p-grupos; possibilitando assim, a determinação dos p-grupos finitos. Fazemos isto no capítulo 3, onde também incluímos um exemplo de algumas iterações deste procedimento, calculando manualmente 0s 2-grupos 2-gerados de ordem menor o igual a 24<br>Abstract: Not informed<br>Mestrado<br>Mestre em Matemática