ПРИЛОЖЕНИЕ С. ВЕРНЫЕ ЦИФРЫ И ВЫЧИСЛИТЕЛЬНАЯ ЭФФЕКТИВНОСТЬ

До сих пор мы рассматривали эффективность использования информации ИФ. При определении этой характеристики не учитываются ни стоимость вычислений значений функции и ее производных, ни общее количество элементов информации, необходимое для достижения заданной погрешности нахождения корня. В этом приложении мы построим характеристику «вычислительной эффективности», учитывающую эти показатели (см. также Ehrmann [С-1]).

Пусть приближение к корню а имеет верных цифр,

(все логарифмы в этом приложении десятичные). Тогда

причем мало. Предположим, что последовательность имеет порядок . В этом случае

где С — константа асимптотики погрешности. Без ограничения общности можно считать, что . В дальнейших рассуждениях настоящего приложения используем вместо приближенные соотношения

Из и имеем

а из

где оператор восходящей разности Заметим, что если то даже при возможен рост числа верных цифр на каждой итерации. В последнем случае по.

Предположим теперь, что и выведем критерии, позволяющие сравнивать вычислительную эффективность двух

произвольных ИФ, которые в дальнейшем обозначаем об. Будем исходить из допущения, что стоимость одной итерации определяется только стоимостью вычисления новых значений а стоимость «комбинирования» этих значений в процессе вычисления очередного приближения к корню пренебрежимо мала. Пусть погрешности ИФ а и удовлетворяют уравнениям

Положим Тогда

Общие решения этих разностных уравнений имеют вид

Предположим, что вычисления с использованием обеих ИФ начинаются из одного и того же начального приближения. Отсюда следует, что То. Пусть вычисления оканчиваются, как только у очередного приближения к корню окажется заданное количество верных цифр. Тогда в момент прекращения вычислений имеем для некоторых номеров а связь между количеством потребовавшихся итераций определяется уравнением

Пусть стоимость одной итерации для ИФ а равна а для . Тогда суммарные стоимости произведенных вычислений определяются соотношениями откуда

В общем случае уравнение не позволяет получить достаточно простую оценку для отношения Однако в одном важном частном случае это отношение определяется из уравнения точно. Пусть а — ИФ метода секущих, Ь - ИФ Нъютона; тогда и уравнение принимает вид

Отсюда сразу получаем

После подстановки в имеем

Пусть стоимость вычисления одного значения равна единице, а стоимость вычисления значения производной при равна Тогда из получаем

Из последнего соотношения видно, что если стоимость вычисления первой производной то ИФ метода секущих более «экономна», чем ИФ метода Ньютона. Этот результат был получен в работе Jeeves [С-2].

Вернемся к общему случаю. Предположим, что второе слагаемое левой части уравнения пренебрежимо мало по сравнению с первым слагаемым; например, это имеет место, если обе константы близки к единице. Тогда снова получаем

Пусть, например, а обозначает (смысл обозначений см. в п. 5.1.3). В этом случае

и если , то экономнее, чем В частности, это имеет место в случае, когда стоимости вычислений равны между собой.

Уравнение указывает на целесообразность определения вычислительной эффективности применительно к функции соотношением

где стоимость вычисления значения производной Если объем информационного запроса равен одно и то же для всех то вычислительная эффективность не зависит от и определяется равенством

Островский (Ostrowski [С-3, р. 20]) использует уравнение для определения индекса эффективности ИФ. Индекс обладает следующим свойством: если то

Коснемся вопроса относительной стоимости вычисления производных 0, для различных функциональных классов.

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

В работе Traub, Sherman [С-4] отмечалось, что при решении набора однотипных уравнений может оказаться целесообразным сначала получить оценку стоимости вычисления производных для «типичного» значения аргумента, после чего программным способом выбрать для решения всего набора уравнений ИФ с наибольшей вычислительной эффективностью.

Если функция удовлетворяет дифференциальному уравнению второго порядка, то вторая производная может быть вычислена непосредственно из уравнения (см. Hofsommer [С-5] и Wynn [С-6]. В этом случае ИФ будет эффективнее, чем

Выше было показано, что одноточечные ИФ с памятью всегда содержат члены, числители и знаменатели которых стремятся к нулю. Было бы весьма полезно ввести понятие, аналогичное понятию «объем информационного запроса», которое учитывало бы трудоемкость вычисления этих членов. Пока это не сделано.