Д. Кнут - Искусство программирования том 1 (1119450), страница 15
Текст из файла (страница 15)
Е (22) и+ ю пв- вэ >О Здесь переменная а имеет и подстрочных индексов, например для и = 5 это выражение примет следующий вид: П11111 + О21110 + И22100 + Пз!100 + О32000 + П41000 + 1130000. (См. замечания о разбиении числа в разделе 1.2.1.) УПРАЖНЕНИЯ (часть 1) 1. [О1] Что означает запись 2 1«„„а1 для и = 3.14? 2. [10] Не пользуясь знаком суммы 2, запишите эквивалент выражения О<к<3 а также выражения 1 2пх+ 1 О< ><3 3. [12] Обаясните,почему несмотря ва правило (Ь) результаты предыдущего упражнения различны. 4. (10) Не пользуясь знаком "2,", запишите эквиваленты каждой части равенства (10) как суммы сумм для случая и = 3.
3. [НМ20] Докажите, что правило (а) справедливо для произвольного бесконечного ряда при условии, что этот ряд сходится. 6. (НМ20] Докажите, что правило (й) справедливо для произвольного бесконечного ряда при условии, что сходятся любые три суммы из четырех. т. [НМ22] Покажите, что если с — любое целое число, то 2,'я1 102 = ~лм а, 1, даже если оба ряда бесконечны. 8. [НМ20] Приведите пример бесконечного ряда, для которого равенство (7) ложно. й. [03] Справедливо ли доказательство формулы (14) для и = — 1? 10. [ОБ] Справедливо ли доказательство формулы (14) для и = — 2? 11. [ОЮ] Чему равна правая часть формулы (14) при х = 1? 12. [10] Чему равна сумма 1+ -'+ „— '+ — „' + + (-')'? 13.
[10] Используя формулу (15) и предполагая, что т < и, вычислите сумму 3 „" 1. 14. [11] Используя результат предыдущего упражнения, вычислите сумму 2,',". 2,'л „12ь л 15. [МЯЯ] Вычислитесумллу 1х2+2х2 +3х2 +.. +п2" для малых значений п. Заметили ли вы какую-либо закономерность в этих числах? Если нет, постарайтесь обнаружить ее с помо!цью действий, аналогичных тем, которые применялись при выводе формулы (14). 16. [М22] Не применяя ллетод математической индукции, докажите, что пх"'л~ — (п+ 1)хюм + х" (х — 1)з если х ~ 1. л 17.
[МОО] ПУсть Я вЂ” множество целых чисел. ЧемУ Равна сУмиа 4 ', з 1? 18. [М20] Покажите, как изменить порядок суммирования в равенстве (9), если Л(!)— это соотношение "п кратно !", а Я(л, 1) — зто соотношение "1 < 1 < л'. 19. [20] Чему равна сумма Я" (ау — а,,)'! л 20. [25] Д-р Матрица* обнаружил удивительную закономерность: 9 х 1 + 2 = 11, 9 х 12 ч- 3 = 111, 9 х 123 + 4 = 1111, 9 х 1234+ 5 = 11111. а) Запишите зто великое открытие доктора с полющью знака суммы "2 Ь) В вашем ответе к п. (а), без сомнения, фигурирует число 16 как основание десятичной системы.
Обобщите полученную формулу так, чтобы ее можно было применять для любого основания Ь. с) Докажите формулу из п (Ь) с помощью фориул, выведенных в тексте раздела или в упр 16. л 21. [М25] Выведите правило (с)) из правил (а) и (с) с поиощью обозначения Айверсона (16). ° . 22. [90] Сформулируйте аналоги равенств (5), (7), (8) и (11) для произведений. 23. [10] ОбъЯсните, почемУ целссообРазно опРеделить 2 лн>а! и Пя1 ! а! как нУль и единицу соответственно, если соотношению )?(1) не удовлетворяет ни одно целое число.
24. [20] Предположилл, что )?(1) верно только для конечного числа 1. Индукцией по числу целых чисел, удовлетворяющих Я(1), докажите равенство 1облп, а, = 2„я 3(1обла,) при условии, что все а, > О. л 25. [15] Есть ли ошибка в следующей цепочке преобразований? 26. [25] Покажите, что с помощью соотношений нз упр. 22 П" „П', а,а! можно выразить через П," „а,.
В оригивале — !. У Малпх. Лрим. перле. 27. [М30] Обобщите результат упр. 1.2.1 — 9, доказав неравенство П( -')-' -Е-з У=г гмг при условии, чтоб < а < 1. 23. [Мйй] Н йд щ у Фо у у д П,"=,(1 — 10*). ь 29. [МУ0] (а) Выразите сумму Е'=о Я~=о Кь во;азаь, используя способ записи с сколькими индексами, который приведен в конце данного раздела. (Ь) Выразите зту же сумму через 1т,7 ап ~,".
„а; н гт,". еа; [см Формулу (13)]. ь 30. [МЯУ] (Ж. Бине (Л. Вшес), 1812.) Не пользуясь индукцией, докажите тождество < в Ъ|" l" и аухт~ ~~ ЬУУГ) = ~ ~ отрг) г[ ЯЬУх ° ~]+ ~ ~(аУЬь — аьЬу)(хурь — хьр ). з=г 1=1 У=г У=г С кз<ьбь [У етого тождества есть важный частный случай: если ппиолгить а. = юз, ЬУ = 3, х. = ют, уг —— х,, то для пронзвольныт комплексных чисел юг, ..., ю„, гг, ..., г„выпслпяетса равенство Члены [гизуь — гиг 91 [~ неотрнцательны, поэтому знаменитое неравенство Коюп-Шварца является следствием формулы Бине.) 31.
[МЯ0] С помощью формулы Бине выразите сумму Я <.«„(нт пь)(вг — еь) через , изез, 1 "., и, и ),"ы, е„. 32. [МЯО] Докажите, что ПЕ"= Е 1=~ .=г г<'п...з < ь 33. [МЯО] Однажды вечером д-р Матрица открыл формулы, которые мекаю считать еще более замечательными по сравнению с формулами, приведенными в упр. 20: + 1 — О, (с — а)(с — Ь) (Ь вЂ” а)(Ь вЂ” с) (а — Ь)(а — с) + — О, (с — а)(с — Ь) (Ь вЂ” а)(Ь вЂ” с) [а — Ь)(а — с) 2 Ь + с + 1, (с — а)(с — Ь) (а — Ь)(а — с) (6 — а)(Ь вЂ” с) аз с а+6+с + + (ь — 6)(ь — .) (6 — а)(6 — с) (с — а)(с — Ь) Докажите, что эти формулы являются частными случаями более общего закона.
Покажи- те, что если х>,хг,...,х„— различные числа, то О, еглиО<г<и — 1; Е(х,"/ П (х> — хь))ж 1, с<лиг=п — 1; »<э<э г 2 "., х, если г = и. ь>ьг' 34. (Мйб) Для произвольного х и 1 < пг < и докажите, что П>«„„„Л (х+ Й вЂ” г) П><,<.„Фь(Ь вЂ” г) Например, есин и = 4 и и> = 2, то х(х — 2)(х — 3) (х + 1)(х — 1)(х — 2) (х + 2)х(х — 1) (х + 3)(х + 1)х (-1)(-2)(-3) (1)(-1)(-2) (2)(1)(-1) (3)(2)(1) + + + Зб. (НМ20) Запись эирл у а> применяется для обозначения точной верхней грани элементов а„", при этом используется тот же принцип, что и в случае применения знаков "2 " и "П". (Если й(У) выполнЯетсЯ только длЯ конечного числа У', то вместо ЗапИси эиРл1 > аг часто используется запись гпахкы> а>.) Покажите, как нужно видоизменить правила (а), (Ь), (с) и (д) для выполнения операций с эщим обозначением.
В частности, рассмотрите аналог правила (а) (эиРяб>а,)+(виР 1 >Ь,) = эиРлб (эиР ~,.>(а; ->-Ьу)) и дайте соответствующее определение эир „а для случая, когда К(у) не выполняется ии длл одного уб УПРАЖНЕНИЯ (часть 2) Мащриим и определиглели (дегаермиианщм), Приведенные ниже задачи предназначены для читателя, который и>веет хотя бы общее представление об определителях и элементарной теории матриц.
Детерминант можно вычислить, комбинируя определенным образом следующие операции: (а) вынесение общего множителя из строки или столбца; (Ь) прибавление кратного одной строки (или столбца) к другой строке (или столбцу); (с) разложение по элементам какой-либо строки (или столбца). Простейший и наиболее часто используемый вариант операции (с) относится к случаю, когда все элементы первой строки нли первого столбца — нули, за исключением элемента в левом верхнем углу, который равен +1.
Тогда первая строка и первый столбец просто вычеркиваются и вычисляется определитель оставшейся части матрицы, а зто уже определитель меньшего порядка. В общем случае под алгебраическим дополнением элемента ац определителя порядка и х и понимают помноженный на (-1)'~> определитель порядка (и — 1) х (и — 1), который получается в результате вычеркивания той строки н того столбца, на пересечении которых находится элемент а,>.
Тогда определитель матрицы равен 2 а, алгебраическое дополнение (ао), причем один из индексов (1 либо >) фиксируется, а суммирование выполняется по другому индексу, который пробегает значения от 1 до и. Егли (Ьи) — это матрица, обратиал матрице (а, ), то каждый ее элемент Ь„равен алгебраическому дополнению а>, (а не а, ), деленному на определитель всей матрицы. ь 4б. [Мйб] Масарика Гальбсрта, которую иногда называют сегментом размера и х и сбесканечнай) матрицы Гильберта,' — это матрица, элементы которой имеют следующвй вндс асг = 1/(с + у — 1). Покажите, что матрица Гильберта является частным случаем матрицы Коши; найдите для нее обратнтую матрицу; покажите, что все элементы этой обратной матрицы являются целыми чвсламн и что сумма всех элементов обратной матрицы равна лз.
[Замечание. Матрицы Гильберта часто используются для тестирования различш пс алгоритмов, в которых выполняются операции над матрицами, так вак, во-первых, ови численно неустойчввы относительно преобразований и, во-вторых, для них известны обратные матрицы. Но было бы ошибкой сравнивать известную обратную натрии:;у, заданную в этсвс упражнении, с ам»и<сенной обратной матрицей к матрице Гвльбертв, поскольку, прелсде чем находить обратную матрицу, неабходвмо округлить элементы перваначалс сюй матрицы.
В результате ссс-за уже упомянутой неустойчивости обратная матрица к округленной матрице Гильберта будет несколько отличаться от точного варианта обратной матрицы. Элементы обратной матрицы ввлшотся целыми числами, т. е. их ве надо округлять, поэтому обратнав матрица определена точно и можно попытаться ее обратить. Но заметим, что обратная матрица так же неустойчива, как и первоначальная. Кроме того, элементами обратной матрицы являются достаточно большие числа.] Для решения данной задачи необходима знание основных фактов о факториалах и биномиальных ксвффициевтах, о которых будет говориться в разделах 1.2.5 и 1.2.б.
ь 46. [МЗ0] Пуссь А — матрица размера сл х я, а  — матрица ркзмера п х пз При условии, что 1 < ус,уз,...,у < и, обозначим через А,м,, матрицу размера т х т, состоящую нз столбцов ус,...,у матрицы А, а через В чу, . — матрицу размера пз х т, состоящую вз строк )с,...,1, матрицы В. Докажите тол<де<слез Бине-Коши бт(АВ) = ~ ~без(Азсзз--з )без(Вз,зз, д ). с<и<уз«--з' «» (Обратите внимание ва частные случавс (с) т = и (й) т = 1 (ш) В = Аз (1т) пз ~ п (г) тп = 2.) 47. [М27] (К. Краттенхалер (С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
