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.


 

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

319. Основы менеджмента и школы управленческой деятельности 115 KB
  Школа человеческих отношений. Хотторнские эксперименты. Критерии управленческого мастерства. Менеджмент как теория и практика. Модель стратегического управления. Сегментация рынка и позиционирование товара. Портфельная стратегия.
320. Оформление налоговых накладных и построение Декларации по НДС в системе 1С Предприятие 8.2 84.5 KB
  Принципы построения учета НДС в системе 1С Предприятие 8.2. Регистрация операций по входящему НДС. Экспорт отчетов в программу сдачи электронной отчетности. Выписка налоговой накладной и передача ее в Единый реестр.
321. Распознавание принадлежности объектов к заданным классам детерминированными методами 66.5 KB
  Принадлежность объектов к одному из заданных классов. Мера сходства между объектами aj и ak по одному количественному признаку. определение принадлежности заданного объекта к одному из классов по средней мере сходства этого объекта и объектов заданных классов.
322. Создание базы данных 315 KB
  Данная курсовая работа рассматривает создание базы данных Справочная ГИБДД. В курсовой работе разрабатывается БД, с помощью которой, можно будет вести отчет по любому водителю и его автомобилю.
323. Проектирование промышленного здания в Макеевке 227.5 KB
  Проектируемое здание предназначено для размещения основного производства, одноэтажное, с металлическим каркасом. Применяемый тип колон – сплошного сечения. Здание имеет II степень долговечности – срок службы составляет не менее 50 лет.
324. Малоэтажный жилой дом из мелкоразмерных элементов в г. Владимир 201 KB
  Индивидуальный мансардный одноквартирный 5-комнатный жилой дом с пристроенными гаражом и хозпостройкой. Здание имеет бескаркасную конструктивную схему с опиранием перекрытий на продольные и поперечные стены.
325. Теория международных отношений 697.39 KB
  Правовое регулирование МО. Социально-гуманитарные науки, изучающие мировые политические процессы, в качестве объекта исследования рассматривают общественные явления. Цели, средства и стратегии участников МО. Международное сотрудничество.
326. Исследование работы разрядной лампы с балластными сопротивлениями различных видов 86 KB
  Изучить влияние активного, индуктивного и ёмкостного балластного сопротивления на работу люминесцентной лампы. С увеличением коэффициента амплитуды резко снижается поток излучения лампы и срок службы электродов.
327. Анализ устойчивости элементов металлических конструкций 523 KB
  Коэффициент запаса устойчивости для данной стойки составляет. Значения критических усилий, определенные по методике СП, практически не отличаются от полученных в программе SCAD. Упругопластическая работа стержня с начальными несовершенствами.