Поскольку точность интерполяции функции зависит от количества используемых узлов, то оценку погрешности интерполяции в точке принято проводить по следующей формуле:
R |
| f(x) L |
m |
(x) | | L |
(x) L |
m |
(x) |, |
m |
|
|
m 1 |
|
где m– число узлов, используемое в формуле.
В этом случае, для того чтобы добиться заданной точности, при решении задачи интерполяции нужно использовать две процедуры (рис. 2.2-1 и 2.2-2). Если функция интерполируется при заданном количестве узлов, используется только процедура, представленная на рис. 2.2-2.
Для того чтобы уменьшить погрешность интерполяции, используется прием перенумерации узлов исходной таблицы [3].
2.2.2. Первая интерполяционная формула Ньютона
Первая интерполяционная формула Ньютона используется, если требуется найти значение функцииy=f(x), заданной в равноотстоящих узлах
так, что |
|
xi = x0 +ih, где h – |
шаг интерполяции, |
а i = 0, 1, …, n, в точке, |
|||||||||||||||||||||
расположенной в начале таблицы. |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
Формула имеет следующий вид [3]: |
|
|
y |
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
y |
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|||
P (x) y |
|
|
|
|
(x x |
) |
|
2 |
|
|
(x x |
)(x x |
) ... |
n |
|
|
(x x |
)...(x x |
|
). |
|||||
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
n |
|
|
0 |
|
1!h |
|
0 |
|
|
|
|
2 |
|
0 |
1 |
|
|
n |
0 |
|
n 1 |
|
|||
|
|
|
|
|
|
|
|
|
2!h |
|
|
|
|
|
n!h |
|
|
|
|
|
|||||
Здесь y0, |
2y0, … |
|
ny0 – соответствующие конечные разности. |
|
|||||||||||||||||||||
Если интерполируемая функция задана таблично, то оценку |
|||||||||||||||||||||||||
погрешности интерполяции можно произвести по формуле: |
|
|
|
||||||||||||||||||||||
R |
|
q(q 1)...(q n) |
|
n 1 |
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
n |
|
|
|
(n 1)! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Схема алгоритма интерполяции в точкепо первой формуле Ньютона приведена на рис. 2.2-3. При необходимости получения значений интерполяционного полинома при разном количестве узлов, в процедуре рекомендуется вставить промежуточную печать.
20
Рис. 2.2-3. Алгоритм интерполяции в точке по 1-й формуле Ньютона
21
2.2.3. Вторая интерполяционная формула Ньютона
Вторая интерполяционная формула Ньютона используется, если требуется найти значение функции y=f(x), заданной в равноотстоящих узлах
так, что |
x |
i |
= x0 +ih, где h – шаг интерполяции, |
|
|||
|
|
|
расположенной в конце таблицы. Формула имеет следующий вид [3]:
а i = 0, 1, …, n, в точке,
|
|
|
|
|
|
|
|
|
|
y |
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
n |
|
|
|
P (x) y |
|
y |
|
q |
|
|
|
n 2 |
q(q 1) |
... |
|
|
0 |
q(q 1)...(q n 1). |
|||
n |
|
|
|
|
|
|
|
|
|||||||||
n |
|
|
|
n 1 |
|
|
2! |
|
|
n! |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Здесь Δyn-1, |
2yn-2, … |
|
|
ny0 – соответствующие конечные разности. |
|||||||||||||
Если интерполируемая функция задана таблично, то оценку |
|||||||||||||||||
погрешности интерполяции можно произвести по формуле: |
|||||||||||||||||
R |
q(q 1)...(q n) |
|
n 1 |
y |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|||
n |
|
(n 1)! |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Схема алгоритма интерполяции в точке с заданной степенью точности по второй формуле Ньютона приведена на рис. 2.2-4. Здесь точность интерполяции достигается путем добавления узлов. Если исчерпаны все узлы заданной таблицы, а точность не достигнута, то за результат принимается значение интерполяционного многочлена при максимальном количестве узлов. В качестве выходного параметра выступает массив значений полинома в точке хх, где индекс массива – текущая степень интерполяционного полинома.
Рис. 2.2-4.Алгоритм интерполяции в точке по 2-й формуле Ньютона
22
Рис. 2.2-5. Заполнение матрицы конечных разностей
23
Рис. 2.2-6. Вычисление значения полинома степени iв точке хх
Рис. 2.2-7. Вычисление значения полинома степени m
2.3.Алгоритм аппроксимации функции методом наименьших квадратов
Схема алгоритма, аппроксимации функции по методу наименьших квадратов (МНК) приведена на рис. 2.4-1.
МНК[3] является одним из наиболее распространенных методов аппроксимации функции. В этом методе параметры a0, a1, ..., an
определяются из условия минимума суммы квадратов отклонений значений аппроксимирующей функции от табличных данных.
Вектор коэффициентов aT определяют из условия минимизации
n |
n |
|
|
2 |
[φ(xi ) f(xi )] |
2 |
min, |
E ei |
|
||
i 0 |
i 0 |
|
|
где (n+1) – количество узловых точек. φ(x)=a0φ0(x)+a1φ1(x)+...+amφm(x) – аппроксимирующая функция
степениm
Для получения искомых значений параметров a0, a1,…amследует составить и решить систему (m+1) линейных уравнений
E |
0, |
E |
0,... |
E |
0. |
|||
a |
0 |
a |
a |
m |
||||
|
|
|
||||||
|
|
1 |
|
|
|
|||
24
В качестве меры уклонения заданных значений функции y0, y1, ..., yn от многочлена степени m -, принимается величина
|
1 |
n |
|
|
|
|
|
|
|
ρ |
|
[φ |
(x |
) f(x |
2 |
, |
|
||
|
)] |
|
|||||||
|
n 1 |
m |
i |
i |
|
|
|
||
|
i 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Поскольку |
МНК |
требует решения системы линейных |
уравнений |
||||||
(СЛУ), на рис. 2.4-2 |
приведена схема алгоритма решения СЛУ методом |
||||||||
Гаусса [1]. Метод |
сводится к последовательному исключению |
1 из всех |
|||||||
|
|
|
|
|
|
|
|
|
x |
уравнений, начиная со второго, затем
x |
2 |
|
- начиная с третьего и т.д. Это
позволяет получить эквивалентную систему, имеющую треугольную матрицу (прямой ход), а затем, действуя в противоположной последовательности, получают решение (обратный ход).
Рис. 2.3-1.Алгоритм метода наименьших квадратов
25
Рис. 2.3-2. Формирование матрицы Грама
Рис. 2.3-3. Вычисление элемента матрицы Грама
26
Рис. 2.3-4. Вычисление элемента правой части системы нормальных уравнений
27
Рис. 2.3-5.Решение системы линейных уравнений методом Гаусса
28
Рис. 2.3-6.Вычисление значения аппроксимирующей функции в заданных точках
Рис. 2.3-7. Вычисление невязки
29