X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/kahina_paper2.git/blobdiff_plain/dbd33e2eb7d60d68e5e062fa18923e6bc224aeab..867e83f7cceed45f069eddbdc5ae04562f715ddb:/paper.tex?ds=sidebyside diff --git a/paper.tex b/paper.tex index 93a0366..49cd195 100644 --- a/paper.tex +++ b/paper.tex @@ -661,42 +661,48 @@ EA: z^{k+1}_{i}=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}} {1-\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}\sum_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}}}, i=1,. . . .,n \end{equation} -contain 4 steps, start from the initial approximations of all the roots of the polynomial,the second step initialize the solution vector $Z$ using the Guggenheimer~\cite{Gugg86} method to assure the distinction of the initial vector roots, +This methods contains 4 steps. The first step consists of the initial +approximations of all the roots of the polynomial. The second step +initializes the solution vector $Z$ using the Guggenheimer +method~\cite{Gugg86} to ensure the distinction of the initial vector +roots. In step 3, the iterative function based on the Newton's +method~\cite{newt70} and Weiestrass operator~\cite{Weierstrass03} is +applied. With this step the computation of roots will converge, +provided that all roots are different. - than in step 3 we apply the the iterative function based on the Newton's method~\cite{newt70} and Weiestrass operator~\cite{Weierstrass03}, wich will make it possible to converge to the roots solution, provided that all the root are different. - - At the end of each application of the iterative function, a stop condition is verified consists in stopping the iterative process when the whole of the modules of the roots are lower than a fixed value $\xi$. +In order to stop the iterative function, a stop condition is +applied. This condition checks that all the root modules are lower +than a fixed value $\xi$. \begin{equation} \label{eq:Aberth-Conv-Cond} \forall i \in [1,n];\vert\frac{z_{i}^{k}-z_{i}^{k-1}}{z_{i}^{k}}\vert<\xi \end{equation} \subsection{Improving Ehrlich-Aberth method} -With high degree polynomial, the Ehrlich-Aberth method suffer from overflow because the limited number in the mantissa of floating points representations, which makes the computation of $p(z)$ wrong when z is large. +With high degree polynomials, the Ehrlich-Aberth method suffers from +floating point overflows due to the mantissa of floating points +representations. This induces errors in the computation of $p(z)$ when +$z$ is large. -Experimentally, it is very difficult to solve polynomials with Ehrlich-Aberth method and have roots which except the circle of unit, represented by the radius $r$ evaluated as: - -\begin{equation} -\label{R.EL} -R = exp(log(DBL\_MAX)/(2*n) ); -\end{equation} - +%Experimentally, it is very difficult to solve polynomials with the Ehrlich-Aberth method and have roots which except the circle of unit, represented by the radius $r$ evaluated as: %\begin{equation} - -%R = \exp( \log(DBL\_MAX) / (2*n) ) +%\label{R.EL} +%R = exp(log(DBL\_MAX)/(2*n) ); %\end{equation} - where \verb=DBL_MAX= stands for the maximum representable \verb=double= value. - -In order to hold into account the limit of size of floats, we propose to modifying the iterative function and compute the logarithm of: -\begin{equation} -EA: z^{k+1}_{i}=z_{i}^{k}-\frac{\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}} -{1-\frac{p(z_{i}^{k})}{p'(z_{i}^{k})}\sum_{j=1,j\neq i}^{j=n}{\frac{1}{(z_{i}^{k}-z_{j}^{k})}}}, i=1,. . . .,n -\end{equation} -This method allows, indeed, to exceed the computation of the polynomials of degree 100,000 and to reach a degree upper to 1,000,000. For that purpose, it is necessary to use the logarithm and the exponential of a complex. The iterative function of Ehrlich-Aberth method with exponential and logarithm is given as following: + +% where \verb=DBL_MAX= stands for the maximum representable \verb=double= value. + +In order to solve this problem, we propose to modify the iterative +function by using the logarithm and the exponential of a complex and +we propose a new version of the Ehrlich-Aberth method. This method +allows us to exceed the computation of the polynomials of degree +100,000 and to reach a degree up to more than 1,000,000. This new +version of the Ehrlich-Aberth method with exponential and logarithm is +defined as follows: \begin{equation} \label{Log_H2} @@ -706,15 +712,16 @@ p(z_{i}^{k})\right)-\ln\left(p'(z^{k}_{i})\right)- \ln\left(1-Q(z^{k}_{i})\right where: -\begin{equation} +\begin{eqnarray} \label{Log_H1} Q(z^{k}_{i})=\exp\left( \ln (p(z^{k}_{i}))-\ln(p'(z^{k}_{i}))+\ln \left( -\sum_{i\neq j}^{n}\frac{1}{z^{k}_{i}-z^{k}_{j}}\right)\right)i=1,...,n, -\end{equation} +\sum_{i\neq j}^{n}\frac{1}{z^{k}_{i}-z^{k}_{j}}\right)\right)\\ +i=1,...,n, \nonumber +\end{eqnarray} %We propose to use the logarithm and the exponential of a complex in order to compute the power at a high exponent. -Using the logarithm and the exponential operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower absolute values and the roots for large polynomial degrees can be looked for successfully~\cite{Karimall98}. +Using the logarithm and the exponential operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower absolute values~\cite{Karimall98}. %This problem was discussed earlier in~\cite{Karimall98} for the Durand-Kerner method. The authors %propose to use the logarithm and the exponential of a complex in order to compute the power at a high exponent. Using the logarithm and the exponential operators, we can replace any multiplications and divisions with additions and subtractions. Consequently, computations manipulate lower absolute values and the roots for large polynomial degrees can be looked for successfully~\cite{Karimall98}.