Abstract
Let \(X\) be a Banach space and \(\varphi:X\rightarrow X\) a nonlinear operator. Assume the equation \(x=\varphi \left( x\right)\) has a solution \(x^{\ast}\), and the sequence \(x_{n}=\varphi \left( x_{n-1}\right) ,\ n\geq1\) converges with order at least \(k\geq2\).
We consider a setting useful for practical applications, where the sequence \(\left( x_{n}\right) _{n\geq0}\) is replaced by an approximate one \(\left( \xi_{n}\right) _{n\geq0\text{}}\) where \(\xi_{n}=\varphi^{\ast}\left( \xi_{n-1}\right) ,\ n\geq1\), where \(\left \Vert \varphi \left( x\right) -\varphi^{\ast}\left( x\right) \right \Vert \leq \varepsilon\) in a neighborhood of the solution.
We obtain a result regarding the evaluation of the errors \(\left \Vert \xi_{n}-x^{\ast}\right \Vert \), under the hypothesis that from a certain step, the sequence \(\left( \xi_{n}\right) _{n\geq0}\) is stationary.
Authors
Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)
Title
Original title (in Romanian)
Evaluarea erorilor în rezolvarea numerică a ecuaţiilor operatoriale
English translation of the title
Error estimation in the numerical solving of operator equations
Keywords
iterative methods; succesive approximations; approximate computations; convergence order; error estimation
Cite this paper as:
I. Păvăloiu, Evaluarea erorilor în rezolvarea numerică a ecuaţiilor operatoriale, Studii şi cercetări matematice, 9 23 (1971), pp. 1459-1464 (in Romanian).
About this paper
Journal
Studii şi cercetări matematice
Publisher Name
Academia Republicii S.R.
DOI
Not available yet.
Print ISBN
Not available yet.
Online ISBN
Not available yet.
Google Scholar Profile
References
[1] Fujii, M., Remarks to Accelerated Iterative Processes for Numerical Solution of Equations. J. Sci. Hiroshima Univ. Ser. A-I, 27, 97-118. (1963).
[2]. Lankaster P., Error for the Newton – Raphson Method, Numerische Mathematik, 9, 1, 55-68 (1966).
[3] Ostrowski A’M., The Round- off stability of iterations, Z,A.M.M,, 47, ,77-81 (1967).
[4]. Pavaloiu I., Asupra unor inegalitati recurente si aplicatii ale lor. St. cerc. mat. 8, 19, 1175-1179 (1967).
[5] I. Pavaloiu, Observatii asupra rezolvarii sistemelor de ecuatii cu ajutorul procedeelor iterative. Idem 9, 19, 1289-1298 (1967).
[6] Urabe, M., Convergence of Numerical lteratíon of Equations. J. Sci. Hiroshima IJniv. l Ser, A,. 19, 479-489 (1956).
[7] M. Urabe, Solution of Equation by Iteration Process. J. Sci. Hiroshima Univ. Ser. A-I, 26, 77-91 (1962).
Paper (preprint) in HTML form
Original text
Rate this translation
Your feedback will be used to help improve Google Translate
Error estimation in the numerical solving of operator equations
OF
In this paper we will study the evaluation of errors that appear in the approximate solution of operational equations, when their solution is done with rapidly converging iterative procedures. We will give an evaluation of the errors in question using a delimitation of the solutions of some nonlinear recurrent inequalities. In the papers [1], [2], [3], [4], [6] and [7] the authors studied this problem for iterative procedures that have the convergence order 1 and then applied the results found to the study of the errors of procedures with convergence order 2.
We consider the equation
{:(1)x-varphi(x)=0:}\begin{equation*}
x-\varphi(x)=0 \tag{1}
\end{equation*}
and for its solution, the iterative procedure
{:(2)varphi(x_(n))=varphi(x_(n-1))","n=1","2","dots","x_(0)in X:}\begin{equation*}
\varphi\left(x_{n}\right)=\varphi\left(x_{n-1}\right), n=1,2, \ldots, x_{0} \in X \tag{2}
\end{equation*}
wherevarphi\varphiis an operator defined on the spaceXXand with values inXX. Throughout what follows, we will assume that the iterative procedure (2) satisfies the following conditions:
a) There is at least one elementbar(x)in X\bar{x} \in Xfor whichbar(x)=varphi( bar(x))\bar{x}=\varphi(\bar{x}).
b) lim_(n rarr oo)||x_(n)-( bar(x))||=0\lim _{n \rightarrow \infty}\left\|x_{n}-\bar{x}\right\|=0, where(x_(n))_(n=0)^(yes)\left(x_{n}\right)_{n=0}^{\infty}is the string generated by procedure (2).
e) The operatorvarphi\varphiadmits derivatives (in the Fréchet sense) up to the orderkkincluding (k >= 2k \geqq 2- natural number), for which the following conditions are met:
a) There is at least one elementbar(x)in X\bar{x} \in Xfor whichbar(x)=varphi( bar(x))\bar{x}=\varphi(\bar{x}).
b) lim_(n rarr oo)||x_(n)-( bar(x))||=0\lim _{n \rightarrow \infty}\left\|x_{n}-\bar{x}\right\|=0, where(x_(n))_(n=0)^(yes)\left(x_{n}\right)_{n=0}^{\infty}is the string generated by procedure (2).
e) The operatorvarphi\varphiadmits derivatives (in the Fréchet sense) up to the orderkkincluding (k >= 2k \geqq 2- natural number), for which the following conditions are met:
varphi^((i))( bar(x))=theta_(i),i=1,2,dots,k-1;s u p_(x in bar(S))||varphi^((k))(x)|| <= M < +oo,\varphi^{(i)}(\bar{x})=\theta_{i}, i=1,2, \ldots, k-1 ; \sup _{x \in \bar{S}}\left\|\varphi^{(k)}(x)\right\| \leqq M<+\infty,
whereS={x in X:||x-( bar(x))||≦∣( bar(x))-x_(0)||}S=\left\{x \in X:\|x-\bar{x}\| \leqq \mid \bar{x}-x_{0} \|\right\}andtheta_(i)\theta_{i}is the null operationi-i-linear.
If we note with
omega_(n)=((M)/(k!))^((1)/(k-1))*||x_(n)-( bar(x))||,quad n=0,1,2,dots\omega_{n}=\left(\frac{M}{k!}\right)^{\frac{1}{k-1}} \cdot\left\|x_{n}-\bar{x}\right\|, \quad n=0,1,2, \ldots
and we assume thatomega_(0) < 1\omega_{0}<1, taking into account hypotheses a) and c) we will show that the equality holds
lim_(n rarr oo)omega_(n)=0\lim _{n \rightarrow \infty} \omega_{n}=0
that is, the string(x_(n))_(n=0)^(oo)\left(x_{n}\right)_{n=0}^{\infty}is convergent.
Indeed, applying the generalized Taylor formula we deduce the inequalities
Indeed, applying the generalized Taylor formula we deduce the inequalities
omega_(n) <= omega_(0)^(k^(n)),quad n=1,2,dots\omega_{n} \leqq \omega_{0}^{k^{n}}, \quad n=1,2, \ldots
from which we deduce the required equality.
We first prove the following lemma:
Lemma 1. Ifdelta\deltais a non-negative number,(rho_(n))_(n=0)^(oo)\left(\rho_{n}\right)_{n=0}^{\infty}is a sequence of non-negative numbers that satisfies the recurrence relation
We first prove the following lemma:
Lemma 1. Ifdelta\deltais a non-negative number,(rho_(n))_(n=0)^(oo)\left(\rho_{n}\right)_{n=0}^{\infty}is a sequence of non-negative numbers that satisfies the recurrence relation
{:(3)rho_(n) <= rho_(n-1)^(k)+delta","k >= 2","quad n=1","2","dots:}\begin{equation*}
\rho_{n} \leqq \rho_{n-1}^{k}+\delta, k \geqq 2, \quad n=1,2, \ldots \tag{3}
\end{equation*}
{:(4)rho_(0) < 1:}\begin{equation*}
\rho_{0}<1 \tag{4}
\end{equation*}
and ā is the smallest positive solution (if it exists) of the equation
{:(5)alpha=(alpha+rho_(0))^(k)-rho_(0)^(k)+delta:}\begin{equation*}
\alpha=\left(\alpha+\rho_{0}\right)^{k}-\rho_{0}^{k}+\delta \tag{5}
\end{equation*}
Then for anythingn=1,2,dotsn=1,2, \ldotsthe inequalities occur:
{:(6)rho_(n) <= rho_(0)^(kn)+ bar(alpha):}\begin{equation*}
\rho_{n} \leqq \rho_{0}^{k n}+\bar{\alpha} \tag{6}
\end{equation*}
Proof. We will prove inequalities (6) by induction. Forn=1n=1we obtain the inequality
rho_(1) <= (rho_(0)+( bar(alpha)))^(k)+delta\rho_{1} \leqq\left(\rho_{0}+\bar{\alpha}\right)^{k}+\delta
and ifbar(alpha)\bar{\alpha}is a solution of equation (5), then obviously the inequality holds
rho_(1) <= rho_(0)^(k)+ bar(alpha)\rho_{1} \leqq \rho_{0}^{k}+\bar{\alpha}
which proves the statement of the lemma for the casen=1n=1From (4) and (5) we deduce that forn=1,2,dotsn=1,2, \ldotsinequalities occur
{:(7)C_(k)^(1)*rho_(0)^(k^(n)(k-1)) bar(alpha)+dots+C_(k)^(k-1)rho_(0)^(k^(n)) bar(alpha)^(k-1)+ bar(alpha)^(k)+delta <= bar(alpha).:}\begin{equation*}
C_{k}^{1} \cdot \rho_{0}^{k^{n}(k-1)} \bar{\alpha}+\ldots+C_{k}^{k-1} \rho_{0}^{k^{n}} \bar{\alpha}^{k-1}+\bar{\alpha}^{k}+\delta \leqq \bar{\alpha} . \tag{7}
\end{equation*}
We assume by induction that the inequality holds:
rho_(n-1) <= rho_(0)^(k^(n-1))+ bar(alpha)\rho_{n-1} \leqq \rho_{0}^{k^{n-1}}+\bar{\alpha}
which by substituting it in (3) we obtain
rho_(n) <= (rho_(0)^(k^(n-1))+( bar(alpha)))^(k)+delta\rho_{n} \leqq\left(\rho_{0}^{k^{n-1}}+\bar{\alpha}\right)^{k}+\delta
from which, expanding according to Newton's binomial formula and taking into account inequalities (7.), we deduce
rho_(n)=rho_(0)^(k^(n))+ bar(alpha)\rho_{n}=\rho_{0}^{k^{n}}+\bar{\alpha}
which proves the statement of the lemma.
For the study of errors we will consider, alongside the iterative procedure (2), the following approximate procedure,
For the study of errors we will consider, alongside the iterative procedure (2), the following approximate procedure,
{:(8)xi_(n)=varphi^(**)(xi_(n-1))","" unde "xi_(0)=x_(0)","n=1","2","dots:}\begin{equation*}
\xi_{n}=\varphi^{*}\left(\xi_{n-1}\right), \text { unde } \xi_{0}=x_{0}, n=1,2, \ldots \tag{8}
\end{equation*}
where the operatorvarphi^(**)\varphi^{*}is defined on the spaceXXand with values inXX.
Theorem 1. Given a negative real number e. We assume that relative to e there is at least one positive numberM_(1)M_{1}so that the conditions are met:
a) Equation (5) where
Theorem 1. Given a negative real number e. We assume that relative to e there is at least one positive numberM_(1)M_{1}so that the conditions are met:
a) Equation (5) where
rho_(0)=((M_(1))/(k!))^((1)/(k-1))*||( bar(x))-x_(0)||,quad delta=epsi((M_(1))/(k!))^((1)/(k-1))\rho_{0}=\left(\frac{M_{1}}{k!}\right)^{\frac{1}{k-1}} \cdot\left\|\bar{x}-x_{0}\right\|, \quad \delta=\varepsilon\left(\frac{M_{1}}{k!}\right)^{\frac{1}{k-1}}
has at least one positive real solution.
b) Fréchet derivativevarphi^((k))\varphi^{(k)}check the inequality
b) Fréchet derivativevarphi^((k))\varphi^{(k)}check the inequality
||varphi^((k))(x)|| <= M_(1) < +oo\left\|\varphi^{(k)}(x)\right\| \leqq M_{1}<+\infty
for anythingw inS^(')w \in S^{\prime}whereS^(')={x in X:||x-( bar(x))|| <= ||( bar(x))-x_(0)||+( bar(alpha))((k!)/(M_(1)))^((1)/(k-1))}S^{\prime}=\left\{x \in X:\|x-\bar{x}\| \leq\left\|\bar{x}-x_{0}\right\|+\bar{\alpha}\left(\frac{k!}{M_{1}}\right)^{\frac{1}{k-1}}\right\}and ā is the smallest positive solution of equation (5).
e) The numberM_(1)M_{1}and the elementx_(0)x_{0}are such that the inequality holdsrho_(0) < 1\rho_{0}<1d )
The operatorvarphi^(**)\varphi^{*}is chosen so that the inequality is verified
e) The numberM_(1)M_{1}and the elementx_(0)x_{0}are such that the inequality holdsrho_(0) < 1\rho_{0}<1d )
The operatorvarphi^(**)\varphi^{*}is chosen so that the inequality is verified
||varphi(x)-varphi^(**)(x)|| <= epsi," pentru orice "x inS^(').\left\|\varphi(x)-\varphi^{*}(x)\right\| \leqq \varepsilon, \text { pentru orice } x \in S^{\prime} .
Under these conditions all successive iterations(xi_(n))_(n=0)^(oo)\left(\xi_{n}\right)_{n=0}^{\infty}belong to the sphereS^(')S^{\prime}and the delimitation takes place
{:(9)||( bar(x))-xi_(n)|| <= ((k!)/(M_(1)))^((1)/(k-1))*(rho_(0)^(k^(n))+( bar(alpha)))","quad n=1","2","dots:}\begin{equation*}
\left\|\bar{x}-\xi_{n}\right\| \leqq\left(\frac{k!}{M_{1}}\right)^{\frac{1}{k-1}} \cdot\left(\rho_{0}^{k^{n}}+\bar{\alpha}\right), \quad n=1,2, \ldots \tag{9}
\end{equation*}
Demonstration. Indeed, becausexi_(0)=x_(0)inS^(')\xi_{0}=x_{0} \in S^{\prime}we will have
||( bar(x))-xi_(1)|| <= ||varphi(( bar(x)))-varphi(xi_(0))||+||varphi(xi_(0))-varphi^(**)(xi_(0))|| <= (M_(1))/(k!)||( bar(x))-xi_(0)||^(k)+epsi\left\|\bar{x}-\xi_{1}\right\| \leqq\left\|\varphi(\bar{x})-\varphi\left(\xi_{0}\right)\right\|+\left\|\varphi\left(\xi_{0}\right)-\varphi^{*}\left(\xi_{0}\right)\right\| \leqq \frac{M_{1}}{k!}\left\|\bar{x}-\xi_{0}\right\|^{k}+\varepsilonand noting
||( bar(x))-xi_(1)|| <= ||varphi(( bar(x)))-varphi(xi_(0))||+||varphi(xi_(0))-varphi^(**)(xi_(0))|| <= (M_(1))/(k!)||( bar(x))-xi_(0)||^(k)+epsi\left\|\bar{x}-\xi_{1}\right\| \leqq\left\|\varphi(\bar{x})-\varphi\left(\xi_{0}\right)\right\|+\left\|\varphi\left(\xi_{0}\right)-\varphi^{*}\left(\xi_{0}\right)\right\| \leqq \frac{M_{1}}{k!}\left\|\bar{x}-\xi_{0}\right\|^{k}+\varepsilonand noting
rho_(1)=((M_(1))/(k!))^((1)/(k-1))||( bar(x))-xi_(1)||" şi "rho_(0)=((M_(1))/(k!))^((1)/(k-1))||( bar(x))-xi_(0)||\rho_{1}=\left(\frac{M_{1}}{k!}\right)^{\frac{1}{k-1}}\left\|\bar{x}-\xi_{1}\right\| \text { şi } \rho_{0}=\left(\frac{M_{1}}{k!}\right)^{\frac{1}{k-1}}\left\|\bar{x}-\xi_{0}\right\|ş
we deduce the inequality
rho_(1) <= rho_(0)^(k)+delta.\rho_{1} \leqq \rho_{0}^{k}+\delta .
Thus the conditions of Lemma 1 are satisfied forrho_(0)\rho_{0}andrho_(1)\rho_{1}.
Eitherbar(alpha)\bar{\alpha}the smallest positive solution of equation (5). Taking into account lemma 1 and condition c) we have
Eitherbar(alpha)\bar{\alpha}the smallest positive solution of equation (5). Taking into account lemma 1 and condition c) we have
rho_(1) <= rho_(0)^(k)+ bar(alpha)\rho_{1} \leqq \rho_{0}^{k}+\bar{\alpha}
from which we easily deduce thatxi_(1)inS^(')\xi_{1} \in S^{\prime}.
We now assume by induction thatxi_(n-1)inS^(')\xi_{n-1} \in S^{\prime}and we demonstrate thatxi_(n)inS^(')\xi_{n} \in S^{\prime}Indeed, we have:
We now assume by induction thatxi_(n-1)inS^(')\xi_{n-1} \in S^{\prime}and we demonstrate thatxi_(n)inS^(')\xi_{n} \in S^{\prime}Indeed, we have:
{:[||( bar(x))-xi_(n)|| <= ||varphi(( bar(x)))-varphi(xi_(n-1))||+||varphi(xi_(n-1))-varphi^(**)(xi_(n-1))|| <= ],[ <= (M_(1))/(k!)||( vec(x))-xi_(n-1)||^(pi)+epsi]:}\begin{gathered}
\left\|\bar{x}-\xi_{n}\right\| \leqq\left\|\varphi(\bar{x})-\varphi\left(\xi_{n-1}\right)\right\|+\left\|\varphi\left(\xi_{n-1}\right)-\varphi^{*}\left(\xi_{n-1}\right)\right\| \leqq \\
\leqq \frac{M_{1}}{k!}\left\|\vec{x}-\xi_{n-1}\right\|^{\pi}+\varepsilon
\end{gathered}
where, noting withrho_(n)=((M_(1))/(k!))^((1)/(k-1))||( bar(x))-xi_(n)||,n=2,3,dots\rho_{n}=\left(\frac{M_{1}}{k!}\right)^{\frac{1}{k-1}}\left\|\bar{x}-\xi_{n}\right\|, n=2,3, \ldots, we have
rho_(n) <= rho_(n-1)^(k)+delta\rho_{n} \leqq \rho_{n-1}^{k}+\delta
Applying lemma 1 we deduce inequality (9) from which it follows thatxi_(n)inS^(')\xi_{n} \in S^{\prime}.
Note. It may happen that during the calculations, starting with a certain stepNN, let's havexi_(N)=xi_(N+1)=dots\xi_{N}=\xi_{N+1}=\ldotsIn this case for anyn==N,N+1,dotsn= =N, N+1, \ldotsinequality occurs
{:(10)||xi_(n)-( bar(x))|| <= ((k!)/(M_(1)))^((1)/(k-1)) bar(alpha):}\begin{equation*}
\left\|\xi_{n}-\bar{x}\right\| \leqq\left(\frac{k!}{M_{1}}\right)^{\frac{1}{k-1}} \bar{\alpha} \tag{10}
\end{equation*}
Example. Bevarphi(x)=(1)/(2)(x+(0,2)/(x))\varphi(x)=\frac{1}{2}\left(x+\frac{0,2}{x}\right)which generates the following iterative process
x_(n)=(1)/(2)(x_(n-1)+(0,2)/(x_(n-1))),x_(0)!=0,n=1,2,dotsx_{n}=\frac{1}{2}\left(x_{n-1}+\frac{0,2}{x_{n-1}}\right), x_{0} \neq 0, n=1,2, \ldots
which is used to calculate the positive root of the equation
x^(2)-0,2=0x^{2}-0,2=0
Assuming thatepsi=10^(-7)\varepsilon=10^{-7}andx_(0)=0,44x_{0}=0,44, we find||( bar(x))-x_(0)|| <= 0,01,M_(1)=4\left\|\bar{x}-x_{0}\right\| \leqq 0,01, M_{1}=4, rho_(0)=0,02,delta=2*10^(-7), bar(alpha) <= 3*10^(-7)\rho_{0}=0,02, \delta=2 \cdot 10^{-7}, \bar{\alpha} \leqq 3 \cdot 10^{-7}The successive interactions and therefore the values of the functionvarphi^(**)\varphi^{*}are given in the table.
Table
| No. crt. | xi_(n)\xi_{n} | varphi^(***)(xi_(n))\varphi^{\star}\left(\xi_{n}\right) |
| 0 | 0,44 | 0,44727272 |
| 1 | 0,44727272 | 0,44721359 |
| 2 | 0,44721359 | 0,44721359 |
| 3 | 0,44721359 | - |
The table shows thatxi_(2)=xi_(3)=dots=0,44721359\xi_{2}=\xi_{3}=\ldots=0,44721359, from which, taking into account the above observation and inequality (10), we obtain
|sqrt(0,2)-0,44721359| <= 1,5*10^(-7)|\sqrt{0,2}-0,44721359| \leqq 1,5 \cdot 10^{-7}
Received by the editorial office on October 10, 1970.
EVALUATION OF ERRORS IN THE NUMERICAL SOLUTION OF OPERATIONAL EQUATIONS
(RÉSUMÉ)
In the work we give an evaluation of errors for the case where a given operational equation is solved with the iterative method having an order of convergencek(k >= 2)k(k \geqq 2). Thus we generalize the results of works [1], [2], [3], [4], [5] and [7].
BIBLIOGRAPHY
- Fujit, M., Remarks to Accelerated Iterative Processes for Numerical Solution of Equations. J. Sci. Hiroshima Univ. Ser. A-I, 27, 97-118 (1963).
- Lankaster, P., Error for the Newton - Raphson Method. Numerische Mathematik, 9, 1, 55-68 (1966).
.3. Ostrowski, A.M., The Round - off Stability of iterations. Z.A.M.M., 47, 77-81 (1967). - Păvăloiv, I., On some recurrent inequalities and their applications. St. cerc. mat. 8, 19, 11751179 (1967).
-
- Observations on the solution of systems of equations using iterative procedures. Idem, 9, 19, 1289-1298 (1967).
- Jrabe, M., Convergence of Numerical Iteration of Equations. J. Sci. Hiroshima Univ. 1 Ser. A, 19, 479-489 (1956).
-
- Solution of Equations by Iteration Process. J. Sci. Hiroshima Univ. Ser. A-I, 26, 77-91 (1962).