Interpolation.

NUMERICAL METHODS

(Summary of Lectures)

V. N. Pavlysh

dep. of numerical mathematics and programming

(For the students of English Engineering Faculty)

Donetsk 2006

Донецкий национальный технический университет

ЧИСЛЕННЫЕ МЕТОДЫ

(конспект лекций)

В.Н. Павлыш

каф. вычислительной математики и программирования

(на английском языке)

(Для студентов английского технического факультета)

Донецк 2006

Донецкий национальный технический университет

ЧИСЛЕННЫЕ МЕТОДЫ

(конспект лекций)

(Для студентов английского технического факультета)

Рассмотрено

на заседании кафедры вычислитель-ной математики и программирования

прот. № 7 от 14.02.2006

(на английском языке)

Утверждено

на заседании учебно-издательского

совета института международного сотрудничества ДонНТУ

прот. № от 2006

Донецк 2006

Численные методы (конспект лекций).

(Для студентов английского технического факультета) / Составитель

В.Н. Павлыш (на английском языке) – Донецк: ДонНТУ, 2006.- 28с.

Составитель: В.Н. Павлыш, доцент

Рецензент: С.А. Ковалев, доцент

Донецк 2006

Interpolation.

Problem:

Let we have a function y = f (x), given by the table:

The given value is x₀ < x < x_n, x ¹ x_i, i=0, 1, …, n; how to obtain y = f(x), when formula f(x) is unknown?

The method of solution of this problem is: to create some known function F(x), which represents our given function f(x) such as:

1) F(x_i) = f(x_i), i = 0, 1, …, n;

2) | F(x) – f(x) | ® min, x₀ £ x £ x_n.

The most convenient form of F(x) is polynomial.

Lagrange suggested one of possible ways.

The idea of Lagrange:

1. To create the system of fundamental polynomials, which response to condition:

2. To construct interpolation polynomial in the form:

The fundamental polynomial may be constructed as:

The first condition is responded.

The second condition is:

Q_i⁽ⁿ⁾(x_k) = 1, i = k, i.e. Q_i⁽ⁿ⁾(x_i) = 1

g(x_i–x₀)(x_i –x₁)…(x_i –x_i–1)(x_i –x_i+1)…(x_i –x_n) = 1

g =

Then:

Q_i⁽ⁿ⁾(x) =

Lagrange’s interpolation polynomial:

L(x) =

The compact form of the Lagrange’s polynomial.

Let us consider P(x) = (x–x₀)(x–x₁)(x–x₂)…(x–x_n).

Then (x–x₀)(x–x₁)…(x–x_i–1)(x–x_i+1)…(x–x_n) = .

Let us consider P¢ (x):

P¢ (x) = (x–x₁)(x–x₂)…(x–x_n)+(x–x₀)(x–x₂)…(x–x_n)+…+(x–x₀)(x–x₁)…(x–x_i–1)(x–

–x_i+1)…(x–x_n)+…+ (x–x₀)(x–x₁)…(x–x_n–1).

Then (x_i–x₀)(x_i –x₁)…(x_i –x_i–1)(x_i –x_i+1)…(x_i –x_n) = P¢ (x_i).

So, the Lagrange’s polynomial can be written:

L(x) = P(x) .

Interpolation for proportional tables.

x₁–x₀ = x₂–x₁ =…= x_n–x_n–1 = h = const, where h is a step of a table.

Substitution: x = x₀+ht;

t=0 Þ x = x₀

x_i = x₀+ih

t = .

P(x) = (x–x₀)(x–x₁)(x–x₂)…(x–x_n);

x–x₀ = ht; x–x_i = x₀+ht–(x₀+ih) = h(t–i);

x_k–x_i = x₀+kh–(x₀+ih) = h(k–i);

P(x₀+ht) = ht× h(t–1)× …× h(t–(n–1))× h(t–n) = h^n+1­× t(t–1)(t–2)× …× (t–n+1)(t–n);

P*(t) = t(t–1)(t–2)…(t–n+1)(t–n);

P(x) = P(x₀+ht) = h^n+1­P*(t);

P¢ (x_k) = (x_k–x₀)(x_k­–x₁)…(x_k–x_k–1)(x_k–x_k+1)…(x_k–x_n);

P¢ (x_k) = h(k–0)× h(k–1)× …× h× 1× h(–1)h(–2)× …× h(–(n–k)) = hⁿ× 1× 2× …× k(–1)(–2)× …´

´ (–(n–k)) = hⁿ× (–1)^n–kk! (n–k)!;

L(x) = L(x₀+ht) = hⁿ⁺¹P*(t) ;

Lagrange’s polynomial for proportional tables:

L(x₀+ht) = P*(t)