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.


 

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

77680. Физиологическое состояние и продуктивные качества цыплят-бройлеров при инъекции и аэрозольном применении гала-вета 190.5 KB
  Цель настоящей работы - дать физиологическую оценку эффективности использования при выращивании цыплят-бройлеров нового иммуномодулятора гала-вета как средства повышающего иммунную защиту организма выявить продуктивное действие оптимальные дозы и способы...
77681. Мониторы. Виды мониторов и их преимущества 108 KB
  Жидкий кристалл – это специфическое агрегатное состояние вещества, в котором оно проявляет одновременно свойства кристалла и жидкости. Сразу надо оговориться, что далеко не все вещества могут находиться в жидкокристаллическом состоянии.
77682. Цивилизационная концепция Н. Я. Данилевского 89.5 KB
  Исторические события ХХ века поставили под сомнение многие, казалось бы, прочно утвердившиеся научные концепции общественного развития. Прежде всего это относится к теориям общего для всего человечества постиндустриального развития, связанного с прогрессом развития средств производства...
77683. SATA 428.5 KB
  Теоретически ST 150 и ST 300 устройства должны быть совместимы как ST 300 контроллер и ST 150 устройство так и ST 150 контроллер и ST 300 устройство за счёт поддержки согласования скоростей в меньшую сторону однако для некоторых устройств и контроллеров требуется ручное выставление режима работы например на НЖМД фирмы Segte поддерживающих ST 300 для принудительного включения режима ST 150 предусмотрен специальный джампер. Разъём питания ST подаёт 3 напряжения питания: 12 В 5 В и 33 В; однако современные устройства могут...
77685. Устройство накопителя на жестких магнитных дисках 1.79 MB
  Головка чтения/записи в любом дисковом накопителе состоит из U-образного ферромагнитного сердечника и намотанной на него катушки (обмотки), по которой может протекать электрический ток. При пропускании тока через обмотку в сердечнике (магнитопроводе) головки создается магнитное поле. При переключении направления протекающего тока полярность магнитного поля также изменяется. В сущности, головки представляют собой электромагниты
77686. ОРГАНИЗАЦИЯ ЖЕСТКИХ ДИСКОВ 1.12 MB
  Функции BIOS для работы с жесткими дисками. Проблемы BIOS при работе с большими дисками. Структурная схема жесткого диска. Вдоль каждой поверхности каждого диска синхронно перемещаются магнитные головки обеспечивающая чтение и запись информации.
77687. Устройство жесткого диска 376 KB
  Накопитель на жестких магнитных дисках состоит из четырех главных элементов, каждый из которых вносит свой вклад в его общие характеристики. НЖМД состоит из собственно носителя (пакета дисковых пластин - платтеров, вращающихся наоси)
77688. Характеристики Жестких дисков 144.5 KB
  За 45 лет прошедших с момента появления первых устройств магнитного хранения данных поверхностная плотность записи выросла более чем в пять миллионов раз. Емкость накопителя С декабря 1998 года Международная электротехническая комиссия МЭК занимающаяся стандартизацией в области электротехники представила в качестве официального стандарта систему названий и символов единиц измерения для использования в области обработки и передачи данных. На основании этого значения можно сделать вывод об эффективности того или иного способа записи...