solution of equations by divided difference interpolaton


Divided diference interpolation can be used to obtain approximate solutions to equations and to invert functionsMathworldPlanetmath numerically. The idea is that, given an equation f(y)=x which we want to solve for y, we first take several numbers y1,,yn and compute x1xn as xi=f(yi). Then we compute the divided differencesDlmfMathworldPlanetmath of the yi’s regarded as functions of the xi’s and form the divided difference series. Substituting x in this series provides an approximation to y.

To illustrate how this works, we will examine the transcendental equation x+e-x=2. We note that 2+e-2=2.13533 and 1.5+e-1.5=1.72313, so there will be a solution between 1.5 and 2, likely closer to 2 than 1.5. Therefore, as our values of the yi’s, we shall take 1.5, 1.6, 1.7, 1.8, 1.9, 2.0, 2.1. We now tabulate xi=yi+e-yi for those values:

yi xi
1.5 1.72313
1.6 1.80190
1.7 1.88268
1.8 1.96530
1.9 2.04957
2.0 2.13533
2.1 2.22246

Next, we form a divided difference table of the yi’s as a function of the xi’s:

1.723131.500001.269521.801901.60000-0.197991.237930.120821.882681.70000-0.16873-0.0396091.210360.107890.0915531.965301.80000-0.14201-0.077347-0.134571.186660.082100.0243602.049571.90000-0.12127-0.0671021.166040.059302.135332.00000-0.106021.147712.222462.10000

From this table, we form the series

1.50000 +1.26952(x-1.72313)-0.19799(x-1.72313)(x-1.80190)
+0.12082(x-1.72313)(x-1.80190)(x-1.88268)
-0.039609(x-1.72313)(x-1.80190)(x-1.88268)(x-1.96530)
+0.091553(x-1.72313)(x-1.80190)(x-1.88268)(x-1.96530)(x-2.04957)
-0.13457(x-1.72313)(x-1.80190)(x-1.88268)(x-1.96530)(x-2.04957)(x-2.13533)

Substituting 2.00000 for x, we obtain 1.84140. Given that

1.84140+e-1.84140<2<1.84141+e-1.84141,

this answer is correct to all 5 decimal places.

In the presentation above, we tacitly assumed that there was a solution to our equation and focussed our attention on finding that answer numerically. To completePlanetmathPlanetmathPlanetmath the treatment we will now show that there indeed exists a unique solution to the equation x+e-x=2 in the interval (0,).

Existence follows from the intermediate value theorem. As noted above,

1.5+e-1.5<2<3+e-2.

Since x+e-x depends continuously on x, it follows that there exists x(1.5,2) such that x+e-x=2.

As for uniqueness, note that the derivativePlanetmathPlanetmath of x+e-x is 1-e-x. When x>0, we have e-x<1, or 1-e-x>0. Hence, x+e-x is a strictly increaing function of x, so there can be at most one x such that x+e-x=2.

Title solution of equations by divided difference interpolaton
Canonical name SolutionOfEquationsByDividedDifferenceInterpolaton
Date of creation 2013-03-22 16:49:22
Last modified on 2013-03-22 16:49:22
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 16
Author rspuzio (6075)
Entry type Application
Classification msc 39A70