Вычислительная математика
Темы занятий
Тема 3. Приближение функций
Тема 3. Приближение функций Геометрический смысл:
Тема 3. Приближение функций Геометрический смысл:
Тема 3. Приближение функций
Тема 3.1 Аппроксимация по методу наименьших квадратов
Метод наименьших квадратов
Метод наименьших квадратов
Метод наименьших квадратов
Метод наименьших квадратов
Виды эмпирической зависимости
Метод наименьших квадратов
Метод наименьших квадратов
Метод наименьших квадратов
Метод наименьших квадратов
Тема 3.2 Интерполяция
Тема 3.2 Интерполяция Геометрический смысл:
Тема 3.2 Интерполяция
Тема 3.2 Интерполяция
Тема 3.2 Интерполяция
Тема 3.2 Интерполяция
Тема 3.2.1 Интерполяционный многочлен (полином) Лагранжа
Тема 3.2.1 Интерполяционный многочлен (полином) Лагранжа
3.2.1 Интерполяционная формула Лагранжа
Ввод исходных данных в программу на языке Pascal
3.2.2 Интерполяционный полином Ньютона
3.2.2 Полином Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
3.2.2 Полином Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
3.2.2 Полином Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
3.2.2 1-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
3.2.2 1-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
3.2.2 2-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
2-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
2-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
1-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)
Блок-схема 1-я формула Ньютона
Блок-схема 2-я формула Ньютона
Полином Ньютона для неравноотстоящих узлов интерполяции (xi+1–xi=h ≠ const)
Полином Ньютона для неравноотстоящих узлов интерполяции (xi+1–xi=h ≠ const)
Погрешность полиномиальной интерполяции
Полином Ньютона для неравноотстоящих узлов интерполяции (xi+1–xi=h ≠ const)
Блок-схема 1-я формула Ньютона (в разделенных разностях)
Блок-схема 2-я формула Ньютона (в разделенных разностях)
723.00K
Category: mathematicsmathematics

Вычислительная математика. Лекция 6

1. Вычислительная математика

Лекция 6
1

2. Темы занятий

Алгебра
1. Решение систем линейных алгебраических
уравнений (СЛАУ).
2. Решение нелинейных алгебраических
уравнений.
Математический анализ
3. Приближение функций.
4. Вычисление определенных интегралов.
5. Решение дифференциальных уравнений.
2

3. Тема 3. Приближение функций

Обобщенная постановка задачи:
Дано:
функция
y = f(x)
Найти:
функцию y = g(x) такую, что f(x) ≈ g(x), то есть
погрешность приближения |f(x) – g(x)| достаточно мала
для всех х [a, b].
Нахождение функции y = g(x) называется задачей
аппроксимации функции y = f(x). Функция y = g(x)
называется аппроксимирующей функцией.
3

4. Тема 3. Приближение функций Геометрический смысл:

y
y = g(x)
O
y = f(x)
x
4

5. Тема 3. Приближение функций Геометрический смысл:

y
y = g(x)
O
y = f(x)
x
5

6. Тема 3. Приближение функций

Необходимость решения задачи аппроксимации возникает, когда:
функция y = f(x) задана таблицей своих (в общем случае
приближенных) значений:
yi f(xi), i = 0, 1, 2, …, n;
~
x xi
при этом нужно вычислять значения функции y = f(x) в точках
(такая задача возникает при экспериментальном вычислении значений
функции y = f(x));
функция y = f(x) задана сложным аналитическим выражением,
затрудняющим вычисления; при этом требуется заменить сложную
функцию y = f(x) на более простую функцию y = g(x) (такая задача
возникает при необходимости многократного вычисления значений
функции y = f(x) или при необходимости выполнения операций над
функцией y = f(x), например, дифференцирования или интегрирования).
6

7. Тема 3.1 Аппроксимация по методу наименьших квадратов

Пусть аппроксимирующая функция имеет вид
y = Q(x, a0, a1, …, am),
где ai (i = 0, 1, …, m) – числовые параметры, значения которых
находятся из условия
n
2
S (a0 , a1 , , am ) Q( xi , a0 , a1 , , am ) yi min
i 0
Тогда значения параметров находятся из системы уравнений,
полученной из необходимого условия экстремума функции:
S
a 0;
0
S 0;
a
1
.......... .......... .
S 0.
am
7

8. Метод наименьших квадратов

Пусть
Q(x, a0, a1, …, am) = a0 + a1x + a2 x2 + ... +am xm.
Тогда
2
j
S (a0 , a1 , , am ) a j xi yi
i 0 j 0
Следовательно,
n m
S
j
k
(a0 , a1 , , am ) 2 a j xi yi xi
ak
i 0 j 0
n
n
m
2 a0 a1 xi a2 xi2 ... am xim yi xik
i 0
n
2 a0 xik a1 xik 1 a2 xik 2 ... am xik m yi xik
i 0
n k
n k 1
n k m
n
2 xi a0 xi a1 ... xi am yi xik .
i 0
i 0
i 0
i 0
8

9. Метод наименьших квадратов

Таким образом, получена СЛАУ на нахождение значений
параметров ai (i = 0, 1, …, m) имеет вид:
n
n
n 2
n m
(n 1)a0 xi a1 xi a2 ... xi am yi ;
i 0
i 0
i 0
i 0
n
n
n 2
n 3
n m 1
xi a0 xi a1 xi a2 ... xi am yi xi ;
i 0
i 0
i 0
i 0
i 0
n
n
n 3
n 4
n m 2
2
2
xi a0 xi a1 xi a2 ... xi am yi xi ;
i 0
i 0
i 0
i 0
i 0
......................................................................................................
n
n m 1
n m 2
n 2m
n m
m
x
a
x
a
x
a
...
x
a
y
x
1
i
2
i
m
i i .
i 0 i
i 0
i 0
i 0
i 0
i 0
9

10. Метод наименьших квадратов

В частном случае при m = 4 имеем СЛАУ :
n
n
n 2
n 3
n 4
(n 1)a0 xi a1 xi a2 xi a2 xi a2 yi ;
i 0
i 0
i 0
i 0
i 0
n
n
n 2
n 3
n 4
n 5
xi a0 xi a1 xi a2 xi a2 xi a2 yi xi ;
i 0
i 0
i 0
i 0
i 0
i 0
n
n
n 3
n 4
n 5
n 6
2
2
xi a0 xi a1 xi a2 xi a2 xi a2 yi xi ;
i 0
i 0
i 0
i 0
i 0
i 0
n
n
n 4
n 5
n 6
n 7
3
xi a0 xi a1 xi a2 xi a2 xi a2 yi xi3 ;
i 0
i 0
i 0
i 0
i 0
i 0
n
n
n
n
n
n
4
5
6
7
8
x a x a x a x a x a y x 4 .
i 0 i 0 i 0 i 1 i 0 i 2 i 0 i 2 i 0 i 2 i 0 i i
10

11. Метод наименьших квадратов

Пусть m = 1, a0 = b, a1 = k.
Тогда получим
n
n
(n 1)b xi k yi ;
i 0
i 0
n
n
n
x b x 2 k
yi xi .
i
i
i 0
i 0 i 0
Отсюда
c d c d
c d c d
k 11 2 122 1 , b 22 1 12 2 2 ,
c11c22 c12
c11c22 c12
где
n
n
n
n
i 0
i 0
c11 n 1, c12 xi , c22 x , d1 yi , d 2 yi xi .
i 0
i 0
2
i
11

12. Виды эмпирической зависимости


Преобразование
переменных
1 Xi = xi ,
Yi = xiyi
Эмпирическая формула
y = α + β/x,
2 Xi = xi ,
Yi = 1/yi
y = 1/(αx + β), α = k, β = b
3 Xi = xi ,
Yi = xi /yi
y = x/(αx + β), α = k, β = b
4 Xi = xi ,
Yi = ln yi
y = αβx,
α = eb, β = ek
5 Xi = ln xi , Yi = yi
y = αln x + β,
α = k, β = b
6 Xi = ln xi , Yi = ln yi
y = αxβ,
α = eb, β = k
α = k, β = b
12

13. Метод наименьших квадратов

Пусть
Q(x, a0, a1, …, am) = a0φ0(x) + a1φ1(x) + a2 φ2(x) + ... +am φm(x).
2
Тогда
n m
S (a0 , a1 , , am ) a j j ( xi ) yi
Следовательно,
i 0
j 0
n m
S
(a0 , a1 , , am ) 2 a j j ( xi ) yi k ( xi )
ak
i 0 j 0
n
2 a0 0 ( xi ) a1 1 ( xi ) a2 2 ( xi ) ... am m ( xi ) yi k ( xi )
i 0
n
2 a0 0 ( xi ) k ( xi ) a1 1 ( xi ) k ( xi ) a2 2 ( xi ) k ( xi ) ... am m ( xi ) k ( xi ) yi k ( xi )
i 0
n
n
n
n
2 0 ( xi ) k ( xi ) a0 1 ( xi ) k ( xi ) a1 ... m ( xi ) k ( xi ) am yi k (13xi ) .
i 0
i 0
i 0
i 0

14. Метод наименьших квадратов

Таким образом, получена СЛАУ уравнений на нахождение
значений параметров ai (i = 0, 1, …, m) имеет вид:
n
n 2
n
n
n
0 ( xi ) a0 1 ( xi ) 0 ( xi ) a1 2 ( xi ) 0 ( xi ) a2 ... m ( xi ) 0 ( xi ) am yi 0 ( xi );
i 0
i 0
i 0
i 0
i 0
n
n
n 2 n
n
1 ( xi ) a1 2 ( xi ) 1 ( xi ) a2 ... m ( xi ) 1 ( xi ) am yi 1 ( xi );
1 ( xi ) 0 ( xi ) a0
i 0
i 0
i 0
i 0
i 0
n
n
n
n 2
n
2 ( xi ) a2 ... m ( xi ) 2 ( xi ) am yi 2 ( xi );
1 ( xi ) 0 ( xi ) a0 2 ( xi ) 1 ( xi ) a1
i 0
i 0
i 0
i 0
i 0
......................................................................................................
n
n
n
n 2
n
m ( xi ) am yi m ( xi ).
m ( xi ) 0 ( xi ) a0 m ( xi ) 1 ( xi ) a1 m ( xi ) 2 ( xi ) a2 ...
i 0
i 0
i 0
i 0
i 0
14

15. Метод наименьших квадратов

Например, пусть m = 2k + 1 и
Q( x, a0 , a1 , b1 , a2 , b2 , , ak , bk ) a0 a j cos jx b j sin jx .
Тогда СЛАУ примет вид
k
j 1
k
k
n
n
n
(n 1)a0 a j cos jxi
b j sin jxi
yi ;
j 1
j 1
i 0
i 0
i 0
k
n
n
k n
n
cos pxi a0 a j (cos jxi cos pxi ) b j (sin jxi cos pxi ( yi cos pxi );
j 1
i 0
j 1 i 0
i 0
i 0
n
k
n
k n
n
sin pxi a0 a j (cos jxi sin pxi ) b j (sin jxi sin pxi ) ( yi sin pxi );
i 0
j 1
i 0
j 1 i 0
i 0
p 1, 2, , k
15

16. Метод наименьших квадратов

В частном случае при k = 2 получим СЛАУ
n
n
n
n
n
(n 1)a0
cos xi a1
cos 2 xi a2
sin xi b1
sin 2 xi b2 yi ;
i 0
i 0
i 0
i 0
i 0
n
n
n
n
n
n
2
cos xi a1 cos 2 xi cos xi a2 sin xi cos xi b1 sin 2 xi cos xi b2 yi cos xi ;
cos xi a0
i 0
i 0
i 0
i 0
i 0
i 0
n
n
n
n
n
n
2
cos 2 xi a2 sin xi cos 2 xi b1 sin 2 xi cos 2 xi b2 yi cos 2 xi ;
cos 2 xi a0 cos xi cos 2 x i a1
i 0
i 0
i 0
i 0
i 0
i 0
n
n
n
n
n
n
2
sin xi a0 cos xi sin x i a1 cos 2 xi sin xi a2
sin xi b1 sin 2 xi sin xi b2 yi sin xi ;
i 0
i 0
i 0
i 0
i 0
i 0
n
n
n
n
n
n
2
sin 2 x a cos x sin 2 x a cos 2 x sin 2 x a sin x sin 2 x b
sin 2 xi b2 yi sin 2 xi ;
i
0
i
i
1
i
i
2
i
i 1
i 0
i 0
i 0
i 0
i 0
i 0
16

17. Тема 3.2 Интерполяция

Обобщенная постановка задачи интерполяции:
Дано:
значения функции y = f(x), x [a, b]:
yi = f(xi), i = 0, 1, 2, …, n (xi [a, b]).
Найти:
функцию y = g(x) такую, что
g(xi) = yi, i = 0, 1, 2, …, n.
17

18. Тема 3.2 Интерполяция Геометрический смысл:

y
y2
y = g(x)
y0
y5
y4
x0 O
y3
y1
x1
x2
x3
x4
y = f(x)
x5
x
18

19. Тема 3.2 Интерполяция

Задача интерполяции обобщенным многочленом:
Пусть задана система функций:
φ0(x), φ1(x), φ2(x), ..., φn(x).
Обобщенным многочленом называется функция
n
n(x) = a0φ0(x)+a1φ1(x)+a2φ2(x)+...+anφn(x) = a j j ( x),
j 1
такая, что
n(xi) = yi, i = 0, 1, 2, …, n.
19

20. Тема 3.2 Интерполяция

Коэффициенты aj (j = 0, 1, 2, …, n) находятся из условия:
a0 0 ( x0 ) a1 1 ( x0 ) a2 2 ( x0 ) ... an n ( x0 ) y0 ,
a ( x ) a ( x ) a ( x ) ... a ( x ) y ,
1 1 1
2 2 1
n n 1
1
0 0 1
a0 0 ( x2 ) a1 1 ( x2 ) a2 2 ( x2 ) ... an n ( x2 ) y2 , – СЛАУ.
.....................................................................................
a0 0 ( xn ) a1 1 ( xn ) a2 2 ( xn ) ... an n ( xn ) yn ;
Для решения СЛАУ необходимо, чтобы для любых xi (i = 0, 1, 2, …, n), xi x j ,
i j
0 ( x0 ) 1 ( x0 ) ... n ( x0 )
0 ( x1 ) 1 ( x1 ) ... n ( x1 )
(1)
...
...
...
...
0 ( xn ) 1 ( xn ) ... n ( xn )
0,
система функций {φj(x)}j=0,1,...,n , удовлетворяющая условию (1), называется
20
чебышевской системой функций.

21. Тема 3.2 Интерполяция

Задача полиномиальной интерполяции:
Пусть задана система функций вида:
φ0(x) = 1, φ1(x) = x, φ2(x) = x2, ..., φn(x) = xn.
Интерполяционным многочленом (полиномом)
называется функция
n
j
2
n
a
x
Pn(x) = a0x + a1x + a2 x + ... +an x = j ,
j 0
такая, что
Pn(xi) = yi, i = 0, 1, 2, …, n.
21

22. Тема 3.2 Интерполяция

Теорема
Система функций {1, x, x2, ..., xn} является чебышевской.
Доказательство:
1
1
1
...
1
x0
x1
x2
...
xn
x02
x12
x22
...
xn2
...
...
...
...
...
x0n
x1n
n
n
x2 ( xi x j ) 0 – определитель Вандермонда.
0 j i n
...
xnn
22

23. Тема 3.2.1 Интерполяционный многочлен (полином) Лагранжа

Интерполяционный многочлен (полином) Лагранжа
имеет следующий вид:
Ln ( x) y0 Pn0 ( x) y1 Pn1 ( x) y2 Pn2 ( x) ... yn Pnn ( x),
где многочлен степени n такой, что
1, i j,
j
Pn ( xi )
0, i j.
Многочлен Pni ( x) Ci ( x x0 )( x x1 )...(x xi 1 )( x xi 1 )...(x xn ),
Pni ( xi ) 1 Ci
Pni ( x)
1
( xi x0 )( xi x1 )...(xi xi 1 )( xi xi 1 )...(xi xn )
n (x x )
( x x0 )( x x1 )...(x xi 1 )( x xi 1 )...(x xn )
j
.
( xi x0 )( xi x1 )...(xi xi 1 )( xi xi 1 )...(xi xn ) j 0, ( xi x j ) 23
j i

24. Тема 3.2.1 Интерполяционный многочлен (полином) Лагранжа

Интерполяционный многочлен (полином) Лагранжа
Общая формула:
n
n
n
Ln ( x)
i 0
yi Pni ( x)
(x x j )
yi ( x x ) .
i 0
j 0 ,
j i
i
j
Частные случаи:
x x0
x x1
y1
n = 1: L1 ( x) y0
x0 x1
n = 2: L2 ( x) y0
n = 3: L3 ( x) y0
x1 x0
( x x1 )( x x2 )
( x x0 )( x x2 )
( x x0 )( x x1 )
y1
y2
( x0 x1 )( x0 x2 )
( x1 x0 )( x1 x2 )
( x2 x0 )( x2 x1 )
( x x1)( x x2 )( x x3 )
( x x0 )( x x2 )( x x3 )
( x x0 )( x x1)( x x3 )
( x x0 )( x x1)( x x2 )
y1
y2
y3
.
( x0 x1)( x0 x2 )( x0 x3 ) ( x1 x0 )( x1 x2 )( x1 x3 ) ( x2 x0 )( x2 x1)( x2 x3 ) ( x3 x0 )( x3 x1)( x3 x2 )
24

25. 3.2.1 Интерполяционная формула Лагранжа

Блок-схема алгоритма
Begin
L:=0
for i:=0 to n do
P:=1
for j:=0 to i–1 do
P:=P*(~
x –x(j))/(x(i)–x(j))
for j:=i+1 to n do
P:=P*(~
x–x(j))/(x(i)–x(j))
L:=L+y(i)*P
25
End

26. Ввод исходных данных в программу на языке Pascal

const
n = 10;
a = 0;
b = 1;
var
x[n], y[n], L, P, h: double;
i, j: integer;
function f(x: double): double;
begin
f := sqrt(x);
end;
begin
h := (b–a)/n;
x[0] := a;
for i:=1 to n do
x[i] := x[i–1] + h;
for i:=0 to n do
y[i] := f(x[i]);
...
end.
26

27. 3.2.2 Интерполяционный полином Ньютона

Общий вид:
первая формула Ньютона:
Pn(1) ( x) a0 a1 ( x x0 ) a 2 ( x x0 )( x x1 ) ... a n ( x x0 )( x x1 )...( x x n 1 )
вторая формула Ньютона:
Pn( 2) ( x) b0 b1 ( x x n ) b2 ( x x n )( x x n 1 ) ... bn ( x x n )( x x n 1 )...( x x1 )
27

28. 3.2.2 Полином Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

Конечные разности:
yi = yi+1–yi – конечные разности первого порядка;
2yi = yi+1– yi – конечные разности второго порядка;
3yi = 2yi+1– 2yi – конечные разности третьего порядка;
...
nyi = n-1yi+1– n-1yi – конечные разности n-го порядка;
28

29. 3.2.2 Полином Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

Конечные разности:
yi = yi+1–yi – конечные разности первого порядка;
2yi = yi+1– yi – конечные разности второго порядка;
3yi = 2yi+1– 2yi – конечные разности третьего порядка;
...
nyi = n-1yi+1– n-1yi – конечные разности n-го порядка;
29

30. 3.2.2 Полином Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

Таблица конечных разностей:
i
yi
yi
2 yi
3 yi
4 yi
5 yi
0
y0
y0
2y0
3y0
4y0
5y0
1
y1
y1
2y1
3y1
4y1
2
y2
y2
2y2
3y2
3
y3
y3
2y3
4
y4
y4
5
y5
30

31. 3.2.2 1-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

Условия на аi:
Pn(1) ( x0 ) y 0 ,
a0 y 0 ,
Pn(1) ( x1 ) y1 ,
a0 a1 h y1 ,
Pn(1) ( x 2 ) y 2 , a0 2a1 h 2a 2 h 2 y 2 ,
...
...
Pn(1) ( x n ) y n ;
a0 na1 h n(n 1)a 2 h 2 ... n!a n h n y n .
31

32. 3.2.2 1-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

a0 y0 ,
y1 y 0 y 0
a1
,
h
h
y 2 2 y1 y 0 y1
a 0 2a1 h 2a 2 h
2,
2
2h
2h
...
2
Общая формула аi:
k y 0
ak
, k 0,1,..., n
k
k! h
32

33. 3.2.2 2-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

Общая формула:
y 0
2 y 0
n y 0
P ( x) y 0
( x x0 )
( x x0 )( x x1 ) ...
( x x0 )( x x1 )...( x xn 1 )
2
n
h
2!h
n!h
(1)
n
Для программной реализации:
Pn(1) ( x) y 0 y 0
( x x0 )
( x x0 ) ( x x1 )
( x x0 ) ( x x1 ) ( x x 2 )
2 y 0
3 y 0
...
h
h 2
h
h
2h
3h
c1
n y 0
c2
c3
( x x0 ) ( x x1 ) ( x x n 1 )
...
.
h
2h nh
cn
( x x0 )
c1
,
h
( x xk )
c k 1 c k
, k 1,..., n 1
(k 1)h
33

34. 2-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

Условия на bi:
Pn( 2 ) ( x n ) y n ,
b0 y n ,
Pn( 2 ) ( x n 1 ) y n 1 ,
b0 b1 h y n 1 ,
Pn( 2 ) ( x n 2 ) y n 2 , b0 2b1 h 2b2 h 2 y n 2 ,
...
...
Pn( 2 ) ( x0 ) y 0 ;
b0 nb1 h n(n 1)b2 h 2 ... ( 1) n n!bn h n y 0 .
34

35. 2-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

b0 y n ,
y n y n 1 y n 1
b1
,
h
h
y n 2 y n 1 y n 2 y n 2
2
b0 2b1 h 2a 2 h
,
2
2
2h
2h
...
Общая формула bi:
k y n k
bk
, k 0,1,..., n
k
k! h
35

36. 1-я формула Ньютона для равноотстоящих узлов интерполяции (xi+1–xi=h≡const)

Общая формула:
y n 1
2 y n 2
n y 0
P ( x) y n
( x xn )
( x xn )( x xn 1 ) ...
( x x n )( x xn 1 )...( x x1 )
2
n
h
2!h
n!h
( 2)
n
Для программной реализации:
Pn( 2) ( x) y n y n 1
( x xn )
( x x n ) ( x x n 1 )
( x x n ) ( x x n 1 ) ( x x n 2 )
2 y n 1
3 y n 2
...
h
h
2
h
h
2
h
3
h
c1
n y 0
c2
c3
( x x n ) ( x x n 1 ) ( x x1 )
...
.
h
2
h
nh
cn
( x xn )
c1
,
h
( x xn k )
c k 1 c k
, k 1,..., n 1
(k 1)h
36

37. Блок-схема 1-я формула Ньютона

Begin
P:=y[0]
for i:=0 to n do
dy[i]:=y[i]
c:=(x–x[0])/h
for i:=1 to n do
for i:=1 to n do
P:=P+dy[i]*c
for j:=n downto i do
c:=c*(x–x[i])/(h*(i+1))
dy[j]:=dy[j]–dy[j–1]
End
37

38. Блок-схема 2-я формула Ньютона

Begin
P:=y[n]
for i:=0 to n do
c:=(x–x[n])/h
dy[i]:=y[i]
for i:=1 to n do
for i:=1 to n do
P:=P+dy[n–i]*c
for j:=1 to n–i do
c:=c*(x–x[n–i])/(h*(i+1))
dy[j]:=dy[j]–dy[j–1]
End
38

39. Полином Ньютона для неравноотстоящих узлов интерполяции (xi+1–xi=h ≠ const)

Разделенные разности:
xi , xi 1 yi 1 yi
xi 1 xi
– разделенные разности первого порядка;
xi , xi 1 , xi 2 xi 1 , xi 2 xi , xi 1 – разделенные разности второго порядка;
xi 2 xi
xi , xi 1 , xi 2 , xi 3 xi 1 , xi 2 , xi 3 xi , xi 1 , xi 2 – разделенные разности третьего порядка;
xi 3 xi
...
xi , xi 1 ,..., xi n xi 1 ,..., xi n xi ,..., xi n 1 – разделенные разности n-го порядка.
xi n xi
39

40. Полином Ньютона для неравноотстоящих узлов интерполяции (xi+1–xi=h ≠ const)

Таблица разделенных разностей:
i
xi
yi [xi, xi+1] [xi, xi+1, xi+2] [xi, xi+1, xi+2, xi+3] [xi, xi+1, xi+2, xi+3 , xi+4]
0 x0 y0 [x0, x1]
[x0, x1, x2] [x0, x1, x2, x3]
1 x1 y1 [x1, x2]
[x1, x2, x3] [x1, x2, x3 , x4]
2 x2 y2 [x2, x3]
[x2, x3, x4]
[x0, x1, x2, x3 , x4]
3 x3 y3 [x3, x4]
4 x4 y4
40

41. Погрешность полиномиальной интерполяции

Теорема:
M n 1 ~
f (~
x ) Pn ( ~
x)
( x x0 )( ~
x x1 )...( ~
x xn ) ,
(n 1)!
M n 1 max f ( n 1) ( x)
x [ x0 , xn ]

42. Полином Ньютона для неравноотстоящих узлов интерполяции (xi+1–xi=h ≠ const)

Общий вид:
первая формула Ньютона:
Pn(1) ( x) y0 [ x0 , x1 ]( x x0 ) [ x0 , x1 , x2 ]( x x0 )( x x1 ) ...
[ x0 , x1 ,..., xn ]( x x0 )( x x1 )...( x xn 1 );
вторая формула Ньютона:
Pn( 2) ( x) yn [ xn 1 , xn ]( x xn ) [ xn 2 , xn 1 , xn ]( x xn )( x xn 1 ) ...
[ x0 , x1 ,..., xn ]( x xn )( x xn 1 )...( x x1 ).
42

43. Блок-схема 1-я формула Ньютона (в разделенных разностях)

Begin
P:=y[0]
for i:=0 to n do
c:=(x–x[0])
dy[i]:=y[i]
for i:=1 to n do
for i:=1 to n do
P:=P+dy[i]*c
for j:=n downto i do
c:=c*(x–x[i])
dy[j]:=(dy[j]–dy[j–1])/(x[j]-x[j+i])
End
43

44. Блок-схема 2-я формула Ньютона (в разделенных разностях)

Begin
P:=y[n]
for i:=0 to n do
c:=(x–x[n])
dy[i]:=y[i]
for i:=1 to n do
for i:=1 to n do
P:=P+dy[n–i]*c
for j:=1 to n–i do
c:=c*(x–x[n–i])
dy[j]:=(dy[j]–dy[j–1])/(x[j]-x[j+i])
End
44
English     Русский Rules