74243

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

Лекция

Информатика, кибернетика и программирование

Основу численных методов вычисления определенных интегралов составляет их геометрический смысл. В этом случае подынтегральную функцию кривую заменяют прямой а формула для вычисления площади прямоугольника известна. приведена схема алгоритма реализующего вычисления по формуле прямоугольников слева.

Русский

2014-12-30

1.27 MB

11 чел.

Лекция 5

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

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

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

 

 

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

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

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

где          

   

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

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

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

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

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

,

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

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

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

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

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

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

xk = x0+kh; k=0, 1, …, n;  x0=a;  xn=b

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

yk=f(xk);  k=0, 1, …, n,

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

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

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

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

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

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

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

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

где  

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

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

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

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

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

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

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

.

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

| tn ( 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.

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

[a0, b0],  [a1, b1],  …,  [an, bn], … ,

для которой

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

поэтому условие выхода из цикла

или условие продолжения цикла

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

      y

                                                                                                             

f(z)

  1.                 a    

                            x*           z                 b          

f(a)      

                              a)

y

                                                                            y=f(x)

 0                 a       x*

f(z)                       z              b                        x

f(a)

                             b)

Метод касательных

Для обеспечения сходимости метода касательных (метода Ньютона) необходимо, чтобы производные f' (x) и f" (x) были определены, непрерывны и сохраняли постоянные знаки на отрезке [a, b]. На рис. 5.14 представлена геометрическая интерпретация метода Ньютона.

Выберем некоторую точку x0 на отрезке [a, b] и проведем касательную к кривой y=f(x) в точке P0(x0, y0). Ее уравнение

y = y0 + f' (x0)(xx0),

где y0 = f(x0).

Новое приближение корня х1, равно абсциссе точки пересечения касательной с осью абсцисс, т. е.

y

y0

y1

y2

Выберем некоторую точку x0 на отрезке [a, b] и проведем касательную к кривой y=f(x) в точке P0(x0, y0). Ее уравнение

y = y0 + f' (x0)(xx0),

где y0 = f(x0).

Новое приближение корня х1, равно абсциссе точки пересечения касательной с осью абсцисс, т. е.

Проведя касательную через точку P1(x1, y1), получим второе приближение корня x2. Вычисление приближений корня по формуле

продолжается до выполнения неравенства

,

где ε – абсолютная погрешность определения корня уравнения.

Начальное приближение х0 выбирают таким образом, чтобы выполнялось условие

В противном случае сходимость метода Ньютона не гарантируется. На практике выбирают x0 = a или x0 = b, в зависимости от того, в какой из этих точек выполняется указанное условие. Схема алгоритма уточнения корня методом Ньютона (методом касательных) приведена на рис. 5.15.

Алгоритмы обработки массивов

Определение минимального элемента в массиве.

Задача нахождения минимума (или максимума) в массиве из N элементов может быть решена последовательным сравнением "текущего" минимального (максимального) значения со значением очередного элемента массива и "запоминанием" при необходимости нового значения. Схема алгоритма показана на рис. 5.18.

 

Рис. 5.18  Алгоритм определения минимального элемента массива

Сортировка массива. 

Допустим, необходимо упорядочить массив из N элементов по возрастанию. Задача решается последовательным сравнением пар соседних элементов массива и при необходимости их перестановкой. Сравнение происходит при  N-1 проходах по всему массиву. Схема алгоритма показана на рис. 5.19.

Рис. 5.19  Алгоритм сортировки массива методом пузырька

Произведение матриц

Пусть необходимо найти произведение двух матриц А и В размером 2х3 и 3х3 соответственно. Элементы результирующей матрицы С (размером 2х3) определяются по формуле

где n – число строк матрицы А;

     m – число столбцов матрицы А и число строк матрицы В;

     p – число столбцов матрицы В.

В общем случае результирующая матрица имеет размер np. Схема алгоритма умножения двух матриц представлена на рис. 5.20.

Рис. 5.20  Алгоритм умножения матриц


Алгоритм обработки строк

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

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

Схема алгоритма решения данной задачи приведена на рис. 5.21. При этом алгоритм удаления пробелов в начале строки оформлен в виде процедуры, а выделения слова – в виде функции.

Рис. 5.21  Алгоритм подсчета количества слов в строке и их вывод

Алгоритм обработка записей

Пусть имеются некоторые данные о заводах города, сведенные в следующую таблицу:

Завод

Основные сведения

Зани-маемая площадь

Объем выпускаемой продукции

Количество обслуживающего персонала

по плану

факти-чески

с высшим образованием

со средним образованием

АЗЛК

ВАЗ

ЗИЛ

ИЖ

800

396

203

544

484,9

348,5

384,3

667,3

484,9

348,7

399,4

701,3

282

130

448

396

204

669

125

157

Всего

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

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

Рис. 5.22  Алгоритм обработки массива записей

PAGE  16


y=f(x)

a

     y

  x

 b

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

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

0    a=x0     x1        x2      …       b=xn   x

y=f(x)

y1

y2

Обязательные параметры отсутствуют или неверны.Рис. 5.2  Иллюстрация метода прямоугольников

 y

Начало

a, b, n

EMBED Equation.3  

s:=s+f(x)

x:=x+h

x:=a

EMBED Equation.3  

s:=sh

s

Нет

Да

онец

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

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

Начало

Ввод a, b, n

EMBED Equation.3  

s:=s+f(x)

x:=x+h

EMBED Equation.3  

EMBED Equation.3  

s:=sh

Вывод s

Конец

Нет

Да

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

интеграла по формуле средних.

Начало

Ввод a, b, n

EMBED Equation.3  

x:=a+h

s:=s+f(x)

x:=x+h

EMBED Equation.3  

s:=sּh

Вывод s

Конец

Нет

Да

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

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

Начало

Ввод a, b, n

EMBED Equation.3  

x:=a+h

s:=s+4f(x)

x:=x+h

s:=s+2f(x)

x:=x+h

EMBED Equation.3  

EMBED Equation.3  

Вывод s

Конец

Нет

Да

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

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

Начало

Ввод x, ε

EMBED Equation.3  

|t|>ε

t:=tn(x)

s:=s+t

n:=n+1

Конец

Вывод s

Начало

Ввод x xx, ε

EMBED Equation.3  

|t|>ε

t:=n(x)

s:=s+t

n:=n+1

Вывод s

Конец

Нет

Да

Нет

Да

Рис. 5.10  Схемы алгоритмов итерационных циклов,

реализующих вычисление бесконечной суммы

б)

а)

y=f(x)

Рис. 5.12  Графическая иллюстрация

метода половинного деления

Начало

Ввод a, b, ε

|b-a| ≥ ε

EMBED Equation.3  

f(z)f(a) < 0

a:=z

b:=z

EMBED Equation.3  

Вывод x, f(x)

Конец

Нет

Да

Да

Нет

Рис. 5.13  Схема алгоритма уточнения корня

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

Рис. 5.14 Геометрическая интерпретация

метода касательных

      0                 a                   x*         x2           x1                x0          b   x

y=f(x)

Начало

Ввод a, b, ε

f(a)f"(a) > 0

f(b)f"(b) > 0

x:=a

x:=b

"ошибка"

h:=f(x)/f'(x)

x:=x-h

|h| < ε

Вывод x, f(x)

Конец

Нет

Да

Нет

Да

5.15  Схема алгоритма уточнения корня методом касательных


 

А также другие работы, которые могут Вас заинтересовать

85317. Влияние христианства на искусство России 39.75 KB
  Любимейшим чтением русских людей были жития святых называемые также агиографией. Так появились жития первых русских святых Бориса и Глеба Феодосия Печерского Мстислава и Ольги Александра Невского. Автором первых русских житийных произведений о Борисе и Глебе о Феодосии Печерском был монах Нестор один из составителей Повести Временных лет. Особой любовью у русских людей пользовался сложившийся в XII XIV вв.
85318. Художественно-эстетические аспекты народной художественной культуры 40.37 KB
  Гранина: Зачем нужно искусство речь шла о первобытном искусстве заметил что скорее всего изображения в пещерах создавались не ради самих изображений искусство ради искусства не ради того чтобы изобразить цель охоты а изображали то что боялись[301]. То есть искусство боролось уже не только со смертью но и с бесформенностью с бессодержательностью мира. Лихачева о том что искусство борется даже не с хаосом так как хаос в какойто мере форма существования мира а с хаотичностью[310]. Искусство стремится ввести восприятие в русло...
85319. Многообразие и самобытность традиций художественных культур народов России 32.27 KB
  Естественно что преимущественно можно наблюдать разнообразие народных культур. Но вместе с тем можно говорить и о единстве нородных культур России.Соответственно люди перенимают полностью или частично у друг друга некоторые традиции обычаи и другие культурные особенности.
85320. Характеристика архаического и традиционного общества 38.79 KB
  АРХАИЧНОЕ ОБЩЕСТВО это общество выделившееся из природного мира на самых ранних фазах своего существования. Общество локально. Общество напоминает острова разбросанные в природном океане. Архаичное общество охватывает длительный период человеческой истории включающий в себя и самые ранние первобытные формы общественной жизни и более поздние с уже сложившимися властными и экономическими институтами: царскими династиями рабо и землевладением всем тем что подпадает под емкое хотя и географически неточное определение К.
85321. Хронотоп в традиционной обрядовой культуре 44.39 KB
  χρόνος время и τόπος место закономерная связь пространственновременных координат[1]. Пространство и время культуры как хронотоп Пространство и время обязательные координаты любых культурных явлений и событий которые всегда происходят гдето и когдато. ввел в культурологию и философию понятие хронотопа которое подчеркивает что пространство и время культуры всегда связаны с субъективными переживаниями меняющимися в разных исторических эпохах и культурных ситуациях. Вернадского в которой единое пространствовремя связано с...
85322. Проблемы возрождения и сохранения фольклора 41.15 KB
  Подобная точка зрения акцентирует одну сторону традиции связь народного искусства с прошлым его корни древние истоки без которых вообще невозможно понимание этого явления человеческой культуры. Абсолютизируя одну сторону традиции некоторые ученые видят в традициях народного искусства только прошлое и делают вывод о косности отсталости этого искусства отсутствии в нем связей с современностью. Салтыков...
85323. Предмет, цель и задачи курса Теория и история НХК 33.73 KB
  На теоретическом уровне дисциплина представляет собой систему понятий положений выводов касающихся сущности содержания средств и методов организации учебновоспитательного процесса в изучении народного художественного творчества на основе современных требований к формированию личности педагога как субъекта обучения и воспитания. На методическом уроне изучаются технологические основы народного художественного творчества в системе социокультурной деятельности современного образования. На практическом уровне будущие руководители приобретают...
85324. Функции традиционного народного костюма 39.08 KB
  В искусстве костюма органично соединились различные виды декоративного творчества: ткачество вышивка кружевоплетение низание шитье аппликация и изобразительное использование разнообразных материалов: тканей кожи меха лыка бисера бус блесток пуговиц шелковых лент тесьмы позумента кружев птичьих перьев речного жемчуга перламутра цветных граненных стеклышек и др. Хранителями древних традиций народного костюма у русских как и большинства других народов были крестьяне.Борева включал не только зачатки различных видов...
85325. Семиотические основы изучения народной художественной культуры 39.09 KB
  Решающим фактором народной культуры является процесс антропогенеза и происхождения народной культуры как таковой. В животном мире культуры не существует. В животном мире обнаруживаются явления которые в дальнейшем послужили основанием для формирования народной культуры.