Вычисление матриц Якоби и Гессе
Материал из MachineLearning.
м (→Оценка погрешности метода) |
(→Оценка погрешности метода) |
||
Строка 58: | Строка 58: | ||
содержать ещё одно слагаемое <tex> r_2 = - \frac{\vareps_1 - \vareps_2}{h} \le 2E/h </tex>. Таким образом, оценка суммарной погрешности имеет вид <tex>|r| \le |r_1| + |r_2| \le f(h) = M_2 h/2 + 2E/h </tex>. Эта оценка достигает минимума при | содержать ещё одно слагаемое <tex> r_2 = - \frac{\vareps_1 - \vareps_2}{h} \le 2E/h </tex>. Таким образом, оценка суммарной погрешности имеет вид <tex>|r| \le |r_1| + |r_2| \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>. |
===Метод Бройдена=== | ===Метод Бройдена=== |
Версия 15:30, 23 октября 2008
Содержание |
Введение
Постановка математической задачи
Вычисление матрицы Якоби
Пусть задана система функций от переменных. Матрицей Якоби или якобианом данной системы функций называется матрица, составленная из частных производных этих функций по всем переменным.
Если в некоторой точке очень сложно или невозможно вычислить частные производные, , то для вычисления матрицы Якоби применяются методы численного дифференцирования.
Вычисление матрицы Гессе
Матрицей Гессе функции переменных называется матрица, составленная из вторых производных функции по всем переменным
Если в некоторой точке очень сложно или невозможно вычислить частные производные, , то для вычисления матрицы Гессе применяются методы численного дифференцирования.
Методы вычисления матрицы Якоби
Прямое вычисление частных производных
Для вычисления матрицы Якоби в заданной необходимо найти частные производные всех функций системы по всем переменным. Для вычисления производной применяются методы вычисления первой производной.
Формула для элемента якобиана при использовании правой разностной производной:
Формула для элемента якобиана при использовании центральной разностной производной:
Вычисление якобиана с использованием правой разностной производной требует вычислять значения функций в
точках. Если использовать центральную производную, то нужно находить значения функций в точках. С другой, стороны погрешность правой производной имеет порядок а центральной - .
В большинстве случаев вычисление значения функции - это затратная по времени операция, поэтому используется правая разностная производная.
Оценка погрешности метода
Основная проблема при вычислении каждого элемента матрицы Якоби - как правильно выбрать шаг метода . Шаг выбирается независимо для каждого элемента матрицы.
Проанализируем зависимость погрешности метода от величины шага в случае использования правой разностной производной. Для сокращения записи введём обозначения . Остаточный член в соотношении имеет вид . Если , то Если значения и заданы с погрешностями , то погрешность будет содержать ещё одно слагаемое . Таким образом, оценка суммарной погрешности имеет вид . Эта оценка достигает минимума при . При этом . Оценка погрешности имеет один глобальный миниум. Поэтому выбор очень маленького шага не привидёт к росту точности. При величине шага, близкой к погрешность имеет порядок .
Метод Бройдена
Чаще всего вычисление якобиана является одной из подзадач в различных методах оптимизации и решения систем нелинейных уравнений. При решении систем нелинейных уравнений методом Ньютона требуется вычислять якобиан на каждой итерации. Вычисление якобиана требует вычисления функций в точках. Это сложная и затратная по времени операция. Суть метода Бройдена состоит в том, чтобы вычислить якобиан аналитически или с помощью метода конечных разностей на первой итерации, а после этого на каждой итерации обновлять якобиан, не вычисляя значения функций и их производных.
Пусть задана система нелинейных уравнений , где .
Тогда якобиан на -ой итерации выражается по формуле
После этого следующее приближение вычисляется по формуле
Методы вычисления матрицы Гессе
Как и матрица Якоби, матрица Гессе может быть вычислена с помощью разностной аппроксимации производных. , где - вектор переменных, а и - единичные вектора. Эта формула требует вычисления значений функции в точках. Погрешность формулы имеет порядок .
Численный эксперимент
В качестве примера рассчитаем с помощью вышеизложенного метода матрицу Гессе функции в точке (1, 1)
Величина шага | Численный результат | Истинное значение | Погрешность |
---|---|---|---|
0.01 |
|
|
|
0.001 |
|
|
|
0.0001 |
|
|
|
0.00001 |
|
|
|
Рекомендации программисту
Вычисление матрицы Якоби требует большого числа операций. Поэтому при выборе метода её вычисления следует найти оптимальный баланс между погрешностью метода и его скоростью.
Программа для вычисления якобиана, исходный код [1кб]
Программа для вычисления гессиана, исходный код [1кб]
Библиотека алгоритмов линейной алгебры [180кб]
Заключение
Список литературы
- А. А. Самарский, А. В. Гулин. Численные методы. Москва «Наука», 1989.
- Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. Численные методы. Лаборатория Базовых Знаний, 2003.
- Магнус Я. Р., Нейдеккер Х. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике: Пер. с англ./ Под ред. С. А. Айвазяна. — М.:ФИЗМАТЛИТ, 2002. — 496 с.
- Хайкин С. Нейронные сети, полный курс. 2е издание, испр. - М: Вильямс. 2008. - 1103 с. ISBN 978-5-8459-0890-2