Как считать двойную сумму

math serfer .narod.ru

где — функция целочисленного аргумента. Здесь символ (большая греческая буква «сигма») означает суммирование. Запись внизу символа суммирования показывает, что переменная, которая меняет свои значения от слагаемого к слагаемому, обозначена буквой и что начальное значение этой переменной равно . Запись вверху обозначает последнее значение, которое принимает переменная .

1) .

2) . Так как в правой части стоит сумма геометрической прогрессии с первым членом равным и знаменателем прогрессии равным , то эту сумму легко найти

3) .

4) .

5) .

В курсе линейной алгебры чаще всего будут встречаться суммы вида . Здесь переменная с индексом рассматривается как функция от своего индекса. Поэтому

С помощью знака суммы формулу (10.1) скалярного произведения векторов можно записать так:

( 14 .2)

где для трехмерного пространства , для плоскости .

Для единообразия будем считать, что

и говорить, что это сумма, содержащая одно слагаемое.

в правой части никакой буквы />нет, значит, и результат от />не зависит.

Доказательство этого предложения предоставляется читателю.

( 14 .3)

Это предложение является частным случаем следующего утверждения.

( 14 .4)

Раскроем скобки в правой части этого равенства. Получим сумму элементов при всех допустимых значениях индексов суммирования. Слагаемые сгруппируем по-другому, а именно, сначала соберем все слагаемые, у которых первый индекс равен 1, потом, у которых первый индекс равен 2 и т.д. Получим

Заменив в этом равенстве в левой части его выражением через знаки суммирования, получим формулу (14.4).

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

Если границы изменения всех индексов суммирования одинаковы, то можно для суммирования по нескольким индексам использовать запись вида

Иногда под символом суммы указывают дополнительные условия, налагаемые на индексы суммирования. Так запись

означает, что в сумму не включаются величины , . , то есть с равными индексами.

Иногда в записи суммы не указываются границы изменения индексов, например,

Такая запись используется, когда значения, которые могут принимать индексы, очевидны из предыдущего текста или будут оговорены сразу после окончания формулы.

Как легко понять знаки Σ и П с помощью программирования

Вот говорят, что если ты не закончил Физтех, ФПМ или Бауманку, тебе в программировании делать нечего. Почему так говорят? Потому что, дескать, ты не учил сложную математику, а в программировании без неё никуда.

Это всё чушь, конечно. Если вы плохо знаете математику, вы можете быть блестящим разработчиком. Вы вряд ли напишете драйверы для видеокарты, но вы запросто сделаете мобильное приложение или веб-сервис. А это — основные деньги в этой среде.

Но всё же, чтобы получить некоторое интеллектуальное превосходство, вот вам пара примеров из страшного мира математики. Пусть они покажут вам, что не все закорючки в математике — это ад и ужас. Вот две нестрашные закорючки.

Знак Σ — сумма

Когда математикам нужно сложить несколько чисел подряд, они иногда пишут так:

Σ (читается «сигма») — это знак алгебраической суммы, который означает, что нам нужно сложить все числа от нижнего до верхнего, а перед этим сделать с ними то, что написано после знака Σ.

На картинке выше написано следующее: «посчитать сумму всех чисел от 5 до 15, умноженных на два». То есть:

1. Взять все числа от 5 до 15 (снизу и сверху знака Σ).
2. С каждым из этих чисел сделать то, что написано справа от Σ, — то есть умножить на два.
3. Сложить результаты этих операций.

Давайте для закрепления ещё один пример. На картинке ниже будет сказано «Найди сумму квадратов чисел от 5 до 10». То есть «возьми все числа от 5 до 10, каждое из них возведи в квадрат, а результаты сложи».

Но мы с вами как программисты видим, что здесь есть повторяющиеся действия: мы много раз складываем числа, которые меняются по одному и тому же правилу. А раз мы знаем это правило и знаем, сколько раз надо его применить, то это легко превратить в цикл. Для наглядности мы показали, какие параметры в Σ за что отвечают в цикле:

Произведение П

С произведением в математике работает точно такое же правило, только мы не складываем все элементы, а перемножаем их друг на друга:

А если это перевести в цикл, то алгоритм получится почти такой же, что и в сложении:

Что дальше

Сумма и произведение — простые математические операции, пусть они и обозначаются страшными символами. Впереди нас ждут интегралы, дифференциалы, приращения и бесконечные ряды. С ними тоже всё не так сложно, как кажется на первый взгляд.

Как считать двойную сумму

Члены суммы могут быть снабжены не только одним, а двумя и более индексами. Вот пример двойной суммы из девяти членов, управляемой двумя индексами и :

Для таких сумм используются те же обозначения и методы, что и для сумм с единственным индексом. Так, если и к связаны некоторым условием то сумма всех членов а, таких, что истинно, может быть записана двумя способами, в одном из которых используется нотация Айверсона, а суммирование осуществляется по всем парам целых и :

Несмотря на то, что здесь имеется более одного индекса суммирования, достаточно только одного знака который означает сумму по всем допустимым комбинациям индексов.

Впрочем, случается использовать и две сигмы, когда речь идет о сумме сумм. Например,

— это сокращенная запись суммы

которая представляет собой сумму по всем целым членов в свою очередь являющихся суммами по всем целым к всех таких членов а, которые удовлетворяют условию . В таких случаях говорят, что двойная сумма „суммируется сначала по к“ Сумму, которая зависит более чем от одного индекса, можно начинать суммировать с любого из этих индексов.

Это обстоятельство представляет собой важное правило, называемое изменением порядка суммирования и обобщающее сочетательный закон (2.16), с которым мы уже знакомы:

В этом правиле средний член представляет собой сумму по двум переменным. В левой части означает суммирование сперва по , а потом по . В правой части означает суммирование сначала по а затем по . На практике, когда нам надо вычислить двойную сумму в замкнутой форме, обычно проще сначала просуммировать по какому-то одному из двух индексов, а не по другому — мы свободны в выборе более удобного из них.

Суммы сумм — не повод для паники, но они могут сбить с толку начинающего — поэтому давайтека решим еще несколько примеров. Девятичленная сумма, с которой мы начинали, служит хорошей иллюстрацией преобразования двойных сумм, поскольку эта сумма действительно может быть упрощена, а сам процесс упрощения типичен для того, что можно делать с двойными суммами:

Здесь в первой строке записана сумма из девяти членов безотносительно их порядка. Во второй строке эти члены сгруппированы по три, . В третьей строке используется распределительный закон для вынесения за скобки всех -членов, поскольку и не зависят от к; это дает Четвертая строка аналогична третьей, но с дополнительной парой скобок, введенных с тем, чтобы следующая строка не выглядела слишком загадочной. В пятой строке выносится множитель который встречается при каждом Последняя строка — всего-навсего другая форма записи предыдущей. Подобный вывод можно использовать для доказательства общего распределительного закона

справедливого для всех множеств индексов и К.

Основное правило (2.27) изменения порядка суммирования допускает разного рода вариации, возникающие, когда мы хотим ограничить области изменения индексов вместо суммирования по всем целым и к. Эти вариации вызывают два ощущения: ванили и булыжной мостовой. Сперва — „ванильная» версия:

Это всего лишь другой способ записи (2.27), поскольку скобки Айверсона распадаются в произведение скобок . Правило с привкусом ванили применимо во всех случаях, когда области изменения и к не зависят друг от друга.

„Булыжная» формула изменения порядка суммирования несколько более мудреная. Она применима, когда область изменения индекса внутренней суммы зависит от переменного индекса внешней суммы:

В этом случае множества должны быть связаны так, чтобы

В принципе, разложение такого рода всегда возможно, поскольку можно считать множеством всех целых чисел, а — основным условием , которое управляет двойной суммой. Вместе с тем существуют важные частные случаи, когда множества имеют довольно простую форму. С ними часто приходится сталкиваться в приложениях. Вот пример весьма полезного разложения:

Это равенство по Айверсону делает справедливой следующую запись:

Одну из этих двух двойных сумм обычно легче вычислить, чем другую, — мы можем воспользоваться равенством (2.32) для переключения с трудной суммы на легкую.

Используем эти соображения с пользой для дела. Рассмотрим матрицу

из произведений Наша цель — найти простую формулу для

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

Подобные наводящие соображения служат поводом для следующих манипуляций:

поскольку можно переобозначить как Кроме того, поскольку

Первая сумма по общему распределительному закону (2.28) есть а вторая — . Поэтому

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

Воодушевленные таким успехом, рассмотрим еще одну двойную сумму:

Здесь мы снова имеем симметрию относительно перестановки :

Поэтому сумму можно сложить саму с собой, используя соотношение

с тем, чтобы заключить, что

Вторая сумма здесь обращается в нуль, а как насчет первой? А она распадается на четыре отдельные суммы, каждая из которых отдает ванилью:

На последнем шаге обе суммы подверглись упрощению в соответствии с общим распределительным законом (2.28). Если же

преобразование первой суммы остается загадкой — воспроизведем его не спеша снова:

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

Возвращаясь к тому месту, где мы остановились, теперь можно поделить все пополам, произвести перестановку и получить интересную формулу:

В качестве частных случаев это соотношение дает неравенства Чебышева для сумм:

(В общем случае, если и если — некоторая перестановка множества то нетрудно доказать, что наибольшее значение достигается при а наименьшее значение — при

Многократное суммирование имеет интересную связь с общей операцией замены переменной суммирования в однократных суммах. В силу переместительного закона мы знаем, что

если является некоторой перестановкой целых чисел. Но что будет, если заменить к на , где — произвольная функция

которая переводит целое в целое ? Общая формула замены переменной выглядит так:

где обозначает число элементов множества

т. е. число элементов таких, что равно к.

Формулу (2.35) легко доказать, изменив порядок суммирования:

поскольку частном случае, когда — взаимно однозначное соответствие между и К, имеем при всех к, и общая формула (2.35) сводится к формуле

Это переместительный закон (2.17), с которым мы уже имели дело — в слегка замаскированном виде.

До сих пор все наши примеры кратных сумм включали в себя произвольные члены типа или Но поскольку эта книга претендует на конкретность, давайте рассмотрим кратную сумму, включающую реальные числа:

Обычный способ вычисления двойной суммы состоит в суммировании сначала по или же сначала по к — поэтому давайте испробуем обе возможности.

Увы! Мы не знаем, как загнать сумму гармонических чисел в замкнутую форму.

Если же попробовать начать суммировать по-другому, то получим

И вновь оказываемся в том же самом тупике.

Но имеется еще один путь, по которому можно добраться до цели, если заменить на прежде чем решиться на сведение к сумме сумм:

Ура! Мы нашли . Сопоставляя результаты этого „забега» с допущенными фальстартами, мы получаем в качестве приза следующее соотношение:

Использованную здесь уловку можно осмыслить двояко: во-первых, алгебраически, а во-вторых, геометрически. (1) Алгебраически: если дана двойная сумма, члены которой включают в себя где — произвольная функция, то этот пример показывает, что неплохо попробовать заменить к на и просуммировать по Геометрически: можно представить сумму например сумму при в следующем виде:

Наши первые попытки просуммировать сначала по (по столбцам) или по к (по строкам), давали . Но выигрышный ход, по существу, заключался в суммировании по диагоналям, и он давал