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

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

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 м


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

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
English     Русский Rules