A Krylov subspace generalization of the improved Wilkinson's algorithm for ill-conditioned linear systems (Q260135): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
To solve the system \(Ax=b\), this note proposes to start with an initial \(x^{(0)}\) and iterate with \(x^{(n+1)}=x^{(n)}+e^{(n)}\) where \(e^{(n)}=(D+pA)^{-1}p(b-Ax^{(n)})\). \(D\) is a symmetric positive definite matrix and \(p>0\). \textit{R. W. Freund} et al. poposed previously in [in: Acta Numerica 1992. Cambridge: Cambridge University Press. 57--100 (1992; Zbl 0762.65019)] a special case with \(D=qI\) as an improved Wilkinson iteration (originally Wilkinson chose \(q=0\) and \(p=1\)). In this note, the authors show that they may choose \(p\) such that the spectral radius of the iteration matrix is less than 1 so that convergence is guaranteed and moreover that the residue \(r^{(n)}=b-Ax^{(n)}\) belongs to the Krylov subspace \(K_n(C,r^{(0)})\) and \(x^{(n)}\in x^{(0)}+EK_{n-1}(C,r^{(0)})\) with \(E=p(D+pA)^{-1}\) and \(C=AE\), hence identifying the iteration as a preconditioned Krylov iteration. | |||
Property / review text: To solve the system \(Ax=b\), this note proposes to start with an initial \(x^{(0)}\) and iterate with \(x^{(n+1)}=x^{(n)}+e^{(n)}\) where \(e^{(n)}=(D+pA)^{-1}p(b-Ax^{(n)})\). \(D\) is a symmetric positive definite matrix and \(p>0\). \textit{R. W. Freund} et al. poposed previously in [in: Acta Numerica 1992. Cambridge: Cambridge University Press. 57--100 (1992; Zbl 0762.65019)] a special case with \(D=qI\) as an improved Wilkinson iteration (originally Wilkinson chose \(q=0\) and \(p=1\)). In this note, the authors show that they may choose \(p\) such that the spectral radius of the iteration matrix is less than 1 so that convergence is guaranteed and moreover that the residue \(r^{(n)}=b-Ax^{(n)}\) belongs to the Krylov subspace \(K_n(C,r^{(0)})\) and \(x^{(n)}\in x^{(0)}+EK_{n-1}(C,r^{(0)})\) with \(E=p(D+pA)^{-1}\) and \(C=AE\), hence identifying the iteration as a preconditioned Krylov iteration. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Adhemar Bultheel / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 15A18 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65F15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65F22 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6558494 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
linear system | |||
Property / zbMATH Keywords: linear system / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
iterative method | |||
Property / zbMATH Keywords: iterative method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
ill-conditioned problems | |||
Property / zbMATH Keywords: ill-conditioned problems / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Wilkinson's method | |||
Property / zbMATH Keywords: Wilkinson's method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Krylov subspace method | |||
Property / zbMATH Keywords: Krylov subspace method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
preconditioning | |||
Property / zbMATH Keywords: preconditioning / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10092-014-0135-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2100956693 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4016503 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5689624 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3857636 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4342463 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Iterative refinement of solution with biparameter for solving ill-conditioned systems of linear algebraic equations. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matrix theory. Basic results and techniques / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 16:09, 11 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Krylov subspace generalization of the improved Wilkinson's algorithm for ill-conditioned linear systems |
scientific article |
Statements
A Krylov subspace generalization of the improved Wilkinson's algorithm for ill-conditioned linear systems (English)
0 references
18 March 2016
0 references
To solve the system \(Ax=b\), this note proposes to start with an initial \(x^{(0)}\) and iterate with \(x^{(n+1)}=x^{(n)}+e^{(n)}\) where \(e^{(n)}=(D+pA)^{-1}p(b-Ax^{(n)})\). \(D\) is a symmetric positive definite matrix and \(p>0\). \textit{R. W. Freund} et al. poposed previously in [in: Acta Numerica 1992. Cambridge: Cambridge University Press. 57--100 (1992; Zbl 0762.65019)] a special case with \(D=qI\) as an improved Wilkinson iteration (originally Wilkinson chose \(q=0\) and \(p=1\)). In this note, the authors show that they may choose \(p\) such that the spectral radius of the iteration matrix is less than 1 so that convergence is guaranteed and moreover that the residue \(r^{(n)}=b-Ax^{(n)}\) belongs to the Krylov subspace \(K_n(C,r^{(0)})\) and \(x^{(n)}\in x^{(0)}+EK_{n-1}(C,r^{(0)})\) with \(E=p(D+pA)^{-1}\) and \(C=AE\), hence identifying the iteration as a preconditioned Krylov iteration.
0 references
linear system
0 references
iterative method
0 references
ill-conditioned problems
0 references
Wilkinson's method
0 references
Krylov subspace method
0 references
preconditioning
0 references
0 references