- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- A theoretical justification that Anderson acceleration...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
A theoretical justification that Anderson acceleration improves linear convergence rates. Pollock, Sara
Description
The extrapolation method known as Anderson acceleration has been used for decades to speed the convergence of nonlinear solvers in many applications. A mathematical justification of the improved convergence rate however has remained elusive. Here, we provide theory to establish the improved convergence rate. The key ideas of the analysis are relating the difference of consecutive iterates to residuals based on performing the inner-optimization in a Hilbert space setting, and explicitly defining the gain in the optimization stage to be the ratio of improvement over a step of the unaccelerated fixed point iteration. The main result we prove is this method of acceleration improves the convergence rate of a fixed point iteration to first order by a factor of the gain at each step as the method converges.
Item Metadata
Title |
A theoretical justification that Anderson acceleration improves linear convergence rates.
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2019-05-16T13:32
|
Description |
The extrapolation method known as Anderson acceleration has been used for decades to speed the convergence of nonlinear solvers in many applications. A mathematical justification of the improved convergence rate however has remained elusive. Here, we provide theory to establish the improved convergence rate. The key ideas of the analysis are relating the difference of consecutive iterates to residuals based on performing the inner-optimization in a Hilbert space setting, and explicitly defining the gain in the optimization stage to be the ratio of improvement over a step of the unaccelerated fixed point iteration. The main result we prove is this method of acceleration improves the convergence rate of a fixed point iteration to first order by a factor of the gain at each step as the method converges.
|
Extent |
29.0 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: University of Florida
|
Series | |
Date Available |
2020-09-12
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0394333
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Researcher
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International