Лекция 5

Алгоритмы вычисления определенных интегралов.

Основу численных методов вычисления определенных интегралов составляет их геометрический смысл. Определенным интегралом

называют площадь криволинейной трапеции, ограниченную подынтегральной кривой, осью абсцисс и ординатами f(a) и f(b). На рис. 5.1 данная площадь заштрихована.

Рис. 5.1 Геометрический смысл

определенного интеграла

При численном интегрировании подынтегральную функцию заменяют более простой, для которой вычисление указанной площади производится в соответствии с достаточно простыми формулами, и искомый интеграл вычисляют приближенно с определенной точностью.

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

Наиболее простым методом численного интегрирования является метод, основанный на применении формулы прямоугольников. В этом случае подынтегральную функцию/кривую заменяют прямой, а формула для вычисления площади прямоугольника известна. Для повышения точности вычислений участок интегрирования [a, b] разбивается на n равных частей. Далее берутся значения подынтегральной функции в левых (или правых) концах полученных участков. При этом подынтегральная функция f(x) на отрезке [a, b] заменяется ступенчатой кривой (см. рис. 5.2), и приближенное значение интеграла определяется суммой площадей прямоугольников

где

y

Аналогичная формула прямоугольников получится и в том случае, если брать для интегральной суммы значения функции f(x) не в левых, а в правых концах участков разбиения:

В результате расчетов по формулам «слева» и «справа» получается приближенное значение интервала (с недостатком или с избытком), которое может отличаться от действительного на некоторую величину, называемую ошибкой ограничения. Эта ошибка определяется величиной остаточного члена ряда Тейлора:

В качестве примера на рис. 5.3 приведена схема алгоритма, реализующего вычисления по формуле прямоугольников «слева». Увеличение числа участков разбиения n приводит к повышению точности вычисления интеграла. Следует обратить внимание также на формирование условия выхода из цикла на рис. 5.3, добавление половины шага h в условие необходимо для избежания возможного сравнения на равенство двух вещественных значений x и b–h.

Определение интеграла по формуле прямоугольников

Рис. 5.3 Алгоритм вычисления определенного

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

С целью повышения точности вычислений по методу прямоугольников значение подынтегральной функции целесообразно взять не на концах участков, а в их середине. В результате получим формулу средних:

,

где i=1,2,…,n. Остаточный член формулы средних где M = max |f "(v)| v[a,b].

Данный метод вычисления определенного интеграла обеспечивает более высокую точность при равном n по сравнению с формулами прямоугольников. Формулу средних рекомендуется использовать для достаточно гладких функций f(x), не содержащих высокочастотных колебаний на отдельных интервалах интегрирования. На рис. 5.4 показана схема алгоритма вычисления интеграла по формуле средних.

Формулы Ньютона-Котеса

Если подынтегральную функцию заменить каким-либо интерполяционным многочленом, то получим квадратурные формулы вида:

где х_к – выбранные узлы интерполяции; A_k – коэффициенты, которые зависят от выбранных узлов, но не зависят от вида функции f(x); R – остаточный член, определяющий максимальную ошибку при использовании квадратурной формулы; k=0, 1, …, n.

Разбивая отрезок интегрирования [a, b] на n равных частей системой точек

x_k = x₀+kh; k=0, 1, …, n; x₀=a; x_n=b

и вычисляя подынтегральную функцию в полученных узлах

y_k=f(x_k); k=0, 1, …, n,

получают квадратурные формулы для равноотстоящих узлов. Эти формулы называют формулами Ньютона-Котеса. Наиболее удобны при численном интегрировании интерполяционные многочлены невысоких порядков, при использовании которых получают достаточно простые составные формулы.

Формула трапеций.

Формула трапеций получается в случае использования интерполяционного многочлена 1-го порядка:

Остаточный член имеет вид: Использование формулы трапеций при вычислении определенного интеграла приводит к ошибке где

Для нахождения приближенного значения определенного интеграла по формуле трапеций можно использовать алгоритм, схема которого представлена на рис. 5.5.

Ошибка ограничения для метода трапеций больше, нежели чем для других формул Ньютона-Котеса, но его привлекательность заключается в простой реализации. Кроме того, незначительное усложнение алгоритма позволяет существенно снизить погрешность вычислений, поэтому формула трапеций достаточно часто используется (в сочетании с другими формулами).

Рис. 5.5 Алгоритм вычисления определенного

интеграла по формуле трапеций

Формула парабол (Симпсона)

Используя интерполяционный многочлен 2-го порядка (параболу) получают формулу численного интегрирования – формулу Симпсона:

где

На рис. 5.6 показана схема алгоритма, реализующего вычисления по формуле парабол. При реализации формулы число узлов обязательно нечетно, т. е. число участков разбиения интервала интегрирования должно быть четным: n=2m. В алгоритме использован прием, при котором число повторений цикла уменьшается в два раза, т. е. дважды реализуется модификация параметра цикла, что уменьшает время выполнения алгоритма. Метод Симпсона считается одним из наиболее применяемых методов численного интегрирования, обеспечивающим достаточно хорошую точность вычислений.

Рис. 5.6 Алгоритм вычисления определенного

интеграла по формуле Симпсона

Алгоритм вычисления суммы бесконечного ряда

Характерным примером итерационных циклов является задача вычисления суммы бесконечного ряда:

где t_n(x) – слагаемое, зависящее от параметра x (в общем случае) и номера n. Вычисляемая последовательность

где – частная сумма.

Для контроля погрешности можно использовать последовательность

где t_n(x) = s_n(x) – s_n-1(x) – слагаемые ряда n.

.

Условие выхода из итерационного цикла (справедливо при знакопеременном ряде {t_n(x)}):

| t_n ( x ) | <  .

Алгоритм вычисления бесконечной суммы является модификацией одного из алгоритмов вычисления конечной суммы. Если применение рекуррентных формул нецелесообразно, то вычисления будут наиболее эффективными, если каждое слагаемое определять по общей формуле и полученные значения накапливать в некоторой переменной. Общий вид схемы алгоритма, реализующего вычисление бесконечной суммы с погрешностью  с помощью цикла с предусловием, показан на рис. 5.10, а.

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

то общая схема итерационного алгоритма для вычисления бесконечной суммы показана на рис. 5.10, б.

Например, тригонометрическая функция sin(x) может быть представлена в виде бесконечной суммы

В данном случае

тогда

Теперь можно определить

Начальное значение слагаемого находим по формуле

Алгоритмы нахождения корней уравнений.

Решение алгебраических уравнений численными методами состоит из двух этапов:

– отделение корней, т. е. отыскание достаточно малых интервалов
(a, b), в каждом из которых заключен один и только один корень;

– вычисление (уточнение) корня с заданной погрешностью.

Рассмотрим более подробно алгоритмы для уточнения корней.

Метод половинного деления

Метод половинного деления является более универсальным, всегда приводит к искомому результату, хотя и требует большого объема вычислений. Для нахождения корня уравнения f(x)=0, принадлежащего отрезку [a, b], делим отрезок пополам z = (a+b)/2 (см. рис. 5.12,а). Далее рассмотрим значения функции y = f(x) в точках x = a и x = z. Если значения f(a) и f(z) разных знаков, т. е. f(a) f(z) < 0, то исходный отрезок [a, b] уменьшим в два раза путем переноса точки x = b в точку x = z. Новый отрезок [a, b] вновь делим пополам (см. рис. 5.12,б) и так как f(a) f(z) < 0, то переносим точку x = a в точку x = z, уменьшая [a, b] в два раза. Повторяем указанную процедуру до тех пор, пока длина отрезка, содержащего корень, не станет меньше заданной погрешности ε. Любое значение является искомым значением корня, однако на практике в качестве корня выбирают середину отрезка, т. е. x = (a+b)/2.

При организации итерационного цикла вычисляется последовательность отрезков

[a₀, b₀], [a₁, b₁], …, [a_n, b_n], … ,

для которой

Для контроля точности вычисления корня можно использовать следующую последовательность значений