Приближенное вычисление определенных интегралов по формуле Макария. Алгоритм стандартной подпрограммы

Размещено на http: //www. allbest. ru/

Руководство программиста

Приближенное вычисление определенных интегралов по формуле Макария. Алгоритм стандартной подпрограммы

Разработчик: Гончаров В.И.

Самара 2011



Содержание

Введение

1. Исходная формулировка задачи

2. Математическая модель процесса приближенного интегрирования

3. Алгоритмическое описание процесса приближенного интегрирования

4. Повышение эффективности вычислений при использовании подпрограммы

5. Тестирование стандартной подпрограммы

6. Область применения алгоритма

7. Текст стандартной подпрограммы

Литература



Введение

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

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



1. Исходная формулировка задачи

Разработать алгоритм приближенного вычисления определенных интегралов

В качестве теоретической базы применить установленное в теореме ([1], С.334) свойство определенных интегралов, выражаемое равенством

где функция интегрируема

в при ; .

алгоритм интеграл приближенный

Здесь обозначает промежуточное значение, которое рассматривается в качестве числовой характеристики подынтегральной функции на отрезке интегрирования. Для некоторых функций промежуточное значение может не принадлежать множеству принимаемых ею значений. Когда функция непрерывна, то суть наименьшее и наибольшее значения функции на отрезке интегрирования, факт существования которых установлен в теореме Вейерштрасса ([1], С.135). В этом случае промежуточное значение по теореме Больцано - Коши ([1], С.131) принимается функцией в некоторой точке отрезка т. е.

.



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

2. Математическая модель процесса приближенного интегрирования

На основе теоремы ([1], С.334) построим формулу Макария. Для вывода формулы выполним регулярное разбиение отрезка интегрирования точками

на равных частичных отрезков

,

где

Для приближенного представления функции регулярно выберем на отрезке интегрирования узлов интерполяции

, где

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

.

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

где константа, . Узлом интерполяции выбираем точку . Требуется, чтобы значение функции в этом узле совпадало со значением функции :

.

Составим уравнение, из которого однозначно определяется коэффициент

.

Тогда приближающая функция на частичном отрезке имеет вид

.

На каждом частичном отрезке :

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



- вычислим определенный интеграл от приближающей функции

Составим сумму по всем частичным отрезкам

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

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

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

. (3)



Если точное значение интеграла неизвестно, то для оценки погрешности

формулы (3) при выбранном разбиении отрезка интегрирования на частичных отрезков необходимо использовать остаточный член квадратурной формулы Макария

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

В выбранном разбиении отрезка интегрирования формула Макария содержит параметров: , которые не зависят от функции Указанные параметры надо выбрать так, чтобы погрешность формулы Макария не превышала заданную погрешность. Среди перечисленных параметров только параметр является свободным, остальные параметры зависят от параметра . Таким образом, для обеспечения требуемой точности вычисления интеграла необходимо изменять значение параметра . С этой целью выполним последовательное разбиение отрезка интегрирования на 2, 3, 4, … частичных отрезков и для каждого разбиения вычислим по формуле (2) суммы . Составим числовую последовательность (первый член последовательности условно принят равным нулю, т. е. ). Члены этой последовательности рассматриваются как приближения интеграла.

Отметим три свойства этой последовательности, которые будут использованы при построении математической модели.

1) Последовательность для интегрируемых функций имеет своим конечным пределом ([1], С.327)

С помощью сумм значение определенного интеграла для каждой интегрируемой функции может быть вычислено с любой степенью точностью: при возрастании n до бесконечности абсолютная погрешность формулы Макария безгранично убывает. 2) Последовательность имеющая конечный предел , удовлетворяет критерию Коши ([1], С.107): для любого числа существует такой номер что для всех номеров

и

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

.

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



Установлено ([1], С.105), если последовательность имеет определенный предел , то тот же предел имеет и частичная последовательность

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

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

.

Последняя соответствует последовательному разбиению отрезка на

k = 0,1,2,…

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

Начальное приближение (для k = 0) выберем в виде

Формулы для определения последовательностей имеют вид

где множество узлов интерполяции, выбранных на -ой итерации;

шаг между выбранными узлами интерполяции; число вновь выбранных узлов интерполяции.

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



;

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

С помощью указанных формул установлено правило преобразования предыдущего приближения интеграла (в том числе и начального приближения) в следующее приближение при последовательном изменении параметра k от 1 с шагом 1. При этом погрешность -го члена последовательности при возрастании k до бесконечности безгранично убывает (основание: третье свойство частичной последовательности). Вычисления последовательности прекращают после того как два последовательных приближения совпадают с заданной степенью точности, т. е., когда выполнится неравенство

где заданная погрешность (основание: второе свойство последовательности).

Тогда в качестве приближенного значения интеграла полагают т. е.

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

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



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

Приведем алгоритм процесса приближенного интегрирования.

3. Алгоритмическое описание процесса приближенного интегрирования

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

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

;



- вычислить шаг между соседними узлами

- вычислить число узлов, вновь выбранных на текущей итерации

;

- присвоить начальное значение абсциссе определяющей текущий узел интерполяции,

- вычислить шаг между узлами, вновь выбранными на текущей итерации

;

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

;



Здесь интерпретируется как вызов подпрограммы для вычисления значения подынтегральной функции; из стандартной подпрограммы в эту подпрограмму передается в качестве аргумента(абсцисса текущего узла, вновь выбранного на текущей итерации); - вычислить абсциссу следующего узла интерполяции, вновь выбранного на текущей итерации,

и передать управление в начало цикла ;

- на текущей итерации после выполнения цикла вычислить приближенное значение интеграла

- проверить неравенство

.

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

4. Повышение эффективности вычислений при использовании подпрограммы

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

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

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

5. Тестирование стандартной подпрограммы

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



6. Область применения алгоритма

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

7. Текст стандартной подпрограммы

Для иллюстрации в качестве примера приведем текст стандартной подпрограммы

SPVM983.PRG. Среда программирования и выполнения подпрограммы: операционная

система MS DOS, система программирования CLIPPER 5.0.

// ---

// ПРИБЛИЖЕННОЕ ВЫЧИСЛЕНИЕ ОПРЕДЕЛЕННЫХ ИНТЕГРАЛОВ

// ПО ФОРМУЛЕ МАКАРИЯ. СТАНДАРТНАЯ ПОДПРОГРАММА

FUNCTION SPVM983 (pg1, pg2, pg3, pg4)

// pg1 - нижний предел интеграла

// pg2 - верхний предел интеграла

// pg3 - абсолютная погрешность приближенного значения интеграла

// pg4 - имя подпрограммы для вычисления значений подынтегральной функции

LOCAL is, pc1, pc2, pc3, pc4, pc5, pc6, pc7:= 0, pc8, pc9, pc10

// pc1 - длина отрезка интегрирования

// pc2 - число узлов интерполяции на предыдущей итерации

// pc3 - число узлов интерполяции на текущей итерации

// pc4 - шаг между соседними узлами интерполяции

// pc5 - сумма частных значений подынтегральной функции в узлах интерполяции

// pc6 - приближенное значение интеграла на предыдущей итерации

// pc7 - приближенное значение интеграла на текущей итерации

// pc8 - число узлов, вновь выбранных на текущей итерации

// pc9 - абсцисса текущего узла, вновь выбранного на текущей итерации

// pc10 - шаг между узлами, вновь выбранными на текущей итерации

IF pg1 # pg2

pc1 pg2 - pg1

pc2 2

pc4 pc1

pc5 &pg4.(pg1) + &pg4.(pg2)

pc6 pc1 * (pc5 / pc2)

DO WHILE .T.

pc3 2 * pc2 - 1

pc4 pc4 / 2

pc8 pc3 - pc2

pc9 pg1 + pc4

pc10 2* pc4

FOR is 1 TO pc8

pc5 pc5 + &pg4.(pc9)

pc9 pc9 + pc10

NEXT

pc7 pc1 * (pc5 / pc3)

IF ABS (pc6 - pc7) < pg3 .AND. pc3 > 5

EXIT

ENDIF

pc2 pc3

pc6 pc7

ENDDO

ENDIF

RETURN pc7

// ---------------------

Примечания:

1. В приведенном примере вызов подпрограммы для вычисления значения подынтегральной функции из стандартной подпрограммы производится с использованием макропеременной &pg4.(pg1), где & - операция макроподстановки, pg4 - макропеременная, точка (.) является макроразделителем и используется для маркировки конца макропеременной и отделения ее от примыкающего текста в выражении, pg1 - аргумент, который передается из стандартной подпрограммы в подпрограмму для вычисления значения подынтегральной функции. В процессе выполнения стандартной подпрограммы содержимое макропеременной компилируется макрокомпилятором и выполняется. При этом скомпилированный код не сохраняется. 2. В приведенном примере вызов подпрограммы для вычисления значения подынтегральной функции может быть заменен исполнением блока кода. Например, в основной программе переменной bBlock присвоен блок кода

bBlock := { | x | MyFunc(x) },



где MyFunc - имя подпрограммы для вычисления значения подынтегральной функции, x - формальный параметр блока кода. При вызове стандартной подпрограммы SPVM983 из основной программы в качестве четвертого аргумента указывается переменная bBlock. В этом случае в стандартной подпрограмме вместо макропеременной &pg4.(pg1) используется функция EVAL() для выполнения блока кода. В частности, оператор

pc5 &pg4.(pg1) + &pg4.(pg2)

заменяется оператором

pc5 EVAL(pg4, pg1) + EVAL(pg4, pg2),

оператор

pc5 pc5 + &pg4.(pc9)

заменяется оператором

pc5 pc5 + EVAL(pg4, pc9),

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



Литература

1. Фихтенгольц Г.М. Основы математического анализа, т.1. 5-е изд. -М.: Наука, 1964. - С.440

Размещено на Allbest.ru

...