Вычислительная математика. Ч. 2. Асламова В.С - 7 стр.

UptoLike

13
ции
kiii
yyy
++
,,,
1
K
, причём
nki +
; поэтому при больших значениях i
мы не можем вычислить разности высших порядков (
ink
). Например,
при i=n-3 в (1.16) можно учесть только
yy
2
, ΔΔ
и
y
3
Δ
.
Для правой половины рассматриваемого отрезка разности лучше вычис-
лять справа налево. В этом случае
h
xx
t
n
)(
=
,
т.е. t < 0, и интерполяционный многочлен Ньютона будет иметь вид:
.
!
)1()1(
!2
)1(
)(
02
2
1
y
n
nttt
y
tt
ytythxN
n
nnnn
Δ
+
++Δ
+Δ+=+
K
K
(1.17)
Полученная формула называется вторым интерполяционным многочле-
ном Ньютона для интерполирования назад.
Отметим, что разные способы построения многочленов Лагранжа и Нью-
тона дают тождественные интерполяционные формулы при заданной таблице
значений функции. Это следует из единственности интерполяционного мно-
гочлена заданной степени (при отсутствии совпадающих узлов интерполя-
ции).
Блок-схема интерполяции функции полиномом Ньютона предста
влена на
рис. 3.
1.3. Линейная и квадратичная интерполяция
Простейшим и часто используемым видом локальной интерполяции явля-
ется линейная интерполяция, которая заключается в следующем: узлы интер-
поляции (
ii
yx ,
)(
ni ,,1,0 K
=
) соединяются прямолинейными отрезками,
и функция f(x) аппроксимируется ломаной.
Уравнения каждого отрезка ломаной в общем случае разные. Поскольку
имеется n интервалов (
ii
xx ,
1
), то для каждого из них в качестве уравнения
интерполяционного многочлена используется уравнение прямой, проходящей
через две точки. В частности для i-го интервала можно записать уравнение
прямой, проходящей через точки (
11
,
ii
yx
) и (
ii
yx ,
), в виде:
1
1
1
1
=
ii
i
ii
i
xx
xx
yy
yy
.
14
Начало
ввод N
i := 0, N
ввод
X[i],Y[i]
j
:= 1, N
D[j,1]:=Y[j]-Y[j-1]
j
:= 2, N
i := 1, N
D[i,j]:=0
j
:= 2, N
i :=1, N-J+1
D[i, j]:=D[i+1, j-1]-D[i, j-1]
1
Вычисление первых
разностей
Очистка матрицы
разностей D, кроме
первого столбца
Вычисление j-ых
разностей
ции y i , y i +1 , K, y i + k , причём i + k ≤ n ; поэтому при больших значениях i
мы не можем вычислить разности высших порядков ( k ≤ n − i ). Например,                                  Начало
при i=n-3 в (1.16) можно учесть только Δy , Δ y и Δ y .
                                                      2        3


   Для правой половины рассматриваемого отрезка разности лучше вычис-                                    ввод N
лять справа налево. В этом случае
                                             (x − xn )                                                   i := 0, N
                                       t =             ,
                                                 h
т.е. t < 0, и интерполяционный многочлен Ньютона будет иметь вид:                                         ввод
                                   t (t − 1) 2            t (t − 1)K(t − n + 1) n                        X[i],Y[i]
    N ( xn + th) = y n + tΔy n−1 +          Δ y n−2 + K +                      Δ y0 . (1.17)
                                       2!                           n!
                                                                                                                                Вычисление первых
    Полученная формула называется вторым интерполяционным многочле-
                                                                                                                                разностей
ном Ньютона для интерполирования назад.                                                                  j := 1, N
    Отметим, что разные способы построения многочленов Лагранжа и Нью-
тона дают тождественные интерполяционные формулы при заданной таблице
                                                                                                    D[j,1]:=Y[j]-Y[j-1]
значений функции. Это следует из единственности интерполяционного мно-
гочлена заданной степени (при отсутствии совпадающих узлов интерполя-                                                              Очистка матрицы
ции).                                                                                                                              разностей D, кроме
    Блок-схема интерполяции функции полиномом Ньютона представлена на                                                              первого столбца
                                                                                                         j := 2, N
рис. 3.
                  1.3. Линейная и квадратичная интерполяция
    Простейшим и часто используемым видом локальной интерполяции явля-                                  i := 1, N
ется линейная интерполяция, которая заключается в следующем: узлы интер-
поляции ( x i , y i )( i = 0 , 1, K , n ) соединяются прямолинейными отрезками,                                                     j := 2, N              1
                                                                                                         D[i,j]:=0                                             Вычисление j-ых
и функция f(x) аппроксимируется ломаной.                                                                                                                       разностей
   Уравнения каждого отрезка ломаной в общем случае разные. Поскольку                                                             i :=1, N-J+1
имеется n интервалов ( x i −1 , x i ), то для каждого из них в качестве уравнения
интерполяционного многочлена используется уравнение прямой, проходящей                                                    D[i, j]:=D[i+1, j-1]-D[i, j-1]
через две точки. В частности для i-го интервала можно записать уравнение
прямой, проходящей через точки ( x i −1 , y i −1 ) и ( x i , y i ), в виде:
                                  y − y i −1    x − x i −1 .
                                              =
                                  y i − y i −1 xi − xi −1




                                                                                        13     14