Основы программирования (Иванова Г.С. Основы программирования), страница 11

Практикум. Точность решения задачвычислительной математикиВычислительная математика занимается рассмотрением численных ме­тодов вычисления значений функций, решения алгебраических и трансцен­дентных уравнений, систем уравнений, интерполяции функций и т.д. К тойже группе задач относится и задача о нахождении суммы ряда, рассмотрен­ная в предыдущем параграфе. Естественно в рамках одного параграфа невоз­можно рассмотреть алгоритмы решения всех задач данного раздела матема­тики, но попробуем на примере двух из них продемонстрировать проблемыдостижения заданной точности результатов, которые возникают при реше­нии задач этой области.Пример 3.6. Разработать программу вычисления определенного интег­рала функции f(x) на заданном отрезке [а, Ь] методом прямоугольников.Определенный интеграл вычисляется как площадь фигуры, ограничен­ной графиком функции, отрезком оси абсцисс и вертикальными линиями,проходящими через границы отрезка.

Метод прямоугольников предполагает,что площадь определяется как сумма площадей п прямоугольников, основа­нием которых является п-я часть отрезка [а,Ь], а стороной - значение функ­ции на одном из концов отрезка (например, левом, как на рис. 3.15).ИтакSl= f(xi)x5 + f(x2)x6 + f(x3)x5 + ...+ f(x„)x5 = 5xZ f(xi),i=lгде 5 = (b-a) / n.Значение определенного интеграла SI,определенное по данной формуле, является неточным, причем с увеличением количества от­резков п точность значения S1 увеличивается.Считают, что значение определено с заданнойточностью, если абсолютная величина разно­сти двух последовательных приближений ре­зультата, полученных при разных значенияхп, не превышает заданной погрешности.Для определения момента достижениязаданной точности необходимо организоватьОаb Xп=6Рис.

3.15. Вычислениеопределенного интеграламетодом прямоугольника63Часть L Основы алгоритмизации и процедурное программирование/(Начало j©/Ввод у/a,b,eps /S1:=0Sl:=10''r^i:=l,n,lVnn:=5S2:=S1n:=2n1d:=(b-a)/nx:=a^Рис. 3.16. Схема алгоритма вычисления определенного интегралаеще один - внешний цикл, в котором значение п будем увеличивать, напри­мер, в два раза, и рассчитывать значение S1, предварительно сохранив пре­дыдущее значение S1 в переменной S2. Цикл должен завершаться, когда аб­солютная величина разности двух приближений S1 и S2 станет меньше s. Ис­ходное значение S2 примем достаточно большим, чтобы цикл не завершилсяпри лервой проверке условия.Схема алгоритма вычисления определенного интеграла для функцииf(x) = х^ - 1 приведена на рис.

3.16.Ниже приведена программа, реализующая данную схему алгоритма.Program ex;Var а, b,Sl,S2,d, eps,x:real:n, i.'longint;BeginWriteLnCВведите a, b и эпсилон:');ReadLnfa, b, eps);S1:=1E+10;n:=5;643. Управляющие операторы языкаrepeatS2-S1;п:=п*2;d:^(b'a)/n;х:=а;S1-0;for i:=l to п dobeginS]:=SI+x*X'l;x:=x+d;end;SJ:=SJ*d;until abs(Sl-S2)<eps:WriteLnCI=\Sl:10:6);EndПри выполнении программы с разными значениями погрешности eps иотрезком [0,2] получаем разные приближения результата I (табл. 3.2). Точноезначение определенного интеграла равно 2/3. Определим абсолютную и от­носительную погрешности результата.В данном случае абсолютная погрешность результата всегда будетменьше eps, так как это определяется самим методом.

Последнее верно недля любого метода.Пример 3.7. Разработать программу, которая определяет корень непре­рывной функции f(x) на заданном отрезке [а, Ь] методом хорд.Метод работает в том случае, если значения функции на концах отрезкаразных знаков, т.е. если функция только касается оси абсцисс, то ее кореньданным методом определить нельзя. Если на заданном отрезке у функции не­сколько корней, то, используя данный метод, найдем один из них.Метод хорд заключается в следующем. Значения функции на концах от­резка соединяют отрезком прямой.

В точке пересечения этой прямой с осьюабсцисс определяют значение функции. Если это значение меньше заданнойпогрешности функции, то абсцисса точки пересечения считается корнемТ а б л и ц а 3.2epsпIAl5i,%6400.6604200.0060.90.00151200.6658850.00020.060.0001409600.6665690.000040.0120.01165Часть 1. Основы алгоритмизации и процедурное программированиефункции, иначе корень функцииищется на том отрезке из двух полу­ченных, для которого значенияфункции на концах разных знаков.На рис.

3.17 показана графическаяинтерпретация метода.На рис. 3.18 представлена схе­ма алгоритма программы для функ­ции f(x) = х^ - 1.Полученный алгоритм являет­ся не структурным, так как цикл,который в нем использован, не яв­ляется ни циклом-до, ни цикломпока. Для преобразования алгорит­ма в структурный используем при-Рис. 3.17. Нахождение корняметодом хордГ Начало j//Вводa,b,epsУ/fa:=a*a-lfb:=b*b-lнет-^^2-<fa*fb>07' "Метод неприменим(КонецjРис.

3.18. Схема алгоритма нахождения корня методом хорд66Часть L Основы алгоритмизации и процедурное программированиеРис. 3.19. Соотношение Лу и А^ в зависимости от вида функции:а ~ угол наклона производной в корне больше 45**; б - меньше 45**функции. Однако, если бы производная функции в точке корня была близкак нулю, это соотношение было бы обратным (рис. 3.19), и, следовательно,метод оказался бы неприменимым.В качестве альтернативы можно предложить алгоритм, в котором выходиз цикла вычислений выполняется, когда разность между двумя соседнимиприближениями значений корня становится меньше заданного eps (по анало­гии с примером 3.6).

Однако этот алгоритм был бы не применим для поискакорня, если угол наклона производной функции в корне больше 45°.Следовательно, применяя тот или иной методы вычислительной матема­тики, необходимо проверять обеспечение точности получаемых результатов.Задания для самопроверкиЗадание 1. Разработайте программу вычисленияarctg X = X - х^/З + х5/5 - х^/7 + ...при заданном значении х и точности 10*^, 10"^. Оцените количество итераций вкаждом случае.Задание 2.

Разработайте программу, которая определяет сумму первых к чиселпоследовательности Фибоначчи. Последовательность задана закономF, = l,Fn = F.п-1 + F,п-2для п > 2.Задание 3. Разработайте программу вычисления длины кривой на отрезке [0,4].Кривая задана уравнением у=х^^. Вычисления выполните с точностью 10'^, Ю""*.Оцените количество итераций в каждом случае.Задание 4. Разработайте программу, которая определяет, является ли введенноечисло п простым.__,,,Задание 5.

Разработайте программу вычисления:683, Управляющие операторы языкаем, рассмотренный в примере 3.3. А именно: повторяем в конце тела циклаоператоры, выполняемые в начале цикла до условия, и организуем цикл, какцикл-пока. Поскольку выход из цикла-пока осуществляется по нарушениюусловия цикла, придется также изменить условие цикла. Программа, реали­зующая структурный вариант алгоритма, имеет следующий вид:Program ex;Var a,bjjajb,eps,x:real;BeginWriteLnCBeedume a, b и эпсилон: *);ReadLn(a, b, eps);fa:^a*a-l;Jb:^b''b'l;iffa*fb>-0 then WriteLn(*Метод не пргшеним. *)elsebeginx:=(b'a) *abs(fa)/abs(fa'fb)+a;while abs(f)>-eps dobegin{условие выхода из цикла}iffaj<0 thenbegin b:=x; Jb:=f; endelse begin a:=x; fa:=f; end;х:-(Ыа) *abs(fa)/abs(fa'fb)'^a;f:-x*x-l;end;WriteLnCnpu x= \ x:9:6, ' y= \ f:10:8);end;EndМеняя значение погрешности, получим разные значения корня и значе­ния функции в корне (табл.

3.3). Зная точное значение корня х=1, определимпредельную абсолютную и относительную погрешности в каждом случае.Из таблицы видно, что погрешность корня меньше погрешности значенияТ а б л и ц а 3.3eps = AyXУАх5х, %0.010.997260-0.005471950.0030.30.0010.999695-0.000609480.000310.030.00010.999966-0.000067740.0000340.003673, Управляющие операторы языка3.6. Неструктурные алгоритмы и их реализацияС точки зрения теории программирования неструктурные оператор ипроцедуры передачи управления являются «лишними», так как любой алго­ритм может быть преобразован в структурный и реализован без них. Однакоинтуитивно построенные алгоритмы, как это видно на ттредыдущих приме­рах, часто получаются неструктурными, и для их реализации может потре­боваться использование неструктурных вариантов передач управления.

Про­анализируем достоинства и недостатки реализации неструктурных алгорит­мов.Для организации неструктурных передач управления используют опера­тор безусловной передачи управления goto и специальные процедуры.Оператор безусловной передачи управления. Этот оператор передаетуправление в точку, определенную специальной меткой (рис.

3.20).Все метки в программе должны быть описаны инструкцией объявленияметок label (рис. 3.21). Метка ставится перед любым выполняемым операто­ром программы, причем на один оператор можно поставить несколько меток.Неструктурную передачу управления таюке осуществляют следующиепроцедуры:Break - реализует выход из цикла любого типа;Continue - осуществляет переход на следующую итерацию цикла,игнорируя оставшиеся до конца тела цикла операторы;Halt (<код, завершения>) - осуществляет выход из программы, возвра­щая операционной системе заданный код завершения. Считается, что про­грамма завершилась нормально, если код завершения равен нулю.

Возвраще­ние кода завершения, отличного от нуля, обычно означает,что программа за­вершена по обнаружении каких-либо ошибок. Коды завершения назначают­ся программистом, а информация о них помещается в программную доку­ментацию;Exit- осуществляет выход из подпрограммы (см. главу 5). Если проце­дура использована в основной программе, то она выполняется аналогичноHalt.-*/^ label Л - j-*/goto V-H МеткаРис.