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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21. Полёт мяча

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

24. Полёт мяча

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

26. Полёт мяча

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

27. Полёт мяча

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

59. Дисперсия

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

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

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

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

Решение вычислительных задач, 10 класс, Паскаль
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 класс, Паскаль
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. Решение вычислительных задач на компьютере (язык Паскаль)

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

69. Закон Гука

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

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

Решение вычислительных задач, 10 класс, Паскаль
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 класс, Паскаль
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 класс, Паскаль
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
x y
k i 1N
*
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;
К.Ю. Поляков, Е.А. Ерёмин, 2018-2019
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

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