Задачи и приёмы суммирования

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

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

Целью данной работы является рассмотрение и исследование особенностей приёмов, и методов решения задач суммирования.

1. Постановка задач суммирования

1.1 Связь между задачами суммирования и нахождения функции по заданной разности между её значениями в двух соседних точках из множества равноотстоящих значений аргумента.

Эта глава посвящена одной важной задаче теории конечных разностей - задаче суммирования функций. Задача эта ставится так. Нам дана некоторая функция f(x). Найти в конечном виде точно или приближённо, сумму:

,

при фиксированных x0 и h и большом n, если известны некоторые аналитические свойства f(x).

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

В дальнейшем для удобства всегда будем считать x0=0, h=1. Это, естественно, не повлияет на общность рассуждений, так как, положив:

,

получим, что:

.

Задача, грубо говоря, состоит из нахождения суммы:

,

как функции от п. Можно показать, что эта задача может быть сведена к такой задаче: дана функция , найти функцию F(x), такую что:

.

Действительно, пусть нашли F(x), такую, что:

,

[по-прежнему ], тогда:

, F(2)-F(1)=, … ,

Складывая эти равенства, получим:

(1)

а это и есть решение задачи о суммировании функции

Полной эквивалентности этих задач нет, так как Sn определена лишь для целых значений п, но если умеем найти не только Sп, а и сумму:

,

при любом х, то можем найти и F(x) следующим образом: при:

.

Найдём

т.е F(x), определённая таким образом, будет решением уравнения Формула (1) есть прямой аналог формулы Ньютона-Лейбница, выражающей связь между первообразной и определённым интегралом.

1.2 Случаи элементарного суммирования

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

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

Из определения конечной разности:

,

помощью вычислений легко получим формулы:

1)

2)

3)

4).

С помощью преобразований, легко получаем формулы:

1)Геометрической прогрессией:

2) Методом математической индукции:

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

Большую роль в теории конечных разностей играет уже известная обобщённая степень:

(k - целое). Для обобщённой степени, формулы суммирования выглядят очень просто. Как уже знаем:

 (2)

поэтому:

Аналогично можно определить обобщённые отрицательные степени (k-целое положительное число):

Найдём :

(5)

Отсюда получим соответствующую формулу:

Из приёмов элементарного суммирования отметим преобразование Абеля-аналог интегрирования по частям. Преобразованием Абеля называется тождество:

Для доказательства этого тождества заметим, что:

,

Суммируя от т до п, получаем (7).

С помощью преобразования Абеля можно просуммировать, например, функцию Положим тогда , поэтому:

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

2. Метод неопределённых коэффициентов и область его применения

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

Рассмотрим сумму:

каждое слагаемое которой, является многочленом натуральной переменной со степенью не выше чем k, причём количество слагаемых задаётся выражением в виде многочлена той же самой натуральной переменной k, со степенью не выше чем s. Очевидно, что в результате такая сумма даёт многочлен переменной п, степень которой не превосходит числа k+s.

Пример: В сумме всякое слагаемое есть многочлен п не выше чем 2, а количество слагаемых той же переменной в степени не выше чем 1, тогда сумма представляет собой многочлен степени не выше чем k+s, т.е. 3. А потому

, где A, B, C, D- неопределённые коэффициенты.

Потребуем, чтобы набор коэффициентов A, B, C, D при любом натуральном k обеспечивал выполнение равенств вида:

M(k)-M(k-1) =k2,

где M(n)=An3+Bn2+Cn+D,

Подробно распишем условие M(k)- M(k-1) =k2:

Ak3+Bk2+Ck - A(k-1)3-B(k-1)2-C(k-1)=k2

Ak3 + Bk2 + Ck

- A(k3 - 3k2 + 3k-1)-

-B( k2 - 2k+1)-

-C( k-1)= k2

(B+3A-B) k2+(C - 3A + 2B - C)k + A - B + C = k2

3Ak2- (3A + 2B)k + A - B + C = k2, так как последнее равенство является тождеством двух многочленов, то у них должны соответственно равняться коэффициенты при каждой из них. Тогда А, В, С подчиняются системе:

Делаем подстановку для нахождения суммы:

2.1 Разложение дроби на простейшие

Классическим примером применения метода неопределённых коэффициентов является разложение правильной рациональной дроби в комплексной или вещественной области на элементарные дроби.

Пусть P и Q -- многочлены с комплексными коэффициентами, причём степень многочлена P меньше степени многочлена Q. Будем полагать, что степень многочлена Q равна n, коэффициент при старшем члене многочлена Q равен 1, а zk, Ї различные корни многочлена Q с кратностями , соответственно. Отсюда имеем:

.

Функция представима, и притом единственным образом, в виде суммы элементарных дробей:

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

Примечание. Нахождение коэффициентов упрощается, если Q имеет только некратные корни zk, k=1,…,n, т.е. все и:

.

После умножения на последнего равенства и подстановки непосредственно получаем значение соответствующего коэффициента:

Пример: Используем метод разложения на простейшие. Разложим функцию на простейшие слагаемые:

Приравняем числители и учтем, что коэффициенты при одинаковых степенях х, стоящие слева и справа должны совпадать:

Решая эту систему, находим:

2.2 Обращение ряда

Если функция , не равная нулю при x=0 разложена в ряд Маклорена:

то существует ряд Маклорена противоположной функции:

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

Аналогичным, но более громоздким, образом можно найти коэффициенты ряда обратной функции:

При этом используется соотношение , то есть весь ряд для подставляется вместо x в ряд для g(x).

3. Правила и законы суммирования и их использование

3.1 Правила и законы суммирования

Существует 3 основных закона суммирования:

1. Распределительный закон:

2. Сочетательный закон:

3. Переместительный закон:

,

где p(k) - некая перестановка множества k.

Для любых множеств К и К' если они конечны и входят в состав натурального ряда:

.

Справедливо правило изменения порядка суммирования:

,

Частный случай правила изменения порядка суммирования:

.

Общий распределительный закон сложения.

.

Возможна ситуация когда внутренний индекс суммирования принимает значение, зависящее от внешнего индекса суммирования.

.

Данное равенство будет справедливым в том случае, если выполнено условие:

В частности простейшая реализация этого равенства возможна при выполнении условия:

3.2 Использование свойств конечных сумм для получения модификации неравенств Чебышёва

Одно из основных неравенств для монотонных последовательностей или функций. В случае конечных последовательностей:

,

оно имеет вид:

Пример: Пусть даны две последовательности чисел{an}:a1,a2,…, an и {bn}:b1, b2, …, bn. Рассмотрим суммы следующего вида:

Сложив их, получим:

В результате получаем:

Пусть теперь последовательности и являются монотонными. Если характер монотонности у этих последовательностей одинаков, то, а вместе с тем .

Если характер монотонности у этих последовательностей различен, то, а вместе с тем .

4. Приёмы суммирования основанные на свойствах прогрессии

4.1 Арифметическая прогрессия и связанные с ней приёмы суммирования

Характеристическое свойство арифметической прогрессии.

Последовательность является арифметической прогрессией тогда и только тогда, когда для любых натуральных чисел n, p, k, t соответствует равенство:

,

Пример: Докажите, что для всякой арифметической прогрессии с положительными членами справедливо равенство:

Левая часть:

Пример 2:

Левая часть:

Пример 3:

d - разность прогрессии, р - количество множителей в каждом знаменателе.

и так далее.

Суммируем левые и правые части записанных равенств и получаем:

4.2 Геометрическая прогрессия и связанные с ней приёмы суммирования

Любой член геометрической прогрессии может быть вычислен по формуле:

, ,

Характеристическое свойство геометрической прогрессии.

Если справедливо, что для любого

,

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

то:

4.3 Приёмы суммирования основанные на использовании двух различных прогрессий

1) Сумма парных произведений элементов двух арифметических прогрессий с одинаковыми номерами:

Пусть даны две арифметические прогрессии {ап} и {вп}

n-количество слагаемых.

Sn=2*3+6*5+10*7+…+(2+4k)(3+2k)

{an}:an=1+4(n-1), bn=3+2(n-1); (2+4(n-1))=2+4k, n-1=k, n=k+1; 3+2k=3+2(n-1), k=n-1, n=k+1

{ап} - арифметическая прогрессия:

{вп} - геометрическая прогрессия:

2) Введём формулу суммы парных произведений членов арифметической и геометрической прогрессий с одинаковыми номерами:

5. Формулы суммирования, выводимые методом математической индукции

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

Пример 1: Дана сумма первых членов арифметической прогрессии методом математической индукции нужно доказать равенство суммы первых натуральных чисел от 1 до n:

Доказательство при n=1 равенство справедливо:

Предположим, что равенство справедливо для номера n-1:

Докажем его истинность для номера n:

.

Здесь мы в квадратные скобки подставили выражение из предыдущего равенства, затем раскрыли скобки и привели подобные, и снова разложили на множители. Получилось выражение того же вида, в котором n-1 заменено на n.

Что и требовалось доказать.

Пример 2: Докажем, что для любого справедливы:

2. Предположим, что :

Пример 3:

Дополнительно установим количество k всех членов арифметической прогрессии, входящих в сумму в скобках:

Заключение

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

Рассматриваются задачи суммирования не только как самостоятельные, но и в ситуации, когда они являются этапом в решении более серьёзных комплексов задач.

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

Последний факт даёт возможность расширить сферу применения результатов, полученных при решении основной задачи, тогда как источником появления такой возможности явилось использование приёмов суммирования.

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

арифметический неравенство суммирование

Список литературы

1. Вересова Е.Е., Денисова Н.С., Практикум по решению математических задач, Просвещение - 1979, 238с.

2. Гельфонд А.О., Исчисление конечных разностей, Государственное издательство технико-теоретической литературы, Москва - 1952, 478с.

3. Грэхем Р., Кнут Д., Поташник О., Конкретная математика, Москва «Мир» - 1998, 703с.

4. Иванов Б.Н., Дискретная математика, Москва «Известия» - 2011.

5. Поздняков С.Н., Рыбин С.В., Дискретная математика, Академия - 2008.

Размещено на Allbest.ru