Дискретно-непрерывная математика (стр. 84 )

Простые реализации таких методов задаются с помощью так называемых методов деления. Это — интервальные варианты метода двоичного поиска или других методов поиска. Мы кратко опишем такую процедуру. Для нее требуется лишь существова­ние интервального вычисления функции f в интер­вале Х(0). Чтобы улучшить локализацию нулей в Х(0\ мы делим Х(0) пополам точкой

на интервалытакие что

Еслито U(0) может содержать нуль функции f, и

потому мы повторяем ту же процедуру для U(0). Если то мы аналогичным образом повторяем процедуру для V(0). Если же мы имеем или то игнорируем соответствующий подынтервал, так как ввиду (1 микромодуля 24) он не может содержать нуля функции f. Поэтому такой подынтервал исклю­чается из дальнейших вычислений. Описанный итерационный процесс порождает последовательность подынтервалов, содер­жащихся в Х(0) и «подозрительных на наличие нуля функции f». Ширина этих интервалов стремится к нулю, так как она умень­шается вдвое на каждом шаге. Ввиду (5 микромодуля 24) эти постепенно вы­числяемые интервалы сходятся к нулям функции f в интервале Х(0).

Чтобы предотвратить слишком сильный рост количества «по­дозрительных» интервалов, мы можем ввести следующую моди­фикацию. На каждом шаге мы исследуем либо только правую половину интервала, либо только левую. Если на некотором шаге мы имеем для этого полуинтервала Y, то процедура повторяется снова, начиная с интервала (соответственно Таким образом, мы последовательно вычисляем отдельные нули функции f в порядке справа налево (соответственно слева направо) и не сталкиваемся с проблемой хранения большого количества «подозрительных» интервалов.

8.1. А. Методы ньютоновского типа

В этом и следующем разделах мы исследуем интервальные модификации метода Ньютона. Для этого рассмотрим непре­рывную функцию f, имеющуюнуль в данном интервале

для некоторого Пусть

(1)

в граничных точках интервала Х(0). Пусть, далее, т1, т2 — гра­ницы разностных отношений

(2)

Эти границы определяют интервал (Аналогичные соображения справедливы, если предположить,

что Очевидно, что при сделан-

ных предположениях функция f не имеет других корней в Х(0). Начав с исходного локализующего интервала мы вычисляем итерационно новые интервалы , cогласно следующей процедуре:

(3)

где

Этот шаг изображен на рис. 1.

Рис. 1

Не пользуясь интервальными операциями, можно записать итерации (3) в виде

(3')

В обеих формулировках (3) и (3')

обозначает некоторую процедуру выбора вещественного числа т из данного интервала. Часто используют его середину

(4)

Теперь мы перечислим важнейшие свойства последователь­ности итераций

Теорема 1. Пусть f — непрерывная функция, ξ — нуль функции f в интервале Х(0), причем имеют место (1) и (2) для интервала

Тогда последовательность вы-

численная по формулам (3), обладает следующими свойствами:

(5) (6)

либо эта последовательность стабилизируется через конечное число шагов на точке

(7)

Доказательство. (5): Из (2) и следствия 1.п.7.5 получаем

Для k > 1 применяем метод математической индукции.

(6), (7): Предположим, что Теперь если имеет

местото с помощью (3') мы по­лучаем

Если же имеет местото из (3′)

получаем

Случайдоказывается аналогично. Если, однако, то и потому и

Это доказывает (7). Ввиду т1≤ т2

откуда следует

Отсюда и из (5) следует если только элементы

последовательности не вырождаются в точку:

для некоторого k0. Первая часть соотношения (6) следует из

формул (3).

Таким образом, теорема 1 гарантирует, что в ее предполо­жениях последовательные приближениясходятся к нулю ξ функции f, причем каждый из этих интервалов содержит искомый нуль. Если же мы применяем (3), начав с интервала Х(0), такого что то найдется индекс k0, для которого пересечение в (3) пусто. Это легко доказать от противного, ис­пользуя (7) и предположение, что пересечение непусто. Этот итерационный метод в общей постановке был глубоко исследован. Он связан также с итерацией монотонных функций для нахождения неподвижной точки. Анало­гичные процедуры для многочленов были использованы Бауэром еще в 1917 г.

Рассмотрим теперь два уточнения формул (3), возникающие при конкретном выборе точки т. Взяв в качестве m середину интервала, мы получаем следующее утверждение.

Следствие 2. Если в предположениях теоремы 1 сделан выбор

то для последовательности приближений верно неравенство

(8)

уточняющее (7).

Доказательство. В доказательстве соотношения (7) из тео­ремы 1 мы имеем при нашем конкретном выборе точки m(Xw), что

Отсюда получаем (8).

Таким образом, при выборе середины интервала в качестве m(X(k)) нам гарантировано уменьшение ширины локализующего интервала по крайней мере вдвое.

Рассматривались и другие выборы Например,

используется