Solving polynomial operator equations of degree 2 by Steffensen-type iterations with approximate inverses

Let $X$ be a Banach space over the field $\mathbb{K}(\mathbb{K}=\mathbb{R}$ or $\mathbb{C}),F:X\rightarrow X$ a polynomial operator of degree 2, and consider the equation

Such equations often appear in different problems, as eigenproblems for linear operators, Chandrasekhar integral equations, etc. This motivates the study of the iterative methods for solving (1.1), by enhancing the particularities appearing in the case of the second degree polynomials. The second order derivative is a constant bilinear operator, i.e. its expression does not depend on $x$. This allows the obtaining of some simpler convergence conditions, compared to the general case (see also [19, [26, [36, [10]-[13]).

The solving of a linear equation at each iteration step is an important aspect when analyzing the iterative methods. From this standpoint, the methods which approximate at each step the inverse of the Frechét derivative of the first order divided differences are important to analyze.

Given $x_{0}\in X$ and the linear continuous operator $\Gamma_{0}\in\mathcal{L}(X)$, we shall consider the sequences $\left(x_{k}\right)_{k\geq 0}$ and $\left(\Gamma_{k}\right)_{k\geq 0}$ given by

where $[x,y,F]$ denotes the first order divided difference of $F$ on $x$ and $y$, and $G:X\rightarrow X$ is an operator such that equation (1.1) is equivalent to

As it can be seen, the above method is a Steffensen type one, with the approximation of the inverse of the first order divided difference.

We shall consider in the following the application $G$ given by

with some $\gamma\in\mathbb{K}(\gamma\neq 0)$ fixed.
Since $F$ is a polynomial of degree 2, one has

where $\theta_{3}$ denotes the trilinear null mapping, and $[t,u,v,w;F]$ denotes the divided difference of order 3 of $F$ on the nodes $t,u,v,w\in X$. It is then obvious that the second order divided difference is a constant bilinear operator (it does not depend on the nodes). Denote

We shall need the following auxiliary result.
Lemma 1 Let $\alpha,\beta\in\mathbb{R},\alpha,\beta>0$ and $\left(\delta_{k}\right)_{k\geq 0},\left(\eta_{k}\right)_{k\geq 0}\subset\mathbb{R}_{+}$obeying

If $\delta_{0},\eta_{0}\leq uq$ for some $0<q<1$ and $u=\min\left\{\frac{1}{1+\alpha},\frac{1}{(1+\beta)^{2}}\right\}$, then

Proof. Obviously, $u(1+\alpha)\leq 1$ and $u(1+\beta)^{2}\leq 1$. Relations 2.2. for $k=0$ are verified by the assumption. Supposing now that 2.2 are satisfied for $k=s$, then by 2.1 we obtain for $k=s+1$

which ends the proof.
We shall assume that

and that, given $x_{0}\in X$, there exists $r>0$ such that

where $\bar{B}_{r}\left(x_{0}\right)=\left\{x\in X:\left\|x-x_{0}\right\|\leq r\right\}$.
We obtain the following result.
Theorem 2 Assume (1.5), (2.3), (2.4), and that the operator $\Gamma_{0}\in\mathcal{L}(X)$ is invertible, obeying

where
$0\leq q<1$,
$b_{0}=\left\|\left[x_{0},G\left(x_{0}\right);F\right]^{-1}\right\|$,
$\rho=\frac{b_{0}}{1-q}$,
$b=\rho\eta_{0}+1$,
$\beta=ab^{2}(2+|\gamma|c)$,
$\alpha=ab(b+|\gamma|)$,
$u=\min\left\{\frac{1}{1+\alpha},\frac{1}{(1+\beta)^{2}}\right\}$ and
$p=b_{0}a(2+|\gamma|c)r$.
If $x_{0},G\left(x_{0}\right)\in B_{r}\left(x_{0}\right),\left\|F\left(x_{0}\right)\right\|=\delta_{0}\leq uq$, and

then

• •

  the elements $x_{k},G\left(x_{k}\right)$ remain in $\bar{B}_{r}\left(x_{0}\right)$,

  Report issue for preceding element
• •

  the sequences $\left(x_{k}\right)_{k\geq 0},\left(\Gamma_{k}\right)_{k\geq 0}$ are Cauchy,

  Report issue for preceding element
• •

  denoting $x^{*}=\lim x_{k}$, one has the estimates

  Report issue for preceding element

$-\lim_{k\rightarrow\infty}\Gamma_{k}=\left[x^{*},G\left(x^{*}\right);F\right]^{-1}$, and

Proof. Hypothesis $p<1$ and the existence of $\left[x_{0},G\left(x_{0}\right);F\right]^{-1}$ imply the existence of $[x,G(x);F]^{-1}$ for all $x\in\bar{B}_{r}\left(x_{0}\right)$, and moreover

and

Denoting $\eta_{k}=\left\|I-\left[x_{k},G\left(x_{k}\right);F\right]\Gamma_{k}\right\|$ and $\delta_{k}=\left\|F\left(x_{k}\right)\right\|,k=0,1,\ldots$, for $x_{k},G\left(x_{k}\right)\in\bar{B}_{r}\left(x_{0}\right)$, we will show that the elements $\eta_{k}$ and $\delta_{k}$ satisfy the assumptions of Lemma 2.1, which will imply

Indeed, since $F$ is a polynomial operator of degree 2 we have

whence, by 1.2

and therefore

i.e. $\delta_{k+1}\leq\eta_{k}\delta_{k}+\alpha\delta_{k}^{2}$, with $\alpha=ab(b+|\gamma|)$.
From (1.2) we also get

One can easily verify that

whence, taking into account the notations we made, it follows

with $\beta=ab^{2}(2+|\gamma|c)$.
Now we show that $\left(x_{k}\right)_{k\geq 0},\left(G\left(x_{k}\right)\right)_{k\geq 0}\in\bar{B}_{r}\left(x_{0}\right)$.
Assume that for some $k\geq 0$, $x_{s}\in\bar{B}_{r}\left(x_{0}\right),s=\overline{0,k}$.
We have that

Then

and

Using inequality 2.8 we shall show that the sequences $\left(\Gamma_{k}\right)_{k\geq 0}$ and $\left(x_{k}\right)_{k\geq 0}$ are Cauchy, and therefore they converge.

Indeed,

Then,

which shows that $\left(x_{k}\right)_{k\geq 0}$ is fundamental. Consequently, there exists $x^{*}=\lim_{k\rightarrow\infty}x_{k}$ and

Regarding the approximations $\Gamma_{k}$ we have

But

whence

which shows that $\lim\Gamma_{k}=\left[x^{*},G\left(x^{*}\right);F\right]^{-1}$, and

Denote $V=\mathbb{K}^{n}$ and let $A\in\mathbb{K}^{n\times n}$ where $\mathbb{K}=\mathbb{R}$ or $\mathbb{C}$.
For computing the eigenpairs of $A$ one may consider a mapping $H$ : $V\rightarrow\mathbb{K}$ with $H(0)\neq 1$.

The eigenvalues and eigenvectors of $A$ are the solutions of

where $x=\binom{v}{\lambda}\in V\times\mathbb{K}=\mathbb{K}^{n+1}$.
Denoting $v=\left(x^{(1)},x^{(2)},\ldots,x^{(n)}\right)$ and $\lambda=x^{(n+1)}$ then the first $n$ components of $F$ are
$F_{i}(x)=$
$a_{i1}x^{(1)}+\cdots+a_{i,i-1}x^{(i-1)}+\left(a_{ii}-x^{(n+1)}\right)x^{(i)}+a_{i,i+1}x^{(i+1)}+\cdots+a_{in}x^{(n)}$.
If we take $H$ as

for some fixed $\alpha\in\mathbb{R}$ then

The matrices associated to the first order divided differences of $F$ at the points $x_{1},x_{2}\in\mathbb{K}^{n+1}$ are

where $b_{ii}=a_{ii}-\frac{1}{2}\left(x_{2}^{(n+1)}+x_{1}^{(n+1)}\right),a_{i,n+1}=-\frac{1}{2}\left(x_{2}^{(i)}+x_{1}^{(i)}\right)$ and $a_{n+1,i}=\alpha\left(x_{1}^{(i)}+x_{2}^{(i)}\right)$, for $i=1,\ldots,n$.

The second order divided differences of $F$ at $x_{1},x_{2},x_{3}$ are given by

for all $h,k\in\mathbb{K}^{n+1}$.
We shall consider the max norm on $V$ and taking $\|x\|=\max\left\{\|v\|_{\infty},|\lambda|\right\}$ for all $x=\binom{v}{\lambda}\in\mathbb{K}^{n+1}$ we are led to the max norm on $\mathbb{K}^{n+1}$. It can be easily verified that $\left\|\left[x_{1},x_{2},x_{3};F\right]\right\|_{\infty}\leq\max\{1,n|\alpha|\}$.

The classical choice for $\alpha$ is $\alpha=1/2$. We have proposed in 11 the choice $\alpha=1/(2n)$, which may lead to smaller bounds for the norm of the second order finite differences.

We shall consider the Fidap002 test matrix from the Harwell Boeing collection ¹ in order to study the behavior of method (1.2) for approximating the eigenpairs. The program was written in Matlab; we took $\gamma=0.05$ and $\Gamma_{0}=\left[x_{0},G\left(x_{0}\right);F\right]^{-1}$, computed with MatLab.

This real symmetric matrix of dimension $n=441$ arise from finite element modeling. Its eigenvalues are all simple and range from $-7\cdot 10^{8}$ to $3\cdot 10^{6}$. We have chosen to study the smallest eigenvalue, which is well separated. The initial approximations were taken $\lambda_{0}=\lambda^{*}+1\cdot 10^{1}$ and for the initial vector $v_{0}$ we perturbed the solution $v^{*}$ with random vectors having the components uniformly distributed on $(-\varepsilon,\varepsilon),\varepsilon=1\cdot 10^{-4}$; this value for $\varepsilon$ had to be taken smaller than for other methods in order to obtain the attraction of the iterates (1.2); also, these iterates converged slower than others (see, e.g. [13]). The following results are typical for the runs made (we have considered a common vector $\varepsilon$ ).

[1] M. P. Anselone and L. B. Rall - The solution of characteristic valuevector problems by Newton method, Numer. Math., vol. 11, 1968, pp. 38-45.
[2] I. K. Argyros - Quadratic equations and applications Chandrasekhar’s and related equations, Bull. Austral. Math. Soc., vol. 32, 1985, pp. 275-297.
[3] I. K. Argyros - On polynomial equations in Banach space, perturbation techniques and applications, Intern. J. Math. Math. Sci., vol. 10, no. 1, 1987, pp. 69-78.
[4] I. K. Argyros - On the number of solutions of some integral equations arising in radiative transfer, Intern. J. Math. Math. Sci., vol. 12, no. 2, 1989, pp. 297-304.
[5] I. K. Argyros - On a class of quadratic equations with perturbation, Funct. et Approx. Comm. Math., vol. XX, 1992, pp. 51-63.
[6] I. K. Argyros - Polynomial Operator Equations in Abstract Spaces and Applications, CRC Press, Boca Raton, FL, 1998.
[7] I. K. Argyros - Advances in the Efficiency of Computational Methods and Applications, World Scientific. Singapore, 2000.
[8] L. W. Busbridge - The Mathematics of Radiative Transfer, Cambridge University Publ., Cambridge, England, 1960.
[9] B. Cahlon and M. Eskin - Existence theorems for an integral equation of the Chandrasekhar $H$-equation with perturbation, J. Math. Anal. Applic., vol. 83, 1981, pp. 159-171.
[10] E. Cătinaş and I. Păvăloiu - On the Chebyshev method for approximating the eigenvalues of linear operators, Rev. Anal. Numér. Théor. Approx., vol. 25, nos. 1-2, 1996, pp. 43-56.
[11] E. Cătinaş and I. Păvăloiu - On a Chebyshev-type method for approximating the solutions of polynomial operator equations of degree 2, Proceedings of International Conference on Approximation and Optimization, Cluj-Napoca, July 29 - august 1, 1996, vol. 1, pp. 219-226.
[12] E. Cătinaş and I. Păvăloiu - On some interpolatory iterative methods for the second degree polynomial operators (I), Rev. Anal. Numér. Théor. Approx., vol. 27, 1998, pp. 33-45.
[13] E. Cătinaş and I. Părăloiu - On some interpolatory iterative methods for the second degree polynomial operators (II), Rev. Anal. Numér. Théor. Approx., vol. 28, 1999, pp. 133-143.
[14] S. Chandrasekhar - Radiative Transfer, Dover Publ., New York, 1960.
[15] F. Chatelin - Valeurs propers de matrices, Mason, Paris, 1988.
[16] P. G. Ciarlet - Introduction à l’analyse numérique matricielle et à l’optimisation, Mason, Paris, 1990.
[17] L. Collatz - Functionalanalysis und Numerische Mathematik, SpringerVerlag, Berlin, 1964.
[18] A. Diaconu - On the convergence of an iterative method of Chebyshev type, Rev. Anal. Numér. Théor. Approx. vol. 24, no. 1-2, 1995, pp. 91-102.
[19] A. Diaconu and I. Părăloiu - Sur quelques méthodes itératives pour la résolution des équations opérationnelles, Rev. Anal. Numér. Théor. Approx., vol. 1, 1972, pp. 45-61.
[20] J. J. Dongarra, C. B. Moler and J. H. Wilkinson - Improving the accuracy of the computed eigenvalues and eigenvectors, SIAM J. Numer. Anal., vol. 20, no. 1, 1983, pp. 23-45.
[21] S. M. Grzegórski - On the scaled Newton method for the symmetric eigenvalue problem, Computing, vol. 45, 1990, pp. 277-282.
[22] V. S. Kartîşov and F. L. Iuhno - O nekotorîh modifikatiah metoda niutona dlea resenia nelineinoi spektralnoi Zadaci, J. Vîcisl. matem. i matem. fiz., vol. 33, no. 9, 1973, pp. 1403-1409.
[23] I. Lazăr - On a Newton-type method, Rev. Anal. Numér. Théor. Approx., vol. 23, no. 2, 1994, pp. 167-174.
[24] J. M. Ortega and W. C. Rheinboldt - Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
[25] I. Păvăloiu - Sur les procédés itératifs à un order élevé de convergence, Mathematica (Cluj), vol. 12(35), no. 2, 1970, pp. 309-324.
[26] I. Păvăloiu - Introduction in the Approximation Theory for the Solutions of Equations, Ed. Dacia, Cluj-Napoca, 1986 (in Romanian).
[27] I. Păvăloiu - Observations concerning some approximation methods for the solutions of operator equations, Rev. Anal. Numér. Théor. Approx., vol. 23, no. 2, 1994, pp. 185-196.
[28] I. Păvăloiu - Approximation of the root of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, vol. 32, no. 1-2, 1995, pp. 69-82.
[29] I. Păvăloiu and E. Cătinaş - Remarks on some Newton on Chebyshevtype methods for approximation eigenvalues and eigenvectors of matrices, Computer Science Journal of Moldova, vol. 7, no. 1, 1999, pp. 3-17.
[30] G. Peters and J. H. Wilkinson - Inverse iteration, ill-conditioned equations and Newton’s method, SIAM Review, vol. 21, no. 3, 1979, pp. 339-360.
[31] L. B. Rall - Quadratic equations in Banach space, Rend. Circ. Math. Palermo, vol. 10, 1961, pp. 314-332.
[32] D. Ruch - On uniformly contractive systems and quadratic equations in Banach space, Bull. Austral. Math. Soc., vol. 95, 1995, pp. 441-455.
[33] M. C. Santos - A note on the Newton iteration for the algebraic eigenvalue problem, SIAM J. Matrix Anal. Appl., vol. 9, no. 4, 1988, pp. 561-569.
[34] R. A. Tapia and L. D. Whitley - The projected Newton method has order $1+\sqrt{2}$ for the symmetric eigenvalue problem, SIAM J. Numer. Anal., vol. 25, no. 6, 1988, pp. 1376-1382.
[35] F. J. Traub - Iterative Methods for the Solution of Equations, PrenticeHall Inc., Englewood Cliffs, N.J., 1964.
[36] S. Ul’m - On the iterative method with simultaneous approximation of the inverse of the operator, Izv. Acad. Nauk. Estonskoi S.S.R., vol. 16, no. 4, 1967, pp. 403-411.
[37] T. Yamamoto -Error bounds for computed eigenvalues and eigenvectors, Numer. Math., vol. 34, 1980, pp. 189-199.