On a Chebyshev-type method for approximating the solutions of polynomial operator equations of degree 2

1. Introduction

For solving the nonlinear equations, in a recent paper, A. Diaconu [7] has proposed the Chebyshev-type method $\left(1.2\right)$ , for which the computation of the inverse of the derivative at each step is avoided. Similar methods have been studied by other authors [5], [6], [14], but these does not preserve the r-convergence order 3.

In this note we shall apply method $\left(1.2\right)$ for solving polynomial operator equations of degree 2. We shall show that the hypotheses for the convergence of the method take a simplified form, the convergence order remaining unaltered. We shall consider then the eigenproblem for scalar matrices, applying to it the studied method. Numerical examples are also given.

Let $X$ be a Banach space, $F:X\rightarrow X$ a nonlinear operator and consider the equation

F\left(x\right)=\overline{\theta},

1.1

$\overline{\theta}$ being the null element of $X$ .

For solving $\left(1.1\right)$ in [7] there are considered three sequences, $\left(x_{k}\right)_{k\geq 0}\subset X$ and $\left(B_{k}\right)_{k\geq 0}$ , $\left(C_{k}\right)_{k\geq 0}\subset{\Cal{L}}\left(X\right)$ given by

$\displaystyle C_{k}$	$\displaystyle=B_{k}\left(2I-F^{\prime}\left(x_{k}\right)B_{k}\right)$	$1.2$
$\displaystyle x_{k+1}$	$\displaystyle=x_{k}-C_{k}F\left(x_{k}\right)-\tfrac{1}{2}C_{k}F^{\prime\prime}% \left(x_{k}\right)\left(C_{k}F\left(x_{k}\right)\right)^{2}$
$\displaystyle B_{k+1}$	$\displaystyle=B_{k}\left[3I-3F^{\prime}\left(x_{k+1}\right)B_{k}+\left(F^{% \prime}\left(x_{k+1}\right)B_{k}\right)^{2}\right],\qquad k=0,1,.\;,$

where $x_{0}\in X$ and $B_{0}\in{\Cal{L}}\left(X\right)$ , ${\Cal{L}}\left(X\right)$ being the set of all linear continuous operators on $X$ and $I\in{\Cal{L}}\left(X\right)$ being the identity operator.

Remark. The convergence with r-order 3 of this method is obtained despite a general principle which suggests that every newly computed unknown should be used at once in the determination of the other unknowns (e.g. the Gauss-Seidel method for linear systems). In our case we could consider $C_{k}$ instead of $B_{k}$ in the determination of $B_{k+1}.$

2. The convergence of the method

We shall give first a lemma.

Lemma

If the sequences of real positive numbers $\left(\delta_{k}\right)_{k\geq 0}$ and $\left(\rho_{k}\right)_{k\geq 0}$ satisfy

	$\displaystyle\delta_{k+1}$	$\displaystyle\leq\left(\delta_{k}+2\rho_{k}+2\rho_{k}^{2}\right)^{3}$
	$\displaystyle\rho_{k+1}$	$\displaystyle\leq\,\rho_{k}\delta_{k}^{2}+\,\rho_{k}^{2}\delta_{k}^{2}+2\,\rho% _{k}^{3}+\,\rho_{k}^{4},\qquad k=0,1,.,$

where $\max\left\{\,\delta_{0},\rho_{0}\right\}\leq\frac{1}{7}d$ for some $0<d<1,$

then the following relation holds:

\max\left\{\,\delta_{k},\rho_{k}\right\}\leq\tfrac{1}{7}d^{3^{k}},\qquad k=0,1% ,...\;.

The proof can be easily obtained by induction.

In the following we shall study the convergence of method $\left(1.2\right)$ supposing that $F$ is a polynomial operator of degree 2, i.e. $F$ is indefinite differentiable on $X$ and $F^{\left(i\right)}=\theta_{i}$ for $i\geq 3,$ $\theta_{i}$ being the $i$ -linear null operators.

Under this condition $F$ satisfies

F\left(y\right)=F\left(x\right)+F^{\prime}\left(x\right)\left(y-x\right)+% \tfrac{1}{2}F^{\prime\prime}\left(x\right)\left(y-x\right)^{2},\qquad\text{for% all }x,y\in X,

2.1

where, in fact, $F^{\prime\prime}\left(x\right)$ is a constant bilinear operator which does not depend on $x .$

Let $x_{0}\in X$ and $r,K>0$ be two real numbers. Denote $S=\left\{x\in X|\left\|x-x_{0}\right\|\leq r\right\}$ and suppose that we have the estimation

\left\|F^{\prime\prime}\left(x\right)\right\|\leq K,\qquad\text{for all }x\in S.

Concerning the convergence of method $\left(1.2\right),$ the following result holds:

Theorem

If the operator $F$ and the elements $x_{0}\in X$ , $B_{0}\in{\Cal{L}}\left(X\right)$ satisfy:

a) there exists $F^{\prime}\left(x_{0}\right)^{-1}$ and $\|F^{\prime}\left(x_{0}\right)^{-1}\|\leq b_{0}$ for some $b_{0}>0;$

b) $q=Kb_{0}r<1;$

c) $\max\left\{\delta_{0},\rho_{0}\right\}\leq\frac{1}{7}d$ for some $0<d<1$ , where

\rho_{0}=\tfrac{Ka^{2}}{2}\left\|F\left(x_{0}\right)\right\|,\quad\delta_{0}=% \left\|I-F^{\prime}\left(x_{0}\right)B_{0}\right\|,\quad a=\tfrac{64}{49}b% \text{ and}\quad b=\tfrac{b_{0}}{1-q};

d) $\tfrac{16d}{49Ka\left(1-d^{2}\right)}\leq r,$

then the following properties hold:

1) the sequences $\left(x_{k}\right)_{k\geq 0}$ , $\left(B_{k}\right)_{k\geq 0}$ , $\left(C_{k}\right)_{k\geq 0}$ converge and $\left(x_{k}\right)_{k\geq 0}\subset S;$

2) denoting $x^{*}=\lim x_{k},\;B=\lim B_{k},\;C=\lim C_{k}$ , then $F\left(x^{*}\right)=\bar{\theta}$ and $B=C=F^{\prime}\left(x^{*}\right)^{-1};$

3) the following estimations are true:

	$\displaystyle\left\\|x^{*}-x_{k}\right\\|$	$\displaystyle\leq\frac{16\,d^{3^{k}}}{49K\,a\left(1-d^{2\cdot 3^{k}}\right)};$
	$\displaystyle\left\\|B-B_{k}\right\\|$	$\displaystyle\leq\frac{1656\,a\,d^{3^{k}}}{2401\left(1-d^{2\cdot 3^{k}}\right)% },\qquad k=0,1,\dots$

Demonstration Proof

We shall prove firstly that the first order derivative of $F$ is invertible on $S$ . By a) and b) we have

\|I-F^{\prime}\left(x_{0}\right)^{-1}F^{\prime}\left(x\right)\|\leq\|F^{\prime% }\left(x_{0}\right)^{-1}\|\left\|F^{\prime}\left(x_{0}\right)-F^{\prime}\left(% x\right)\right\|\leq b_{0}Kr=q<1,

for all $x\in S$ . It follows that the operator $T\left(x\right)=F^{\prime}\left(x_{0}\right)^{-1}F^{\prime}\left(x\right)$ is invertible on $S$ and $T\left(x\right)^{-1}=F^{\prime}\left(x\right)^{-1}F^{\prime}\left(x_{0}\right),$ whence $F^{\prime}\left(x\right)^{-1}=T\left(x\right)^{-1}F^{\prime}\left(x_{0}\right)% ^{-1}$ and

\|F^{\prime}\left(x\right)^{-1}\|\leq\tfrac{b_{0}}{1-q}=b.

For the norms of $B_{0}$ and $C_{0}$ , taking into account the hypotheses, we get

	$\displaystyle\left\\|B_{0}\right\\|\leq$	$\displaystyle\\|B_{0}-F^{\prime}\left(x_{0}\right)^{-1}\\|+\\|F^{\prime}\left(x_{% 0}\right)^{-1}\\|$
	$\displaystyle\leq$	$\displaystyle\\|F^{\prime}\left(x_{0}\right)^{-1}\\|\left(1+\left\\|I-F^{\prime}% \left(x_{0}\right)B_{0}\right\\|\right)$
	$\displaystyle\leq$	$\displaystyle b_{0}\left(1+\delta_{0}\right)\leq\tfrac{8}{7}b_{0}<\tfrac{8}{7}b$

and

\left\|C_{0}\right\|\leq\left\|B_{0}\right\|+\left\|I-F^{\prime}\left(x_{0}% \right)B_{0}\right\|\cdot\left\|B_{0}\right\|\leq\left\|B_{0}\right\|\left(1+% \delta_{0}\right)\leq\tfrac{64}{49}b=a,

so $\left\|B_{0}\right\|\leq a$ and $\left\|C_{0}\right\|\leq a$ .

From $\left(1.2\right)$ we have

	$\displaystyle\left\\|x_{1}-x_{0}\right\\|\leq$	$\displaystyle a\big(1+\tfrac{Ka^{2}}{2}\left\\|F\left(x_{0}\right)\right\\|\big)% \left\\|F\left(x_{0}\right)\right\\|$
	$\displaystyle\leq$	$\displaystyle a\left(1+\rho_{0}\right)\left\\|F\left(x_{0}\right)\right\\|$
	$\displaystyle<$	$\displaystyle\tfrac{8}{7}a\left\\|F\left(x_{0}\right)\right\\|=\tfrac{2\rho_{0}}% {Ka^{2}}\cdot\tfrac{8}{7}a=\tfrac{16d}{49Ka},$

whence, taking into account d) it follows that $x_{1}\in S$ .

Further, by $\left(1.2\right)$ and $\left(2.1\right)$ ,

	$\displaystyle\left\\|F\left(x_{1}\right)\right\\|\leq$	$\displaystyle\left\\|I-F^{\prime}\left(x_{0}\right)C_{0}\right\\|\big(1+\tfrac{1% }{2}\left\\|F^{\prime\prime}\left(x_{0}\right)\right\\|\left\\|C_{0}\right\\|^{2}% \left\\|F^{\prime}\left(x_{0}\right)\right\\|\big)\left\\|F\left(x_{0}\right)\right\\|$
		$\displaystyle+\tfrac{1}{2}\left\\|F^{\prime\prime}\left(x_{0}\right)\right\\|^{2% }\left\\|C_{0}\right\\|^{4}\left\\|F\left(x_{0}\right)\right\\|^{3}+\tfrac{1}{8}% \left\\|F^{\prime\prime}\left(x_{0}\right)\right\\|^{3}\left\\|C_{0}\right\\|^{6}% \left\\|F\left(x_{0}\right)\right\\|^{4},$

whence

	$\displaystyle\tfrac{Ka^{2}}{2}\left\\|F\left(x_{1}\right)\right\\|\leq$	$\displaystyle\tfrac{Ka^{2}}{2}\left\\|F\left(x_{0}\right)\right\\|\cdot\left\\|I-% F^{\prime}\left(x_{0}\right)C_{0}\right\\|\big(1+\tfrac{Ka^{2}}{2}\left\\|F\left% (x_{0}\right)\right\\|\big)$
		$\displaystyle+2\big(\tfrac{Ka^{2}}{2}\left\\|F\left(x_{0}\right)\right\\|\big)^{% 3}+\big(\tfrac{Ka^{2}}{2}\left\\|F\left(x_{0}\right)\right\\|\big)^{4}.$

Denoting $\rho_{1}=\tfrac{Ka^{2}}{2}\left\|F\left(x_{1}\right)\right\|$ and taking into account the inequality

\left\|I-F^{\prime}\left(x_{0}\right)C_{0}\right\|\leq\left\|I-F^{\prime}\left% (x_{0}\right)B_{0}\right\|^{2}=\delta_{0}^{2}

it follows

\rho_{1}\leq\rho_{0}\delta_{0}^{2}+\rho_{0}^{2}\delta_{0}^{2}+2\rho_{0}^{3}+% \rho_{0}^{4}.

2.2

From the third relation of $\left(1.2\right)$ we get

	$\displaystyle\left\\|I-F^{\prime}\left(x_{1}\right)B_{1}\right\\|=$	$\displaystyle\big\\|\left(I-F^{\prime}\left(x_{1}\right)B_{0}\right)^{3}\big\\|$
	$\displaystyle\leq$	$\displaystyle\left\\|I-F^{\prime}\left(x_{1}\right)B_{0}\right\\|^{3}\leq$
	$\displaystyle\leq$	$\displaystyle\big(\left\\|I-F^{\prime}\left(x_{0}\right)B_{0}\right\\|+\left\\|B_% {0}\right\\|K\left\\|x_{1}-x_{0}\right\\|\big)^{3}$
	$\displaystyle\leq$	$\displaystyle\left(\delta_{0}+2\rho_{0}+2\rho_{0}^{2}\right)^{3},$

i.e.,

\delta_{1}\leq\left(\delta_{0}+2\rho_{0}+2\rho_{0}^{2}\right)^{3}.

2.3

By $\left(2.2\right),\left(2.3\right)$ and hypothesis b), we obtain

\begin{matrix}\rho_{1}&\leq&\tfrac{1}{7}d^{3}\\ \delta_{1}&\leq&\tfrac{1}{7}d^{3}.\end{matrix}

Suppose now that the following properties hold:

$\lx@ams@boldsymbol@{\alpha}$ $\boldkey{)}$ $x_{0},x_{1},...,x_{k}\in S;$

$\lx@ams@boldsymbol@{\beta}\boldkey{)}$ $\rho_{i}:=\tfrac{Ka^{2}}{2}\left\|F\left(x_{i}\right)\right\|\leq\tfrac{1}{7}d% ^{3^{i}}$ and $\delta_{i}:=\left\|I-F^{\prime}\left(x_{i}\right)B_{i}\right\|\leq\tfrac{1}{7}% d^{3^{i}},\;i=\overline{0,k}.$

It easily follows that $\left\|B_{k}\right\|\leq a$ , $\left\|C_{k}\right\|\leq a$ and

$\displaystyle\left\\|x_{k+1}-x_{k}\right\\|\leq$	$\displaystyle a\big(1+\tfrac{Ka^{2}}{2}\left\\|F\left(x_{k}\right)\right\\|\big)% \left\\|F\left(x_{k}\right)\right\\|$	$2.4$
$\displaystyle\leq$	$\displaystyle a\left(1+\rho_{k}\right)\left\\|F\left(x_{k}\right)\right\\|$
$\displaystyle\leq$	$\displaystyle\tfrac{16\rho_{k}}{7Ka}\leq\tfrac{16d^{3}}{49Ka}.$

From the above formula it follows that $x_{k+1}\in S$ :

\left\|x_{k+1}-x_{0}\right\|\leq\tfrac{16d}{49Ka}\sum\limits_{i=0}^{k}d^{3^{i}% -1}\leq\tfrac{16d}{49Ka\left(1-d^{2}\right)}\leq r.

Denoting $\rho_{k+1}=\frac{Ka^{2}}{2}\left\|F\left(x_{k+1}\right)\right\|$ and $\delta_{k+1}=\left\|I-F^{\prime}\left(x_{k+1}\right)B_{k+1}\right\|$ , the following relations are obtained in the same manner as for $\rho_{1}$ and $\delta_{1}$ :

	$\displaystyle\rho_{k+1}$	$\displaystyle\leq\rho_{k}\delta_{k}^{2}+\rho_{k}^{2}\delta_{k}^{2}+2\rho_{k}^{% 3}+\rho_{k}^{4}$
	$\displaystyle\delta_{k+1}$	$\displaystyle\leq\left(\delta_{k}+2\rho_{k}+2\rho_{k}^{2}\right)^{3},$

whence, by the Lemma, we get

\begin{gathered}\rho_{k+1}\leq\tfrac{1}{7}d^{3^{k+1}}\\ \delta_{k+1}\leq\tfrac{1}{7}d^{3^{k+1}}.\end{gathered}

2.5

Then properties $\lx@ams@boldsymbol@{\alpha}\boldkey{)}$ , $\lx@ams@boldsymbol@{\beta}\boldkey{)},$ $\left(2.4\right)$ and $\left(2.5\right)$ hold for all $k\in{\mathbb{N}}.$ We shall prove now that $\left(x_{k}\right)_{k\geq 0}$ is a Cauchy sequence.

Indeed,

\left\|x_{k+s}-x_{k}\right\|\leq\tfrac{16d^{3^{k}}}{49Ka}\;\sum\limits_{i=k}^{% k+s-1}d^{3^{s}-3^{k}}\leq\tfrac{16d^{3^{k}}}{49Ka\left(1-d^{2\cdot 3^{k}}% \right)},

for all $s,k\in{\mathbb{N}}$ , which proves that $\left(x_{k}\right)_{k\geq 0}$ converges. Denoting $x^{*}=\lim\limits_{k\rightarrow\infty}x_{k}$ and passing to limit for $s\rightarrow\infty$ in the above inequality, we obtain

\left\|x^{*}-x_{k}\right\|\leq\tfrac{16d^{3^{k}}}{49Ka\left(1-d^{2\cdot 3^{k}}% \right)},\quad k=0,1,\dots

The convergence of $\left(B_{k}\right)_{k\geq 0}$ is obtained from the third relation of $\left(1.2\right)$ :

	$\displaystyle\left\\|B_{k+1}-B_{k}\right\\|\leq$	$\displaystyle\left\\|B_{k}\right\\|\cdot\left\\|2I-F^{\prime}\left(x_{k+1}\right)% B_{k}\right\\|\cdot\left\\|I-F^{\prime}\left(x_{k+1}\right)B_{k}\right\\|$
	$\displaystyle\leq$	$\displaystyle a\left(1+\delta_{k}+2\rho_{k}+2\rho_{k}^{2}\right)\left(\rho_{k}% +2\rho_{k}+2\rho_{k}^{2}\right)\leq a\tfrac{1656}{2401}d^{3^{k}}.$

Denoting $B=\lim B_{k}$ it easily follows that

\left\|B-B_{k}\right\|\leq\tfrac{1656ad^{3^{k}}}{2401\left(1-d^{2\cdot 3^{k}}% \right)},\quad k=0,1,\dots\qquad\qed

Remark. The inequalities from the hypothesis of the Lemma can be replaced by $\delta_{0}\leq\alpha d,\;\rho_{0}\leq\beta d$ for $0<d<1$ and $\alpha,\beta>0$ satisfying $\left(\alpha+2\beta+2\beta^{2}d\right)^{3}\leq\alpha$ and $\beta\alpha^{2}+\beta^{2}\alpha^{2}+2\beta^{3}+\beta^{4}d\leq\beta.$

We shall obviously obtain in the conclusion that $\delta_{k}\leq\alpha d^{3^{k}},\;\rho_{k}\leq\beta d^{3^{k}},\;k=0,1,...\,.$ The theorem can be reformulated then accordingly. ∎

3. The eigenproblem for linear continuous operators

3.1. The infinite dimensional case

Let $V$ be a Banach space over the field ${\mathbb{K}}$ (where ${\mathbb{K}}={\mathbb{C}}$ or ${\mathbb{K}}={\mathbb{R}}$ ) and $A:V\rightarrow V$ a linear continuous operator. The scalar $\lambda\in{\mathbb{K}}$ is an eigenvalue of $A$ iff the equation

Av-\lambda v=\theta

3.1

has at least a solution $v^{*}\neq\theta$ , called an eigenvector of $A$ corresponding to $\lambda$ , where $\theta$ is the null element of $V$ .

For the simultaneous determination of a $v^{*}$ and a $\lambda$ we attach to equation (3.1) another equation

G\left(v\right)=1,

3.2

where $G:V\rightarrow{\mathbb{K}}$ is a polynomial functional of degree two for which $G\left(0\right)\neq 1$ (a norming function).

Remark. The functional $G$ may also be taken as a polynomial functional of degree one, i.e. a linear continuous functional, but then $\dim\operatorname{Ker}G=\dim V-\dim\operatorname{Im}G=n-1,$ for the finite dimensional case, and $\dim\operatorname{Ker}G=\infty$ otherwise. So, there exist eigenvectors which do not fulfill equation (3.2). ∎

Denote the Banach space $X=V\times{\mathbb{K}}$ and for $x=\binom{v}{\lambda}$ , with $v\in V$ and $\lambda\in{\mathbb{K}}$ , define

\left\|x\right\|=\max\left\{\left\|v\right\|,\left|\lambda\right|\right\}.

Considering the operator $F:X\rightarrow X$ given by

F\left(x\right)=\left(\begin{matrix}Av-\lambda v\\ G\left(v\right)-1\end{matrix}\right)=\left(\begin{matrix}\left(A-\lambda I% \right)v\\ G\left(v\right)-1\end{matrix}\right),

and denoting by $\bar{\theta}=\binom{\theta}{0}$ the null element of $X$ , then the operatorial equation for which the solution yields an eigenvalue and an eigenvector of $A$ is

F\left(x\right)=\bar{\theta}.

3.3

It is known that the Fréchet derivatives of $F$ are (see [4]):

	$\displaystyle F^{\prime}\left(x_{0}\right)h_{1}=$	$\displaystyle\left(\begin{matrix}A-\lambda_{0}I&-v_{0}\\ G^{\prime}\left(v_{0}\right)&0\end{matrix}\right)\left(\begin{matrix}u_{1}\\ \alpha_{1}\end{matrix}\right)=\left(\begin{matrix}Au_{1}-\lambda_{0}u_{1}-% \alpha_{1}v_{0}\\ G^{\prime}\left(v_{0}\right)u_{1}\end{matrix}\right),$
	$\displaystyle F^{\prime\prime}\left(x_{0}\right)h_{1}h_{2}=$	$\displaystyle\left(\begin{matrix}-\alpha_{1}u_{2}-\alpha_{2}u_{1}\\ G^{\prime\prime}\left(v_{0}\right)u_{1}u_{2}\end{matrix}\right),$

where $x_{0}=\binom{v_{0}}{\lambda_{0}},$ $h_{1}=\binom{u_{1}}{\alpha_{1}},\,h_{2}=\binom{u_{2}}{\alpha_{2}}$ with $v_{0},$ $u_{1},u_{2}\in V$ and $\lambda_{0},\alpha_{1},\alpha_{2}\in{\mathbb{K}}$ .

It is obvious that $F^{\left(i\right)}\left(x_{0}\right)h_{1}...h_{i}=\bar{\theta},$ for all $i\geq 3$ and $x_{0}$ , $h_{1},...,h_{i}\in X.$

Our theorem can be applied for this function $F$ and we can take $K=\max\left\{2,\left\|G^{\prime\prime}\right\|\right\}.$

3.2. The eigenproblem for complex matrices

In the following we shall apply the studied method for the approximation of the eigenvalues and eigenvectors of complex matrices.

Let $A=\left(a_{ij}\right)_{i,j=1,n}\in{\Cal{M}}_{n}\left({\mathbb{K}}\right)$ be a square matrix with the elements $a_{ij}\in{\mathbb{K}}.$ Consider $V={\mathbb{K}}^{n}$ and $X=V\times{\mathbb{K}}={\mathbb{K}}^{n+1}.$ In this case the equation (3.3) is written

F_{i}\left(x\right)=F_{i}\big(x^{\left(1\right)},...,x^{\left(n+1\right)}\big)% =0,\qquad i=\overline{1,n+1},

where for $i=\overline{1,n}$ we have

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

and for the norming function $G$ we can take

F_{n+1}\big(x^{\left(1\right)},...,x^{\left(n+1\right)}\big)=\tfrac{1}{2}\sum_% {i=1}^{n}\big(x^{\left(i\right)}\big)^{2}-1.

3.4

A solution $x^{*}$ of equation $F\left(x\right)=\bar{\theta}$ yields an eigenvalue $\lambda=x_{*}^{\left(n+1\right)}$ and a corresponding eigenvector $v^{*}=\big(x_{*}^{\left(1\right)},...,x_{*}^{\left(n\right)}\big)$ of the matrix $A$ .

The first and second order derivatives of $F$ are given by

F^{\prime}\left(x\right)h=\left(\begin{matrix}a_{11}-x^{\left(n+1\right)}&a_{1% 2}&...&a_{1n}&-x^{\left(1\right)}\\ a_{21}&a_{22}-x^{\left(n+1\right)}&...&a_{2n}&-x^{\left(2\right)}\\ \vdots&\vdots&&\vdots&\vdots\\ a_{n1}&a_{n2}&...&a_{nn}-x^{\left(n+1\right)}&-x^{\left(n\right)}\\ x^{\left(1\right)}&x^{\left(2\right)}&...&x^{\left(n\right)}&0\end{matrix}% \right)\left(\begin{matrix}h^{\left(1\right)}\\ h^{\left(2\right)}\\ \vdots\\ h^{\left(n\right)}\\ h^{\left(n+1\right)}\end{matrix}\right),

and

F^{\prime\prime}\left(x\right)hk=\left(\begin{matrix}-k^{\left(n+1\right)}&0&.% ..&0&-k^{\left(1\right)}\\ 0&-k^{\left(n+1\right)}&...&0&-k^{\left(2\right)}\\ \vdots&\vdots&&\vdots&\vdots\\ 0&0&...&-k^{\left(n+1\right)}&-k^{\left(n\right)}\\ k^{(1)}&k^{(2)}&...&k^{(n)}&0\end{matrix}\right)\left(\begin{matrix}h^{\left(1% \right)}\\ h^{\left(2\right)}\\ \vdots\\ h^{\left(n\right)}\\ h^{\left(n+1\right)}\end{matrix}\right).

3.5

where $x=\left(x^{\left(1\right)},...,x^{\left(n+1\right)}\right),\,h=\left(h^{\left(% 1\right)},...,h^{\left(n+1\right)}\right),\,k=\left(k^{\left(1\right)},...,k^{% \left(n+1\right)}\right)\in{\mathbb{K}}^{n+1}.$

Suppose that ${\mathbb{K}}^{n+1}$ is equipped with the norm

\left\|x\right\|=\max_{1\leq i\leq n+1}\big|x^{\left(i\right)}\big|,\qquad x=% \big(x^{\left(1\right)},...,x^{\left(n+1\right)}\big)\in{\mathbb{K}}^{n+1}.

Then, from (3.5) it follows that we can take $K=\left\|F^{\prime\prime}\right\|=n.$ Our theorem can be stated accordingly.

Another possible choice for the definition of $F_{n+1},$ is:

F_{n+1}\big(x^{\left(1\right)},...,x^{\left(n+1\right)}\big)=\tfrac{1}{2n}\sum% _{i=1}^{n}\big(x^{\left(i\right)}\big)^{2}-1,

3.6

in which case we can take $K=\left\|F^{\prime\prime}\right\|=2$ . In this case $K$ does not depend on $n$ .

Remark. In [15] it is proved the following result. If $(v,\lambda)$ is an eigenpair then $F^{\prime}(v,\lambda)$ is nonsingular iff $\lambda$ is simple. Hence our results apply only for simple eigenvalues.

4. Numerical examples

Consider

A=\left(\begin{matrix}1&1&1&1\\ 1&1&-1&-1\\ 1&-1&1&-1\\ 1&-1&-1&1\end{matrix}\right),

having the eigenvalues and the corresponding eigenvectors $\lambda_{1,2,3}=2,$ $v_{1}=\left(1,0,0,1\right),$ $v_{2}=\left(1,0,1,0\right),$ $v_{3}=\left(1,1,0,0\right)$ , $\lambda_{4}=-2,$ $v_{4}=\left(-1,1,1,1\right).$

Taking $x_{0}=\left(-1,3,1,3,-1.5\right),$ $B_{0}=F^{\prime}\left(x_{0}\right)^{-1}$ and using formula (3.4) for $F_{n+1}$ we get:

\begin{matrix}k&x_{k}^{\left(1\right)}&x_{k}^{\left(2\right)}&x_{k}^{\left(3% \right)}&x_{k}^{\left(4\right)}&x_{k}^{\left(5\right)}\\ 0&-0.3000000000&1.000000000&0.3000000000&1.000000000&-1.700000000\\ 1&-0.6344924627&0.6757048140&0.6344924627&0.6757048140&-1.901115297\\ 2&-0.7066264375&0.7068982234&0.7066264375&0.7068982234&-1.998773347\\ 3&-0.7071067705&0.7071067768&0.7071067705&0.7071067768&-1.999999976\\ 4&-0.7071067812&0.7071067812&0.7071067812&0.7071067812&-2.000000000\\ \end{matrix}

Using formula (3.6) for $F_{n+1}$ and taking $x_{0}=\left(-1,1.8,1,1.8,-1.6\right),\ B_{0}=F^{\prime}\left(x_{0}\right)^{-1},$ we obtain

\begin{matrix}k&x_{k}^{\left(1\right)}&x_{k}^{\left(2\right)}&x_{k}^{\left(3% \right)}&x_{k}^{\left(4\right)}&x_{k}^{\left(5\right)}\\ 0&-1.000000000&1.800000000&1.000000000&1.800000000&-1.600000000\\ 1&-1.382930642&1.405515579&1.382930642&1.405515579&-1.972622248\\ 2&-1.414185197&1.414209835&1.414185197&1.414209835&-1.999975824\\ 3&-1.414213562&1.414213562&1.414213562&1.414213562&-2.000000000\\ \end{matrix}

References

1 ANSELONE, M. P., RALL, B. L., The solution of characteristic value-vector problems by Newton method, Numer. Math. 11 (1968), 38–45.
2 CIARLET, P.G., Introduction à l’analyse numérique matricielle et à l’optimisation, Mason, 1990.
3 CHATELIN, F., Valeurs propres de matrices, Mason, 1988.
4 COLLATZ, L., Functionalanalysis und Numerische Mathematik, Springer-Verlag, 1964.
5 DIACONU, A, PĂVĂLOIU, I., Sur quelques méthodes iteratives pour la résolution des equations operationelles, Rev. Anal. Numér. Théor. Approx. 1 (1972), no. 1, 45–61.
6 DIACONU, A., Sur quelques méthods itératives combinées, Mathematica 22 (45) (1980), no. 2, 247–261.
7 DIACONU, A., On the convergence of an iterative proceeding of Chebyshev type, Rev. Anal. Numér. Théor. Approx. 24 (1995), no. 1-2, 91–102.
8 KARTÎŞOV, V. S., IUHNO, F. L., O nekotorîh Modifikaţiah Metoda Niutona dlea Resenia Nelineinoi Spektralnoi Zadaci, J. Vîcisl. matem. i matem. fiz. 33 (1973), no. 9, 1403–1409.
9 ORTEGA, J.M., RHEINBOLDT, W.C., Iterative Solutions of Nonlinear Equations in Several Variables, Academic Press, 1970.
10 PĂVĂLOIU, I., Sur les procédés itératifs à un ordre élevé de convergence, Mathematica (Cluj) 12 (35) (1970), no. 2, 309–324.
11 PETERS, G., WILKINSON, J.H., Inverse iteration, ill-conditioned equations and Newton’s method, SIAM Review 21 (1979), no. 3, 339–360.
12 SANTOS, C.M., A note on the Newton iteration for the algebraic eigenvalue problem, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 561–569.
13 TRAUB, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall Inc., 1964.
14 ULM, S., Ob iterationnyh metodah s’posledovatel’noi approximacii obratnovo operatora, Izv. Acad. Nauk Estonskoi SSR 16 (1967), no. 4, 403–411.
15 YAMAMOTO, T., Error bounds for computed eigenvalues and eigenvectors, Numer. Math. 34 (1980), 189–199.

	$\displaystyle\left\\|x_{1}-x_{0}\right\\|\leq$	$\displaystyle a\big(1+\tfrac{Ka^{2}}{2}\left\\|F\left(x_{0}\right)\right\\|\big)% \left\\|F\left(x_{0}\right)\right\\|$
	$\displaystyle\leq$	$\displaystyle a\left(1+\rho_{0}\right)\left\\|F\left(x_{0}\right)\right\\|$
	$\displaystyle<$	$\displaystyle\tfrac{8}{7}a\left\\|F\left(x_{0}\right)\right\\|=\tfrac{2\rho_{0}}% {Ka^{2}}\cdot\tfrac{8}{7}a=\tfrac{16d}{49Ka},$

On a Chebyshev-type method for approximating the solutions of polynomial operator equations of degree 2

Abstract

Authors

Keywords

Paper coordinates

PDF

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

1. Introduction

2. The convergence of the method

Lemma

Theorem

Demonstration Proof

3. The eigenproblem for linear continuous operators

3.1. The infinite dimensional case

3.2. The eigenproblem for complex matrices

4. Numerical examples

References

Related Posts