Понятие об итерационных методах уточнения корней

Пусть уже произведена локализация корней и известен отрезок [a; b], в котором заключён ровно один корень r Î [a; b] уравнения f(x) = 0. Как уточнить значение корня?

Как правило, для этого используются итерационные методы (от iteratia – повторение). Их суть заключается в том, что по заданной погрешности D и начальному приближению x₀ строится последовательность {x_n}_{n Î N} приближений корня, сходящаяся к r – точному значению корня уравнения f(x) = 0. Вычисления производятся по явно указанной формуле следующего общего вида x_n+1 = g(x_n, x_n–1, …, x₀). Таким образом, каждая последующая величина может зависеть от всех или некоторых предыдущих.

На практике для экономии памяти и других вычислительных ресурсов количество используемых предыдущих членов последовательности приближений в рекуррентной формуле не велико: обычно x_n+1 = g(x_n, x_n–1 ) или даже x_n+1 = g(x_n). Вычисления продолжаются, пока |x_n+1 – x_n | > D или |f(x_n)| > D. Конечно, в идеале хотелось бы обеспечить условие малости абсолютной погрешности |x_n – r| < D, но величина r неизвестна, так что это условие сходимости заменяется приближённым.

Говорят, что итерационный процесс x_n+1 = g(x_n, x_n–1, …, x₀) имеет порядок сходимости k Î R, если существует такая константа c > 0, для которой при всех n Î N выполнено неравенство |x_n+1 – r| < c·|x_n – r|^k. Смысл этого понятия в том, что абсолютная погрешность D_n+1 = |x_n+1 – r| вычисления корня меньше величины c·D_n^k. Для того чтобы величина k действительно контролировала степень сходимости итерационного процесса (т.е. ), она должна быть положительной. В большинстве реальных применений рассматривается k Î N. При этом в случае k = 1 говорят о линейной скорости сходимости итерационного процесса, а при k = 2 – о квадратичной.

Ясно, что, если итерационный процесс имеет порядок сходимости k, то В случае k = 1 получаем |x_n+1 – r| < cⁿ·|x₁ – r|, а при k > 1 приходим к оценке |x_n+1 – r| < . Таким образом, для итерационного процесса с линейной скоростью сходимости величина погрешности D_n+1 = |x_n+1 – r| оценивается как cⁿ·D₁ – член геометрической прогрессии со знаменателем c, а в случае порядка сходимости k > 1 получае6тся D_n+1 < – показательное выражение с . В случае выполнения подобных оценок говорят, что итерационный процесс сходится со скоростью геометрической прогрессии или с показательной скоростью соответственно. В этих оценках особо важен случай c < 1, D₁ < 1. Тогда сразу получается, что , т.е. последовательность приближений сходится к точному значению r.

Упражнение: Найдите итерационный процесс, имеющий скорость сходимости геометрической прогрессии, но не сходящийся линейно.

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

Рассмотрим простейший итерационный процесс уточнения корней – метод деления пополам (метод вилки). Пусть известен отрезок [a; b], в котором заключён ровно один корень r Î [a; b] уравнения f(x) = 0, причём f(a)·f(b) < 0.

Метод деления пополам (метод вилки)

1. полагаем x₀ = a = a₀, b₀ = b, D₀ = |b – a|, причём f(a₀)·f(b₀) < 0;

2. пусть уже известны x_n, a_n, b_n, D_n, где f(a_n)·f(b_n) £ 0;

3. если D_n £ D и |f(x_n)| £ D, то процесс завершён, x_n – приближённое значение корня;

4. если D_n > D или |f(x_n)| > D, то x_n+1 = – середина отрезка [a_n; b_n], [a_n+1; b_n+1] = ,

D_n+1 = , возврат к шагу 2.

Применение метода иллюстрируют следующие рисунки:

Теорема (о методе деления пополам). Пусть известен отрезок [a; b], в котором есть ровно один корень уравнения f(x) = 0, причём f(a)·f(b) < 0. Метод деления пополам определяет последовательность {x_n}_{n Î N}, сходящуюся к корню r Î [a; b] со скоростью геометрической прогрессии.

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

Во-первых, описанный алгоритм всегда определяет новое приближение x_n+1 по уже известным. Действительно, это следует из того, что одно из условий f(a_n)·f(x_n+1) < 0 или f(x_n+1)·f(b_n) < 0, используемых для вычисления a_n+1, b_n+1 в шаге 4 описанного алгоритма, обязательно будет выполнено: если это не так, то обе эти величины положительны (в случае обращения в ноль одной из них корень уже найден), а значит, f(a_n)·f(x_n+1)²·f(b_n) > 0, т.е. f(a_n)·f(b_n) > 0, вопреки пункту 2 алгоритма.

Далее, в ходе итерационного процесса на самом деле строится последовательность вложенных отрезков [a₀; b₀] = [x₀; x₁] É [a₁; b₁] É …, на концах которых функция f(x) принимает значения противоположных знаков: f(a_i)·f(b_i) < 0. Формально,

[a_i+1; b_i+1] = .

Эта последовательность вложенных отрезков стягивающаяся, т.к. из построения D_i+1 = |b_i+1 – a_i+1 | = . Значит, все эти отрезки содержат общую точку x, причём , f(x)² = £ 0, т.е. f(x) = 0, и значит, x = r – корень функции f(x), к которому сходятся концы рассматриваемых стягивающихся отрезков – члены последовательности {x_n}_{n Î N}.

Утверждение о скорости сходимости следует из очевидной оценки |x_i+1 – r| £ D_i+1 = .

Теорема доказана.

Примеры: 1. Уточнить значение корня функции f(x) = ln x на отрезке [0, 5; 1, 7] с точностью D = 0, 05. Точное значение корня, очевидно, равно 1.

Таким образом, приближённым значением корня будет 0, 99, поскольку D₅ = 0, 038 < 0, 05 и |f(x₅)| = 0, 0126 < 0, 05.

2. Уточнить значение корня функции f(x) = 32·x³ – 48·x² + 22·x – 3 на отрезке [0; 0, 34] с точностью D = 0, 01. Точное значение корня 0, 25.

Поскольку D₆ = 0, 005 < 0, 01 и | f(x₆)| = 0, 0013 < 0, 01, заключаем, что приближённое значение корня равно x₆» 0, 25.

В методе деления пополам можно контролировать количество итераций: если D – заданная погрешность, то из соотношения D_k = находим количество требуемых итераций:

.

Так, для первого из рассмотренных выше примеров сразу можно оценить k ³ 1, 443·ln = 1, 443·ln (20·1, 2)» 4, 59, т.е. k = 5. Для второго примера k ³ 1, 443·ln = 1, 443·ln (50)» 5, 65, т.е. k = 6.

Рассмотрим теперь вопрос о порядке сходимости метода деления пополам. Во многих книгах (в том числе, к сожалению, и в учебнике [7, стр. 90]) утверждается, что это метод первого порядка. Однако такое заключение необоснованно: следующий пример иллюстрирует ошибочность этого вывода.

Пример. Уточнить корень на отрезке [0; 1] с точностью до D = 0, 001. Точное значение корня r = 0, 49804687499.

В таблицах ниже приведены вычисления по методу деления пополам. Следует учесть, что значения f(x_i) в методе деления пополам сами по себе не важны, метод деления пополам оперирует лишь знаками этих значений, которые полностью определяются знаками разности x_i – r. Поэтому в приводимых ниже вычислениях участвуют не значения функции (которая даже не задана), а знаки этих значений.

Представленные в таблицах отношения x_i+1 / x_i показывают, что подобрать константу c со свойством |x_i+1 – r| £ c·|x_i – r| при всех достаточно больших i Î N не представляется возможным. Причина состоит в непредсказуемом поведении величины x_i+1 / x_i при “переходе через корень”. Таким образом, метод деления пополам достаточно быстро сходится (со скоростью геометрической прогрессии), но утверждать, что он имеет первый порядок сходимости, нельзя.

Краткая характеристика метода деления пополам приведена в приложении (таблица I).