Ітерація

Шаблон:Парадигми програмування Ітера́ція (від Шаблон:Lang-la — повторювання) — багатозначний термін, який залежно від контексту може означати:

• Повторне застосування математичної операції (із зміненими даними) при розв'язанні обчислювальних задач, яке дає можливість поступово наблизитися до правильного результату.
• Результат багаторазового повторення якоїсь математичної операції.

Застосування

Задача про нерухому точку

Ітерації застосовуються для розв'язування задачі

$x=Ax$,

де x — елемент певної множини, а A — оператор, що відображає множину саму в себе.

Ітераційна процедура розв'язку починається з довільно обраного елемента множини $x_0$. За цим елементом визначається наступна, перша ітерація

$x_1=A{x}_0$.

Продовжуючи послідовно застосовувати оператор A, отримуємо для n-ї ітерації:

$x_n=A{x}_{n-1}=A^n{x}_0$.

При виконанні певних умов така процедура збігається до певного елемента множини, який є розв'язком задачі.

Однак ітераційна процедура не завжди збіжна.

Фрактальні структури

Незбіжні ітеративні процедури використовуються для побудови та вивчення фракталів. Наприклад, множина Мандельброта утворюється при ітеруванні:

$z_{n+1}=z_n^2+c$,

де $z_0=0$, $z_n$ та c — комплексні числа.

Програмування

У програмуванні розрізняють ітераційні та рекурсивні алгоритми. При ітераційному алгоритмі певна функція викликається послідовно, і при потребі її повторного застосування, викликається знову із новим аргументом. У рекурсивних алгоритмах використовуються вкладені виклики функції, що призводить до залучення стеку викликів. Задля уникнення навантаження на стек викликів застосовують хвостову рекурсію, яка зводить рекурсивний алгоритм до ітераційного.

Див. також

• Метод ітерації (алгоритм)
• Рекурсія
• Ітератор
• Нерухома точка

Джерела

• Шаблон:Книга

• Шаблон:Книга