Remarks on polynomial methods for solving systems of linear algebraic equations (Q1209417)

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.