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.


 

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

49492. Проект ОКС 7 на ГТС с УВС 1.27 MB
  Список всех возможных нормальных сигнальных маршрутов сети ОКС для каждой пары пунктов сигнализации ПСi ПСj формируется по следующим правилам: нормальный маршрут должен быть либо прямым без транзитов либо если прямых маршрутов нет проходить через минимальное число транзитных пунктов STP SP STP. телефонным Указатель выбранных нормальных маршрутов Исх i Вхд j...
49493. Vетоды проектирования линейной части цифровой волоконно-оптической системы передачи данных 1.3 MB
  Разработана линейная часть волоконнооптической системы передачи данных со следующими параметрами: а число каналов 4320 288 из них не заняты; б рабочая длины волны 1310 мкм; в протяженностью трассы 612 км; г метод прокладки: подвес вдоль ж д; д минимальный энергетический запас 4 дБ; е компенсация дисперсии на трассе не требуется; ж оптическое волокно марки OFS llWve; з марка кабеля ОФС ДТ 865 8; и семь регенерационных пунктов; к избыточностью системы 67; л стоимостью каналокилометра: ; м коэффициентом готовности 0. Так...
49495. Определение в планируемом периоде количества ТО и КР 287.5 KB
  Каждому типу машин присуще свое определенное распределение трудоемкости по видам работ. Удельный вес видов работ в общем, объеме трудоемкость остается без существенных изменений, несмотря на совершенствование технологии ремонта и снижение общих трудозатрат на ремонт машин данного типа.
49496. Разработка стенда для диагностирования системы охлаждения 1.15 MB
  Ремонтно-механические мастерские, как правило, работают в одну смену, и только при большой загрузке и в целях лучшего использования дорогостоящего оборудования механические отделения и некоторые другие участки иногда работают в две смены.
49497. Проект ОКС 7 на ГТС с УВС и УИС 717 KB
  ОКС7 предоставляет универсальную структуру для организации сигнализации сообщений сетевого взаимодействия и технического обслуживания телефонной сети. SS5 и более ранние версии использовали принцип сигнализации в линии где информация необходимая для соединения передавалась специальными тонами DTMF в телефонной линии известной как Bканал. Такой тип сигнализации создавал уязвимость в безопасности протокола поскольку злоумышленник мог эмулировать набор служебных...
49498. Система автоматического регулирования частоты вращения ДПТ 857 KB
  Область применения системы. Принцип работы системы. Передаточные функции системы. Анализ структурной устойчивости САР 20 Коэффициент усиления системы в разомкнутом состоянии.
49499. РАЗРАБОТКА ТЕХНОЛОГИЧЕСКОГО ПРОЦЕССА ИЗГОТОВЛЕНИЯ ДЕТАЛИ 671 KB
  Физическая сущность процесса сварки заключается в образовании прочных связей между атомами или молекулами на соединяемых поверхностях заготовок. Экономическая эффективность применения сварки по сравнению с механическими способами соединения деталей и литьем заключается в экономии металла снижении трудоемкости работ и технологической гибкости процесса.д Все способы сварки условно делятся на две группы. К первой относятся способы сварки при которых соединение получается за счет расплавления металла.