Исследование точности вычислений площади криволинейной фигуры различными численными методами

Муниципальное бюджетное общеобразовательное учреждение  

«Гимназия №75 Московского района города Казани»

Секция: информатика и ИКТ

Исследовательская работа

Исследование точности вычислений площади криволинейной фигуры различными численными методами

Бубнов Максим,  9 класс

Научный руководитель: Домрачева И. Н., учитель информатики гимназии №75

Казань, 2010

С О Д Е Р Ж А Н И Е

1. О площадях криволинейных фигур                                                                        

2. Постановка задачи                                                                                                

3. Методы вычисления площади криволинейной трапеции                                        

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

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

3.3. Метод Симпсона                                                                                                

4. Описание метода решения задачи                                                                        

5. Описание алгоритма решения задачи                                                                

6. Текст программы                                                                                                

7. Результаты работы программы                                                                        

8. Анализ точности вычислений                                                                                

9. Выводы                                                                                                                

10. Список использованных источников:                                                                

11. Приложение                                        

О площадях криволинейных фигур

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

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

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

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

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

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

        Для написания программы был использован Турбо Паскаль -  один из наиболее распространённых языков программирования 80-90х годов, поддерживающий самые современные методологии проектирования программ (нисходящее, модульное проектирование, структурное программирование), позволяющий решать широкий класс задач и автоматизировать процесс вычислений.

Постановка задачи

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

        Задачи:

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

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

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

- построить график функции f(x) на заданном интервале [a,b];

- провести исследование точности вычислений различными методами и определить наиболее эффективный метод;

- результат исследования вывести на экран с текстовыми комментариями.

Методы вычисления площади криволинейной трапеции

Криволинейная трапеция – фигура, ограниченная осью абсцисс, графиком заданной функции f(x), и вертикальными прямыми x=a, x=b.

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

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

1. Весь участок [a,b] делим на n равных отрезков с шагом h=(b-a)/n. 
2. Определяем значение yi  функции f(x) в каждой части деления, т.е.

3. В каждой части деления  функцию f(x)  заменяем прямой, параллельной оси OX. В результате вся функция на участке [a,b] заменяется ломаной линией.
4. Для каждой части деления определяем площадь Si частичного прямоугольника, как произведению высоты на основание.
5. Суммируем эти площади. Приближенное значение площади равно сумме площадей частичных прямоугольников.

   Sn = f ( x 1 )* x 1 + f ( x 2 )* x 2 + … f ( x n )* x n .

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

Рис. 1.  Метод левых прямоугольников

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

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

Точность каждого метода прямоугольников имеет порядок h.

Алгоритм вычисления площади построим в виде итерационного процесса поиска с автоматическим выбором шага. На каждом шаге будем уменьшать приращение аргумента в два раза, то есть увеличивать число шагов n в два раза. Выход из процесса поиска организуем по точности вычисления площади. Начальное число шагов n=2. Схема алгоритма методов прямоугольников представлена на рис.3.

Рис. 3.  Схема алгоритма метода прямоугольников (с автоматическим выбором шага)

Условные обозначения:

a,b - концы интервала,

e - заданная точность,

с=0 - метод левых прямоугольников,

с=1 - метод правых прямоугольников,

S1 - значение площади на предыдущем шаге,

S - значение площади на текущем шаге.

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

Словесный алгоритм метода трапеций:

1. Интервал [a,b] делим на n равных частей с шагом h=(b-a)/n.
2. Вычисляем значение функции в каждой узловой точке  yi=f(xi),

         причем х0 =а   и  хn =b.

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

Найдем площади Si частичных трапеций:

где S1= ((f(x0)+f(x1))*h)/2

       S2 = ((f(x1)+f(x2))*h)/2

       S3=((f(x2)+f(x3))*h)/2 …

       Sn=((f(xn-1)+f(xn))*h)/2

Приближенное значение площади  равно

Схема алгоритма метода трапеций представлена на рис.4.

Рис. 4  Схема алгоритма метода трапеций (с автоматическим выбором шага)

Чем на большее число частей мы разобьем отрезок [a,b], тем точнее будет результат. Точность метода трапеций имеет порядок h2.

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

        Если n=1, то заданная функция заменяется прямой линией, т.е. фактически получается метод трапеций. Если же взять n=2,  получаем  метод Симпсона.

        Идея метода исходит из того, что на частичном промежутке дуга некоторой параболы в общем случае теснее прилегает к кривой y=f(x), чем хорда, соединяющая концы дуги этой кривой, и поэтому значения площадей соответствующих элементарных трапеций, ограниченных “сверху” дугами парабол, являются более близкими к значениям площадей соответствующих частичных криволинейных трапеций, ограниченных сверху дугой кривой y=f(x), чем значения площадей соответствующих прямолинейных трапеций.

В методе Симпсона в каждой части деления заданная функция заменяется квадратичной параболой a0x2+a1x+a2. В результате вся кривая заданной функции на участке [a,b] заменяется кусочно-непрерывной линией, состоящей из отрезков квадратичных парабол. Приближенное значение площади S равно сумме площадей под квадратичными параболами.

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

Lk=2h.

В результате количество частей деления N2=n/2. Тогда n в методе Симпсона всегда четное число.

Определим площадь S1 на участке [x0, x2]

Площадь S1  на участке [x0, x2]определяется по формуле:

Неизвестные коэффициенты квадратичной параболы а0, а1, а2 определяются из условия прохождения параболой через три узловых точки с координатами (x0y0), (x1x1), (x2y2).

На основании этого условия строится система линейных уравнений:

Решая эту систему, находятся коэффициенты параболы.

В результате имеем: S1=h/3*(y0+4y1+y2)

Для участка [x2, x4]:. S2=h/3*(y2+4y3+y4)

Для участка [xi-1, xi+1]: Sk=h/3*(yi-1+4yi+yi+1), где k=(i+1)/2

Суммируя все площади Si под квадратичными параболами, получим формулу по методу Симпсона:

Где N2 - количество частей деления.

Схема алгоритма метода Симпсона представлена на рис.6.

Рис. 6.  Схема алгоритма Симпсона (с автоматическим выбором шага)

        Геометрический смысл формулы Симпсона очевиден: площадь криволинейной трапеции, ограниченной графиком функции f(x) на отрезке [a, b] приближенно заменяется суммой площадей фигур, лежащих под параболами (прямыми).

        Таким образом, отрезок [a, b] разбивается на n=2m частей x0 =a, x1 =a+h, ..., xn =b с шагом h=(b-a)/n. Вычисляются значения yi  = F(xi ) функции в точках xi  и находится значение площади по формуле Симпсона.

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

Если Rn  > e, то количество точек разбиения удваивается. Значение суммы 2(y1 +y2 +...+y2m-1 ) сохраняется, поэтому для вычисления площади при удвоении количества точек разбиения требуется вычислять значения yi  лишь в новых точках разбиения.

        Когда функция сложная, отрезок [a, b] разбивается на  n  частей  и  к каждому из отрезков применяется выше изложенный алгоритм.

Точность метода Симпсона имеет порядок (h3/h4), т.е. на два порядка выше точности метода трапеций.

Описание метода решения задачи

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

2) Задать количество точек, на которые будет делиться отрезок.

3) Ввести функцию f(x).

4) Ввести значение погрешности.

5) Вычислить площадь методом прямоугольников.
6) Вычислить площадь методом трапеций.
7) Вычислить площадь методом Симпсона.

8) Сравнить полученные результаты и сделать выводы.

9) Вывести график функции на экран с учётом масштаба.

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

1) Функция f - вычисляет значение  функции в заданной точке.

2) Функция pramoyg вычисляет площадь методом прямоугольников.
3) Функция trap - вычисляет площадь методом трапеций.
4) Функция simpson - вычисляет площадь методом Симпсона;
5) Процедура norm - вычисляет порядок числа, необходимый для построения графика функции с учётом масштаба.

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

Описание алгоритма решения задачи

Последовательность решения поставленной задачи

1. Начало программы

2. Запрос на ввод значений А и В.
3. Ввод значений А и В с клавиатуры.

4. Запрос на ввод точности вычислений eps.
5. Ввод точности вычислений eps.
7. Установка начального значения счётчика отрезков, равным 3.
8. Вычисление начального значения функции методом трапеций.
9. Запоминание предыдущего значения функции, вычисленного методом трапеций, увеличение значения числа отрезков на 2, вычисление следующего значения функции методом трапеций.
10. Проверка условия: абсолютное значение разности текущего и предыдущего значений функций меньше чем eps, если да, то выход из цикла, если нет, то переход на пункт 9.
11. Вывод результатов, полученных при вычислении площади методом трапеций на экран.

12 Установка начального значения счётчика отрезков, равным 3.
13. Вычисление начального значения функции методом прямоугольников.
14. Запоминание предыдущего значения функции, вычисленного методом прямоугольников, увеличение значения числа отрезков на 2, вычисление следующего значения функции.
15. Проверка условия: абсолютное значение разности текущего и предыдущего значений функций меньше чем eps, если да, то выход из цикла, если нет, то переход на пункт 14.
16. Вывод результатов, полученных при вычислении площади методом прямоугольников на экран.

17. Установка начального значения счётчика отрезков равным 3.

18. Вычисление значения начального значения площади методом Симпсона.
19. Запоминание предыдущего значения функции, вычисленного методом Симпсона, увеличение значения числа отрезков на 2, вычисление следующего значения функции методом Симпсона.

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

21. Вывод результатов, полученных при вычислении интеграла методом Симпсона на экран.

22. Конец программы.

Текст программы

program tr_s;
var Eps:real; a,b:real; { Границы отрезка }
r,r2:real; { Предыдущее и текущее приближенные значения функции}
n:integer; { Счетчик }
function f(x:real):real;
begin
f:=1/(x*ln(x)*0.43429);
end;
{ Метод трапеций }
function trap(a,b:real;n:integer):real;
var
s:real; { Полученная сумма }
h:real; { Шаг }
m:integer; { Счетчик }
begin
h:=(b-a)/(n-1); { Определяется шаг }
s:=(f(a)+f(b))/2; { Начальное значение суммы }
for m:=1 to n-2 do s:=s+f(a+m*h); { Суммирование остальных элементов}
trap:=s*h; { Возвращается значение площади }
end;

function pramoyg(a,b:real;n:integer):real;

var

s:real; {Полученная сумма }

h:real; {Шаг}

m:integer; {Счётчик}

begin

h:=((b-a)/n); {Определяется шаг}

s:=(f(a)); {Начальное значение суммы}

for m:=1 to n-1 do

begin

s:=s+f(a)*h; {Суммирование остальных элементов}

a:=a+h;

end;

pramoyg:=s; {Возвращается значение функции}

end;
{ Метод Симпсона }
function simpson(a,b:real;n:integer):real;
var
s:real; { Сумма } h:real; { Шаг } m:integer; { Счетчик } mn:integer; { Очередной множитель }
begin
h:=(b-a)/(n-1); { Рассчитывается шаг }
s:=f(a)+f(b); { Начальное значение шага }
mn:=4; { Первый множитель - 4 }
{ Суммирование остальных элементов }
for m:=1 to n-2 do begin
s:=s+mn*f(a+h*m);
if (mn=4) then mn:=2 else mn:=4;{ Изменение множителя 2<>4 }
end;
simpson:=s*h/3; { Возвращается вычисленное значение }
end;

{ Процедура вычисления порядка числа }
procedure norm(a:real);
var n:real;
begin
{ Если число слишком мало - возвращается ноль }
if (a<0.00001) then n:=0
else begin
{ Если число меньше единицы }
if (a<1) then begin
n:=1;
repeat
a:=a*10; n:=n/10;
until (trunc(a)<>0);
end else begin
{ Если число больше единицы }
n:=1;
repeat
a:=a/10; n:=n*10;
until (trunc(a)=0);
end;
end;
a:=n;
end;

{ Основная программа }
begin
{ Ввод границ отрезков }
write(' Введите A,B: '); readln(a,b);

Writeln(‘Введите значение точности вычисления’); Readln(‘eps’)
{ Вычисляется интеграл по методу трапеций }
n:=3;
r:=trap(a,b,n); { Начальное значение }
repeat
r2:=r; { Запоминается предыдущее значение }
n:=n+2; { Увеличивается количество шагов }
r:=trap(a,b,n); { Рассчитывается новое значение }
until (abs(r-r2)<0.001);{ Повторяется до достижения необходимой точности }
{ Вывод результатов }
writeln(‘ Результат по методу трапеций равен: ',r:6:3);
writeln(' для получения необходимой точности интервал был разбит на');
writeln(n,' отрезков');

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

n:=3;

r:=pramoyg(a,b,n); { Начальное зачение }

repeat

r2:=r; { Запоминается предыдущее значение }

n:=n+2; { Увеличивается количество шагов }

r:=pramoyg(a,b,n); { Рассчитывается новое значение }

until (abs(r-r2)

{ Вывод результатов }

Writeln;

writeln(‘ Результат по методу прямоугольников равен: ',r:6:3);
writeln(' для получения необходимой точности интервал был разбит на');
writeln(n,' отрезков');

{ Вычисляется интеграл по методу Симпсона }
n:=3;
r:=simpson(a,b,n); { Начальное значение }
repeat
r2:=r; { Запоминается предыдущее значение }
n:=n+2; { Увеличивается количество шагов }
r:=simpson(a,b,n); { Рассчитывается новое значение }
until (abs(r-r2)<0.001);{ Повторяется до достижения необходимой
точности }
{ Вывод результатов }
writeln;
writeln(' Резльтат по методу Симпсона равен: ',r:6:3);
writeln(' для получения необходимой точности интервал
был разбит на ');
writeln(n,' отрезков');
end.

Результаты работы программы

Таблица 1. Результаты вычислений

Анализ точности вычислений

Таблица 2. Погрешность вычислений

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

Метод трапеции является наиболее простым методом приближённого вычисления площади криволинейной трапеции, но требует довольно много итераций. Более совершенным является метод Симпсона, использующий для вычислений почти в 2 раза меньше количества интервалов. Например, для функции 1/x при погрешности 0,001 для метода Симпсона требуется 59 разбиений, а для метода трапеций 95. При точности вычислений 0.0001 метод прямоугольников требует 683 разбиения, тогда как метод Симпсона – всего 103, а метод трапеций – 205. То есть метод парабол сходится значительно быстрее метода трапеций, тогда как с точки зрения техники вычислений оба метода одинаковы. Метод прямоугольников является наиболее затратным и неточным. Но для некоторых функций (например, с бесконечно большой плоскостью) этот метод эффективен.

        Метод Симпсона дает результат высокой точности для параболы и фигур, близких по кривизне к параболе. Формула Симпсона на частичном отрезке  имеет точность О(h5), а на всем отрезке - O(h4). Например, для функции y=cos(x*x) при точности вычислений 0.1 метод Симпсона требует 215 разбиений, метод трапеций – 127, а метод прямоугольников – 71. Методы трапеций и прямоугольников дают практически одинаковые результаты, расхождение значений составляет 0,065, а с методом Симпсона эта разность более 1.

Выводы

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

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

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

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

Список использованных источников

1. Белецкий Я. Турбо Паскаль с графикой для персональных компьютеров перевод с польского Д.И.Юренкова. -М.: Машиностроение , 1991. - 320 с.
2. Сергиевский М.В., Шалашов А.В. Турбо Паскаль 7.0; язык, среда программирования. -М: Машиностроение.-1994,-254 с.ил.
3. Справочник по процедурам и функциям Borland Pascal 7.0. - Киев: Диалектика, 1993. - 272 с.
4. Самарский А.А, Гулин А.В. Численные методы.М.:Наука,1989. - 430 с.

5. http://wikipedia.com/

6. www.alport.lg.ua