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.


 

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

16798. Минералого-геохимические особенности поведения благородных металлов в условиях разнообразных природных систем 72 KB
  Минералого-геохимические особенности поведения благородных металлов в условиях разнообразных природных систем. К благородным металлам относятся золото и серебро, а также 6 элементов платиновой группы: рутений, родий, палладий, осмий, иридий и платина...
16799. Организация дежурной службы в частях пожарной охраны 53.05 KB
  Цель изучения темы – формирование у обучаемых соответствующей современным требованиям и нормам степени подготовленности, необходимых знаний, умений и навыков в области организации и несения службы в частях пожарной охраны и обеспечения пожарной безопасности.
16800. Минерально-сырьевой потенциал платиновых металлов России на пороге XXI века 316 KB
  Минеральносырьевой потенциал платиновых металлов России на пороге XXI века Н.М.Чернышов Д.А.Додин Воронежский государственный университет г.Воронеж ВНИИ Океангеология г.СанктПетербург Аннотация Предложена оригинальная классификация платиноидных ме
16801. Намывные россыпи как новый источник получения золота и платины 80 KB
  Намывные россыпи как новый источник получения золота и платины От редакции бюлл. Золотодобыча. Новое как известно часто является хорошо забытым старым. Нижеприведенная статья по мелкому золоту написана в 1932 году но мы уверены что она с интересом будет прочитана и сег...
16802. НОВЫЕ ТЕХНИКА И ТЕХНОЛОГИИ ОБОГАЩЕНИЯ ПЕСКОВ 225 KB
  НОВЫЕ ТЕХНИКА И ТЕХНОЛОГИИ ОБОГАЩЕНИЯ ПЕСКОВ Несмотря на снижение объема добычи золота из россыпей они продолжают оставаться наиболее выгодным объектом для промышленного освоения как в современных условиях так и в среднесрочной перспективе поскольку их минераль
16803. Стратегическое значение мелких месторождений коренного золота в Хабаровском крае и Амурской области 40 KB
  О стратегическом значении мелких месторождений коренного золота в Хабаровском крае и Амурской области Е.В.Нигай к.г.м.н ст.науч.сотр. ИГД ДВО РАН Золотодобыча №121 Декабрь 2008 Разведка и эксплуатация мелких месторождений коренного золота в пределах Дальнего Востока ...
16804. Обобщенная характеристика россыпей благородных металлов Приморья 46 KB
  Обобщенная характеристика россыпей благородных металлов Приморья Россыпи развитые на территории СихотэАлиня и Южного Приморья Иванов Хомич 1997 разделяются на монокомпонентные однометалльные одноэлементные и многокомпонентные комплексные. Последние охватыва
16805. Оборудование для добычи золота 1.83 MB
  Оборудование для добычи золота 8ми футовая машина Может устанавливаться на берегу или на понтонах легко подготавливается к перевозке любым транспортом. В конструкции нет вибраторов что упрощает эксплуатацию и повышает надёжность.Оптимальный ...
16806. Оборудование для пробоподготовки 1.32 MB
  Оборудование для пробоподготовки Кольцевые мельницы НАСТОЛЬНАЯ КОЛЬЦЕВАЯ МЕЛЬНИЦА Компактная и лёгкая настольная мельница предназначена для истирания проб максимальным весом до 100 грамм. Предназначена для ис...