1835:
Lyness and Moler showed in 1966 that using undetermined coefficients for the polynomials in
Neville's algorithm, one can compute the Maclaurin expansion of the final interpolating polynomial, which yields numerical approximations for the derivatives of the function at the origin. While "this process
1778:
1836:
requires more arithmetic operations than is required in finite difference methods", "the choice of points for function evaluation is not restricted in any way". They also show that their method can be applied directly to the solution of linear systems of the
Vandermonde type.
506:
1517:
1821:
1472:
549:
277:
1344:
1191:
946:
747:
640:
1509:
314:
1285:
1237:
1132:
1086:
1038:
992:
887:
841:
793:
688:
322:
1864:
1773:{\displaystyle p'_{i,j}(x)={\frac {(x_{j}-x)p'_{i,j-1}(x)-p_{i,j-1}(x)+(x-x_{i})p'_{i+1,j}(x)+p_{i+1,j}(x)}{x_{j}-x_{i}}},\,}
1874:
J. N. Lyness and C.B. Moler, Van Der Monde
Systems and Numerical Differentiation, Numerische Mathematik 8 (1966) 458-464 (
21:
1784:
512:
1925:
223:
1293:
1140:
895:
696:
589:
1478:
1422:
283:
1920:
48:
138:
This polynomial exists and it is unique. Neville's algorithm evaluates the polynomial at some point
44:
25:
1247:
1199:
1094:
1048:
1000:
954:
849:
803:
755:
650:
579:= 4, one can use the recurrence to fill the triangular tableau below from the left to the right.
501:{\displaystyle p_{i,j}(x)={\frac {(x-x_{i})p_{i+1,j}(x)-(x-x_{j})p_{i,j-1}(x)}{x_{j}-x_{i}}},\,}
1893:
1860:
1854:
40:
52:
1896:
1402:
1394:
1914:
36:
which goes through the given points. Neville's algorithm evaluates this polynomial.
1875:
1881:
Neville, E.H.: Iterative interpolation. J. Indian Math. Soc.20, 87–120 (1934)
1901:
1847:
1846:
Press, William; Saul
Teukolsky; William Vetterling; Brian Flannery (1992).
1412:
The derivative of the polynomial can be obtained in the same manner, i.e:
1409:) floating point operations to interpolate a polynomial of degree n.
43:
of the interpolating polynomial and the recursion relation for the
572:), which is the value being sought. This is Neville's algorithm.
1401:) floating point operations to interpolate a single point, and
1848:"§3.1 Polynomial Interpolation and Extrapolation (encrypted)"
94:
are the same, the interpolating polynomial is the polynomial
1856:
Numerical
Recipes in C. The Art of Scientific Computing
1787:
1520:
1481:
1425:
1296:
1250:
1202:
1143:
1097:
1051:
1003:
957:
898:
852:
806:
758:
699:
653:
592:
515:
325:
286:
226:
32:+ 1 points, there is a unique polynomial of degree
1815:
1772:
1503:
1466:
1338:
1279:
1231:
1185:
1126:
1080:
1032:
986:
940:
881:
835:
787:
741:
682:
634:
543:
500:
308:
271:
1364:), the value of the polynomial going through the
8:
1859:(2nd ed.). Cambridge University Press.
1812:
1786:
1769:
1757:
1744:
1711:
1674:
1661:
1618:
1581:
1562:
1552:
1525:
1519:
1500:
1480:
1463:
1430:
1424:
1335:
1329:
1301:
1295:
1276:
1255:
1249:
1228:
1207:
1201:
1182:
1176:
1148:
1142:
1123:
1102:
1096:
1077:
1056:
1050:
1029:
1008:
1002:
983:
962:
956:
937:
931:
903:
897:
878:
857:
851:
832:
811:
805:
784:
763:
757:
738:
732:
704:
698:
679:
658:
652:
631:
625:
597:
591:
540:
514:
497:
485:
472:
439:
426:
383:
370:
354:
330:
324:
305:
285:
268:
259:
231:
225:
1831:Application to numerical differentiation
24:that was derived by the mathematician
1816:{\displaystyle 0\leq i<j\leq n.\,}
544:{\displaystyle 0\leq i<j\leq n.\,}
7:
39:Neville's algorithm is based on the
272:{\displaystyle p_{i,i}(x)=y_{i},\,}
1339:{\displaystyle p_{4,4}(x)=y_{4}\,}
1186:{\displaystyle p_{3,3}(x)=y_{3}\,}
941:{\displaystyle p_{2,2}(x)=y_{2}\,}
742:{\displaystyle p_{1,1}(x)=y_{1}\,}
635:{\displaystyle p_{0,0}(x)=y_{0}\,}
14:
1504:{\displaystyle 0\leq i\leq n,\,}
1467:{\displaystyle p'_{i,i}(x)=0,\,}
309:{\displaystyle 0\leq i\leq n,\,}
213:satisfy the recurrence relation
158:denote the polynomial of degree
166:which goes through the points (
55:), which is nowadays not used.
1735:
1729:
1701:
1695:
1667:
1648:
1642:
1636:
1608:
1602:
1574:
1555:
1546:
1540:
1451:
1445:
1319:
1313:
1273:
1267:
1225:
1219:
1166:
1160:
1120:
1114:
1074:
1068:
1026:
1020:
980:
974:
921:
915:
875:
869:
829:
823:
781:
775:
722:
716:
676:
670:
615:
609:
558:This recurrence can calculate
463:
457:
432:
413:
407:
401:
376:
357:
348:
342:
249:
243:
1:
1280:{\displaystyle p_{3,4}(x)\,}
1232:{\displaystyle p_{2,4}(x)\,}
1127:{\displaystyle p_{1,4}(x)\,}
1081:{\displaystyle p_{2,3}(x)\,}
1033:{\displaystyle p_{0,4}(x)\,}
987:{\displaystyle p_{1,3}(x)\,}
882:{\displaystyle p_{0,3}(x)\,}
836:{\displaystyle p_{1,2}(x)\,}
788:{\displaystyle p_{0,2}(x)\,}
683:{\displaystyle p_{0,1}(x)\,}
1942:
20:is an algorithm used for
22:polynomial interpolation
1876:doi:10.1007/BF02166671
1817:
1774:
1505:
1468:
1340:
1281:
1233:
1187:
1128:
1082:
1034:
988:
942:
883:
837:
789:
743:
684:
636:
545:
502:
310:
273:
1897:"Neville's Algorithm"
1818:
1775:
1506:
1469:
1393:This algorithm needs
1353:This process yields
1341:
1282:
1234:
1188:
1129:
1083:
1035:
989:
943:
884:
838:
790:
744:
685:
637:
546:
503:
311:
274:
1785:
1518:
1479:
1423:
1294:
1248:
1200:
1141:
1095:
1049:
1001:
955:
896:
850:
804:
756:
697:
651:
590:
513:
323:
284:
224:
1694:
1601:
1539:
1444:
47:. It is similar to
45:divided differences
26:Eric Harold Neville
18:Neville's algorithm
1894:Weisstein, Eric W.
1813:
1770:
1670:
1577:
1521:
1501:
1464:
1426:
1336:
1277:
1229:
1183:
1124:
1078:
1030:
984:
938:
879:
833:
785:
739:
680:
632:
575:For instance, for
541:
498:
306:
269:
102:with the property
98:of degree at most
49:Aitken's algorithm
1866:978-0-521-43108-8
1826:
1825:
1764:
1368:+ 1 data points (
1349:
1348:
554:
553:
492:
1933:
1907:
1906:
1870:
1852:
1822:
1820:
1819:
1814:
1779:
1777:
1776:
1771:
1765:
1763:
1762:
1761:
1749:
1748:
1738:
1728:
1727:
1690:
1666:
1665:
1635:
1634:
1597:
1567:
1566:
1553:
1535:
1510:
1508:
1507:
1502:
1473:
1471:
1470:
1465:
1440:
1417:
1416:
1345:
1343:
1342:
1337:
1334:
1333:
1312:
1311:
1286:
1284:
1283:
1278:
1266:
1265:
1238:
1236:
1235:
1230:
1218:
1217:
1192:
1190:
1189:
1184:
1181:
1180:
1159:
1158:
1133:
1131:
1130:
1125:
1113:
1112:
1087:
1085:
1084:
1079:
1067:
1066:
1039:
1037:
1036:
1031:
1019:
1018:
993:
991:
990:
985:
973:
972:
947:
945:
944:
939:
936:
935:
914:
913:
888:
886:
885:
880:
868:
867:
842:
840:
839:
834:
822:
821:
794:
792:
791:
786:
774:
773:
748:
746:
745:
740:
737:
736:
715:
714:
689:
687:
686:
681:
669:
668:
641:
639:
638:
633:
630:
629:
608:
607:
584:
583:
550:
548:
547:
542:
507:
505:
504:
499:
493:
491:
490:
489:
477:
476:
466:
456:
455:
431:
430:
400:
399:
375:
374:
355:
341:
340:
315:
313:
312:
307:
278:
276:
275:
270:
264:
263:
242:
241:
218:
217:
67:+1 data points (
53:Alexander Aitken
16:In mathematics,
1941:
1940:
1936:
1935:
1934:
1932:
1931:
1930:
1911:
1910:
1892:
1891:
1888:
1867:
1850:
1845:
1842:
1833:
1783:
1782:
1753:
1740:
1739:
1707:
1657:
1614:
1558:
1554:
1516:
1515:
1477:
1476:
1421:
1420:
1386:) at the point
1385:
1376:
1359:
1325:
1297:
1292:
1291:
1251:
1246:
1245:
1203:
1198:
1197:
1172:
1144:
1139:
1138:
1098:
1093:
1092:
1052:
1047:
1046:
1004:
999:
998:
958:
953:
952:
927:
899:
894:
893:
853:
848:
847:
807:
802:
801:
759:
754:
753:
728:
700:
695:
694:
654:
649:
648:
621:
593:
588:
587:
567:
511:
510:
481:
468:
467:
435:
422:
379:
366:
356:
326:
321:
320:
282:
281:
255:
227:
222:
221:
212:
183:
174:
157:
126:
117:
93:
85:) where no two
84:
75:
63:Given a set of
61:
28:in 1934. Given
12:
11:
5:
1939:
1937:
1929:
1928:
1923:
1913:
1912:
1909:
1908:
1887:
1886:External links
1884:
1883:
1882:
1879:
1872:
1865:
1841:
1838:
1832:
1829:
1828:
1827:
1824:
1823:
1811:
1808:
1805:
1802:
1799:
1796:
1793:
1790:
1780:
1768:
1760:
1756:
1752:
1747:
1743:
1737:
1734:
1731:
1726:
1723:
1720:
1717:
1714:
1710:
1706:
1703:
1700:
1697:
1693:
1689:
1686:
1683:
1680:
1677:
1673:
1669:
1664:
1660:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1633:
1630:
1627:
1624:
1621:
1617:
1613:
1610:
1607:
1604:
1600:
1596:
1593:
1590:
1587:
1584:
1580:
1576:
1573:
1570:
1565:
1561:
1557:
1551:
1548:
1545:
1542:
1538:
1534:
1531:
1528:
1524:
1512:
1511:
1499:
1496:
1493:
1490:
1487:
1484:
1474:
1462:
1459:
1456:
1453:
1450:
1447:
1443:
1439:
1436:
1433:
1429:
1381:
1372:
1357:
1351:
1350:
1347:
1346:
1332:
1328:
1324:
1321:
1318:
1315:
1310:
1307:
1304:
1300:
1288:
1287:
1275:
1272:
1269:
1264:
1261:
1258:
1254:
1243:
1240:
1239:
1227:
1224:
1221:
1216:
1213:
1210:
1206:
1195:
1193:
1179:
1175:
1171:
1168:
1165:
1162:
1157:
1154:
1151:
1147:
1135:
1134:
1122:
1119:
1116:
1111:
1108:
1105:
1101:
1090:
1088:
1076:
1073:
1070:
1065:
1062:
1059:
1055:
1044:
1041:
1040:
1028:
1025:
1022:
1017:
1014:
1011:
1007:
996:
994:
982:
979:
976:
971:
968:
965:
961:
950:
948:
934:
930:
926:
923:
920:
917:
912:
909:
906:
902:
890:
889:
877:
874:
871:
866:
863:
860:
856:
845:
843:
831:
828:
825:
820:
817:
814:
810:
799:
796:
795:
783:
780:
777:
772:
769:
766:
762:
751:
749:
735:
731:
727:
724:
721:
718:
713:
710:
707:
703:
691:
690:
678:
675:
672:
667:
664:
661:
657:
646:
643:
642:
628:
624:
620:
617:
614:
611:
606:
603:
600:
596:
562:
556:
555:
552:
551:
539:
536:
533:
530:
527:
524:
521:
518:
508:
496:
488:
484:
480:
475:
471:
465:
462:
459:
454:
451:
448:
445:
442:
438:
434:
429:
425:
421:
418:
415:
412:
409:
406:
403:
398:
395:
392:
389:
386:
382:
378:
373:
369:
365:
362:
359:
353:
350:
347:
344:
339:
336:
333:
329:
317:
316:
304:
301:
298:
295:
292:
289:
279:
267:
262:
258:
254:
251:
248:
245:
240:
237:
234:
230:
204:
179:
170:
149:
136:
135:
122:
113:
89:
80:
71:
60:
57:
13:
10:
9:
6:
4:
3:
2:
1938:
1927:
1926:Interpolation
1924:
1922:
1919:
1918:
1916:
1904:
1903:
1898:
1895:
1890:
1889:
1885:
1880:
1877:
1873:
1871:(link is bad)
1868:
1862:
1858:
1857:
1849:
1844:
1843:
1839:
1837:
1830:
1809:
1806:
1803:
1800:
1797:
1794:
1791:
1788:
1781:
1766:
1758:
1754:
1750:
1745:
1741:
1732:
1724:
1721:
1718:
1715:
1712:
1708:
1704:
1698:
1691:
1687:
1684:
1681:
1678:
1675:
1671:
1662:
1658:
1654:
1651:
1645:
1639:
1631:
1628:
1625:
1622:
1619:
1615:
1611:
1605:
1598:
1594:
1591:
1588:
1585:
1582:
1578:
1571:
1568:
1563:
1559:
1549:
1543:
1536:
1532:
1529:
1526:
1522:
1514:
1513:
1497:
1494:
1491:
1488:
1485:
1482:
1475:
1460:
1457:
1454:
1448:
1441:
1437:
1434:
1431:
1427:
1419:
1418:
1415:
1414:
1413:
1410:
1408:
1404:
1400:
1396:
1391:
1389:
1384:
1380:
1375:
1371:
1367:
1363:
1356:
1330:
1326:
1322:
1316:
1308:
1305:
1302:
1298:
1290:
1289:
1270:
1262:
1259:
1256:
1252:
1244:
1242:
1241:
1222:
1214:
1211:
1208:
1204:
1196:
1194:
1177:
1173:
1169:
1163:
1155:
1152:
1149:
1145:
1137:
1136:
1117:
1109:
1106:
1103:
1099:
1091:
1089:
1071:
1063:
1060:
1057:
1053:
1045:
1043:
1042:
1023:
1015:
1012:
1009:
1005:
997:
995:
977:
969:
966:
963:
959:
951:
949:
932:
928:
924:
918:
910:
907:
904:
900:
892:
891:
872:
864:
861:
858:
854:
846:
844:
826:
818:
815:
812:
808:
800:
798:
797:
778:
770:
767:
764:
760:
752:
750:
733:
729:
725:
719:
711:
708:
705:
701:
693:
692:
673:
665:
662:
659:
655:
647:
645:
644:
626:
622:
618:
612:
604:
601:
598:
594:
586:
585:
582:
581:
580:
578:
573:
571:
566:
561:
537:
534:
531:
528:
525:
522:
519:
516:
509:
494:
486:
482:
478:
473:
469:
460:
452:
449:
446:
443:
440:
436:
427:
423:
419:
416:
410:
404:
396:
393:
390:
387:
384:
380:
371:
367:
363:
360:
351:
345:
337:
334:
331:
327:
319:
318:
302:
299:
296:
293:
290:
287:
280:
265:
260:
256:
252:
246:
238:
235:
232:
228:
220:
219:
216:
215:
214:
211:
207:
203:
199:
195:
191:
187:
182:
178:
173:
169:
165:
161:
156:
152:
148:
143:
141:
134:
130:
125:
121:
116:
112:
108:
105:
104:
103:
101:
97:
92:
88:
83:
79:
74:
70:
66:
59:The algorithm
58:
56:
54:
51:(named after
50:
46:
42:
37:
35:
31:
27:
23:
19:
1900:
1855:
1834:
1411:
1406:
1398:
1392:
1387:
1382:
1378:
1373:
1369:
1365:
1361:
1354:
1352:
576:
574:
569:
564:
559:
557:
209:
205:
201:
197:
193:
189:
185:
180:
176:
171:
167:
163:
159:
154:
150:
146:
144:
139:
137:
132:
128:
123:
119:
114:
110:
106:
99:
95:
90:
86:
81:
77:
72:
68:
64:
62:
38:
33:
29:
17:
15:
1921:Polynomials
41:Newton form
1915:Categories
1840:References
196:+ 1, ...,
1902:MathWorld
1804:≤
1792:≤
1751:−
1655:−
1629:−
1612:−
1592:−
1569:−
1492:≤
1486:≤
532:≤
520:≤
479:−
450:−
420:−
411:−
364:−
297:≤
291:≤
1692:′
1599:′
1537:′
1442:′
162:−
131:= 0,...,
127:for all
200:. The
1863:
184:) for
1851:(PDF)
1861:ISBN
1798:<
526:<
145:Let
118:) =
1358:0,4
34:≤ n
1917::
1899:.
1853:.
1390:.
1377:,
563:0,
192:,
188:=
175:,
142:.
76:,
1905:.
1878:)
1869:.
1810:.
1807:n
1801:j
1795:i
1789:0
1767:,
1759:i
1755:x
1746:j
1742:x
1736:)
1733:x
1730:(
1725:j
1722:,
1719:1
1716:+
1713:i
1709:p
1705:+
1702:)
1699:x
1696:(
1688:j
1685:,
1682:1
1679:+
1676:i
1672:p
1668:)
1663:i
1659:x
1652:x
1649:(
1646:+
1643:)
1640:x
1637:(
1632:1
1626:j
1623:,
1620:i
1616:p
1609:)
1606:x
1603:(
1595:1
1589:j
1586:,
1583:i
1579:p
1575:)
1572:x
1564:j
1560:x
1556:(
1550:=
1547:)
1544:x
1541:(
1533:j
1530:,
1527:i
1523:p
1498:,
1495:n
1489:i
1483:0
1461:,
1458:0
1455:=
1452:)
1449:x
1446:(
1438:i
1435:,
1432:i
1428:p
1407:n
1405:(
1403:O
1399:n
1397:(
1395:O
1388:x
1383:i
1379:y
1374:i
1370:x
1366:n
1362:x
1360:(
1355:p
1331:4
1327:y
1323:=
1320:)
1317:x
1314:(
1309:4
1306:,
1303:4
1299:p
1274:)
1271:x
1268:(
1263:4
1260:,
1257:3
1253:p
1226:)
1223:x
1220:(
1215:4
1212:,
1209:2
1205:p
1178:3
1174:y
1170:=
1167:)
1164:x
1161:(
1156:3
1153:,
1150:3
1146:p
1121:)
1118:x
1115:(
1110:4
1107:,
1104:1
1100:p
1075:)
1072:x
1069:(
1064:3
1061:,
1058:2
1054:p
1027:)
1024:x
1021:(
1016:4
1013:,
1010:0
1006:p
981:)
978:x
975:(
970:3
967:,
964:1
960:p
933:2
929:y
925:=
922:)
919:x
916:(
911:2
908:,
905:2
901:p
876:)
873:x
870:(
865:3
862:,
859:0
855:p
830:)
827:x
824:(
819:2
816:,
813:1
809:p
782:)
779:x
776:(
771:2
768:,
765:0
761:p
734:1
730:y
726:=
723:)
720:x
717:(
712:1
709:,
706:1
702:p
677:)
674:x
671:(
666:1
663:,
660:0
656:p
627:0
623:y
619:=
616:)
613:x
610:(
605:0
602:,
599:0
595:p
577:n
570:x
568:(
565:n
560:p
538:.
535:n
529:j
523:i
517:0
495:,
487:i
483:x
474:j
470:x
464:)
461:x
458:(
453:1
447:j
444:,
441:i
437:p
433:)
428:j
424:x
417:x
414:(
408:)
405:x
402:(
397:j
394:,
391:1
388:+
385:i
381:p
377:)
372:i
368:x
361:x
358:(
352:=
349:)
346:x
343:(
338:j
335:,
332:i
328:p
303:,
300:n
294:i
288:0
266:,
261:i
257:y
253:=
250:)
247:x
244:(
239:i
236:,
233:i
229:p
210:j
208:,
206:i
202:p
198:j
194:i
190:i
186:k
181:k
177:y
172:k
168:x
164:i
160:j
155:j
153:,
151:i
147:p
140:x
133:n
129:i
124:i
120:y
115:i
111:x
109:(
107:p
100:n
96:p
91:i
87:x
82:i
78:y
73:i
69:x
65:n
30:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.