Решение вычислительных задач на компьютере (язык С++)

1. Решение вычислительных задач на компьютере (язык С++)

1
Решение
вычислительных задач
на компьютере
(язык С++)
§ 69. Точность вычислений
§ 70. Решение уравнений
§ 71. Дискретизация
§ 72. Оптимизация
§ 73. Статистические расчёты
§ 74. Обработка результатов
эксперимента
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

2. Решение вычислительных задач на компьютере (язык С++)

2
Решение
вычислительных задач
на компьютере
(язык С++)
§ 69. Точность вычислений
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

3. Погрешности измерений

Решение вычислительных задач, 10 класс, C++
3
Погрешности измерений
«Недостатки математического образования с
наибольшей отчетливостью проявляются в
чрезмерной точности численных расчетов».
Карл Фридрих Гаусс.
Погрешность (ошибка) – отклонение измеренного или
вычисленного значения от истинного значения.
10
10
цена деления 0,1 см
9
9
8
8
7
7
6
6
5
5
4
3
2
1
4
3
2
1
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
измерено
8,2 см
7,8 см
Толщина дна:
вычислено
0,4 см
фактически
8,15 ... 8,25 см
7,75 ... 7,85 см
фактически
0,3 ... 0,5 см
0,4 0,1см
http://kpolyakov.spb.ru

4. Погрешности измерений

Решение вычислительных задач, 10 класс, C++
4
Погрешности измерений
абсолютная
погрешность x
0,4 0,1
0,1 см
?
Можно ли оценить
точность измерений?
Относительная погрешность:
x
x *
x*
измеренное
истинное
значение
0,1
x
0,25 25%
0,4
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

5. Погрешности вычислений

Решение вычислительных задач, 10 класс, C++
5
Погрешности вычислений
D 1,2 0,1 см
S
D2
Smin
S ?
1,1309733552923255658465516179806...
4
1,12
0,950...
4
S 1,1 0,2 см
Smax
1,32
4
1,327...
0,2
x
100% 18%
1,1
Все практические расчеты выполняются неточно.
Погрешность результата вычислений определяется
погрешностью исходных данных.
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

6. Погрешности вычислений

Решение вычислительных задач, 10 класс, C++
6
Погрешности вычислений
a 1000 0,001; b 0,002 0,001;
a c
x
c 1000 0,001; d 0,003 0,001.
b d
0,001
0,001
0,001
50% b
33%
a c
0,01% b
0,002
0,003
1000
1000 1000
неточные числа
x
166667
0,002 0,003
в знаменателе
1000 1000
xmax
750000
0,001 0,004
750000 166667
x
352%
1000 1000
166667
xmin
166667
0,003 0,002
Метод вычислительно неустойчив: малые погрешности
в исходных данных могут привести к большим
погрешностям в решении.
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

7. Источники погрешностей

Решение вычислительных задач, 10 класс, C++
7
Источники погрешностей
• неточность исходных данных
• неточность записи вещественных чисел в двоичном
коде конечной длины
• погрешности приближенного вычисления некоторых
стандартных функций (sin, cos, …)
• накопление погрешностей при арифметических
действиях с неточными данными
• погрешность метода
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

8. Решение вычислительных задач на компьютере (язык С++)

8
Решение
вычислительных задач
на компьютере
(язык С++)
§ 70. Решение уравнений
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

9. Методы решения уравнений

Решение вычислительных задач, 10 класс, C++
9
Методы решения уравнений
Точные (аналитические) методы:
ax b 1,
x cos x
a 0
?
1 b
x
a
Как решать?
Графический метод:
!
Можно поручить такой поиск компьютеру!
?
Можно ли получить точное решение?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

10. Приближённые методы

Решение вычислительных задач, 10 класс, C++
10
Приближённые методы
Сжатие отрезка:
1) выбрать начальный отрезок [a0, b0] (одно решение!)
2) уточнить решение с помощью некоторого
алгоритма: [a, b]
3) повторять шаг 2, пока длина отрезка [a, b] не станет
достаточно мала
a
?
x
a b
2
?
b
Как оценить ошибку?
Завершение работы:
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
Что лучше выбрать в
качестве решения?
b a
x x
2
b a 2
*
допустимая
ошибка
http://kpolyakov.spb.ru

11. Приближенные методы

Решение вычислительных задач, 10 класс, C++
11
Приближенные методы
По одной точке:
1) выбрать начальное приближение x0
2) уточнить решение с помощью некоторого алгоритма:
x
3) повторять шаг 2, пока два последовательных
приближения не будут отличаться достаточно мало
y
Завершение работы:
xi xi 1
касательная
метод Ньютона
(метод касательных)
x*
0
x2 x1
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
x0
x
http://kpolyakov.spb.ru

12. Приближенные методы

Решение вычислительных задач, 10 класс, C++
12
Приближенные методы
Итерационные методы (лат. iteratio – повторение) –
основаны на многократном выполнении одинаковых
шагов, каждый из которых уточняет решение.
xk 1 f ( xk )
следующее
приближение
предыдущее
приближение
дают какое-то решение, если точное неизвестно
могут давать меньшие ошибки, чем вычисления по
точным формулам
решение приближенное: x
= 1,23345
ответ – число (зависимость от параметра?)
большой объем вычислений
не всегда просто оценить погрешность
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

13. Метод перебора

Решение вычислительных задач, 10 класс, C++
13
Метод перебора
f ( x) 0
x cos x x cos x 0
Задача. Найти решение уравнения справа от точки x a
с точностью .
Алгоритм:
y
1) разбить отрезок [a, b] на
полосы шириной = 2
x*
2) найти полосу [a*, b*], в
которой находится x*
a
b x
3) решение:
a* b*
*
*
a b
x
2
*
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

14. Есть ли решение на [x, x+ ]?

Решение вычислительных задач, 10 класс, C++
14
Есть ли решение на [x, x+ ]?
нет решения
y
есть решение!
y
x*
0
x
x+
f ( x) 0
f (x ) 0
!
x
0
x*
x
нет решения
y
x+
x
x*
0
x
x
?
f ( x) 0
В чём отличие?
f (x ) 0
x+
f ( x) 0
f (x ) 0
Если непрерывная функция f (x) имеет разные знаки
на концах интервала [a, b], то в некоторой точке x*
внутри [a, b] она равна 0, то есть f (x* ) = 0!
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

15. Метод перебора (a = 0)

Решение вычислительных задач, 10 класс, C++
15
Метод перебора (a = 0)
алг Перебор
нач
вещ eps, x, delta
eps:= 0.001
x:= 0 | x:= a
Когда остановится?
delta:= 2*eps
нц пока f(x)*f(x+delta) > 0
x:= x + delta
Зацикливание?
кц
вывод 'x = ', x+eps
кон
?
?
алг вещ f( вещ x )
нач
знач:= x - cos(x)
кон
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

16. Метод перебора (a = 0)

Решение вычислительных задач, 10 класс, C++
16
Метод перебора (a = 0)
float f( x ) {
return x - cos(x);
}
int main() {
float eps = 0.001;
float x = 0; # x = a;
Когда остановится?
float delta = 2*eps;
while( f(x)*f(x+delta) > 0 )
x += delta;
cout << "x = " << fixed << setw(6)
<< setprecision(3) << x + eps;
}
?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
Зацикливание?
http://kpolyakov.spb.ru

17. Метод перебора

Решение вычислительных задач, 10 класс, C++
17
Метод перебора
простота
можно получить решение с любой заданной
точностью
большой объем вычислений
Усовершенствованный перебор:
1) отделение корней – перебор с большим шагом
2) уточнение корней – перебор с шагом 2
y
x*
0
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
x
http://kpolyakov.spb.ru

18. Метод деления отрезка пополам

Решение вычислительных задач, 10 класс, C++
18
Метод деления отрезка пополам
.
y
Алгоритм:
1) вычислить середину
x*
0
c
a
b x
отрезка: c
a b
2
2) если на отрезке [a,c] есть
решение, присвоить
b:=c, иначе a:=c
?
?
Что напоминает?
3) повторять шаги 1-2 до тех
пор, пока b a 2
п.2: как определить, есть ли решение?
Вариант:
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
1, x 0
sign x 0, x 0
1, x 0
http://kpolyakov.spb.ru

19. Метод деления отрезка пополам

Решение вычислительных задач, 10 класс, C++
19
Метод деления отрезка пополам
.
Алгоритмический язык:
delta:= 2*eps
нц пока b - a > delta
c:= (a + b) / 2
если f(a)*f(c) <= 0 то
b:= c
sign(f(a)) <> sign(f(c))
иначе
a:= c
все
кц
вывод 'x = ', (a+b)/2
?
Как меняется длина отрезка?
?
За сколько шагов уменьшится в 1000 раз?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

20. Метод деления отрезка пополам

Решение вычислительных задач, 10 класс, C++
20
Метод деления отрезка пополам
.
C++:
float delta = 2*eps;
while( b - a > delta ) {
float c = (a + b) / 2;
if( f(a)*f(c) <= 0 )
b = c;
else a = c;
}
cout << "x = " << fixed << setw(6)
<< setprecision(3) << (a+b)/2;
?
?
Как меняется длина отрезка?
За сколько шагов уменьшится в 1000 раз?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

21. Полёт мяча

Решение вычислительных задач, 10 класс, C++
21
Полёт мяча
y
v0
неизвестен
H
x
S
10 м
2м
4м
x v0 t cos ,
gt 2
y v0 t sin
2
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

22. Полёт мяча

Решение вычислительных задач, 10 класс, C++
22
Полёт мяча
Задача. Найти угол (и время t) при котором x = S и y = H:
gt 2
S v0 t cos , H v0 t sin
2
Решение:
S
t
v0 cos
v0 S sin
g S2
H
2
v0 cos
2v0 cos 2
g S2
f ( ) S tg 2
H 0
2
2v0 cos
Диапазон углов для поиска: [0 ...90 ] 0...
2
Как уточнить?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

23. Уточнение диапазона углов

Решение вычислительных задач, 10 класс, C++
23
Уточнение диапазона углов
min arctg
H
S
H
Диапазон углов для поиска: arctg ...
S 2
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

24. Полёт мяча

Решение вычислительных задач, 10 класс, C++
24
Полёт мяча
Программа на алгоритмическом языке:
pi:= 3.1415926
u:= 0
delta:= 2*eps
нц пока u < pi/2
если f(u)*f(u+delta) <= 0 то
вывод 'Угол: ', (u+eps)*180/pi
вывод ' градусов', нс
все
u:= u + delta
кц
1 35,6
2 65,8
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

25. Полёт мяча

Решение вычислительных задач, 10 класс, C++
25
Полёт мяча
Программа на языке C++:
float u = 0;
float delta = 2*eps;
while( u < M_PI/2 ) {
if( f(u)*f(u+delta) <= 0 ) {
float alpha = (u+eps)*180/M_PI;
cout << "Угол: " << fixed << setw(4)
<< setprecision(1)
<< alpha << " градусов";
}
u += delta;
}
1 35,6
2 65,8
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

26. Полёт мяча

Решение вычислительных задач, 10 класс, C++
26
Полёт мяча
Использование табличного процессора:
имя ячейки
или диапазона
Диапазон углов:
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

27. Полёт мяча

Решение вычислительных задач, 10 класс, C++
27
Полёт мяча
S $B$1
Excel: РАДИАНЫ
Диаграмма XY:
Excel: Точечная
1 35
2 65
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
3
2
1
0
-1
10
20
30
40
50
60
-2
-3
-4
-5
-6
http://kpolyakov.spb.ru

28. Полёт мяча

Решение вычислительных задач, 10 класс, C++
28
Полёт мяча
с графика!
начальное приближение
Сервис – Подбор параметра:
целевая
ячейка
нужно
f( ) = 0
?
Как найти второе
решение?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
изменяем
начальное
приближение
результат
в H2!
http://kpolyakov.spb.ru

29. Решение вычислительных задач на компьютере (язык С++)

29
Решение
вычислительных задач
на компьютере
(язык С++)
§ 71. Дискретизация
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

30. Вычисление длины линии

Решение вычислительных задач, 10 класс, C++
30
Вычисление длины линии
Ломаная:
y
y3
y2
y1
0
x1
x2
x3 x
L ( x2 x1 )2 ( y2 y1 )2 ( x3 x2 )2 ( y3 y2 )2
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

31. Вычисление длины линии

Решение вычислительных задач, 10 класс, C++
31
Вычисление длины линии
Кривая:
L' L
L
y
L'
0
a
b
x
h
шаг дискретизации
!
?
Выполнена дискретизация!
Как увеличить точность?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
h
http://kpolyakov.spb.ru

32. Дискретизация

Решение вычислительных задач, 10 класс, C++
32
Дискретизация
• цель – представить задачу в виде, пригодном для
компьютерных расчётов
• есть потеря информации
• методы приближённые
• для уменьшения погрешности нужно уменьшать шаг
дискретизации
Что ухудшится?
?
• при малом шаге на результат могут сильно влиять
погрешности вычислений
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

33. Вычисление длины кривой

Решение вычислительных задач, 10 класс, C++
33
Вычисление длины кривой
Программа на алгоритмическом языке:
x:= a
L:= 0
нц пока x < b
y1:= f(x)
y2:= f(x+h)
L:= L + sqrt(h*h + (y1-y2)*(y1-y2))
x:= x + h
кц
вывод 'Длина кривой ', L
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

34. Вычисление длины кривой

Решение вычислительных задач, 10 класс, C++
34
Вычисление длины кривой
Программа на C++:
float x = a;
float L = 0;
while( x < b ) {
float y1 = f(x);
float y2 = f(x+h);
L += sqrt(h*h + (y2-y1)*(y2-y1));
x += h;
}
cout << "Длина кривой " << fixed
<< setw(10) << setprecision(3) << L;
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

35. Площадь фигуры

Решение вычислительных задач, 10 класс, C++
35
Площадь фигуры
y
f1 ( x)
f 2 ( x)
a
!
b
x
Аналитически решается не всегда!
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

36. Дискретизация

Решение вычислительных задач, 10 класс, C++
36
Дискретизация
Метод прямоугольников:
y
f1 ( x)
f1 ( x)
S2
S1
S3
S4
f 2 ( x)
0
f 2 ( x)
a
h
S S1 S 2 S 3 S 4
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
b
x
x
x h
S x h f 1 ( x) f 2 ( x)
?
Как улучшить?
http://kpolyakov.spb.ru

37. Метод прямоугольников

Решение вычислительных задач, 10 класс, C++
37
Метод прямоугольников
Алгоритмический язык:
S:= 0; x:= a
нц пока x < b
S:= S + f1(x+h/2) - f2(x+h/2)
x:= x + h
кц
в середине
S:= h*S
отрезка [x, x+h]
вывод 'Площадь ', S
C++:
float S = 0, x = a;
while( x < b ) {
S += f1(x+h/2)- f2(x+h/2);
x += h;
}
S *= h;
cout << "Площадь " << fixed
<< setw(8) << setprecision(3) << S;
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

38. Метод трапеций

Решение вычислительных задач, 10 класс, C++
38
Метод трапеций
y
f1 ( x h)
f1 ( x)
f1 ( x)
f 2 ( x)
f 2 ( x)
0
a
h
b
x
x
f 2 ( x h)
x h
h
S x f 1 ( x ) f 2 ( x ) f 1 ( x h) f 2 ( x h)
2
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

39. Метод трапеций

Решение вычислительных задач, 10 класс, C++
39
Метод трапеций
Алгоритмический язык:
S:= 0; x:= a
нц пока x < b
S:= S + f1(x)- f2(x)+
f1(x+h)- f2(x+h)
x:= x + h
кц
S:= h*S/2
Как улучшить?
?
вывод 'Площадь ', S
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

40. Метод трапеций

Решение вычислительных задач, 10 класс, C++
40
Метод трапеций
Язык C++:
float S = 0, x = a;
while( x < b ) {
f2(x) +
S += f1(x)- f2(x)+
f1(x+h)- f2(x+h);
Как улучшить?
x += h;
}
S *=
*= h/2;
h/2;
S
cout << "Площадь " << fixed
<< setw(8) << setprecision(3) << S;
?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

41. Решение вычислительных задач на компьютере (язык С++)

41
Решение
вычислительных задач
на компьютере
(язык С++)
§ 72. Оптимизация
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

42. Что такое оптимизация?

Решение вычислительных задач, 10 класс, C++
42
Что такое оптимизация?
Оптимизация – это поиск наилучшего (оптимального)
решения задачи в заданных условиях.
1) Цель: выбрать неизвестный x, так чтобы
f ( x) min
или
целевая функция
f ( x) max
f ( x) min
2) Ограничения
задача
оптимизации
?
Почему неправильно «самый оптимальный»?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

43. Что такое минимум?

Решение вычислительных задач, 10 класс, C++
43
Что такое минимум?
f (x)
локальный
минимум
глобальный
минимум
x
• обычно нужно найти глобальный минимум
• большинство численных методов находят только
локальный минимум
!
Результат локальной оптимизации зависит от
начального приближения!
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

44. Метод дихотомии

Решение вычислительных задач, 10 класс, C++
44
Метод дихотомии
y
y f (x)
f ( x1 )
f ( x2 )
0 a
x2 x*
c
x1
r
b
x
r
Алгоритм:
a b
c
1) вычислить середину отрезка:
2
2) найти симметричные точки x1= c - r, x2 = c + r
3) если f(x1) > f(x2), далее ищем на [x1, b]
иначе ищем на [a, x2]
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

45. Метод дихотомии

Решение вычислительных задач, 10 класс, C++
45
Метод дихотомии
a b
c
x1 c r , x 2 c r
2
?
Как выбрать r?
b a
0 r
r k (b a), 0 k 0,5
2
Уменьшение интервала:
стало
было
b a
k (b a) (0,5 k ) (b a)
2
!
Выгоднее выбирать k близко к нулю!
?
Почему нельзя k = 0?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

46. Метод дихотомии

Решение вычислительных задач, 10 класс, C++
46
Метод дихотомии
Алгоритмический язык:
k:= 0.01
delta:= 2*eps
нц пока b - a > delta
r:= k*(b - a)
x1:=(a + b)/2 - r
? Как улучшить?
x2:=(a + b)/2 + r
если f(x1) > f(x2) то
a:= x1
иначе b:= x2
все
кц
вывод 'x = ', (a+b)/2
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

47. Метод дихотомии

Решение вычислительных задач, 10 класс, C++
47
Метод дихотомии
С++:
float k = 0.01;
float delta = 2*eps;
while( b - a > delta ) {
float r = k*(b - a);
float x1 = (a + b)/2 – r;
float x2 = (a + b)/2 + r;
if( f(x1) > f(x2) )
a = x1;
? Как улучшить?
else b = x2;
}
cout << "x = " << fixed << setw(10)
<< setprecision(3) << (a+b)/2;
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

48. Метод золотого сечения

Решение вычислительных задач, 10 класс, C++
48
Метод золотого сечения
Золотое сечение – большая часть относится к меньшей
как целое к большей части.
L
b
a
a L
L a
Отношение золотого сечения:
b a
2
a Lb L( L a)
a 2 a( a a) a 2 ( 2 )
1
2
2 1 0
1 5
1 5
1
1,618... , 2
0,618...
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

49. Золотое сечение

Решение вычислительных задач, 10 класс, C++
49
Золотое сечение
Отношение золотого сечения:
b
a
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
a a b
1,618...
b
a
Античный циркуль
http://kpolyakov.spb.ru

50. Золотое сечение: спирали

Решение вычислительных задач, 10 класс, C++
50
Золотое сечение: спирали
Ряд Фибоначчи:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …, Fn-1, Fn , …
Fn
1,618...
при больших n:
Fn 1
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

51. Метод золотого сечения

Решение вычислительных задач, 10 класс, C++
51
Метод золотого сечения
L
L
a
L
2
'
1
x
x2
x1
x2'
L
2
L
b
x1 b
Уменьшение интервала:
(b a)
!
b a
x2 a
b a
b a
На каждом шаге вычисляется одна точка!
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

52. Оптимальный раскрой листа

Решение вычислительных задач, 10 класс, C++
52
Оптимальный раскрой листа
1м
z
x
x
z
Цель:
V ( x) max
?
Ограничения:
?
V ( x) x (1 2 x) 2 max
Какие ограничения?
0 x 0,5
Какой результат ожидаете (по интуиции)?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

53. Оптимальный раскрой листа

Решение вычислительных задач, 10 класс, C++
53
Оптимальный раскрой листа
В табличном процессоре:
V
0
0,1
0,2
начальное
приближение 0,2
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
0,3
0,4
?
0,5
x
Какая формула в F2?
http://kpolyakov.spb.ru

54. Оптимизация в табличном процессоре

Решение вычислительных задач, 10 класс, C++
54
Оптимизация в табличном процессоре
Задача оптимизации: найти максимум (или минимум)
целевой функции в ячейке …, изменяя значения ячеек
… при ограничениях ….
OpenOffice.org Calc:
модуль Solver for Nonlinear Programming
(входит в LibreOffice)
Excel:
надстройка Поиск решения
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

55. Оптимизация в табличном процессоре

Решение вычислительных задач, 10 класс, C++
55
Оптимизация в табличном процессоре
OpenOffice.org Calc:
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

56. Оптимизация в табличном процессоре

Решение вычислительных задач, 10 класс, C++
56
Оптимизация в табличном процессоре
Excel:
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

57. Решение вычислительных задач на компьютере (язык С++)

57
Решение
вычислительных задач
на компьютере
(язык С++)
§ 73. Статистические
расчёты
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

58. Что такое статистика?

Решение вычислительных задач, 10 класс, C++
58
Что такое статистика?
Статистика – это наука, которая изучает методы
обработки и анализа больших массивов данных.
Ряд данных:
x1 , x2 , ... xn
Свойства ряда данных:
сумма:
среднее:
минимальное:
максимальное:
количество чисел:
=SUM(A1:A20)
=AVERAGE(A1:A20)
=MIN(A1:A20)
=MAX(A1:A20)
=COUNT(A1:A20)
сколько ячеек удовлетворяет условию:
=COUNTIF(A1:A20;"=5")
=COUNTIF(A1:A20;">3")
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
только числа!
=СУММ(A1:A20)
=СРЗНАЧ(A1:A20)
=МИН(A1:A20)
=МАКС(A1:20)
=СЧЁТ(A1:20)
СЧЁТЕСЛИ
http://kpolyakov.spb.ru

59. Дисперсия

Решение вычислительных задач, 10 класс, C++
59
Дисперсия
Для этих рядов одинаковы МИН, МАКС, СРЗНАЧ
?
В чем различие?
Дисперсия («разброс») характеризует разброс
данных относительно среднего значения.
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

60. Дисперсия

Решение вычислительных задач, 10 класс, C++
60
Дисперсия
n
2
(
x
x
)
i
( x1 x ) 2 ( x2 x ) 2 ( x n x ) 2
Dx
i 1
n
n
x1 x2 xn
x
среднее арифметическое
n
( x1 x )
2
квадрат
отклонения x1
от среднего
D x средний квадрат
отклонения от
среднего значения
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

61. Дисперсия и СКВО

Решение вычислительных задач, 10 класс, C++
61
Дисперсия и СКВО
n
Dx
2
(
x
x
)
i
?
i 1
В каких единицах измеряется?
n
Что неудобно:
если x измеряется в метрах, то D x – в м2
СКВО = среднеквадратическое отклонение
x Dx
=STDEVP(A1:A20)
=СТАНДОТКЛОНП(A1:A20)
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

62. Условные вычисления

Решение вычислительных задач, 10 класс, C++
62
Условные вычисления
Доставка:
• бесплатно при >500 руб.
• 20% для остальных
условие
если B2 > 500 то
C2:= 0
иначе
C2:= B2*0.2
все
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
= IF(B2>500;0;B2*0,2)
=ЕСЛИ(B2>500;0;B2*0,2)
если «да»
если «нет»
http://kpolyakov.spb.ru

63. Сложные условия

Решение вычислительных задач, 10 класс, C++
63
Сложные условия
NOT (НЕ, отрицание)
AND (И, логическое умножение)
OR (ИЛИ, логическое сложение)
=IF( AND(A2<1500;B2>500) ;0;B2*0,2)
=IF(AND(B2>1994;C2>175); "да"; "–")
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

64. Сложные условия

Решение вычислительных задач, 10 класс, C++
64
Сложные условия
=IF(OR(B2=100;C2=100;B2+C2>=180); "да"; "–")
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

65. Вложенные условия

Решение вычислительных задач, 10 класс, C++
65
Вложенные условия
Доставка:
• бесплатно при >500 руб.
• 10% при >200 руб.
• 20% для остальных
если B2 > 500 то
C2:= 0
иначе
если B2 > 200 то
C2:= B2*0.1
иначе
C2:= B2*0.2
все
все
=IF(B2>500;0; IF(B2>200;B2*0,1;B2*0,2) )
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

66. Связь двух рядов данных

Решение вычислительных задач, 10 класс, C++
66
Связь двух рядов данных
Два ряда одинаковой длины:
x1 , x2 , ..., xn
y1 , y2 , ..., yn
Вопросы:
• есть ли связь между этими рядами (соответствуют
ли пары ( xi , yi ) какой-нибудь зависимости y f (x) )
• насколько сильна эта связь?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

67. Коэффициент корреляции

Решение вычислительных задач, 10 класс, C++
67
Коэффициент корреляции
средние рядов
n
1
( xi x )( yi y )
n i 1
xy
x y
СКВО рядов
?
?
В каких единицах
измеряется?
безразмерный!
Если x и y – один и
тот же ряд?
1 xy 1
=CORREL(A1:A20;B1:B20)
=КОРРЕЛ(A1:A20;B1:B20)
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

68. Коэффициент корреляции

Решение вычислительных задач, 10 класс, C++
68
Коэффициент корреляции
Как понимать это число?
• если xy 0 : увеличение x приводит к увеличению y
• если xy 0 : увеличение x приводит к уменьшению y
• если xy 0 : связь обнаружить не удалось
Сильная связь: xy 0,5
xy 1 : линейная зависимость y kx b,
k 0
xy 1 : линейная зависимость y kx b, k 0
?
Если xy 0, то связи нет?
!
Метод для определения линейной зависимости!
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

69. Решение вычислительных задач на компьютере (язык С++)

69
Решение
вычислительных задач
на компьютере
(язык С++)
§ 74. Обработка результатов
эксперимента
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

70. Закон Гука

Решение вычислительных задач, 10 класс, C++
70
Закон Гука
F k
F
k
F
Fi
, (i 1,...n)
Несколько опытов: ki
i
?
Что принять за k?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

71. Метод наименьших квадратов (МНК)

Решение вычислительных задач, 10 класс, C++
71
Метод наименьших квадратов (МНК)
y k x
Y3
y2
y
y1
Y1
0
Y2
x1 x2
неизвестно!
y3
Yi k xi
x3 x
Ошибка определяется величиной:
n
2
2
2
E (k ) (Y1 y1 ) (Y2 y2 ) (Yn yn ) (Yi yi ) 2
i 1
Метод наименьших квадратов: E (k ) min
!
Это задача оптимизации!
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

72. Метод наименьших квадратов (МНК)

Решение вычислительных задач, 10 класс, C++
72
Метод наименьших квадратов (МНК)
(Yi yi ) 2 (k xi yi ) 2 k 2 xi2 2kxi yi yi2
E (k ) A k B k C
2
n
n
A xi2
B 2 xi yi
i 1
i 1
n
C yi2
i 1
E
k*
k*
B
2A
k
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

73. Метод наименьших квадратов (МНК)

Решение вычислительных задач, 10 класс, C++
73
Метод наименьших квадратов (МНК)
Алгоритмический язык:
A:= 0; B:= 0
нц для i от 1 до N
A:= A + x[i]*x[i]
B:= B + x[i]*y[i]
кц
k:= B / A
вещ A, B, k
вещ x[1:N], y[1..N]
C++:
float A = 0, B = 0;
for(int i=0; i<N; i++) {
A += x[i]*x[i];
B += x[i]*y[i];
}
k = B / A;
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
N
k*
x y
i 1
N
i
i
2
x
i
i 1
http://kpolyakov.spb.ru

74. Метод наименьших квадратов (МНК)

Решение вычислительных задач, 10 класс, C++
74
Метод наименьших квадратов (МНК)
Табличный процессор:
начальное
приближение
СУММКВРАЗН
Поиск решения: выбрать B1 так, что B2 min
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

75. Восстановление зависимостей

Решение вычислительных задач, 10 класс, C++
75
Восстановление зависимостей
Два ряда одинаковой длины:
y1 , y2 , ..., yn
x1 , x2 , ..., xn
задают некоторую неизвестную функцию y f (x)
Зачем:
• найти y в промежуточных
точках (интерполяция)
y f (x)
y2
y1
x1 x2
xn
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
• найти y вне диапазона
измерений
(экстраполяция,
прогнозирование)
http://kpolyakov.spb.ru

76. Восстановление зависимостей

Решение вычислительных задач, 10 класс, C++
76
Восстановление зависимостей
y f 2 ( x)
y f1 ( x)
y2
y1
x1 x2
!
xn
Через заданный набор точек проходит
бесконечно много разных кривых!
Вывод: задача некорректна, поскольку решение
неединственно.
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

77. Восстановление зависимостей

Решение вычислительных задач, 10 класс, C++
77
Восстановление зависимостей
Корректная задача: найти функцию заданного вида,
которая лучше всего соответствует данным.
Примеры:
y f (x)
• линейная y a x b
y2
• полиномиальная
y1
y a3 x 3 a2 x 2 a1 x a0
• степенная y a x
• экспоненциальная
b
x1 x2
!
xn
График функции не
обязательно проходит
через заданные точки!
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
y a ebx
• логарифмическая
y a ln x b
?
Как выбрать
функцию?
http://kpolyakov.spb.ru

78. Что значит «лучше всего соответствует»?

Решение вычислительных задач, 10 класс, C++
78
Что значит «лучше всего соответствует»?
n
R2 1
(y Y )
i 1
n
i
i
( y y)
i 1
2
2
i
( xi , yi ) заданные пары
значений
Yi f ( xi )
y – среднее значение yi
коэффициент
детерминации
Крайние случаи:
2
• если график проходит через точки: R 1
2
• если считаем, что y не меняется и Yi y : R 0
R 2 max когда
!
n
2
(
y
Y
)
i i min
i 1
Фактически – метод наименьших квадратов!
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

79. Восстановление зависимостей

Решение вычислительных задач, 10 класс, C++
79
Восстановление зависимостей
Табличный процессор:
1) Диаграмма XY (Excel: Точечная)
2) ПКМ – Вставить линию тренда
тип функции
показать уравнение
коэффициент
детерминации
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

80. Прогнозирование

Решение вычислительных задач, 10 класс, C++
80
Прогнозирование
12
y = -0,0833x4 + 0,8333x3 - 2,4167x2 + 3,6667x - 2E-11
R² = 1
10
8
6
4
хорошо соответствует
данным, непригодна
для прогноза!
2
0
-2
0
2
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
4
6
http://kpolyakov.spb.ru

81. Конец фильма

Решение вычислительных задач, 10 класс, C++
81
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

82. Источники иллюстраций

Решение вычислительных задач, 10 класс, C++
82
Источники иллюстраций
1.
2.
3.
4.
5.
6.
vispo.ru
www.ars-sport.ru
dostoyanieplaneti.ru
www.remstroydecor.ru
иллюстрации художников издательства «Бином»
авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru