Remarks on polynomial methods for solving systems of linear algebraic equations
type: Item
instance of: scholarly article
title: Remarks on polynomial methods for solving systems of linear algebraic equations
zbMATH Open document ID: 0802.65032
published in: Applications of Mathematics
publication date: 1993-05-16T00:00:00Z
full work available at URL: https://eudml.org/doc/15725
review text: Let \(A\) be a non-singular, complex, non-Hermitian \(n\times n\) matrix. The author considers a method for solving the linear system (1) \(Ax= b\), assuming that \(\sigma(A)\), the spectrum of \(A\), is known to be contained in a given open domain \(\Omega\) of the complex plane \(\mathbb{C}\), \(0\not\in\Omega\). Furthermore, for any open \(K\) with regular Jordan boundary \(\Gamma\), \(\sigma(A)\subset K\subset \overline K\subset\Omega\). The Dunford integral (2) \(f(z)= (2\pi i)^{-1}\int_ \Gamma f(z)(z- A)^{-1} dz\) constitutes the starting point of the method. Here \(f(z)= \varphi(z)- w_ N(z)\) with \(\varphi(z)= 1/z\) and \(w_ N(z)\) a complex polynomial of degree \(\leq N\). The estimate \(\| A^{-1}- w_ N(A)\|= C\|\varphi- w_ N\|_{\overline K_ \infty}\) easily follows from (2). The algorithm for solving (1) then contains the following two stages: 1) Find a polynomial \(w_ N\) approximating \(1/z\) on \(\Omega\) in the \(\|\cdot\|_{\overline K_ \infty}\) norm. 2) Take \(x_ N= w_ N(A)b\) as an approximate solution of (1). \(w_ N(z)\) is constructed as a Fourier expansion of the function \(1/z\), related to orthogonal polynomials in \(L^ 2(\Omega)\) space. The orthogonality property makes the algorithm perfectly stable, in the cost of an extensive memory space, however. The fact that the quality of approximation depends on \(N\) but not on \(n\) makes the method suitable in cases \(n\gg N\). In practice \(N\leq 40\). Difficulties arise if \(\sigma(A)\) is too large and not far enough from the origin. In order to avoid this inconvenience and to find more effective special algorithms for some special forms of \(A\), several modifications in realizing the stages 1) and 2) are given. In order to visualize some advantages and drawbacks, numerical examples using different forms and different positions of the region \(\Omega\) are given. Some misprints.
Mathematics Subject Classification ID: 65F10
zbMATH DE Number: 167847
zbMATH Keywords: polynomial methods
zbMATH Keywords: Fourier expansions
zbMATH Keywords: Richardson iteration
zbMATH Keywords: numerical examples
author: Krzysztof Moszyński
reviewed by: Veikko Seppälä
MaRDI profile type: Publication
cites work: Q4286977
cites work: Remarks on the lemma of Nersesyan in complex approximation
cites work: Polynomials by Conformal Mapping for the Richardson Iteration Method for Complex Linear Systems
description: scientific article; zbMATH DE number 167847