Язык Python. Решение вычислительных задач на компьютере

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс, Python
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 класс, Python
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 класс, Python
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 класс, Python
16
Метод перебора (a = 0)
from math import cos
def f( x ):
return x - cos(x)
eps = 0.001
x = 0 # x = a
delta = 2*eps
Когда остановится?
while f(x)*f(x+delta) > 0:
x += delta
print('x = {:6.3f}'.format(x+eps))
?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
Зацикливание?
http://kpolyakov.spb.ru

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

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

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

Решение вычислительных задач, 10 класс, Python
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 класс, Python
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 класс, Python
20
Метод деления отрезка пополам
.
Python:
delta = 2*eps
while b - a > delta:
c = (a + b) / 2
if f(a)*f(c) <= 0:
b = c
else: a = c
print('x = {:6.3f}'.format (a+b)/2))
?
Как меняется длина отрезка?
?
За сколько шагов уменьшится в 1000 раз?
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

21. Полёт мяча

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

24. Полёт мяча

Решение вычислительных задач, 10 класс, Python
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 класс, Python
25
Полёт мяча
Программа на языке Python:
u =0
delta = 2*eps
while u < math.pi/2:
if f(u)*f(u+delta) <= 0:
alpha = (u+eps)*180/math.pi
print('Угол: {:4.1f}'.format(alpha),
' градусов')
u += delta
1 35,6
2 65,8
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

26. Полёт мяча

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

27. Полёт мяча

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

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс, Python
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 класс, Python
34
Вычисление длины кривой
Программа на Python:
x = a
L = 0
while x < b:
y1 = f(x)
y2 = f(x+h)
L += math.sqrt(h*h + (y2-y1)*(y2-y1))
x += h
print( 'Длина кривой {:10.3f}'.format(L) )
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

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

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

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

Решение вычислительных задач, 10 класс, Python
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 класс, Python
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
Python:
S, x = 0, a
while x < b:
S += f1(x+h/2)- f2(x+h/2)
x += h
S *= h
print( 'Площадь {:8.3f}'.format(S) )
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс, Python
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 класс, Python
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
?
Python:
Как улучшить?
S, x = 0, a
while x < b:
S += f1(x)- f2(x)+ f1(x+h)- f2(x+h)
x += h
S *= h/2
print( 'Площадь {:8.3f}'.format(S) )
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс, Python
43
Метод дихотомии
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

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

Решение вычислительных задач, 10 класс, Python
44
Метод дихотомии
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

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

Решение вычислительных задач, 10 класс, Python
45
Метод дихотомии
Алгоритмический язык:
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

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

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

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

Решение вычислительных задач, 10 класс, Python
47
Метод золотого сечения
Золотое сечение – большая часть относится к меньшей
как целое к большей части.
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

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

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

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

Решение вычислительных задач, 10 класс, Python
49
Золотое сечение: спирали
Ряд Фибоначчи:
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

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

Решение вычислительных задач, 10 класс, Python
50
Метод золотого сечения
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

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

Решение вычислительных задач, 10 класс, Python
51
Оптимальный раскрой листа
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

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

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

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

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

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс, Python
57
Что такое статистика?
Статистика – это наука, которая изучает методы
обработки и анализа больших массивов данных.
Ряд данных:
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

58. Дисперсия

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

59. Дисперсия

Решение вычислительных задач, 10 класс, Python
59
Дисперсия
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

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

Решение вычислительных задач, 10 класс, Python
60
Дисперсия и СКВО
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

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

Решение вычислительных задач, 10 класс, Python
61
Условные вычисления
Доставка:
• бесплатно при >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

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

Решение вычислительных задач, 10 класс, Python
62
Сложные условия
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

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

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

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

Решение вычислительных задач, 10 класс, Python
64
Вложенные условия
Доставка:
• бесплатно при >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

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

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

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

Решение вычислительных задач, 10 класс, Python
66
Коэффициент корреляции
средние рядов
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

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

Решение вычислительных задач, 10 класс, Python
67
Коэффициент корреляции
Как понимать это число?
• если 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

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

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

69. Закон Гука

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

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

Решение вычислительных задач, 10 класс, Python
70
Метод наименьших квадратов (МНК)
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

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

Решение вычислительных задач, 10 класс, Python
71
Метод наименьших квадратов (МНК)
(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

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

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

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

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

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

Решение вычислительных задач, 10 класс, Python
74
Восстановление зависимостей
Два ряда одинаковой длины:
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

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

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

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

Решение вычислительных задач, 10 класс, Python
76
Восстановление зависимостей
Корректная задача: найти функцию заданного вида,
которая лучше всего соответствует данным.
Примеры:
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

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

Решение вычислительных задач, 10 класс, Python
77
Что значит «лучше всего соответствует»?
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

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

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

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

Решение вычислительных задач, 10 класс, Python
79
Прогнозирование
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

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

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

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

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