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

Московский Авиационный Институт (Государственный Технический Университет) Расчетно-графическая работа по информатике на тему «Табулирование функции» Москва 2008 Содержание: Содержание: 2 Задание 3 Анализ задания. 4 Обоснование и описание вычисление корня нелинейного уравнения методом бисекции (половинного деления): 5 Таблица обозначения переменных главной программы.

6 Схемы алгоритмов 7 Главная программа: 7 Функция mfunc: 8 Функция func: 8 Функция sign: 8 Процедура Bisect: 9 Программа Pascal. 10 Результаты. 12 Задание Разработать схему алгоритма вычисления таблицы значений функции при заданных значениях аргумента Х и параметра А. Параметр В принимает значение, численно равное интегралу.

Аргумент 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) задачи уточнения одним из известных м嬬то¬дов най¬ден¬ного корня  с за¬дан¬¬¬ной погрешностью . Предположим теперь, что найден от¬ре¬зок [а, b] тବ¬кой,

что F(а)F(b) < 0. Тогда, согласно т嬬о¬ре¬ме Боль¬ца¬но-Коши, внут¬ри от¬рез¬ка [а, b] су¬щес¬т¬ву¬ет точка &#61560;, в которой F(&#61560;) = 0. Дବлее не¬об¬хо¬димо убе¬дить¬ся, что най¬ден¬¬ная точка &#61560; единс¬т¬вен¬ная на от¬рез¬ке [а, b]. О䬬ним из методов яв¬ляется де¬ле¬ние отрезка на не¬сколь¬¬¬ко частей, на¬пр謬мер на че¬ты¬ре, и проверка на кон¬¬цах каждого из от¬рез¬ков зна¬ка функции.

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

Этот процесс по¬стро¬е¬ния п¬сл嬬два¬тель¬нос¬ти вло¬жен¬ных отрезков по¬зво¬ляет на鬬¬ти нуль функ¬ции (F(х) = 0) с лю¬бой за¬дан¬ной точ¬¬¬ностью. Опишем подробно один шаг итерации. Пусть на k-м ша¬ге найден отрезок [аk , bk], на концах кто¬рого F(х) меняет знак. Заметим, что обязательно [аk, bk] &#61646; [а, b]. Разделим те¬перь отрезок [аk, bk] пополам и вы¬д嬬лим

F(&#61560;), где &#61560; - се¬ре¬д謬на [аk , bk]. Здесь воз¬мо欬ны два слу¬чая: первый, ког¬да F(&#61560;) = 0, тогда мы го¬ворим, что ко¬рень найден; вто¬рой, ког¬да F(&#61560;) &#61625; 0, тог¬да сра⬬ниваем знак F(&#61560;) с F(аk) и F(bk) и из двух плвин [аk, &#61560;] и [&#61560;, bk] вы¬бираем ту, на концах ко¬то¬рой функ¬ция меняет свой знак.

Та¬ким образом, аk = а , bk = &#61560;, если F(&#61560;)F(аk) < 0 , и аk = &#61560; , bk = b, ес¬ли F(&#61560;)F(bk) < 0. При заданной точности &#61541; деление пополам про¬дол¬жа¬ют до тех пор, пока длина отрезка не ста¬нет меньше &#61490;&#61541;, тогда координата середины псле䬬¬¬него на鬬¬денного от¬резка и есть значение кор¬¬ня тре¬бу¬е¬мой точ¬ности.

Метод дихотомии — простой и надежный ме¬тод п¬ис¬ка простого корня уравнения F(х) = 0. Он схо¬дит¬ся для лю¬бых непрерывных фунꬬций F(х), в том чис¬ле и н嬬диф¬фе¬рен¬ци¬ру¬е¬мых. Недостатки метода: 1) проблема определения отрезка, на ко¬то¬ром фунꬬция ме¬няет свой знак (как правило, это отдельная вы¬чис¬ли¬тель¬ная задача, на¬и¬бо¬лее слож¬ная и трудоемкая час¬ть ре¬ше¬ния);

2) если корней на выделенном отрезке не¬сколь¬ко, то нельзя заранее сказать, к какому из них со鬬¬дет¬ся про¬цесс; 3) не применим к корням четной крат¬нос¬ти; 4) для корней нечетной, но высокой кратности м嬬¬тод неустойчив, дает большие ошибки; 5) медленно сходится. Для достижения &#61541; н嬬оᬬхо¬димо выполнить N итераций , т.е. для по¬лу¬ч嬬ния 3 верных цифр (&#61541; = 0.0005) на¬до вы¬полнить около 10

ит嬬раций, ес¬ли отрезок имеет единичную длину. Программа, по которой можно вычислить кор¬ни ме¬тодом дихотомии, построена по сле¬ду¬ю¬щ嬬му ал¬го¬рит¬му: Шаг 1. Определить входные параметры А, В, ЕРS. Шаг 2. Присвоить: А1 &#61660;&#61472;А; В1 &#61660;&#61472;В; К &#61660; 0. Шаг 3. Присвоить: Х1 &#61660;

А1; Х2 &#61660; В1; К &#61660; К + 1; Х3 &#61660;&#61472;(В1+А1)/2. Шаг 4. Если F(Х1) &#61620; F(Х3) < 0, то перейти на шаг 5 ина¬че на шаг 7. Шаг 5. Присвоить: В1 &#61660; Х3. Шаг 6. Если | А1 - В1| < ЕРS, то перейти на шаг 10 инବче на шаг 3. Шаг 7. Если F(Х2) &#61620; F(Х3) < 0, то перейти на шаг 8 инବ¬че на шаг 11.

Шаг 8. Присвоить: А1 &#61660;&#61472;Х3. Шаг 9. Перейти на шаг 6. Шаг 10. Печать: Х3 - корень уравнения; К - ко¬ли¬чес¬тво ит嬬¬раций. Шаг 11. | А1 - В1| / 2 - погрешность решения. Шаг 12. Конец программы. Это наиболее простое решение задачи, но не сବмое эф¬фективное. Эффективность можно по¬вы¬сить, если: 1) заменить произведения

F(х1)&#61655;F(х3) и F(х2)&#61655;F(х3) на ис¬¬поль¬зование функции sign(x). 2) определить процедуру-функцию, вы¬чис¬ля¬ю¬щую F(х) толь¬¬ко один раз; 3) заменить в операторе цикла медленный оператор (А+В)/2 на более быстрый (А+В)*0.5. Таблица обозначения переменных главной программы. Обозначение в задании Обозначение В алгоритме Наименование M M число значений аргумента, не зависящих друг от друга, целый

тип X Х Массив аргументов, вещественный тип An An начальное значение параметра, вещественный тип Da Da шаг изменения параметра A, вещественный тип N N число значений параметра, изменяемого от значения An с шагом Da, целый тип Y Значение функции, вещественный тип maxit На¬и¬боль¬¬шее раз¬ре¬шен¬ное количество ите¬раций; целый тип.

B B Значение определенного интеграла, вещественный тип &#949; Eps Заданная погрешность вычисления корня нелинейного уравнения, вещественный тип с, d c, d Левый и правый пределы отрезка, на котором вычисляется корень, вещественный тип Схемы алгоритмов В соответствие с принципами структурного программирования каждый функциональный законченный фрагмент программы оформлен в виде подпрограммы. В результате программа включает главною программу и

набор подпрограмм, предназначенных соответственно для вычисления значения функции, вычисления корня нелинейного уравнения. Главная программа: Функция 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