(Колтакова Ирина Павловна, ГБОУ города Москвы «Лицей №1451»
Существуют вычислительные процессы, которые содержат циклы с неизвестным заранее числом повторений. Такие циклы, характеризующиеся последовательным приближением вычисляемых величин к исходному значению, называются итерационными. Окончание цикла в этом случае обычно осуществляется при достижении заданной точности вычисления результата. К итерационным циклам приводят задачи вычисления сумм бесконечных рядов, реализации численных методов интегрирования, решения алгебраических и трансцендентных уравнений, решения систем уравнений, задачи оптимизации.
В итерационных процессах результаты, полученные на текущем шаге, используются в качестве исходных данных для расчета на следующем шаге цикла.
При реализации итерационного процесса на компьютере необходимо задавать начальные значения и критерий, в соответствии с которым произойдет окончание процесса. Рассмотрим сущность итерационного циклического процесса на примере решения алгебраического уравнения.
Математический метод итерации состоит в следующем. Пусть необходимо найти корень алгебраического уравнения F(x)=0. Это уравнение представляется в виде: x=φ(x).
При этом считается, что очередное приближение корня равно значение функции φ от приближения корня, полученного на предыдущем шаге: xi=φ(xi-1).
Смысл метода итерации можно пояснить и графически:
Представим левую и правую части уравнения x=φ(x) в виде двух функций Y=x и Y=φ(x). Исходя из уравнения x=φ(x) точка пересечения графиков функций Y=x и Y=φ(x) дает искомый корень уравнения ξ, который находится последовательным приближением в соответствии с формулой результат xi=φ(xi-1), где начальное приближение корня x=x может быть найдено, например графическим построением функции f(x).
При реализации итерационного процесса обычно придерживаются следующего порядка вычислений.
δxi=Xi-Xi-1=φ(xi-1)-xi-1
Затем определяют значение нового приближения корня:
=Xi=xi-1+δxi
Такой подход экономит память машины и сокращает количество операторов для реализации алгоритма. Схема данного алгоритма представлена на рисунке.
Задача сводится к нахождению суммы
S= U(1)+ U(2)+ U(3)+ … +U(n) = ∑U(n), сумма N от 1 до бесконечности.
каждое слагаемое является функцией от номера N, определяющего место этого слагаемого в сумме. А также может являться функцией одного или несколько дополнительных параметров, например:
S=1/2*3 + 2/3*4 + … + n/(n+1)(n+2) + …. = ∑n/(n+1)*(n+2),
или
S= X2 /1*2 + X4/3*4 + … + (-1)n-1 *X2n/(2n-1)*2n +…= ∑(-1)n+1 *X2n/(2n-1)*2n,
Сумма N от 1 до бесконечности.
В общем случае начальное значение номера члена ряда N может быть отличным от 1 (например, равным 0). Обозначив его через ν, получим S = ∑U(n), сумма N от 1 до бесконечности.
Для вычисления суммы ряда используется прием накопления суммы: суммирование считается законченным при выполнении условия достижения заданной погрешности ξ: |U(n)|≤ ξ.
Задача нахождения суммы ряда является типичным примером итерационного процесса, так как заранее не известно, при каком числе членов ряда будет достигнута требуемая точность.
Процесс вычисления определяется рекуррентным соотношением
S(n)=S(n-1)+U(n). Для определения начального значения суммы перепишем S = ∑U(n), сумма N от 1 до бесконечности, в виде: S=U(ν)+∑U(n).
Элемент U(ν) можно принять в качестве начального значения суммы, а параметр n в итерационном процессе будет принимать значения ν+1, ν+2, .
Общая схема алгоритма вычисления суммы приведена на рисунке. Поскольку в вычислениях по рекуррентной формуле одновременно участвуют лишь два значения S(n) и S(n-1), в схеме алгоритма вместо этих переменных используется переменная S. Значение S будет изменяться каждый раз при прибавлении очередного члена суммы. Справа от знака присваивания значение переменной соответствует предыдущему значению суммы S(n-1), слева – текущему S(n)
Обычно формула общего члена суммы принадлежит одному из следующих типов:
Решение: Вычисление суммы бесконечного ряда
На языке Паскаль | |
Input x, epsS=1: U=1: n=1 While abs(u) > eps
U=(-1)*u*x*x/((2*n-1)*2*n) S=S+u N=n+1 Wend Print “n=”,n,”S=”,S end | Var x, eps : real;BeginRead(x, eps); { ввод значений x, eps}S:=1; U:=1; n:=1; {задание начальных значений} While abs(u) > eps Do {проверка условия цикла} Begin U:=(-1)*u*x*x/((2*n-1)*2*n);{слагаемое суммы ряда} S:=S+u; {наращивание суммы} N:=n+1; {увеличение N на единицу} End; Write (‘n=’, n, ‘S=’,S); {вывод результата суммы} End. |
Задание 1. Разложение SinX ряда Тейлора без остаточного члена. Считать, что требуемая точность достигнута, если очередное слагаемое по модулю <ξ. Все последующие слагаемые можно уже не учитывать. Полученную сумму сравнивать с результатом обращения к соответствующей встроенной функции.
Решение: Вычислить с точностью ξ>0, вводимой с клавиатуры сумму ряда:
SinX=X-X3/3!+X5/5!–X7/7!+X9/9!-X11/11! +…+ (-1)n-1*X(2n-1)/(2n-1)!
Выполняемые опера ции | Значения | |||
I | Y | S | ||
Ввести значение Х:= | ||||
Ввести значение eps := 0.0001 | ||||
0 (перед циклом) | Abs(Y) > eps |
I := 1 |
Y := X |
S :=X |
1 |
| I + 1 = 2 | Y1 := (-1) *(X*Х)/(2*3) *Y | S := S+ Y1 |
2 |
| I + 1 = 3 | Y2 := (-1) *(X*Х)/(4*5) *Y1 | S := S+ Y2 |
3 |
| I + 1 = 4 | Y3 := (-1) *(X*Х)/(6*7) *Y2 | S := S+ Y3 |
… | … | … | … | … |
N |
| I + 1 = N | Вычисление общего члена ряда: Yn := (-1) 2n-1*(X*Х)/((2*I-2)*(2*I-1))*Yn-1 | S := S+ Yn |
Задание 2. Разложение CosX ряда Тейлора без остаточного члена. Считать, что требуемая точность достигнута, если очередное слагаемое по модулю <ξ. Все последующие слагаемые можно уже не учитывать. Полученную сумму сравнивать с результатом обращения к соответствующей встроенной функции.
Решение: Вычислить с точностью ξ>0, вводимой с клавиатуры сумму ряда:
CosX = 1 – X2/2! + X4/4! – X6/6! +…+ (-1)n*X(2n)/(2n)!
Выполняемые опера ции | Значения | |||
I |
Y | S | ||
Ввести значение Х:= | ||||
Ввести значение eps := 0.0001 | ||||
0 (перед циклом) | Abs(Y) > eps |
I := 0 |
Y := 1 |
S :=1 |
1 |
| I + 2 = 0+2 = 2 | Y1 := (-1) *(X*Х)/(2*1) *Y | S := S+ Y1 |
2 |
| I + 2 = 2+2 = 4 | Y2 := (-1) *(X*Х)/(4*3) *Y1 | S := S+ Y2 |
3 |
| I + 2= 4+2 = 6 | Y3 := (-1) *(X*Х)/(6*5) *Y2 | S := S+ Y3 |
… | … | … | … | … |
N |
| I + 1 = N | Вычисление общего члена ряда: Yn := (-1) 2n*(X*Х)/(I*(I-1)) *Yn-1 | S := S+ Yn |
Задание 3. Вычислить с N-ое приближение выражения
Arctg(X) = X – X2/2! + X4/4! – X6/6! +…+ (-1)nX(2n)/(2n)!
Считать, что требуемая точность достигнута, если очередное слагаемое по модулю <ξ. Все последующие слагаемые можно уже не учитывать.
Решение:
Выполняемые опера ции | Значения | |||
I |
Y | S | ||
Ввести значение Х:= | ||||
Ввести значение eps := 0.0001 | ||||
0 (перед циклом) | Abs(Y) > eps |
I := 0 |
Y := X |
S :=0 |
1 |
| I + 1 = 2 | Y1 := (-1) *(X*Х)/3 *Y | S := S+ Y1 |
2 |
| I + 1 = 3 | Y2 := (-1) *(X*Х)/5 *Y1 | S := S+ Y2 |
3 |
| I + 1 = 4 | Y3 := (-1) *(X*Х)/7 *Y2 | S := S+ Y3 |
… | … | … | … | … |
N |
| I + 1 = N | Вычисление общего члена ряда: Yn := (-1) 2n-1 *(X*Х)/(2*I-1))*Yn-1 | S := S+ Yn |