К.Ю. Поляков, Е.А. Ерёмин, 2013 Решение вычислительных задач на компьютере § 70. Решение уравнений 1. - презентация

1 К.Ю. Поляков, Е.А. Ерёмин, Решение вычислительных задач на компьютере § 70. Решение уравнений 1

2 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Методы решения уравнений 2 Точные (аналитические) методы: Графический метод: Как решать? ? Можно поручить такой поиск компьютеру! ! Можно ли получить точное решение? ?

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

4 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Приближенные методы 4 По одной точке: 1)выбрать начальное приближение x 0 2)уточнить решение с помощью некоторого алгоритма: x 3)повторять шаг 2, пока два последовательных приближения не будут отличаться достаточно мало 0 x y x*x* x0x0 x1x1 x2x2 касательная Завершение работы: метод Ньютона (метод касательных)

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

6 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод перебора 6 Задача. Найти решение уравнения справа от точки с точностью. x y x*x* a b b*b* a*a* Алгоритм: 1)разбить отрезок [a, b] на полосы шириной = 2 2)найти полосу [a *, b * ], в которой находится x * 3)решение:

7 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Есть ли решение на [x, x+ ] ? 7 Если непрерывная функция f (x) имеет разные знаки на концах интервала [a, b], то в некоторой точке x * внутри [a, b] она равна 0, то есть f (x * ) = 0 ! ! x y x*x* 0 x x+ нет решения x y x*x* 0 x x+ есть решение! x y x*x* 0 x x+ нет решения В чём отличие? ?

8 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод перебора ( a = 0 ) 8 алг Перебор нач вещ eps, x, delta eps:= x:= 0 | x:= a delta:= 2*eps нц пока f(x)*f(x+delta) > 0 x:= x + delta кц вывод 'x = ', x+eps кон алг Перебор нач вещ eps, x, delta eps:= x:= 0 | x:= a delta:= 2*eps нц пока f(x)*f(x+delta) > 0 x:= x + delta кц вывод 'x = ', x+eps кон алг вещ f( вещ x ) нач знач:= x - cos(x) кон алг вещ f( вещ x ) нач знач:= x - cos(x) кон Когда остановится? ? Зацикливание? ?

9 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод перебора ( a = 0 ) 9 const eps = 0.001; var x, delta: real; 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. const eps = 0.001; var x, delta: real; 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. function f(x: real):real; begin f:= x - cos(x) end; function f(x: real):real; begin f:= x - cos(x) end; Когда остановится? ? Зацикливание? ?

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

11 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, c Метод деления отрезка пополам 11 x y x*x* 0 ab Алгоритм: 1)вычислить середину отрезка: 2)если на отрезке [a,c] есть решение, присвоить b:=c, иначе a:=c 3)повторять шаги 1-2 до тех пор, пока. Что напоминает? ? п.2: как определить, если ли решение? ? Вариант:

12 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод деления отрезка пополам 12. delta:= 2*eps нц пока b - a > delta c:= (a + b) / 2 если f(a)*f(c) <= 0 то b:= c иначе a:= c все кц вывод 'x = ', (a+b)/2 delta:= 2*eps нц пока b - a > delta c:= (a + b) / 2 если f(a)*f(c) <= 0 то b:= c иначе a:= c все кц вывод 'x = ', (a+b)/2 Как меняется длина отрезка? ? За сколько шагов уменьшится в 1000 раз? ? Алгоритмический язык: sign(f(a)) <> sign(f(c))

13 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод деления отрезка пополам 13. 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); 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 раз? ? Паскаль:

14 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Полёт мяча 14 4 м 2 м 2 м 10 м неизвестен

15 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Полёт мяча 15 Задача. Найти угол (и время t ) при котором x = S и y = H : Решение: Диапазон углов для поиска: Как уточнить? ?

16 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Уточнение диапазона углов 16 Диапазон углов для поиска:

17 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Полёт мяча 17 pi:= u:= 0 delta:= 2*eps нц пока u < pi/2 если f(u)*f(u+delta) <= 0 то вывод 'Угол: ', (u+eps)*180/pi вывод ' градусов', нс все u:= u + delta кц pi:= u:= 0 delta:= 2*eps нц пока u < pi/2 если f(u)*f(u+delta) <= 0 то вывод 'Угол: ', (u+eps)*180/pi вывод ' градусов', нс все u:= u + delta кц Программа на алгоритмическом языке:

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

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

20 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Полёт мяча 20 Excel: РАДИАНЫ S $B$ Диаграмма XY: Excel: Точечная

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

22 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

23 Решение вычислительных задач, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Источники иллюстраций 23 1.vispo.ruvispo.ru иллюстрации художников издательства «Бином» 4. авторские материалы