Решение вычислительных задач на компьютере (язык Python)
Решение вычислительных задач на компьютере (язык Python)
Погрешности измерений
Погрешности измерений
Погрешности вычислений
Погрешности вычислений
Источники погрешностей
Решение вычислительных задач на компьютере (язык Python)
Методы решения уравнений
Приближённые методы
Приближенные методы
Приближенные методы
Метод перебора
Есть ли решение на [x, x+ ]?
Метод перебора (a = 0)
Метод перебора (a = 0)
Метод перебора
Метод деления отрезка пополам
Метод деления отрезка пополам
Метод деления отрезка пополам
Полёт мяча
Полёт мяча
Уточнение диапазона углов
Полёт мяча
Полёт мяча
Полёт мяча
Полёт мяча
Полёт мяча
Решение вычислительных задач на компьютере (язык Python)
Вычисление длины линии
Вычисление длины линии
Дискретизация
Вычисление длины кривой
Вычисление длины кривой
Площадь фигуры
Дискретизация
Метод прямоугольников
Метод трапеций
Метод трапеций
Решение вычислительных задач на компьютере (язык Python)
Что такое оптимизация?
Что такое минимум?
Метод дихотомии
Метод дихотомии
Метод дихотомии
Метод дихотомии
Метод золотого сечения
Золотое сечение
Золотое сечение: спирали
Метод золотого сечения
Оптимальный раскрой листа
Оптимальный раскрой листа
Оптимизация в табличном процессоре
Оптимизация в табличном процессоре
Оптимизация в табличном процессоре
Решение вычислительных задач на компьютере (язык Python)
Что такое статистика?
Дисперсия
Дисперсия
Дисперсия и СКВО
Условные вычисления
Сложные условия
Сложные условия
Вложенные условия
Связь двух рядов данных
Коэффициент корреляции
Коэффициент корреляции
Решение вычислительных задач на компьютере (язык Python)
Закон Гука
Метод наименьших квадратов (МНК)
Метод наименьших квадратов (МНК)
Метод наименьших квадратов (МНК)
Метод наименьших квадратов (МНК)
Восстановление зависимостей
Восстановление зависимостей
Восстановление зависимостей
Что значит «лучше всего соответствует»?
Восстановление зависимостей
Прогнозирование
Конец фильма
Источники иллюстраций
3.47M
Categories: programmingprogramming informaticsinformatics

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

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
S ?
1,1309733552923255658465516179806...
4
1,12
S min
0,950...
4
S 1,1 0,2 см
Smax
x
1,32
4
1,327...
0,2
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
x*
0
x
нет решения
y
x+
x
x*
0
x
x+
x
?
f ( x) 0
В чём отличие?
f (x ) 0
f ( x) 0
f (x ) 0
f ( x) 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
a
b x
c
отрезка: c
a b
2
2) если на отрезке [a,c] есть
решение, присвоить
b:=c, иначе a:=c
? Что напоминает?
? п.2: как определить, есть ли решение?
3) повторять шаги 1-2 до тех
пор, пока b a 2
f ( a ) f (c ) 0
Вариант:
sign[ f (a)] sign[ f (c)]
К.Ю. Поляков, Е.А. Ерёмин, 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 м


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)
S1
S2
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
Оптимальный раскрой листа

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)
=СУММ(A1:A20)
среднее: =AVERAGE(A1:A20) =СРЗНАЧ(A1:A20)
минимальное: =MIN(A1:A20)
=МИН(A1:A20)
=МАКС(A1:20)
максимальное: =MAX(A1:A20)
количество чисел: =COUNT(A1:A20)
=СЧЁТ(A1:20)
сколько ячеек удовлетворяет условию:
=COUNTIF(A1:A20;"=5")
=COUNTIF(A1:A20;">3")
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
СЧЁТЕСЛИ
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 ( x 2 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
? Если 0, то связи нет?
xy
! Метод для определения линейной зависимости!
К.Ю. Поляков, Е.А. Ерёмин, 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 ) (k xi yi ) k x 2kxi yi y
2
2
2
2
i
2
i
E (k ) A k 2 B k C
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
вещ A, B, k
вещ x[1:N], y[1..N]
N
k i 1N
*
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
x y
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
Восстановление зависимостей
Два ряда одинаковой длины:
x1 , x2 , ..., xn
y1 , y2 , ..., yn
задают некоторую неизвестную функцию 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
(y Y )
R 2 1 i n1
i
2
i
2
(
y
y
)
i
i 1
( xi , yi ) заданные пары
значений
Yi f ( xi )
y – среднее значение yi
коэффициент
детерминации
Крайние случаи:
2
• если график проходит через точки: R 1
2
R
0
• если считаем, что y не меняется и Yi y :
n
R 2 max когда ( yi Yi ) 2 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
English     Русский Rules