Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 268
Текст из файла (страница 268)
Члены сходящегося ряда не могут быть суммированы в произвольном порядке. Однако можно переставлять члены абсслююпо сходящегося ряда, те. ряда ~;~~ г аги для которого ряд ~;~~ |аь~ также является сходящимся. Линейность Для любого действительного числа с и любых конечных последовательностей аыаг,аи и Ьг,Ьг,...,Ьи и и и (саь+Ьь) =с~~ аь+~Ьь ь=г и=1 /с=1 Свойство линейности справедливо также для бесконечных сходящихся рядов. Это свойство может использоваться при работе с суммами, в которые входят асимптотические обозначения, например и и Евай))=Е ЕЮ /с=1 /с=1 Арифметическая прогрессия Сумма 2 Ь=1+г+."+ и= 1 называется арпфмегппческой прогрессией и равна сс = -п(а+1) 1 /с=1 ц( г) (А.1) (А.2) В этом уравнении т)-обозначение в левой части применяется к переменной /с, а в правой — к и. Аналогичные действия применимы и к бесконечным сходящим- ся рядам.
1200 Суммы квадратов и кубов Для сумм квадратов н кубов справедливы следующие формулы: п(п + 1) (2п + 1) 6 (А.З) п2(„+ 1)2 (А.4) Геометрическая нрогрессия Для действительного х ф 1 сумма ~хе =1+х+хз+. +хо я=а называется геомешрической прогрессией и равна х"+' — 1 х — 1 я=о (А.5) В случае бесконечного ряда и ~х~ < 1 получается бесконечно убывающая геомет- рическая прогрессия, сумма которой равна 1 я=о (А.б) Поскольку мы считаем, что Оо = 1, эти формулы применимы даже при х = О. Гармонический рвд Для положительного целого п и-е гармоническое число представляет собой 1 1 1 1 1+ — + — + — +..+— 2 3 4 и я=1 1пп+О(1) . (А.7) (Мы докажем это соотношение в разделе А.2.) Интегрирование и дифференцирование рядов Путем интегрирования или дифференцирования приведенных выше формул могут быть получены новые формулы.
Например, дифференцируя обе части уравнения суммы бесконечной геометрической прогрессии (А.б) и умножая на х, мы и йз я=о ~~, 'йз я=о Часть ьлн. Приложения: мателттинесяие осноеи Прае ожение А. суяаяе и ряды 1201 получим для )х! < 1 х 1схь = (1 — х)з (А.З) Суммы разностей (телескопические рады) Для любой последовательности ао, ам ., ., ап справедливо соотношение и (аа — аь с) = ап — ао ~ я=1 (А.9) и — 1 ~(ая — аа+1) = аΠ— ап а=о В качестве примера такого ряда рассмотрим сумму и-1 1 Ей( ) Поскольку каждый ее член можно записать как 1 1 1 lс(/с+1) )с )с+1 ' получаем 1 =1 —— и Произведения Конечное произведение азат ап может быль кратко записано следующим образом: и П" Если и = О, значение произведения считается равным 1.
Мы можем преобразо- вать формулу с произведением в формулу с суммой с помощью тождества (и'1п 1К ~Паь~ = Е)баь. я=1 я=1 ПОСКОЛЬКУ КажДЫй ИЗ ЧЛЕНОВ ам аа,..., ап 1 ПРИбаВЛЯЕтСЯ Н ВЫЧИтаЕтСЯ РОВНО один раз. Такие ряды именуют теаескопнческняси (се!езсорез). Аналогично 1202 Часть Р111. Принижении математические основы Упражнения А.1.1 Найдите простое выражение для ~,",,(2л — 1). А.1.2 * Покажите, используя формулу для гармонического ряда, что 2 ~ 1 1/(2/с — 1) 1п(з/й) + 0(1). А.1.3 Покажите, что для ~х~ ( 1 справедливо соотношение 2 „о Йзх" = х(1+ х)/(1 )з А.1.4 * Покажите, что 2 ~~ о(к — 1)/2" = О.
А.1.5 * Вычислите сумму 2 ~,(21+ 1)хз" для )х( < 1. А.1.6 Докажите, используя свойство линейности суммирования, что 2 ",, 0(Яг)) 0(2',ь 1Яг)). А.1. 7 Вычислите произведение П",, 2 4". А.1.8 * Вычислите произведение П~ (1 — 1/л~). А2. Оценки сумм Имеется множество методов оценки величин сумм, которые описывают время работы того или иного алгоритма. Здесь мы рассмотрим только наиболее распространенные из них.
Математическая индукции Основным способом вычисления сумм рядов является метод математической индукции. В качестве примера докажем, что сумма арифметической прогрессии 1 Й равна -'п(п + 1). Можно легко убедиться, что эта формула верна при и = 1. Сделаем предположение, что эта формула верна длл неюторого и, и дока- Приложение А. Суммы и ряды !ло! жем, что в этом случае она верна и для и + 1: Ей=к) + (и+1) 1=1 !с=1 1 = -п(п + 1) + (и + 1) 2 1 = -(и+1)(и+2) .
2 ~~, ' Зь + 3 «-1 а=о сЗ" + 3"+' ~- + -) сЗ"+ сЗ" + ~з' = а=о (согласно гипотезе индукции) что справедливо при (1/3 + 1/с) < 1, или, что то же самое, при с > 3/2. Таким образом, ~,", Зь = 0(3"), что и требовалось доказать. При использовании асимптотических обозначений для доказательства по индукции следует быть предельно внимательным и осторожным. Рассмотрим следующее "доказательство" того, что 2 ,'1,, !с = 0(и). Очевидно, что 2" 1, !е = 0(1). Исходя из справедливости оценки для и, докажем ее для и + 1: Ей = Ей+(и+ 1) !с=1 а=1 = О(и) + (и+ 1) = О(и+1) . ~ Ошибкар Ошибка в том, что "константа", скрытая в 0(и), растет вместе с п, а значит, юн- стантой не является.
Мы не смогли показать, что одна и та же константа работает для осел и. Почленное сравнение Иногда можно получить неплохую верхнюю оценку ряда, заменив каждый его член ббльшим (иногда для этого можно воспользоваться наибольшим членом). Чтобы воспользоваться математической индукцией, не всегда требуется предположение о точном значении суммы. Индукцию можно применять и для получения границы суммы. В качестве примера докажем, что сумма геометрической прогрессии ~,~", 03 равна 0(3"). Точнее говоря, докажем, что 2,~, 03 < сЗ" для неюторой константы с. В качестве начального условия при и = 0 мы имеем 3" = 1 < с . 1, что справедливо при с > 1.
Считая, что указанная граница о справедлива для п, докажем, что она справедлива для п + 1. Мы имеем Часть сП1 Прииожеиияс математические а<вавы Например, вот как можно оценить верхнюю границу арифметической прогрес- сии (А.1): а и ~~с )е < ~~с и 1с= 1 а=1 г = И В общем случае для суммы 2 ,'ь, аы если положить а = шахг<ь<„аы аь<п а„„„ Е аь < а=о ~~с, аот и=о т и=о 1 ао 1 — т Можно применить этот метод к ряду Сьыг(й/3").
Для того чтобы сумма начиналась с 1с = О, пеРепишем Рад как 2 „о(()е + 1)/Зь+'). ПеРвый член (ао) равен 1/3, а отношение последовательных членов (т) равно (к + 2)/Зь ьг 1 )е + 2 (1+1)/3"+г 3 1+1 2 <— 3 для всех )с > О. Таким образом, имеем Еу= )е а=1 Е к+1 Зь+ г а=о 1 1 3 1 — 2/3 1.
Способ ограничения наибольшим членом — весьма слабый метод, если в действительности ряд можно ограничить геометрической прогрессией. Предположим, что для ряда 2„"„оаь для всех lс > О выполняется аь~г/аь < т, где О < т < 1 — константа. Мы можем ограничить сумму бесконечно убывающей геометрической прогрессией, поскольку аь < аоть, и, таким образом !205 Приложение А. Суммы и роды Распространенной ошибкой при использовании этого метода является то, что из того, что отношение двух последовательных членов ряда меньше 1, делается вывод об ограниченности ряда геометрической прогрессией. В качестве контр- примера можно привести гармонический ряд, который расходится, так как й1ш 9(1бп) н — Кю Несмотря на то что отношение (й+ 1)- и Й-го членов этого ряда равно (с/(л + 1) < 1, ряд расходится. Для того чтобы ряд бьш ограничен геометрической прогрессией, нужно показать наличие константы г < 1, такой, что отношение двух соседних членов никогда не превосходит значения г.
В случае гармонического ряда такой константы не существует, поскольку отношение двух соседних членов может быть сколь угодно близким к 1. Разбиение сумм Еще один способ получения оценки сложной суммы состоит в представлении ряда в виде суммы двух или более рядов путем разделения на части всего диапазона индексов и в оценке сумм частей по отдельности. Предположим, например, что мы ищем нижнюю гРаницУ аРифметической пРогРессии 2„ь Й, дла которой, как мы уже выяснили, верхняя граница равна пз.
Можно попытаться ограничить каждый член суммы наименьшим, но поскольку наименьший член этого ряда равен 1, мы получим в качестве нижней границы и, что слишком далеко от найденной верхней границы и . Лучший результат для нижней границы можно получить, если сначала разбить ряд на две части. Предположим для удобства, что и — четное число.
Тогда н1'2 н ~ й+ а=1 Ь=н(2+1 н/2 н 0 + ~~~ (и/2) Ь= 12+1 ( /2) П( 2) что является асимптотически точной оценкой, поскольку 2 ~ л = 0(пз). В рядах, рассматриваемых в ходе анализа алгоритмов, зачастую можно разбить ряд на части и просто проигнорировать некоторое конечное число начальных членов. Обычно этот метод применим, если каждый член аь ряда 2 ь оаь не Часть 1сШ. Приложенинс математические основы !206 зависит от п. Тогда для любой константы йс > О можно записать ио-1 оь = ~ аь + ~ оь 1=0 и=о и=во = ст(1) + ~ аь, поскольку начальные члены суммы — постоянные величины, и в отдельный ряд выделено постоянное их количество.
После такого разделения для поиска границ РЯда 2;~", ь, аь можно использовать дРУгие методы. Описаннаа методика пРименима и к бесконечным рядам. Например, для поиска асимптотической верхней границы ряда хг Е— и=о заметим, что отношение последовательных членов ряда ()с+ 1)2/2ь+1 (ь+ цг се 2 /2" 212 8 < —, 9' если й > 3. С учетом сказанного разобьем ряд следующим образом. поскольку количество членов первой суммы — константа, а вторая представляет собой бесконечно убывающую геометрическую прогрессию. Метод разбиения ряда может быть применен для определения асимптотических границ в гораздо более сложных ситуациях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
