На этом шаге мы рассмотрим понятие итерации и соответствующий функционал.

Определение.

Итерация (от лат. iteratio - повторение) - это результат повторного применения какой-либо математической операции.

Определение.

(1) Первой, второй, третьей .,..., n-ой итерациями функции y=f(x) называются соответственно функции
```
   f₁(x)=f(x), f₂(x)=f(f₁(x)), f₃(x)=f(f₂(x)),...,f_n(x)=f(f_n-1(x)).
```
Показателем итерации называется индекс n.
(2) Итерированием называется процесс перехода от функции f(x) к функциям f₁(x), f₂(x), ..., f_n(x).

Пример процесса итерирования.

Если f(x)=x^α, то получаем

                ₂          ₂      ₃              _n-1     _n
   f₂(x)=(x^α)^α=x^α, f₃(x)=(x^α )^α =x^α ,...,f_n(x)=(x^α   )^α=x^α ,...

Для некоторых классов функций можно определить итерации с произвольным действительным и даже комплексным показателем.

Определение.

(1) Итерационные методы - это методы построения последовательных приближений к решению задачи. Применение метода начинают с выбора одного или нескольких приближений. Для получения каждого из последующих приближений выполняют однотипный набор действий с использованием ранее найденных приближений, который называется итерацией. Неограниченное продолжение этого итерационного процесса теоретически позволяет построить бесконечную последовательность приближений к решению - итерационную последовательность.
(2) Говорят, что итерационный метод сходится, если итерационная последовательность сходится к решению задачи.

Замечание. Первые попытки изучения итераций выполнены Л.Эйлером (1778).

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

   [x,f(x),f(f(x)),f(f(f(x))),...]

имеет следующий синтаксис:

   iterate:: (a -> a) -> a -> [a]
   iterate f x

Например:

   > iterate sqrt 256
   [256.0,16.0,4.0,2.0,1.4142135623731,1.18920711500272,...]

В заключение приведем небольшой пример.

   -- Демонстрация использования функционала iterate, который
   -- формирует потенциально бесконечный список вида
   --
   --  [x, sqrt x, sqrt(sqrt x)), sqrt(sqrt(sqrt x))),...]
   -- *****************************************************
   -- Функция f, возвращающая значение квадратного корня из
   -- вещественного числа x0;  итерации  продолжаются, пока
   -- в списке итераций не будет получено число, меньшее e
   -------------------------------------------------------
   f:: Float -> Float -> Int -> (Float,Int)
   f x0 e i | (s !! i)>e = f x0 e (i+1)
            | True       = (s !! i,i)
         where s = iterate sqrt x0
   ----------------------------------
   f1:: Float -> Float -> (Float,Int)
   f1 x0 e = (last s,length s)  
         where s = takeWhile (\x -> x>e) (iterate sqrt x0)
   -- ****************************************************
   -- Неудачные тестовые примеры:
   ------------------------------
   test1 = f  36 1.0006 0
   test2 = f1 36 1.0006

Файл с примерами можно взять здесь.

На следующем шаге мы рассмотрим функционал для организации циклических процессов.

Предыдущий шаг Содержание Следующий шаг