A Relation Between Anderson Acceleration and GMRES
(2020) In Bachelor's Theses in Mathematical Sciences NUMK11 20201Centre for Mathematical Sciences
- Abstract
- A very common type of problem within mathematics and numerical analysis are fixed-point problems, which can arise as sub-problems of optimization methods, differential equations solvers and much more. The most basic iterative approach for fixed-point problems is fixed-point iteration, special cases of which actually date back as far as the Babylonians, where it was used to to find the square roots of positive numbers. An issue with fixed-point iteration is that it can be very slow, as a consequence, acceleration methods have been developed, which are, not surprisingly, methods for speeding up fixed-point iteration. One of these methods are called Anderson acceleration, which has a very strong relationship with GMRES, an algorithm for... (More)
- A very common type of problem within mathematics and numerical analysis are fixed-point problems, which can arise as sub-problems of optimization methods, differential equations solvers and much more. The most basic iterative approach for fixed-point problems is fixed-point iteration, special cases of which actually date back as far as the Babylonians, where it was used to to find the square roots of positive numbers. An issue with fixed-point iteration is that it can be very slow, as a consequence, acceleration methods have been developed, which are, not surprisingly, methods for speeding up fixed-point iteration. One of these methods are called Anderson acceleration, which has a very strong relationship with GMRES, an algorithm for solving systems of linear equations, which at first glance, seems completely unrelated. The purpose of this thesis is to investigate the theory behind this relationship and to test it numerically. (Less)
- Popular Abstract
- Two types of problems which often arise within mathematics and numerical analysis are fixed-point problems and systems of linear equations, therefore, developing algorithms that solve these problems efficiently, is of particular interest.
Fixed-point iteration arguably the simplest way of solving fixed-point problem and special cases of this method actually date back as far as the Babylonians, where it was used to to find the square roots of positive numbers. An issue with fixed-point iteration is that it often too slow at finding a solution, therefore acceleration methods, such as Anderson acceleration have been developed.
What is interesting is that Anderson acceleration has a very strong relation to "the generalized minimal... (More) - Two types of problems which often arise within mathematics and numerical analysis are fixed-point problems and systems of linear equations, therefore, developing algorithms that solve these problems efficiently, is of particular interest.
Fixed-point iteration arguably the simplest way of solving fixed-point problem and special cases of this method actually date back as far as the Babylonians, where it was used to to find the square roots of positive numbers. An issue with fixed-point iteration is that it often too slow at finding a solution, therefore acceleration methods, such as Anderson acceleration have been developed.
What is interesting is that Anderson acceleration has a very strong relation to "the generalized minimal residual method" (GMRES), a very successful algorithm of solving a system of linear equations, which at first glance, seems completely unrelated. In this thesis we investigate the relationship between these algorithms and test it numerically. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9031089
- author
- Lorentzon, Gustaf LU
- supervisor
- organization
- course
- NUMK11 20201
- year
- 2020
- type
- M2 - Bachelor Degree
- subject
- keywords
- Numerical analysis, acceleration methods, fixed-point iteration, generalized minimal residual method, GMRES, iterative methods, numerical linear algebra, finite difference method
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFNA-4033-2020
- ISSN
- 1654-6229
- other publication id
- 2020:K17
- language
- English
- id
- 9031089
- date added to LUP
- 2021-06-08 17:24:20
- date last changed
- 2021-06-08 17:24:20
@misc{9031089,
abstract = {{A very common type of problem within mathematics and numerical analysis are fixed-point problems, which can arise as sub-problems of optimization methods, differential equations solvers and much more. The most basic iterative approach for fixed-point problems is fixed-point iteration, special cases of which actually date back as far as the Babylonians, where it was used to to find the square roots of positive numbers. An issue with fixed-point iteration is that it can be very slow, as a consequence, acceleration methods have been developed, which are, not surprisingly, methods for speeding up fixed-point iteration. One of these methods are called Anderson acceleration, which has a very strong relationship with GMRES, an algorithm for solving systems of linear equations, which at first glance, seems completely unrelated. The purpose of this thesis is to investigate the theory behind this relationship and to test it numerically.}},
author = {{Lorentzon, Gustaf}},
issn = {{1654-6229}},
language = {{eng}},
note = {{Student Paper}},
series = {{Bachelor's Theses in Mathematical Sciences}},
title = {{A Relation Between Anderson Acceleration and GMRES}},
year = {{2020}},
}