<!DOCTYPE html>
<html lang="en">
<head>
<script>
  MathJax = { 
    tex: {
		    inlineMath: [['\\(','\\)']]
	} }
</script>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js">
</script>
<meta name="generator" content="plasTeX" />
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>On the convergence of some quasi-Newton iterates <br />studied by I. Păvăloiu: On the convergence of some quasi-Newton iterates <br />studied by I. Păvăloiu</title>
<link rel="stylesheet" href="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/styles/theme-white.css" />
</head>

<body>

<div class="wrapper">

<div class="content">
<div class="content-wrapper">


<div class="main-text">


<div class="titlepage">
<h1>On the convergence of some quasi-Newton iterates <br />studied by I. Păvăloiu</h1>
<p class="authors">
<span class="author">Emil Cătinaş\(^\ast \)</span>
</p>
<p class="date">October 3, 2015.</p>
</div>
<p>\(^\ast \)“T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68-1, Cluj-Napoca, Romania, e-mail: <span class="ttfamily">ecatinas@ictp.acad.ro</span>. </p>
<p>Dedicated to prof. I. Păvăloiu on the occasion of his 75th anniversary </p>

<div class="abstract"><p> I. Păvăloiu has considered a Banach space \(X\) and the problem </p>
<div class="displaymath" id="a0000000002">
  \begin{equation*}  x=\lambda D\left( x\right) +y \qquad (D:X\rightarrow X,\  \lambda \in {\mathbb R}, \  y \in X \  {\rm given}) \label{f.1}\end{equation*}
</div>
<p> written in the equivalent form \(F(x):=x -\lambda D\left( x\right) -y=0\) and solved by the general quasi-Newton method </p>
<div class="displaymath" id="a0000000003">
  \begin{equation*}  x_{k+1}=x_{k}-A\left( x_{k}\right) \left[ x_{k}-\lambda D\left( x_{k}\right) -y\right] ,\qquad k=0,1,\ldots \end{equation*}
</div>
<p>Semilocal convergence results were obtained, ensuring linear convergence of this method. Further results were obtained for the iterates: </p>
<div class="displaymath" id="a0000000004">
  \[  x_{k+1}=x_{k}-[I+\lambda D^\prime \left( x_{k}\right)] \left[ x_{k}-\lambda D\left( x_{k}\right) -y\right] ,\qquad k=0,1,\ldots  \]
</div>
<p>In this note, we analyze the local convergence of these iterates, and, using the Ostrowski local attraction theorem, we give some sufficient conditions such that the iterates converge locally either linearly or with higher convergence orders. The local convergence results require fewer differentiability assumptions for \(D\). </p>
<p><b class="bf">MSC.</b> 65H10. </p>
<p><b class="bf">Keywords.</b> quasi-Newton methods, Ostrowski local attraction theorem, local convergence. </p>
</div>
<h1 id="a0000000005">1 Introduction</h1>
<p>In <span class="cite">
	[
	<a href="#Pavaloiu 1986" >6</a>
	]
</span>, Păvăloiu has considered a Banach space \((X,\| \cdot \| )\), a nonlinear mapping \(D:X\rightarrow X\), a parameter \(\lambda \in {\mathbb R}\), an element \(y \in X\) and the equation (arising from certain integral equations) </p>
<div class="equation" id="f.1 eq x=lam D(x)+y">
<p>
  <div class="equation_content">
    \begin{equation}  x=\lambda D\left( x\right) +y, \label{f.1 eq x=lam D(x)+y}\end{equation}
  </div>
  <span class="equation_label">1</span>
</p>
</div>
<p> solved by the following iterations: </p>
<div class="equation" id="f.2 xn+1=xn-An(xn-lam D(xn)-y)">
<p>
  <div class="equation_content">
    \begin{equation}  x_{k+1}=x_{k}-A\left( x_{k}\right) \left[ x_{k}-\lambda D\left( x_{k}\right) -y\right] ,\qquad k=0,1,\ldots ,x_{0}\in E\subseteq X, \label{f.2 xn+1=xn-An(xn-lam D(xn)-y)}\end{equation}
  </div>
  <span class="equation_label">2</span>
</p>
</div>
<p> where \(A(x) :E\rightarrow E\) is a linear continuous mapping (<i class="it">i.e.</i>, \(A(x)\in {\mathcal L}(X)\)), for each \(x\in E\). </p>
<p>Denoting </p>
<div class="equation" id="f F(x)=x-lam D(x)+y">
<p>
  <div class="equation_content">
    \begin{equation}  \label{f F(x)=x-lam D(x)+y} F(x)=x-\lambda D(x) - y, \end{equation}
  </div>
  <span class="equation_label">3</span>
</p>
</div>
<p> the above iterations can be written as </p>
<div class="displaymath" id="a0000000006">
  \[  x_{k+1}=x_{k}-A\left( x_{k}\right) F(x_{k}) ,\qquad k=0,1,\ldots ;  \]
</div>
<p> in a subsequent paper, Păvăloiu <span class="cite">
	[
	<a href="#Pavaloiu 2009" >7</a>
	]
</span> has analyzed the above iterations for general mappings \(F\), not necessarily given by (<a href="#f F(x)=x-lam D(x)+y">3</a>). </p>
<p>The following semilocal convergence results were obtained. </p>
<p><div class="theorem_thmwrapper " id="Theoreme 1.">
  <div class="theorem_thmheading">
    <span class="theorem_thmcaption">
    Theorem
    </span>
    <span class="theorem_thmlabel">1</span>
  </div>
  <div class="theorem_thmcontent">
  <p><span class="cite">
	[
	<a href="#Pavaloiu 1986" >6</a>
	]
</span>  If the mappings \(D\) and \(A\left( x\right) ,\) the initial approximation \(x_{0}\) and the real number \(r{\gt}0\) satisfy the following conditions: </p>
<ul class="itemize">
  <li><p>the mapping \(D\) admits Fréchet derivatives of order one and two on the ball \(S=S\left( x_{0},r\right) ;\) </p>
</li>
  <li><p>\(\left\Vert A\left( x\right) \right\Vert \leq \beta ,\) for each \(x\in S,\) and some \(\beta {\gt}0;\) </p>
</li>
  <li><p>\(\left\Vert I-F^{\prime }\left( x\right) A\left( x\right) \right\Vert \leq \alpha ,\) for each \(x\in S ,\) and some \(\alpha {\gt}0;\) </p>
</li>
  <li><p>\(\left\Vert D^{\prime \prime }\left( x\right) \right\Vert \leq M/\left\vert \lambda \right\vert ,\) for each \(x\in S ,\) and some \(M{\gt}0;\) </p>
</li>
  <li><p>\(\frac{\beta \rho _{0}}{1-d_{0}} \leq r,\) where \(\rho _{0}=\left\Vert F\left( x_{0}\right) \right\Vert ,\  d_{0}=\frac{M\beta ^{2}\rho _{0}}{2}+\alpha ;\) </p>
</li>
  <li><p>\(d_{0}{\lt}1,\) </p>
</li>
</ul>
<p> then the sequence \(\left( x_{k}\right) _{k\geq 0}\) given by <span class="rm">(<a href="#f.2 xn+1=xn-An(xn-lam D(xn)-y)">2</a>)</span> converges: \(x^\ast =\lim _{k\rightarrow \infty }x_{k},\) with \(F\left( x^\ast \right) =0\). The following estimations hold:</p>
<div class="displaymath" id="a0000000007">
  \begin{equation*}  \left\Vert x^\ast -x_{k}\right\Vert \leq \frac{\beta d_{0}^{k}\rho _{0}}{1-d_{0}},\qquad k=0,1,\ldots \label{f.3}\end{equation*}
</div>

  </div>
</div> </p>
<p>When \(\| \lambda D^\prime (x)\| {\lt}1\), it is known that the operator \(I-\lambda D^\prime \left( x\right) \) is invertible, with \(\big(I-\lambda D^\prime (x) \big)^{-1}= I+\lambda D^\prime (x) + \lambda ^2 D^\prime (x)^2 + \ldots \) Păvăloiu has considered the operator \(A(x)\) as being given by the first two terms of this expansion, obtaining the following iterates </p>
<div class="equation" id="f. xn+1=xn-(I+D'xn)(xn-lam D(xn)-y)">
<p>
  <div class="equation_content">
    \begin{equation}  x_{k+1}=x_{k}-\big(I+\lambda D^\prime (x_{k}) \big) \left[ x_{k}-\lambda D\left( x_{k}\right) -y\right] ,\qquad k=0,1,\ldots , \label{f. xn+1=xn-(I+D'xn)(xn-lam D(xn)-y)}\end{equation}
  </div>
  <span class="equation_label">4</span>
</p>
</div>
<p> and the following result. </p>
<p><div class="theorem_thmwrapper " id="Theorem 2.">
  <div class="theorem_thmheading">
    <span class="theorem_thmcaption">
    Theorem
    </span>
    <span class="theorem_thmlabel">2</span>
  </div>
  <div class="theorem_thmcontent">
  <p><span class="cite">
	[
	<a href="#Pavaloiu 1986" >6</a>
	]
</span>  If the mapping \(D,\) the initial approximation \(x_{0}\) and the real number \(r{\gt}0\) satisfy the following assumptions: </p>
<ul class="itemize">
  <li><p>the mapping \(D\) admits Fréchet derivatives of order one and two for each \(x\in S=S\left( x_{0},r\right) ;\) </p>
</li>
  <li><p>\(\left\Vert D^{\prime }\left( x\right) \right\Vert \leq b,\) for each \(x\in S;\) </p>
</li>
  <li><p>\(\left\Vert D^{\prime \prime }\left( x\right) \right\Vert \leq M/\left\vert \lambda \right\vert ,\) for each \(x\in S;\) </p>
</li>
  <li><p>\(2-M\rho _{0}{\gt}0,\) where \(\rho _{0}=\left\Vert x_{0}-\lambda D\left( x_{0}\right) -y\right\Vert ;\) </p>
</li>
  <li><p>\( \tfrac {\rho _{0}\left( 1+\left\vert \lambda \right\vert b\right) }{1-d_{0}}\leq r ,\) where \(d_{0}=M\tfrac {(1+\left\vert \lambda \right\vert b)^{2}}{2} \rho _{0} +\lambda ^{2} b^{2}; \) </p>
</li>
  <li><p>\(\left\vert \lambda \right\vert \leq \displaystyle \tfrac { 2-M\rho _{0}}{ b( 2+M\rho _{0})} ,\) </p>
</li>
</ul>
<p> then the sequence given by <span class="rm">(<a href="#f. xn+1=xn-(I+D'xn)(xn-lam D(xn)-y)">4</a>)</span> converges to a solution \(x^\ast \) of equation <span class="rm">(<a href="#f.1 eq x=lam D(x)+y">1</a>)</span> and the following estimates hold:</p>
<div class="displaymath" id="a0000000008">
  \[  \left\Vert x^\ast -x_{k}\right\Vert \leq \frac{\left( 1+\left\vert \lambda \right\vert b\right) d_{0}^{k}\rho _{0}}{1-d_{0}},\qquad k=0,1,\ldots  \]
</div>

  </div>
</div> </p>
<p><div class="remark_thmwrapper " id="rem 1">
  <div class="remark_thmheading">
    <span class="remark_thmcaption">
    Remark
    </span>
    <span class="remark_thmlabel">3</span>
  </div>
  <div class="remark_thmcontent">
  <p> We note that the assumptions of the above results require the existence of the second derivative of \(D\), and also that the smaller \(d_0\) (<i class="it">i.e.</i>, the smaller \(|\lambda |, b, M\) and \(\rho _0\)), the faster is the convergence of sequence (<a href="#f. xn+1=xn-(I+D'xn)(xn-lam D(xn)-y)">4</a>). <span class="qed">â–¡</span></p>

  </div>
</div> </p>
<h1 id="a0000000009">2 Local convergence</h1>
<p>In order to analyze the local convergence of the considered iterates, we shall use the Ostrowski local attraction theorem, which offers sharp general conditions ensuring the local convergence. We shall consider for simplicity that \(X={\mathbb R}^n\), with \(\|  \cdot \| \) an arbitrary given norm, though the results hold in Banach spaces (see, e.g., <span class="cite">
	[
	<a href="#OR70" >5</a>
	, 
	NR 10.1-3.
	]
</span>). </p>
<p><div class="theorem_thmwrapper " id="Th. Ostrowski">
  <div class="theorem_thmheading">
    <span class="theorem_thmcaption">
    Theorem
    </span>
    <span class="theorem_thmlabel">4</span>
    <span class="theorem_thmtitle">Ostrowski local attraction theorem</span>
  </div>
  <div class="theorem_thmcontent">
  <p><span class="cite">
	[
	<a href="#OR70" >5</a>
	, 
	Th. 10.1.3
	]
</span>  Suppose that \(G:\Omega \subset {\mathbb R}^n \rightarrow {\mathbb R}^n\) has a fixed point \(x^\ast \in \operatorname {int}(\Omega )\) and is differentiable at \(x^\ast \). If the spectral radius of \(G^\prime (x^\ast )\) satisfies </p>
<div class="displaymath" id="a0000000010">
  \[  \rho (G^\prime (x^\ast ))=\sigma {\lt}1,  \]
</div>
<p> then \(x^\ast \) is a point of attraction of the successive approximations \(x_{k+1}=G(x_k),\) \(k\geq 0,\) i.e., there exists an open neighborhood \(V\subseteq \Omega \) of \(x^\ast \) such that \(\forall x_0 \in V\), the successive approximations given above all lie in \(\Omega \) and converge to \(x^\ast \). </p>

  </div>
</div> </p>
<p><div class="remark_thmwrapper " id="Rem.1">
  <div class="remark_thmheading">
    <span class="remark_thmcaption">
    Remark
    </span>
    <span class="remark_thmlabel">5</span>
  </div>
  <div class="remark_thmcontent">
  <p> The classical book of Ortega and Rheinboldt also contains completions to this result (see <span class="cite">
	[
	<a href="#OR70" >5</a>
	, 
	Ch. 10
	]
</span>), in the sense that the spectral radius \(\sigma \) yields the “worst” (\(r\)-)convergence factor among the sequences converging to the fixed point: when \(\sigma \neq 0\), the convergence of the (whole) process is not faster than linear (though, theoretically, there may exist sequences converging at least \(r\)-superlinearly), while when \(\sigma = 0\), all the sequences converge at least \(r\)-superlinearly. This result was refined by us in <span class="cite">
	[
	<a href="#Catinas 2002" >1</a>
	]
</span>, where we have shown that \(x_k \rightarrow x^\ast \) \(q\)-superlinearly iff \(G^\prime (x^\ast )\) has a zero eigenvalue and, starting from a certain step, \(x^\ast - x_k\) are corresponding eigenvectors. This implies that no \(q\)-superlinear convergence may occur when \(G^\prime (x^\ast )\) has no zero eigenvalue. <span class="qed">â–¡</span></p>

  </div>
</div> </p>
<p>The above result can be applied to method (<a href="#f.2 xn+1=xn-An(xn-lam D(xn)-y)">2</a>) if we notice that the derivative of \(x-A(x)F(x)\) has a simple form at the fixed point \(x^\ast \), the following auxiliary result being similar to (Lemma) 10.2.1 in <span class="cite">
	[
	<a href="#OR70" >5</a>
	]
</span>. </p>
<p><div class="lemma_thmwrapper " id="lem 1">
  <div class="lemma_thmheading">
    <span class="lemma_thmcaption">
    Lemma
    </span>
    <span class="lemma_thmlabel">6</span>
  </div>
  <div class="lemma_thmcontent">
  <p> Suppose that \(F:\Omega \subset {\mathbb R}^n \rightarrow {\mathbb R}^n\) is differentiable at a point \(x^\ast \in \operatorname {int}(\Omega )\) for which \(F(x^\ast )=0\). Let \(A:\Omega _0 \rightarrow {\mathcal L}({\mathbb R}^n)\) be defined on an open neighborhood \(\Omega _0 \subseteq \Omega \) of \(x^\ast \) and continuous at \(x^\ast \). Then the mapping \(G:S\rightarrow {\mathbb R}^n,\) </p>
<div class="displaymath" id="a0000000011">
  \[  G(x)=x-A(x)F(x)  \]
</div>
<p> is differentiable at \(x^\ast \) and </p>
<div class="displaymath" id="a0000000012">
  \[  G^\prime (x^\ast )=I-A(x^\ast )F^\prime (x^\ast ).  \]
</div>

  </div>
</div> </p>
<p><div class="proof_wrapper" id="a0000000013">
  <div class="proof_heading">
    <span class="proof_caption">
    Proof
    </span>
    <span class="expand-proof">â–¼</span>
  </div>
  <div class="proof_content">
  
  </div>
</div>The proof is elementary: </p>
<div class="displaymath" id="a0000000014">
  \begin{align*} & \| G(x)-G(x^\ast ) - [I-A(x^\ast )F^\prime (x^\ast )](x-x^\ast )\| = \\ & =\| (A(x)-A(x^\ast ))F(x) + A(x^\ast )[F(x)-F(x^\ast )-F^\prime (x^\ast )(x-x^\ast )]\|  \\ & =o(\| x-x^\ast \| ), \qquad {\rm as\  } x \rightarrow x^\ast . \end{align*}
</div>
<p>Now we can state the main results of this note. First, consider iterations (<a href="#f.2 xn+1=xn-An(xn-lam D(xn)-y)">2</a>). </p>
<p><div class="theorem_thmwrapper " id="a0000000015">
  <div class="theorem_thmheading">
    <span class="theorem_thmcaption">
    Theorem
    </span>
    <span class="theorem_thmlabel">7</span>
  </div>
  <div class="theorem_thmcontent">
  <p>Let \(D:{\mathbb R}^n\rightarrow {\mathbb R}^n\), \(y \in {\mathbb R}^n\), \(\lambda \in {\mathbb R}\), \(x^\ast \) a solution of \(F(x):=x-\lambda D(x)-y=0\), and the mapping \(A\) is defined on an open neighborhood \(E\) of \(x^\ast \), \(A:E \rightarrow {\mathcal L}({\mathbb R}^n)\). If \(D\) is differentiable at \(x^\ast \), \(A\) is continuous at \(x^\ast \) and </p>
<div class="displaymath" id="a0000000016">
  \[  \rho \big(I-A(x^\ast )(I-\lambda D^\prime (x^\ast )\big) {\lt} 1  \]
</div>
<p> then \(x^\ast \) is a point of attraction for the method <span class="rm">(<a href="#f.2 xn+1=xn-An(xn-lam D(xn)-y)">2</a>)</span>. </p>

  </div>
</div> </p>
<p>The proof is an immediate application of Lemma <a href="#lem 1">6</a> and Theorem <a href="#Th. Ostrowski">4</a>. </p>
<p>The conditions are much simpler for the case of the second method. </p>
<p><div class="theorem_thmwrapper " id="a0000000017">
  <div class="theorem_thmheading">
    <span class="theorem_thmcaption">
    Theorem
    </span>
    <span class="theorem_thmlabel">8</span>
  </div>
  <div class="theorem_thmcontent">
  <p>Let \(D:{\mathbb R}^n\rightarrow {\mathbb R}^n\), \(y \in {\mathbb R}^n\), \(\lambda \in {\mathbb R}\), \(x^\ast \) a solution of \(F(x):=x-\lambda D(x)-y=0\). If the mapping \(D\) is differentiable on an open neighborhood of \(x^\ast \), with \(D^\prime \) continuous at \(x^\ast \), and </p>
<div class="displaymath" id="a0000000018">
  \[  |\lambda | \rho \big(D^\prime (x^\ast )\big) {\lt} 1  \]
</div>
<p> then \(x^\ast \) is a point of attraction for the method <span class="rm">(<a href="#f. xn+1=xn-(I+D'xn)(xn-lam D(xn)-y)">4</a>)</span>. </p>

  </div>
</div> </p>
<p><div class="proof_wrapper" id="a0000000019">
  <div class="proof_heading">
    <span class="proof_caption">
    Proof
    </span>
    <span class="expand-proof">â–¼</span>
  </div>
  <div class="proof_content">
  
  </div>
</div>By Lemma <a href="#lem 1">6</a> we get </p>
<div class="displaymath" id="a0000000020">
  \[  G^\prime (x^\ast )= I - \big(I+\lambda D^\prime (x^\ast )\big)(I-\lambda D^\prime (x^\ast )\big)= \lambda ^2 D^\prime (x^\ast )^2,  \]
</div>
<p> whence, by Theorem <a href="#Th. Ostrowski">4</a>, the conclusion follows. </p>
<p>The same observations as in Remark <a href="#Rem.1">5</a> apply. </p>
<p><small class="footnotesize">  </small></p>
<div class="bibliography">
<h1>Bibliography</h1>
<dl class="bibliography">
  <dt><a name="Catinas 2002">1</a></dt>
  <dd><p><a href ="http://dx.doi.org/10.1023/A:1015304720071"> E. <i class="sc">Cătinaş</i>, <i class="it">On the superlinear convergence of the successive approximations method</i>, J. Optim. Theory Appl., 113 (2002) no. 3, pp. 473–485. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="Catinas 2005">2</a></dt>
  <dd><p><a href ="http://dx.doi.org/10.1090/S0025-5718-04-01646-1"> E. <i class="sc">Cătinaş</i>, <i class="it">The inexact, inexact perturbed and quasi-Newton methods are equivalent models</i>, Math. Comp., 74 (2005) no. 249, pp. 291–301. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="Catinas 2015">3</a></dt>
  <dd><p>E. <i class="sc">Cătinaş</i>, <i class="it">On the convergence orders</i>, manuscript. </p>
</dd>
  <dt><a name="2 DiaconuPavaloiu">4</a></dt>
  <dd><p><a href ="http://ictp.acad.ro/jnaat/journal/article/view/1972-vol1-art3"> Diaconu, A., Păvăloiu, I., <i class="itshape">Sur quelque méthodes itératives pour la resolution</i> <i class="itshape">des équations opérationnelles</i>, Rev. Anal. Numér. Theor. Approx., vol. 1, 45–61 (1972). <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="OR70">5</a></dt>
  <dd><p>J.M. <i class="sc">Ortega</i>, W.C. <i class="sc">Rheinboldt</i>, <i class="it">Iterative solution of nonlinear equations in several variables</i>, Academic Press, New York, 1970. </p>
</dd>
  <dt><a name="Pavaloiu 1986">6</a></dt>
  <dd><p>I. Păvăloiu, <i class="it">La convergence de certaines méthodes itératives pour résoudre certaines equations operationnelles</i>, Seminar on functional analysis and numerical methods, Preprint no. 1 (1986), pp. 127-132 (in French). </p>
</dd>
  <dt><a name="Pavaloiu 2009">7</a></dt>
  <dd><p><i class="sc">I. Păvăloiu</i>, <i class="it">A unified treatment of the modified Newton and chord methods</i>, Carpathian J. Math. 25 (2009) no. 2, pp. 192–196. </p>
</dd>
</dl>


</div>
</div> <!--main-text -->
</div> <!-- content-wrapper -->
</div> <!-- content -->
</div> <!-- wrapper -->

<nav class="prev_up_next">
</nav>

<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/jquery.min.js"></script>
<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/plastex.js"></script>
<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/svgxuse.js"></script>
</body>
</html>