In this dissertation, we consider modified inexact Newton methods applied to second order nonlinear problems. In the implementation of Newton's method applied to problems with a large number of degrees of freedom, it is often necessary to solve the linear Jacobian system iteratively. Although a general theory for the convergence of modified inexact Newton's methods has been developed, its application to nonlinear problems from nonlinear PDE's is far from complete. The case where the nonlinear operator is a zeroth order perturbation of a fixed linear operator was considered in the paper written by Brown et al.. The goal of this dissertation is to show that one can develop modified inexact Newton's methods which converge at a rate independent of the number of unknowns for problems with higher order nonlinearities. To do this, we are required to first, set up the problem on a scale of Hilbert spaces, and second, to devise a special iterative technique which converges in a higher order Sobolev norm, i.e., H1+alpha(omega) \ H1 0(omega) with 0 < alpha < 1/2. We show that the linear system solved in Newton's method can be replaced with one iterative step provided that the initial iterate is close enough. The closeness criteria can be taken independent of the mesh size. In addition, we have the same convergence rates of the method in the norm of H1 0(omega) using the discrete Sobolev inequalities.

Newton's method is at the core of many algorithms used for solving nonlinear equations. A globalized Newton method is an implementation of Newton's method augmented with ``globalization procedures' intended to enhance the likelihood of convergence to a solution from an arbitrary initial guess. A Newton-GMRES method is an implementation of Newton's method in which the iterative linear algebra method GMRES is used to solve approximately the linear system that characterizes the Newton step. A globalized Newton-GMRES method combines both globalization procedures and the GMRES scheme to develop robust and efficient algorithms for solving nonlinear equations. The aim of this project is to describe the development of some globalized Newton-GMRES methods and to compare their performances on a few benchmark fluid flow problems.

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

The development, analysis, and implementation of efficient methods to solve algebraic systems of equations are main research directions in the field of numerical simulation and are the focus of this thesis. Due to their lesser demands for computer resources, iterative solution methods are the choice to make, when very large scale simulations have to be performed. To improve their efficiency, iterative methods are combined with proper techniques to accelerate convergence. A general technique to do this is to use a so-called preconditioner. Constructing and analysing various preconditioning methods has been an active field of research already for decades. Special attention is devoted to the class of the so-called optimal order preconditioners, that possess both optimal convergence rate and optimal computational complexity. The preconditioning techniques, proposed and studied in this thesis, utilise the block structure of the underlying matrices, and lead to methods that are of optimal order. In the first part of the thesis, we construct an Algebraic MultiLevel Iteration (AMLI) method for systems arising from discretizations of parabolic problems, using Crouzeix-Raviart finite elements. The developed AMLI method is based on an approximated block factorization of the original system matrix, where the partitioning is associated with a sequence of nested discretization meshes. In the second part of the thesis we develop solution methods for the numerical simulation of multiphase flow problems, modelled by the Cahn-Hilliard (C-H) equation. We consider the discrete C-H problem, obtained via finite element discretization in space and implicit schemes in time. We propose techniques to precondition the Jacobian of the discrete nonlinear system, based on its natural two-by-two block structure. The preconditioners are used in the framework of inexact Newton methods. We develop two nonlinear solution algorithms for the Cahn-Hilliard problem. Both lead to efficient optimal order methods. One of the main advantages of the proposed methods is that they are implemented using available software toolboxes for both sequential and distributed execution. The theoretical analysis of the solution methods presented in this thesis is combined with numerical studies that confirm their efficiency.

The objective of this PhD research program is to develop an accurate and efficient heterogeneous three-dimensional computational model for simulating the drying of wood at temperatures below the boiling point of water. The complex macroscopic drying equations comprise a coupled and highly nonlinear system of physical laws for liquid and energy conservation. Due to the heterogeneous nature of wood, the physical model parameters strongly depend upon the local pore structure, wood density variation within growth rings and variations in primary and secondary system variables. In order to provide a realistic representation of this behaviour, a set of previously determined parameters derived using sophisticated image analysis methods and homogenisation techniques is embedded within the model. From the literature it is noted that current three-dimensional computational models for wood drying do not take into consideration the heterogeneities of the medium. A significant advance made by the research conducted in this thesis is the development of a three - dimensional computational model that takes into account the heterogeneous board material properties which vary within the transverse plane with respect to the pith position that defines the radial and tangential directions. The development of an accurate and efficient computational model requires the consideration of a number of significant numerical issues, including the virtual board description, an effective mesh design based on triangular prismatic elements, the control volume finite element discretisation process for the cou- pled conservation laws, the derivation of an accurate dux expression based on gradient approximations together with flux limiting, and finally the solution of a large, coupled, nonlinear system using an inexact Newton method with a suitably preconditioned iterative linear solver for computing the Newton correction. This thesis addresses all of these issues for the case of low temperature drying of softwood. Specific case studies are presented that highlight the efficiency of the proposed numerical techniques and illustrate the complex heat and mass transport processes that evolve throughout drying.

Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2015-10-29T19:04:41Z No. of bitstreams: 2 Tese - Tiberio Bittencourt de Oliveira Martins.pdf: 1155588 bytes, checksum: add1eac74c4397efc29678341b834448 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-11-03T14:25:04Z (GMT) No. of bitstreams: 2 Tese - Tiberio Bittencourt de Oliveira Martins.pdf: 1155588 bytes, checksum: add1eac74c4397efc29678341b834448 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-11-03T14:25:04Z (GMT). No. of bitstreams: 2 Tese - Tiberio Bittencourt de Oliveira Martins.pdf: 1155588 bytes, checksum: add1eac74c4397efc29678341b834448 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-06-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Apresentamos, nesta tese, uma an álise da convergência do m étodo de Newton inexato com tolerância de erro residual relativa e uma an alise semi-local de m etodos de Newton robustos exato e inexato, objetivando encontrar uma singularidade de um campo de vetores diferenci avel de nido em uma variedade Riemanniana completa, baseados no princ pio majorante a m invariante. Sob hip oteses locais e considerando uma fun ção majorante geral, a Q-convergância linear do m etodo de Newton inexato com uma tolerância de erro residual relativa xa e provada. Na ausência dos erros, a an alise apresentada reobtem o teorema local cl assico sobre o m etodo de Newton no contexto Riemanniano. Na an alise semi-local dos m etodos exato e inexato de Newton apresentada, a cl assica condi ção de Lipschitz tamb em e relaxada usando uma fun ção majorante geral, permitindo estabelecer existência e unicidade local da solu ção, uni cando previamente resultados pertencentes ao m etodo de Newton. A an alise enfatiza a robustez, a saber, e dada uma bola prescrita em torno do ponto inicial que satifaz as hip oteses de Kantorovich, garantindo a convergência do m etodo para qualquer ponto inicial nesta bola. Al em disso, limitantes que dependem da função majorante para a taxa de convergência Q-quadr atica do m étodo exato e para a taxa de convergência Q-linear para o m etodo inexato são obtidos. / A local convergence analysis with relative residual error tolerance of inexact Newton method and a semi-local analysis of a robust exact and inexact Newton methods are presented in this thesis, objecting to nd a singularity of a di erentiable vector eld de ned on a complete Riemannian manifold, based on a ne invariant majorant principle. Considering local assumptions and a general majorant function, the Q-linear convergence of inexact Newton method with a xed relative residual error tolerance is proved. In the absence of errors, the analysis presented retrieves the classical local theorem on Newton's method in Riemannian context. In the semi-local analysis of exact and inexact Newton methods presented, the classical Lipschitz condition is also relaxed by using a general majorant function, allowing to establish the existence and also local uniqueness of the solution, unifying previous results pertaining Newton's method. The analysis emphasizes robustness, being more speci c, is given a prescribed ball around the point satisfying Kantorovich's assumptions, ensuring convergence of the method for any starting point in this ball. Furthermore, the bounds depending on the majorant function for Q-quadratic convergence rate of the exact method and Q-linear convergence rate of the inexact method are obtained.

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2017-03-22T20:23:25Z No. of bitstreams: 2 Tese - Gilson do Nascimento Silva - 2017.pdf: 2015008 bytes, checksum: e0148664ca46221978f71731aeabfa36 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-03-23T11:30:21Z (GMT) No. of bitstreams: 2 Tese - Gilson do Nascimento Silva - 2017.pdf: 2015008 bytes, checksum: e0148664ca46221978f71731aeabfa36 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-23T11:30:21Z (GMT). No. of bitstreams: 2 Tese - Gilson do Nascimento Silva - 2017.pdf: 2015008 bytes, checksum: e0148664ca46221978f71731aeabfa36 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-03-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / We consider Newton’s method for solving a generalized equation of the form f(x) + F(x) 3 0, where f : Ω → Y is continuously differentiable, X and Y are Banach spaces, Ω ⊆ X is open and F : X ⇒ Y has nonempty closed graph. Assuming strong regularity of the equation and that the starting point satisfies Kantorovich’s conditions, we show that the method is quadratically convergent to a solution, which is unique in a suitable neighborhood of the starting point. In addition, a local convergence analysis of this method is presented. Moreover, using convex optimization techniques introduced by S. M. Robinson (Numer. Math., Vol. 19, 1972, pp. 341-347), we prove a robust convergence theorem for inexact Newton’s method for solving nonlinear inclusion problems in Banach space, i.e., when F(x) = −C and C is a closed convex set. Our analysis, which is based on Kantorovich’s majorant technique, enables us to obtain convergence results under Lipschitz, Smale’s and Nesterov-Nemirovskii’s self-concordant conditions. / N´os consideraremos o m´etodo de Newton para resolver uma equa¸c˜ao generalizada da forma f(x) + F(x) 3 0, onde f : Ω → Y ´e continuamente diferenci´avel, X e Y s˜ao espa¸cos de Banach, Ω ⊆ X ´e aberto e F : X ⇒ Y tem gr´afico fechado n˜ao-vazio. Supondo regularidade forte da equa¸c˜ao e que o ponto inicial satisfaz as hip´oteses de Kantorovich, mostraremos que o m´etodo ´e quadraticamente convergente para uma solu¸c˜ao, a qual ´e ´unica em uma vizinhan¸ca do ponto inicial. Uma an´alise de convergˆencia local deste m´etodo tamb´em ´e apresentada. Al´em disso, usando t´ecnicas de otimiza¸c˜ao convexa introduzida por S. M. Robinson (Numer. Math., Vol. 19, 1972, pp. 341-347), provaremos um robusto teorema de convergˆencia para o m´etodo de Newton inexato para resolver problemas de inclus˜ao n˜ao–linear em espa¸cos de Banach, i.e., quando F(x) = −C e C ´e um conjunto convexo fechado. Nossa an´alise, a qual ´e baseada na t´ecnica majorante de Kantorovich, nos permite obter resultados de convergˆencia sob as condi¸c˜oes Lipschitz, Smale e Nesterov-Nemirovskii auto-concordante.

Σε αυτή την εργασία, ασχολούμαστε με το πρόβλημα της επίλυσης συστημάτων μη γραμμικών αλγεβρικών ή/και υπερβατικών εξισώσεων και συγκεκριμένα αναφερόμαστε σε βελτιωμένες αλγοριθμικές τεχνικές επίλυσης τέτοιων συστημάτων. Μη γραμμικά συστήματα υπάρχουν σε πολλούς τομείς της επιστήμης, όπως στη Μηχανική, την Ιατρική, τη Χημεία, τη Ρομποτική, τα Οικονομικά, κ.τ.λ. Υπάρχουν πολλές μέθοδοι για την επίλυση συστημάτων μη γραμμικών εξισώσεων. Ανάμεσά τους η μέθοδος Newton είναι η πιο γνωστή μέθοδος, λόγω της τετραγωνικής της σύγκλισης όταν υπάρχει μια καλή αρχική εκτίμηση και ο Ιακωβιανός πίνακας είναι nonsingular. Η μέθοδος Newton έχει μερικά μειονεκτήματα, όπως τοπική σύγκλιση, αναγκαιότητα υπολογισμού του Ιακωβιανού πίνακα και ακριβής επίλυση του γραμμικού συστήματος σε κάθε επανάληψη. Σε αυτή τη μεταπτυχιακή διπλωματική εργασία αναλύουμε τη μέθοδο Newton και κατηγοριοποιούμε μεθόδους που συμβάλλουν στην αντιμετώπιση των μειονεκτημάτων της μεθόδου Newton, π.χ. Quasi-Newton και Inexact-Newton μεθόδους. Μερικές πιο πρόσφατες μέθοδοι που περιγράφονται σε αυτή την εργασία είναι η μέθοδος MRV και δύο νέες μέθοδοι Newton χωρίς άμεσες συναρτησιακές τιμές, κατάλληλες για προβλήματα με μη ακριβείς συναρτησιακές τιμές ή με μεγάλο υπολογιστικό κόστος. Στο τέλος αυτής της μεταπτυχιακής εργασίας, παρουσιάζουμε τις βασικές αρχές της Ανάλυσης Διαστημάτων και τη Διαστηματική μέθοδο Newton. / In this contribution, we deal with the problem of solving systems of nonlinear algebraic or/and transcendental equations and in particular we are referred to improved algorithmic techniques of such kind of systems. Nonlinear systems arise in many domains of science, such as Mechanics, Medicine, Chemistry, Robotics, Economics, etc. There are several methods for solving systems of nonlinear equations. Among them Newton's method is the most famous, because of its quadratic convergence when a good initial guess exists and the Jacobian matrix is nonsingular. Newton's method has some disadvantages, such as local convergence, necessity of computation of Jacobian matrix and the exact solution of linear system at each iteration. In this master thesis we analyze Newton's method and we categorize methods that contribute to the treatment of drawbacks of Newton's method, e.g. Quasi-Newton and Inexact-Newton methods. Some more recent methods which are described in this thesis are the MRV method and two new Newton's methods without direct function evaluations, ideal for problems with inaccurate function values or high computational cost. At the end of this master thesis, we present the basic principles of Interval Analysis and Interval Newton's method.