§ 10. Качество оценок

83

получаются оценки числа итераций для классических методов (ал­горитмов) приближенного решения уравнений. Вспомним две такие оценки.

Пусть корень уравнения /(х) = 0 разыскивается на отрезке [а,Ъ], на котором функция /(х) непрерывна, /(а)/(Ь) «SO. Ошибка не долж­на превышать данного е > 0. При е^О и фиксированных f(x),a,b число итераций метода делений пополам есть

log,- + 0(1). (9.15)

Метод же Ньютона (касательных) требует

О flog log -) (9.16)

s

итераций при соблюдении ограничений на функцию /(х), обеспечи­вающих сходимость метода.

§ 10. Качество оценок

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

Пример 10.1. В примере 9.1 для сложности Т_Е{а_г) по числу деле­ний алгоритма Евклида мы легко получили верхнюю оценку а_ъ а за­тем, после некоторых усилий, пришли к логарифмической верхней оценке (9.6). Отвлекаясь от значений констант, перейдем от (9.6) к

r_E(a₁) = 0(loga₁). (10.1)

Нами пока не доказано, что оценка (10.1) является точной, и, как следствие, что не верна, скажем, оценка O{\f\oga₁) или CKlogloga^) и т.д. Чтобы доказать точность (10.1), достаточно подобрать для ал­горитма Евклида последовательность входов

{а^,а^), (а™,а™), ...

таких, что последовательность а^ (последовательность размеров вхо­да) неограниченно возрастает и С_Е(,а^\ а^) = f2(loga^ⁿ⁾) при п—><*>; тогда, очевидно, будем иметь Т_Е(а^) = U(loga^).

Фактически, нам нужна последовательность таких входов возрас­тающего размера, для каждого из которых алгоритм Евклида ра­ботает медленно. Подойдет, например, последовательность входов

84 Глава 3. Оценивание числа шагов (итераций) алгоритма

UWbFJ, п = 0,1, ..., где Fq,^,^, ... —числа Фибоначчи, определяе­мые равенствами F₀ = О, F_x = 1 и правилом «каждое следующее чис­ло равно сумме двух предыдущих», т. е. рекуррентным соотношением Fn+2 = Fn+i +Fn. Из определения чисел Фибоначчи следует, что при­менение алгоритма Евклида к F_n+1,F_n при п ^ 1 требует п делений (все частные будут равны единице), поэтому C_E(F_n+1,FJ = п.

По индукции доказывается, что для всех неотрицательных п спра­ведлива формула Бине:

J7 -_к(фл_(_ф)-л) (Ю.2)

V5

где

ф= ^{1 + A/g} = 1,61803...

(деление отрезка в отношении 1 : ф называют золотым сечением). Так как ф > 1, то из (10.2) получаем

0" = _A/5F_n(l+o(l)), (10.3)

и, поскольку log₀(1 +о(1)) = о(1), с помощью логарифмирования (10.3) по основанию ф имеем

СеС^п+i» Рп) = п = log<p F_n + 0(1) = n(logF_n),

откуда следует, что оценка (10.1) точная. Мы докажем более сильное утверждение:

Т_Е{а₁)>^\о%_фа₁+_Г, (10.4)

где у— некоторая константа. Это вместе с (10.1) даст

r_E(a₁) = e(loga₁). (10.5)

Приступая к доказательству, мы перейдем от функции C_E(a₀,a_i), имеющей два аргумента, к функции одного аргумента. Каждому вхо­ду (a_n, сь), a_n ^ сь > 0, мы сопоставим рациональное число г = — ^ 1, которое однозначно определяет число шагов алгоритма Евклида для

a_n, а-.. (Пусть - = ^, апиа, взаимно просты, a_n = ua_n, сь = ua-i; то- uj i _Q^ a_t

гда остатки a₂, a₃, ... и a₂, a₃, ..., возникающие в ходе применения ал­горитма Евклида к а₀,а_г и соответственно к а₀,а_г, отличаются лишь множителем и.) Будем обозначать это число шагов через С'_Е{г). Таким

образом, если г = ^, то С'(г) = C_E(a₀,a_i).