File:Catastrophic cancellation.svg

Summary[edit]

DescriptionCatastrophic cancellation.svg	English: catastrophic cancellation or Loss of significance
Date	1 November 2014
Source	Own work
Author	Adam majewski
SVG development InfoField	The SVG code is valid.   This plot was created with Gnuplot.    This plot uses embedded text that can be easily translated using a text editor.

Summary[edit]

Question ( Stackoverflow )^[1] about exercise 13.3 from Numerical Linear Algebra - Lloyd N. Trefethen, David Bau.^[2]

There are 2 forms of the same function :

• factored : ${\displaystyle (x-2)^{9}}$
• expanded : ${\displaystyle x^{9}-18x^{8}+144x^{7}-672x^{6}+2016x^{5}-4032x^{4}+5376x^{3}-4608x^{2}+2304x-512}$

One can check that :

e:x^9 - 18*x^8 + 144*x^7 -672*x^6 + 2016*x^5 - 4032*x^4 + 5376*x^3 - 4608*x^2 + 2304*x - 512$
factor(e);
(x−2)^9

a:(x−2)^9;
expand(a);
x^9−18*x^8+144*x^7−672*x^6+2016*x^5−4032*x^4+5376*x^3−4608*x^2+2304*x−512

" (x−2) is small by definition of x, (x−2)^9 is even much smaller but can be computed with small relative error.

The single terms of the expanded polynomial are much larger and therefore you will suffer from catastrophic cancellation"

Is it chaotic ?^[3]

Maxima CAS src code[edit]

/* Maxima CAS src code */

load(draw);
draw2d(
   file_name = "f",
   color = gray,
   key = "expanded ",
   explicit(x^9 - 18*x^8 + 144*x^7 -672*x^6 + 2016*x^5 - 4032*x^4 + 
5376*x^3 - 4608*x^2 + 2304*x - 512 ,x, 2-0.0000005,2.0000005),
   color = red,
   key = " factored ",
   explicit((x-2)^9, x, 2-0.0000005,2.0000005),
   xtics  = 0.0000005,
   title      = "Plot of 2 forms of polynomial function : (x-2)^9",
   terminal = 'svg) $

One can also check horner form, but it looks similar to expanded :

kill(all);
remvalue(all);


f: (x-2)^9;
e: expand(f);
h: horner(horner:(e));





/* http://riotorto.users.sourceforge.net/gnuplot/multiplots/index.html */

load(draw);




scn1:gr2d(title       = "y = x^9−18*x^8+144*x^7−672*x^6+2016*x^5−4032*x^4+5376*x^3−4608*x^2+2304*x−512 ",
          color = gray,
          explicit(e, x ,2-0.0000005,2.0000005),
          xtics  = 0.0000005
         )$

scn2:gr2d(title       = " y = (x−2)^9 ",
          color = red,
          explicit(f, x, 2-0.0000005,2.0000005),
          xtics  = 0.0000005
         )$


scn3:gr2d(title       = "y = x*(x*(x*(x*(x*(x*(x*((x−18)*x+144)−672)+2016)−4032)+5376)−4608)+2304)−512 ",
          color = blue,
          explicit(h, x ,2-0.0000005,2.0000005),
          xtics  = 0.0000005
         )$



draw(terminal   = 'svg,
     file_name = "i",
     columns    = 1,
     dimensions=[600,1800], /* Since Maxima 5.23, pic_width and pic_height are deprecated.  */
     scn1, scn2, scn3)$

Licensing[edit]

I, the copyright holder of this work, hereby publish it under the following license:

This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.

You are free:

• to share – to copy, distribute and transmit the work
• to remix – to adapt the work

Under the following conditions:

• attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
• share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

https://creativecommons.org/licenses/by-sa/4.0CC BY-SA 4.0 Creative Commons Attribution-Share Alike 4.0 truetrue

References[edit]

1. ↑ Stackoverflow question
2. ↑ Numerical Linear Algebra - Lloyd N. Trefethen, David Bau. Archived from the original on 2014-01-24. Retrieved on 2014-11-02.
3. ↑ math.stackexchange question : is-loss-of-significance-chaotic