Analysis of the Dynamic Evaluation of Newton Polynomials

Interpolating the expnential function at the points 0, 0.25, 0.5, 0.75, and 1 is shown in Figure 1a. Figure 1b shows the error of the evaluation of the interpolating Newton polynomial using forward evaluation (red), backward evaluation (aquamarine), and dynamic evaluation (black).

Examining the plot, the error of the foward evaluation is often greater than one unit of least precision (ULP) and backward evaluation often results in an error greater than 0.5 ULPs. The evaluation of the dynamic Newton polynomial, however, is almost universally less than 0.5 ULPs—the best possible result.

The mean squared error (MSE) of the dynamic evaluation is 8.92e-17 while the MSEs of the forward and backward evaluations are 9.68e-17 and 1.03e-16.


Figure 1a. Evaluating the exponential at 0, 0.25, 0.5, 0.75, and 1.


Figure 1b. The absolute errors of evaluations of the Newton polynomial of Figure 1a.

From this point, all numeric values are given to sufficient precision to be able to easily determine the actual double-precision floating-point number used within the program. For example, 0.94961000836901832134 converted to binary is the number 0.1111001100011001101001000011100111100110001100110100100000000000000000111101101101001010111100101011··· which is clearly the double 1.1110011000110011010010000111001111001100011001101001×2-1. The relative error of the approximation is 8.6×10-22—significantly less than the error for a double.

Figures 2a, 3a, and 3b show the exponential function evaluated at four random intermediate points in [0, 1] together with the end points:

  • Figure 1: 0, 0.21004692928867738089, 0.34859573170477325954, 0.69577480593965146394, 0.94961000836901832134, 1
  • Figure 2: 0, 0.16058411433388669609, 0.30648085396107327405, 0.59330819504955234489, 0.81079067874736654442, 1
  • Figure 3: 0, 0.1683000212853308919, 0.29263987301040433886, 0.74615058465681527444, 0.81476921835670679251, 1

The absolute errors of the evaluations are shown in Figures 2b through 4b and in all three cases, the error of the dynamic evaluation remains resonably bounded by 0.5 ULPs while both forward and backward evaluation result in errors greater which are, in some cases, greater than 1 ULP.

The MSEs of the dynamic evaluation remain relatively low at 8.91e-17, 8.84e-17, and 8.99e-17; while the MSE for the forward evaluation is approximately 10% higher with 9.76e-17, 9.94e-17, and 9.88e-17, respectively; and the MSE for the backward evaluatoin is closer to 20% higher with 1.15e-16, 1.03e-16, and 1.05e-16, respectively.


Figure 2a. Evaluating the exponential at six points on [0, 1].


Figure 2b. The absolute errors of evaluations of the Newton polynomial of Figure 2a.


Figure 3a. Evaluating the exponential at six points on [0, 1].


Figure 3b. The absolute errors of evaluations of the Newton polynomial of Figure 3a.


Figure 4a. Evaluating the exponential at six points on [0, 1].


Figure 4b. The absolute errors of evaluations of the Newton polynomial of Figure 4a.

Four Random Points

The next three examples, shown in Figures 5a through 7a, are interpolations of four randomly generated points on the region [0, 1] × (1, 2). The points are:

  • Figure 4: (0,1.031233522124231472), (0.32085050401317444235,1.6759028023462290147), (0.73958415549229095109,1.8520633475166108362), (1,1.6679793217535965333)
  • Figure 5: (0,1.028037212802114464), (0.083329775642291534221,1.1197614125533781326), (0.78759920517336534651,1.3566313937104452769), (1,1.8942805709756354027)
  • Figure 6: (0,1.1720901286099525418), (0.15682804126144761492,1.9314584806242298676), (0.78573469248867344739,1.2802369111591189732), (1,1.2368283319458497349)

The absolute errors of the evaluations are shown in Figures 5b through 7b. In all these cases, the MSE of the forward and backward evaluations is anywhere from 5% to almost 100% worse than the MSE of dynamic evaluation. Consider Table 1 which lists the MSEs for the three figures.

Table 1. Mean-squared Error of the evaluation of Newton polynomials on four points.

DynamicForwardBackward
Figure 56.58e-179.40e-177.19e-17
Figure 66.56e-176.88e-171.00e-16
Figure 78.98e-171.77e-161.01e-16

In most cases, the dynamic evaluation results in an approximation which is usually within 0.5 ULPs; however, forward and backward evaluation result in errors as large as 3 ULPs.


Figure 5a. An interpolation of four randomly generated points on [0, 1] × (1, 2).


Figure 5b. The absolute errors of evaluations of the Newton polynomial of Figure 5a.


Figure 6a. An interpolation of four randomly generated points on [0, 1] × (1, 2).


Figure 6b. The absolute errors of evaluations of the Newton polynomial of Figure 6a.


Figure 7a. An interpolation of four randomly generated points on [0, 1] × (1, 2).


Figure 7b. The absolute errors of evaluations of the Newton polynomial of Figure 7a.

Five Random Points

The examples given in Figures 8a through 10a show interpolations of five points randomly generated points on the region [0, 1] × (1, 2). The points are:

  • Figure 8: (0,1.8584220744010164772), (0.17722988757796734327,1.4289050695620966192), (0.58976952945337146605,1.9815645217809660927), (0.82673781822749314863,1.5764810240717981316), (1,1.8253612624599417913)
  • Figure 9: (0,1.6360859487373782262), (0.26628213077765677808,1.9034275747385935862), (0.39293391446564374103,1.956638259327336371), (0.8171560921786148457,1.3508287506880372053), (1,1.0256115640632861297)
  • Figure 10: (0,1.2519286066535528779), (0.30086670379815627641,1.6073352906887117264), (0.50432926176007031316,1.0672643739112022132), (0.7171177805325875676,1.3399629580508745086), (1,1.5485863907023269537)

The absolute errors of the evaluations are shown in Figures 8b through 10b and in each case, forward evaluation results in poorer evaluations near x = 0 and backward evaluation results in significantly poorer evaluations near x = 1. Table 2 lists the MSEs for the three figures.

Table 2. Mean-squared Error of the evaluation of Newton polynomials on five points.

DynamicForwardBackward
Figure 87.31e-171.14e-161.28e-16
Figure 96.83e-171.29e-161.04e-16
Figure 106.48e-178.43e-177.75e-17

Again, dynamic evaluation results in an approximation which is usually within 0.5 ULPs (the best one could expect); however, forward and backward evaluation can result in errors larger than 3 ULPs.


Figure 8a. An interpolation of five randomly generated points on [0, 1] × (1, 2).


Figure 8b. The absolute errors of evaluations of the Newton polynomial of Figure 8a. Note that the interpolating polynomial breaks 2 on [0.5, 0.6].


Figure 9a. An interpolation of five randomly generated points on [0, 1] × (1, 2).


Figure 9b. The absolute errors of evaluations of the Newton polynomial of Figure 9a.


Figure 10a. An interpolation of five randomly generated points on [0, 1] × (1, 2).


Figure 10b. The absolute errors of evaluations of the Newton polynomial of Figure 10a.

Six Random Points

Following this exploration, Figures 11a through 16a show interpolations of six points randomly generated points on the region [0, 1] × (1, 2). The points for the corresponding figures are:

  • Figure 11: (0,1.8069248608345747087), (0.20216505820963767692,1.3977437905956728859), (0.33760704325400620052,1.6581034141863246756), (0.74985515791916057537,1.0537828891788529884), (0.87321546353549484021,1.1249470264301388855), (1,1.1232200707882735724)
  • Figure 12: (0,1.3522853289508658392), (0.21772065349748387364,1.0680296598319103385), (0.47467602520467527816,1.0676622572670049216), (0.61056713625349434693,1.708597596599067403), (0.79958205590936448637,1.7758223608954912809), (1,1.8128606909014566284)
  • Figure 13: (0,1.9752811975662043498), (0.10202566888277682378,1.035117685345521954), (0.4372960076142549668,1.1646452104508155934), (0.51213293255406100446,1.4910625803708390524), (0.76147263416157695559,1.6491439187196752503), (1,1.0852739047656179139)
  • Figure 14: (0,1.2836409231106009621), (0.06595284099036494152,1.2590688188835368333), (0.26148922253003775706,1.2702297997987967992), (0.68576829574805142631,1.6801294850558645688), (0.78316170653941186153,1.515695049667588945), (1,1.8739029289567390446)
  • Figure 15: (0,1.4328378538754014127), (0.23395729413440324862,1.3859265751139850931), (0.49075864464545559951,1.8052932395624430306), (0.65615613032419051187,1.6936461984615989174), (0.77861193359299185612,1.8592498092256717346), (1,1.9633337529205407979)
  • Figure 16: (0,1.03906649725468192), (0.15204443603383582806,1.2489648374025545952), (0.49760509317163614806,1.9860301483357465369), (0.7262919220264497655,1.4018773592085937985), (0.88206370402223599481,1.6967851080451090695), (1,1.6958480145297236685)

Figures 11b through 16b show the absolute errors and Figure 13c and 16c, due to the large absolute errors, restrict the showing errors in [0, 1e-15]. Both forward and backward evaluation have significantly larger evaluation errors, as is shown in Table 3. In two cases, the error is greater than 5 ULPs.

Table 3. Mean-squared Error of the evaluation of Newton polynomials on six points.

DynamicForwardBackward
Figure 116.68e-172.34e-161.10e-16
Figure 126.73e-172.81e-162.43e-16
Figure 136.15e-176.70e-163.08e-16
Figure 146.57e-177.72e-172.94e-16
Figure 157.88e-171.10e-162.59e-16
Figure 168.38e-171.50e-165.61e-16

With dynamic evaluation, the absolute error does more regularly break the 0.5 ULP barrier; however, the general trend is that most evaluations remain restricted to the optimal range. Using foward and backward evaluation, the error can be as significant as 13 ULPs.


Figure 11a. An interpolation of six randomly generated points on [0, 1] × (1, 2).


Figure 11b. The absolute errors of evaluations of the Newton polynomial of Figure 11a.


Figure 12a. An interpolation of six randomly generated points on [0, 1] × (1, 2).


Figure 12b. The absolute errors of evaluations of the Newton polynomial of Figure 12a.


Figure 13a. An interpolation of six randomly generated points on [0, 1] × (1, 2).


Figure 13b. The absolute errors of evaluations of the Newton polynomial of Figure 13a.


Figure 13c. The absolute errors of Figure 13b restricted to [0, 1e-15].


Figure 14a. An interpolation of six randomly generated points on [0, 1] × (1, 2).


Figure 14b. The absolute errors of evaluations of the Newton polynomial of Figure 14a.


Figure 15a. An interpolation of six randomly generated points on [0, 1] × (1, 2).


Figure 15b. The absolute errors of evaluations of the Newton polynomial of Figure 15a.


Figure 16a. An interpolation of six randomly generated points on [0, 1] × (1, 2).


Figure 16b. The absolute errors of evaluations of the Newton polynomial of Figure 16a.


Figure 16c. The absolute errors of Figure 16b restricted to [0, 1e-15].

Nine Random Points

Finally, on nine randomly generated points on the region [0, 1] × (1, 2), the errors begin to grow significantly. The points for Figures 17a through 23a are given here:

  • Figure 17: (0,1.5334052315603035055), (0.083516686994091260399,1.4983148819293430343), (0.15129669124121358781,1.1140910913767716472), (0.34719113609290136457,1.1663332228392051526), (0.49945569859925326162,1.930099467248702183), (0.66632882157502304477,1.8065926026583614128), (0.77775605957185400818,1.7242736484502785288), (0.97758282034811427863,1.6542704453013235), (1,1.097621076785782801)
  • Figure 18: (0,1.1628119704140404966), (0.034863686604428359428,1.7627920544533022262), (0.17935682256143925528,1.1856671484120502313), (0.29946150431783541412,1.1284441394398194713), (0.56403540027914889077,1.9814219693566774705), (0.70374846477901287223,1.9792464421965398902), (0.78158276471383070216,1.161633527912960151), (0.9638039134274255515,1.8182921269062404246), (1,1.5771051359256287316)
  • Figure 19: (0,1.5906014491760178675), (0.095282852095350881183,1.7437367531208958216), (0.2654133318562788002,1.7896527782034374887), (0.34930046391308194886,1.2512242241069786441), (0.56191607371327945142,1.9703634581390598868), (0.58607148858735202968,1.6589865724830825666), (0.80702898868553896161,1.0538805239153470339), (0.87106495377856807405,1.1913602087606489643), (1,1.37111891311179801)
  • Figure 20: (0,1.6223498487949137292), (0.13256065912863537748,1.4532344348045227456), (0.21129730400224092102,1.6091691686814506568), (0.40392591909555197738,1.5797679338509997837), (0.4566423009679583811,1.0326278289000634381), (0.69590656478432577625,1.3172303146297252852), (0.82365607894462089522,1.2316017021572225332), (0.88440952837140340836,1.3613162070332636144), (1,1.9230338954008341368)
  • Figure 21: (0,1.1438096361904450671), (0.053027004693447815642,1.4696462449942000461), (0.24368916762632344963,1.0053752786504921435), (0.42544298193138763153,1.991712867744133364), (0.45068041801683889069,1.1121663889438688777), (0.63441875759518384648,1.2161202496924066185), (0.79133363956448055099,1.9139940328495548272), (0.87683116951543693673,1.9873256590158332457), (1,1.1417815248210827495)
  • Figure 22: (0,1.0026363795635460097), (0.09202692575514506701,1.8242843564712836191), (0.18080346580765238595,1.0727525414306449125), (0.29699170802845897832,1.6330396014419568118), (0.52900324094661532737,1.1613324094383663532), (0.57965709888094241187,1.9285518075006788941), (0.74450561665075298823,1.3772982756501521706), (0.88456029612517261818,1.0901006875047929423), (1,1.1453677551566472381)
  • Figure 23: (0,1.8305133538462750042), (0.084430184986376555223,1.8908553001893941836), (0.22939469582838689643,1.0874866308120483271), (0.3175045334482919368,1.0212151794793153936), (0.48759500059785887416,1.2494864776960976638), (0.631118700867374538,1.56457439789761521), (0.78559306214025714787,1.5500390271423565292), (0.90471860961543060231,1.271376279774762752), (1,1.7761600677744300292)

The absolute errors are shown in Figures 17b through 23b and restrictions to errors on the range [0, 1e-15] are shown in Figures 17c through 23c.

The MSE for the dynamically evaluated polynomials continue to remain low; however, in one case, Figure 21b, the MSE jumps significantly due likely to the significantly larger oscillations. The maximum error with forward or backward evaluation is as much as two orders of magnitude larger that of dynamic evaluation for the example in Figures 22a-c. The MSEs are listed in Table 4.

Table 4. Mean-squared Error of the evaluation of Newton polynomials on nine points.

DynamicForwardBackward
Figure 178.36e-172.63e-154.07e-15
Figure 189.33e-175.79e-158.57e-15
Figure 191.26e-163.98e-153.45e-15
Figure 209.44e-174.23e-153.68e-15
Figure 212.63e-161.36e-141.17e-14
Figure 221.53e-162.56e-146.33e-15
Figure 236.91e-171.99e-151.53e-15


Figure 17a. An interpolation of nine randomly generated points on [0, 1] × (1, 2).


Figure 17b. The absolute errors of evaluations of the Newton polynomial of Figure 17a.


Figure 17c. The absolute errors of Figure 17b restricted to [0, 1e-15].

image missing
Figure 18a. An interpolation of nine randomly generated points on [0, 1] × (1, 2).


Figure 18b. The absolute errors of evaluations of the Newton polynomial of Figure 18a.


Figure 18c. The absolute errors of Figure 18b restricted to [0, 1e-15].


Figure 19a. An interpolation of nine randomly generated points on [0, 1] × (1, 2).


Figure 19b. The absolute errors of evaluations of the Newton polynomial of Figure 19a.


Figure 19c. The absolute errors of Figure 19b restricted to [0, 1e-15].


Figure 20a. An interpolation of nine randomly generated points on [0, 1] × (1, 2).


Figure 20b. The absolute errors of evaluations of the Newton polynomial of Figure 20a.


Figure 20c. The absolute errors of Figure 20b restricted to [0, 1e-15].


Figure 21a. An interpolation of nine randomly generated points on [0, 1] × (1, 2).


Figure 21b. The absolute errors of evaluations of the Newton polynomial of Figure 21a.


Figure 21c. The absolute errors of Figure 21b restricted to [0, 1e-15].


Figure 22a. An interpolation of nine randomly generated points on [0, 1] × (1, 2).


Figure 22b. The absolute errors of evaluations of the Newton polynomial of Figure 22a.


Figure 22c. The absolute errors of Figure 22b restricted to [0, 1e-15].


Figure 23a. An interpolation of nine randomly generated points on [0, 1] × (1, 2).


Figure 23b. The absolute errors of evaluations of the Newton polynomial of Figure 23a.


Figure 23c. The absolute errors of Figure 23b restricted to [0, 1e-15].