Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Численное интегрирование функций - файл 1.doc


Численное интегрирование функций
скачать (266 kb.)

Доступные файлы (1):

1.doc266kb.29.11.2011 18:48скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
РЕФЕРАТ

Численное интегрирование функций

Содержание





Введение……………………………………………………………………….

3

Численное интегрирование функций………………………………………..

5

Метод прямоугольников (метод Эйлера)…………………………………...

8

Метод трапеций………………………………………………………………

10

Проверка устойчивости решения……………………………………………

11

Метод парабол (метод Симпсона)…………………………………………...

12

Увеличение точности…………………………………………………………

16

Метод Гаусса………………………………………………………………….

19

Метод Монте-Карло………………………………………………………….

21

Список использованной литературы………………………………………..

23


Введение



Появление и непрерывное совершенствование быстродействующих электронных вычислительных машин (ЭВМ) привело к подлинно революционному преобразованию науки вообще и математики в особенности. Изменилась технология научных исследований, колоссально увеличились возможности теоретического изучения, прогноза сложных процессов, проектирования инженерных конструкций. Решение крупных научно-технических проблем, примерами которых могут служить проблемы овладения ядерной энергией и освоения космоса, стало возможным лишь благодаря применению математического моделирования и новых численных методов, предназначенных для ЭВМ.

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

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

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

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

Численное интегрирование функций



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



где - число точек, в которых вычисляется значение подынтегральной функции. Точки называются узлами метода, числа - весами узлов. При замене подынтегральной функции на полином нулевой, первой и второй степени получаются соответственно методы прямоугольников, трапеций и парабол (Симпсона). Часто формулы для оценки значения интеграла называют квадратурными формулами.

Пусть функция задана на интервале . Задача состоит в том, чтобы подобрать точки и коэффициенты так, чтобы квадратурная формула



была точной для всех полиномов наивысшей возможной степени.

Ввиду того, что имеется параметров и , а полином степени определяется коэффициентами, эта наивысшая степень в общем случае .

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

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

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

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

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

Интерполяция - в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений.

Многим из тех, кто сталкивается с научными и инженерными расчётами часто приходится оперировать наборами значений, полученных экспериментальным путём или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией кривой. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных.

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

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

Кратко рассмотрим основные методы численного интегрирования.

^

Метод прямоугольников (метод Эйлера)






Пусть функцию необходимо проинтегрировать численным методом на отрезке [a, b]. Разделим отрезок на N равных интервалов (на рисунке N = 4).
Площадь каждой из 4-х криволинейных трапеций можно заменить на площадь прямоугольника.

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

В качестве выбора высоты прямоугольников можно предложить выбрать значение функции на левой границе. В этом случае высота первого прямоугольника составит f(a), второго – f(x1), третьего – f(x2), последнего – f(x3). Приближенное значение интеграла получается суммированием площадей прямоугольников

Если в качестве выбора высоты прямоугольников взять значение функции на правой границе, то в этом случае высота первого прямоугольника составит f(x1), второго – f(x2), третьего – f(x3), последнего – f(b).


Как видно, в этом случае, одна из формул дает приближение к интегралу с избытком, а вторая c недостатком. Можно предложить еще один способ, очевидно лучший, чем обе эти формулы – использовать для аппроксимации значение функции в середине отрезка интегрирования.

В общем виде, если отрезок [a, b] разбить на N равных интервалов интегрирования (h) и к каждому интервалу применить формулу прямоугольников, то получим




^

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



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

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

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




^

Проверка устойчивости решения



Как правило, чем меньше длина каждого интервала, т.е. чем больше число этих интервалов, тем меньше различаются приближенное и точное значение интеграла. Это справедливо для большинства функций. В методе трапеций ошибка вычисления интеграла (δ) приблизительно пропорциональна квадрату шага интегрирования h 2

δ ~ h 2

Таким образом, для вычисления интеграла некоторой функции в пределах a, b необходимо разделить отрезок [a, b] на n0 интервалов и найти сумму площадей трапеций. Затем нужно увеличить число интервалов (n1), опять вычислить сумму трапеций и сравнить полученное значение с предыдущим результатом. Это следует повторять до тех пор (ni), пока не будет достигнута заданная точность результата (критерия сходимости).

Для методов прямоугольников и трапеций обычно на каждом шаге итерации число интервалов увеличивается в 2 раза, т.е. ni+1 = 2 ni. Алгоритм процедуры интегрирования можно записать следующим образом:

интеграл (I) рассчитывается по формуле
, где ,

а критерий сходимости

Главное преимущество правила трапеций – его простота. Однако если при вычислении интеграла требуется высокая точность, применение этого метода может потребовать слишком большого количества итераций или машинного времени.
^

Метод парабол (метод Симпсона)



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

Рассмотрим произвольный интеграл

Воспользуемся заменой переменной таким образом, чтобы границы отрезка интегрирования вместо [a,b] стали [-1,1], для этого введем переменную z:
, тогда и

Рассмотрим задачу интерполирования полиномом второй степени (параболой) подынтегральной функции, используя в качестве узлов три равноудаленные узловые точки – z = -1, z = 0, z = +1 (шаг равен 1, длина отрезка интегрирования равна 2). Обозначим соответствующие значения подынтегральной функции в узлах интерполяции


Система уравнений для нахождения коэффициентов полинома

, проходящего через три точки , и

примет вид
или
Коэффициенты легко могут быть получены

Вычислим теперь значение интеграла от интерполяционного многочлена



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


  • соответствует




  • соответствует




  • соответствует


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

Для первого отрезка интегрирования узлами интерполирования будут являться точки a, a+h, a+2h, для второго – a+2h, a+3h, a+4h, третьего a+4h, a+5h, a+6h и т.д. Приближенное значение интеграла получается суммированием N площадей:

В данную сумму входят одинаковые слагаемые (для внутренних узлов с четным значением индекса - 2i). Поэтому можно перегруппировать слагаемые в этой сумме таким образом
, что эквивалентно
, так как
Погрешность этого приближенного метода уменьшается пропорционально длине шага интегрирования в четвертой степени, т.е. при увеличении числа интервалов вдвое ошибка уменьшается в 16 раз

δ ~ h 4


^

Увеличение точности


Здесь мы рассмотрим так называемый процесс Эйткена. Он дает возможность оценить погрешность метода и указывает алгоритм уточнения результатов. Расчет проводится последовательно три раза при различных шагах разбиения h1, h2, h3, причем их отношения постоянны: h2/ h1 = h3/ h2 = q (например, при делении шага пополам q=0.5). Пусть в результате численного интегрирования получены значения интеграла I1, I2, I3. Тогда уточненное значение интеграла вычисляется по формуле



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

.

Уточнение значения интеграла можно также проводить методом Рунге-Ромберга.

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

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

Рассмотрим принцип работы адаптивного алгоритма. Первоначально отрезок [a,b] разбиваем на n частей. В дальнейшем каждый такой элементарный отрезок делим последовательно пополам. Окончательное число шагов, их расположение и размеры зависят от подынтегральной функции и допустимой погрешности e .

К каждому элементарному отрезку [xi-1, xi] применяем формулы численного интегрирования при двух различных его разбиениях. Получаем приближения для интеграла по этому отрезку:



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

Процесс деления отрезка пополам и вычисления уточненных значений продолжается до тех пор, пока их разность станет не больше некоторой заданной величины di, зависящей от e и h:

.

Аналогичная процедура проводится для всех n элементарных отрезков. Величина принимается в качестве искомого значения интеграла. Условия и соответствующий выбор величин di обеспечивают выполнение условия



^

Метод Гаусса



Описанные выше методы используют фиксированные точки отрезка (концы и середину) и имеют низкий порядок точности (0 - методы правых и левых прямоугольников, 1 - методы средних прямоугольников и трапеций, 3 - метод парабол (Симпсона)). Если мы можем выбирать точки, в которых мы вычисляем значения функции , то можно при том же количестве вычислений подынтегральной функции получить методы более высокого порядка точности. Так для двух (как в методе трапеций) вычислений значений подынтегральной функции, можно получить метод уже не 1-го, а 3-го порядка точности:

.

В общем случае, используя точек, можно получить метод с порядком точности . Значения узлов метода Гаусса по точкам являются корнями полинома Лежандра степени .

Значения узлов метода Гаусса и их весов приводятся в справочниках специальных функций. Наиболее известен метод Гаусса по пяти точкам.

При заданном числе интервалов разбиения следует расположить их концы так, чтобы получить наивысшую точность интегрирования. В математическом плане это означает выбор коэффициентов Ai и узлов ti, i=1,...,n квадратурных формул Гаусса:



такими, чтобы формулы были точны для многочленов наивысшей возможной степени N. Можно показать, что при n узлах точно интерпретируются все многочлены степени N2n-1.

Узлы ti являются корнями многочлена Лежандра:

.

Коэффициенты Ai вычисляются по формуле:

, i=1,...,n.

Погрешность усечения Rn:

, t[-1,1].

Для вычисления интеграла отрезок [a,b] преобразуется в отрезок [-1,1] путем замены переменной:

.

В результате формула Гаусса приобретает вид

,

где , .

Квадратурная формула Гаусса обеспечивает высокую точность вычислений при небольшом числе узлов.


^

Метод Монте-Карло



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

Проиллюстрируем применение этого метода на примере приближенного вычисления следующего интеграла:





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

,

попадающие в эту область. В данном случае абсциссы и ординаты точек должны быть случайными числами, равномерно распределенными на отрезке [0, 1].

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



Если условие выполняется, то выбранная точка соответствует «успеху», если нет – то «промаху». Таким образом, процедура может быть описана как игра в «попадание» случайно выбранной точки в область под графиком (отсюда и название метода - Монте-Карло).

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

Отсюда получается формула метода Монте-Карло:

Для реализации метода существенное значение имеет качество используемого датчика случайных чисел. Идеальный датчик должен давать равномерное распределение чисел в заданном диапазоне. Точность расчета интеграла определяется так же числом точек (N), используемых при вычислениях и, очевидно, должна увеличиваться при его росте.

Метод Монте-Карло широко используется в современных методах моделирования динамики молекулярных систем, взаимодействия растворенного вещества с молекулами растворителя, кинетики адсорбции веществ на твердых поверхностях и т.д.


^

Список использованной литературы





  1. Бахвалов Н., Жидков Н., Кобельков Г. Численные методы. М.: Лаборатория базовых знаний, 2001. 632 с.

  2. Вержбицкий, В. М. Численные методы. Математический анализ и обыкновенные дифференциальные уравнения. М.: Высш.шк., 2001. 400 с.

  3. Самарский А.А., Гулин А.В. Численные методы: Учебное пособие для ВУЗов. М.: Наука, 2003. 432 с.




Скачать файл (266 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации