Оптимальное вычисление матрицы Якоби

8.6. Оптимальное вычисление матрицы Якоби#

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

Пусть дана функция $f : R^{n} \to R^{m}$ и стоит задача вычисления её матрицы Якоби

J_{i j} = \frac{\partial f_{i}}{\partial x_{j}} (x_{1}, \dots, x_{n}), i = 1, \dots, m, j = 1, \dots, n,

за минимальное число операций. Как нам уже известно, при $n ≫ m$ эффективней по быстродействию использовать автоматическое дифференцирование назад, а в обратном случае $n ≪ m$ — дифференцирование вперёд.

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

Мы продемонстрируем эту идею на функции с (очень) специфическим графом вычислений, показанном на Рисунке 8.11.

../_images/graph-cross-example.svg — Рис. 8.11 Пример графа вычисления, для которого эффективно использовать оба вида дифференцирования. Промежуточное значение $g$ является точкой сочленения.#

В этом случае разумно использовать оба вида дифференцирования. Для этого представим исходную функцию $f$ в виде

f_{i} = f_{i} (g (x_{1}, \dots, x_{n})), i = 1, \dots, m,

где промежуточное значение $g$ является функцией $R^{n} \to R$ . Тогда производные (элементы матрицы Якоби) имеют вид

J_{i j} = \frac{\partial f_{i}}{\partial x_{j}} = \frac{\partial f_{i}}{\partial g} \frac{\partial g}{\partial x_{j}} .

Производные $\partial g / \partial x_{j}$ эффективно вычисляются дифференцированием назад, поскольку $n ≫ 1$ . В свою очередь, производные $\partial f_{i} / \partial g$ эффективно вычисляются дифференцированием вперёд ( $1 ≪ m$ ).

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