In this thesis, we consider the inverse Toeplitz eigenvalue problem which recover a real symmetric Toeplitz with desired eigenvalues. First some lower dimensional cases are solved by algebraic methods. This gives more insight on the inverse problem. Next, we explore the geometric meaning of real symmetric Toeplitz matrices. For high dimensional cases, numerical are unavoidable. From our numerical experiments, Newton-like methods are very effective for this problem.

Root-finding algorithms have been studied for ages for their various applications. Newton's Method is just one of these root-finding algorithms. This report discusses Newton's Method and aims to describe the procedures behind the method and to determine its capabilities in finding the zeros for various functions. The possible outcomes when using this method are also explained; whether the Newton function will converge to a root, diverge from the root, or enter a cycle. Modifications of the method and its applications are also described, showing the flexibility of the method for different situations. / text

No description available.

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.

Optimal control of general dynamic systems under realistic constraints on input signals and state variables is an important problem area in control theory. Many practical control problems can be formulated as optimization tasks, and this leads toa significant demand for efficient numerical solution algorithms. Several such algorithms have been developed, and they are typically derived from a dynamic programming view point. In this thesis a differentapproach is taken. The discretetime dynamic optimization problem is formulated as a static one, with the inputs as free variables. Newton's approach to solving such a problem with constraints, also known as Wilson's method, is then consistently pursued, anda algorithm is developed that isa true Newton algorithm for the problem, at the same time as the inherent structure is utilized for efficient calculations. An advantage with such an approach is that global and local convergence properties can be studied in a familiar framework. The algorithm is tested on several examples and comparisons to other algorithms are carried out. These show that the Newton algorithm performs well and is competitive with other methods. lt handles state variable constraints in a direct and efficient manner, and its practical convergence properties are robust. A general algorithm for !arge scale static problems is also developed in the thesis, and it is tested on a problem with load distribution in an electrical power network.

This thesis proposes a novel method for locating a p-dimensional invariant torus of an n-dimensional map. A set of non-linear equations is formulated and solved using the Newton-Raphson scheme. The method requires a set of sampled points on a guess invariant torus. An interpolant is passed through these points to compute the pointwise shift on the invariant torus, which is used to formulate the equation of invariance for the torus under the given map. The principal application of this method is to locate invariant tori of continuous systems. These tori occur for continuous dynamical systems having quasiperiodic orbits in state space. The discretization of the continuous system in terms of a map is accomplished in terms of its flow function. Results for one-dimensional invariant tori in two and three-dimensional state space and for two-dimensional invariant tori in three and four-dimensional maps are presented. / Master of Science

Convex optimization has developed a wide variety of useful tools critical to many applications in machine learning. However, unlike linear and quadratic programming, general convex solvers have not yet reached sufficient maturity to fully decouple the convex programming model from the numerical algorithms required for implementation. Especially as datasets grow in size, there is a significant gap in speed and scalability between general solvers and specialized algorithms. This thesis addresses this gap with a new model for convex programming based on an intermediate representation of convex problems as a sum of functions with efficient proximal operators. This representation serves two purposes: 1) many problems can be expressed in terms of functions with simple proximal operators, and 2) the proximal operator form serves as a general interface to any specialized algorithm that can incorporate additional `2-regularization. On a single CPU core, numerical results demonstrate that the prox-affine form results in significantly faster algorithms than existing general solvers based on conic forms. In addition, splitting problems into separable sums is attractive from the perspective of distributing solver work amongst multiple cores and machines. We apply large-scale convex programming to several problems arising from building the next-generation, information-enabled electrical grid. In these problems (as is common in many domains) large, high-dimensional datasets present opportunities for novel data-driven solutions. We present approaches based on convex models for several problems: probabilistic forecasting of electricity generation and demand, preventing failures in microgrids and source separation for whole-home energy disaggregation.

In order to make use of Newton&rsquo / s method for complex flow domains, an Euler multi-block Newton solver is developed. The generated Newton solver uses Analytical Jacobian derivation technique to construct the Jacobian matrices with different flux discretization schemes up to the second order face interpolations. Constructed sparse matrices are solved by parallel and series matrix solvers. In order to use structured grids for complex domains, multi-block grid construction is needed. Each block has its own Jacobian matrices and during the iterations the communication between the blocks should be performed. Required communication is performed with &ldquo / halo&rdquo / nodes. Increase in the number of grids requires parallelization to minimize the solution time. Parallelization of the analyses is performed by using matrix solvers having parallelization capability. In this thesis, some applications of the multi-block Newton method to different problems are given. Results are compared by using different flux discretization schemes. Convergence, analysis time and matrix solver performances are examined for different number of blocks.

The Multiplicative Schwarz Preconditioned Inexact Newton (MSPIN) algorithm is presented as a complement to Additive Schwarz Preconditioned Inexact Newton (ASPIN). At an algebraic level, ASPIN and MSPIN are variants of the same strategy to improve the convergence of systems with unbalanced nonlinearities; however, they have natural complementarity in practice. MSPIN is naturally based on partitioning of degrees of freedom in a nonlinear PDE system by field type rather than by subdomain, where a modest factor of concurrency can be sacrificed for physically motivated convergence robustness. ASPIN, originally introduced for decompositions into subdomains, is natural for high concurrency and reduction of global synchronization. The ASPIN framework, as an option for the outermost solver, successfully handles strong nonlinearities in computational fluid dynamics, but is barely explored for the highly nonlinear models of complex multiphase flow with capillarity, heterogeneity, and complex geometry. In this dissertation, the fully implicit ASPIN method is demonstrated for a finite volume discretization based on incompressible two-phase reservoir simulators in the presence of capillary forces and gravity. Numerical experiments show that the number of global nonlinear iterations is not only scalable with respect to the number of processors, but also significantly reduced compared with the standard inexact Newton method with a backtracking technique. Moreover, the ASPIN method, in contrast with the IMPES method, saves overall execution time because of the savings in timestep size. We consider the additive and multiplicative types of inexact Newton algorithms in the field-split context, and we augment the classical convergence theory of ASPIN for the multiplicative case. Moreover, we provide the convergence analysis of the MSPIN algorithm. Under suitable assumptions, it is shown that MSPIN is locally convergent, and desired superlinear or even quadratic convergence can be obtained when the forcing terms are picked suitably. Numerical experiments show that MSPIN can be significantly more robust than Newton methods based on global linearizations, and that MSPIN can be more robust than ASPIN, and maintain fast convergence even for challenging problems, such as high-Reynolds number Navier-Stokes equations.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第20153号 / 理博第4238号 / 新制||理||1609(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 坂上 貴之, 教授 上田 哲生, 教授 國府 寛司 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM