Вычисление матриц Якоби и Гессе
Материал из MachineLearning.
Строка 5: | Строка 5: | ||
==== Вычисление матрицы Якоби ==== | ==== Вычисление матрицы Якоби ==== | ||
- | Пусть задана система <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 | + | 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
Содержание |
Введение
Постановка математической задачи
Вычисление матрицы Якоби
Пусть задана система функций от переменных. Матрицей Якоби или якобианом данной системы функций называется матрица, составленная из частных производных этих функций по всем переменным.
Если в некоторой точке очень сложно или невозможно вычислить частные производные, , то для вычисления матрицы Якоби применяются методы численного дифференцирования.
Вычисление матрицы Гессе
Матрицей Гессе функции переменных называется матрица, составленная из вторых производных функции по всем переменным
Если в некоторой точке очень сложно или невозможно вычислить частные производные, , то для вычисления матрицы Гессе применяются методы численного дифференцирования.
Изложение методов
Прямое вычисление частных производных
Для вычисления матрицы Якоби в заданной необходимо найти частные производные всех функций системы по всем переменным. Для вычисления производной применяются методы вычисления первой производной.
Формула для элемента якобиана при использовании правой разностной производной:
Формула для элемента якобиана при использовании центральной разностной производной:
Вычисление якобиана с использованием правой разностной производной требует вычислять значения функций в
точках. Если использовать центральную производную, то нужно находить значения функций в точках. С другой, стороны погрешность правой производной имеет порядок а центральной - .
В большинстве случаев вычисление значения функции - это затратная по времени операция, поэтому используется правая разностная производная.
Оценка погрешности метода
Основная проблема при вычислении каждого элемента матрицы Якоби - как правильно выбрать шаг метода . Шаг выбирается независимо для каждого элемента матрицы.
Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной. Для сокращения записи введём обозначения Остаточный член в соотношении имеет вид . Если , то Если значения и заданы с погрешностями , то погрешность будет содержать ещё одно слагаемое . Таким образом, оценка суммарной погрешности имеет вид . Эта оценка достигает минимума при . При этом . Оценка погрешности имеет один глобальный миниум. Поэтому выбор очень маленького шага не привидёт к росту точности. С При величине шага, близкой к погрешность имеет порядок . Чтобы найти оптимальный
Метод Бройдена
Чаще всего вычисление якобиана является одной из подзадач в различных методах оптимизации и решения систем нелинейных уравнений. При решении систем нелинейных уравнений методом Ньютона требуется вычислять якобиан на каждой итерации. Вычисление якобиана требует вычисления функций в точках. Это сложная и затратная по времени операция. Суть метода Бройдена состоит в том, чтобы вычислить якобиан аналитически или с помощью метода конечных разностей на первой итерации, а после этого на каждой итерации обновлять якобиан, не вычисляя значения функций и их производных.
Пусть задана система нелинейных уравнений , где .
Тогда якобиан на -ой итерации выражается по формуле
После этого следующее приближение вычисляется по формуле
Числовой пример
Рекомендации программисту
Вычисление матрицы Якоби требует большого числа операций. Поэтому при выборе метода её вычисления следует найти оптимальный баланс между погрешностью метода и его скоростью.
Заключение
Список литературы
- А. А. Самарский, А. В. Гулин. Численные методы. Москва «Наука», 1989.
- Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. Численные методы. Лаборатория Базовых Знаний, 2003.
- Магнус Я. Р., Нейдеккер Х. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике: Пер. с англ./ Под ред. С. А. Айвазяна. — М.:ФИЗМАТЛИТ, 2002. — 496 с.
- Хайкин С. Нейронные сети, полный курс. 2е издание, испр. - М: Вильямс. 2008. - 1103 с. ISBN 978-5-8459-0890-2