On some interpolatory iterative methods for the second degree polynomial operators (II)

8 years ago

(original), html, inverse interpolation, paper, semilocal convergence, solving F(x)=0 iteratively

Abstract

In this paper we apply some iterative methods obtained by inverse interpolation, in order to solve some specific classes of equations: the Ricatti equation, a Fredholm type equation, and the eigenvalue problem for a class of linear operators.

We obtain some semilocal convergence results, showing the r-convergence orders of the iterates.

Authors

Emil Cătinaş
(Tiberiu Popoviciu Institute of Numerical Analysis)

Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)

Keywords

inverse interpolation iterative methods; Ricatti equation; Fredholm type equation; eigenvalue problem; semilocal convergence results; r-convergence order.

Cite this paper as:

E. Cătinaş, I. Păvăloiu, On some interpolatory iterative methods for the second degree polynomial operators (II), Rev. Anal. Numér. Théor. Approx., 28 (1999) no. 2, pp. 133-143.

PDF

Scanned paper: on the journal website.

Latex version of the paper (soon).

About this paper

Journal

Revue d’Analyse et de Theorie de l’Approximation

Publisher Name

Editions de l’Academie Roumaine.

Paper on the journal website.

https://ictp.acad.ro/jnaat/journal/article/view/1999-vol28-no2-art4

Print ISSN

1222-9024

Online ISSN

2457-8126

MR

ZBL

Google Scholar citations

[1] M.P. Anselone and L.B. Rall, The Solution of Characteristic Value-Vector Problems by Newton Method, Numer. Math. 11 (1968), 38-45.

[2] E. Catinas and I. Pavaloiu, On the Chebyshev method for approximating the eigenvalue of linear operators, Rev. Anal. Numer. Theor. Approx., 25, 1-2 (1996), 43-56.
post

[3] E. Catinas and I. Pavaloiu, On a Chebyshev-type Method for approximating the solutions of Polynomial Operator Equations of Degree 2. Proceedings of the International Conference on Approximation and Optimization, Cluj-Napoca, July 29-August 1, 1996, Vol. 1, 219-226.

[4] E. Catinas and I. Pavaloiu, On approximating the eigenvalues and eigenvectors of linear continuous operators, Rev. Anal. Numer. Theor. Approx. 26 1-2 (1997), 19-27.
post

[5] E. Catinas and I. Pavaloiu, On some interpolatory iterative methods for the second degree polynomial operators (I). Rev. Anal. Numer. Theor. Approx., to appear.
post

[6] F. Chatelin, Valeurs propres de matrices. Mason, Paris, 1988.

[7] L. Collatz, Functionalanalysis und Numerische Mathematic. Springer-Verlag, Berlin, 1964.

[8] J.J. Dongarra, C.B. Moler and J.H. Wilkinson, Improving the Accurarcy of the Computed Eigenvalues and Eigenvectors. SIAM J. Numer. Anal., 20 1 (1983), 23-45.

[9] S. M. Grzegórski, On the Scaled Newton Method for the Symmetric Eigenvalue Problem. Computingh, 45 (1990), pp.277-282.

[10] V. S, Kartîşov and L. Iuhno, O nekotorîh Modifikatiah Metoda Niutona dlea Resenia Nelineinoi Spektralnoi Zadaci. J. Vîcisl. matem. i matem. fiz.,33 9 (1973), pp. 1403-1409 (in Russìan).

[11] M. L. Krasnov, lntegral Equations, Theoretical Introduction, Nauka Moskow, 1975 (in russian).

[12] J. M. Ortega and W. C Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press. New York. 1970

[13] C. Peters and J H. Wilkison. Inverse Iteration, III-Conditioned Equations and Newton’s Method, SIAM Review.21. 3 (1979), pp.339-360.

[14] M. C. Santos. A Note on the Newton Iteration for the Algebraic Eigenvalue Problem, SIAM J. Matrix Anal. Appl., 9 4 (1988), pp.561-569.

[15] R. A. Tapia und L. D. Whitley. The Projected Newton Method has Order 1+√2 for the Symmetric Eigenvalue Problem, SIAM J. Numer. Anal. 25,6 (1988), pp.1376-1382.

[16] S. Ul’m, On the Iterative Method with Simultaneous Approximation of the Inverse of the Operator, Izv. Acad. Nauk. Estonskoi S.S.R., 16 4 (1967), pp. 40-411.

[17] K. Wu. Y. Saad and A. Stathopoulos, Inexact Newton Preconditioning Techniques for Eigenvalue Problems, Lawrence Berkeley National Laboratory report number 41382 and Minnesota Supercomputing Institute report number UMSI 98-10, 1998.

[18] T. Yamamoto, Error Bounds for Computed Eigenvalues and Eigenvectors, Numer. Math., 34 (1980), pp.189-199.

Paper (preprint) in HTML form

On some Interpolatory Iterative Methods for the Second Degree Polynomial Operators (II)

On some Interpolatory Iterative Methods
for the Second Degree Polynomial Operators (II)

Emil Cătinaş and Ion Păvăloiu

1. The approximation of the solutions of Riccati differential equations

^†^†1991 AMS Subject Classification: 65J20, 65H17.

Consider the differential equation

(1)

y^{\prime}=a_{0}\left(x\right)y^{2}+a_{1}\left(x\right)y+a_{2}\left(x\right)

where the applications $a_{0},a_{1},a_{2}:\left[a,b\right]\rightarrow\mathbb{R}$ are continuous on the interval $\left[a,b\right],$ $a<b$ and $a_{2}$ is not the null function.

We are interested to approximate the solution of (1) with the condition

(2)

y\left(a\right)=y_{a}.

The solution will be searched in the space $C^{1}\left[a,b\right].$ For this purpose we consider the operator $F:C^{1}\left[a,b\right]\rightarrow C\left[a,b\right]$ given by

(3)

F\left(y\right)\left(x\right)=y^{\prime}\left(x\right)-a_{0}\left(x\right)y^{2% }\left(x\right)-a_{1}\left(x\right)y\left(x\right)-a_{2}\left(x\right).

The first and second order divided differences of $F$ are given by

(4)

\left[y_{1},y_{2};F\right]h\left(x\right)=h^{\prime}\left(x\right)-\big(a_{0}% \left(x\right)\big(y_{1}\left(x\right)+y_{2}\left(x\right)\big)+a_{1}\left(x% \right)\big)h\left(x\right)

respectively

(5)

\left[y_{1},y_{2},y_{3};F\right]h\left(x\right)k\left(x\right)=-a_{0}\left(x% \right)h\left(x\right)k\left(x\right),

for all $y_{1},y_{2},y_{3},h,k\in C^{1}\left[a,b\right].$

Formula (5) shows that the divided differences of order higher than two are the null multilinear operators.

Let $y_{0},y_{1}\in C^{1}\left[a,b\right]$ be given. The chord iterates $y_{k}\in C^{1}\left[a,b\right],$ $k=2,3,\ldots$ are constructed by

(6)

\left[y_{k-1},y_{k};F\right]\left(y_{k+1}-y_{k}\right)+F\left(y_{k}\right)=0,% \quad k=1,2,\ldots

As we shall see, the above equations lead to some first order linear nonhomogeneous differential equations.

Replacing in (6) the expression (4) of $F$ we get for $y_{k+1}$ the following differential equation.

(7)

y_{k+1}^{\prime}\left(x\right)=\varphi_{k}\left(x\right)y_{k+1}\left(x\right)+% \psi_{k}\left(x\right),

where we have denoted

	$\displaystyle\varphi_{k}\left(x\right)$	$\displaystyle=$	$\displaystyle a_{0}\left(x\right)\left(y_{k-1}\left(x\right)+y_{k}\left(x% \right)\right)+a_{1}\left(x\right)\quad\text{and}$
	$\displaystyle\psi_{k}\left(x\right)$	$\displaystyle=$	$\displaystyle-a_{0}\left(x\right)y_{k}\left(x\right)y_{k-1}\left(x\right)+a_{2% }\left(x\right).$

For solving (7) consider the condition

(8)

y_{k+1}\left(a\right)=y_{a},

so we are led to the expression of $y_{k+1}:$

(9)

y_{k+1}\left(x\right)=\exp\left(\int_{a}^{x}\varphi_{k}\left(s\right)ds\right)% \left(y_{a}+\int_{a}^{x}\psi_{k}\left(s\right)\exp\left(-\int_{a}^{s}\varphi_{% k}\left(t\right)dt\right)ds\right).

We are interested to find a bound for $\|\left[y_{0},y_{1};F\right]^{-1}\|.$

For this purpose consider the problem

\left\{\begin{array}[]{l}\left[y_{0},y_{1};F\right]h\left(x\right)=u\left(x% \right),\qquad u\in C\left[a,b\right]\\ h\left(a\right)=0\end{array}\right.

which has the solution

h\left(x\right)=\exp\left(\int_{a}^{x}\varphi_{1}\left(s\right)ds\right)\int_{% a}^{x}u\left(s\right)\exp\left(-\int_{a}^{s}\varphi_{1}\left(t\right)dt\right)ds.

This equality yields

(10)

\|\left[y_{0},y_{1};F\right]^{-1}\|\leq\sup\limits_{x\in\left[a,b\right]}\exp% \left(\int_{a}^{x}\varphi_{1}\left(s\right)ds\right)\int_{a}^{x}\exp\left(-% \int_{a}^{s}\varphi_{1}\left(t\right)dt\right)ds.

For the second order divided differences we have

(11)

\left\|\left[u,v,w;F\right]\right\|\leq\sup\limits_{x\in\left[a,b\right]}\left% |a_{0}\left(x\right)\right|.

Now denote

\displaystyle\bar{b}_{0}

\displaystyle=

\displaystyle\sup\limits_{x\in\left[a,b\right]}\exp\left(\int_{a}^{x}\varphi_{% 1}\left(s\right)ds\right)\int_{a}^{x}\exp\left(-\int_{a}^{s}\varphi_{1}\left(t% \right)dt\right)ds;

$\displaystyle\bar{\alpha}$	$\displaystyle=$	$\displaystyle\sup\limits_{x\in\left[a,b\right]}\left\|a_{0}\left(x\right)\right\|$
$\displaystyle\bar{d}_{0}$	$\displaystyle=$	$\displaystyle\sup\limits_{x\in\left[a,b\right]}\left\|y_{1}\left(x\right)-y_{0}% \left(x\right)\right\|$
$\displaystyle\bar{B}_{\bar{r}}\left(y_{0}\right)$	$\displaystyle=$	$\displaystyle\big\{y\in C^{1}\left[a,b\right]\;\|\;\sup\nolimits_{x\in\left[a,b% \right]}\left\|y\left(x\right)-y_{0}\left(x\right)\right\|\leq\bar{r}\big\}.$

With the above notations and taking into account relations (10) and (11), Theorem 4.1 from [6] implies:

Theorem 1.1.

Assume the functions $y_{0},y_{1}\in C^{1}\left[a,b\right],a_{0},a_{1},a_{2}\in C\left[a,b\right]$ and the real positive numbers $\overline{b}_{0},$ $\overline{\alpha},$ $\overline{d}_{0}$ and $\bar{r}$ satisfy the following conditions:

a) $\bar{b}_{0}\bar{\alpha}\left(2\bar{r}+\bar{d}_{0}\right)=q<1;$

b) $\varepsilon_{0}=\bar{\alpha}\bar{b}\sup\limits_{x\in\left[a,b\right]}\left|F% \left(y_{0}\right)\left(x\right)\right|<1,\;\bar{\alpha}\bar{b}\sup\limits_{x% \in\left[a,b\right]}\left|F\left(y_{1}\right)\left(x\right)\right|\leq% \varepsilon_{0}^{l},$ where $\bar{b}=\frac{\bar{b}_{0}}{1-q}$ and $l=\frac{1+\sqrt{5}}{2};$

c) $\frac{\varepsilon_{0}^{l}}{\bar{\alpha}\bar{b}\left(1-\varepsilon_{0}\right)}+% \bar{d}_{0}\leq\bar{r}.$

Then the sequence $\left(y_{k}\right)_{k\geq 0}$ given by (9) converges uniformly and its elements lie in the ball $\bar{B}_{\bar{r}}\left(y_{0}\right).$ Denoting $y^{\ast}=\lim\limits_{k\rightarrow\infty}y_{k}$ then $y^{\ast}$ is a solution of (1)-(2). Moreover, the following estimation hold:

\sup\limits_{x\in\left[a,b\right]}\left|y^{\ast}\left(x\right)-y_{k}\left(x% \right)\right|\leq\frac{\varepsilon_{0}^{l^{k}}}{\bar{\alpha}\bar{b}\left(1-% \varepsilon_{0}^{l}\right)},\quad k=2,3,\ldots

2. The approximation of the solutions of Fredholm integral equations

Consider the integral equation

(12)

\varphi\left(t\right)=\lambda\int_{a}^{b}a_{1}\left(t,s\right)\varphi\left(s% \right)ds+\mu\int_{a}^{b}a_{2}\left(t,s\right)\varphi^{2}\left(s\right)ds+f% \left(t\right),

where $\lambda,\mu\in\mathbb{R},$ $a_{1},a_{2}\in C\left[a,b\right]^{2}$ and $f\in C\left[a,b\right].$

Here we take the operator $F:C\left[a,b\right]\rightarrow C\left[a,b\right]$ given by

(13)

\quad\quad F\left(\varphi\right)\left(t\right)=\varphi\left(t\right)-\lambda% \int_{a}^{b}a_{1}\left(t,s\right)\varphi\left(s\right)ds-\mu\int_{a}^{b}a_{2}% \left(t,s\right)\varphi^{2}\left(s\right)ds-f\left(t\right)

The first and the second order divided differences of $F$ on $u,v,w\in C\left[a,b\right]$ are given by the following relations:

(14)

\begin{array}[]{l}\left[u,v;F\right]h(t)=h\left(t\right)-\lambda\!\!% \displaystyle\int_{a}^{b}\!a_{1}\left(t,s\right)h\left(s\right)ds-\mu\!\!% \displaystyle\int_{a}^{b}\!a_{2}\left(t,s\right)\left[u\left(s\right)+v\left(s% \right)\right]h\left(s\right)ds\\ \left[u,v,w;F\right]h\left(t\right)k\left(t\right)=-\mu\!\!\displaystyle\int_{% a}^{b}a_{2}\left(t,s\right)h\left(s\right)k\left(s\right)ds\end{array}

where $h,k\in C\left[a,b\right].$

Let $\varphi_{0},\varphi_{1}\in C\left[a,b\right]$ be given. As in the previous section, we shall construct the sequence $\left(\varphi_{k}\right)_{k\geq 0}\subset C\left[a,b\right]$ with the solutions of the following linear integral equations

(15)

\left[\varphi_{k-1},\varphi_{k};F\right]\left(\varphi_{k+1}-\varphi_{k}\right)% +F\left(\varphi_{k}\right)=0,\quad k=1,2,\ldots

From (15), by (13) and (14) we get for $\varphi_{k+1}$ the following linear integral Fredholm equation

(16)		$\displaystyle\varphi_{k+1}\left(t\right)=$	$\displaystyle\lambda\int_{a}^{b}a_{1}\left(t,s\right)\varphi_{k+1}\left(s% \right)ds$
		$\displaystyle+\mu\int_{a}^{b}a_{2}\left(t,s\right)\left(\varphi_{k-1}\left(s% \right)+\varphi_{k}\left(s\right)\right)\varphi_{k+1}\left(s\right)ds+G_{k}% \left(t\right)$

where

(17)

G_{k}\left(t\right)=f\left(t\right)-\mu\int_{a}^{b}a_{2}\left(t,s\right)\big(% \varphi_{k-1}\left(s\right)+\varphi_{k}\left(s\right)\big)ds.

In order to consider Theorem 4.1 [6] for the convergence of the sequence $\left(\varphi_{k}\right)_{k\geq 0}$ we need a bound for the operator $\left[\varphi_{0},\varphi_{1};F\right]^{-1}.$ In this respect we take the following equation

\left[\varphi_{0},\varphi_{1};F\right]h\left(t\right)=u\left(t\right),\qquad% \text{\ with }\lambda\neq 0,

i.e.

(18)

\quad\quad h\left(t\right)=\lambda\int_{a}^{b}a_{1}\left(t,s\right)h\left(s% \right)ds+\mu\int_{a}^{b}a_{2}\left(t,s\right)\big(\varphi_{0}\left(s\right)+% \varphi_{1}\left(s\right)\big)h\left(s\right)ds+u\left(t\right).

We shall assume that this equation has a unique solution. Denote $K_{0}\left(t,s,\lambda,\frac{\mu}{\lambda}\right)$ the corresponding ”resolvent” kernel. Then the solution of (18) has the following form:

(19)

h\left(t\right)=u\left(t\right)+\lambda\int_{a}^{b}K_{0}\left(t,s,\lambda,% \tfrac{\mu}{\lambda}\right)u\left(s\right)ds.

It can be easily seen by the above considerations that the following hold:

(20)

\|\left[\varphi_{0},\varphi_{1};F\right]^{-1}\|\leq 1+\left|\lambda\right|% \left(b-a\right)\sup\limits_{a\leq t,s\leq b}\left|K_{0}\left(t,s,\lambda,% \tfrac{\mu}{\lambda}\right)\right|.

At the same time, the norm of $\left[u,v,w;F\right]$ is bounded by

\left\|\left[u,v,w;F\right]\right\|\leq\left|\mu\right|\left(b-a\right)\sup% \limits_{a\leq t,s\leq b}\left|a_{2}\left(t,s\right)\right|.

We make the following notations:

$\displaystyle\widetilde{b}_{0}$	$\displaystyle=$	$\displaystyle 1+\left\|\lambda\right\|\left(b-a\right)\sup\limits_{a\leq t,s\leq b% }\left\|K_{0}\left(t,s,\lambda,\tfrac{\mu}{\lambda}\right)\right\|$
$\displaystyle\widetilde{\alpha}$	$\displaystyle=$	$\displaystyle\left\|\mu\right\|\left(b-a\right)\sup\limits_{a\leq t,s\leq b}% \left\|a_{2}\left(t,s\right)\right\|$
$\displaystyle\widetilde{d}_{0}$	$\displaystyle=$	$\displaystyle\sup\limits_{t\in\left[a,b\right]}\left\|\varphi_{1}\left(t\right)% -\varphi_{0}\left(t\right)\right\|$
$\displaystyle\bar{B}_{\tilde{r}}\left(\varphi_{0}\right)$	$\displaystyle=$	$\displaystyle\left\{\varphi\in C\left[a,b\right]\;\|\;\sup\nolimits_{t\in\left[% a,b\right]}\left\|\varphi\left(t\right)-\varphi_{0}\left(t\right)\right\|\leq% \tilde{r}\right\}$

Theorem 4.1 from [6] then implies the next result.

Theorem 2.1.

Assume the functions $a_{1},a_{2}\in C(\left[a,b\right]^{2})$ and the real numbers $\lambda,\mu,\widetilde{b}_{0},\widetilde{\alpha},\widetilde{d}_{0}$ and $\tilde{r}$ satisfy the following conditions:

a) $\widetilde{b}_{0}\widetilde{\alpha}\left(2\widetilde{r}+\widetilde{d}_{0}% \right)=\widetilde{q}<1;$

b) $\varepsilon_{0}=\widetilde{\alpha}\widetilde{b}^{2}\left\|F\left(\varphi_{0}% \right)\right\|<1,\;\rho_{1}=\widetilde{\alpha}\widetilde{b}\left\|F\left(% \varphi_{1}\right)\right\|\leq\varepsilon_{0}^{l}$ , where
$\left\|F\left(\varphi_{i}\right)\right\|=\sup\limits_{t\in\left[a,b\right]}% \left|F\left(\varphi_{i}\right)\left(t\right)\right|,\quad i=1,2;\quad% \widetilde{b}=\frac{\widetilde{b}_{0}}{1-\widetilde{q}}$ and $l=\frac{1+\sqrt{5}}{2};$

c) $\frac{\varepsilon_{0}^{l}}{\widetilde{\alpha}\widetilde{b}\left(1-\varepsilon_% {0}\right)}+\widetilde{d}_{0}\leq\widetilde{r}.$

Then the sequence $\left(\varphi_{k}\right)_{k\geq 0}$ generated by (16) converges uniformly and its elements lie in $\bar{B}_{\widetilde{r}}\left(\varphi_{0}\right).$ Denoting $\varphi^{\ast}=\lim\limits_{k\rightarrow\infty}\varphi_{k}$ then $\varphi^{\ast}$ is a solution of the integral equation (12) and the following estimations hold:

\sup\limits_{t\in\left[a,b\right]}\left|\varphi^{\ast}\left(t\right)-\varphi_{% k}\left(t\right)\right|\leq\frac{\varepsilon_{0}^{l^{k}}}{\widetilde{\alpha}% \widetilde{b}\left(1-\varepsilon_{0}^{l}\right)},\quad k=2,3,\ldots

As we have seen, the chord method requires the solving of a linear integral Fredholm equation at each iteration step. The problem takes a simplified form from the practical viewpoint when the kernels $a_{1}$ and $a_{2}$ from (12) are degenerate. In this case the linear integral equations (16) will be also with degenerate kernels, as can be easily seen. We shall consider in the following this particular case.

Let $\alpha_{i},\beta_{i}\in C\left[a,b\right],$ $i=1,\ldots,p$ two sets containing $p$ linear independent functions and also $\gamma_{i},\delta_{i}\in C\left[a,b\right],$ $i=1,\ldots,m$ two other sets with the same properties.

Assume the kernels $a_{1}$ and $a_{2}$ have the following form:

	$\displaystyle a_{1}\left(t,s\right)$	$\displaystyle=$	$\displaystyle\sum\limits_{i=1}^{p}\alpha_{i}\left(t\right)\beta_{i}\left(s% \right)\quad\text{and}$
	$\displaystyle a_{2}\left(t,s\right)$	$\displaystyle=$	$\displaystyle\sum\limits_{i=1}^{m}\gamma_{i}\left(t\right)\delta_{i}\left(s% \right).$

It can be verified without difficulty that the solution $\varphi_{k+1}$ of equation (16) has the form

(21)

\begin{array}[]{l}\varphi_{k+1}\left(t\right)=\lambda\sum\limits_{i=1}^{p}% \alpha_{i}\left(t\right)\displaystyle\int_{a}^{b}\beta_{i}\left(s\right)% \varphi_{k+1}\left(s\right)ds+\\ \quad\quad\quad\quad\quad+\mu\sum\limits_{i=1}^{m}\gamma_{i}\left(t\right)% \displaystyle\int_{a}^{b}\delta_{i}\left(s\right)\big(\varphi_{k-1}\left(s% \right)+\varphi_{k}\left(s\right)\big)\varphi_{k+1}\left(s\right)ds+G_{k}\left% (t\right).\end{array}

Consider the following notations:

\begin{array}[]{rcll}x_{i}^{\left(k+1\right)}&=&\displaystyle\int_{a}^{b}\beta% _{i}\left(s\right)\varphi_{k+1}\left(s\right)ds,&i=1,\ldots,p\\[5.69054pt] y_{i}^{\left(k+1\right)}&=&\displaystyle\int_{a}^{b}\delta_{i}\left(s\right)% \left(\varphi_{k-1}\left(s\right)+\varphi_{k}\left(s\right)\right)\varphi_{k+1% }\left(s\right)ds,&i=1,\ldots,m\\[5.69054pt] a_{ij}&=&\displaystyle\int_{a}^{b}\alpha_{i}\left(t\right)\beta_{j}\left(t% \right)dt,\quad&i,j=1,\ldots,p\\[5.69054pt] b_{ij}&=&\displaystyle\int_{a}^{b}\gamma_{i}\left(t\right)\beta_{j}\left(t% \right)dt,&i=1,\ldots,m,\;j=1,\ldots,p\\[5.69054pt] A_{ji}^{\left(k+1\right)}&=&\displaystyle\int_{a}^{b}\alpha_{i}\left(t\right)% \delta_{j}\left(t\right)\left(\varphi_{k}\left(t\right)+\varphi_{k-1}\left(t% \right)\right)dt,&i=1,\ldots,p,\;j=1,\ldots,m\\[5.69054pt] B_{ji}^{\left(k+1\right)}&=&\displaystyle\int_{a}^{b}\gamma_{i}\left(t\right)% \delta_{j}\left(t\right)\left(\varphi_{k}\left(t\right)+\varphi_{k-1}\left(t% \right)\right)dt&i,j=1,\ldots,m\\[5.69054pt] \theta_{j}^{\left(k+1\right)}&=&\displaystyle\int_{a}^{b}\beta_{j}\left(t% \right)G_{k}\left(t\right)dt&j=1,\ldots,p\\[5.69054pt] \varepsilon_{j}^{\left(k+1\right)}&=&\displaystyle\int_{a}^{b}\delta_{j}\left(% t\right)\left(\varphi_{k}\left(t\right)+\varphi_{k-1}\left(t\right)\right)G_{k% }\left(t\right)dt&j=1,\ldots,m\end{array}

We obtain then for $\varphi_{k+1}$ the expression

(22)

\varphi_{k+1}\left(t\right)=\lambda\sum\limits_{i=1}^{p}x_{i}^{\left(k+1\right% )}\alpha_{i}\left(t\right)+\mu\sum\limits_{i=1}^{m}y_{i}^{\left(k+1\right)}% \gamma_{i}\left(t\right)+G_{k}\left(t\right),

where $x_{i}^{\left(k+1\right)},$ $i=1,\ldots,p$ and $y_{i}^{\left(k+1\right)},$ $i=1,\ldots,m$ represent the solution of the linear system

(23)		$\displaystyle X^{\left(k+1\right)}$	$\displaystyle=$	$\displaystyle\lambda UX^{\left(k+1\right)}+\mu VY^{\left(k+1\right)}+\theta^{% \left(k+1\right)}$
	$\displaystyle Y^{\left(k+1\right)}$	$\displaystyle=$	$\displaystyle\lambda W^{\left(k+1\right)}X^{\left(k+1\right)}+\mu T^{\left(k+1% \right)}Y^{\left(k+1\right)}+\varepsilon^{\left(k+1\right)}$

where

$\displaystyle U$	$\displaystyle=$	$\displaystyle\left(a_{ji}\right)_{1\leq i,j\leq p},\quad V=\left(b_{ji}\right)% _{\begin{subarray}{c}1\leq i\leq p\\ 1\leq j\leq m\end{subarray}},$
$\displaystyle W^{\left(k+1\right)}$	$\displaystyle=$	$\displaystyle\left(A_{ji}\right)_{\begin{subarray}{c}1\leq i\leq p\\ 1\leq j\leq m\end{subarray}},\quad T^{\left(k+1\right)}=\left(B_{ji}\right)_{1% \leq i,j\leq m},$
$\displaystyle X^{\left(k+1\right)}$	$\displaystyle=$	$\displaystyle\left(x_{1}^{\left(k+1\right)},x_{2}^{\left(k+1\right)},\ldots,x_% {p}^{\left(k+1\right)}\right)^{T},$
$\displaystyle Y^{\left(k+1\right)}$	$\displaystyle=$	$\displaystyle\left(y_{1}^{\left(k+1\right)},y_{2}^{\left(k+1\right)},\ldots,y_% {m}^{\left(k+1\right)}\right)^{T},$
$\displaystyle\theta^{\left(k+1\right)}$	$\displaystyle=$	$\displaystyle\left(\theta_{1}^{\left(k+1\right)},\theta_{2}^{\left(k+1\right)}% ,\ldots,\theta_{p}^{\left(k+1\right)}\right)^{T},$
$\displaystyle\varepsilon^{\left(k+1\right)}$	$\displaystyle=$	$\displaystyle\left(\varepsilon_{1}^{\left(k+1\right)},\varepsilon_{2}^{\left(k% +1\right)},\ldots,\varepsilon_{m}^{\left(k+1\right)}\right)^{T}.$

It can be easily seen that under the conditions of Theorem 2.1 the sequences $\left(X^{k}\right)_{k\geq 0}$ and $\left(Y^{k}\right)_{k\geq 0}$ converge.

3. The approximation of the eigenpairs of matrices

Denote $V=\mathbb{K}^{n}$ and let $A\in$ $\mathbb{K}^{n\times n}$ where $\mathbb{K}=\mathbb{R}$ or $\mathbb{C}.$ As we have seen in [6], for computing the eigenpairs of $A$ we may consider a mapping $G:V\rightarrow\mathbb{K}$ with $G\left(0\right)\neq 1.$ The eigenvalues and eigenvectors are the solutions of the nonlinear system

(24)

F\left(x\right)=\left(\begin{array}[]{c}Av-\lambda v\\ G\left(v\right)-1\end{array}\right)=0,

where $x=\binom{v}{\lambda}\in V\times\mathbb{K}=\mathbb{K}^{n+1}.$ Denoting $v=\left(x^{\left(1\right)},x^{\left(2\right)},\ldots,x^{\left(n\right)}\right)$ and $\lambda=x^{\left(n+1\right)}$ then the first $n$ components of $F$ , $F_{i}$ , $i=1,\ldots,n$ , are given by

F_{i}\left(x\right)=a_{i1}x^{\left(1\right)}+\cdots+a_{i,i-1}x^{\left(i-1% \right)}+\left(a_{ii}-x^{\left(n+1\right)}\right)x^{\left(i\right)}+a_{i,i+1}x% ^{\left(i+1\right)}+\cdots+a_{in}x^{\left(n\right)}.

If we take $G$ as

G\left(v\right)=a\left\|v\right\|_{2}

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

F_{n+1}\left(x\right)=a\Big(\big(x^{\left(1\right)}\big)^{2}+\cdots+\big(x^{% \left(n\right)}\big)^{2}\Big)-1.

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

\left[x_{1},x_{2};F\right]=\left(\begin{array}[]{lllll}b_{11}&a_{12}&\cdots&a_% {1n}&a_{1,n+1}^{1}\\ a_{21}&b_{22}&\cdots&a_{2n}&a_{2,n+1}^{1}\\ \vdots&\vdots&&\vdots&\vdots\\ a_{n1}&a_{n2}&\cdots&b_{nn}&a_{n,n+1}^{1}\\ a_{n+1,1}&a_{n+1,2}&\cdots&a_{n+1,n}&0\end{array}\right)

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

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

\left[x_{1},x_{2},x_{3};F\right]hk\!\!=\!\!\left(\!\!\begin{array}[]{ccccc}-% \frac{1}{2}k^{\left(n+1\right)}&0&\cdots&0&\!\!-\frac{1}{2}k^{\left(1\right)}% \!\!\\ 0&-\frac{1}{2}k^{\left(n+1\right)}&\cdots&0&\!\!-\frac{1}{2}k^{\left(2\right)}% \!\!\\ \vdots&\vdots&&\vdots&\vdots\\ 0&0&\cdots&-\frac{1}{2}k^{\left(n+1\right)}&\!\!-\frac{1}{2}k^{\left(n\right)}% \!\!\\ ak^{\left(1\right)}&ak^{\left(2\right)}&\cdots&ak^{\left(n\right)}&0\end{array% }\!\!\right)\!\!\left(\begin{array}[]{c}h^{\left(1\right)}\\ h^{\left(2\right)}\\ \vdots\\ h^{\left(n\right)}\\ \!\!h^{\left(n+1\right)}\!\!\end{array}\!\!\right)

for all $h,k\in\mathbb{K}^{n+1}.$

We shall consider the max norm on $V$ and taking $\left\|x\right\|=\max\left\{\left\|v\right\|_{\infty},\left|\lambda\right|\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\left\{1,n% \left|a\right|\right\}.

Let $x_{0},x_{1}\in\mathbb{K}^{n+1}$ be such that $\left[x_{0},x_{1},F\right]$ is nonsingular. Denote $\hat{b}_{0}=\|\left[x_{0},x_{1};F\right]^{-1}\|_{\infty},$ $\hat{d}_{0}=\left\|x_{0}-x_{1}\right\|_{\infty},$ $\hat{\alpha}=\max\left\{1,n\left|a\right|\right\}$ and
$\overline{B}_{\hat{r}}=\left\{x\in\mathbb{K}^{n+1}\,|\,\left\|x-x_{0}\right\|_% {\infty}\leq\hat{r}\right\}.$ Applying Theorem 4.1 from [6] we get

Theorem 3.1.

Assume that the matrix $\left[x_{0},x_{1};F\right]$ is nonsingular and the numbers $\hat{b}_{0},\hat{d},\hat{\alpha}$ and $\hat{r}$ satisfy :

a) $\hat{b}_{0}\left(2\hat{r}+\hat{d}_{0}\right)=\hat{q}<1;$

b) $\varepsilon_{0}=b^{2}\left\|F\left(x_{0}\right)\right\|_{\infty}<1,\;b^{2}% \left\|F\left(x_{0}\right)\right\|\leq\varepsilon_{0}^{l}$ where $b=\frac{\hat{b}_{0}}{1-\hat{q}}$ and $l=\frac{1+\sqrt{5}}{2};$

c) $\frac{\varepsilon_{0}^{l}}{b\left(1-\varepsilon_{0}\right)}+\hat{d}_{0}\leq% \hat{r}.$

Then the sequence $\left(x_{k}\right)_{k\geq 0}$ given by the iterations $\left[x_{k-1},x_{k};F\right]\left(x_{k+1}-x_{k}\right)+F\left(x_{k}\right)=0,$ $k=1,2,\ldots$ lie in the ball $\overline{B}_{\hat{r}}\left(x_{0}\right)$ and converges. Denoting $x^{\ast}=\lim\limits_{k\rightarrow\infty}x_{k}$ then $F\left(x^{\ast}\right)=0$ and the following estimations hold

\left\|x^{\ast}-x_{k}\right\|_{\infty}\leq\frac{\varepsilon_{0}^{l^{k}}}{b% \left(1-\varepsilon_{0}^{l}\right)},\quad k=2,3,\ldots

4. Numerical examples

We shall consider two test matrices^†^†These matrices are available from MatrixMarket at the following address: http://math.nist.gov/MatrixMarket/. in order to study the behavior of the chord method for approximating the eigenpairs. The programs were written in Matlab^†^†MATLAB is a registered trademark of the MathWorks, Inc. and were run on a PC.

Pores1 matrix. This matrix arise from oil reservoir simulation. It is real, unsymmetric, of dimension 30 and has 20 real eigenvalues. We have chosen to study the largest eigenvalue $\lambda^{\ast}=\numprint{-1.8363e+1}$ . The initial approximations were taken $\lambda_{0}=\lambda^{\ast}+0.5$ and $\lambda_{1}=\lambda^{\ast}+0.25$ ; for the initial vector $v_{0}$ we perturbed the solution $v^{\ast}$ (computed by Matlab and then properly scaled to fulfill the norming equation) with random vectors having the components uniformly distributed on (- $\varepsilon$ , $\varepsilon$ ), $\varepsilon=0.2$ ; for the vector $v_{1}$ we halved the perturbation. The following results are typical for the runs made (we have considered here the same vector $\varepsilon$ for the four initial approximations), where for choice I we took in $G$ $a=\frac{1}{2}$ , while for choice II $a=\frac{1}{2n}$ .

Fidap002 matrix. This real symmetric matrix of dimension $n=441$ arise from finite element modeling. Its eigenvalues are all simple and range from

	Choice I		Choice II
$k$	$\left\\|x^{\ast}-x_{k}\right\\|$	$\left\\|F\left(x_{k}\right)\right\\|$	$\left\\|x^{\ast}-x_{k}\right\\|$	$\left\\|F\left(x_{k}\right)\right\\|$
0	8.533 3 ${}\cdot{}$ 10^-01	1.793 8 ${}\cdot{}$ 10⁺⁰⁶	8.533 3 ${}\cdot{}$ 10^-01	1.793 8 ${}\cdot{}$ 10⁺⁰⁶
1	4.266 7 ${}\cdot{}$ 10^-01	8.969 1 ${}\cdot{}$ 10⁺⁰⁵	4.266 7 ${}\cdot{}$ 10^-01	8.969 0 ${}\cdot{}$ 10⁺⁰⁵
2	7.860 1 ${}\cdot{}$ 10^-02	2.060 9 ${}\cdot{}$ 10^-01	1.624 5 ${}\cdot{}$ 10^-02	1.722 1 ${}\cdot{}$ 10^-01
3	6.683 1 ${}\cdot{}$ 10^-03	9.518 0 ${}\cdot{}$ 10^-03	2.908 6 ${}\cdot{}$ 10^-04	1.967 7 ${}\cdot{}$ 10^-03
4	1.764 7 ${}\cdot{}$ 10^-04	2.500 7 ${}\cdot{}$ 10^-04	2.978 3 ${}\cdot{}$ 10^-07	2.140 5 ${}\cdot{}$ 10^-06
5	2.370 6 ${}\cdot{}$ 10^-07	3.345 8 ${}\cdot{}$ 10^-07	7.586 2 ${}\cdot{}$ 10^-11	9.143 0 ${}\cdot{}$ 10^-10
6	4.662 4 ${}\cdot{}$ 10^-10	8.231 7 ${}\cdot{}$ 10^-10

Table 1. The chord method for Pores1.

$-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^{\ast}+10^{2}=-6.9996\cdot 10^{8}+100$ , resp. $\lambda_{1}=\lambda^{\ast}+10$ ; for the initial vector $v_{0}$ we perturbed the solution $v^{\ast}$ with random vectors having the components uniformly distributed on (- $\varepsilon$ , $\varepsilon$ ), $\varepsilon=0.5$ ; for the vector $v_{1}$ we halved the perturbation. The following results are typical for the runs made (we have considered a common vector $\varepsilon$ ).

	Choice I		Choice II
$k$	$\left\\|x^{\ast}-x_{k}\right\\|$	$\left\\|F\left(x_{k}\right)\right\\|$	$\left\\|x^{\ast}-x_{k}\right\\|$	$\left\\|F\left(x_{k}\right)\right\\|$
0	1.000 3 ${}\cdot{}$ 10⁺²	1.746 7 ${}\cdot{}$ 10⁺⁰⁹	2.510 7 ${}\cdot{}$ 10⁺⁰⁰	1.746 7 ${}\cdot{}$ 10⁺⁰⁹
1	1.007 8 ${}\cdot{}$ 10⁺¹	8.733 5 ${}\cdot{}$ 10⁺⁰⁸	1.255 3 ${}\cdot{}$ 10⁺⁰⁰	8.733 5 ${}\cdot{}$ 10⁺⁰⁸
2	3.485 3 ${}\cdot{}$ 10⁺¹	1.646 2 ${}\cdot{}$ 10⁺⁰²	5.287 7 ${}\cdot{}$ 10^-02	3.564 1 ${}\cdot{}$ 10^-03
3	2.136 8 ${}\cdot{}$ 10⁺⁰	2.337 3 ${}\cdot{}$ 10⁺⁰¹	6.180 4 ${}\cdot{}$ 10^-05	4.904 8 ${}\cdot{}$ 10^-06
4	4.476 1 ${}\cdot{}$ 10^-1	6.352 1 ${}\cdot{}$ 10^-01	5.985 8 ${}\cdot{}$ 10^-07	4.430 9 ${}\cdot{}$ 10^-06
5	6.521 4 ${}\cdot{}$ 10^-3	9.223 8 ${}\cdot{}$ 10^-03
6	1.561 7 ${}\cdot{}$ 10^-5	2.296 1 ${}\cdot{}$ 10^-05
7	5.960 5 ${}\cdot{}$ 10^-7	8.564 7 ${}\cdot{}$ 10^-08

Table 2. The secant method for Fidap002.

References

[1]
[2] M.P. Anselone, L.B. Rall, The solution of characteristic value-vector problems by Newton method, Numer. Math. 11 (1968), pp. 38–45.
[3] 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. 25 (1996) nos. 1–2, pp. 43–56.
[4] E. Cătinaş and I. Păvăloiu, On the Chebyshev method for approximating the eigenvalues of linear operators, Proceedings of International Conference on Approximation and Optimization, Cluj-Napoca, July 29 - August 1, 1996, vol. 1, pp. 219–226.
[5] E. Cătinaş and I. Păvăloiu, On approximating the eigenvalues and eigenvectors of linear continuous operators, Rev. Anal. Numér. Théor. Approx. 26 (1997) nos. 1–2, pp. 19–27.
[6] 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., 27 (1998) no. 1, pp. 33–45.
[7] F. Chatelin, Valeurs propres de matrices, Mason, Paris, 1988.
[8] L. Collatz, Functionalanalysis und Numerische Mathematik, Springer-Verlag, Berlin, 1964.
[9] J.J. Dongarra, C.B. Moler and J.H. Wilkinson, Improving the accuracy of the computed eigenvalues and eigenvectors, SIAM J. Numer. Anal., 20 (1983) no. 1, pp. 23–45.
[10] S.M. Grzegórski, On the scaled Newton method for the symmetric eigenvalue problem, Computing, 45 (1990), pp. 277–282.
[11] V.S. Kartîşov and F.L. Iuhno, O nekotorîh Modifikaţiah Metoda Niutona dlea Resenia Nelineinoi Spektralnoi Zadaci, J. Vîcisl. matem. i matem. fiz. 33 (1973) 9, pp. 1403–1409 (in Russian).
[12] M.L. Krasnov, Integral Equations. Theoretical Introduction, Nauka, Moskow, 1975 (in Russian).
[13] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
[14] G. Peters and J.H. Wilkinson, Inverse iteration, ill-conditioned equations and Newton’s method, SIAM Review, 21 (1979) no. 3, pp. 339–360.
[15] M.C. Santos, A note on the Newton iteration for the algebraic eigenvalue problem, SIAM J. Matrix Anal. Appl., 9 (1988) no. 4, pp. 561–569.
[16] R.A. Tapia, L.D. Whitley, The projected Newton method has order $1+\sqrt{2}$ for the symmetric eigenvalue problem, SIAM J. Numer. Anal., 25 (1988) no. 6, pp. 1376–1382.
[17] S. Ul’m, On the iterative method with simultaneous approximation of the inverse of the operator, Izv. Acad. Nauk. Estonskoi S.S.R., 16 (1967) 4, pp. 403–411.
[18] K. Wu, Y. Saad and A. Stathopoulos, Inexact Newton preconditioning techniques for eigenvalue problems, Lawrence Berkeley National Laboratory report number 41382 and Minnesota Supercomputing Institute report number UMSI 98-10, 1998.
[19] T. Yamamoto, Error bounds for computed eigenvalues and eigenvectors, Numer. Math. 34 (1980), pp. 189–199.

Received: March 3, 1998.

Tiberiu Popoviciu Institute of Numerical Analysis

Romanian Academy

P.O. Box 68

3400 Cluj-Napoca 1

Romania

1999

Extension of Lipschitz functions and best approximation

May 4, 2023

Periodic solutions of superlinear impulsive differential systems

April 6, 2022

Two-dimensional inverse problem of Dynamics for families in parametric form

October 15, 2024

On some interpolatory iterative methods for the second degree polynomial operators (II)

Abstract

Authors

Keywords

Cite this paper as:

PDF

About this paper

Journal

Publisher Name

Paper on the journal website.

Print ISSN

Online ISSN

MR

ZBL

Google Scholar citations

References

Paper (preprint) in HTML form

On some Interpolatory Iterative Methods for the Second Degree Polynomial Operators (II)

1. The approximation of the solutions of Riccati differential equations

Theorem 1.1.

2. The approximation of the solutions of Fredholm integral equations

Theorem 2.1.

3. The approximation of the eigenpairs of matrices

Theorem 3.1.

4. Numerical examples

References

Related Posts

On some Interpolatory Iterative Methods
for the Second Degree Polynomial Operators (II)