10989

Newton Interpolating Polynomial

Лекция

Математика и математический анализ

Newton Interpolating Polynomial Case 1: Constant Polynomial Only one xvalue is given in the table X x1 Y y1 Let P0x be the interpolating polynomial function. Hence P0x1 = y1. It passes through the one point x1y1 given in the table. Hence choose 6.1 Case 2: Linear Polynomial Two xvalues are given in the table ...

Английский

2013-04-03

76.5 KB

0 чел.

Newton Interpolating Polynomial

Case 1: Constant Polynomial Only one x-value is given in the table

X

x1

Y

y1

Let P0(x) be the interpolating polynomial function. Hence,
P0(x1) = y1. It passes through the one point (x1,y1) given in the table. Hence, choose

(6.1)

Case 2: Linear Polynomial Two x-values are given in the table

X

x1

x2

Y

y1

y2

Let P1(x) be the interpolating polynomial function. Hence, P1(x1) = y1, P1(x2) = y2. In this case P1(x) passes through the two points (x1,y1) and (x2,y2). Choose P1(x) as the straight. Hence the equation of the line is

where slope of the line we signify as

But y1 = P0(x) from equation (6.1). Therefore,

.   (6.2)

Case 3: Polynomial of order k

Let Pk-1(x) be the polynomial interpolating a table with k values as given below:

X

x1

x2

x3

...

xk

Y

y1

y2

y3

...

yk

So we have, Pk-1(x1) = y1,

 Pk-1(x2) = y2,

Pk-1(x3) = y3,

...

Pk-1(xk) = yk.

Consider Pk(x) defined as

. (6.3)

Note that (x - xi) is a factor of the second term for 1 <= i <= k, and hence the second term vanishes for x = xi for 1 <= i <= k. Also,

Pk(x1)=Pk-1(x1) = y1,

 Pk(x2)=Pk-1(x2) = y2,

...

Pk(xk)=Pk-1(xk) = yk.

Hence Pk(x) interpolates all the values Pk-1(x) interpolates. Suppose a table with k+1 values, x1, x2... xk, xk+1 is given as below:

X

x1

x2

x3

...

xk

xk+1

Y

y1

y2

y3

...

yk

yk+1

In order that Pk(x) interpolates the table, it should satisfy the last pair (xk+1, yk+1).

Hence,

,

,

.  (6.4)

Hence (see (6.3)),

,

interpolates a table of (k+1) values, where ck is given by (6.4).

Note 

 Pk(x) is a polynomial of order k defined recursively in terms of Pk-1(x), and the base case is given by P0(x) = y1.

 Pk(x) is known as Gregory-Newton interpolation polynomial.

Example

Using the Gregory-Newton polynomial, interpolate the following table and find the value of P4(3):

X

0

1

-1

2

-2

Y

-5

-3

-15

39

-9

Step 1 Constant Polynomial

Using the first pair (0,-5) we get the constant polynomial as

P0(x) = -5.

Graphing the constant function along with the point it interpolates we get the following figure.

Step 2 Linear Polynomial

The linear polynomial that interpolates the first two pairs (0, -5) and (1, -3) is given by:

P1(x) = P0(x) + c1(x - x1),

where c1 is given by (6.4):

.

Substituting for P0(x), c1 and x1, we get

P1(x) = -5 + 2x.

Graphing the linear function along with the points it interpolates we get the Figure 6.3.

Step 3 Quadratic Polynomial

The Quadratic polynomial that interpolates the first three pairs
(0, -5), (1, -3) and (-1, -15) is given by:

P2(x) = P1(x) + c2(x - x1) (x - x2).

Substituting for P1(x), x1 and x2, we get

P2(x) = -5 + 2x + c2(x - 0) (x - 1).

P2(x) interpolates (-1,-15). Hence,

-15 = -5 + 2(-1) + c2(-1)(-2),   2c2 = -8  c2 = -4.

So we have the quadratic polynomial

P2(x) = -5 + 2x -4x(x-1).

Graphing the quadratic function along with the points it interpolates we get the following figure.

Step 4 Cubic Polynomial

The Cubic polynomial that interpolates the first four pairs (0, -5), (1, -3), (-1, -15) and (2, 39) is given by:

P3(x) = P2(x) + c3(x - x1) (x - x2) (x - x3).

Substituting for P2(x), x1, x2 and x3, we get

P3(x) = -5 + 2x -4x(x - 1) + c3(x - 0) (x - 1)(x + 1).

P3(x) interpolates (2, 39). Hence,

39 = -5 + 2(2) - 4(2)(2-1) + c32(2-1)(2+1),

6c3 = 39 + 9 c3 = 48/6 = 8.

P3(x) = -5 + 2x -4x(x - 1)+8x(x - 1)(x + 1).

Illustrating the cubic function along with the points it interpolates we get the following figure.

Step 5 Polynomial of order 4

The polynomial of order 4 that interpolates all the five pairs
(0, -5), (1, -3), (-1, -15), (2, 39) and (-2, -9) is given by:

P4(x) = P3(x) + c4(x - x1) (x - x2) (x - x3)(x - x4).

Substituting for P3(x), x1, x2, x3,and x4, we get

P4(x) = -5 + 2x - 4x(x - 1) + 8x(x - 1)(x + 1) +

+ c4(x - 0) (x - 1)(x + 1)(x - 2).

Substituting for point (-2, -9) in P4(x), we get

-9 = -5 + 2(-2) - 4(-2)(-2 - 1) +8(-2)(-2 - 1)(-2 + 1) +

+ c4(-2)(-2 -1)(-2 + 1)(-2 -2),

24c4 = -9 + 9 +24 +48,  c4 = 72/24 = 3.

P4(x) = -5 + 2x - 4x(x -1) + 8x(x -1)(x +1) + 3x(x -1)(x +1)(x - 2).

Graphing the biquadratic function along with the points it interpolates we get the following figure.

Figure 6.6. Biquadratic function – five points.

The polynomial P4(x) can be written in a nested form as follows:

P4(x) = -5 + 2x -4x(x - 1) + x(x - 1)(x + 1){8 + 3(x - 2)} =

= -5 +2x + x(x - 1){-4 + (x + 1){8 + 3(x - 2)}} =

= -5 + x{2 +(x - 1){-4 + (x + 1){8 +3(x - 2)}}}.

Step 6 Find the value of P4(3)

Using the nested form, we have:

P4(3) = - 5 + 3 (2 + (3 - 1)(-4 + (3 + 1) (8 + 3(3 - 2)))) =

= -5 + 3 (2 + (3 - 1)(-4 + (3 + 1)(8 + 3))) =

= -5 + 3 (2 + (3 - 1)(-4 + 44)) =

= -5 + 3 (2 + 80) =

= -5 + 246 =

= 241.


 

А также другие работы, которые могут Вас заинтересовать

61630. Умножение многозначного числа на однозначное 18.44 KB
  Цель: учить находить способы определения значений произведений, в которых один множитель – однозначное число, а второй – многозначное.
61631. Умножение однозначного числа на десяток и сотню 19.79 KB
  Момент Проверка домашнего задания Ребята давайте вспомним что мы проходили на прошлом уроке кто мне скажет что было Блиц-опрос Для счета предметов применяются числа натуральные Любое трехзначное число больше меньше двухзначного.
61632. Деление суммы на число 16.71 KB
  На сколько больше орехов он отдал сестре чем оставил себе Задание 6 устно Прочитайте задание. Оба способа решения дали одинаковые результаты Чем отличается решение Можно ли решениями поставить знак равно Правило Чтобы разделить сумму на число...
61633. Проценты 21.83 KB
  Узнайте массу бобра в кг Какие геометрические фигуры вы здесь видите Используя результаты вычислений ответьте на вопросы: правило умножения на 01 правило деления на 100 25 кг ц Какую часть от ц составляет кг 2.
61634. Вычитание в пределах 20 с переходом. Случаи (11-6-15-6-11-5-14-5) 20.03 KB
  Проверка домашнего задания.2 Выполнение задания на доске. Сперва пока они шли по тропинке на краю Дремучего Леса оба молчали; но когда они дошли до речки и стали помогать друг другу перебираться по камушкам им пришлось решить еще два задания.
61636. Музыкальные инструменты 28.51 KB
  Задачи урока: Образовательные: Научить ребят эмоционально осознанно целостно образно воспринимать выразительные возможности особенности тембровой окраски фортепиано: мир счастливого детства в интонациях темах и образах детских пьес...
61637. Диез. Бемоль. Бекар 17.08 KB
  Цель: Продолжить знакомство детей с музыкальной грамотой закрепить знания о знаках альтерации: диез бемоль бекар; Продолжить формировать умение внимательно слушать музыку рассказывать о содержании музыкального произведения...
61638. Темп как средство выразительности музыки 25.87 KB
  Цель: познакомить с таким средством музыкальной выразительности как темп. Задачи: Воспитывающая: на основе эмоционального восприятия музыки П.И. Чайковского «Неаполитанский танец», русский народный хороводная...