Материал: Алгоритмы пособие
Рис. 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