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.


 

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

45032. Путешествие по Индии 128 KB
  Супер Нам всё нравится 20 Отели Надо отметить что в Индии ни на одной отельной вывеске вы не увидите заветных звезд. Стандартный набор осматриваемых объектов в столице это Ворота Индии Здание Высокого суда Старый Форт и знаменитая мечеть Кутуб Минар с которой и начинается наша экскурсия. И тут перед нами предстала картина которую возможно увидеть пожалуй только в Индии.
45033. Семантика по книге Стивена Пинкера «Язык как инстинкт» 130 KB
  Пинкер известен за его широко охватывающую защиту эволюционной психологии и Вычислительной теории разума. Академическая специализация Пинкера визуальное восприятие и развитие речи у детей и он более известен как популяризатор идеи о том что язык на котором мы говорим является инстинктом или биологической адаптацией сформированной естественным отбором. Этот доклад был написан мною по одной из самых известных книг Стивена Пинкера Язык как инстинкт.
45034. Инженерная подготовка строительной площадки 42.64 KB
  Бетонную смесь готовят бетоносмесителями и транспортируют с помощью системы внутренних транспортных средств до места заливки либо привозят готовую бетонную смесь автобетоносмесителями или самосвалами Технология устройства защитных покрытии Гидро и пароизоляционные работы выполняют по завершению изготовления конструкции или монтажа сборных конструкций. Однако эти работы могут вестись параллельно с некоторым технологически обусловленным отставанием от работ по изготовлению конструкций на которые будет наноситься гидро и пароизоляция. В...
45035. Семантические принципы 29.5 KB
  Принцип предметности: предложение должно говорить о предметах обозначаемых входящими в него именами а не о самих этих именах. Предложение Стул - это существительное построено правильно. Принцип взаимозаменимости: при замене имен с одинаковым значением предложение в котором эта замена осуществляется не должно изменять свое истинностное значение истинное предложение должно оставаться истинным а ложное ложным. Пусть дано предложение Земля вращается вокруг Солнца.
45036. TRAVELLING BY AIR 33.95 KB
  Modern life is impossible without traveling. There are many ways of traveling: by sea, by plane, by train, by car, on foot. Tastes differ. That іs why it is up to you to decide which means of travelling you'd prefer
45037. TRAVELLING BY SEA 33.59 KB
  It іs wonderful to feel the deck under the feet to see the rise nd fll of the wves to feel the fresh se wind blowing in the fce to her the cry of segulls. Every modern liner hs number of decks with ll sorts of nmes such s promende deck sun deck etc. There re pssenger cbins bove nd below deck.
45038. Розрахунок на точність важільного мікрометра 1.09 MB
  Зовнішній вигляд важільного мікрометра Механізм відліку рисунок 2 складається з синусного механізму з довжиною важеля а виконаного у вигляді вилки 3 з сталевою кулькою який впирається в стінку паза рухомої пятки 2 і зубчатого сектора 4 встановленого на одній осі О з синусним важелем і входячим в зачеплення з центральним колесом 5. Рисунок 2 Схема механізму відлікового пристрою важільного мікрометра Похибка схеми мікрометра обумовлена використанням в ній синусного механізму який має нелінійну функцію перетворення. Знайдемо...
45040. Технология публикации информации в формате. Виды форматов 2.52 MB
  Компьютерный формат файла специфический способ кодирования информации на компьютере. Существуют различные форматы файлов: звуковые форматы форматы автоматизированного проектирования форматы Continer цифровая звукозапись графические форматы видео форматы и т. Чтобы компьютер понимал к какому типу относится тот или иной файл и в какой программе его открыть после имени файла указывается расширение. Расширение файла это часть имени файла которое отделяется от основного имени точкой.