Участник:Oleggium/Метод Ньютона для решения систем нелинейных уравнений(2): различия между версиями
Dimx19 (обсуждение | вклад) |
Dimx19 (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{algorithm | {{algorithm | ||
| name = Метод Ньютона | | name = Метод Ньютона | ||
− | | serial_complexity = <math>O(n^3)</math> | + | | serial_complexity = <math>O(n^3)</math> в случае решения СЛАУ методом Гаусса |
− | | input_data = n n-мерных функций (так же дополнительно могут быть даны производные) + n-мерный вектор - начальное приближение | + | | input_data = <math>F(x)</math> - <math>n</math> <math>n</math>-мерных функций (так же дополнительно могут быть даны производные) + <math>n</math>-мерный вектор <math>x^0</math> - начальное приближение |
− | | output_data = n-мерный вектор | + | | output_data = <math>n</math>-мерный вектор |
}} | }} | ||
Авторы: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]] | Авторы: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]] | ||
Строка 14: | Строка 14: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
− | Рассмотрим систему нелинейных уравнений | + | Рассмотрим систему нелинейных уравнений<ref name="VOLA">http://www.apmath.spbu.ru%2Fru%2Fstructure%2Fdepts%2Fis%2Fcourse2task4_1.pdf</ref> |
<math>F(x) = 0, F(x), x \in \mathbb{R}^{n}, (1)</math> | <math>F(x) = 0, F(x), x \in \mathbb{R}^{n}, (1)</math> | ||
Строка 74: | Строка 74: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
+ | |||
+ | Вычислительными ядрами данного алгоритма являются: | ||
+ | |||
+ | * Численное вычисление Якобиана(в случае, если производные не даны) <math>\frac{\partial F(x^k)}{\partial x} </math> | ||
+ | * Решение СЛАУ(например, методом Гаусса) <math>\frac{\partial F(x^k)}{\partial x} \cdot \Delta x^k = -F(x^k)</math> | ||
+ | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
+ | |||
+ | Как уже было описано в вычислительном ядре, данный метод сводится к решению СЛАУ. | ||
+ | |||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
− | + | Входные данные:<math>F(x)</math> - <math>n</math> <math>n</math>-мерных функций; <math>n</math>-мерный вектор <math>x^0</math> - начальное приближение. | |
+ | <math>\varepsilon</math> - точность | ||
+ | |||
− | + | ---- | |
− | |||
<math>x^k = x^0</math> | <math>x^k = x^0</math> | ||
− | + | '''DO''' | |
− | + | :Вычисляем <math>\frac{\partial F(x^k)}{\partial x} </math> (если производные не даны, то их можно вычислить численно) | |
− | + | :Вычисляем <math>F(x^k)</math> | |
− | + | :Решаем СЛАУ(например, методом Гаусса) <math>\frac{\partial F(x^k)}{\partial x} \cdot \Delta x^k = -F(x^k)</math> | |
+ | :<math>x^{k} = x^k + \Delta x^k</math> | ||
+ | '''WHILE''' <math>||\Delta x^k|| < \varepsilon</math> | ||
+ | |||
+ | ---- | ||
+ | |||
+ | Выходные данные: численное решение <math>x^k</math> | ||
+ | |||
+ | |||
+ | === Последовательная сложность алгоритма === | ||
+ | |||
− | |||
− | |||
− | |||
+ | |||
=== Информационный граф === | === Информационный граф === | ||
Строка 102: | Строка 120: | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
+ | |||
+ | Входные данные:<math>F(x)</math> - <math>n</math> <math>n</math>-мерных функций; <math>n</math>-мерный вектор <math>x^0</math> - начальное приближение. | ||
+ | <math>\varepsilon</math> - точность | ||
+ | |||
+ | Выходные данные: численное решение <math>x^k</math> | ||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Строка 110: | Строка 133: | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
+ | |||
+ | Как уже было сказано, основная часть данного алгоритма составляет решение СЛАУ. Поэтому, целесообразно не искать уже реализованный алгоритм, а взять некоторую библиотеку, быстро рещающую СЛАУ(параллельно или последовательно), и все остальные шаги алгоритма реализовать самому(ведь их не очень много). Имеется огромное количество библиотек на любых языках программирования, решающих СЛАУ. Одна из возможных реализаций алгоритма доступна [http://dumpz.org/13923/ здесь] | ||
== Литература == | == Литература == | ||
+ | |||
+ | |||
+ | :Тыртышников Е. Е. Методы численного анализа — М., Академия, 2007. - 320 c. | ||
+ | |||
+ | :Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с. | ||
+ | |||
+ | |||
+ | |||
+ | <references \> |
Версия 20:21, 13 октября 2016
Метод Ньютона | |
Последовательный алгоритм | |
Последовательная сложность | [math]O(n^3)[/math] в случае решения СЛАУ методом Гаусса |
Объём входных данных | [math]F(x)[/math] - [math]n[/math] [math]n[/math]-мерных функций (так же дополнительно могут быть даны производные) + [math]n[/math]-мерный вектор [math]x^0[/math] - начальное приближение |
Объём выходных данных | [math]n[/math]-мерный вектор |
Авторы: Гирняк О.Р., Васильков Д.А.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Метод Ньютона для решение систем нелинейных уравнений - обобщение классического метода Ньютона (метода касательных) нахождения корня (нуля) заданной функции. Однормерный метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации.
Впервые метод был опубликован в трактате «Алгебра» Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе «Общий анализ уравнений» (лат. «Analysis aequationum universalis»). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений [math]x_{n}[/math] вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.
1.2 Математическое описание алгоритма
Рассмотрим систему нелинейных уравнений[1]
[math]F(x) = 0, F(x), x \in \mathbb{R}^{n}, (1)[/math]
и предположим, что существует вектор [math]\bar{x} \in D \subset \mathbb{R}^{n}[/math], являющийся решением системы (1).
Будем считать, что [math]F(x) = (f_1(x), f_2(x), ... f_n(x))^T[/math], причем [math]f_i(\cdot) \in C^1(D) \forall i[/math]
Разложим [math]F(x)[/math] в окрестности точки [math]\bar{x}: F(x) = F(x^0) + F'(x^0)(x-x^0) + o(||x-x^0||)[/math].
Здесь [math] F'(x) = \frac{\partial{F(x)}}{\partial{x}} = \begin{pmatrix} \frac{\partial{f_1(x_1)}}{\partial{x_1}} & \frac{\partial{f_1(x_2)}}{\partial{x_2}} & \cdots & \frac{\partial{f_1(x_n)}}{\partial{x_n}}\\ \frac{\partial{f_2(x_1)}}{\partial{x_1}} & \frac{\partial{f_2(x_2)}}{\partial{x_2}} & \cdots & \frac{\partial{f_2(x_n)}}{\partial{x_n}}\\ \vdots & \vdots & \ddots & \vdots\\ \frac{\partial{f_n(x_1)}}{\partial{x_1}} & \frac{\partial{f_n(x_2)}}{\partial{x_2}} & \cdots & \frac{\partial{f_n(x_n)}}{\partial{x_n}} \end{pmatrix} [/math]
называется матрицей Якоби, а её определитель – якобианом системы (1).
Исходное уравнение заменим следующим: [math]F(x^0) + F'(x^0)(x-x^0) = 0[/math]. Считая матрицу Якоби [math]F'(x^0)[/math] неособой, разрешим это уравнение относительно [math]x: x = x^0 - [F'(x)]^{-1}F(x^0)[/math]. И вообще положим
[math]x^{k+1} = x^{k} - [F'(x^k)]^{-1}F(x^k)[/math].
При сделанных относительно [math]F(\cdot)[/math] предположениях имеет место сходимость последовательности [math]x^{k}[/math] к решению системы со скоростью геометрической прогрессии при условии, что начальное приближение [math]x^0[/math] выбрано из достаточно малой окрестности решения [math]\bar{x}[/math].
При дополнительном предположении [math]F(\cdot) \in C^2[/math] имеет место квадратичная сходимость метода, т.е.
[math]||x^{k+1}-\bar{x}|| \le \omega||x^{k}-\bar{x}||^2[/math].
Сформулируем теорему.
Теорема. Пусть в некоторой окрестности решения [math]\bar{x}[/math] системы (1) функции [math]f_i(\cdot) \in C^2[/math] и якобиан системы отличен от нуля в этой окрестности. Тогда существует [math]\delta[/math]-окрестность точки [math]\bar{x}[/math] такая, что при любом выборе начального приближения [math]x^0[/math] из этой окрестности последовательность [math]{x_k}[/math] не выходит из неё и имеет место квадратичная сходимость этой последовательности.
Замечание 1. В качестве критерия окончания процесса итераций обычно берут условие: [math]||x^{k+1}-x^k|| \lt \varepsilon[/math].
Замечание 2. Сложность метода Ньютона – в обращении матрицы Якоби. Вводя обозначение [math]\Delta x^k = x^{k+1}-x^k[/math], получаем для вычисления [math]\Delta x^k[/math] СЛАУ
[math]\frac{\partial F(x^k)}{\partial x} \cdot \Delta x^k = -F(x^k)[/math],
откуда и находим искомую поправку [math]\Delta x^k[/math], а затем и следующее приближение [math]x^{k+1} = x^k + \Delta x[/math] к решению [math]\bar{x}[/math]. Очевидно, что это значительно сокращает количество арифметических операций для построения очередного приближения.
Замечание 3. Начиная с некоторого шага [math]k_0[/math] решают стационарную СЛАУ
[math]\frac{\partial F(x^{k_0})}{\partial x} \cdot \Delta x^k = -F(x^k)[/math],
Данное видоизменение носит название модифицированный метод Ньютона.
Замечание 4. (О выборе начального приближения). Пусть вектор-функция [math]\Phi(\lambda, x)[/math] такова, что [math]\Phi(1, x) = F(x)[/math], а система [math]\Phi(0, x) = 0[/math] может быть решена. Тогда разбивая [math][0,1][/math] на [math]N[/math] частей решают методом Ньютона набор из [math]N[/math] систем [math]\Phi(i/N, x) = F(x), i = 1,... N[/math], принимая для каждой следующей системы в качестве начального приближения решение предыдущей системы.
1.3 Вычислительное ядро алгоритма
Вычислительными ядрами данного алгоритма являются:
- Численное вычисление Якобиана(в случае, если производные не даны) [math]\frac{\partial F(x^k)}{\partial x} [/math]
- Решение СЛАУ(например, методом Гаусса) [math]\frac{\partial F(x^k)}{\partial x} \cdot \Delta x^k = -F(x^k)[/math]
1.4 Макроструктура алгоритма
Как уже было описано в вычислительном ядре, данный метод сводится к решению СЛАУ.
1.5 Схема реализации последовательного алгоритма
Входные данные:[math]F(x)[/math] - [math]n[/math] [math]n[/math]-мерных функций; [math]n[/math]-мерный вектор [math]x^0[/math] - начальное приближение. [math]\varepsilon[/math] - точность
[math]x^k = x^0[/math]
DO
- Вычисляем [math]\frac{\partial F(x^k)}{\partial x} [/math] (если производные не даны, то их можно вычислить численно)
- Вычисляем [math]F(x^k)[/math]
- Решаем СЛАУ(например, методом Гаусса) [math]\frac{\partial F(x^k)}{\partial x} \cdot \Delta x^k = -F(x^k)[/math]
- [math]x^{k} = x^k + \Delta x^k[/math]
WHILE [math]||\Delta x^k|| \lt \varepsilon[/math]
Выходные данные: численное решение [math]x^k[/math]
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
Входные данные:[math]F(x)[/math] - [math]n[/math] [math]n[/math]-мерных функций; [math]n[/math]-мерный вектор [math]x^0[/math] - начальное приближение. [math]\varepsilon[/math] - точность
Выходные данные: численное решение [math]x^k[/math]
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Масштабируемость алгоритма и его реализации
2.2 Существующие реализации алгоритма
Как уже было сказано, основная часть данного алгоритма составляет решение СЛАУ. Поэтому, целесообразно не искать уже реализованный алгоритм, а взять некоторую библиотеку, быстро рещающую СЛАУ(параллельно или последовательно), и все остальные шаги алгоритма реализовать самому(ведь их не очень много). Имеется огромное количество библиотек на любых языках программирования, решающих СЛАУ. Одна из возможных реализаций алгоритма доступна здесь
3 Литература
- Тыртышников Е. Е. Методы численного анализа — М., Академия, 2007. - 320 c.
- Бахвалов Н. С., Жидков Н. П., Кобельков. Г. М. — 6-е изд. — М. : БИНОМ. Лаборатория знаний, 2008. — 636 с.
<references \>