4

Ministry of Education and Science of Ukraine

Donetsk National Technical University

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

УДК 681.3.06 (071)

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

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

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

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

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

Донецк 2006

Interpolation.

Problem:

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

x0	x1	x2	x3	…	xn-1	xn	n+1 points
y0	y1	y2	y3	…	yn-1	yn

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

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

 =

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)

Finite differences.

The finite difference of the first order for y₀ is the value: y₀ = y₁–y₀ (the first finite difference). Analogously: y₁ = y₂–y₁,…, y_k = y_k+1–y_k.

The second finite differences:

²y₀ = y₁–y₀

…

²y_k = y_k+1–y_k

The finite difference of the k-th order: ^ky_i = ^k–1y_i+1–^k–1y_i.

Let us consider the term:

²y₀ = y₁–y₀ = y₂–y₁–(y₁–y₀) = y₂–2y₁+y₀

³y₀ = ²y₁–²y₀ = y₃–2y₂+y₁–(y₂–2y₁+y₀) = y₃–3y₂+3y₁–y₀

…

^my₀ = (–1)^kC y_m–k

^my_i = (–1)^kC y_m+i–k

The table of differences:

		y	2y	3y	4y	5y
x0	y0
		y0
x1	y1		2y0
		y1		3y0
x2	y2		2y1		4y0
		y2		3y1		5y0
x3	y3		2y2		4y1
		y3		3y2
x4	y4		2y3
		y4
x5	y5

Divided differences.

The first divided difference:

f(x₀,x₁) = [x₀,x₁] = y_0,1 = =

y_1,2 =

The divided difference of the second order:

y_0,1,2 = ; y_1,2,3 =

Let us consider the table of the function:

y_0,1 = =

y_0,1,2 =

=

y_0,1,…,m =

Properties:

1. (φ + ψ) = φ + ψ : (φ+ψ)_0,1 = φ_0,1+ψ_0,1

2. (cy) = cy : (cy)_0,1 = cy_0,1

3. : y_0,1,…,k = y_3,0,1,…,k

Connection between fin. and div. dif. (h = const)

Newton’s polynomials.

Let us consider a divided difference:

f(x,x₀) = .

The unknown value is:

f(x) = f(x₀)+f(x,x₀)(x–x₀). (1)

We know f(x₀), but we do not know f(x,x₀), then

f(x,x₀,x₁) = ,

so

f(x,x₀) = f(x₀,x₁)+f(x,x₀,x₁)(x–x₁). (2)

Now let us put (2) into (1):

f(x) = f(x₀)+f(x₀,x₁)(x–x₀)+f(x,x₀,x₁)(x–x₀)(x–x₁).

Continuing this process we shall obtain:

f(x)=f(x₀)+f(x₀,x₁)(x–x₀)+f(x₀,x₁,x₂)(x–x₀)(x–x₁)+…+f(x₀,x₁,…,x_n)(x–x₀)(x–x₁)…

(x––x_n–1)+ f(x,x₀,x₁,…,x_n)(x–x₀)(x–x₁)…(x–x_n).

The member f(x,x₀,x₁,…,x_n)(x–x₀)(x–x₁)…(x–x_n) is unknown, so we can say that it is an error, then

f(x)f(x₀)+f(x₀,x₁)(x–x₀)+f(x₀,x₁,x₂)(x–x₀)(x–x₁)+…+f(x₀,x₁,…,x_n)(x–x₀)(x–x₁)…(x––x_n–1)

f(x)=P_n(x) + f(x,x₀,x₁,..,x_n)(x-x₀)(x-x₁)...(x-x_n)

f(x)P_n(x)

P_n(x)= y₀+y_0,1(x-x₀)+y_0,1,2(x-x₀)(x-x₁)+...+y_0,1,...n(x-x₀)...(x-x_n-1)

When we have proportional table:

(3)

x₀ y₀

y₀

x₁ y₁ ^y₀

y₁ ^y₀

x₂ y₂ ^y₁ ^y₀

y₂ ^y₁ ^y₀

x₃ y₃ ^y₂ ^y₁

y₃ ^y₂

x₄ y₄ ^y₃

y₄

x₅ y₅

Formula (3) named “First interpolational formula of Newton”, or “formula of forward interpolation ”

It use divided differences, which form high incline in the table of differences.

Formula (3) is used when unknown point x is at the beginning of the table.

Consider difference

etc.

f(x)y_n + y_n,n-1(x-x_n) + y_n,n-1,n-2(x-x_n)(x-x_n-1)+..+y_{n,n-1,...,1,0}(x-x_n)(x-x_n-1)...(x-x₁)

(4)

Formula (4) named «Second interpolational formula of Newton» or «formula of back interpolation». It use divided differences, which form lower incline in the table of differences. Formula (4) is used when point x is at the ending of table.

Interpolation in the middle of the table.

Let’s rename table points in such way

x_-3 y_-3

y_-3

x_-2 y_-2 ^y_-3

y_-2 ^y_-3

x_-1 y_-1 ^y_-2 ^y_-3

y_-1 ^y_-2 ^y_-3

x₀ y₀ ^y_-1 ^y_-2 ^y_-3

~~ y₀ ~~ ^y_-1 ~~ ^y_-2 ~~

x₁ y₁ ~~ ^y₀ ~~~ ^y_-1 ~~

y₁ ^y₀

x₂ y₂ ^y₁

y₂

x₃ y₃

Consider first interpolational formula of Newton, that use differences, formed lower braked line in the middle of the table(underline «~»):

(5)

(5)- first interpolational formula of Gauss. Analogously, consider differences, formed high braked line:

(6)

6. - second interpolational formula of Gauss.

Numerical integration.





 When F(x) is unknown then :

x₀ x₁ x₂ ... x_n

y₀ y₁ y₂ ... y_n y_i=f(x_i)

f(x) L(x)

.

Coefficients A_i are depended only of points and not depend of function.

When we have proportional table: x=x₀+ht

dx=hdt

-coefficients of Kotes.

They depend only of number of points and may be calculated for various n.

- formula of Newton-Kotes.

Particular cases.

1)

_b

f(x)dx=S_X0,Y0,Xn,Yn

^a

- formula of left rectangles.

- formula of right rectangles.

2) n=1 (particular formula of trapezes): h=b-a

.

Total formula of trapezes:

3) n=2 (particular formula of Simpson)

^.

Total formula of Simpson:

4) n=3 (particular formula of Newton);

Total formula of Newton (law of )

n=3m

Error: