П Р О Г Р А М М И Р О В А Н И Е И Т Е Р А Ц И О Н Н Ы Х Ц И К Л О В

Итерационным называется такой вычислительный процесс, для которого заранее неизвестно количество выполнений цикла; это количество зависит от конкретных значений исходных данных. Критерием окончания циклического процесса является выполнение некоторого заранее заданного условия.

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

Как правило, признаком окончания вычислений является достижение заданной точности:

где - максимально допустимая погрешность вычисления функции ;

- предыдущее и очередное значения функции .

Пример 1.Итерационная формула Ньютона для функции :

,

где - начальное приближение. В частности, для получим:

.

Рассмотрим действие формулы Ньютона для = 16; = 0.01 .

= 16 ;

= 0.5 * (16 + 16/16) = 8.5 ;

= 0.5 * (8.5 + 16/8.5) = 5.191176 ;

= 0.5 * (5.191176 + 16/5.191176) = 4.136664 ;

= 0.5 * (4.136664 + 16/4.136664) = 4.002257 ;

= 0.5 * (4.002257 + 16/4.002257) = 4.000005 .

Условие выполняется при n = 4. Следовательно, значение = 4.000005 есть значение искомой функции при = 16 с погрешностью не более = 0.01 .

а) б)

а) б)

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

В программе вместо исходных переменных будут использованы переменные y, yn.

Program Newton1;

Consteps = 0.00001;

Varx,y,yn : real;

Begin

Ввод и печать x

y:=x; yn:=x+2*eps;

If x>0 then

While abs(y-yn)>eps do

Begin

yn:=y;

y:=0.5*(yn+x/yn);

End;

Печать y

End.

Оператор "Ifx > 0 then" в программе Newton1 исключает прерывание программы из-за деления на нуль при x = 0 (если x = 0, то при первом выполнении цикла yn = y = 0).

Пример 2. Вычисление функции по ее разложению в ряд.

В Паскале, как и в других языках программирования высокого уровня, определены стандартные функции sin(x), cos(x) и др. Вполне очевидно, что вычисление этих функций производится по некоторым формулам, а не по таблицам значений. Одним из методов вычисления функций является разложение их в ряд, в частности, в так называемый ряд Маклорена (существуют и другие ряды, например, ряд Лорана, ряд Фурье, разложение по полиномам Чебышева и пр.). Программная реализация таких рядов сводится к организации итерационных циклов.

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

( 1 )

Как известно, n! = 1 × 2 × 3 × ... × n . Например, 5! = 1 × 2 × 3 × 4 × 5 = 120.

В частности, считают 1! = 1; 0! = 1 .

Тогда

Является очевидным, что при малых значениях аргумента (например, < 0.1), значение функции примерно равно первому члену ее разложения в ряд, т.е. значению самого аргумента .

Пусть . Тогда

0.5-0.020833+0.0002604-

- 0.00000155+...

При = 0.001 достаточно взять первые три члена разложения функции sin(x) в ряд. Тогда y = sin(0.5) = 0.4794 .

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

Обозначим члены ряда через . Тогда общий член ряда

( 2 )

Частная сумма, определяющая с некоторой погрешностью значение искомой функции , есть

…………………………..

( 3 )

Условие окончания вычислений (окончания итерационного цикла):

или, используя (3),

.

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

Например, при вычислении нужно выполнить действия

,

для вычисления - действия

.

Однако при вычислении уже были получены значения и 5! Поэтому при вычислении целесообразно использовать уже имеющееся значение :

Выведем формулу для общего случая вычисления .

Из формулы (2), подставив вместо значение , получим

.

Тогда

( 4 )

Формула типа (4), в которой для вычисления очередного члена числовой последовательности используется значение ее предыдущего члена , называется рекуррентной.

Для вычисления ряда (1) имеем следующие рабочие формулы:

Program MacLoren;

Const eps = 0.00001;

Var x,a,S,n : real;

Begin

Ввод и печать x

a:=x; S:=x; n:=0;

While abs(a)>eps do

Begin

a:=-sqr(x)*a/((2*n+2)*(2*n+3));

S:=S+a; n:=n+1

End;

Печать S

End.

Значение целочисленной переменной непосредственно входит в формулу для вычисления элемента . Чтобы исключить многочисленные преобразования integer ® real, в программе переменная объявлена вещественной.

Блок-схема вычислений:

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

Из существующих методов уточнения корня функции будем использовать наиболее простой - метод половинного деления.

Вычислим и . Поскольку на заданном интервале расположен лишь один корень функции, то .

Разделим исходный интервал пополам и определим

и .

Если , то передвинем левую границу к середине интервала, т.е. примем и . В противном случае к середине интервала сдвигаем правую границу: . Деление интервала пополам будем продолжать до тех пор, пока не будет выполнено условие .

Определение корня функции методом половинного деления реализовано ниже в программе Root на примере функции

на интервале .

ProgramRoot;

Const eps = 0.001;

Varn : byte;

a,b,c,Fa,Fb,Fc : real;

Begin

a:=0.5*pi; b:=1.5*pi;

Fa:=0.25*sqrt(a)+sin(a); Fb:=0.25*sqrt(b)+sin(b);

n:=0;

While (b-a)>eps do

Begin

Inc(n);

c:=0.5*(a+b); Fc:=0.25*sqrt(c)+sin(c);

If Fa*Fc>0 then{ если Fa*Fc>0, то переменные }

Begin{ Fa и Fc имеют одинаковый }

a:=c; Fa:=Fc { знак }

End

Else

Begin

b:=c; Fb:=Fc

End

End;

c:=0.5*(a+b); Fc:=0.25*sqrt(c)+sin(c);

Writeln('n = ',n,' c = ',c:9:6,' Fc = ',Fc:12);

End.

Результаты вычислений по программе Root приведены в таблице на следующей странице.

0.01 0.001 0.0001 0.00001 0.000001		3.641670 3.638986 3.638746 3.638702 3.638699	-2.41473E-03 -2.33136E-04 -3.81965E-05 -1.63049E-06 -1.07303E-07

Примечание. Рассмотренный ранее алгоритм Евклида также является итерационным. Здесь количество циклов заранее неизвестно и определяется значениями исходных данных и . Условием окончания цикла является выполнение отношения .