ОСНОВЫ ПРОГРАММИРОВАНИЯ Раздел 2. Математические основы программирования Численные алгоритмы Старший преподаватель Кафедры ВС, к.т.н. Поляков Артем Юрьевич 1 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Рассматриваемые вопросы Примеры численных алгоритмов: – вычисление определенного интеграла функции одной переменной; 2 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Геометрический смысл определенного интеграла 3 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» f (x) ab x y Под определенным интегралом S понимают площадь подграфика функции f (x) на отрезке [a, b].

Приближенное вычисление определенного интеграла (метод левых прямоугольников) 4 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» f (x) a b x y

Приближенное вычисление определенного интеграла (метод правых прямоугольников) 5 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» f (x) a b x y

Приближенное вычисление определенного интеграла (метод прямоугольников) 6 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» f (x) a b x y

Алгоритм метода прямоугольников 7 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» f (x), a, b, N i = 0, S=0, h = (b a)/N НАЧАЛО i N 1 x = a + h·(i + 0,5) S = S + f (x)·h i = i + 1 КОНЕЦ НЕТ ДА S

Псевдокод алгоритма метода прямоугольников 8 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ввод f (x), N, a, b i = 0 S = 0 h = (b a)/N пока i N 1 делать x = a + h·(i + 0,5) S = S + f (x)·h i = i + 1 конец пока вывод S

Погрешность метода прямоугольников 9 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Точность метода зависит: 1.От длины интервала интегрирования (b – a). 2.От длины h шага приближенного интегрирования. 3.От функции f(x), которая представлена первой или второй производной. Единственный параметр, на который можно повлиять – это шаг h. Какой максимальной точности можно добиться при фиксированных остальных параметрах? - Метод левых и правых прямоугольников - Метод прямоугольников

Метод трапеций (приближение полиномами первой степени) 10 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» xixi x i+1

Алгоритм метода трапеций 11 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» f (x), N, a, b i = 0, S=0,h=(b a)/N НАЧАЛО i (N – 1) x 1 = a + h·i x 2 = a + h·(i + 1) S = S + ( f (x 1 ) + f (x 2 ))·h/2 i = i + 1 КОНЕЦ НЕТ ДА S

Псевдокод алгоритма метода трапеций 12 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ввод f (x), N, a, b i = 0 S = 0 h=(b a)/N пока i (N – 1) делать x 1 = a + h·i x 2 = x 1 + h S = S + ( f (x 1 ) + f (x 2 ))· h /2 i = i + 1 конец пока вывод S

Погрешность метода трапеций 13 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Точность метода зависит: 1.От длины интервала интегрирования (b – a). 2.От длины h шага приближенного интегрирования. 3.От функции f(x), которая представлена второй производной f''(x). Единственный параметр, на который можно повлиять – это шаг h. Какой максимальной точности можно добиться при фиксированных остальных параметрах?

14 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Метод Симпсона (приближение полиномом 2-й степени) xixi x i+1/2 xi+1xi+1

Алгоритм метода Симпсона 15 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» f (x), N, a, b i = 0, S=0, h = (b a)/N НАЧАЛО i N 1 x i = a + h·i x i+1 = x i + h x i+1/2 = (x i + x i+1 )/2 S = S + ( f (x i ) +4 f (x i+1/2 )+ f (x i+1 ))·h/6 i = i + 1 КОНЕЦ НЕТ ДА S

Псевдокод алгоритма Симпсона 16 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ввод f (x), N, a, b i = 0 S = 0 h=(b a)/N пока i N – 1 делать x i = a + h·i x i+1 = x i + h x i+1/2 = (x i + x i+1 )/2 S = S + ( f (x i ) +4 f (x i+1/2 )+ f (x i+1 ))·h/6 i = i + 1 конец пока вывод S

Погрешность метода Симпсона 17 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Точность метода зависит: 1.От длины интервала интегрирования (b – a). 2.От длины h шага приближенного интегрирования. 3.От функции f(x), которая представлена третьей производной. Единственный параметр, на который можно повлиять – это шаг h. Какой максимальной точности можно добиться при фиксированных остальных параметрах?

ИТОГИ 18 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Рассмотрено 5 алгоритмов численного интегрирования и рассмотрены факторы, влияющие на точность их работы: 1.Метод левых прямоугольников 2.Метод правых прямоугольников 3.Метод и алгоритм прямоугольников (средних) 4.Метод трапеций 5.Метод Симпсона