Д. Кнут - Искусство программирования том 1 (1119450), страница 14
Текст из файла (страница 14)
Запись из приведенного выше примера будет иметь смысл, только если либо т', либо !т (но не оба) не является немым индексом, т. е. имеет самостоятельное значение. В основном, мы будем использовать запись (2) только тогда, когда сумма конечна, т. е. когда только конечное число значений т удовлетворяет хгЦ) и ат т- О. Чтобы найти бесконечную сумму, например ат = ~~~ а = ат + аэ + аз + Е которая содержит бесконечно много ненулевых слагаемых, необходимо применить методы вычислений.
В этом случае выражению (2) мы будем придавать следующий смысл: ~"=(- "Н - ") нщ н(,) п(г) о<у<к — <у<о (при условии, что оба предела существуют). Если же хотя бы один предел не существует, то бесконечная сумма расходипгся; зто означает, что вычислить ее нельзя. В противном случае (если оба предела существуют) сумма является сходящейся.
Если под знаком «~ " содержится несколько условий (больше одного), как в формуле (3), значит, должны выполняться все условия одновременно. Очень важное значение имеют четыре простые алгебраические операции над суммами; знакомство с ними позволяет найти решение многих задач, позтому сейчас мы займемся обсуждением этих операций. а) Распределиглельннй закон для произведений сумм: Чтобы понять этот закон, рассмотрим частный случай: г а;) ( ~~ Ь ) = (аз + аз)(Ьз+ Ьг+ Ьз) г<м = (азЬз + адЬг + аз Ьз) + (агЬз + агЬг + агЬз) Обычно скобки в правой части равенства (4) опускают и двойную сумму, например г) ( ~ я,.
а;,), записывают в виде ~ н(, ~ .(,) акн Ъ) Залзена индекса: аг = ~ ау = ~~ ао(ян аг = зй)< а з= ~ а (6) г<1<н-~-1 з<г-зйн Советую читателю внимательно изучить этот пример. Замену у на р(у) можно выполнить не для всех бесконечнмхгсумм. Такая замена всегда возможна, если р(~) = охи (как в примере, приведенном выше), но в других н(г) нб) н(о(У)) В этом равенстве представлены два вида преобразований. В первом случае просто происходит замена индекса суммирования г' на у. Второй случай представляет больший интерес.
Здесь рЦ) — зто функция от у, задающая некоторую переспзановку на области суммирования; точнее — для каждого целого з', удовлетворяющего соотношению Л(з), должно существовать единственное целое число у', удовлетворяющее соотношению р(у) = з. Данное условие всегда выполняется в следующих важных случаях: р(д) = с+ ) и р(у) = с — у, где с — целое число, не зависящее от ). Эти случаи важны потому, что на практике они встречаются чаще всего, например ситуациях необходимо принять некоторые меры. (Например, см.
Т. М. Аров(о!, Магйеша((са) Ала)ув)в (Неад1пя, Маявл Адд|воп-ЪЧез!еу, 1957), Саар(ег 12. Достаточным условием справедливости соотношения (б) для любой перестановки целых чисел РЦ) ЯвлЯетсЯ сходимость 2 л ) ]а ~.] с) Изменение порядка суммирования: аб = ~ ~~~ асо (7) Щг) Я(1) ЯВ) л(1) Давайте рассмотрим очень простой частный случай этого равенства: а,; = ~ (ап +ам), Я(0 1=1 н(() а,, = ~ ап + ~а,г.
уеп л(г) л(г) л(г) Согласно (7) правые части данных соотношений равны, т. е. ~~> (Ь, + с;) = ~~ Ь, + ~ с(, 1$(е) и(() л(й (8) где Ь; = ап, а с; = аиь Операция изменения порядка суммирования очень полезна, так как часто простое выРажение длЯ сУммы 2л ) а,, известно, а длЯ сУммы 2 вб) аб — нет. Необходимость в изменении порядка суммирования возникает также в более общем случае, когда соотношение 5()) зависит и от (, и от 1. В подобной ситуации его можно обозначить через 5((,1). Изменение порядка суммирования всегда можно выполнить, по крайней мере теоретически, следующим образом: а; = ~~~ ~~ асб л(г) в(иу) я'(г) л'(ыг) (9) о Ф о и а( =~~а;,.
(10) г=-1 1=1 [Замечание. Как и в случае (Ь) (замена индекса), операция изменения порядка суммирования не всегда справедлива для бесконечных рядов. Если ряд абсолютно сходитсл, т. е. если сходитсЯ х ~л () ') )в,. ]а;,], то можно показать, что Равенства (7) и (9) верны. Кроме того, если одно из соотношений В(1) и 5(у) определяет конечную сумму в (7) и каждая бесконечная сумма сходится, то операция изменения порядка суммирования также законна. В частности, для сходящихся бесконечных сумм соотношение (8) всегда справедливо.] где 5'Ц) означает, что "существует целое (, такое, что справедливы как В(1), так и 5((,у)"; а В'((, )) означает, что "верны как Л((), так и 5((, г)".
Например, если вычисляется сумма 2 ',".ы, 2 '., а;,, то условие 5'(г) звучит так: "существует целое г, такое, что 1 < 1 < и н 1 < г < г", т. е. 1 < г < и, а Л'((,у) превращается в условие 1 < 1 < и и 1 < г < г, т. е. ) < 1 < и. В результате получаем й) Манивуллг(ии обласшью суммирования. Если В(у) и 5(у) — произвольные соотношения, то имеем ~аг+~~1 а = ~~~ а + ~~ а. Я(1) 5Ц) Я(21 нлн 5(гй Я(у) н 5(1) Например, если 1 < пг < и, то Е +Е =(Е )т1<У<не то<1<о 1<1<о (12) Здесь область "В(у) и о'О)н просто принимает вид "у = пг", поэтому вторая сумма свелась только к одному слагаемому на ". В большинстве случаев равенства (11) или соотношения Л(г') и о'Ц) одновременно выполняются только для одного-двух значений у либо вообще не существует таких у, лля которых справедливы и Д(у), и Щ). В последнем случае вторая сумма в правой части равенства (11) просто исчезает.
А теперь, когда мы изучили четыре основных правила выполнения операций над суммами, давайте рассмотрим примеры их использования. Пример 1. а = ~ ~ау + ~ ~а согласно правилу (с() О<1<о 1 нечетное о<1< гчетное о<1<о агте1 согласно пРавилУ (Ъ) Ойгг--1< 21+1 нечетное О<ггйн 21 четное агу + огтч.1.
Е о<1<нД о<1<о(г На последнем шаге выполняется упрощение соотношений, находящихся под знаками суммы. Пример 2. Пусть о1 = ~~1 ~ аго, = ~~1 ~ ~а;а согласно правилу (с) (см. (11))) (=о у=о а;ат согласно правилу (Ь). г=о 1=» Здесь выполнена замена 1 на г' и использован тот факт, что а;а, = агат. Обозначая последнюю сумму через 52, имеем согласно (8) а;а; + а1а1 согласно (8) 2 22 п 12'Π— ч, а,) ~ ~а.) + ( ~~ а~) согласно правилу (а) 2=0 2=0 2=0 согласно правилу (Ъ). аа,= — 2 а; + ~~ а, (13) Пример 3 (Су2<ма геометрической прогрессии). Предположим, что х ~ 1, п > О. Тогда по определению (2) =а+ ~ ах1 согласно правилу (с() 1<2<в =а+х ~ ~ах' согласно частному случаю правила (а) согласно правилу (Ъ) [см.
(6)[ 0<1<в-1 = а + х ,'2 ах1 — ах" согласно правилу (21). 0(1(22 Сравнивая первое и последнее выражения, получаем (1 — Х) ~~2 ОХ' = а — ОХ"т', (14). В /'2 в 22, = 2, + ы = х'(О,, 2х,.;) 1=0 1=0 2 22 22 и аа.+~~ аа; 2=0 2=0 2=0 Таким образом, мы получили важное тождество: а+ах+ +ах" = ~ ~ах2 а<1<п 1<1<п = а+х т ах1 О<1<Я отсюда следует важная формула ах' = а( 0<2<в согласно правилу (21) [см.
(12)) Пример 4 (Сумма арифметической прогрессии). Предположим, что и > О. Тогда а + (а+Ь) + ° + (а + пЬ) Е (а+ Ьу) по определению (2) 0<1< п (0+ Ь(п — у)) по правилу (Ь) 0<п-э<п (а+ Ьп — Ьу) в результате упрощения 0<1<0 ~ (2а+ Ьп) — ~ (а+ Ь1) согласно (8) 0<1<п 0<1<в = (и+ 1)(2а+ Ьп) — ~ (а+ ЬЯ, 0<1<п так как первая сумма — это просто (п+1) одинаковых слагаемых, не зависящих от ~. Теперь, приравнивая первое и последнее выражения и деля их на 2, получаем (а + Ц) = а(п + 1) + 1 Ьп(п + 1).
(15) (( 1, если утверждение истинно; утверждение] = ! ( О, если утверждение ложно, (1б) Например, можно записать ад = ~ а,(Л(у)) Ябй 1 (17) Обратите внимание, что в правой части суммирование производится по всем целым у, и это ничего не меняет, поскольку те слагаемые, для которых утверждение Я(у) ложно, просто равны нулю. (Мы предполагаем, что а, определены для всех у.) А это равно и + 1, умноженному на 1'(а + (а + Ьп)), что можно интерпретировать как количество слагаемых, умноженное на среднее первого и последнего слагаемых. Итак, выполняя только простые операции над суммами, мы получили важные соотношения (13)-(15). В большинстве учебников эти формулы просто приводятся, а затем доказываются по индукции.
Индукция — это, конечно, идеальный способ доказательства, но он не дает никакого объяснения по поводу того, каким же образом кому-то удалось придумать саму формулу, если исключить возможность некоего внезапного озарения. Занимаясь анализом алгоритмов, мы будем сталкиваться с сотнями сумм, которые не соответствуют нн одному из известных образцов.
Но, выполняя над этими суммами приведенные выше операции, мы во многих случаях сможем найти решение и без догадок. Многие операции над суммами и другие формулы можно значительно упростить, если использовать следующее обозначение: Пользуясь введенным обозначением, можно оригинальным способом вывести правило (Ъ) из правил (а) и (с): ир80 = ~ арбй [В(Р(ф))] н(рбй э а, [гг(г)] [1 = р(у)] а; [1г(1)1 ~~~ [1 = рЦ)] . (18) Сумма по у' равна 1, когда В(г') истинно, если предположить, что р — это перестановка в области суммирования, как требуется в (5); таким образом, остается сумма,' '„.
а, [Н(г)], которую можно записать как ~ н 0 аь Соотношение (5) доказано. Если же р не является перестановкой в области суммирования, то значение суммы ~н< 09 ар~0 выражается формулой (18). Самым известным частным случаем обозначения (16) является так называемый символ Кронекера, ( 1, ~~[0, если 1~у, введенный Леопольдом Кронекером (1.еоро!б Кгопес1сег) в 1868 году. Более общие обозначения типа (16) были введены К.
Ю. Айверсоном (К. Е. 1гегвоп) в 1962 году, поэтому (16) часто называют обозначением Айверсона. [См. Р. Е. Книгам, АММ 99 (1992), 403 — 422.] Для произведений величин, как и для сумм, тоже существует краткая запись: Ябй об= ~~~ а;", ~~~ ~ а, = ~ ~аьо 0(1<п 0(1<п 0510(п 0<151<п 0(1(п 0<15~ Так обозначается произведение всех аз для которых целое число ~' удовлетворяет соотношению В(у). Если ни одного такого целого у не существует, то по определению произведение равно 1 (а не О). Правила (Ъ), (с) и (г1) справедливы для произведений П так же, как и для сумм 2 „ если внести в них необходимые коррективы.
Несколько примеров, в которых необходимо выполнить операции над произведениями, приводится в упражнениях (они даны в конце раздела). И в завершение этого раздела приведем еще одно обозначение кратного суммирования, которое часто бывает очень удобным. Для одного или более соотношений, зависящих от нескольких индексов суммирования, можно использовать один знак суммы 2 ,'; это означает, что сумма берется по всем комбинациям индексов, удовлетворяющим заданным условиям, например В этой записи ни одному индексу не отдается предпочтение над другим. Выведем с ее помощью соотношение (10) новым способом аб — — ~~1 об[1<1<и][1 <2 <1] = ~~1 об[1<у <и][у <1<и] 1=1 1=1 ьу 13 и в а1 воспользовавшись тем, что [1 < 1 < и] [1 <? < 1] = [1 < у < 1 < и] = [1 <? < и] [у < 1 < и], Аналогично более общая форма соотношения (9) следует из тождества [тг(1)] [о(1,0)] = [л(1) и л(г,,у)] = [о"(у)1[В~(1,0)] (21) Приведем еще один пример, который демонстрирует удобство суммирования с несколькими индексами: а..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
