[Scilab-users] improve accuracy of roots

Stéphane Mottelet stephane.mottelet at utc.fr
Tue Jan 15 18:14:05 CET 2019 

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

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

More information about the users mailing list