§ 2. Понятие об итерационных методах уточнения корней
Пусть уже произведена локализация корней и известен отрезок [; ], в котором заключён ровно один корень r [; ] уравнения f(x) = 0. Как уточнить значение корня ?
Как правило, для этого используются итерационные методы (от iteratia – повторение). Их суть заключается в том, что по заданной погрешности и начальному приближению x0 строится последовательность {xn}n N приближений корня, сходящаяся к r – точному значению корня уравнения f(x) = 0. Вычисления производятся по явно указанной формуле следующего общего вида xn+1 = g(xn , xn–1 , … , x0). Таким образом, каждая последующая величина может зависеть от всех или некоторых предыдущих.
На практике для экономии памяти и других вычислительных ресурсов количество используемых предыдущих членов последовательности приближений в рекуррентной формуле не велико: обычно xn+1 = g(xn , xn–1 ) или даже xn+1 = g(xn ). Вычисления продолжаются, пока |xn+1 – xn | > или |f(xn)| > . Конечно, в идеале хотелось бы обеспечить условие малости абсолютной погрешности |xn – r| < , но величина r неизвестна, так что это условие сходимости заменяется приближённым.
Говорят, что
итерационный процесс xn+1
= g(xn
, xn–1
, … , x0)
имеет порядок
сходимости k
R,
если существует такая константа c
> 0, для
которой при всех n
N
выполнено неравенство |xn+1
– r|
< c·|xn
– r|k.
Смысл этого понятия в том, что абсолютная
погрешность n+1
= |xn+1
– r|
вычисления
корня меньше величины c·nk
. Для того
чтобы величина k
действительно контролировала степень
сходимости итерационного процесса
(т.е.
),
она должна быть положительной. В
большинстве реальных применений
рассматривается k
N.
При этом в случае k
= 1 говорят
о линейной
скорости сходимости итерационного
процесса,
а при k
= 2 – о
квадратичной.
Ясно, что, если
итерационный процесс имеет порядок
сходимости k,
то
В случае k
= 1 получаем
|xn+1
– r|
< cn·|x1
– r|,
а при k
> 1 приходим
к оценке |xn+1
– r|
<
.
Таким образом, для итерационного
процесса с линейной скоростью сходимости
величина погрешности n+1
= |xn+1
– r|
оценивается
как cn·1
– член
геометрической прогрессии со знаменателем
c,
а в случае порядка сходимости k
> 1 получае6тся
n+1
<
–
показательное
выражение с
. В случае выполнения подобных оценок
говорят, что итерационный процесс
сходится со
скоростью геометрической прогрессии
или
с показательной скоростью соответственно.
В этих оценках особо важен случай c
< 1, 1
< 1. Тогда
сразу получается, что
,
т.е. последовательность приближений
сходится к точному значению r.
Упражнение: Найдите итерационный процесс, имеющий скорость сходимости геометрической прогрессии, но не сходящийся линейно.
Нужно заметить, что поскольку на практике при использовании итерационного процесса ограничиваются лишь конечным числом итераций, понятие порядка сходимости не играет определяющей роли. В то же время, конечно, лучше использовать методы, для которых вычислен порядок сходимости. Чем выше этот порядок, тем быстрее сходится итерационный процесс.
Рассмотрим простейший итерационный процесс уточнения корней – метод деления пополам (метод вилки). Пусть известен отрезок [; ], в котором заключён ровно один корень r [; ] уравнения f(x) = 0, причём f()·f() < 0.