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

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

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

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

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс
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
Все практические расчеты выполняются неточно.
Погрешность результата вычислений определяется
погрешностью исходных данных.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
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
Метод вычислительно неустойчив: малые погрешности
в исходных данных могут привести к большим
погрешностям в решении.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

7. Погрешность вычислений с помощью функций MS Excel

Решение вычислительных задач, 10 класс
С использованием встроенных функций Excel расчет доверительного
интервала проводится следующим образом.
1) Рассчитывается среднее значение
=СРЗНАЧ(число1; число2; ...)
число1, число2, ... — аргументы, для которых вычисляется среднее.
2) Рассчитывается стандартное отклонение
=СТАНДОТКЛОНП(число1; число2; ...)
число1, число2, ... — аргументы, для которых вычисляется стандартное
отклонение.
3) Рассчитывается абсолютная погрешность
=ДОВЕРИТ(альфа ;станд_откл;размер)
альфа — уровень значимости используемый для вычисления уровня
надежности.
( , т.е. означает надежности , для расчета возьмите равным 0,5 );
станд_откл — стандартное отклонение, предполагается известным;
размер — размер выборки.
Относительная погрешность – это отношение
абсолютной погрешности к приближенному значению числа
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
7

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс
14
Метод перебора
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
*
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

Решение вычислительных задач, 10 класс
16
Метод перебора (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)
кон
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
17
Метод перебора (a = 0)
const eps = 0.001;
var x, delta: real;
function f(x: real):real;
begin
f:= x - cos(x)
end;
begin
x:= 0; {x:= a;}
Когда остановится?
delta:= 2*eps;
while f(x)*f(x+delta) > 0 do
x:= x + delta;
Зацикливание?
writeln('x = ',(x+eps):6:3)
end.
?
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

Решение вычислительных задач, 10 класс
19
Метод деления отрезка пополам
.
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: как определить, есть ли решение?
f ( a ) f (c ) 0
Вариант:
sign[ f (a)] sign[ f (c)]
К.Ю. Поляков, Е.А. Ерёмин, 2013
1, x 0
sign x 0, x 0
1, x 0
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
20
Метод деления отрезка пополам
.
Алгоритмический язык:
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 раз?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
21
Метод деления отрезка пополам
.
Паскаль:
delta:= 2*eps;
while b - a > delta do begin
c:= (a + b) / 2;
if f(a)*f(c) <= 0 then
b:= c
else a:= c;
end;
writeln('x = ', (a+b)/2:6:3);
?
Как меняется длина отрезка?
?
За сколько шагов уменьшится в 1000 раз?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

22. Полёт мяча

Решение вычислительных задач, 10 класс
22
Полёт мяча
y
v0
неизвестен
H
x
S
10 м


x v0 t cos ,
gt 2
y v0 t sin
2
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

23. Полёт мяча

Решение вычислительных задач, 10 класс
23
Полёт мяча
Задача. Найти угол (и время 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
Как уточнить?
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

25. Полёт мяча

Решение вычислительных задач, 10 класс
25
Полёт мяча
Программа на алгоритмическом языке:
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
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

26. Полёт мяча

Решение вычислительных задач, 10 класс
26
Полёт мяча
Программа на языке Паскаль:
u:= 0;
delta:= 2*eps;
while u < pi/2 do begin
if f(u)*f(u+delta) <= 0 then begin
alpha:= (u+eps)*180/pi;
writeln('Угол: ', alpha:4:1, ' градусов');
end;
u:= u + delta
end;
1 35,6
2 65,8
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

27. Полёт мяча

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

28. Полёт мяча

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

29. Полёт мяча

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

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

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

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс
34
Вычисление длины кривой
Программа на алгоритмическом языке:
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
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
35
Вычисление длины кривой
Программа на Паскале:
x:= a;
L:= 0;
while x < b do begin
y1:= f(x);
y2:= f(x+h);
L:= L + sqrt(h*h + (y2-y1)*(y2-y1));
x:= x + h
end;
writeln('Длина кривой ', L:10:3);
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

Решение вычислительных задач, 10 класс
37
Дискретизация
Метод прямоугольников:
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
К.Ю. Поляков, Е.А. Ерёмин, 2013
b
x
x
x h
S x h f 1 ( x) f 2 ( x)
?
Как улучшить?
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
38
Метод прямоугольников
Алгоритмический язык:
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
Паскаль:
S:= 0; x:= a;
while x < b do begin
S:= S + f1(x+h/2)- f2(x+h/2);
x:= x + h
end;
S:= h*S;
writeln('Площадь ', S:8:3);
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
39
Метод трапеций
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
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
40
Метод трапеций
Алгоритмический язык:
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
?
Паскаль:
Как улучшить?
S:= 0; x:= a;
while x < b do begin
S:= S + f1(x)- f2(x)+ f1(x+h)- f2(x+h);
x:= x + h
end;
S:= h*S/2;
writeln('Площадь ', S:8:3);
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс
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]
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
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 близко к нулю!
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
Почему нельзя k = 0?
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
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
К.Ю. Поляков, Е.А. Ерёмин, 2013
?
Как улучшить?
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
47
Метод дихотомии
Паскаль:
k:= 0.01;
delta:= 2*eps;
while b - a > delta do begin
r:= k*(b - a);
x1:=(a + b)/2 - r;
Как улучшить?
x2:=(a + b)/2 + r;
if f(x1) > f(x2) then
a:= x1
else b:= x2
end;
writeln('x = ', (a+b)/2:10:3 );
?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
48
Метод золотого сечения
L
a
x2
x1
2
L
L
2
L
(b a)
L
x2
x1
L
L
2
отношение
золотого
сечения
1 5
1,618...
2
1 0
1 5
0,618...
2
(0,5 k ) (b a) 0,5 k
К.Ю. Поляков, Е.А. Ерёмин, 2013
b
1
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
49
Оптимальный раскрой листа

z
x
x
z
Цель:
V ( x) max
?
Ограничения:
?
V ( x) x (1 2 x) 2 max
Какие ограничения?
0 x 0,5
Какой результат ожидаете (по интуиции)?
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс
55
Что такое статистика?
Статистика – это наука, которая изучает методы
обработки и анализа больших массивов данных.
Ряд данных:
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")
К.Ю. Поляков, Е.А. Ерёмин, 2013
только числа!
=СУММ(A1:A20)
=СРЗНАЧ(A1:A20)
=МИН(A1:A20)
=МАКС(A1:20)
=СЧЁТ(A1:20)
СЧЁТЕСЛИ
http://kpolyakov.spb.ru

56. Дисперсия

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

57. Дисперсия

Решение вычислительных задач, 10 класс
57
Дисперсия
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 средний квадрат
отклонения от
среднего значения
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс
62
Вложенные условия
Доставка:
• бесплатно при >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) )
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

Решение вычислительных задач, 10 класс
64
Коэффициент корреляции
средние рядов
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)
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
65
Коэффициент корреляции
Как понимать это число?
• если 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, то связи нет?
!
Метод для определения линейной зависимости!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

67. Закон Гука

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

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

Решение вычислительных задач, 10 класс
68
Метод наименьших квадратов (МНК)
y k x
Y3
y2
y
y1
Y1
Y2
x1 x2
0
неизвестно!
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
!
Это задача оптимизации!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

Решение вычислительных задач, 10 класс
70
Метод наименьших квадратов (МНК)
Алгоритмический язык:
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*
x y
i 1
N
i
i
Паскаль:
2
x
i
A:= 0; B:= 0;
i 1
for i:=1 to N do begin
A:= A + x[i]*x[i];
B:= B + x[i]*y[i]
end;
var A, B, k: real;
k:= B / A;
x,y: array[1..N] of real;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

Решение вычислительных задач, 10 класс
74
Восстановление зависимостей
Корректная задача: найти функцию заданного вида,
которая лучше всего соответствует данным.
Примеры:
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
График функции не
обязательно проходит
через заданные точки!
К.Ю. Поляков, Е.А. Ерёмин, 2013
y a ebx
• логарифмическая
y a ln x b
?
Как выбрать
функцию?
http://kpolyakov.spb.ru

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

Решение вычислительных задач, 10 класс
75
Что значит «лучше всего соответствует»?
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
Фактически – метод наименьших квадратов!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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