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

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

(Различия между версиями)

Перейти к: навигация, поиск

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

Содержание

1 Введение
- 1.1 Постановка математической задачи
  - 1.1.1 Вычисление матрицы Якоби
  - 1.1.2 Вычисление матрицы Гессе
2 Изложение методов
- 2.1 Прямое вычисление частных производных
  - 2.1.1 Оценка погрешности метода
- 2.2 Метод Бройдена
3 Числовой пример
4 Рекомендации программисту
5 Заключение
6 Список литературы

Введение

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

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

Пусть задана система $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

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86_%D0%AF%D0%BA%D0%BE%D0%B1%D0%B8_%D0%B8_%D0%93%D0%B5%D1%81%D1%81%D0%B5»

Категории: Незавершённые статьи | Численное дифференцирование | Учебные задачи | Регрессионный анализ

@@ Строка 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>
-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>
@@ Строка 28: / Строка 28: @@
 Если в некоторой точке <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>
 == Числовой пример ==
 == Рекомендации программисту ==
+Вычисление матрицы Якоби требует большого числа операций.  Поэтому при выборе метода её вычисления следует найти оптимальный баланс
+между погрешностью метода и его скоростью.
 == Заключение ==