37. Матричные функции

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

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

.

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

Реализация цепи Маркова

В качестве примера попробуем рассчитать в электронной таблице значения цепи Маркова (о том, что это такое, подробно рассказано в главе 22). Здесь мы должны начать с матрицы переходов, содержащей вероятности переходов между несколькими состояниями, где столбец соответствует состоянию, из которого выполняется переход, а строка — состоянию, в которое он выполняется. Учитывая тот факт, что в любой момент времени мы можем находиться только в одном состоянии, также можно просуммировать содержимое каждого столбца с помощью функции SUM() и убедиться, что все суммы равны 1. После этого в отдельном столбце введите элементы вектора-столбца, представляющего начальное состояние, сумма которых тоже должна равняться 1. Для простейшей машины состояний (см. главу 22), которая из состояния 1 всегда переходит в состояние 2, из состояния 2 с вероятностью 50 % — в состояние 1 или 3, а из состояния 3 с равной вероятностью — в любое из трех состояний, исходные данные будут выглядеть следующим образом (рис. 37.1).

Рис. 37.1

Для элементов, равных половине (в столбце C), можно ввести значение 0,5 или формулу =1/2. Для элементов, равных 1/3 (в столбце D), используйте формулу =1/3, а не десятичную дробь, чтобы избежать ошибок округления.

Теперь обеспечим отслеживание количества совершенных переходов. В ячейке G1, соответствующей исходному состоянию, введите число 0. В ячейке H1 нужно ввести число 1, в ячейке I1 — число 2 и т.д. Это можно сделать следующим образом: введите в ячейке H1 формулу =G1+1, выделите пару десятков расположенных правее ячеек (нажимая клавишу Стрелка вправо и удерживая клавишу Shift) и выполните их автозаполнение с помощью клавиш Ctrl+R (как вы могли заметить, это то же сочетание клавиш, которое мы применяем для пересчета ячеек, использующих функцию RAND()).

А что насчет вычисления новых векторов-столбцов? Как вы помните, чтобы получить первый элемент следующего вектора-столбца (H2), мы должны поэлементно умножить на исходный вектор-столбец (G2:G4) первую строку матрицы переходов (B2:D2). В данном случае это несложно сделать вручную: вы можете ввести формулу =B2*G2+C2*G3+D2*G4 в ячейку H2 и таким же образом заполнить все остальные строки и столбцы. Но, поскольку нам хотелось бы заполнить текущий столбец путем автозаполнения вниз, а все остальные столбцы — авто­заполнением вправо, следует избирательно применять абсолютные и относительные ссылки. В случае строк матрицы мы должны неизменно использовать столбцы B, C и D (нам не нужно задействовать содержимое каких-либо других столбцов, в то время как номер строки может варьироваться в диапазоне от 2 до 4). В случае векторов-столбцов мы должны неизменно использовать строки 2, 3 и 4 (на это, например, указывает то, что все формулы в ячейках H2:H4 ссылаются на ячейки G2:G4). Таким образом, на самом деле нужно применять формулу =$B2*G$2+$C2*G$3+$D2*G$4. Теперь вы можете записать ее в ячейке H2, после чего с помощью функции автозаполнения продублировать ее вниз вплоть до ячейки H4 (используя клавиши Ctrl+D), а затем — на пару десятков столбцов вправо (клавиши Ctrl+R). Также можно продублировать вправо содержимое 5-й строки, чтобы убедиться в том, что элементы всех последующих векторов-столбцов по-прежнему дают в сумме 1.

Надо сказать, что при использовании более крупной матрицы переходов, такой как, например, матрица для игры «Спуски и лестницы», которую мы рассмотрели в той же главе 22, данный метод требует неприемлемо большого количества усилий. Готовы ли вы вручную вводить формулы, описывающие 82 операции умножения? И сможете ли сделать это, не допустив ни одной ошибки (или легко найти допущенные ошибки)? Есть и другой способ, он немного сложнее, но затраченные усилия окупаются значительной экономией времени.

В данном случае нужно получить сумму результатов поэлементного умножения диапазона $B2:$D2 на диапазон G$2:G$4, но если мы просто запишем формулу =($B2:$D2) * (G$2:G$4), это не сработает, прежде всего потому, что это диапазоны разной формы (размерами 1 × 3 и 3 × 1). К счастью, редакторы электронных таблиц позволяют использовать функцию TRANSPOSE(), которая меняет горизонтальную ориентацию на вертикальную и наоборот, подобно команде Paste Special/Paste Transposed (Специальная вставка/Вставка с транспонированием), о которой говорилось в предыдущей главе. Поэтому можно записать формулу =TRANSPOSE($B2:$D2) * (G$2:G$4), однако и это не сработает — результат будет представлять собой ряд из трех элементов — результатов поэлементного умножения исходных диапазонов. Мы должны сложить эти элементы с помощью формулы =SUM(TRANSPOSE($B2:$D2)*(G$2:G$4)). Это уже верная формула, но и она не сработает, потому что по умолчанию в редакторах электронных таблиц не определена операция умножения одного диапазона ячеек на другой и они не знают, как это делается. Однако обойти эту проблему можно, рассматривая каждый диапазон ячеек как массив, поскольку умножение одного массива на другой работает именно так, как нам нужно в данном случае. Для этого при вводе формулы нужно вместо клавиши Enter нажать сочетание клавиш Ctrl+Shift+Enter. Редактор Google Sheets при этом вызовет еще одну формулу, =ArrayFormula(SUM(TRANSPOSE($B2:$D2)*(G$2:G$4)). Того же результата можно добиться, не используя горячие клавиши, а просто вручную добавив в формулу функцию ArrayFormula(). Эта формула наконец-то сработает как надо, и, продублировав ее вниз и вправо, вы сможете получить все последующие результаты (рис. 37.2).

Рис. 37.2

В данном конкретном случае у нас нет конечного состояния и мы можем продолжать переключаться между состояниями до бесконечности. Но, когда конечное состояние есть (как, например, в случае из главы 22, где вычислялось количество ходов, в среднем необходимое для перехода в последнюю клетку в игре «Спуски и лестницы»), мы можем попытаться определить, сколько времени в среднем требуется для достижения конечного состояния.

То количество ходов, после которого вероятность нахождения в конечном состоянии впервые достигает 50 %, является медианой. Вы можете просто снабдить пометкой «Медиана» строку с элементами векторов-столбцов, соответствующими конечному состоянию, потому что эти значения, по сути, представляют собой суммарную вероятность достижения конечного состояния. Когда она доходит до 0,5, это говорит о том, что половине игр требуется больше, а половине игр — меньше времени, значит, соответствующее количество ходов является медианным количеством ходов, необходимых для достижения конечного состояния.

Чтобы определить вероятность того, что вы перейдете в конечное состояние именно на заданном ходу, а не на одном из предыдущих, необходимо из вероятности нахождения в конечном состоянии, указанной в текущем векторе-столбце, вычесть соответствующее значение предыдущего вектора-столбца. Чтобы найти модальное количество ходов, позволяющее достичь конечного состояния с наибольшей степенью вероятности, нужно сначала определить максимальное значение вероятности с помощью функции MAX(). Чтобы теперь определить, где находится это максимальное значение, определите положение соответствующего столбца с помощью функции MATCH(), о которой говорилось в главе 32.

Чтобы найти среднее (ожидаемое) количество ходов, необходимых для достижения конечного состояния, нужно определить вероятность перехода в конечное состояние на каждом конкретном ходу (вероятность конкретного результата) и умножить ее на соответствующее количество ходов (конкретный результат). Затем, как при расчете любых ожидаемых значений, следует просуммировать все результаты умножения вероятности на результат. Если, например, вероятности находятся в ячейках H6:ZZ6, а количество ходов — в ячейках H1:ZZ1, можно вновь воспользоваться формулой =ArrayFormula(SUM((H1:ZZ1)*(H6:ZZ6)).

Расчет матрицы выплат

Чтобы найти решение в случае нетранзитивных отношений (о них говорилось в главе 25), сначала нужно составить матрицу выплат, показывающую, какой размер преимуществ или издержек получает игрок в случае выбора им и его соперником той или иной комбинации ходов в игре с противостоянием в режиме «один на один», такой как «Камень, ножницы, бумага». После этого следует умножить эту матрицу на вектор-столбец, содержащий вероятности совершения соперником того или иного хода. Это позволит определить ожидаемый результат каждого из ходов, которые может выбрать игрок.

С математической точки зрения при этом происходит следующее. Вы умножае­те матрицу выплат M на вектор вероятностей c и получаете в результате вектор выплат p:

Mc = p.

Как упоминалось в главе 25, размер всех выплат должен быть одинаковым, а значит, все элементы вектора p представляют собой одно и то же число. Что это за число? Оно может быть абсолютно любым, поскольку при его изменении нужно будет просто умножить вектор вероятностей c на определенную константу. Если требуется, чтобы сумма содержащихся в векторе c вероятностей равнялась 1, мы можем соответствующим образом масштабировать вектор p или просто скорректировать полученный ответ, разделив каждый элемент вектора c на сумму всех его элементов. Однако помните о том, что не следует заполнять вектор p одними нулями, даже если речь идет об игре с нулевой суммой, где выплаты действительно равны нулю. В таком случае единственное возможное решение, как правило, сводится к тому, чтобы заполнить одними нулями и вектор c, что, будучи верным с технической точки зрения, окажется нецелесообразно с практической.

Таким образом, мы знаем, что представляют собой вектор p и матрица выплат M, но не знаем, с какой вероятностью игрок может выбрать тот или иной вариант броска, и, соответственно, должны решить приведенное ранее уравнение относительно переменной c. Если бы мы имели дело с простыми числами, то просто разделили бы обе части уравнения на число M, то есть умножили бы их на мультипликативную инверсию числа M. Примерно то же самое нужно сделать и здесь, а именно умножить обе части уравнения на инверсию матрицы M, что в математике называется обратной матрицей и обозначается M–1.

С матрицами инверсия выполняется немного не так, как с обычными числами: умножение матрицы на свою инверсию должно давать в результате матрицу то­ждественности I с единицами на диагонали и на всех других позициях. Эту матрицу называют матрицей тождественности, потому что, умножив ее на любой вектор-столбец или матрицу, вы получите в результате тот же вектор или матрицу (точно так же число 1 называют мультипликативным тождеством, потому что умножение на 1 любого числа дает в результате то же число).

Таким образом, умножив на M–1 обе части исходного уравнения Mc = p, получим:

M–1Mc = M–1p;

c = M–1p.

То есть если мы умножим инверсию матрицы M на вектор выплат, то получим в результате вектор с относительными вероятностями каждого варианта броска. Но как получить инвертированную версию матрицы? Рассчитывать ее вручную крайне сложно, с тем же успехом мы можем просто решить соответствующую систему уравнений, совершенно не используя матрицы. Однако редакторы электронных таблиц предлагают две полезные функции, которые могут сделать эту работу за нас. Одна из них — функция MINVERSE(), она в качестве единственного параметра принимает диапазон ячеек, который рассматривается как матрица и возвращает инверсию этой матрицы. Конечно, мы не можем получить нужный результат, применяя только эту функцию, потому что матрица не может поместиться в одной ячейке. Кроме того, нам нужно умножить эту матрицу на вектор-столбец, что можно сделать с помощью функции MMULT(). В качестве двух параметров эта функция принимает диапазоны ячеек, представляющие матрицы, которые требуется перемножить (в данном случае это квадратная инвертированная версия матрицы выплат и вектор выплат).

После этого, как уже делалось раньше, следует воспользоваться клавишами Ctrl+Shift+Enter (или записать функцию ArrayFormula() в редакторе Google Sheets), чтобы электронная таблица рассматривала полученный результат как отдельный элемент выходного массива, а затем заполнить этой формулой весь вектор-столбец с помощью функции автозаполнения.

Допустим, что в нашем случае матрица выплат находится в ячейках B2:D4, а содержащий единицы вектор-столбец — в ячейках E2:E4. В таком случае введите в ячейке F2 формулу =MMULT(MINVERSE(B2:D4), E2:E4) и нажмите клавиши Ctrl+Shift+Enter. После этого в ячейках F2:F4 появятся значения вашего вектора вероятностей (рис. 37.3).

В данном случае нам нужно получить решение для игры «Камень, ножницы, бумага», в которой за победы, получаемые с помощью камня, начисляется удвоенное количество очков. Как вы могли заметить, полученные нами вероятности представляют собой очень большие числа и, естественно, не попадают в диапазон от 0 до 1. Мы можем исправить это, просто разделив каждое из этих чисел на их сумму (рис. 37.4).

Рис. 37.3

Рис. 37.4

Возможно, вас беспокоит тот факт, что в ячейке C4 вносится небольшая погрешность округления. Почему мы не можем просто записать в ней число 1? Дело в том, что у некоторых матриц нет инвертированной версии, в случае чего функция MINVERSE() возвращает сообщение об ошибке #NUM!. Если вы видите его, немного измените одно из значений и посмотрите, позволяет ли это устранить проблему. Если да, то в вашем случае нельзя найти точное решение с помощью обратной матрицы, но можно использовать другие методы или просто внести очень небольшое искажение в одну из ячеек и таким образом получить довольно близкий к истине ответ, позволяющий догадаться, как выглядит реальное решение (в данном случае это соотношение 0,25/0,50/0,25).

Решатели

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

Побочные квесты

Побочный квест 37.1. Доверяй, но проверяй

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

Альтернативная задача. Попробуйте самостоятельно найти решение для любого примера с матрицей выплат из главы 25.

Побочный квест 37.2. Создание автоматического матричного решателя

Создайте универсальный автоматический решатель для матрицы выплат размером 3 × 3. Также реализуйте резервное решение, сначала приводящее матрицу к треугольному виду (о том, как это делается, мы говорили в главе 25). Это может потребовать последовательного внесения в матрицу следующих изменений.

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

2. Если элемент, расположенный под верхним диагональным элементом, не равен нулю, сделайте следующее. Если верхний диагональный элемент равен a, а расположенный под ним элемент равен b, умножьте все элементы второй строки на –a/b и сложите их с соответствующими элементами первой.

3. Таким же образом сделайте равной нулю крайнюю левую ячейку нижней строки.

4. Если средняя ячейка второй строки равна нулю, а средняя ячейка нижней строки — нет, поменяйте местами эти строки.

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

Если вы не обнаружили ненулевой элемент на шагах 1 и 4 или если после выполнения шага 5 нижняя строка содержит только нули, то для вашей матрицы выплат невозможно найти единственное решение, поскольку она имеет бесконечное множество возможных решений (как и игра «Камень, ножницы, бумага, отбойный молоток» из главы 25). В таком случае достаточно вывести на экран соответствующее сообщение об ошибке. В противном случае вам останется лишь решить полученную треугольную матрицу, используя формулы и подстановку, и с гордостью отобразить в качестве результата вектор вероятностей. Убедитесь, что этот ответ совпадает с тем ответом, который дает решение на основе функций MMULT() и MINVERSE().

Более сложная задача. Создайте более сложную версию своего автоматического решателя для матриц выплат размером 4 × 4.

Задача-максимум. Изучите некоторые из доступных вам сторонних решателей и попробуйте применить один из них для того, чтобы обеспечить определенное соотношение между камнем, бумагой и ножницами в базовой версии игры «Камень, ножницы, бумага». Этот результат должен быть достигнут исключительно варьированием весовых коэффициентов, умножаемых на размер выигрыша, получаемого с помощью каждого варианта броска (но не использованием дополнительных бросков). Например, если нужно, чтобы на каждый выбрасываемый камень приходилось две бумаги и четверо ножниц, то каким должен быть размер выигрыша, получаемого с помощью камня, бумаги и ножниц, чтобы применение такого соотношения вариантов броска стало оптимальной стратегией?

---