Учащиеся читают теорию (текст спроецирован на экран или интерактивную доску либо находится в файле, имеющемся на каждом компьютере):
Итерационным (от латинского iteratio – повторение) называют цикл, характеризующийся последовательным приближением вычисляемой величины (величин) к искомому результату.
Подобные вычисления можно реализовать двумя способами:
1. С помощью цикла с заранее неизвестным числом повторений (т. е. цикла с предусловием или
с постусловием). В этом случае цикл заканчивается при достижении заданной точности, когда абсолютная величина разности вычисленного и точного значения искомой величины становится меньше требуемой точности.
2. С помощью цикла с известным числом повторений (т.е. цикла с параметром). В этом случае ставится ограничение на максимальное число повторений цикла, и цикл заканчивается, как только произойдет одно из двух: либо будет достигнута заданная точность, либо будет исчерпано максимальное число повторений цикла.
В разделе “Цикл с параметром” мы будем программировать итерационные циклы вторым способом.
К итерационным циклам приводят задачи:
1. Вычисления сумм и произведений бесконечных рядов;
2. Реализации численных методов решения уравнений и их систем;
3. Задачи нахождения максимумов и минимумов функций
и некоторые другие задачи.
Наиболее простым видом задач, реализуемых с помощью итерационных циклов, являются задачи вычисления сумм и произведений бесконечных рядов. Эти задачи мы и будем рассматривать на примерах.
Пример. Составить программу вычисления суммы ряда
с точностью до члена ряда, по модулю меньшего ε, для заданного значения x.
Для реализации решения этой задачи с помощью цикла с параметром следует ограничить максимальное количество итераций, т. е. максимальное количество повторений цикла. В качестве числа, ограничивающего этот максимум, следует взять такой номер N, при котором, как предполагается, гарантировано неравенство формула. Начальное значение параметра цикла будет равно единице, а конечное - N.
При выполнении этого цикла возможны три случая:
1. Параметр цикла еще не достиг значения N, а абсолютная величина очередного члена ряда стала меньше, чем ε. В этом случае точность уже достигнута, и цикл следует прервать досрочно. Это можно сделать оператором BREAK.
2. Параметр цикла достиг значения N, и абсолютная величина N-го члена ряда меньше ε (абсолютная величина (N - 1)-го члена при этом больше либо равна ε. В этом случае точность достигается именно при завершении цикла «вовремя».
3. Параметр цикла достиг значения N, но абсолютная величина N-го члена ряда больше либо равна ε. В этом случае при завершении цикла «вовремя» требуемая точность еще не достигнута. Это, в свою очередь, означает одно из трех:
1) Число N выбрано недостаточно большим. Можно попробовать увеличить N. Если это помогает, проблема решена.
2) Допущена ошибка в формуле, используемой для вычисления члена ряда. Необходимо исправить эту ошибку и заново откомпилировать программу.
3) Ряд расходится, т. е. члены ряда никогда не станут по модулю меньше ε. В этом случае задача неразрешима.
В данном примере в качестве N возьмем число 100, т. е. будем суммировать не более 100 членов ряда.
Программа имеет вид:
PROGRAM RjadSinusov;
CONST N : integer = 100;
VAR S, x, z, eps : real;
i, k : integer;
BEGIN
readln (x, eps);
S := 0;
FOR i := 1 TO N DO
BEGIN
k := 2 * i - 1;
z := sin (k * x) / k;
S := S + z;
IF (abs (z) < eps) THEN Break;
END;
writeln ('S = ', S, ', z = ', z, ', i = ', i);
END.
Вопрос для учащихся:
Какие переменные служат входными (аргумент x, точность ε) и выходными (вычисленная сумма S, последний член ряда z, количество членов i) данными в этой программе?
Запустим программу на выполнение. В качестве x введем единицу (вещественную!), в качестве ε - 1E-3 (т. е. 10-3).
Получим результаты: S = 7.8214648250E-01, z = -8.6001686648E-04, i = 57.
Мы видим, что просуммировано 57 членов, причем значение последнего члена приблизительно равно -8 • 10-4, т. е. по модулю немногим меньше, чем 10-3. Из полученных результатов можно сделать вывод, что требуемая точность достигнута.
Выполним теперь программу еще раз при x = 1 и ε = 10-5.
Результаты при таких начальных данных будут:
S = 7.8395912895E-01, z = -4.4311499301E-03, i = 100.
На этот раз просуммировано 100 членов, но требуемая точность еще не достигнута. Попробуем увеличить максимальное число членов. Меняем в тексте программы N на 200, компилируем программу и запускаем ее на выполнение. На этот раз результаты следующие:
S = 7.8630245665E-01, z = -8.4914155554E-08, i = 178.
Итак, в данном случае 100 членов было недостаточно для достижения точности, но 200 членов хватило.
Из сказанного можно сделать вывод: Чем выше требуемая точность, тем больше членов необходимо просуммировать.
Вопрос на засыпку:
Почему итерационный процесс суммирования бесконечного ряда удобнее реализовать именно с помощью цикла с параметром, несмотря на то, что количество суммируемых членов ряда заранее неизвестно?
Ответ:
В цикле с параметром количество повторений не только известно заранее, но и конечно, поэтому зацикливание невозможно. Результат (точный или неточный) всегда будет получен за конечное время. Если же использовать цикл с предусловием или постусловием (используя в качестве критерия окончания цикла достижение заданной точности), то в случае расходимости ряда или ошибки в формуле вычисления членов ряда произойдет зацикливание, т. е. цикл будет выполняться бесконечно, и мы никогда не получим результат. Поэтому итерационные процессы следует реализовать именно с помощью цикла с параметром.
Учащиеся самостоятельно составляют программу вычисления суммы бесконечного рядаформула с заданной точностью ε (суммировать до 1000 членов ряда) и протестировать эту программу для значений ε, равных 10-2, 10-10 и 10-20.
Программа имеет вид:
PROGRAM Iter;
CONST N : integer = 1000;
VAR pi, eps, S, z : real;
k : integer;
BEGIN
readln (eps);
S := 0;
FOR k := 0 TO N DO
BEGIN
z := 1. / sqr (sqr (2. * k + 1));
S := S + z;
IF (abs (z) < eps) THEN Break;
END;
pi := sqrt (sqrt (96. * S));
writeln ('pi = ', pi, ', z = ', z, ', k = ', k);
END.
Результаты вычислений:
При ε = 10-2: π = 3,1410256322, z = 1,6 • 10-3, k = 2;
При ε = 10-10: π = 3,1415926496, z = 9,9029127142 • 10-11, k = 158;
При ε = 10-20: π = 3,1415926535, z = 6,2375156094 • 10-14, k = 1000.
В последнем случае 1000 членов недостаточно для достижения точности, и число N необходимо увеличить до 50000 (изменив при этом тип константы N и переменной k на LongInt, а тип переменной pi на Double, поскольку
N в данном случае превышает 32767, а число π вычисляется с 20-ю знаками после запятой).
После внесения изменений в программу получаем:
π = 3,14159265350132, z = 9,99960001000003 • 10-21, k = 50000.
Т. о., точность ε = 10-20 достигается ровно на 50000-й итерации.
Учащимся предлагается ответить на контрольные вопросы:
1) Какой цикл называется итерационным?
2) Какие задачи решаются с помощью итерационных циклов?
3) Какими способами можно реализовать итерационный процесс?
4) Какой способ предпочтительнее и почему?
5) Каким образом проверяется критерий достижения заданной точности?
6) Как следует поступать в случаях, когда максимальное количество итераций исчерпано, но требуемая точность не достигнута?
Составить программу вычисления бесконечного произведения P = формула . Аргумент x и точность ε вводятся с клавиатуры. Протестировать программу при различных значениях аргумента и точности, а именно:
1) При x = 0.05 и ε = 10-3;
2) При x = 0.5 и ε = 10-4;
3)
Программа должна иметь вид:
PROGRAM IterPrzv;
CONST N : integer = 1000;
VAR x, eps, P, z : real;
i : integer;
BEGIN
readln (x, eps);
P := 1.;
FOR i := 1 TO N DO
BEGIN
z := 2 * sin (i * x);
P := P * z;
IF (abs (z) < eps) THEN Break;
END;
writeln ('P = ', P, ', z = ', z, ', i = ', i);
END.
Результаты вычислений:
При x = 0.05 и ε = 10-3 : P = 3,13826971361323 • 10-1, z = 8,88156901861947 • 10-4, i = 377;
при x = 0.5 и ε = 10-4 : P = -4.26745750894497 • 10-2, z = -6.02887067189806 • 10-5, i = 710;
при x = 1.57 и ε = 10-5 : P = 0, z = -1.42958422156516, i = 1000;\\.
В последнем случае никакое увеличение числа N не приводит к достижению требуемой точности: при данном значении x ряд расходится.