Книга: Программирование на языке Ruby

5.10. Перемножение матриц

5.10. Перемножение матриц

Стандартная библиотека matrix предназначена для выполнения операций над числовыми матрицами. В ней определено два класса: Matrix и Vector.

Следует также знать о прекрасной библиотеке NArray, которую написал Масахиро Танака (Masahiro Tanaka) — ее можно найти на сайте www.rubyforge.org. Хотя эта библиотека не относится к числу стандартных, она широко известна и очень полезна. Если вы предъявляете повышенные требования к быстродействию, нуждаетесь в особом представлении данных или желаете выполнять быстрое преобразование Фурье, обязательно ознакомьтесь с этим пакетом. Впрочем, для типичных применений стандартной библиотеки matrix должно хватить, поэтому именно ее мы и рассмотрим.

Чтобы создать матрицу, мы, конечно же, обращаемся к методу класса. Сделать это можно несколькими способами. Самый простой — вызвать метод Matrix.[] и перечислить строки в виде массивов. Ниже мы записали вызов на нескольких строчках, но, разумеется, это необязательно:

m = Matrix[[1,2,3],
           [4,5,6],
           [7,8,9]]

Вместо этого можно вызвать метод rows, передав ему массив массивов (в таком случае «дополнительные» скобки необходимы). Необязательный параметр сору, по умолчанию равный true, указывает, надо ли скопировать переданные массивы или просто сохранить на них ссылки. Оставляйте значение true, если нужно защитить исходные массивы от изменения, и задавайте false, если это несущественно.

Row1 = [2,3]
row2 = [4,5]
m1 = Matrix.rows([row1,row2])       # copy=true
m2 = Matrix.rows([row1,row2],false) # He копировать.
row1[1] = 99                        # Теперь изменим row1.
p m1                                # Matrix[[2, 3], [4, 5]]
p m2                                # Matrix[[2, 99], [4, 5]]

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

m1 = Matrix.rows([[1,2],[3,4]])
m2 = Matrix.columns([[1,3],[2,4]]) # m1 == m2

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

Некоторые специальные матрицы, особенно квадратные, конструируются проще. Так, тождественную матрицу конструирует метод identity (или его синонимы I и unit):

im1 = Matrix.identity(3) # Matrix[[1,0,0],[0,1,0],[0,0,1]]
im2 = Matrix.I(3)        # То же самое.
im3 = Matrix.unit(3)     # То же самое.

Более общий метод scalar строит диагональную матрицу, в которой все элементы на диагонали одинаковы, но не обязательно равны 1:

sm = Matrix.scalar(3,8) # Matrix[[8,0,0],[0,8,0],[0,0,8]]

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

dm = Matrix.diagonal(2,3,7) # Matrix[[2,0,0],[0,3,0],[0,0,7]]

Метод zero создает нулевую матрицу заданной размерности (все элементы равны 0):

zm = Matrix.zero(3) # Matrix[[0,0,0],[0,0,0],[0,0,0]]

Понятно, что методы identity, scalar, diagonal и zero создают квадратные матрицы.

Чтобы создать матрицу размерности 1?N или N?1, воспользуйтесь методом row_vector или column_vector соответственно.

а = Matrix.row_vector(2,4,6,8)    # Matrix[[2,4,6,8]]
b = Matrix.column_vector(6,7,8,9) # Matrix[[6],[7],[8],[9]]

К отдельным элементам матрицы можно обращаться, указывая индексы в квадратных скобках (оба индекса заключаются в одну пару скобок). Отметим, что не существует метода []=. По той же причине, по которой его нет в классе Fixnum: матрицы — неизменяемые объекты (такое решение было принято автором библиотеки).

m = Matrix[[1,2,3],[4,5,6]]
puts m[1,2] # 6

Индексация начинается с 0, как и для массивов в Ruby. Возможно, это противоречит вашему опыту работы с матрицами, но индексация с 1 в качестве альтернативы не предусмотрена. Можно реализовать эту возможность самостоятельно:

# Наивный подход... не поступайте так!
class Matrix
 alias bracket []
 def [] (i,j)
  bracket(i-1,j-1)
 end
end
m = Matrix[[1,2,3],[4,5,6],[7,8,9]]
p m[2,2] # 5

На первый взгляд, этот код должен работать. Большинство операций над матрицами даже будет давать правильный результат при такой индексации. Так в чем же проблема? В том, что мы не знаем деталей внутренней реализации класса Matrix. Если в нем для доступа к элементам матрицы всегда используется собственный метод [], то все будет хорошо. Но если где-нибудь имеются прямые обращения к внутреннему массиву или применяются иные оптимизированные решения, то возникнет ошибка. Поэтому, решившись на такой трюк, вы должны тщательно протестировать новое поведение.

К тому же необходимо изменить методы row и vector. В них индексы тоже начинаются с 0, но метод [] не вызывается. Я не проверял, что еще придется модифицировать.

Иногда необходимо узнать размерность или форму матрицы. Для этого есть разные методы, например row_size и column_size.

Метод row_size возвращает число строк в матрице. Что касается метода column_size, тут есть одна тонкость: он проверяет лишь размер первой строки. Если по каким-либо причинам матрица не прямоугольная, то полученное значение бессмысленно. Кроме того, поскольку метод square? (проверяющий, является ли матрица квадратной) обращается к row_size и column_size, его результат тоже нельзя считать стопроцентно надежным.

m1 = Matrix[[1,2,3],[4,5,6],[7,8,9]]
m2 = Matrix[[1,2,3],[4,5,6],[7,8]]
m1.row_.size   # 3
m1.column_size # 3 m2.row_size # 3
m2.column_size # 3 (неправильно)
m1.square?     # true
m2.square?     # true (неправильно)

Решить эту мелкую проблему можно, например, определив метод rectangular?.

class Matrix
 def rectangular?
  arr = to_a
  first = arr[0].size
  arr[1..-1].all? {|x| x.size == first }
 end
end

Можно, конечно, модифицировать метод square?, так чтобы сначала он проверял, является ли матрица прямоугольной. В таком случае нужно будет изменить метод column_size, чтобы он возвращал nil для непрямоугольной матрицы.

Для вырезания части матрицы имеется несколько методов. Метод row_vectors возвращает массив объектов класса Vector, представляющих строки (см. обсуждение класса Vector ниже.) Метод column_vectors работает аналогично, но для столбцов. Наконец, метод minor возвращает матрицу меньшего размера; его параметрами являются либо четыре числа (нижняя и верхняя границы номеров строк и столбцов), либо два диапазона.

m = Matrix[[1,2,3,4],[5,6,7,8],[6,7,8,9]]
rows = m.row_vectors # Три объекта Vector.
cols = m.column_vectors # Четыре объекта Vector.
m2 = m.minor(1,2,1,2) # Matrix[[6,7,],[7,8]]
m3 = m.minor(0..1,1..3) # Matrix[[[2,3,4],[6,7,8]]

К матрицам применимы обычные операции: сложение, вычитание, умножение и деление. Для выполнения некоторых из них должны соблюдаться ограничения на размеры матриц-операндов; в противном случае будет возбуждено исключение (например, при попытке перемножить матрицы размерностей 3?3 и 4?4).

Поддерживаются стандартные преобразования: inverse (обращение), transpose (транспонирование) и determinant (вычисление определителя). Для целочисленных матриц определитель лучше вычислять с помощью библиотеки mathn (раздел 5.12).

Класс Vector — это, по существу, частный случай одномерной матрицы. Его объект можно создать с помощью методов [] или elements; в первом случае параметром является развернутый массив, а во втором — обычный массив и необязательный параметр сору (по умолчанию равный true).

arr = [2,3,4,5]
v1 = Vector[*arr]               # Vector[2,3,4,5]
v2 = Vector.elements(arr)       # Vector[2,3,4,5]
v3 = Vector.elements(arr,false) # Vector[2,3,4,5]
arr[2] = 7                      # теперь v3 - Vector[2,3,7,5].

Метод covector преобразует вектор длины N в матрицу размерности N?1 (выполняя попутно транспонирование).

v = Vector[2,3,4]
m = v.covector # Matrix[[2,3,4]]

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

v1 = Vector[2,3,4]
v2 = Vector[4,5,6]
v3 = v1 + v2        # Vector[6,8,10]
v4 = v1*v2.covector # Matrix![8,10,12],[12,15,18],[16,20,24]]
v5 = v1*5           # Vector[10,15,20]

Имеется метод inner_product (скалярное произведение):

v1 = Vector[2,3,4]
v2 = Vector[4,5,6]
x = v1.inner_product(v2) # 47

Дополнительную информацию о классах Matrix и vector можно найти в любом справочном руководстве, например воспользовавшись командной утилитой ri, или на сайте ruby-doc.org.

Оглавление книги