Кафедра физхимии ЮФУ(РГУ) - Курс "Численные методы и программирование"

Кафедра физхимии ЮФУ (РГУ)
ЧИСЛЕННЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ
Материалы к лекционному курсу
Лектор – ст. преп. Щербаков И.Н.

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

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

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

, где k – это номер итерации, - это значение, полученное на k-ом шаге процесса.

Итерационной формулой в общем виде называется выражение

позволяющее генерировать последующие члены последовательности через вычисленные ранее (на предыдущих шагах алгоритма). Чаще же всего итерационные формулы имеют более простой вид:

Итерационная последовательность своим пределом должна иметь искомое значение – x*.

Если такой предел существует, то итерационный процесс называется сходящимся. Если нет, то расходящимся.

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

Вот некоторые общие примеры, используемые на практике:

1. абсолютное изменение параметра на соседних шагах итерационного процесса:

2. относительное изменение на соседних шагах

Здесь - наперед заданное малое значение, определяющая точность нахождения решения.

В реализации конкретных численных методов возможно применение специфических критериев или комбинации нескольких критериев.

Таким образом, общая блок-схема итерационных алгоритмов может быть записана так

Типы сходимости итерационных последовательностей

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

Сходимость последовательности к называется линейной (а итерационный процесс – линейно сходящимся), если существует такая постоянная С и такой номер k₀, что

для всех

и сверхлинейной, если существует такая положительная последовательность

, что и

для всех

Другое определение скорости сходимости основывается на понятии порядка сходимости.

Последовательность сходится к по меньшей мере с порядком p (соответственно итерационный процесс имеет по меньшей мере p-й порядок), если найдутся такие константы C>0, k₀и , что

для всех

Сравнивая два определения видим, что для процессов первого порядка сходимости (p=1) имеем определение линейно сходящихся процессов. При p=2 имеет квадратично сходящийся процесс и т.д.

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