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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Оценка погрешности метода)
Строка 52: Строка 52:
Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной.
Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной.
Для сокращения записи введём обозначения <tex>f(\xi_j) = y_i(x_1 \dots \xi_j \dots x_m) </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> f(x)' \approx \frac{f(x+ h) - f1}{h} </tex> имеет вид
<tex>r_1 = - f''(\xi)h/2 </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> |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>f1</tex> и <tex>f2</tex> заданы с погрешностями <tex>\vareps_1, \vareps_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> r2} = - \frac{\vareps_1 - \vareps_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 = 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>h_0</tex> погрешность имеет порядок <tex>O(\sqrt E) </tex>. Чтобы найти оптимальный
===Метод Бройдена===
===Метод Бройдена===

Версия 20:58, 22 октября 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 заданы с погрешностями \vareps_1, \vareps_2 \le E , то погрешность будет содержать ещё одно слагаемое  r2} = - \frac{\vareps_1 - \vareps_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)

Методы вычисления матрицы Гессе

Как и матрица Якоби, матрица Гессе может быть вычислена с помощью разностной аппроксимации производных.  \frac{\partial^2 f}{\partial x_i\,\partial x_j} = 
\frac{ f(x + (e_i + e_j) h) - f(x + e_i h) - f(x + e_j h) + f(x) } {h^2}, где x - вектор переменных, а e_i и e_j - единичные вектора. Эта формула требует вычисления значений функции  f в  \frac {n (n + 1)} {2} точках. Погрешность формулы имеет порядок O(h).

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

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

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

Заключение

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

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