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

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

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

\[J_{i j} = \frac{\partial f_i}{\partial x_j}(x_1, \dots, x_n), \quad i = 1, \dots, m,\ j = 1, \dots, n,\]

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

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

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

Рис. 8.11 Пример графа вычисления, для которого эффективно использовать оба вида дифференцирования. Промежуточное значение \(g\) является точкой сочленения.

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

\[f_i = f_i(g(x_1, \dots, x_n)), \quad i = 1, \dots, m,\]

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

\[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 \gg 1\). В свою очередь, производные \(\partial f_i / \partial g\) эффективно вычисляются дифференцированием вперёд (\(1 \ll m\)).

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