[Scilab-users] improve accuracy of roots

Federico Miyara fmiyara at fceia.unr.edu.ar
Tue Jan 15 19:49:02 CET 2019 

Stéphane,

Thank you very much for your contribution!

Best regards,

Federico Miyara


On 15/01/2019 14:14, Stéphane Mottelet wrote:
> Hello,
>
> After a quick search on the internet I have found and translated in 
> Scilab "multroot", a Matlab Package computing polynomial roots and 
> multiplicities. If you are interested proceed to this url: 
> http://bugzilla.scilab.org/show_bug.cgi?id=15349#c9
>
> Enjoy !
>
> S.
>
> Le 14/01/2019 à 21:07, Federico Miyara a écrit :
>>
>> Denis,
>>
>> What I meant is that convergence is a limiting process. On average, 
>> as the number of iterations rises you´ll be closer to the limit, bu 
>> there is no guarantee that any single iteration will bring you any 
>> closer; it may be a question of luck. Maybe (though it would require 
>> a proof, it is not self-evident for me) in the exact case of a single 
>> multiple root as (x - a)^n the convergence process is monotonous, but 
>> what if you have (x - a1)* ... * (x  - an) where ak are all very 
>> similar but not identical, say, with relative differences of the 
>> order of those reported by the application of the regular version  of 
>> roots.
>> Regards,
>>
>> Federico Miyara
>>
>>
>> On 14/01/2019 13:47, CRETE Denis wrote:
>>> Thank you Frederico!
>>> According to the page you refer to, the method seems to converge more rapidly with this factor equal to the multiplicity of the root.
>>> About overshoot, it is well known to occur for |x|^a where a <1. But for a>1, the risk of overshoot with the Newton-Raphson method seems to be very small...
>>> Best regards
>>> Denis
>>>
>>> [@@ THALES GROUP INTERNAL @@]
>>>
>>> Unité Mixte de Physique CNRS / THALES
>>> 1 Avenue Augustin Fresnel
>>> 91767 Palaiseau CEDEx - France
>>> Tel : +33 (0)1 69 41 58 52 Fax : +33 (0)1 69 41 58 78
>>> e-mail :
>>>   denis.crete at thalesgroup.com  <mailto:%20denis.crete at thalesgroup.com>
>>>   http://www.trt.thalesgroup.com/ump-cnrs-thales
>>>   http://www.research.thalesgroup.com
>>>
>>>
>>> -----Message d'origine-----
>>> De : users [mailto:users-bounces at lists.scilab.org] De la part de Federico Miyara
>>> Envoyé : samedi 12 janvier 2019 07:52
>>> À : Users mailing list for Scilab
>>> Objet : Re: [Scilab-users] improve accuracy of roots
>>>
>>>
>>> Denis,
>>>
>>> I've found the correction here,
>>>
>>> https://en.wikipedia.org/wiki/Newton%27s_method
>>>
>>> It is useful to accelerate convergence in case of multiple roots, but I
>>> guess it is not valid to apply it once to improve accuracy because of
>>> the risk of overshoot.
>>>
>>> Regards,
>>>
>>> Federico Miyara
>>>
>>>
>>> On 10/01/2019 10:32, CRETE Denis wrote:
>>>> Hello,
>>>> I tried this correction to the initial roots z:
>>>>
>>>> z-4*(1+z).^4 ./([ones(z),z,z.^2,z.^3]*(C(2:5).*(1:4))')
>>>>    ans  =
>>>>
>>>>     -1. - 1.923D-13i
>>>>     -1. + 1.189D-12i
>>>>     -1. - 1.189D-12i
>>>>     -1. - 1.919D-13i
>>>>
>>>> // Evaluation of new error, (and defining Z as the intended root, i.e. here Z=-1):
>>>> z2=z-4*(z-Z).^4 ./([ones(z),z,z.^2,z.^3]*(C(2:5).*(1:4))')
>>>> z2 - Z
>>>>    ans  =
>>>>
>>>>      2.233D-08 - 1.923D-13i
>>>>     -2.968D-08 + 1.189D-12i
>>>>     -2.968D-08 - 1.189D-12i
>>>>      2.131D-08 - 1.919D-13i
>>>>
>>>> The factor 4 in the correction is a bit obscure to me, but it seems to work also for R=(3+p)^4, again with an accuracy on the roots of a ~2E-8.
>>>>
>>>> HTH
>>>> Denis
>>>>
>>>> -----Message d'origine-----
>>>> De : users [mailto:users-bounces at lists.scilab.org] De la part de Federico Miyara
>>>> Envoyé : jeudi 10 janvier 2019 00:32
>>>> À :users at lists.scilab.org
>>>> Objet : [Scilab-users] improve accuracy of roots
>>>>
>>>>
>>>> Dear all,
>>>>
>>>> Consider this code:
>>>>
>>>> // Define polynomial variable
>>>> p = poly(0, 'p', 'roots');
>>>>
>>>> // Define fourth degree polynomial
>>>> R = (1 + p)^4;
>>>>
>>>> // Find its roots
>>>> z = roots(R)
>>>>
>>>> The result (Scilab 6.0.1) is
>>>>
>>>>     z  =
>>>>
>>>>      -1.0001886
>>>>      -1. + 0.0001886i
>>>>      -1. - 0.0001886i
>>>>      -0.9998114
>>>>
>>>> It should be something closer to
>>>>
>>>>      -1.
>>>>      -1.
>>>>      -1.
>>>>      -1.
>>>>
>>>> Using these roots
>>>>
>>>> C = coeff((p-z(1))*(p-z(2))*(p-z(3))*(p-z(4)))
>>>>
>>>> yield seemingly accurate coefficients
>>>>     C  =
>>>>
>>>>       1.   4.   6.   4.   1.
>>>>
>>>>
>>>> but
>>>>
>>>> C - [1  4  6 4 1]
>>>>
>>>> shows the actual error:
>>>>
>>>> ans  =
>>>>
>>>>       3.775D-15   1.243D-14   1.155D-14   4.441D-15   0.
>>>>
>>>> This is acceptable for the coefficients, but the error in the roots is
>>>> too large. Somehow the errors cancel out when  assembling back the
>>>> polynomial but each individual zero should be closer to the theoretical
>>>> value
>>>>
>>>> Is there some way to improve the accuracy?
>>>>
>>>> Regards,
>>>>
>>>> Federico Miyara
>>>>
>>>>
>>>>
>>>>
>>>> ---
>>>> El software de antivirus Avast ha analizado este correo electrónico en busca de virus.
>>>> https://www.avast.com/antivirus
>>>>
>>>> _______________________________________________
>>>> users mailing list
>>>> users at lists.scilab.org
>>>> http://lists.scilab.org/mailman/listinfo/users
>>>> _______________________________________________
>>>> users mailing list
>>>> users at lists.scilab.org
>>>> http://lists.scilab.org/mailman/listinfo/users
>>>>
>>>>
>>> _______________________________________________
>>> users mailing list
>>> users at lists.scilab.org
>>> http://lists.scilab.org/mailman/listinfo/users
>>> _______________________________________________
>>> users mailing list
>>> users at lists.scilab.org
>>> http://lists.scilab.org/mailman/listinfo/users
>>>
>>>
>>
>>
>> <https://antispam.utc.fr/proxy/2/c3RlcGhhbmUubW90dGVsZXRAdXRjLmZy/www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient> 
>> 	Libre de virus. www.avast.com 
>> <https://antispam.utc.fr/proxy/2/c3RlcGhhbmUubW90dGVsZXRAdXRjLmZy/www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient> 
>>
>>
>> <#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
>>
>> _______________________________________________
>> users mailing list
>> users at lists.scilab.org
>> https://antispam.utc.fr/proxy/1/c3RlcGhhbmUubW90dGVsZXRAdXRjLmZy/lists.scilab.org/mailman/listinfo/users
>
>
> -- 
> Stéphane Mottelet
> Ingénieur de recherche
> EA 4297 Transformations Intégrées de la Matière Renouvelable
> Département Génie des Procédés Industriels
> Sorbonne Universités - Université de Technologie de Compiègne
> CS 60319, 60203 Compiègne cedex
> Tel : +33(0)344234688
> http://www.utc.fr/~mottelet
>
>
> _______________________________________________
> users mailing list
> users at lists.scilab.org
> http://lists.scilab.org/mailman/listinfo/users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.scilab.org/pipermail/users/attachments/20190115/8e90578e/attachment.htm>

More information about the users mailing list