Табулирование функции и вычисление корня нелинейного уравнения методом бисекции на языке Paskal

Московский Авиационный Институт

(Государственный Технический Университет)

Расчетно-графическая работа по информатике

на тему «Табулирование функции»

Москва 2008

Содержание:

Задание

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

Аргумент X:

M - число значений аргумента, не зависящих друг от друга;

Параметр А:

An – начальное значение параметра;

Da – шаг изменения параметра;

N – число значений параметра, изменяемого от значения An с шагом Da;

B – корень нелинейного уравнения:

,

вычисленный с погрешностью ?

Табулируемая функция:

Анализ задания.

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

где B - параметр функции, принимающий значение корня нелинейного уравнения:

,

который вычисляется с погрешностью Eps половинного деления.

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

Список входных параметров: c,d, Eps, maxit

c, d - левый и правый пределы отрезка, на котором вычисляется корень; тип - вещ.

Eps - заданная погрешность нахождения корня; тип- вещ.

Maxit - на­и­боль­­шее раз­ре­шен­ное количество ите­раций; тип- целое.

Выходные параметры: B

B – корень уравнения; тип вещественные.

k - количество вы­пол­нен­ных ите­­ра­ций; тип- целое.

Входными данными в данной задаче являются: M - число значений аргумента, не зависящих друг от друга, M значений Х, An – начальное значение параметра, Da – шаг изменения параметра, N – число значений параметра, изменяемого от значения An с шагом Da;

Для решения нелинейного уравнения методом биссекции (половинного деления) используются следующие параметры: c, d, погрешность вычисления Eps, Maxit - на­и­боль­­шее раз­ре­шен­ное количество ите­раций.

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

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

Обоснование и описание вычисление корня нелинейного уравнения методом бисекции (половинного деления):

В общем случае редко удается точно найти все кор­­­ни в алгебраических уравнениях, а если к то­му же ко­эф­фи­циенты в уравнении даны с по­греш­нос­тью, то во­прос о точном определении корней во­­­­об­ще теряет вся­кий смысл. Однако если пред­по­­­ло­­жить, что задано урав­нение типа F(x) = 0, то тог­­да без огра­ничения об­щ­нос­ти можно ут­вер­ж­дать, что F(х) име­ет корни, для ко­то­рых су­щес­т­ву­­ет ок­рест­ность , содержащая толь­ко один прос­­той ко­рень. Та­кой корень иногда на­зы­ва­ют изо­­­­ли­ро­ван­ны­м. В ре­зуль­тате общая задача на­хо­ж­де­ния кор­ней или ну­лей функции бу­­дет состоять из сле­ду­ю­­­щих этапов:

1. отделения корней, т.е. устано­вле­­ния ин­тер­ва­ла , где содержится один и толь­ко один ко­­рень урав­­нения;

2. задачи уточнения одним из известных ме­­то­дов най­ден­ного корня x с за­дан­­­ной погрешностью e.

Предположим теперь, что найден от­ре­зок [а, b] та­­­кой, что F(а)F(b) < 0. Тогда, согласно те­­о­ре­ме Боль­ца­но-Коши, внут­ри от­рез­ка [а, b] су­щес­т­ву­ет точка x, в которой F(x) = 0. Да­­лее не­об­хо­димо убе­дить­ся, что най­ден­­ная точка x единс­т­вен­ная на от­рез­ке [а, b]. Од­­ним из методов яв­ляется де­ле­ние отрезка на не­сколь­­­ко частей, на­при­­мер на че­ты­ре, и проверка на кон­­цах каждого из от­рез­ков зна­ка функции.

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

Опишем подробно один шаг итерации. Пусть на k-м ша­ге найден отрезок [а_k , b_k], на концах ко­­то­рого F(х) меняет знак. Заметим, что обязательно [а_k, b_k] ? [а, b]. Разделим те­перь отрезок [а_k, b_k] пополам и вы­де­­лим F(x), где x - се­ре­ди­­на [а_k , b_k]. Здесь воз­мож­­ны два слу­чая: первый, ког­да F(x) = 0, тогда мы го­ворим, что ко­рень найден; вто­рой, ког­да F(x)  0, тог­да срав­­ниваем знак F(x) с F(а_k) и F(b_k) и из двух по­­ло­­вин [а_k, x] и [x, b_k] вы­бираем ту, на концах ко­то­рой функ­ция меняет свой знак. Та­ким образом, а_k = а , b_k = x, если F(x)F(а_k) < 0 , и а_k = x , b_k = b, ес­ли F(x)F(b_k) < 0.

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

Метод дихотомии — простой и надежный ме­тод по­­­ис­ка простого корня уравнения F(х) = 0. Он схо­дит­ся для лю­бых непрерывных функ­­ций F(х), в том чис­ле и не­­диф­фе­рен­ци­ру­е­мых. Недостатки метода:

1. проблема определения отрезка, на ко­то­ром функ­­ция ме­няет свой знак (как правило, это отдельная вы­чис­ли­тель­ная задача, на­и­бо­лее слож­ная и трудоемкая час­ть ре­ше­ния);

2. если корней на выделенном отрезке не­сколь­ко, то нельзя заранее сказать, к какому из них сой­­­дет­ся про­цесс;

3. не применим к корням четной крат­нос­ти;

1. для корней нечетной, но высокой кратности ме­­­тод неустойчив, дает большие ошибки;

1. медленно сходится. Для достижения e не­­об­­хо­димо выполнить N итераций¹, т.е. для по­лу­че­­ния 3 верных цифр (e = 0.0005) на­до вы­полнить около 10 ите­­раций, ес­ли отрезок имеет единичную длину.

Программа, по которой можно вычислить кор­ни ме­­­­­тодом дихотомии, построена по сле­ду­ю­ще­­му ал­го­рит­му:

1. Определить входные параметры А, В, ЕРS.

1. Присвоить: А1 ? А; В1 ? В; К ? 0.

1. Присвоить: Х1 ? А1; Х2 ? В1; К ? К + 1; Х3 ? (В1+А1)/2.

1. Если F(Х1)  F(Х3) < 0, то перейти на шаг 5 ина­че на шаг 7.

1. Присвоить: В1 ? Х3.

1. Если | А1 - В1| < ЕРS, то перейти на шаг 10 ина­­че на шаг 3.

1. Если F(Х2)  F(Х3) < 0, то перейти на шаг 8 ина­­­че на шаг 11.

1. Присвоить: А1 ? Х3.

1. Перейти на шаг 6.

1. Печать: Х3 - корень уравнения; К - ко­ли­чес­тво ите­­­раций.

1. | А1 - В1| / 2 - погрешность решения.

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

Это наиболее простое решение задачи, но не са­­мое эф­фективное. Эффективность можно по­вы­сить, если:

1. заменить произведения F(х₁)F(х₃) и F(х₂)F(х₃) на ис­­поль­зование функции sign(x).

2. определить процедуру-функцию, вы­чис­ля­ю­щую F(х) толь­­ко один раз;

3. заменить в операторе цикла медленный оператор (А+В)/2 на более быстрый (А+В)*0.5.

Таблица обозначения переменных
главной программы.

Схемы алгоритмов

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

Главная программа:

Функция mfunc:



Список формальных параметров: x, a, b.

Список входных параметров:

a, b – параметры функции, тип вещественный.

x – аргумент функции, тип вещественный.

Функция func:

Функция sign:

Процедура Bisect:

Программа Pascal.

program RGR;

uses crt;

const c=0; d=8; eps=0.0001;

var b,a,An,Da:real;

x:array [1..100] of real;

i,j,m,n,k,maxit:integer;

function func(x:real):real;

begin

func:=exp(-x)-sqr(x-1);

end;

function mfunc(a,x,b:real):real;

begin

if x>1

then

mfunc:=sqr(x)/(a*x+b)

else

mfunc:=b*exp(a*x);

end;

function sign(x:real):integer;

begin

if x>=0

then

sign:=1

else

sign:=-1;

end;

procedure bisect (c,d,eps:real; maxit:integer; var X:real; var k:integer);

var C1,D1:real; X1,X2,X3:integer;

begin

X1:=sign(func(C));

X2:=sign(func(D));

C1:=C;

D1:=D;

repeat

inc(K);

X:=(C1+D1)*0.5;

X3:=sign(func(X));

if X3=0 then exit;

if abs(D1-C1)<(2*eps) then exit;

if (X1=X2) and (X2=X3) then exit;

if X1=X3

then

begin

C1:=X;

X1:=X3;

end

else

begin

D1:=X;

X2:=X3;

end;

until K>=maxIT;

end;

begin

write('Введите M: ');

readln(m);

for i:=1 to m do

begin

write('Введите x[',i,']: ');

readln(x[i]);

end;

write('Введите максимальное число итераций: ');

readln(maxit);

bisect(c,d,eps,maxit,b,k);

writeln('Проведено итераций: ',k);

writeln('B=',b:5:3);

write('Введите An, Da, N: ');

readln(An,Da,N);

writeln;

writeln('Таблица значений.');

for i:=1 to m do

begin

writeln;

writeln('x=',x[i]:5:3);

writeln;

a:=an;

for j:=1 to n do

begin

writeln(' A=',a:5:3,'; y=',mfunc(a,x[i],b):5:5);

a:=a+da;

end;

end;

readln;

end.

Результаты.

Введите M: 3

Введите x[1]: -1

Введите x[2]: 3

Введите x[3]: 5

Введите максимальное число итераций: 100

Проведено итераций: 17

B=1.478

Введите An, Da, N: 4 3 2

Таблица значений.

х=-1.000

А=4.000; y=0.02707

А=7.000; y=0.00135

х=3.000

А=4.000; y=0.66777

А=7.000; y=0.40040

х=5.000

А=4.000; y=1.16400

А=7.000; y=0.68535