Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Numerical Algorithms
Erschienen in: Numerical Algorithms 3/2020

20.08.2019 | Original Paper

A convergence study for reduced rank extrapolation on nonlinear systems

verfasst von: Avram Sidi

Erschienen in: Numerical Algorithms | Ausgabe 3/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Reduced Rank Extrapolation (RRE) is a polynomial type method used to accelerate the convergence of sequences of vectors {xm}. It is applied successfully in different disciplines of science and engineering in the solution of large and sparse systems of linear and nonlinear equations of very large dimension. If s is the solution to the system of equations x = f(x), first, a vector sequence {xm} is generated via the fixed-point iterative scheme xm+ 1 = f(xm), m = 0,1,…, and next, RRE is applied to this sequence to accelerate its convergence. RRE produces approximations sn, k to s that are of the form \(\boldsymbol {s}_{n,k}={\sum }_{i=0}^{k} \gamma _{i} \boldsymbol {x}_{n+i}\) for some scalars γi depending (nonlinearly) on xn, xn+ 1,…,xn+k+ 1 and satisfying \({\sum }_{i=0}^{k} \gamma _{i}=1\). The convergence properties of RRE when applied in conjunction with linear f(x) have been analyzed in different publications. In this work, we discuss the convergence of the sn, k obtained from RRE with nonlinear f(x) (i) when \(n\to \infty \) with fixed k, and (ii) in two so-called cycling modes.
Vorheriger Artikel Family weak conjugate gradient algorithms and their convergence analysis for nonconvex functions
Nächster Artikel An ADMM-based scheme for distance function approximation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
It is clear that the integers n and k are chosen by the user and that M is determined by n, k, and the extrapolation method being used.
 
2
The approaches of [18] and [21] to RRE are almost identical, in the sense that \(\boldsymbol {s}_{n,k}={\sum }^{k}_{i=0}\gamma _{i} \boldsymbol {x}_{n+i}\) in [21], while \(\boldsymbol {s}_{n,k}={\sum }^{k}_{i=0}\gamma _{i} \boldsymbol {x}_{n+i+1}\) in [18], the γi being the same for both. The approaches of [11] and [21] are completely different, however; their equivalence was proved in the review paper of Smith, Ford, and Sidi [39].
 
3
Note that M = n + k + 1 for MPE, RRE, MMPE, and SVD-MPE, while M = n + 2k for SEA, VEA, and TEA.
 
4
Given a nonzero vector \(\boldsymbol {u}\in \mathbb {C}^{N},\) the monic polynomial P(λ) is said to be a minimal polynomial of the matrix \(\boldsymbol {T}\in \mathbb {C}^{N\times N}\)with respect tou if P(T)u = 0 and if P(λ) has smallest degree.
The polynomial P(λ) exists and is unique. Moreover, if P1(T)u = 0 for some polynomial P1(λ) with \(\deg P_{1} > \deg P\), then P(λ) divides P1(λ). In particular, P(λ) divides the minimal polynomial of T, which in turn divides the characteristic polynomial of T. [Thus, the degree of P(λ) is at most N and its zeros are some or all of the eigenvalues of T.]
 
5
It is clear that to apply any of the extrapolation methods in this mode, one needs to know the matrix F(s), for which one also needs to know the solution s.
 
6
Note that k is not necessarily fixed in this mode of cycling; it may vary from one cycle to the next. It always satisfies k ≤ N, however.
 
7
Quadratic convergence is relevant only when f(x) is nonlinear. When f(x) is linear, that is, f(x) = Tx + d, where T is a fixed N × N matrix and d is a fixed vector, hence F(s) = T, the solution s is obtained already at the end of step MC2 of the first cycle, that is, we have s(1) = s. Therefore, there is nothing to analyze when f(x) is linear.
 
8
See also Sidi and Shapira [37] concerning a modified version of restarted GMRES with prior Richardson iterations, that is very closely related to RRE.
 
9
Recall that, for any matrix K with rank(K) = r, we have ∥K∥2 ≤∥K∥F ≤ r∥K∥2. See Golub and Van Loan [13].
 
10
Clearly, g(z) = zk is in \(\tilde {\mathcal {P}_{k}}\) and 𝜃k < 1 since L < 1. Next, in general, the polynomial g(z) that gives the optimum in (5.4) is different from zk. Thus, generally speaking, 𝜃k < Lk
 
11
For the linear system \(\boldsymbol {x}=\tilde {\boldsymbol {f}}(\boldsymbol {x})\), we have \(\boldsymbol {\epsilon }_{n+1}=\tilde {\boldsymbol {F}}\boldsymbol {\epsilon }_{n}\), n = 0, 1,…, as power iterations. Thus, in some cases, \(\boldsymbol {e}_{\infty }=\lim _{n\to \infty }\boldsymbol {e}_{n}\) exists and is an eigenvector of \(\tilde {\boldsymbol {F}}\), hence causes \(\text {rank}(\boldsymbol {S}(\boldsymbol {e}_{\infty }))=1\) at most. Clearly, this is a problem when rank(S(en)) = k > 1, for n = 0, 1,….
 
Literatur
1.
2.
3.
Ben-Israel, A., Greville, T.N.E.: Generalized Inverses: Theory and Applications. CMS Books in Mathematics, 2nd edn. Springer, New York (2003)MATH
4.
Brezinski, C.: Application de l’𝜖-algorithme à la résolution des systèmes non linéaires. C. R. Acad. Sci. Paris 271 A, 1174–1177 (1970)MATH
5.
Brezinski, C.: Sur un algorithme de résolution des systèmes non linéaires. C. R. Acad. Sci. Paris 272 A, 145–148 (1971)MATH
6.
Brezinski, C.: Généralisations de la transformation de Shanks, de la table de Padé, et de l’𝜖-algorithme. Calcolo 12, 317–360 (1975)MATHCrossRefMathSciNet
7.
Brezinski, C.: Accélération de la Convergence en Analyse Numérique. Number 584 in Lecture Notes in Mathematics, Springer, Berlin (1977)
8.
Brezinski, C., Redivo Zaglia, M.: Extrapolation Methods: Theory and Practice. North-Holland, Amsterdam (1991)MATH
9.
Cabay, S., Jackson, L.W.: A polynomial extrapolation method for finding limits and antilimits of vector sequences. SIAM J. Numer. Anal. 13, 734–752 (1976)MATHCrossRefMathSciNet
10.
Campbell, S.L., Meyer, C.D. Jr.: Generalized Inverses of Linear Transformations. Dover, New York (1991)MATH
11.
Eddy, R.P.: Extrapolating to the limit of a vector sequence. In: Wang, P.C.C. (ed.) Information Linkage Between Applied Mathematics and Industry, pp 387–396. Academic Press, New York (1979)
12.
13.
Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The Johns Hopkins University Press, Baltimore (2013)MATH
14.
Graves-Morris, P.R., Saff, E.B.: Row convergence theorems for generalised inverse vector-valued Padé, approximants. J. Comp. Appl. Math. 23, 63–85 (1988)MATHCrossRef
15.
Jbilou, K., Sadok, H.: Some results about vector extrapolation methods and related fixed-point iterations. J. Comp. Appl. Math. 36, 385–398 (1991)MATHCrossRefMathSciNet
16.
17.
Jbilou, K., Sadok, H.: LU-implementation of the modified minimal polynomial extrapolation method. IMA J. Numer. Anal. 19, 549–561 (1999)MATHCrossRefMathSciNet
18.
Kaniel, S., Stein, J.: Least-square acceleration of iterative methods for linear equations. J Optimization Theory Appl. 14, 431–437 (1974)MATHCrossRefMathSciNet
19.
Laurens, J., Le Ferrand, H.: Fonctions d’itérations vectorielles, itérations rationelles. C. R. Acad. Sci. Paris 321 I, 631–636 (1995)MATH
20.
Le Ferrand, H.: Convergence of the topological 𝜖-algorithm for solving systems of nonlinear equations. Numer. Algorithms 3, 273–283 (1992)MATHCrossRefMathSciNet
21.
Mes̆ina, M.: Convergence acceleration for the iterative solution of the equations x = AX + f. Comput. Methods Appl. Mech. Engrg. 10, 165–173 (1977)CrossRefMathSciNet
22.
Ortega, J., Rheinboldt, W.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970)MATH
23.
Pugachev, B.P.: Acceleration of the convergence of iterative processes and a method of solving systems of nonlinear equations. U.S.S.R. Comput. Math. Math. Phys. 17, 199–207 (1978)MATHCrossRef
24.
25.
Sidi, A.: Convergence and stability properties of minimal polynomial and reduced rank extrapolation algorithms. SIAM J. Numer. Anal. 23, 197–209 (1986). Originally appeared as NASA TM-83443 (1983)MATHCrossRefMathSciNet
26.
27.
Sidi, A.: Efficient implementation of minimal polynomial and reduced rank extrapolation methods. J. Comp. Appl. Math. 36, 305–337 (1991). Originally appeared as NASA TM-103240 ICOMP-90-20 (1990)MATHCrossRefMathSciNet
28.
Sidi, A.: Convergence of intermediate rows of minimal polynomial and reduced rank extrapolation tables. Numer. Algorithms 6, 229–244 (1994)MATHCrossRefMathSciNet
29.
Sidi, A.: Extension and completion of Wynn’s theory on convergence of columns of the epsilon table. J Approx. Theory 86, 21–40 (1996)MATHCrossRefMathSciNet
30.
Sidi, A.: Review of two vector extrapolation methods of polynomial type with applications to large-scale problems. J. Comput. Sci. 3, 92–101 (2012)CrossRef
31.
Sidi, A.: SVD-MPE: An SVD-based vector extrapolation method of polynomial type. Appl. Math. 7, 1260–1278 (2016). Special issue on Applied Iterative MethodsCrossRef
32.
33.
Sidi, A.: Vector Extrapolation Methods with Applications. Number 17 in SIAM Series on Computational Science and Engineering. SIAM, Philadelphia (2017)CrossRef
34.
Sidi, A., Bridger, J.: Convergence and stability analyses for some vector extrapolation methods in the presence of defective iteration matrices. J. Comp. Appl. Math. 22, 35–61 (1988)MATHCrossRefMathSciNet
35.
Sidi, A., Ford, W.F., Smith, D.A.: Acceleration of convergence of vector sequences. SIAM J. Numer. Anal. 23, 178–196 (1986). Originally appeared as NASA TP-2193 (1983)MATHCrossRefMathSciNet
36.
Sidi, A., Shapira, Y.: Upper bounds for convergence rates of vector extrapolation methods on linear systems with initial iterations. Technical Report 701, Computer Science Dept., Technion–Israel Institute of Technology, 1991. Appeared also as NASA TM-105608 ICOMP-92-09 (1992)
37.
Sidi, A., Shapira, Y.: Upper bounds for convergence rates of acceleration methods with initial iterations. Numer. Algorithms 18, 113–132 (1998)MATHCrossRefMathSciNet
38.
Skelboe, S.: Computation of the periodic steady-state response of nonlinear networks by extrapolation methods. IEEE Trans. Circuits Syst. 27, 161–175 (1980)MATHCrossRefMathSciNet
39.
Smith, D.A., Ford, W.F., Sidi, A.: Extrapolation methods for vector sequences. SIAM Rev. 29, 199–233 (1987). Erratum: SIAM Rev. 30, 623–634 (1988)MATHCrossRefMathSciNet
40.
Stewart, G.W.: On the continuity of the generalized inverse. 17, 33–45 (1969)
41.
42.
Varga, R.S.: Matrix Iterative Analysis. Number 27 in Springer Series in Computational Mathematics, 2nd edn. Springer, New York (2000)
43.
44.
45.
46.
47.
Metadaten
Titel
A convergence study for reduced rank extrapolation on nonlinear systems
verfasst von
Avram Sidi
Publikationsdatum
20.08.2019
Verlag
Springer US
Erschienen in
Numerical Algorithms / Ausgabe 3/2020
Print ISSN: 1017-1398
Elektronische ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-019-00788-6

Weitere Artikel der Ausgabe 3/2020

Numerical Algorithms 3/2020 Zur Ausgabe

Original Paper

Family weak conjugate gradient algorithms and their convergence analysis for nonconvex functions

Original Paper

Optimizations of a fast multipole symmetric Galerkin boundary element method code

Original Paper

Two-step inexact Newton-type method for inverse singular value problems

Original Paper

Reconstruction algorithms of an inverse source problem for the Helmholtz equation

Original Paper

Recursive blocked algorithms for linear systems with Kronecker product structure

Original Paper

Computers in mathematical research: the study of three-point root-finding methods