M
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
У
Численные методы (конспект лекций).
(Для студентов английского технического факультета) / Составитель
В.Н. Павлыш (на английском языке) – Донецк: ДонНТУ, 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 x0 < x < xn, x xi, 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:
F(xi) = f(xi), i = 0, 1,…, n;
|F(x) – f(x)| min, x0 x xn.
The most convenient form of F(x) is polynomial.
Lagrange suggested one of possible ways.
The idea of Lagrange:
To create the system of fundamental polynomials, which response to condition:
To construct interpolation polynomial in the form:
The fundamental polynomial may be constructed as:
The first condition is responded.
The second condition is:
Qi(n)(xk) = 1, i = k, i.e. Qi(n)(xi) = 1
(xi–x0)(xi –x1)…(xi –xi–1)(xi –xi+1)…(xi –xn) = 1
=
Then:
Qi(n)(x) =
Lagrange’s interpolation polynomial:
L(x) =
The compact form of the Lagrange’s polynomial.
Let us consider P(x) = (x–x0)(x–x1)(x–x2)…(x–xn).
Then (x–x0)(x–x1)…(x–xi–1)(x–xi+1)…(x–xn) = .
Let us consider P(x):
P(x) = (x–x1)(x–x2)…(x–xn)+(x–x0)(x–x2)…(x–xn)+…+(x–x0)(x–x1)…(x–xi–1)(x–
–xi+1)…(x–xn)+…+ (x–x0)(x–x1)…(x–xn–1).
Then (xi–x0)(xi –x1)…(xi –xi–1)(xi –xi+1)…(xi –xn) = P(xi).
So, the Lagrange’s polynomial can be written:
L(x) = P(x) .
Interpolation for proportional tables.
x1–x0 = x2–x1 =…= xn–xn–1 = h = const, where h is a step of a table.
Substitution: x = x0+ht;
t=0 x = x0
xi = x0+ih
t = .
P(x) = (x–x0)(x–x1)(x–x2)…(x–xn);
x–x0 = ht; x–xi = x0+ht–(x0+ih) = h(t–i);
xk–xi = x0+kh–(x0+ih) = h(k–i);
P(x0+ht) = hth(t–1)…h(t–(n–1))h(t–n) = hn+1t(t–1)(t–2)…(t–n+1)(t–n);
P*(t) = t(t–1)(t–2)…(t–n+1)(t–n);
P(x) = P(x0+ht) = hn+1P*(t);
P(xk) = (xk–x0)(xk–x1)…(xk–xk–1)(xk–xk+1)…(xk–xn);
P(xk) = h(k–0)h(k–1)…h1h(–1)h(–2)…h(–(n–k)) = hn12…k(–1)(–2)…
(–(n–k)) = hn(–1)n–kk!(n–k)!;
L(x) = L(x0+ht) = hn+1P*(t) ;
Lagrange’s polynomial for proportional tables:
L(x0+ht) = P*(t)
Finite differences.
The finite difference of the first order for y0 is the value: y0 = y1–y0 (the first finite difference). Analogously: y1 = y2–y1,…, yk = yk+1–yk.
The second finite differences:
2y0 = y1–y0
…
2yk = yk+1–yk
The finite difference of the k-th order: kyi = k–1yi+1–k–1yi.
Let us consider the term:
2y0 = y1–y0 = y2–y1–(y1–y0) = y2–2y1+y0
3y0 = 2y1–2y0 = y3–2y2+y1–(y2–2y1+y0) = y3–3y2+3y1–y0
…
my0 = (–1)kC ym–k
myi = (–1)kC ym+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(x0,x1) = [x0,x1] = y0,1 = =
y1,2 =
The divided difference of the second order:
y0,1,2 = ; y1,2,3 =
Let us consider the table of the function:
y0,1 = =
y0,1,2 =
=
y0,1,…,m =
Properties:
(φ + ψ) = φ + ψ : (φ+ψ)0,1 = φ0,1+ψ0,1
(cy) = cy : (cy)0,1 = cy0,1
: y0,1,…,k = y3,0,1,…,k
Connection between fin. and div. dif. (h = const)
Newton’s polynomials.
Let us consider a divided difference:
f(x,x0) = .
The unknown value is:
f(x) = f(x0)+f(x,x0)(x–x0). (1)
We know f(x0), but we do not know f(x,x0), then
f(x,x0,x1) = ,
so
f(x,x0) = f(x0,x1)+f(x,x0,x1)(x–x1). (2)
Now let us put (2) into (1):
f(x) = f(x0)+f(x0,x1)(x–x0)+f(x,x0,x1)(x–x0)(x–x1).
Continuing this process we shall obtain:
f(x)=f(x0)+f(x0,x1)(x–x0)+f(x0,x1,x2)(x–x0)(x–x1)+…+f(x0,x1,…,xn)(x–x0)(x–x1)…
(x––xn–1)+ f(x,x0,x1,…,xn)(x–x0)(x–x1)…(x–xn).
The member f(x,x0,x1,…,xn)(x–x0)(x–x1)…(x–xn) is unknown, so we can say that it is an error, then
f(x)f(x0)+f(x0,x1)(x–x0)+f(x0,x1,x2)(x–x0)(x–x1)+…+f(x0,x1,…,xn)(x–x0)(x–x1)…(x––xn–1)
f(x)=Pn(x) + f(x,x0,x1,..,xn)(x-x0)(x-x1)...(x-xn)
f(x)Pn(x)
Pn(x)= y0+y0,1(x-x0)+y0,1,2(x-x0)(x-x1)+...+y0,1,...n(x-x0)...(x-xn-1)
When we have proportional table:
(3)
x0 y0
y0
x1 y1 y0
y1 y0
x2 y2 y1 y0
y2 y1 y0
x3 y3 y2 y1
y3 y2
x4 y4 y3
y4
x5 y5
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)yn + yn,n-1(x-xn) + yn,n-1,n-2(x-xn)(x-xn-1)+..+yn,n-1,...,1,0(x-xn)(x-xn-1)...(x-x1)
(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
x0 y0 y-1 y-2 y-3
~~ y0 ~~ y-1 ~~ y-2 ~~
x1 y1 ~~ y0 ~~~ y-1 ~~
y1 y0
x2 y2 y1
y2
x3 y3
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)
- second interpolational formula of Gauss.
Numerical integration.
When F(x) is unknown then :
x0 x1 x2 ... xn
y0 y1 y2 ... yn yi=f(xi)
f(x) L(x)
.
Coefficients Ai are depended only of points and not depend of function.
When we have proportional table: x=x0+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=SX0,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: