Руев Г.А. и др. Методы вычислений и их реализация в Excel
Подождите немного. Документ загружается.
51
Матрица СЛАУ (3.1) является ленточной, поэтому система
решается с помощью прямого экономичного метода прогонки.
После этого вычисляются коэффициенты
i
b
,
i
d
:
i
ii
i
h
cc
d
1−
−
=
,
i
iiiiii
i
h
ffhdhc
b
1
2
62
−
−
+−=
,
N
i
,...,
2
,
1
=
. (3.2)
В случае постоянной сетки
hh
i
=
, и тогда система уравнений
упрощается:
0
2
64
2,...,3,2
2
64
2
64
2
21
12
2
11
11
2
012
21
=
+−
=++
−=
+−
=++
+
−
=+
−−
−−
−+
+−
N
NNN
NNN
iii
iii
c
h
fff
ccc
Ni
h
fff
ccc
h
fff
cc
Для вычисления значения
(
)
xS
в произвольной точке отрезка
[
]
bax ,
∈
необходимо решить систему уравнений на коэффициенты
i
c
,
1
,...,
2
,
1
−
=
N
i
, затем найти все коэффициенты
i
b
,
i
d
.
Далее, необходимо определить, на какой интервал
[
]
100
,
+ii
xx
попадает эта точка, и, зная номер
0i
, вычислить значение сплайна и
его производных в точке
z
( ) ( )
(
)
(
)
6
2
3
0
0
2
0
0000
i
i
i
iiii
xz
d
xz
cxzbazS
−
+
−
+−+=
,
( ) ( )
(
)
2
2
0
0000
i
iiii
xz
dxzcbzS
−
+−+=
′
,
(
)
(
)
000 iii
xzdczS
−
+
=
′
′
.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
52
ПРИМЕР 3.2.
Задана таблица значений функции
x
0 1/4 1/2 3/4 1
f
1 2 1 0 1
Требуется вычислить значения функции в точках 0,2 и 0,8,
используя сплайн-интерполяцию.
В нашем случае:
4
1
== hh
i
,
,1,0,1,2,1
43210
=
=
=
=
=
fffff
4
=
N
.
Выпишем систему уравнений для определения
i
c
:
( )
( )
0
192
4
1
1021
6
2
64
0
220
6
2
64
192
4
1
1221
6
2
64
4
2
2
234
432
22
123
321
2
2
012
21
=
=
+⋅−
=
+−
=++
=
+−
=
+−
=++
−=
+⋅−
=
+
−
=+
c
h
fff
ccc
hh
fff
ccc
h
fff
cc
.
Решая эту систему линейных уравнений, получим:
1 2 3 4
48, 0, 48, 0
c c c c
= − = = =
.
192
4
1
48
01
1
−=
−
=
−
=
h
cc
d
,
192
4
1
48
12
2
==
−
=
h
cc
d
,
192
4
1
48
23
3
==
−
=
h
cc
d
,
192
4
1
48
34
4
−=−=
−
=
h
cc
d
.
0
4
1
12
616
192
8
48
62
01
2
11
1
=
−
+
⋅
+
−
=
−
+−=
h
ffhdhc
b
,
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
53
6
4
1
21
616
192
62
12
2
22
2
−=
−
+
⋅
−=
−
+−=
h
ffhdhc
b
,
0
4
1
10
616
192
8
48
62
23
2
33
3
=
−
+
⋅
−=
−
+−=
h
ffhdhc
b
,
6
4
1
01
616
192
62
34
2
44
4
=
−
+
⋅
=
−
+−=
h
ffhdhc
b
,
1,0,1,2
4321
==== aaaa
.
Рассмотрим точку 0,2, которая принадлежит первому отрезку,
т.е.
10
=
i
.
Следовательно, получим,
( ) ( )
(
)
(
)
6
2
3
1
1
2
1
1111
xz
d
xz
cxzbazS
−
+
−
+−+=
( ) ( )
(
)
(
)
944,1
6
25,02,0
192
2
25,02,0
4825,02,0022,0
32
=
−
−
−
−−+=S
Итак, значение функции в точке 0,2 равняется 1,944.
Рассмотрим точку 0.8, которая принадлежит четвертому отрезку,
т.е.
30
=
i
.
Следовательно,
( ) ( )
(
)
(
)
( ) ( )
( ) ( )
064,0000125,0*320025,0*24
6
75,08,0
192
2
75,08,0
4875,08,0008,0
62
32
3
3
3
2
3
3333
=+=
=
−
+
−
+−+=
−
+
−
+−+=
S
xz
d
xz
cxzbazS
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
54
Глобальная интерполяция
В случае глобальной интерполяции отыскивается единая
интерполирующая функция на всем интервале
[
]
ba,
. Самым
распространенным способом является полиномиальная интерполяция.
Будем искать интерполирующую функцию в виде полинома
(многочлена)
m
-ой степени
(
)
m
mm
xaxaxaaxP ++++= ...
2
210
. Какова
должна быть степень многочлена, чтобы удовлетворить всем
условиям интерполяции?
Допустим, что заданы две точки:
(
)
00
, fx
и
(
)
11
, fx
, т.е.
1
=
N
.
Через эти точки можно провести единственную прямую, т.е.
интерполирующей функцией будет полином первой степени
(
)
xaaxP
101
+
=
.
Через три точки (
2
=
N
) можно провести параболу
(
)
2
2102
xaxaaxP ++=
и т.д.
Рассуждая таким способом, можно предположить, что искомый
полином должен иметь степень
N
.
Для того, чтобы доказать это, выпишем систему уравнений на
коэффициенты. Уравнения системы представляют собой условия
интерполяции при каждом
i
xx
=
:
(
)
( )
( )
=+++++=
=+++++=
=+++++=
N
f
N
N
x
N
a
N
xa
N
xa
N
xaa
N
x
N
P
f
N
x
N
axaxaxaax
N
P
f
N
x
N
axaxaxaax
N
P
...
3
3
2
210
...
22
...
3
23
2
222102
11
...
3
13
2
121101
.
Данная система является линейной относительно искомых
коэффициентов
N
aaaa ,..,.,,
210
.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
55
Известно, что СЛАУ имеет решение, если ее определитель
отличен от нуля.
Определитель данной системы
( )
∏
≤<≤
−==∆
Nmk
mk
N
NN
N
N
xx
xx
xx
xx
0
22
11
...1
............
...1
...1
носит имя Вандермонда.
Из курса математического анализа известно, что он отличен от
нуля, если
mk
xx
≠
. В нашем случае это означает, что все узлы
интерполяции различны, что верно по определению.
Таким образом, доказано, что система имеет решение.
Мы показали, что для нахождения коэффициентов
N
aaaa ,..,.,,
210
надо решить СЛАУ, что является сложной задачей.
Но есть другой способ построения полинома
N
-й степени,
который не требует решения такой системы.
Полином Лагранжа
Решение ищем в виде
( ) ( )
∑
=
=
N
i
iin
zlfzL
0
,
где
(
)
zl
i
– базисные полиномы
N
-й степени,
для которых выполняется условие:
( )
≠
=
=
ki
ki
xl
ki
,0
,1
.
Убедимся в том, что если такие полиномы построены,
то
(
)
xL
N
будет удовлетворять условиям интерполяции:
( ) ( ) ( ) ( ) ( ) ( )
k
N
i
kNNkiikkkiikn
fxlfxlfxlfxlfxlfxL =+++++==
∑
=0
1100
......
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
56
Каким образом построить базисные полиномы?
Определим
( )
(
)
(
)
(
)
(
)
(
)
( )( ) ( )( ) ( )
Niiiiiii
Nii
i
xxxxxxxxxx
xzxzxzxzxz
zl
−−−−−
−
−
−
−
−
=
+−
+−
......
......
1110
1110
,
N
i
,...,
2
,
1
,
0
=
.
Легко понять, что
( )
(
)
(
)
(
)
( )( ) ( )
N
N
xxxxxx
xzxzxz
zl
−−−
−
−
−
=
02010
21
0
...
...
,
( )
(
)
(
)
(
)
( )( ) ( )
N
N
xxxxxx
xzxzxz
zl
−−−
−
−
−
=
12101
20
1
...
...
, и т.д.
Функция
(
)
zl
i
является полиномом
N
–й степени от
z
и для нее
выполняются условия «базисности»:
( )
(
)
(
)
(
)
(
)
(
)
( )( ) ( )( ) ( )
ki
xxxxxxxxxx
xxxxxxxxxx
xl
Niiiiiii
Nkikikkk
ki
≠=
−−−−−
−
−
−
−
−
=
+−
+−
,0
......
......
1110
1110
,
т.е.
N
i
i
k
,...,
1
,
1
,...,
2
,
1
+
−
=
;
( )
(
)
(
)
(
)
(
)
(
)
( )( ) ( )( ) ( )
ki
xxxxxxxxxx
xxxxxxxxxx
xl
Niiiiiii
Niiiiiii
ii
==
−−−−−
−
−
−
−
−
=
+−
+−
,1
......
......
1110
1110
.
Таким образом, нам удалось решить задачу о построении
интерполирующего полинома
N
-й степени, и для этого не нужно
решать СЛАУ.
Полином Лагранжа можно записать в виде компактной формулы:
( ) ( )
(
)
( )
∑ ∏∑
= ≠=
−
−
==
N
i ki
ki
k
i
N
i
iiN
xx
xz
fzlfzL
00
.
Погрешность этой формулы можно оценить, если исходная
функция
(
)
xg
имеет производные до
1
+
N
порядка:
( )
(
)
(
)
( )
( )
[ ]
baxz
N
g
zr
N
i
i
N
,,
!1
1
0
1
∈−
+
=
∏
+
=
+
ξ
ξ
.
Из этой формулы следует, что погрешность метода зависит от
свойств функции
(
)
xg
, а также от расположения узлов интерполяции
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
57
и точки
z
. Как показывают расчетные эксперименты, полином
Лагранжа имеет малую погрешность при небольших значениях
20
<
N
. При бόльших
N
погрешность начинает расти, что
свидетельствует о том, что метод Лагранжа не сходится (т.е. его
погрешность не убывает с ростом
N
).
Рассмотрим частные случаи.
Пусть
1
=
N
, т.е. заданы значения функции только в двух точках.
Тогда базовые полиномы имеют вид:
( )
(
)
( )
10
1
0
xx
xz
zl
−
−
=
,
( )
(
)
( )
01
0
1
xx
xz
zl
−
−
=
,
( ) ( ) ( ) ( )
(
)
( )
(
)
( )
( ) ( )
1
01
01
1
01
01
01
0
1
10
1
01100
0
x
xx
ff
fz
xx
ff
xx
xz
f
xx
xz
fzlfzlfzlfzL
N
i
iiN
−
−
−+
−
−
=
=
−
−
+
−
−
=+==
∑
=
,
т.е. получаем формулы кусочно-линейной интерполяции.
Пусть
2
=
N
. Тогда:
( )
(
)
(
)
( )( )
2010
21
0
xxxx
xzxz
zl
−−
−
−
=
,
( )
(
)
(
)
( )( )
2101
20
1
xxxx
xzxz
zl
−−
−−
=
,
( )
(
)
(
)
( )( )
1202
10
2
xxxx
xzxz
zl
−−
−−
=
,
( ) ( )
(
)
(
)
( )( )
(
)
(
)
( )( )
( )( )
( )( )
1202
10
2101
20
1
2010
21
0
2
0
2
xxxx
xzxz
xxxx
xzxz
f
xxxx
xzxz
fzlfzL
i
ii
−−
−−
+
+
−−
−−
+
−−
−−
==
∑
=
.
В результате мы получили формулы, так называемой
квадратичной или параболической интерполяции.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
58
ПРИМЕР 3.3.
Задана таблица значений функции:
x
0 2 3 3,5
f
-1 0,2 0,5 0,8
Требуется найти значение функции при
1
=
z
, используя
интерполяционный полином Лагранжа.
Для этого случая
3
=
N
, т.е. полином Лагранжа имеет третий порядок.
Вычислим значения базисных полиномов при
1
=
z
:
( )
(
)
(
)
(
)
( )( )( )
(
)
(
)
(
)
( )( )( )
238,0
21
5
5,332
5,221
5,303020
5,313121
1
0
=
−
−
=
−−−
−
−
−
=
−−−
−
−
−
=l
,
( )
(
)
(
)
(
)
( )( )( )
(
)
(
)
(
)
( )( )( )
667,1
3
5
5,112
5,221
5,323202
5,313101
1
1
==
−−
−
−
=
−−−
−
−
−
=l
,
( )
(
)
(
)
(
)
( )( )( )
(
)
(
)
(
)
( )( )( )
667,1
5,1
5,2
5,013
5,211
5,332303
5,312101
1
2
−=
−
=
−
−
−
=
−−−
−
−
−
=l
,
( )
(
)
(
)
(
)
( )( )( )
(
)
(
)
(
)
( )( )( )
762,0
625,2
2
5,05,15,3
211
35,325,305,3
312101
1
3
==
−
−
=
−−−
−
−
−
=l
( ) ( ) ( ) ( )
129,0762,08,0
667,15,0667,12,0238,01
3
0
3
−=⋅+
−⋅+⋅+−==
∑
=i
ii
zlfzL
Итак, интерполирующая функция принимает в точке 1 значение -
0,129.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
59
Подбор эмпирических формул
При интерполировании функций мы использовали условие
равенства значений интерполяционного полинома и данной функции в
узлах интерполяции. Если же исходные данные получены в результате
опытных измерений, полученных с некоторой погрешностью, точного
выполнения условий интерполяции не требуется. В этих случаях
интерполирующая функция F(x) должна удовлетворять условиям
(
)
(
)
ε
<−
ii
xfxF
, i=1, 2, …, N.
Это условие означает, что интерполирующая функция
(
)
xF
проходит не точно через заданные точки, а в некоторой их окрестности,
как, например, показано на рис. 3.3.
Рис. 3.3. Приближенная интерполяция
Тогда говорят о подборе эмпирических формул, описывающих
заданные точки.
Построение эмпирической формулы состоит из двух этапов:
1. подбор вида этой формулы
(
)
m
aaax ,...,,,
10
ϕ
, содержащей
неизвестные параметры
m
aaa ,...,,
10
, и
2. определение наилучших в некотором смысле этих параметров.
Вид формулы иногда известен из физических соображений
(например, связь между напряжением и деформацией для упругой
среды), или выбирается из геометрических соображений.
x
y
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
60
Для этого экспериментальные точки наносятся на график и путем
сравнения поведения точек с графиками известных функций
подбирается общий вид зависимости.
Успех в значительной степени определяется опытом и интуицией
исследователя.
Для практики важен случай аппроксимации функции
многочленами, т.е.
(
)
m
m
xaxaxaaxF ++++= ...
2
210
.
После того, как выбран вид эмпирической зависимости, степень
близости к эмпирическим данным определяется, используя минимум
суммы квадратов отклонений вычисленных и
экспериментальных данных.
Метод наименьших квадратов
Пусть для исходных данных
Nifx
ii
,...,2,1,,
=
выбран вид
эмпирической зависимости:
(
)
m
aaaxy ,...,,,
10
ϕ
=
с неизвестными коэффициентами
m
aaa ,...,,
10
.
Запишем сумму квадратов отклонений между вычисленными по
эмпирической формуле и заданными опытными данными:
( ) ( )( )
∑
=
−=
N
i
imm
faaaxaaaS
1
2
1010
,...,,,,...,,
ϕ
.
Параметры
m
aaa ,...,,
10
будем находить из условия минимума
функции
(
)
m
aaaS ,...,,
10
.
В этом состоит метод наименьших квадратов (МНК).
Известно, что в точке минимума все частные производные от
S
по параметрам
m
aaa ,...,,
10
равны нулю:
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.