Вычисление матриц Якоби и Гессе

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 5: Строка 5:
==== Вычисление матрицы Якоби ====
==== Вычисление матрицы Якоби ====
-
Пусть задана система <tex>m</tex> функций <tex>y_1(x_1, x_2, \dots x_n) \dots y_m(x_1, x_2, \dots x_n)</tex> от <tex>m</tex> переменных. '''Матрицей Якоби''' данной системы функций называется
+
Пусть задана система <tex>n</tex> функций <tex>y_1(x_1, x_2, \dots x_m) \dots y_n(x_1, x_2, \dots x_m)</tex> от <tex>m</tex> переменных. '''Матрицей Якоби''' или '''якобианом''' данной системы функций называется
матрица, составленная из частных производных этих функций по всем переменным.
матрица, составленная из частных производных этих функций по всем переменным.
<tex>
<tex>
-
J=\begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial y_m}{\partial x_1} & \cdots & \frac{\partial y_m}{\partial x_n} \end{bmatrix}.
+
J=\begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_1}{\partial x_m} \\ \vdots & \ddots & \vdots \\ \frac{\partial y_n}{\partial x_1} & \cdots & \frac{\partial y_n}{\partial x_m} \end{bmatrix}.
</tex>
</tex>
Строка 28: Строка 28:
Если в некоторой точке <tex>x_1 \dots x_m </tex> очень сложно или невозможно вычислить частные производные, <tex>\frac{\partial^2 y}{\partial x_i\ \partial x_j} </tex>, то для вычисления матрицы Гессе применяются методы численного дифференцирования.
Если в некоторой точке <tex>x_1 \dots x_m </tex> очень сложно или невозможно вычислить частные производные, <tex>\frac{\partial^2 y}{\partial x_i\ \partial x_j} </tex>, то для вычисления матрицы Гессе применяются методы численного дифференцирования.
-
== Изложение метода ==
+
== Изложение методов ==
 +
=== Прямое вычисление частных производных ===
Для вычисления матрицы Якоби в заданной необходимо найти частные производные всех функций системы по всем переменным. Для вычисления
Для вычисления матрицы Якоби в заданной необходимо найти частные производные всех функций системы по всем переменным. Для вычисления
-
производной <tex>\frac{\partial y_i}{\partial x_j} </tex> можно воспользоваться любым из методов [[ Вычисление первой производной|вычисления первой производной]].
+
производной <tex>\frac{\partial y_i}{\partial x_j} </tex> применяются методы [[ Вычисление первой производной|вычисления первой производной]].
 +
 
 +
Формула для элемента якобиана при использовании правой разностной производной: <br/>
 +
<tex> J_{ij} = \frac {y_i(x_1 \dots x_j + h_{ij} \dots x_m) - y_i(x_1 \dots x_m)} {h_{ij} } </tex>
 +
 
 +
Формула для элемента якобиана при использовании центральной разностной производной:
 +
<br/>
 +
<tex> J_{ij} = \frac {y_i(x_1 \dots x_j + h_{ij} \dots x_m) - y_i(x_1 \dots x_j - h_{ij} \dots x_m)} {2*h_{ij}} </tex>
 +
 
 +
<br/>
 +
 
 +
 
 +
Вычисление якобиана с использованием правой разностной производной требует вычислять значения функций в <tex>m * (n + 1) </tex>
 +
точках. Если использовать центральную производную, то нужно находить значения функций <tex> y_1 \dots y_n </tex> в <tex>2 * m * n </tex> точках. С другой, стороны погрешность правой производной имеет порядок <tex>o(h)</tex> а центральной - <tex>o(h^2)</tex>.
 +
В большинстве случаев вычисление значения функции <tex>y_i</tex> - это затратная по времени операция, поэтому используется правая разностная производная.
 +
 
 +
====Оценка погрешности метода====
 +
Основная проблема при вычислении каждого элемента матрицы Якоби - как правильно выбрать шаг метода <tex> h_{ij} </tex>. Шаг выбирается независимо для каждого элемента матрицы.
 +
 
 +
Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной.
 +
Для сокращения записи введём обозначения <tex>f(\xi_j) = y_i(x_1 \dots \xi_j \dots x_m) </tex>
 +
Остаточный член в соотношении <tex> \f(x)' \approx \frac{f(x+ h) - f1}{h} </tex> имеет вид
 +
<tex>r_1 = - f''(\xi)h/2 </tex>.
 +
Если <tex> |f''(\xi)| \le M_2 </tex>, то <tex>|r_1| \le M_2*h/2 </tex>
 +
Если значения <tex>f1</tex> и <tex>f2</tex> заданы с погрешностями <tex>\eps_1, eps_2 \le E</tex> , то погрешность будет
 +
содержать ещё одно слагаемое <tex> r2} = - \frac{\eps_1 - \eps_2}{h} \le 2E/h </tex>. Таким образом, оценка суммарной погрешности имеет вид <tex>|r| \le |r1| + |r2| \le f(h) = M_2 h/2 + 2E/h </tex> . Эта оценка достигает минимума при
 +
<tex>h_0 = 2 \sqrt {E/M_2}</tex>. При этом <tex> f(h_0) = 2 \sqrt{M_2 E} </tex>.
 +
Оценка погрешности имеет один глобальный миниум. Поэтому выбор очень маленького шага не привидёт к росту точности. С При величине шага, близкой к <tex>h_0</tex> погрешность имеет порядок <tex>O(\sqrt E) </tex>. Чтобы найти оптимальный
 +
 
 +
 
 +
 
 +
===Метод Бройдена===
 +
Чаще всего вычисление якобиана является одной из подзадач в различных методах оптимизации и решения систем нелинейных уравнений.
 +
При решении систем нелинейных уравнений методом Ньютона требуется вычислять якобиан на каждой итерации.
 +
Вычисление якобиана требует вычисления функций в <tex>O(m * n)</tex> точках. Это сложная и затратная по времени операция. Суть
 +
метода Бройдена состоит в том, чтобы вычислить якобиан аналитически или с помощью метода конечных разностей на первой итерации,
 +
а после этого на каждой итерации обновлять якобиан, не вычисляя значения функций <tex>y_1 \dots y_n</tex> и их производных.
 +
 
 +
Пусть задана система нелинейных уравнений <tex>F(x) = 0</tex>, где <tex> F \colon R^m \mapsto R^n </tex>.
 +
Тогда якобиан на <tex>n</tex>-ой итерации выражается по формуле <br/>
 +
<tex>
 +
J_n = J_{n - 1} + \frac{F(x_n) - F(x_{n-1}) - J_{n - 1} (x_n - x_{n-1})} { ||x_n - x_{n-1}||^2} (x_n - x_{n-1})^T
 +
</tex>
 +
 
 +
После этого следующее приближение вычисляется по формуле
 +
 
 +
<tex>x_{n + 1} = x_n - J_n^{-1} F(x_n) </tex>
 +
 
 +
 
== Числовой пример ==
== Числовой пример ==
== Рекомендации программисту ==
== Рекомендации программисту ==
 +
Вычисление матрицы Якоби требует большого числа операций. Поэтому при выборе метода её вычисления следует найти оптимальный баланс
 +
между погрешностью метода и его скоростью.
 +
== Заключение ==
== Заключение ==

Версия 20:23, 20 октября 2008

Содержание

Введение

Постановка математической задачи

Вычисление матрицы Якоби

Пусть задана система n функций y_1(x_1, x_2, \dots x_m) \dots y_n(x_1, x_2, \dots x_m) от m переменных. Матрицей Якоби или якобианом данной системы функций называется матрица, составленная из частных производных этих функций по всем переменным.


J=\begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial y_1}{\partial x_m} \\ \vdots & \ddots & \vdots \\ \frac{\partial y_n}{\partial x_1} & \cdots & \frac{\partial y_n}{\partial x_m} \end{bmatrix}.

Если в некоторой точке x_1 \dots x_m очень сложно или невозможно вычислить частные производные, \frac{\partial y_i}{\partial x_j} , то для вычисления матрицы Якоби применяются методы численного дифференцирования.

Вычисление матрицы Гессе

Матрицей Гессе функции m переменных y(x_1 \dots x_m) называется матрица, составленная из вторых производных функции y(x_1 \dots x_m) по всем переменным


H(f) = \begin{bmatrix}
\frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1\,\partial x_m} \\  \\
\frac{\partial^2 f}{\partial x_2\,\partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2\,\partial x_m} \\  \\
\vdots & \vdots & \ddots & \vdots \\  \\
\frac{\partial^2 f}{\partial x_m\,\partial x_1} & \frac{\partial^2 f}{\partial x_m\,\partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_m^2}
\end{bmatrix}

Если в некоторой точке x_1 \dots x_m очень сложно или невозможно вычислить частные производные, \frac{\partial^2 y}{\partial x_i\ \partial x_j} , то для вычисления матрицы Гессе применяются методы численного дифференцирования.

Изложение методов

Прямое вычисление частных производных

Для вычисления матрицы Якоби в заданной необходимо найти частные производные всех функций системы по всем переменным. Для вычисления производной \frac{\partial y_i}{\partial x_j} применяются методы вычисления первой производной.

Формула для элемента якобиана при использовании правой разностной производной:
 J_{ij} = \frac {y_i(x_1 \dots x_j + h_{ij} \dots x_m) - y_i(x_1 \dots x_m)} {h_{ij} }

Формула для элемента якобиана при использовании центральной разностной производной:
 J_{ij} = \frac {y_i(x_1 \dots x_j + h_{ij} \dots x_m) - y_i(x_1 \dots x_j - h_{ij} \dots x_m)} {2*h_{ij}}



Вычисление якобиана с использованием правой разностной производной требует вычислять значения функций в m * (n + 1) точках. Если использовать центральную производную, то нужно находить значения функций  y_1 \dots y_n в 2 * m * n   точках. С другой, стороны погрешность правой производной имеет порядок o(h) а центральной - o(h^2). В большинстве случаев вычисление значения функции y_i - это затратная по времени операция, поэтому используется правая разностная производная.

Оценка погрешности метода

Основная проблема при вычислении каждого элемента матрицы Якоби - как правильно выбрать шаг метода  h_{ij} . Шаг выбирается независимо для каждого элемента матрицы.

Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной. Для сокращения записи введём обозначения f(\xi_j) = y_i(x_1 \dots \xi_j \dots x_m) Остаточный член в соотношении  \f(x)' \approx \frac{f(x+ h) - f1}{h} имеет вид r_1 = - f''(\xi)h/2 . Если  |f''(\xi)| \le M_2 , то |r_1| \le M_2*h/2 Если значения f1 и f2 заданы с погрешностями \eps_1, eps_2 \le E , то погрешность будет содержать ещё одно слагаемое  r2} = - \frac{\eps_1 - \eps_2}{h} \le 2E/h . Таким образом, оценка суммарной погрешности имеет вид |r| \le |r1| + |r2| \le f(h) = M_2 h/2 + 2E/h . Эта оценка достигает минимума при h_0 = 2 \sqrt {E/M_2}. При этом  f(h_0) = 2 \sqrt{M_2 E} . Оценка погрешности имеет один глобальный миниум. Поэтому выбор очень маленького шага не привидёт к росту точности. С При величине шага, близкой к h_0 погрешность имеет порядок O(\sqrt E) . Чтобы найти оптимальный


Метод Бройдена

Чаще всего вычисление якобиана является одной из подзадач в различных методах оптимизации и решения систем нелинейных уравнений. При решении систем нелинейных уравнений методом Ньютона требуется вычислять якобиан на каждой итерации. Вычисление якобиана требует вычисления функций в O(m * n) точках. Это сложная и затратная по времени операция. Суть метода Бройдена состоит в том, чтобы вычислить якобиан аналитически или с помощью метода конечных разностей на первой итерации, а после этого на каждой итерации обновлять якобиан, не вычисляя значения функций y_1 \dots y_n и их производных.

Пусть задана система нелинейных уравнений F(x) = 0, где  F \colon R^m \mapsto R^n . Тогда якобиан на n-ой итерации выражается по формуле

J_n = J_{n - 1} + \frac{F(x_n) - F(x_{n-1}) - J_{n - 1} (x_n - x_{n-1})} { ||x_n - x_{n-1}||^2} (x_n - x_{n-1})^T

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

x_{n + 1} = x_n - J_n^{-1} F(x_n)


Числовой пример

Рекомендации программисту

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

Заключение

Список литературы

  • А. А. Самарский, А. В. Гулин. Численные методы. Москва «Наука», 1989.
  • Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. Численные методы. Лаборатория Базовых Знаний, 2003.
  • Магнус Я. Р., Нейдеккер Х. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике: Пер. с англ./ Под ред. С. А. Айвазяна. — М.:ФИЗМАТЛИТ, 2002. — 496 с.
  • Хайкин С. Нейронные сети, полный курс. 2е издание, испр. - М: Вильямс. 2008. - 1103 с. ISBN 978-5-8459-0890-2
Личные инструменты