Вычислительная математика. Введение. Погрешности. Численное дифференцирование

1.

Вычислительная математика. Лекция № 1.
Предмет вычислительной
математики. Классификация
погрешностей. Численное
дифференцирование.
к.ф.-м.н. Уткин Павел Сергеевич
e-mail: [email protected], [email protected]
(926) 2766560
Данная лекция доступна по адресу:
http://mipt.ru/education/chair/computational_mathematics/study/materials/compmath/lectures/
6 сентября 2014 г., МФТИ, Долгопрудный

2.

Предмет
вычислительной
математики
Предмет вычислительной математики. Погрешности. Численное дифференцирование.
2

3.

Краткий экскурс в историю
1768 г. – Леонард Эйлер, метод ломаных
Леонард Эйлер (1707 – 1783)
Предмет вычислительной математики. Погрешности. Численное дифференцирование.
3

4.

Вычислительная математика в наше время
1950-ые
1970-ые
Первая Советская
атомная бомба
Женщины с арифмометрами,
работали пока не уставали…
1990-ые
Первые
многомерные
расчеты
БЭСМ-6, 1 MFlops
2014 год
Сложные трехмерные
расчетные сетки
Кластеры типа Beowolf, ~ 10 GFlops
Серийные
двумерные расчеты
Tianhe-2 (Китай),
с достаточной
более 3 000 000 вычислительных
разрешающей
ядер, ~ 55 PFlops
способностью
Трехмерное
моделирование
Предмет вычислительной математики. Погрешности. Численное дифференцирование.
4

5.

Специфика вычислительной математики
• Вычислительная математика имеет дело не
только с непрерывными, но и с дискретными
объектами → погрешность метода;
• Погрешность вычислений в связи с ошибками
округления;
• Имеет значение обусловленность задач, т.е.
чувствительность решения к малым изменениям
входных данных;
• Выбор вычислительного алгоритма, вообще
говоря, влияет на результат вычислений;
• Важная черта численного метода –
экономичность, т.е. требование минимизации
числа операций.
Предмет вычислительной математики. Погрешности. Численное дифференцирование.
5

6.

Классификация
погрешностей
Предмет вычислительной математики. Погрешности. Численное дифференцирование.
6

7.

Классификация погрешностей
Погрешность решения
задачи
Неустранимая
Устранимая
Неточность
задания числовых
данных
Погрешность
метода
Погрешность
математической
модели
Вычислительная
погрешность
Предмет вычислительной математики. Погрешности. Численное дифференцирование.
7

8.

Пример – колебания математического маятника
• Неустранимая погрешность – трение
зависит от скорости не совсем линейно +
погрешность определения g, l, начальных
условий; Δ1 = | φ1 – φ |.
• Погрешность метода – дифференциальное
уравнение не решается точно, требуется
применить какой-либо численный метод;
Δ2 = | φ2 – φ1 |.
• Вычислительная погрешность связана,
например, с конечностью разрядной
сетки; Δ3 = | φ3 – φ2 |.
ΔΣ = | φ3 – φ | = | φ3 – φ2 + φ2 – φ1 + φ1 – φ | ≤ Δ1 + Δ2 + Δ3
ΔΣ ≤ Δ1 + Δ2 + Δ3
Предмет вычислительной математики. Погрешности. Численное дифференцирование.
8

9.

Вычислительная погрешность
Машинное представление вещественных чисел:
xмаш = x·( 1 + ε(x) ), где мерой ε(x) может служить
«машинное эпсилон» ε – наименьшее положительное
число, для которого ( 1 + ε(x) )маш ≥ 1
Утверждение
1.1.
Относительная
погрешность
округ- ления при представлении вещественного числа
в ЭВМ ε ≈ 2–t, где t – разрядность мантиссы.
В расчетах с двойной точностью t = 52, εdouble ≈ 10–16
Предмет вычислительной математики. Погрешности. Численное дифференцирование.
9

10.

Иллюстрация понятия вычислительной погрешности (1)
Приближенное вычисление значения синуса с
помощью разложения в ряд Тейлора
Ряд сходится для любого значения x
(Тер-Крикоров А.М., Шабунин М.И. Курс математического
анализа. – М.: Физматлит, 2001. – С. 439.)
Напишем программу для вычисления
значения синуса при:
X1 = π / 6 ≈ 0.52366
X2 = 12π + π / 6 ≈ 38.22277
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 10

11.

Иллюстрация понятия вычислительной погрешности (2)
#define EPS 1.e-8
#define X
0.52366
...
int i, k = 0;
double curr_sum = 0.0, curr_sum_old = 0.0, fact;
do {
fact = 1.0;
for ( i = 1; i<= 2*k+1; i++ )
fact *= i;
curr_sum_old = curr_sum;
curr_sum += pow( -1, k) * pow( X, 2*k+1 ) / fact;
k++;
} while ( fabs( curr_sum - curr_sum_old ) > EPS );
Результат расчета значения синуса:
Для X1 = 0.52366: 0.500053…
Для X2 = 38.22277: 1.165079…
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 11

12.

Иллюстрация понятия вычислительной погрешности (3)
Причина – быстрый рост ошибок округления
| ak | ~ 1015
ε ~ 10–16
Δ| ak | ~ 0.1
Для | X | < 1: | ak |
монотонно убывают
Для | X | > 1: | ak |
сначала возрастают, а
затем убывают
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 12

13.

Численное
дифференцирование
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 13

14.

Численное дифференцирование – простейший пример
u’(x) ≈ ?
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 14

15.

Оценка погрешности метода
Погрешность метода рассматривается как мера
малости по степеням h. Говорят, что погрешность
метода O(h), а сам метод обладает первым порядком
аппроксимации.
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 15

16.

Полная погрешность
Пусть u(x) вычисляется с неустранимой
погрешностью δ
Погрешность метода прямо пропорциональна h,
неустранимая – обратно пропорциональна. Значит,
существует оптимальный шаг рассматриваемой формулы
численного дифференцирования.
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 16

17.

Определение оптимального шага
Рассматриваемая
формула точна для
линейной функции u(x),
погрешность метода 0
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 17

18.

Численное дифференцирование – другие примеры
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 18

19.

Постановка задачи численного дифференцирования
u(k)(xj) ≈ ?
Метод неопределенных коэффициентов:
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 19

20.

Формирование системы уравнений
Для простоты рассмотрим случай k = 1
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 20

21.

Система уравнений для нахождения коэффициентов
Число неизвестных равно
числу уравнений при условии:
n=l+m
Остаточный член имеет n-ый
порядок аппроксимации
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 21

22.

Разрешимость полученной системы уравнений
Определитель матрицы A – детерминант
Вандермонда. В случае различия всех узлов
шаблона det A ≠ 0, и, значит, существует единственное
решение системы – набор коэффициентов.
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 22

23.

Определитель Вандермонда
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 23

24.

Общее теоретическое утверждение
На шаблоне из N точек с помощью метода неопределенных
коэффициентов всегда можно построить единственную
формулу для вычисления производной k-го порядка (k от 1
до N – 1) с точностью по крайней мере O(hN–k).
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 24

25.

Замечание
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 25

26.

Пример использования метода неопределенных коэффициентов (1)
с максимальным порядком
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 26

27.

Пример использования метода неопределенных коэффициентов (2)
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 27

28.

Пример использования метода неопределенных коэффициентов (3)
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 28

29.

Примерный план лекций
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
Введение. Погрешности. Численное дифференцирование. (06.09)
Интерполяция. Полиномы Лагранжа и Ньютона. Интерполяция по
Чебышевским узлам. (13.09)
Обусловленность задачи интерполяции. Сплайн-интерполяция.
(20.09)
Численное интегрирование. (27.09)
Введение в методы решения СЛАУ. Нормы векторов и матриц.
Число обусловленности матрицы СЛАУ. (04.10)
Прямые методы решения СЛАУ. (11.10)
Итерационные методы решения СЛАУ. Полусеместровая
контрольная работа. (18.10)
Вариационные методы решения СЛАУ. (25.10)
Метод наименьших квадратов. (01.11)
Методы решения нелинейных уравнений и систем. (08.11)
Основные понятия теории разностных схем. (15.11)
Простейшие численные методы решения задач Коши для ОДУ.
Методы Рунге-Кутты. (22.11)
Численное решение краевых задач для ОДУ. (29.11)
Семестровая контрольная работа. (06.12)
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 29

30.

Рекомендованная литература
1. Петров И.Б., Лобанов А.И. Лекции по вычислительной
математике: учеб. пособие. – М.: Интернет-Университет
Информационных Технологий. Бином. Лаборатория знаний,
2006.
2. Косарев В.И. 12 лекций по вычислительной математике
(вводный курс): учеб. пособие. – 2-е изд., испр. и доп. – М.:
Изд-во МФТИ, 2000.
3. Самарский А.А., Гулин А.В. Численные методы. – М.: Наука,
1989.
4. Рябенький В.С. Введение в вычислительную математику: учеб.
пособие. – 2-е изд., испр. – М.: Физматлит, 2000.
5. Федоренко Р.П. Введение в вычислительную физику: учеб.
пособие. – М.: Изд-во МФТИ, 1994.
6. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные
методы. – М.: Бином. Лаборатория знаний, 2008.
7. Press W.H. et al. Numerical Recipes in C. – Cambridge University
Press, 1992.
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 30

31.

Заключение
Выводы из Лекции № 1
1. Рассмотрены основные особенности предмета вычислительной
математики.
2. Классифицированы погрешности и проанализированы основные
причины их возникновения в расчетах.
3. Сформулирована задача численного дифференцирования и
продемонстрирован способ построения формул численного
дифференцирования методом неопределенных коэффициентов.
Построены формулы для аппроксимации 1-ой и 2-ой производных на
симметричном 3-х точечном шаблоне с максимальным порядком.
При подготовке лекции использовались
1. Петров И.Б., Лобанов А.И. Лекции по вычислительной математике:
учеб. пособие. – М.: Интернет-Университет Информационных
Технологий. Бином. Лаборатория знаний, 2006. – С. 16 – 28.
2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.:
Бином. Лаборатория знаний, 2008. – С. 8 – 20.
3. Федоренко Р.П. Введение в вычислительную физику: учеб. пособие.
– М.: Изд-во МФТИ, 1994. – С. 24 – 25.
Предмет вычислительной математики. Погрешности. Численное дифференцирование. 31