Интерполяция и аппроксимация функций

1. Интерполяция и аппроксимация функций

2. Таблично-заданная функция:

X
Y
x1
y1
x2
y2
...
...
xi
yi
…
…
xn
yn
Достоинство:
Нет необходимости
проводить
дополнительные расчеты
значения функции.
Недостаток:
Невозможность
определения значений
функции при значениях
аргумента, отличных от
табличных.

3. Графическая интерпретация методов: Интерполяция Аппроксимация

y
y
y*=f(x)
y*=f(x)
yi
yi
y=f(x)
y1
y=f(x)
y1
Узлы
Узлы
x1
xi
x
x1
xi
x

4. 1. Интерполяция функций

А) Глобальная интерполяция.
Б) Локальная интерполяция.

5. Локальная интерполяция

Необходимо определиться с видом
интерполирующей функции.
На практике чаще всего использую
следующие виды локальной
интерполяции:
1. Линейная интерполяция
2. Квадратичная интерполяция
3. Сплайн-интерполяция

6. Глобальная интерполяция

Необходимо, чтобы одна интерполирующая
функция проходила через все узлы
таблично заданной функции.
Обычно в этом случае интерполирующую
функцию ищут в виде полинома:
y=c0+c1x+c2x2 +…+cixi+…+cn-1xn-1
Через n точек может проходить только один
график функции полинома n-1 порядка.

7. Интерполяция методом канонических полиномов

В уравнение полиномиальной зависимости
подставляются все значения точек x - y
(аргумент - функция) табличной зависимости.
Таким образом, получается система линейных
уравнений n-го порядка:
c0 c1 x1 c 2 x12 ci x1i c n 1 x1n 1 y1
2
i
n 1
c
c
x
c
x
c
x
c
x
y2
0 1 2
2 2
i 2
n 1 2
2
i
n 1
c
c
x
c
x
c
x
c
x
yi
0 1 i
2 i
i i
n 1 i
c0 c1 x n c 2 x n2 ci x ni c n 1 x nn 1 y n

8.

Решаем полученную СЛАУ одним из
известных методов, получаем значения
параметров полиномиальной зависимости:
c0, c1, c2,…, ci,…, cn-1
В полученное уравнение полиномиальной
функции с найденными параметрами
подставляем значение аргумента xц и
находим значение функции yц.
Данный метод удобен в случаях, когда
необходимо найти несколько значений
функции при нескольких значениях
аргумента.

9. Интерполяция методом полинома Лагранжа

Данный метод удобен в случаях, когда
необходимо найти только одно значение
функции при одном значении аргумента.
В этом методе полином n-1 степени
представляется в виде:
yц y1l1 y 2 l 2 ... yi li ... y n l n
где l1, l2, …, li, …, ln - являются также
полиномиальными зависимостями.

10.

Данные полиномы рассчитываются по следующим формулам:
xц x 2 xц x3
xц xi
xц x n
l1
...
...
x1 x 2 x1 x3
x1 xi
x1 x n
xц x1 xц x3
xц xi
xц x n
l2
...
...
x 2 x1 x 2 x3
x 2 xi
x2 xn
xц x1 xц x 2
xц xi 1 xц xi 1
xц x n
li
...
...
xi x1 xi x 2
xi xi 1 xi xi 1
xi x n
Коэффициент li будет равен 1, если xц=xi , и будет равен 0
(нулю), если xц= x1 , x2 и так далее.

11. Блок-схема интерполяции полиномом Лагранжа

НАЧАЛО
yy=0
ввод
n
Количество пар точек
i=1, n
i=1, n
L=1
ввод
x(i), y(i)
Ввод табличной функции
j=1, n
ввод
xx
Ввод аргумента, при
котором необходимо
рассчитать значение
функции
нет
i≠j
да
L=L*(xx-x(j))/(x(i)-x(j))
Блок-схема
интерполяции
полиномом
Лагранжа
yy=yy+y(i)*L
вывод
yy
КОНЕЦ

12. Достоинства метода интерполяции:

Если исходная таблично заданная функция не
содержит в себе погрешности, то метод
интерполяции дает достаточно точные и
достоверные результаты.
Недостатки метода интерполяции:
1. В случае локальной интерполяции получается
несколько интерполирующих функций, с которыми
неудобно работать.
2. В случае глобальной интерполяции при достаточно
большом количестве пар точек (узлов) получается
достаточно сложная и громоздкая
интерполирующая функция.
3. Если исходная таблично заданная функция
содержит в себе погрешность, то интерполирующая
функция также будет «копировать» эту погрешность
и не даст необходимого достоверного результата.

13. 2. Аппроксимация функций

Всех перечисленных недостатков
интерполяции лишен метод
аппроксимации функций.
Аппроксимирующая функция не проходит
через все узлы, а лежит максимально
близко к ним.
В этом методе в случае флуктуаций
(выбросов) точек, аппроксимирующая
функция получается достаточно гладкой.

14. Пример:

Рассматривается линейная функция.
Метод интерполяции в этом случае неприменим.
Применяется метод аппроксимации.
y
x

15. Возникает вопрос:

Каков критерий близости
аппроксимирующей функции к исходной
таблично заданной?
МЕТОД НАИМЕНЬШИХ КВАДРАТОВ (МНК).
Суть: Аппроксимирующая функция должна
быть такой, чтобы сумма квадратов
отклонений аппроксимирующей функции
от исходной таблично заданной была
минимальной.

16. Согласно МНК только одна функция будет лежать максимально близко к исходным узлам.

y
Согласно МНК
только одна функция
будет лежать
максимально близко
к исходным узлам.
x
y
7
6
4
2
1
3
5
y=y*(x)
n
n
i 1
i 1
S 2i ( yi y * ( xi )) 2 min
x

17. Замечание:

МЕТОД НАИМЕНЬШИХ КВАДРАТОВ не
позволяет определить вид
аппроксимирующей функции.
МНК позволяет определить только
параметры выбранного вида
аппроксимирующей функции.
Вид аппроксимирующей функции
определяет пользователь исходя из
теоретических знаний, логических
предпосылок или других разумных
соображений.

18. Аппроксимация линейной функцией

В качестве аппроксимирующей
выбирают линейную функцию:
y*=c0+c1x.
Здесь c0 и c1 - параметры функции,
которые определим с использованием
МНК.

19.

В формулу суммы квадратов отклонений
подставим аппроксимирующую линейную
функцию, получим:
n
n
n
S ( yi y ( xi )) ( yi c0 c1 xi ) 2 min
i 1
2
i
*
i 1
2
i 1
Находим минимум функции S,приравняв
частные производные функции S по
параметрам аппроксимирующей функции
нулю:
n
S
2 ( yi c0 c1 xi ) xi 0
c1
i 1
n
S
2 ( yi c0 c1 xi ) 0
c0
i 1

20.

Преобразуем полученные выражения:
n
2
(
x
y
c
x
i i 1 i c0 xi ) 0
i 1
n
(y
i 1
i
c1 xi c0 ) 0
В результате получаем СЛАУ, где в качестве
неизвестных выступают параметры линейной
функции c0 и c1:
n
n
n 2
c1 xi c0 xi xi yi
i 1
i 1
i 1
n
n
c
1 xi c0 n yi
i 1
i 1

21.

Решаем полученную СЛАУ методом Крамера:
n
c1
x y
i
i 1
i
n
n
i 1
i 1
2
n xi y i
n
x n xi
i 1
i 1
n
2
i
n
c0
n
n
n
x y x y x
i 1
2
i
i 1
i
i 1
i
i
n
2
xi n xi
i 1
i 1
n
i 1
i
2
Таким образом, вычислив параметры c0 и c1, мы
получаем линейную аппроксимирующую функцию:
y*=c0+c1x.

22. Блок-схема аппроксимации линейной функцией

НАЧАЛО
i=1, n
ввод
n
Количество пар точек
S1=S1+xi*xi
S2=S2+xi
S3=S3+xi*yi
S4=S4+yi
i=1, n
ввод
x(i), y(i)
ввод
xx
Ввод табличной функции
Ввод аргумента, при
котором необходимо
рассчитать значение
функции
c1=(S3*n-S2*S4)/(S1*n-S22))
c0=(S1*S4-S2*S3)/(S1*n-S22))
yy=c0+c1*xx
S1=0; S2=0
S3=0; S4=0
вывод
c1, c0, yy
Блок-схема
аппроксимации
линейной функцией
КОНЕЦ

23. Аппроксимация квадратичной функцией

В качестве аппроксимирующей
выбирают квадратичную функцию:
y*=c0+c1x+c2x2.
Здесь c0 , c1 и c2 - параметры функции,
которые определим с использованием
МНК.

24.

В формулу суммы квадратов отклонений подставим
аппроксимирующую квадратичную функцию, получим:
n
n
n
S ( yi y ( xi )) ( yi c0 c1 xi c2 xi2 ) 2 min
i 1
2
i
*
i 1
2
i 1
Для нахождения минимума функции S приравняем
частные производные функции S по параметрам
аппроксимирующей функции нулю:
n
S
2 ( yi c0 c1 xi c2 xi2 ) xi2 0
c2
i 1
n
S
2 ( yi c0 c1 xi c2 xi2 ) xi 0
c1
i 1
n
S
2 ( yi c0 c1 xi c2 xi2 ) 0
c0
i 1

25.

Преобразуем полученные выражения следующим образом:
n
2
4
3
2
(
x
y
c
x
c
x
c
x
i i 2 i 1 i 0 i ) 0
i 1
n
3
2
(
x
y
c
x
c
x
i i 2 i 1 i c0 xi ) 0
i 1
n
2
(
y
c
x
i 2 i c1 xi c0 ) 0
i 1
В результате получаем систему линейных алгебраических
уравнений, где в качестве неизвестных выступают параметры
квадратичной функции c0 , c1 и c2:
n
n
n
n 4
3
2
2
c
x
c
x
c
x
x
1 i
0 i
i yi
2 i
i 1
i 1
i 1
i 1
n
n
n
n 3
2
1
c2 xi c1 xi c0 xi xi yi
i 1
i 1
i 1
i 1
n
n
n 2
c2 xi c1 xi c0 n yi
i 1
i 1
i 1

26.

Решаем полученную СЛАУ методом Крамера
для систем 3-го порядка и вычисляем
параметры c0 , c1 и c2.
Таким образом, мы получаем квадратичную
аппроксимирующую функцию:
y*=c0+c1x+c2x2

27. Блок-схема аппроксимации квадратичной функцией

НАЧАЛО
i=1, n
ввод
n
Количество пар точек
i=1, n
ввод
x(i), y(i)
ввод
xx
Ввод табличной функции
Ввод аргумента, при
котором необходимо
рассчитать значение
функции
S1=0; S2=0
S3=0; S4=0
S5=0; S6=0
S7=0
Блок-схема
аппроксимации
квадратичной функцией
S1=S1+xi4
S2=S2+xi3
S3=S3+xi2
S4=S4+xi
S5=S5+xi2*yi
S6=S6+xi*yi
S7=S7+yi
a11=S1; a12=S2; a13=S3
a21=S2; a22=S3; a23=S4
a31=S3; a32=S4; a33=n
b1=S5; b2=S6; b3=S7
c2= вычисляются
c1= по формулам
c0=
Крамера
yy=c0+c1*xx+с2*xx2
вывод
c2,c1,c0,yy
КОНЕЦ