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

Этот метод имеет те же свойства, что и метод Мура, приве­денный в разд. С. Если не считать некоторых дополнительных арифметических операций, он менее трудоемок, чем метод Мура, так как значение функции и производной приходится вычислять в одной и той же точке x(k). Для метода Мура производную при­ходится вычислять с использованием интервала X(k). Это в об­щем случае требует больше затрат, чем вычисление значений в одной точке x(k). Если интервал F2 вычисляется легко, то ме­тод (15) с р = 1 предпочтительнее метода Мура. Эти резуль­таты полностью справедливы лишь в теории, когда вычисления считаются точными. Если мы хотим гарантировать локализацию нулей при реализации метода на компьютере, то должны учесть влияние погрешностей округления. Это делается путем реали­зации всех действий в виде машинных интервальных операций. В частности, нам требуется вычислять f'(х(k)), используя машин­ную интервальную арифметику. В этом случае метод (15) при р = 1 требует, если не считать нескольких арифметических опе­раций, того же объема вычислений, что и метод Мура. Так как приходится вычислять еше и интервал F2, следует, видимо, пред­почесть метод Мура, если нужно учитывать погрешности округ­ления.

Следует упомянуть, что существует следующий метод:

в предположении, что f дважды дифференцируема. Мы имеем Условия сходимости не приво-

дятся. Если метод сходится, то последовательность d(X(k)) схо­дится к нулю квадратично, если По сравнению с ме­тодом (15) для р=1 мы должны на каждом шаге производить интервальное оценивание второй производной Это уменьшает постоянную сходимость, но не улучшает порядок схо­димости. (То же верно для метода (15) при р= 1, если на каж­дом шаге заменить постоянный интервал F2 на Ис­пользование этого метода на практике, т. е. с учетом погреш­ностей округления при вычисленииувеличивает объем вычислений еще примерно на треть. Так как сходимость не гарантирована, этот метод несколько менее привлекателен. Применяя метод (15), мы должны выбрать конкретный по­рядок р. Отметим еще, что при определенных предположениях метод (15) оптимален при р = 2, т. е. он является методом третьего порядка.

8.5. E. Интерполяционные методы

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

Различные методы определяются с помощью (п+l)-эле­ментного множества неотрицательных параметров

Положим

и допустим, что

откуда следует, что r > 0 Мы хотим найти нyль

функции f, которая предполагается дифференцируе­мой нужное число раз в Х(0).

Теперь находятся интервалы Н и К, такие что имеет место

Чтобы описать очередной (k + 1 )-й шаг итерации, допустим, что мы уже имеем п+1 попарно различных приближений к нулю ξ:

и что последний из найденных локализующих интервалов Х(k) имеет вид

для некоторого Допустим еще, что

После исполнения описываемых ниже шагов (S1)—(S5) определяется улучшенный локализующий ин­тервал — новая аппроксимация X(k+1)

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

удовлетворяющего интерполяционным условиям

(Мы полагаем f(0) = f, и если mi = 0, то условия в точке x(k-i) отсутствуют.) Определяется интервал по формулам

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

Если такого корня нет, то переходим непосредственно к шагу (S5), положив

(S3) Вычисление интервала F(k), локализующего значение

с помощью выражения

(S4) Вычисление улучшенного локализующего интервала по формуле

(S5) Нахождение нового приближения

нового значения

и нового интервала

(Если оказывается, что некоторые из точек

совпали между собой, то можно взять по формулам

с подходящим гарантирующим несовпадение этих точек и соотношение Такой выбор возможен всегда, когда

Наконец, новое значение ε(k+1) выби­рается по формуле

что дает

Следует отметить, что определение локализующих интерва­лов {X(k)} не использует перемен знака рассматриваемой функ­ции. Это означает, что новый локализующий интервал будет вычислен всегда, даже если несколько последовательно вычис­ленных значений функции имеют один и тот же знак. Будет также показано, что шаги (S3) и (S4) могут быть пропущены лишь конечное число раз. Не требуется, чтобы локализующий интервал X(i) содержал какое либо из предыдущих приближе­ний, кроме х(i). Свойства определенного выше алгоритма собраны в следующей теореме.

Теорема 6. Пусть f — вещественная функция, имеющая нуль ξ, для которого задан локализующий интервал

такой что

Пусть далее для ξ заданы попарно различные приближения

и производные функции f удовлетворяют условиям

и

для интервалов Н, К и всех х в интервале Х(0) при заданных неотрицательных параметрах

Тогда для итераций, заданных шагами (S1—S5), верны следую­щие утверждения:

(19) (20)

или после конечного числа шагов последовательность стабили­зируется на точке [ξ, ξ].

R-порядок итераций (S1) — (S5) (см. приложение А) (21)

равен где s — единственный

положительный корень многочлена

Доказательство (19): В силу (S1) мы имеем. Остаточный член интерполяционной формулы Эрмита дает

где число η лежит в интервале, образованном точками