П р о г р а м м и р о в а н и е и т е р а ц и о н н ы Х ц и к л о в

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

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

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

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

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

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

,

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

.

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

= 16;

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

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

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

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

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

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

а) б)

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

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

int main()

{

float const eps = 0.00001;

float x, y, yn;

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

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

if (x> 0)

while (fabs(y-yn)> eps)

{

yn=y;

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

}

//Печать y

getch();

return 0;

}

Примечания.

1.Функция fabs() возвращает модуль выражения типа float. Для использования этой функции подключается заголовочный файл " math.h ".

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

3.Оператор " yn=x+2*eps; " в программе введен исключительно для задания значения переменной yn, которая используется в проверке условия входа в цикл. От него можно избавиться, если использовать цикл do-while. Ниже приведена реализация этого алгоритма с циклом do-while.

int main()

{

float const eps = 0.01;

float x, y, yn;

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

x=16;

y=x;

if (x> 0)

do

{

yn=y;

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

}

while (fabs(y-yn)> eps);

//Печать y

getch();

return 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.020833334+0.00026041688-

- 0.0000015500993+...

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

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

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

(2)

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

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

(3)

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

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

.

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

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

,

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

.

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

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

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

.

Тогда

(4)

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

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

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

Значение целочисленной переменной непосредственно входит в формулу для вычисления элемента . Чтобы исключить многочисленные преобразования int ® float, в программе переменная объявлена вещественной. Функция pow(x, 2) возвращает значение x², она описана в заголовочном файле" math.h ".

Си-программа.

int main()

{

float const eps = 0.00001;

float x, a, S, n;

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

x=0.5;

a=x; S=x; n=0.;

while (fabs(a)> eps)

{

a=-pow(x, 2)*a/((2*n+2)*(2*n+3));

S+=a; n+=1;

}

//Печать S

getch();

return 0;

}