Метод простой итерации. Теорема о неподвижной точке сжимающего отображения даёт метод первого порядка для решения уравнения h(x) = x

Теорема о неподвижной точке сжимающего отображения даёт метод первого порядка для решения уравнения h(x) = x, если h: [a; b] ® [a; b] – сжимающее отображение. Здесь, конечно, E = [a; b], r(x, y) = |x – y| – обычное расстояние между точками числовой прямой. Поэтому упомянутую теорему можно использовать для уточнения корней уравнений: для уравнения h(x) = x достаточно выбрать любое приближение x₀ Î [a; b] и вычислять последовательно приближения x₁ = h(x₀), x_n+1 = h(x_n) (n Î N ).

Эта общая идея нуждается в дополнительной проработке. Необходимо дать ответы на следующие вопросы:

1. как определить по заданной функции h и отрезку [a; b], выполнено ли условие h([a; b]) Í [a; b]?

2. как определить, будет ли данная функция h: [a; b] ® [a; b] сжимающей?

3. как выбрать наиболее удачное приближение x₀ Î [a; b]?

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

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

1. условие h([a; b]) Í [a; b]. Общих методов решения этой задачи нет. Необходимо, конечно, чтобы h(a), h(b) Î [a; b]. Тогда для непрерывной функции h по теореме о промежуточном значении будет верно включение [h(a); h(b)] Í h([a; b]). Однако обратное включение может не выполняться (приведите пример!).

Как правило, отрезок [a; b] после предварительной локализации корня достаточно мал, а функция h не слишком патологическая. Так что обычно предполагают, что h монотонна на [a; b]. В этом случае проверка проста условия [h(a); h(b)] Í h([a; b]): a £ £ b. Более подробно:

если h не убывает, то нужно h(a) ³ a и h(b) £ b;

если h не возрастает, то нужно h(a) £ b и h(b) ³ a.

Проверка возрастания и убывания функции h очень грубо может быть выполнена по значениям h(a) и h(b): если h(a) > h(b), то h можетубывать, а если h(a) < h(b) – то возрастать. Конечно, этот поверхностный критерий чреват ошибками. Для подстраховки можно взять несколько точек на отрезке и проверить условие монотонности в этих точках, но это тоже не гарантирует точности вывода.

Если предполагать, что функция h дифференцируема на [a; b], то для проверки монотонности можно вычислить производную h¢ и проверять условие " z Î [a; b] h¢ (z) ³ 0 для возрастания функции h и условие " z Î [a; b] h¢ (z) £ 0 для её убывания. Для приближённого ответа на вопрос можно, по крайней мере, вычислить знаки h¢ (z_i) в нескольких точках z_i Î [a; b] (1 £ i £ k). Однако, это не спасает от ошибки.

Самое надёжное – аналитически доказать включение h([a; b]) Í [a; b] или постоянство знака производной на этом отрезке.

2. условие сжимаемости. Для того чтобы заданное отображение h: [a; b] ® [a, b] было сжимающим должно выполняться условие $ с Î [0; 1) " x, y Î [a; b] |h(x) – h(y)| £ c·|x – y|. Если функция h(x) непрерывно дифференцируема на [a; b], то (по теореме Лагранжа) " x, y Î [a; b] $ z Î [x; y] h(x) – h(y) = h¢ (z)·(x – y). Поэтому для сжимаемости отображения h достаточно потребовать существования числа с со свойством |h(x) – h(y)| = |h¢ (z)|·|x – y| £ с·|x – y|, т.е. |h¢ (z)| £ c < 1 при любых z Î [a; b]. Итак, для сжимаемости непрерывно дифференцируемого отображения h: [a; b] ® [a; b] достаточно, чтобы |h¢ (z)| < 1 (в качестве c достаточно взять этотсупремум).

Полученное условие |h¢ (z)| < 1 и необходимо. Действительно, если в некоторой точке x₀ Î [a; b] будет |f¢ (x₀)| > 1, то вблизи x₀ выполнено равенство f(x) = f(x₀) + f¢ (x₀)·(x – x₀)+ u(x – x₀), где . Выберем x так, чтобы для сколь угодно малого e > 0. Тогда |f(x) – f(x₀)| = | f¢ (x₀)·(x – x₀)+ u(x – x₀)| ³ | f¢ (x₀)·(x – x₀)| – |u(x – x₀)| > > |f¢ (x₀)|·|x – x₀| – e·|x – x₀| = (|f¢ (x₀)| – e)·|x – x₀| > |x – x₀| при e < |f¢ (x₀)| – 1.

Таким образом, для сжимаемости непрерывно дифференцируемого отображения h: [a; b] ® [a, b] необходимо и достаточно выполнение условия |h¢ (z)| < 1.

Конечно, проверить это условие в общем случае ничуть не легче, чем решить проблемы предыдущего пункта. Если предположить монотонность и неизменность выпуклости непрерывно дифференцируемой функции h, то проверка проста:

а) если h¢ > 0, h выпукла вниз, то c = h¢ (b) < 1;

б) если h¢ > 0, h выпукла вверх, то c = h¢ (a) < 1;

в) если h¢ < 0, h выпукла вниз, то c = –h¢ (a) < 1;

На представленных рисунках красным цветом выделены предельные положения касательных к кривой, допускаемые в каждом из рассматриваемых случаев в точках x = a (б и в) и x = b (а и г), с угловыми коэффициентами 1 (а и б) и –1 (в и г).

Эти условия применимы, в частности для дважды непрерывно дифференцируемой функции h: [a; b] ® [a; b] с условиями неизменности знака производных h¢ и h¢ ¢ на [a; b]:

если h¢ ·h¢ ¢ ³ 0, то c = |h¢ (b)| < 1 (случаи а) и г));

если h¢ ·h¢ ¢ £ 0, то c = |h¢ (a)| < 1 (случаи б) и в));

К отмеченным четырём случаям можно свести проверку, если отрезок [a; b] достаточно мал, а функция h не слишком патологична. Нарушение этих условий, вообще говоря, не означает, что итерационный процесс не будет сходиться. Однако такое несанкционированное применение метода итераций требует анализа в каждой конкретной ситуации.

3. выбор приближения x₀ Î [a; b]. По теореме о неподвижной точке сжимающего отображения, итерационный процесс x₁ = h(x₀), x_n+1 = h(x_n) является методом первого порядка и сходится при любом начальном приближении x₀ Î [a; b]. Кроме того, |x_n – r| £ , поэтому скорость сходимости последовательности {x_n}_{n Î N} к корню r определяется величиной |x₁ – x₀| = |h(x₀) – x₀|, которую в описанных выше четырёх модельных случаях a) – г) можно уменьшить.

Например, за x₀ можно брать точку пересечения с осью абсцисс касательной к графику функции y = x – h(x), выпущенной из конца g отрезка [a; b], в котором достигается минимум модуля производной |h¢ (x)|.

Например, в случае а) минимум модуля производной |h¢ (x)| равен h¢ (a) < 1. Поэтому пишем уравнение касательной к кривой y = x – h(x) в точке a:

y = a – h(a) + (1 – h¢ (a))·(x – a),

и, приравнивая y к нулю, получаем x₀ = . Эта точка принадлежит отрезку [a; r] Í [a; b]. Действительно, a £ Û Û a £ h(a), что верно ввиду h([a; b]) Í [a; b]. С другой стороны, функция y = x – h(x) возрастает (y¢ = 1 – h¢ (x) > 0) и выпукла вверх на отрезке [a; b]. Поэтому график этой функции лежит под касательной в точке a, т.е. x₀ – h(x₀) £ 0, x₀ £ r.

Рассуждая аналогично в случаях б), в), г), получим следующие значения для начального приближения x₀:

в случаях а) и г) x₀ = ;

в случаях б) и в) x₀ = .

За процедуру уточнения начального приближения x₀ приходится платить дополнительными вычислениями. Поэтому можно в случаях а) и г) брать x₀ = a, а в случаях б) или в) – полагать x₀ = b.

4. условия выхода из итерационного процесса. Если задана погрешность D, то из оценки |x_n – r| £ £ D можно подсчитать количество необходимых итераций: n ³ log_c , т.е. . Как правило, поступают грубее, но проще: итерации выполняют, пока |x_n+1 – x_n| > D или |h(x) – x| > D, списывая неточности на погрешность метода.

Основные из полученных характеристик метода простой итерации для уравнения h(x) = x приведены в приложении (таблица II).

Примеры: 1. Уточнить корень уравнения 4· = x с точностью до 0, 01 на отрезке [4; 9].

Здесь h(x) = 4· , h¢ (x) = > 0, h¢ ¢ (x) = – < 0. При этом h(4) = 4· » 5, 77 Î [4; 9], h(9) = 4· = 8 Î [4; 9]. Значит h([4; 9]) Í [4; 9].

Далее, отображение h удовлетворяет рассмотренному случаю б), оно является сжимающим с коэффициентом c = h¢ (4) = » 0, 64 меньше 1. Поэтому берём x₀ = 9 и производим итерации, пока верно D_n = |x_n+1 – x_n| > 0, 01 или |4· – x | > 0, 01:

Таким образом, приближённое значение корня уравнения равно 7, 46.

Если уточнить приближение x₀ по полученным выше формулам, то

x₀ = ,

так что итераций потребуется меньше.

2. Уточнить второй положительный корень уравнения 4· = x с точностью 0, 01.

Этот корень лежит на отрезке [a; b], где a > 1, 1 < b < 7, 46. Ввиду неравенств h¢ > 0, h¢ ¢ < 0 для применимости метода должны быть выполнены условия h(a) ³ a, h(b) £ b, h¢ (a) < 1.

Удобнее начать с третьего условия: h¢ (a) < 1 Û < 1 Û Û a – 1 > Û a > . Если a = 2, 6, то h(2, 6) = 4· > 2, 6.

Осталось найти 2, 6 < b < 7, 46 со свойством h(b) £ b. Из таблицы предыдущего примера видно, что можно взять b = 7, 448. Теперь уточняем корень, производя стандартные вычисления:

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