From: Kahina Guidouche <guidouche@slayer.iut-bm.univ-fcomte.fr>
Date: Wed, 2 Sep 2015 16:57:46 +0000 (+0200)
Subject: Add the Aberth metho
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper1.git/commitdiff_plain/4fce38567a893e63987a602f906cd7375d3490c3

Add the Aberth metho
---

diff --git a/Root.tex b/Root.tex
index e233465..2ee2c28 100644
--- a/Root.tex
+++ b/Root.tex
@@ -54,9 +54,10 @@ $  Z_{i}=Z_{i}-\frac{P(Z_{i})}{\prod_{i\neq j}(z_{i}-z_{j})} $
 
 This formula is mentioned for the first time from Weiestrass [12]
 as part of the fundamental theorem of Algebra and is rediscovered
-from Ilieff [2], Docev [3], Durand [4], Kerner [5]. Another method
-discovered from Borsch-Supan [6] and also described and brought in
-the following form from Ehrlich [7] and Aberth~\cite{Aberth73}.
+from Ilieff~\cite{Ilief50} [2], Docev [3], Durand [4], Kerner [5].
+Another method discovered from Borsch-Supan [6] and also described
+and brought in the following form from Ehrlich [7] and
+Aberth~\cite{Aberth73}.
 \begin{center}
 
 $  Z_{i}=Z_{i}-\frac{1}{{\frac {P'(Z_{i})}
@@ -112,12 +113,98 @@ and compare it with the Durand Kerner
 implementation.................To be continued..................
 
 
+\section{Aberth method and difficulties}
+A cubically convergent iteration method for finding zeros of
+polynomials was proposed by O.Aberth[?].The Aberth method is a
+purely algebraic derivation.To illustrate the derivation, we let
+$w_{i}(z)$ be the product of linear factor $ w_{i}(z)=\prod_{j=1,j
+\neq i}^{n} (z-x_{j})$
+
+and rational function $R_{i}(z)$ be the correction term of
+Weistrass method (?)
+$$R_{i}(z)=\dfrac{p(z)}{w_{i}(Z)} , i=1,2,...,n. $$
+
+Differentiating the rational function $R_{i}(z)$ and applying the
+Newton method, we have
+$$\dfrac{R_{i}(z)}{R_{i}^{'}(z)}= \dfrac{p(z)}{p^{'}(z)-p(z)\dfrac{w_{i}(z)}{w_{i}^{'}(z)}}= \dfrac{p(z)}{p^{'}(z)-p(z) \sum _{j=1,j \neq i}^{n}\dfrac{1}{z-x_{i}}}, i=1,2,...,n $$
+Substituting $x_{j}$ for z we obtain the Aberth iteration method
+
+Let present the means stages of Aberth's method.
+
+\subsection{Polynomials Initialization}
+ The initialization of polynomial P(z) with complex coefficients
+ are given by:
+ $$ p(z)=\sum{a_{i}z^{n-i}}. where a_{n} \neq 0,a_{0}=1, a_{i}\subset C $$
+
+
+\subsection{Vector $Z^{0)}$ Initialization}
+
+The choice of the initial points $z^{(0)}_{i} , i = 1, . . . , n,$
+from which starting the iteration  (2) or (3), is rather delicate
+since the number of steps needed by the iterative method to reach
+a given approximation strongly depends on it. In [1] the Aberth
+iteration is started by selecting n equispaced points on a circle
+of center 0 and radius r, where r is an upper bound to the moduli
+of the zeros. After[18]  performs this choice by selecting complex
+numbers along different circles and relies on the result of [19].
+
+$$\sigma_{0}=\frac{u+v}{2};u=\frac{\sum_{i=1}^{n}u_{i}}{n.max_{i=1}^{n}u_{i}}; v=\frac{\sum_{i=0}^{n-1}v_{i}}{n.min_{i=0}^{n-1}v_{i}};u_{i}=2.|a_{i}|^{\frac{1}{i}}; v_{i}=\frac{|\frac{a_{n}}{a_{i}}|^{\frac{1}{n-i}}}{2} $$
+
+\subsection{Iterative Function Hi}
+The operator used with Aberth's method is corresponding to the
+following equation which will enable the convergence towards
+polynomial solutions, provided all the roots are distinct.
+
+$$ H_{i}(z)=z_{i}-\frac{1}{\frac{P^{'}(z_{i})}{P(z_{i})}-\sum_{j\neq i}{\frac{1}{z_{i}-z_{j}}}} $$
+
+\subsection{Convergence condition}
+determines the success of the termination. It consists in stopping
+the iterative function $H_{i}(z)$ when the are stable,the method
+converge sufficiently:
+$$  \forall i \in [1,n]; \frac{z_{i}^{(k)}-z_{i}^{(k-1)}}{z_{i}^{(k)}}< \xi$$
+
+\section{Difficulties and amelioration}
+the Aberth method implementation suffer of overflow problems. This
+situation occurs, for instance, in the case where a polynomial
+having positive coefficients and large degree is computed at a
+point $\xi$ where $|\xi| > 1$.Indeed the limited number in the
+mantissa of floating takings the computation of P(z) wrong when z
+is large. for example $(10^{50}) +1+ (- 10_{50})$ will give result
+0 instead of 1 in reality.consequently we can't compute the roots
+for large polynomial's degree. This problem was discuss in [17]
+for the Durand-Kerner method, the authors propose to use the
+logratihm and the exponential of a complex:
+
+$$ \forall(x,y)\in R^{*2}; \ln (x+i.y)=\ln(x^{2}+y^{2}) 2+i.\arcsin(y\sqrt{x^{2}+y^{2}})_{\left] -\pi, \pi\right[ } $$
+$$ \forall(x,y)\in R^{*2}; \exp(x+i.y)= \exp(x).\exp(i.y)$$
+$$                                       =\exp(x).\cos(y)+i.\exp(x).\sin(y)$$
+
+
+The application of logarithm can replace any multiplications and
+divisions with additions and subtractions; consequently it
+manipulates lower absolute values and can be compute the roots for
+large polynomial's degree exceed 1000[17].
+
+Applying this solution for the Aberth method we obtain the
+iteration function with logarithm:
+%%$$ \exp \bigl(  \ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'}))- \ln(1- \exp(\ln(p(z)_{k})-ln(\ln(p(z)_{k}^{'})+\ln\sum_{i\neq j}^{n}\frac{1}{z_{k}-z_{j}})$$
+
+$$ H_{i}(z)=z_{i}^{k}-\exp \left(\ln \left( p(z_{k})\right)-\ln\left(p(z_{k}^{'})\right)- \ln\left(1- \exp\left( \ln (p(z_{k}))-\ln(p(z_{k}^{'}))+\ln \left( \sum_{k\neq j}^{n}\frac{1}{z_{k}-z_{j}}\right)\right) \right) \right)$$
+
+
+
+this solution is applying when it is necessary
+
+\section{The implementation of simultaneous methods in a parallel computer}
+
 
 \bibliographystyle{plain}
 \bibliography{biblio}
 %% \begin{thebibliography}{2}
 
 %% \bibitem [1] {1} O. Aberth, Iteration Methods for Finding
+
+
 %% all Zeros of a Polynomial Simultaneously, Math. Comput. 27, 122
 %% (1973) 339–344.
 
@@ -176,5 +263,14 @@ implementation.................To be continued..................
 %% advanced Networking, Distributed Systems and Applications, Bejaia,
 %% Algeria, pages 53--57, June 2014. IEEE
 
+%% \bibitem [17] {17} Karim Rhofir, François Spies, and Jean-Claude Miellou.
+%%Perfectionnements de la méthode asynchrone de Durand-Kerner pour
+%%les polynômes complexes. Calculateurs Parallèles, 10(4):449-- 458,
+%%1998.
+%% \bibitem [18] {18} Bini, D. A. Numerical computation of polynomial zeros by
+%%means of Aberth’s method. Numerical Algorithms 13 (1996), 179–
+%%200.
+%% \bibitem [19] {19} A. Ostrowski, On a Theorem by J.L. Walsh Concerning the Moduli of Roots of Algebraic Equations,
+%%Bull. A.M.S., 47 (1941) 742–746.
 %% \end{thebibliography}
 \end{document}