Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Différences divisées
Résumé
In mathematics, divided differences is an algorithm, historically used for computing tables of logarithms and trigonometric functions. Charles Babbage's difference engine, an early mechanical calculator, was designed to use this algorithm in its operation.
Divided differences is a recursive division process. Given a sequence of data points , the method calculates the coefficients of the interpolation polynomial of these points in the Newton form.
Given n + 1 data points
where the are assumed to be pairwise distinct, the forward divided differences are defined as:
To make the recursive process of computation clearer, the divided differences can be put in tabular form, where the columns correspond to the value of j above, and each entry in the table is computed from the difference of the entries to its immediate lower left and to its immediate upper left, divided by a difference of corresponding x-values:
Note that the divided difference depends on the values and , but the notation hides the dependency on the x-values. If the data points are given by a function f,
one sometimes writes the divided difference in the notation
Other notations for the divided difference of the function ƒ on the nodes x0, ..., xn are:
Divided differences for and the first few values of :
Linearity
Leibniz rule
Divided differences are symmetric: If is a permutation then
Polynomial interpolation in the Newton form: if is a polynomial function of degree , and is the divided difference, then
If is a polynomial function of degree , then
Mean value theorem for divided differences: if is n times differentiable, then for a number in the open interval determined by the smallest and largest of the 's.
The divided difference scheme can be put into an upper triangular matrix:
Then it holds
if is a scalar
This follows from the Leibniz rule. It means that multiplication of such matrices is commutative. Summarised, the matrices of divided difference schemes with respect to the same set of nodes x form a commutative ring.
Since is a triangular matrix, its eigenvalues are obviously .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.