Тема 4. Рационализация вычислений

Темы

Математический журнал

Рационализация вычислений

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

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

Хрестоматийным примером является «маленький Гаусс»*, который по легенде почти мгновенно заметил, что сумма натуральных чисел от 1 до 100 равняется 5050.

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

*

Таким образом, наблюдение Карла Гаусса обогатило человечество формулой, справедливой для любого натурального числа N.

Заключение

То есть, сто действий сложения оказались заменены одним умножением и одним делением.

N ( N + 1 )

2

Точнее, он заметил, что если под этим рядом записать такой же, только в обратном порядке

Правда таким образом мы сложили требуемый ряд дважды, поэтому получившийся результат 10 100 нужно разделить на 2. В результате получим те самые 5050.

Сумма чисел от 1 до N всегда будет равняться

Имеется в виду один из величайших математиков Карл Фридрих Гаусс, выдающиеся математические способности которого проявлялись уже в детстве.

Важная мысль

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

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

То есть, для любой суммы вида:

Попробуем сложить пять таких дробей:

Пример посложнее.

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

Но можно заметить, что разность между сомножителями, стоящими в знаменателе, неизменна и равна трем. Тогда мы можем всю сумму умножить и разделить на 3

а появившуюся в числителе тройку представить как разность сомножителей из знаменателя.

У нас получится:

Каждую такую дробь, в свою очередь, можно представить в виде разности дробей с общим знаменателем:

Как мы видим, почти все слагаемые в скобках взаимно уничтожаются, поскольку мы имеем

Остается только домножить получившуюся дробь

и результат готов:

,

на

Формулы сокращенного умножения многочленов

Тема: Рационализация вычислений

Продолжая тему рационализации вычислений, нельзя не упомянуть о формулах сокращенного умножения, из самого названия которых следует, что мы тут явно «срезаем какие-то углы», где-то экономим… Вопрос, где?

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

Иногда к ним добавляют формулы для кубов суммы и разности, а также суммы и разности кубов:

,

.

И уже совершенно «высшим пилотажем» оказываются правила умножения для произвольного числа многочленов вида

или правило разложения многочленов вида

О них мы поговорим отдельно. Как мы увидим, в некоторых случаях удается разложить и сумму

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

Заключение

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

Почти все перечисленные здесь формулы мы подробно разбираем в посвященном данной теме видео. И даже выводим разложения частного случая разности n-ых степеней:

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

Если у нас имеется сумма вида

то

,

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

Теперь, чтобы полностью завершить тему разности n-ых степеней, мы можем заметить следующее:

, т. е. как

можно представить в виде

в которой

и

,

Значит,

И, следовательно,

.

В заключение нам остается только добавить, что в том случае, когда степень n является нечетным числом, то сумма

Заключение

aⁿ+ bⁿ

также может быть представлена в виде разности

aⁿ− (−b)ⁿ

и, значит для степеней

n= 2k + 1

эта сумма может быть разложена по полученной нами формуле

aⁿ+ bⁿ= (a + b)( a^{n − 1} − a^{n − 2}b +...− ab^{n − 2}+ b^{n − 1})

n= 2k + 1

при

для разности, т. е:

т. е. как

,

aⁿ+ bⁿ= (a + b)( a^{n − 1} − a^{n − 2}b +...− − ab^{n − 2}+ b^{n − 1})

Предлагаем вам убедиться самостоятельно,

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

В видео мы «‎ручками» вывели формулы для квадрата и куба суммы:

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

( a + b )² = a² + 2ab + b²

( a + b )³ = a³ + 3a²b + 3ab² + b³

Бином Ньютона

Тема: Рационализация вычислений

Мы же тему рационализации вычислений завершаем совсем уже «взрослым» случаем — обобщением этих формул на случай произвольной натуральной степени n: ( a+ b )ⁿ ,

известного математикам под устрашающим именем бинома Ньютона.

n: ( a+ b )ⁿ,

Таким образом, наша главная задача — это показать, что ничего страшного в биноме Ньютона нет.

По определению натуральной степени числа,

Итак, мы начинаем.

( a + b )ⁿ

Из видео мы помним две важные вещи:

При перемножении таких двучленов, т. е. при «раскрытии скобок», получается ровно 2ⁿ слагаемых;

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

— это произведение n числа скобок вида

( a + b )ⁿ , т.е. ( a + b )ⁿ =
= ( a + b ) ( a + b ) ... ( a + b )

1.

2.

( a + b ), т.е. ( a + b )ⁿ = ( a + b ) ( a + b ) ... ( a + b )

n штук

Обобщая сказанное, мы уже понимаем то, как примерно будет выглядеть разложение (a+b)ⁿ: в него будут входить 2ⁿ слагаемых, каждое из которых представляет из себя произведение, состоящее из элементов, а и b, общим числом n.

То есть, это всякий раз будут произведения вида a^kb^n−k

Также можно заметить, что произведение, в которое будут входить только а или только b, т. е. произведения вида aⁿ или bⁿ могут встретиться лишь один раз, поскольку в них входят элементы a или b из всех n скобок.

Которые, кстати, для наглядности можно временно себе представлять как n ящиков, в каждом из которых лежит по два элемента — а и b.

Тогда вопрос о том, сколько произведений вида a^kb^{n — k} может встретиться в разложении бинома Ньютона, можно свести к вопросу о том, сколькими способами мы такое произведение можем составить. А он, в свою очередь, сводится к вопросу о том, сколькими способами мы можем выбрать из n ящиков k элементов a.

n штук

И тогда становится понятно, что произведение вида

a ⁿ= a × a ×… × a

мы можем получить единственным способом, взяв из каждого из n ящиков по одному элементу a.

С другой стороны, произведение вида ab^{n — 1}можно получить n способами — по числу ящиков, из которых мы можем выбрать элемент a, входящий в произведение.

число способов, которыми можно выбрать k элементов a, входящих в произведение a^kb^{n — k}, равно числу способов, которыми можно выбрать n − k этих же элементов.

Здесь же можно заметить и еще одно свойство слагаемых, входящих в разложение бинома Ньютона:

Вообще эти числа, равные числу способов, которыми можно выбрать из n предметов k штук, называются сочетаниями, или (по понятным теперь причинам) биномиальными коэффициентами

и обозначаются как

Первое свойство биномиальных коэффициентов

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

Возможно, эти числа уже встречались кому-то из вас под другим названием — треугольника Паскаля.

Тема: Рационализация вычислений

Правило построения такого треугольника, состоящего из целых чисел, такое:

в вершине записываем 1,

во втором ряду две единицы: 1 1,

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

Правило

Обратите внимание, что сумма чисел ряда всегда равна 2ⁿ, если нумерацию рядов начать с нуля и сверху вниз.

Важная мысль

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

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

Но это правило пока еще ничего не говорит нам о том, почему у сочетаний есть такое свойство.

Попробуем доказать его

Предположим, что у нас есть множество А, состоящее из n элементов. Зафиксируем один из элементов

наборов, которые можно составить из элементов множества А.

и рассмотрим множество всех к-элементных

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

Очевидно, что это и будет число сочетаний

Сочетания, в которые а входит, можно получить, рассмотрев множество всех (к − 1) — элементных наборов, которые можно составить из элементов множества A \ {a}, и затем добавив в каждый такой набор элемент а.

А сочетания, в которые а не входит, это — множество всех к-элементных наборов, которые можно составить из элементов множества A \ {a}. Складывая число сочетаний, получившихся в первом и втором случае, получаем искомое свойство:

.

— причем среди этих сочетаний будут

такие, в которые элемент а входит, и такие, в которые а не входит.

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

Пора, наконец, разобраться и с этим.

Для этого вернемся к нашей аналогии с ящиками: будем считать, что у нас есть n ящиков с двумя элементами a и b в каждом: (a + b)(a + b)…(a + b)

любой элемент из оставшихся n − 1 ящика, и так далее до
k-того места — элемент на это место можно будет взять из оставшихся n − (k − 1) = n − k + 1 ящиков.

И нам нужно, как мы помним, выбрать из этих ящиков k штук элементов a.

Будем постепенно заполнять этими «‎ашками» воображаемую строку длины k.

На первое место

мы можем поставить элемент а, взятый из любого из n ящиков.

На второе место

Значит, всего способов составить строчку из k элементов n ( n − 1 )( n − 2 )...( n − k + 1 ).

Значит, всего способов составить строчку из k элементов
n ( n − 1 )( n − 2 )...( n − k + 1 ).

n штук

Для этого вернемся к нашей аналогии с ящиками: будем считать, что у нас есть n ящиков с двумя элементами a и b в каждом:
(a + b)(a + b)…(a + b)

Важная мысль

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

Мы сможем это сделать, сократив получившееся число n (n − 1)(n − 2)…(n − k + 1) на число всех перестановок, которые можно произвести в k-элементной строчке.

Мы сможем это сделать, сократив получившееся число
n(n − 1)( n − 2 )...(n − k + 1) на число всех перестановок, которые можно произвести в k-элементной строчке.

Будем рассуждать аналогично: первое место в строчке мог занять любой из k элементов, второе — любой из k − 1 оставшихся и т. д., только на этот раз мы дойдем до последнего k-го элемента, место которого уже определено однозначно.

Значит, число перестановок k элементов равно k(k − 1)(k − 2)...2 × 1.

У такого произведения тоже есть свое название — факториал, и оно обозначается так: k(k − 1)(k − 2)...2 × 1

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