AOP_Tom1 (1021736), страница 15
Текст из файла (страница 15)
Итак, выполняя только простые операции над суммами, мы получили важные соотношения (13)-(15). В большинстве учебников эти формулы просто приводятся, а затем доказываются по индукции. Индукция — это, конечно, цдевльный способ доказательства, но он не дает никакого объяснения по поводу того, каким же образом кому-то удалось придумать саму формулу, если исключить возможность некоего внезапного озарения. Занимаясь анализом алгоритмов, мы будем сталкиваться с сотнями сумм, которые не соответствуют ни одному из известных образцов.
Но, выполняя над этими суммами приведенные выше операции, мы во многих случаях сможем найти решение и без догадок. Пользуясь введенным обозначением, можно оригинальным способом вывести правило (Ь) из правил (а) и (с): ~~. арН) = ~~.арВФ(РО))] н)рО)) у а; [гС(1) ] [1 = р(у) ] а;[В(1)] ~ [1 = р(у)]. (18) Сумма по у равна 1, когда В(1) истинно, если предположить, что р — это перестановка в области суммирования, как требуется в (5); таким образом, остается сумма 2 ', а,(В(1)], которую можно записать как ~',нн) а,. Соотношение (5) доказано. Если же р не является перестановкой в области суммирования, то значение суммы 2 н)р,у) ар)у) выражается формулой (18). Самым известным частным случаем обозначения (16) является так называемый символ Кронекера, ) 1, если 1 = у, 10, если 1 ~у, Для произведений величин, как и для сумм, тоже существует краткая запись: П яО) Так обозначается произведение всех а, для которых целое число у удовлетворяет соотношению Л(у).
Если ни одного такого целого у не существует, то по определению произведение равно 1 (а не О). Правила (Ь), (с) и (6) справедливы для произведений П так же, как и для сумм 2,, если внести в ннх необходимые коррективы. Несколько примеров, в которых необходимо выполнить операции над произведениями, приводится в упражнениях (они даны в конце раздела).
И в завершение этого раздела приведем еще одно обозначение кратного суммирования, которое часто бывает очень удобным. Для одного или более соотношений, зависящих от нескольких индексов суммирования, можно использовать один знак суммы 2 '; это означает, что сумма берется по всем комбинациям индексов, удовлетворяющим заданным условиям, например а;, = ~ ~а„", ~~~ ~~ ап = ~~~ аб.
0<в<п 0<Э<п 0<00<п 0<у<1<п 0<1<п 0<)<а введенный Леопольдом Кронекером (Ьеоро!6 Кгопесйег) в 1868 гоцу. Более общие обозначения типа (16) были введены К. Ю. Айверсоном (К. Е. 10егвоп) в 1962 году, поэтому (16) часто называют обозначением Анверсона. (См. Р. Е. КппФЬ, АЛХМ 99 (1992), 403-422.] В этой записи ни одному индексу не отдается предпочтение над другим. Выведем с ее помощью соотношение (10) новым способом я ! аб = ~ ай[1<1<и][1<5<!] = ~ ~а!5[1<у<и][!<!<и! !=1 г=! °,г ! ! я я а;., воспользовавшись тем, что [1<! <п][1<5 <!]=[1<? <! <п]=[1<у<и][у <!<и].
Аналогично более общая форма соотношения (9) следует из тождества Приведем еще один пример, который демонстрирует удобство суммирования с несколькими индексами: (22) а., г„. l!е" зг г,» -! ао Здесь переменная а имеет и подстрочных индексов, например для и = 5 это выражение примет следующий вид: пмгм + пыыо + огггоо + аз! гоо + пзгеоо + пыооо + о!оооо (См. замечания о разбиении числа в разделе 1.2.1.) УПРАЖНЕНИЯ (часть 1) 1.
[01] Что означает запись 2 „«,„аг для и = 3.14? 2. [!0] Не пользуясь знаком суммы 2', запишите зквивалект выражения О<я<! а также выражения 1 2пг+ 1 о< г<! 3. [15] Объясните, почему несмотря иа правило (Ь) результаты предыдущего упражнения различны. 4.
[!0] Не пользуясь знаком "~ ", запишите эквиваленты каждой части равенства (10) как суммы сумм для случая и = 3. б. [НМкО] Докажите, что правило (а) справедливо для произвольного бесконечного ряда при условии, что этот ряд сходится. 6. [НМвО] Докажите, что правило (4) справедливо для произвольного бесконечного ряда при условии, что сходятся любые три суммы из четырех. 7.
[НМОО] Покажите, что есви с — любое целое число, то 2.'р а = 2 л, Н а,, даже если оба ряда бесконечны. 8. [НМ25] Приведите пример бесконечного ряда, для которого ррвеиство (7) ложно. 9. [05] Справедливо ли доказательство формулы (14) лля п = — 1? 10. [05] Справедливо ли доказательство формулы (14) для п = -2? 27. [МЗ0) Обобщите результат упр. 1.2.1 — 9, докыав неравенство П( -а-)'- -Е-1 «=! з ! [1»»)(з «<»)=ф»с)ф«<«г)+ з «« -"«<)ьг -*.«> «=! «=! / !<1<в<» [У этого тол«дества есть вазкный частный случай: если положить а! = «в«, Ь! = 3«, л« = ш«з 0- = з-, то для произвольных комплексных чисел ш«, ..., «в, з!, ..., з выполняется 1ивенсгво Члены [ш«зз — мзз«[~ неотрицательны, поэтому знаменитое нсравенсп«вв Коши-Шварца является следствием формулы Бине.[ 21.
[МЗ0) С помощью формулы Бине выразите сумму 2 '!«. „„(и! - из)(е! — оз) через » Я"»! и«е«, 2 ., и! и ~1»! о!. 22. [МЗ0] Докажите, что » ПЕаз= Е а;„.. а.... «=! =! «<«,,...» < ь ЗЗ. [МУО) Однажды вечером д-р Матрица открыл формулы, которые м«пкно очи!ать еще более замечательными по сравиенюо с формулами, приведенными в упр. 20: =О, с) (с — а)(с — Ь) + с) (Ь вЂ” а)(Ь (а — Ь)(а— — О, + с) (с — а)(с — Ь) (а — Ь)(а— с) (Ь вЂ” )(Ь + Ь + сз + с) (Ь вЂ” а)(Ь с) (с — а)(с — Ь) (а — Ь)(ив Ьз + з з + (о — Ь)(» — ») (Ь вЂ” а)(Ь вЂ” с) (с — а)(с — Ь) при условии, что О < ау < 1.
29. [МЙЗ) Найдите простую формулу для Пз=г (1 зй ). э 29. [МУ0! (а) Выразите сумму 2'", е ~'. е 2„„»еаза«аз, используя способ записи с несколькими индексами, который приведен в конце данного раздела. (Ь) Выразите эту лсе сумму через 2 ", а„ЯУ ра, и ЯУ ва; [см. формулу (13)). ° ЗО. [МЗУ) (Ж. Бине (Л. Вше!), 1812.) Не пользуясь индукцией, докажите тождество Докажите, что эти формулы являются частными случаями более общего закона.
Покажи- те, что если х>, хг,...,х — различные числа, то О, еслиО<г<п — 1> ~()х,"/ П (х,— хг))= 1, если г=п — 1; >'«г '«> ><гб«/ в,,"«, х „если г = и. Тй2 34. (Мйб) Для произвольного х и 1 < т < и докажите, что П>« гг (х Ь>г г) и„„.„„( — ) Например, если и = 4 и т = 2, то х(х — 2Нх — 3) (х+ Ц(х — Ц(х — 2) (х+ 2)х(х — Ц (х+ 3Нх+ Цх ( — Н-2Н-3) (1Н- Н вЂ” 2) (2Н1Н-Ц (ЗН2НЦ 33. (НМ30) Запись вира> > а> применяется для обозначения точной верхней грани элементов а>; при этом используется тот же принцип, что и в случае применения знаков "2,'" и «П". (Если К(у) выполняется только для конечного числа >, то вместо записи виряб > а, часто используется записыпахл>» а>.) Покажите, как нужно видоизменить правила (а), (Ь), (с) и (>1) для выполнения операций с этим обозначеииель В частности, рассмотрите аналог правила (а) (виРл>О а;) + (виРвб> 6>) = виРлн>(виРвн>(а, + 6,)) и дайте соответствующее определение вирл> > а„для случая, когда й(у) не выполняется ни длл одного у.
УПРАЖНЕНИЯ (часть 2) Матриии и определители (детерминанты). Приведенные ниже задачи предназначены для читателя, который имеет хотя бы общее представление об определителях и элементарной теории натрии Детерминант можно вычислить, комбинируя определенным образом следующие операции: (а) вынесение общего множителя из строки или столбца; (Ь) прибавление кратного одной строки (или столбца) к другой строке (или столбцу); (с) разложение по элементам какой-либо строки (или столбца). Простейший и наиболее часто используемый вариант операции (с) Относится к случаю, когда вее элементы первой строки или первого столбца — нули, за исключением элемента в левом верхнем углу, который равен +1.
Тогда первая строка и первый столбец просто вычеркиваются и вычисляется определитель оставшейся части матрицы, а это уже определитель меньшего порядка. В общем случае под алгебраическим дополнением элемента аи определителя порядка и х и понимают помноженный иа (-Ц'+> определитель порядка (и — Ц х (и — Ц, который получается в результате вычеркивания той строки и того столбца, на пересечении которых находится элемент аи.
Тогда опРеделнтель матРицы Равен 2, а„. алгебРаическое дополнение (аи), причем один из индексов (г либо у) фиксируется, а суммирование выполняется по другому индексу, который пробегает значения от 1 до и. Если (Ьи) — это матрица, пбратмал матрице (аи), то каждый ее элемент Ьи равен алгебраическому дополнению а>, (а ие аи), деленному на определитель всей матрицы. ь 4б. [Мйб) Матрасва ГельберавсЬ которую яногда называют сегментом размера и х я (бесконечной) матрицы Гильберта,' — это матрица, элементы которой имеют следующий вядс асв = 1/(в+ в — Ц. Покажите, *сто матРица ГнлъбеРта Явлаетса частным ОвУчаем матРнцы Коши; найдите для все обратною матрацу; покажите, что все элементы этой обратной матрицы являются целыми числами и что сумма всех элементов обратной матрицы равна пв. [Замечание.
Матрицы Гильберта часто использукгсся для тестирования раэличвьпс алгоритмов, в которых выполняются операции над матрицами, так как, ва-нервых, они чисаенно неустойчивы относительно преобразований и, во-вторых, для них взвестны обратные матрицы. Но было бы ошибкой сравнивать взаесваную обратную матрипу, заданную в этом упражнении, с овсчасоонной обратной матрицей к матрице Гильберта, поскольку, преясде чем находить обратную матрицу, необходимо оссруглять элементы первоначаль ной матрицы. В результате нз-за уже уаомннутой неустойчивости обратная матрица к округлеяной матрице Гильберта будет несколько отличаться от точного варианта обратной матрицы.
Элементы обратной матрицы являются целыми числами, т. е. их не нкпо округлять, поэтому обратная матрица определена точна и можно попытаться ее обратвпь. Но заметам, что обратная матрипа так же неустойчива, как к первоначальная. Кроме того, элементами обратной матрицы являются достаточно большие чнсла.] Для решения данной закачн необходимо знание основных фактов о факторвалах н бяномиальных коэффициентах, о которых будет говориться в разделах 1.2.5 и 1.2.б.
ь 46. [МЯО) Пусть А — матрица размера ва х н, а  — матрица размера и х т. При условии, что 1 ( ус, ув,...,у, < и. обозначим через Аввв,...в матрнссу размера пв х пв, состояшую иэ столбцов ус,...,ум матрацы А, а через Вв,б — матрицу размера нв х яв, состоящую из строк ус,...,у матрацы В. Докаясите тозмдестоо Бине-Коши б в(.4В) = '5 4 с(А,„,,„) йев(Вл„з„). 1<зв<ув« "в < (Обратите внимание на частные случаис (в) т = и, (й) ив = 1, (йв) В = Ат, (во) вл > н, (т) пв = 2.) 47. [М37) (К. Кратгензвлер (С. КгавгевсЬа)ег).) докажите, чвп (( +Чв)( +Чз) (к+рс)(х+Чз) (х+рв)(х+рв) 1 (У+Чз)(У+Чз) (У+Рв)(У+Чз) (У+Рс)(У+Уз) (к+Чв)(э+Чз) (э+рв)(з+Чз) (э+рс)(о+рв) = (х — у)(х — з)(у — з)(рс — Чв)(рв — Чз)(рз — Чз), и обобщите это равенство длк определителя матрицы размера и х и, эавислскего от Зя — 2 переменных хс, ..., х„, рс, ..., р„в, Чв, ..., Ч„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
