Итерационные алгоритмы

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

Использование итерационных алгоритмов позволяет решать трансцендентные уравнения. Однако эти методы не являются универсальными. Они применимы только тогда, когда результаты последовательных итераций сходятся, то есть постепенно приближаются к некоторому значению, которое и будет решением уравнения.

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

Таблица 5.1 Уравнения, решаемые методом итераций

Вариант	Уравнение	Итерационная формула	Ограничения
			ab<1, x0>0
			a>0, b>0, b/a<6, x0<π/2
			c>0, x0>0
			a>1, x0>0

Продолжение таблицы 5.1
			ab>c, x0<π/(2b)
			a>0, b>0 c>1, x0>0
			a>0, c>0, x0>0
			a>1, c>1, b<c, x0>1
			a>0, b>0, c>0, x0>0
			a>0, b>0, c>0, x0>0

Алгоритм решения уравнений, приведенных в таблице 5.1.заключается в следующем.

Берется какое-нибудь приближенное значение корня уравнения х0 (начальное приближение) и подставляется в итерационную формулу. Полученное по итерационной формуле новое приближенное значение корня сравнивается с предыдущим. Если эти значения существенно отличаются друг от друга, то новое приближенное значение подставляется в итерационную формулу вместо старого и получается новое приближенное значение. Так продолжается до тех пор, пока новое и старое приближения станут достаточно близкими дуг к другу.

5.1.5.1 Пример итерационного алгоритма для вычисления кубического корня

Примером итерационного алгоритма может служить алгоритм вычисления кубического корня методом Ньютона.

Суть метода заключается в том, что приближенное значение корня находится по формуле 5.1.

(5.1)

где а – число, из которого извлекается корень, x_old – приближенное значение корня, x_new – более точное, чем x_old значение корня.

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

Вычисления проводятся обычно до тех пор, пока разность между двумя последовательными приближениями по абсолютной величине не станет меньше некоторого, наперед заданного, достаточно малого числа.

Для реализации этого алгоритма используется цикл REPEAT.

Схема алгоритма, реализующего этот метод, представлена на рисунке 5.5.

В алгоритме предусмотрено прерывание цикла с помощью инструкции break в том случае, если переменная Xold равна нулю, для того, чтобы исключить деление на 0.

Рисунок 5.5 – Схема алгоритма извлечения кубического корня

5.1.5.2 Задание для самостоятельной работы

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