1.37M
Category: mathematicsmathematics

Интерполяция, экстраполяция, аппроксимация

1.

Тема лекции:
Интерполяция, экстраполяция,
аппроксимация

2.

Интерполяция — в вычислительной математике способ
нахождения промежуточных значений величины по
имеющемуся дискретному набору известных значений.
Экстраполяция — особый тип аппроксимации, при
котором функция аппроксимируется вне заданного
интервала, а не между заданными значениями.
Аппроксимация — научный метод, состоящий в замене
одних объектов другими, в каком-то смысле близкими к
исходным, но более простыми.

3.

ИНТЕРПОЛЯЦИЯ
оригинал
увеличенный участок
интерполяция

4.

ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ
y
X X1
Y Y1
X 2 X1 Y2 Y1
Y2,X2
Y
Y-Y1
Y1,X1
X-X1
Y2-Y1
X
x
Даны две точки: X1, Y1 и X2, Y2. Найти Y для заданной точки X.
Y = Y1+(X-X1)(Y2-Y1)/(X2-X1)
Пример. X1=4, Y1=10. X2=8, Y2=15. Найти Y для X=5.
Y = 10 + (5-4)(15-10)/(8-4) = 11.25

5.

ИНТЕРПОЛЯЦИЯ КУБИЧЕСКИМ СПЛАЙНОМ
Сплайн – функция, которая вместе с несколькими производными
непрерывна на всем заданном отрезке [a, b],  а на каждом частичном
отрезке [xi, xi+1], в отдельности является некоторым алгебраическим
многочленом.
P1, P2, P3, P4 – известные значения функции в точках 0, 1, 2, 3.
Нужно вычислить значение Y для точки X, лежащей между 1 и 2.
D = P2
C = (P3-P1)/2
A = -0.5*P1 + 1.5*P2 - 1.5*P3 + 0.5*P4
B = P1 - 2.5*P2 + 2*P3 - 0.5*P4
Z=X-1
Y = A * Z3 + B * Z2 + C*Z + D

6.

ИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН ЛАГРАНЖА
Интерполяционный многочлен Лагранжа — многочлен минимальной
степени, принимающий данные значения в данном наборе точек. Для n+1 пар
чисел (x0, y0), (x1, y1),…, (xn, yn), где все xj различны, существует единственный
многочлен L(x) степени не более n, для которого L(xj) = yj.
Лагранж предложил способ вычисления таких многочленов:
где базисные полиномы определяются по формуле:

7.

ИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН ЛАГРАНЖА
ПРИМЕР. Найдем формулу интерполяции для f(x) = tan(x) имеющей следующие
значения:

8.

ИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН ЛАГРАНЖА
Функция тангенса и интерполяция

9.

БИЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ
Билинейная интерполяция — расширение линейной интерполяции для функций двух
переменных. Ключевая идея заключается в том, чтобы провести обычную линейную
интерполяцию сначала в одном направлении, затем в перпендикулярном. Формула
билинейной интерполяции интерполирует значения функции в произвольном
прямоугольнике по четырем её значениям в вершинах прямоугольника и экстраполирует
функцию на всю остальную поверхность.
Даны четыре точки: (X1,Y1,Z1), (X2,Y2,Z2), (X3,Y3,Z3) и (X4,Y4,Z4).
Найти Z для заданной точки X,Y.
Пусть F(X1,Y1,X2,Y2,X) вычисляет линейную интерполяцию для точки
X по точкам (X1,Y1) и (X2,Y2).
Вычисление билинейной интерполяции:
1) Z5 = F(X1,Z1,X2,Z2,X)
2) Z6 = F(X3,Z3,X4,Z4,X)
3) Z = F(Y1,Z5,Y3,Z6,Y)

10.

ЭКСТРАПОЛЯЦИЯ
ЭКСТРАПОЛЯЦИЯ — определение будущих, ожидаемых значений
величин, показателей на основе имеющихся данных о тенденциях их
изменений в прошлые периоды. Математически сводится к
продолжению кривой.
Методы экстраполяции
интерполяции.
во многих случаях сходны
с
методами
Применение.
Общее значение — распространение выводов, полученных
наблюдения над одной частью явления, на другую его часть.
из
В маркетинге — распространение выявленных закономерностей
развития изучаемого предмета на будущее.
В статистике — распространение установленных в прошлом
тенденций на будущий период (экстраполяция во времени применяется
для перспективных расчетов населения); распространение выборочных
данных на другую часть совокупности, не подвергнутую наблюдению.

11.

АППРОКСИМАЦИЯ
Аппроксимация
позволяет
исследовать
числовые
характеристики
и
качественные свойства объекта, сводя задачу к изучению более простых или
более удобных объектов (например, таких, характеристики которых легко
вычисляются или свойства которых уже известны).
В геометрии рассматриваются аппроксимации кривых ломаными. Некоторые
разделы математики в сущности целиком посвящены аппроксимации,
например, теория приближения функций, численные методы анализа.
Аппроксимацией (приближением) функции f(x) называется нахождение такой
функции (аппроксимирующей функции) g(x), которая была бы близка
заданной. Критерии близости функций могут быть различные.
В случае если приближение строится на дискретном
аппроксимацию называют точечной или дискретной.
наборе
точек,
В случае если аппроксимация проводится на непрерывном множестве точек
(отрезке),
аппроксимация
называется непрерывной или интегральной.
Примером такой аппроксимации может служить разложение функции в ряд
Тейлора, то есть замена некоторой функции степенным многочленом.

12.

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

13.

МЕТОД НАИМЕНЬШИХ КВАДРАТОВ
Дана таблица исходных данных. Используя метод наименьших
квадратов, аппроксимировать эти данные какой либо зависимостью,
например линейной y=ax+b (коэффициенты a, b - неизвестные).
Находим частные производные функции по приведенной формуле
F(a,b) по переменным а и b, приравниваем эти производные к нулю.

14.

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

15.

МЕТОД НАИМЕНЬШИХ КВАДРАТОВ
Пример. Дана таблица данных.
Заполняем таблицу для удобства вычисления сумм, которые входят в формулы
искомых коэффициентов.
Значения в четвертой строке таблицы получены умножением значений 2-ой
строки на значения 3-ей строки для каждого номера i.
Значения в пятой строке таблицы получены возведением в квадрат значений 2ой строки для каждого номера i .
Значения последнего столбца таблицы – это суммы значений по строкам.

16.

МЕТОД НАИМЕНЬШИХ КВАДРАТОВ
Используем формулы метода наименьших квадратов для нахождения
коэффициентов а и b. Подставляем в них соответствующие значения из
последнего столбца таблицы
Следовательно, y = 0.165 * X + 2.184 - искомая аппроксимирующая прямая.

17.

Алгоритм Дейкстры
метод поиска кратчайшего пути
12
6
-
-
5
Старт
-
13
2
3
-
3
6
3
6
-
1
9
-
8
8
-
-
Финиш
14
2
7
4
2
4
-
-
-
10
-

18.

Алгоритм Дейкстры
метод поиска кратчайшего пути
12
6
-
-
5
Старт
-
13
2
3
-
3
6
3
6
-
1
9
-
8
8
-
-
Финиш
14
2
7
4
2
4
0*
-
-
10
-

19.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5*
6
-
5
Старт
-
13
2
3
-
3
6
3
6
-
1
9
-
8
8
2*
7*
Финиш
14
2
7
4
2
4
0
-
-
10
-

20.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
17*
5
Старт
-
13
3
-
6
3
6
3
-
-
1
9
2
Финиш
8
8
2*
7*
4
14
2
7
-
2
4
0
6
-
10
-

21.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
17
5
Старт
19*
13
2*
2
Финиш
3
-
6
-
3
6
3
-
8
8
1
9
7*
4
14
2
7
23*
2
4
0
6
-
10
-

22.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
17
5
Старт
19*
13
2*
2
Финиш
3
-
6
-
3
6
3
27
8
8
1
9
7*
4
14
2
7
23
2
4
0
6
-
10
-

23.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
17
5
Старт
19
13
2*
2
Финиш
27*
6
3
3
22*
20*
27
8
8
1
9
7*
4
14
2
7
23
2
4
0
6
10
6
3
-

24.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
17
5
Старт
19
13
2*
2
Финиш
27
6
3
3
22*
20*
27
8
8
1
9
7*
4
14
2
7
23
2
4
0
6
10
6
3
30*

25.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
17
5
Старт
15*
13
2
2
Финиш
27
6
3
3
11*
20*
27
8
8
1
9
7*
4
14
2
7
23
2
4
0
6
10
6
3
30*

26.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
17
5
Старт
15*
13
2
2
Финиш
27
6
3
3
9*
20*
27
8
8
1
9
7
4
14
2
7
23
2
4
0
6
10
6
3
30*

27.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
17
5
Старт
12*
13
2
2
Финиш
27
6
3
3
9
12*
27
8
8
1
9
7
4
14
2
7
23
2
4
0
6
10
6
3
30*

28.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14*
5
Старт
12
13
2
2
Финиш
20*
6
3
3
9
12*
26
8
8
1
9
7
4
14
2
7
23
2
4
0
6
10
6
3
30*

29.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20*
6
3
3
9
12*
26
8
8
1
9
7
4
14
2
7
20*
2
4
0
6
10
6
3
30*

30.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20*
6
3
3
9
12*
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
30*

31.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12*
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
23*

32.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
18*
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
22*

33.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
21*

34.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
22

35.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
22

36.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
22

37.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
22

38.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
22

39.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
22

40.

Алгоритм Дейсткры
метод поиска кратчайшего пути
12
5
14
5
Старт
12
13
2
2
Финиш
20
6
3
3
9
12
24
8
8
1
9
7
4
14
2
7
20
2
4
0
6
10
6
3
22
English     Русский Rules