- •1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
- •2. РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ «ИНФОРМАТИКА»
- •2.1 Тематический план дисциплины
- •2.2 Описание содержания основных тем
- •3.ОПОРНЫЙ КОНСПЕКТ ЛЕКЦИЙ
- •Шаговый метод
- •Метод половинного деления
- •Метод Ньютона
- •Метод простой итерации
- •3.3. Численные методы решения систем линейных уравнений
- •Метод Гаусса
- •Метод простой итерации
- •Метод Зейделя
- •3.4. Численные методы решения задачи аппроксимации
- •Постановка задачи
- •Интерполяция. Определение
- •Линейная интерполяция
- •Квадратичная интерполяция
- •Интерполяция с помощью полинома Лагранжа
- •Метод наименьших квадратов
- •Ручная реализация методов интерполяции и аппроксимации
- •4. ОПИСАНИЕ ЛАБОРАТОРНЫХ РАБОТ
- •4.2. Численные методы решения систем линейных уравнений. Реализация в пакете Excel
- •4.3. Интерполяция и аппроксимация функций
- •Линейная интерполяция.
- •Квадратичная интерполяция
- •Аппроксимация функций
- •5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ
- •6. ВАРИАНТЫ ДЛЯ КУРСОВОЙ РАБОТЫ
- •6.1 Нелинейное уравнение
- •6.2. Системы уравнений
- •6.3. Аппроксимация и интерполяция
- •7. КОНТРОЛЬ ЗНАНИЙ СТУДЕНТОВ
- •Контрольные вопросы по численным методам
- •8. ГЛОССАРИЙ
- •9. СПИСОК ЛИТЕРАТУРЫ
Эту систему можно решить, используя, например, метод Гаусса.
Интерполяция с помощью полинома Лагранжа
Метод неопределенных коэффициентов не является единственным методом, используемым при решении задачи интерполяции. Альтернативным методом является использование полинома Лагранжа. Общий вид полиномов Лагранжа первой и второй степени:
L1 (x)
L2 (x)
= |
|
x − x2 |
y + |
x − x1 |
y |
; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
x |
− x |
2 |
|
1 |
x |
2 |
− x |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
= |
|
(x − x2 )(x − x3 ) |
y1 + |
(x − x1 )(x − x3 ) |
|
y2 + |
(x − x1 )(x − x2 ) |
|
y3. |
|||||||||||||||||
|
(x |
|
− x |
)(x |
− x ) |
(x |
2 |
− x )(x |
2 |
− x |
) |
(x |
− x )(x |
− x |
) |
|||||||||||
|
1 |
|
|
2 |
1 |
|
|
3 |
|
|
|
|
1 |
3 |
|
|
3 |
1 |
3 |
2 |
|
|
Применение данного метода будет рассмотрено на конкретном примере позднее.
Метод наименьших квадратов
В большинстве экспериментальных данных, задаваемых с помощью табличной функции, имеется достаточно большой разброс точек. При этом использование кусочной или непрерывной интерполяции не всегда оправдано, поскольку ставится задача исследовать общую тенденцию изменения физической величины. В этом общем случае аппроксимации искомая кривая не обязательно должна проходить через заданные точки.
Рассмотрим рис. 10, отражающий большой разброс точек. В простейшем случае будем искать аппроксимирующую функцию ϕ(x) в виде полинома пер-
вой степени (прямой): ϕ(x) = a0 + a1x.
ϕ(x
Рис. 10. Аппроксимация
31
Таким образом, данная система точек группируется вокруг искомой прямой. Эту прямую легко провести на глаз так, чтобы она наиболее близко подходила к исходным точкам. Однако, можно найти уравнение прямой более строгими математическими методами.
Пусть общее количество точек равно m. Обозначим δi - отклонение i-й точки от искомой прямой:
δi = ϕ(xi ) – yi.
Как видно из рис. 11, отклонения могут быть как положительными, так и отрицательными. Поэтому, для того, чтобы определить близость искомой функции к табличным точкам, необходимо составить сумму квадратов всех отклонений.
Метод наименьших квадратов заключается в минимизации суммы квадратов отклонений. В нашем случае эта функция равна:
m |
m |
S = ∑δi2 = ∑[(a0 + a1xi )− yi ]2 . |
|
i=1 |
i=1 |
δi
Рис. 11. Отклонения
Для нахождения минимума функции S необходимо приравнять нулю ее частные производные. В результате получим систему уравнений:
∂S∂a0∂S∂a1
=0,
=0.
32
Опуская промежуточные преобразования, получим систему уравнений для нахождения неизвестных коэффициентов a0 и a1:
|
|
+ (∑xi ) a1 = ∑yi , |
|
|
|||
m a0 |
|
|
|||||
|
|
) a |
+ ( x2 ) a |
= |
x |
y |
. |
( x |
|||||||
|
∑ i |
0 |
∑ i 1 |
|
∑ i |
i |
|
Здесь m – количество точек; суммирование здесь и далее предполагается по всем точкам (i = 1,2,…,m).
Метод наименьших квадратов несложно распространить на общий слу-
чай, когда мы будем искать функцию ϕ(x) в виде полинома степени n:
ϕ(x) = a0 +a1 x +a2 x2 +...+an xn .
Отметим, что в случае аппроксимации всегда справедливо следующее соотношение, связывающее количество исходных точек m и степень искомого полинома:
n ≤ m – 1,
причем в случае равенства мы приходим к интерполяции (все отклонения равны нулю).
Неизвестные коэффициенты a0, a1, …, an находим из условия минимизации суммы квадратов отклонений искомой функции от исходных точек. По аналогии с полиномом первой степени в нашем случае имеем систему уравнений:
Z • A = B,
где Z - квадратная матрица размерностью (n+1)×(n+1), составленная из известных координат точек, A – вектор неизвестных коэффициентов, Y – век- тор-столбец свободных членов:
m
Z= ∑...xi∑xin
∑xi |
∑xi2 |
∑xi2 |
∑xi3 |
... ... |
|
∑xin+1 |
∑xin+2 |
...
...
...
...
∑xin
∑xin+1 ; A
...
∑xi2n
a0
=a1 ;Y...an
|
∑yi |
|
|
∑xi yi |
|
= |
... |
. |
|
|
|
|
∑xin yi |
33
Ручная реализация методов интерполяции и аппроксимации
Дана табличная функция (3 точки):
x |
-1 |
0 |
1 |
y |
3 |
1 |
5 |
|
|
|
|
Требуется:
•решить задачу интерполяции (кусочно-линейная и квадратичная интерполяция) методом неопределенных коэффициентов;
•решить задачу интерполяции (кусочно-линейная и квадратичная интерполяция) с помощью полинома Лагранжа;
•решить задачу аппроксимации (найти полиномы первой и второй степени методом наименьших квадратов).
Решение.
Вслучае интерполяции функция проходит строго через экспериментальные точки. Для кусочно-линейной интерполяции получим две системы из условия прохождения соответствующей прямой через точки 1 и 2, а также 2 и 3:
a |
|
+ a |
(−1) = 3 |
|
a |
|
=1 |
ϕ(x) =1 |
− 2x. |
А) |
0 |
1 |
|
|
0 |
|
|||
a0 + a1 0 =1 |
|
a1 = −2 |
|
|
a0 |
+ a1 0 =1 |
|
a0 =1 |
ϕ(x) =1 + 4x. |
|
B) a |
0 |
+ a 1 = 5 |
a = 4 |
||
|
1 |
|
1 |
|
Для квадратичной интерполяции с помощью метода неопределенных коэффициентов получим систему:
a0 + a1 (−1) + a2 (−1)2 = 3, |
|
a |
0 |
=1 |
||||
|
|
+ a1 0 + a2 02 =1, |
|
|
|
|||
a0 |
a1 =1 ϕ(x) =1 + x + 3x2 . |
|||||||
a |
0 |
+ a 1 + a |
2 |
12 = 5. |
|
a2 |
= 3 |
|
|
1 |
|
|
|
|
|
Графическая иллюстрация (рис 12):
34
Рис. 12. Ручная реализация интерполяции
Решим ту же задачу с использованием полинома Лагранжа.
Для кусочно-линейной интерполяции получим:
А) для точек 1 и 2: L1(x) = −x1−−00 3 + 0x ++111 =1 − 2x.
В) для точек 2 и 3: L1(x) = 0x ++111 + 0x −−115 =1+ 4x.
Для квадратичной интерполяции с помощью полинома Лагранжа полу-
чим:
L (x) = |
(x −0)(x −1) |
3 + |
(x +1)(x −1) |
1+ |
(x +1)(x −0) |
5 =1+ x +3x2 . |
|
|
|
|
|||||
2 |
(−1 |
−0)(−1−1) |
|
(0 +1)(0 −1) |
|
(1+1)(1−0) |
|
|
|
|
В случае аппроксимации функция не обязательно проходит строго через экспериментальные точки. Используем метод наименьших квадратов. Решаем систему Z• A = B.
А) Полином второй степени.
|
3 |
|
|
Z = |
∑xi |
|
∑xi2 |
∑xi
∑xi2
∑xi3
∑xi2 |
|
|
3 |
0 |
2 |
|
|
∑xi3 |
|
|
0 |
2 |
0 |
|
; |
|
= |
|
|||||
4 |
|
|
2 |
0 |
2 |
|
|
∑xi |
|
|
|
|
35
|
∑ |
y |
|
|
|
9 |
|
a |
|
|
|
|
i |
|
|
2 |
|
|
0 |
|
|
B = |
∑xi |
yi |
= |
; |
A = a1 |
. |
||||
|
2 |
|
|
|
|
8 |
|
|
|
|
|
∑xi |
yi |
|
|
a2 |
|
Имеем систему:
3a0 |
+2a |
|
2a1 |
|
|
|
+2a |
2a0 |
2 |
= 9 |
a0 =1 |
|
|
= 2 |
|
=1 ϕ(x) =1+ x +3x2 . |
|
a1 |
||
|
=8 |
|
=3 |
2 |
a2 |
Получили тот же результат, что и при использовании метода неопределенных коэффициентов. Это означает, что в данном случае отклонения равны нулю, а аппроксимация переходит в интерполяцию.
B) Полином первой степени.
3 |
∑xi |
|
3 |
0 |
|
∑yi |
|
|
9 |
a0 |
|
|
Z = |
2 |
|
= |
|
|
; B = |
= |
; |
A = |
. |
||
∑xi |
|
|
0 |
2 |
|
∑xi yi |
|
|
|
|
||
∑xi |
|
|
|
2 |
a1 |
|
||||||
|
|
3a0 = 9 |
|
a0 = 3 |
|
ϕ(x) = 3 + x. |
||||||
Имеем систему: |
2a |
= 2 |
a =1 |
|||||||||
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
Графическая иллюстрация (рис.14):
Рис. 14. Ручная реализация аппроксимации
36