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

лежащими в X(k-n). Так как получаем, используя

свойство включения интервальной арифметики, что

Так как (S4)—шаг упрощенного метода Ньютона, мы имеем

и потому

(20): Непосредственно следует из определения шага (S1) вместе с (19) и определением шага (S5), где X(k+1) всегда можно вы­брать таким образом, что

где (1/2)≤с< 1.

(21): Можно показать, что всегда имеется такой индекс k1, что для всех шагов с номерами і≥k1 имеется вещественный корень в интервале Доказательство этого

утверждения основано на оценке, показывающей, что если ε(k) достаточно мало, то рk(х) меняет знак либо между х(k) и x(k) + 2ε(k), либо между х(k) и x(k) - 2ε(k) . Таким образом, при оценке порядка сходимости мы всегда можем считать, что шаги (S3) и (S4) выполняются. Из (S4) получаем оценку ширины

Используя (S3) и эту оценку, мы получаем

Так как имеет место соотношение

получаем, наконец, что

и

Окончательный результат получаем, применив теорему 3 из приложения А.

Обсудим теперь еще одно модифицированное семейство ме­тодов локализации. Оно получается путем модификации шага (S2) в случае, когда не существует нужного корня у(k). Чтобы сделать возможным выполнение шага (S4), необходимо тогда определить у(k) иначе. Это делается так.

(S2') Нахождение вещественного корня у(k) многочлена pk(x) в интервалеЕсли такого корня не

существует, то полагаем

(S3') Вычисление локализующего интервала F(k) для величины f(y(k)) с помощью выражения

Непосредственно очевидно, что теорема 6 истинна без каких-либо изменений и для итераций (SI), (S2'), (S3'), (S4), (S5). Дальнейшие предложенные модификацииотносятся к шагу (S1).

(S1') Построение единственного интерполяционного многочлена Эрмита

удовлетворяющего условиям

(Полагаем f(0)=f и считаем, что при mі=0 условия в соответствующей точке отсутствуют.) Теперь вычисляем ин­тервал по формуле

Очевидно, что теорема 6 верна без изменений также и для итераций (S1'), (S2'), (S3'), (S4), (S5).

Среди рассмотренных выше методов вычисления нулей со­держался при п=1 и т0= т1 = 1 интервальный вариант ме­тода секущих. В случае п = 2 и т0 = т1 = т2 = 1 получаем интервальный вариант метода Мюллера.

Рассмотрим пример применения интервального метода се­кущих.

Пример. Рассмотрим функцию

на интервале Х(0) = [0, 1]. Интервальный метод секущих в при­менении к этой формуле порождает приближения, приведенные в табл. 6.

Таблица 6

Кроме описанного выше интервального метода секущих, существует так называемый интервальный метод regula falsi (ложного основания) Этот метод предполагает примерно те же свойства функции f, что и интервальный метод секущих. Он так­же оказывается интерполяционным методом. В противополож­ность описанным ранее методам он использует разделенные раз­ности Ньютона. Опишем его кратко.

Предположим, что функция f дважды непрерывно дифферен­цируема в интервале X и имеет в X единственный и притом простой нуль ξ Далее, мы имеем интервалы Н, К, удовлетво­ряющие условиям

Интервальный метод regula falsi, сокращенно RF, описы­вается теперь так:

при k ≥ 1.

Свойства алгоритма RF резюмированы в следующем утверж­дении.

Теорема 7. Пусть дважды дифференцируемая функция f имеет простой нуль ξ в интервале X. Допустим далее, что выполнены условия

Тогда последовательность {X(k)}, вычисленная согласно про­цедуре RF, либо удовлетворяет условиям

(22) (23)

либо стабилизируется на точке через конечное число шагов.

Для некоторогоимеет место соотношение

(24)

т. е. (см. приложение А)

Доказательство. (22): Доказывается с помощью математи­ческой индукции по k. Для k = 1 утверждение очевидно. Допустим теперь, что для фиксированного k мы имеем Тогда имеет местои х≠xk-1. Рассмотрение интерполяционной формулы Ньютона по­казывает, что

где η находится в интервале, образованном точками x(k), x(k-1) и ξ. Из f(ξ) =0 следует, что

Из предположенияи того, что а также

свойства включения для интервальной арифметики следует, что

откуда в силумы получаем

(23): Следует из построения Z(k) и того, что

(24): Пусть Тогда мы получаем

Из

следует, что

Ввиду

получаем, наконец,

Интервалс центром т(А) удовлетворяет условию

откуда следует соотношение

В применении к предыдущему неравенству оно дает

откуда получается

где Из теоремы 3 (приложение А) мы получаем затем требуемое неравенство для R-порядка.

Используя для данной функции f разделенные разности бо­лее высокого порядка, мы можем построить новые методы, по­рядок сходимости которых тоже лежит между 1 и 2 и которые требуют лишь по одному новому значению функции на каждый шаг итерации.