In this thesis, we mainly study preconditioning techniques for all-at-once linear systems arising from discretization of three types of time-dependent advection-diffusion equation: linear diffusion equation, constant-coefficients advection-diffusion equation, time-fractional sub-diffusion equation. The proposed preconditioners are used with Krylov subspace solvers. The preconditioner developed for linear diffusion equation is based on -circulant ap- proximation of temporal discretization. Diagonalizability, clustering of spectrum and identity-plus-low-rank decomposition are derived for the preconditioned matrix. We also show that generalized minimal residual (GMRES) solver for the preconditioned system has a linear convergence rate independent of matrix-size. The preconditioner for constant-coefficients advection-diffusion equation is based on approximating the discretization of advection term with a matrix diagonalizable by sine transform. Eigenvalues of the preconditioned matrix are proven to be lower and upper bounded by positive constants independent of discretization parameters. Moreover, as the preconditioner is based on spatial approximation, it is also applicable to steady-state problem. We show that GMRES for the preconditioned steady-state problem has a linear convergence rate independent of matrix size. The preconditioner for time-fractional sub-diffusion equation is based on approximat- ing the discretization of diffusion term with a matrix diagonalizable by sine transform. We show that the condition number of the preconditioned matrix is bounded by a constant independent of discretization parameters so that the normalized conjugate gradient (NCG) solver for the preconditioned system has a linear convergence rate independent of discretization parameters and matrix size. Fast implementations based on fast Fourier transform (FFT), fast sine transform (FST) or multigrid approximation are proposed for the developed preconditioners. Numerical results are reported to show the performance of the developed preconditioners

In this thesis, we mainly study preconditioning techniques for all-at-once linear systems arising from discretization of three types of time-dependent advection-diffusion equation: linear diffusion equation, constant-coefficients advection-diffusion equation, time-fractional sub-diffusion equation. The proposed preconditioners are used with Krylov subspace solvers. The preconditioner developed for linear diffusion equation is based on -circulant ap- proximation of temporal discretization. Diagonalizability, clustering of spectrum and identity-plus-low-rank decomposition are derived for the preconditioned matrix. We also show that generalized minimal residual (GMRES) solver for the preconditioned system has a linear convergence rate independent of matrix-size. The preconditioner for constant-coefficients advection-diffusion equation is based on approximating the discretization of advection term with a matrix diagonalizable by sine transform. Eigenvalues of the preconditioned matrix are proven to be lower and upper bounded by positive constants independent of discretization parameters. Moreover, as the preconditioner is based on spatial approximation, it is also applicable to steady-state problem. We show that GMRES for the preconditioned steady-state problem has a linear convergence rate independent of matrix size. The preconditioner for time-fractional sub-diffusion equation is based on approximat- ing the discretization of diffusion term with a matrix diagonalizable by sine transform. We show that the condition number of the preconditioned matrix is bounded by a constant independent of discretization parameters so that the normalized conjugate gradient (NCG) solver for the preconditioned system has a linear convergence rate independent of discretization parameters and matrix size. Fast implementations based on fast Fourier transform (FFT), fast sine transform (FST) or multigrid approximation are proposed for the developed preconditioners. Numerical results are reported to show the performance of the developed preconditioners

This study used the multiple methods of classroom observation, interview with teachers and students, and paper-and-pencil test to investigate the ability development of seventh-grade students in learning two-dimensional linear systems of equations and the corresponding error analysis. Hopefully, the results of this study can be as a reference for the middle school math teachers to plan the suitable teaching strategies when they teach two-dimensional linear systems of equations to their students. At the beginning, the researcher entered two seventh-grade classrooms of one middle school in Kaohsiung to make the preliminary observations and let students (also the teachers) to get used to the appearance of the researcher in the classroom during the period that one-variable linear equations were taught. Subsequently, the formal observations were carried out for 40 class periods that two-dimensional linear systems of equations were taught. All the observations made about how teachers taught and how students learned were recorded and content analyzed. Two paper-and-pencil tests were administered during the period of preliminary observations. And three paper-and pencil tests were given during the period of the formal observations. All the test results were collected and analyzed in numerous ways. Based on the literature survey and the interviews with six middle school math teachers, all relevant abilities of mastering two-dimensional linear systems of equations were classified into three categories: Character Symbols (10 sub-abilities), Operational Principals (five sub-abilities), and Other Abilities (16 sub-abilities). Based on the results of the content analyses of classroom observations and the error analyses of five paper-and-pencils tests for each sub-abilities of mastering the subject, it was observed that during the period of developing the abilities on solving two-dimensional linear systems of equations, most students showed some signs of obstacles and puzzles. Even by the end of the course on two-dimensional linear systems of equations, most students still did not master the subject well. Based on the results of this study, it is proposed that the length of teaching period needs to be increased and more efficient learning strategies need to be introduced to the students when two-dimensional linear systems of equations are taught.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-05T14:28:50Z No. of bitstreams: 2 Dissertação - Ademir Alves Aguiar - 2014.pdf: 1975016 bytes, checksum: 31320b5840b8b149afedc97d0e02b49b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-06T10:38:03Z (GMT) No. of bitstreams: 2 Dissertação - Ademir Alves Aguiar - 2014.pdf: 1975016 bytes, checksum: 31320b5840b8b149afedc97d0e02b49b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-06T10:38:03Z (GMT). No. of bitstreams: 2 Dissertação - Ademir Alves Aguiar - 2014.pdf: 1975016 bytes, checksum: 31320b5840b8b149afedc97d0e02b49b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-12-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this dissertation we present a semi-local convergence analysis for the Gauss-Newton method to solve a special class of systems of non-linear equations, under the hypothesis that the derivative of the non-linear operator satisfies a majorant condition. The proofs and conditions of convergence presented in this work are simplified by using a simple majorant condition. Another tool of demonstration that simplifies our study is to identify regions where the iteration of Gauss-Newton is “well-defined”. Moreover, special cases of the general theory are presented as applications. / Nesta dissertação apresentamos uma análise de convergência semi-local do método de Gauss-Newton para resolver uma classe especial de sistemas de equações não-lineares, sob a hipótese que a derivada do operador não-linear satisfaz uma condição majorante. As demonstrações e condições de convergência apresentadas neste trabalho são simplificadas pelo uso de uma simples condição majorante. Outra ferramenta de demonstração que simplifica o nosso estudo é a identificação de regiões onde a iteração de Gauss-Newton está “bem-definida”. Além disso, casos especiais da teoria geral são apresentados como aplicações.

<p>In computational science it is common to describe dynamic systems by mathematical models in forms of differential or integral equations. These models may contain parameters that have to be computed for the model to be complete. For the special type of ordinary differential equations studied in this thesis, the resulting parameter estimation problem is a separable nonlinear least squares problem with equality constraints. This problem can be solved by iteration, but due to complicated computations of derivatives and the existence of several local minima, so called short-cut methods may be an alternative. These methods are based on simplified versions of the original problem. An algorithm, called the modified Kaufman algorithm, is proposed and it takes the separability into account. Moreover, different kinds of discretizations and formulations of the optimization problem are discussed as well as the effect of ill-conditioning.</p><p>Computation of parameters often includes as a part solution of linear system of equations <i>Ax = b</i>. The corresponding pseudoinverse solution depends on the properties of the matrix <i>A</i> and vector <i>b</i>. The singular value decomposition of <i>A</i> can then be used to construct error propagation matrices and by use of these it is possible to investigate how changes in the input data affect the solution <i>x</i>. Theoretical error bounds based on condition numbers indicate the worst case but the use of experimental error analysis makes it possible to also have information about the effect of a more limited amount of perturbations and in that sense be more realistic. It is shown how the effect of perturbations can be analyzed by a semi-experimental analysis. The analysis combines the theory of the error propagation matrices with an experimental error analysis based on randomly generated perturbations that takes the structure of <i>A</i> into account</p>

In computational science it is common to describe dynamic systems by mathematical models in forms of differential or integral equations. These models may contain parameters that have to be computed for the model to be complete. For the special type of ordinary differential equations studied in this thesis, the resulting parameter estimation problem is a separable nonlinear least squares problem with equality constraints. This problem can be solved by iteration, but due to complicated computations of derivatives and the existence of several local minima, so called short-cut methods may be an alternative. These methods are based on simplified versions of the original problem. An algorithm, called the modified Kaufman algorithm, is proposed and it takes the separability into account. Moreover, different kinds of discretizations and formulations of the optimization problem are discussed as well as the effect of ill-conditioning. Computation of parameters often includes as a part solution of linear system of equations Ax = b. The corresponding pseudoinverse solution depends on the properties of the matrix A and vector b. The singular value decomposition of A can then be used to construct error propagation matrices and by use of these it is possible to investigate how changes in the input data affect the solution x. Theoretical error bounds based on condition numbers indicate the worst case but the use of experimental error analysis makes it possible to also have information about the effect of a more limited amount of perturbations and in that sense be more realistic. It is shown how the effect of perturbations can be analyzed by a semi-experimental analysis. The analysis combines the theory of the error propagation matrices with an experimental error analysis based on randomly generated perturbations that takes the structure of A into account