Участник:Арутюнов А.В.: различия между версиями
(Новая страница: « {{algorithm | name = Решение системы нелинейных уравнений методом Ньютона | serial_complexity = <math…») |
|||
| Строка 15: | Строка 15: | ||
= Свойства и структура алгоритма = | = Свойства и структура алгоритма = | ||
== Общее описание алгоритма == | == Общее описание алгоритма == | ||
| − | + | Это итерационный численный метод нахождения корня (нуля) заданной функции | |
Классический метод Ньютона или касательных заключается в том, что если <math>x_n</math> — некоторое приближение к корню <math>x_*</math> уравнения f(x) = 0, f(x) ghby <math>C^1</math> , то следующее приближение определяется как корень касательной f(x) к функции , проведенной в точке <math>x_n</math> . | Классический метод Ньютона или касательных заключается в том, что если <math>x_n</math> — некоторое приближение к корню <math>x_*</math> уравнения f(x) = 0, f(x) ghby <math>C^1</math> , то следующее приближение определяется как корень касательной f(x) к функции , проведенной в точке <math>x_n</math> . | ||
| − | + | Уравнение касательной к функции f(x) в точке имеет вид: | |
<math>f^(x_j)=y-f(x_n)/(x-x_n)</math> | <math>f^(x_j)=y-f(x_n)/(x-x_n)</math> | ||
| Строка 26: | Строка 26: | ||
Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем: | Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем: | ||
| + | |||
| + | Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. | ||
| + | |||
| + | === Математическое описание алгоритма === | ||
| + | |||
| + | Пусть необходимо найти решение системы: <br /> <br /> | ||
| + | <math> | ||
| + | \left\{\begin{matrix}f_1(x_1, ..., x_n) = 0 | ||
| + | \\ ... | ||
| + | \\ f_n(x_1, ..., x_n) = 0, | ||
| + | |||
| + | \end{matrix}\right. | ||
| + | </math> | ||
| + | <br /> <br /> | ||
| + | где <math>f = (f_1, ..., f_n) : \mathbb{R}^n \rightarrow \mathbb{R}^n</math> - непрерывно дифференцируемое отображение в окрестности решения. | ||
| + | <br /> <br /> | ||
| + | |||
| + | При начальном приближении <math>x_0</math> и сделанных предположениях <math>(k+1)</math>-я итерация метода будет выглядеть следующим образом: | ||
| + | <math> | ||
| + | x_{k+1} = x_k - [f'(x_k)]^{-1}f(x_k)Δ | ||
| + | </math> | ||
| + | |||
| + | === Математическое описание алгоритма === | ||
| + | |||
| + | Идея метода заключается в линеаризации уравнений системы | ||
| + | <br /> <br /> | ||
| + | <math> | ||
| + | \left\{\begin{matrix}f_1(x_1, ..., x_n) = 0 | ||
| + | \\ }f_2(x_1,...x_n)=0 , ‚ что позволяет свести исходную задачу решения СНУ к | ||
| + | \\ ... | ||
| + | \\ f_n(x_1, ..., x_n) = 0, | ||
| + | \end{matrix}\right. | ||
| + | </math> | ||
| + | многократному решению системы линейных уравнений. | ||
| + | Пусть известно приближение (x_i)^(k) решения системы нелинейных уравнений xi .Введем в рассмотрение поправку ΔхΔ как разницу между решением и его приближением: | ||
| + | Δх_i=(х_i)^* — (х_i)^(k) => (х_i)^*=(х_i)^(k) + Δx_I, i=1,n | ||
| + | Подставим полученное выражение для (х_i)^* в исходную систему. | ||
| + | Е1(х‘ +Δх х +Δх2‚ | ||
| + | <br /> <br /> | ||
| + | <math> | ||
| + | \left\{\begin{matrix}f_1((x_1)^(k) +Δx_1, (x_2)^(k)+Ax_2, ..., (x_n)^(k) + Δx_n)=0, | ||
| + | \\ f_2((x_1)^(k) +Δx_1, (x_2)^(k)+Δx_2, ..., (x_n)^(k) + Δx_n)=0, | ||
| + | \\ ... | ||
| + | \\ f_n((x_1)^(k) +Δx_1, (x_2)^(k)+Δx_2, ..., (x_n)^(k) + Δx_n)=0, | ||
| + | \end{matrix}\right. | ||
| + | </math> | ||
| + | Неизвестными в этой системе нашейных уравнений являются поправки Δх_i. Для определения Δх_i нужно решить эту систему. Но решить эту адачу так же сложно, как и исходную. Однако эту систему можно ленеаризовать, и, решив её, получить приближённые значения поправок Δx_i для нашего приближения, т.е. Ax_i. Эти поправки получают сразу получить точное решение (x_i)^*, но дают возможность приблизиться к решению, - получить новое приближение решения | ||
| + | <math> ((x_i)^(k+1) = ((x_i)^(k) +(Δx_i)^(k), i=1.n </math> | ||
| + | Для линеаризации системы следует разложить функцию f_i в ряды Тейлора в окрестности (х_i)^(k), ограничиваясь первыми дифференциалами. Полученная система имеет вид: | ||
| + | |||
| + | Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения х. Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n - метод исключения Гаусса. Значения поправок используются для оценки достигнутой точности решения. Если максимальная по абсолютной величине поправка меньше заданной точности н, расчет завершается. Таким образом, условие окончания расчета: | ||
| Строка 33: | Строка 84: | ||
== Макроструктура алгоритма == | == Макроструктура алгоритма == | ||
| + | Данный алгоритм использует два основных метода решения в каждой итерации, это нахождением матрицы Якоби и решение СЛАУ. | ||
Версия 21:37, 18 января 2017
| Решение системы нелинейных уравнений методом Ньютона | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(n^2 [/math] - одна итерация |
| Объём входных данных | [math]n * m + 1[/math] |
| Объём выходных данных | [math]n[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math][/math] |
| Ширина ярусно-параллельной формы | [math][/math] |
Автор описания: Арутюнов А.В.
Решение системы нелинейных уравнений методом Ньютона
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Это итерационный численный метод нахождения корня (нуля) заданной функции
Классический метод Ньютона или касательных заключается в том, что если [math]x_n[/math] — некоторое приближение к корню [math]x_*[/math] уравнения f(x) = 0, f(x) ghby [math]C^1[/math] , то следующее приближение определяется как корень касательной f(x) к функции , проведенной в точке [math]x_n[/math] .
Уравнение касательной к функции f(x) в точке имеет вид:
[math]f^(x_j)=y-f(x_n)/(x-x_n)[/math]
В уравнении касательной положим y=0 и [math]x=x_n+1[/math].
Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:
Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных.
1.1.1 Математическое описание алгоритма
Пусть необходимо найти решение системы:
[math]
\left\{\begin{matrix}f_1(x_1, ..., x_n) = 0
\\ ...
\\ f_n(x_1, ..., x_n) = 0,
\end{matrix}\right.
[/math]
где [math]f = (f_1, ..., f_n) : \mathbb{R}^n \rightarrow \mathbb{R}^n[/math] - непрерывно дифференцируемое отображение в окрестности решения.
При начальном приближении [math]x_0[/math] и сделанных предположениях [math](k+1)[/math]-я итерация метода будет выглядеть следующим образом: [math] x_{k+1} = x_k - [f'(x_k)]^{-1}f(x_k)Δ [/math]
1.1.2 Математическое описание алгоритма
Идея метода заключается в линеаризации уравнений системы
[math]
\left\{\begin{matrix}f_1(x_1, ..., x_n) = 0
\\ }f_2(x_1,...x_n)=0 , ‚ что позволяет свести исходную задачу решения СНУ к
\\ ...
\\ f_n(x_1, ..., x_n) = 0,
\end{matrix}\right.
[/math]
многократному решению системы линейных уравнений.
Пусть известно приближение (x_i)^(k) решения системы нелинейных уравнений xi .Введем в рассмотрение поправку ΔхΔ как разницу между решением и его приближением:
Δх_i=(х_i)^* — (х_i)^(k) => (х_i)^*=(х_i)^(k) + Δx_I, i=1,n
Подставим полученное выражение для (х_i)^* в исходную систему.
Е1(х‘ +Δх х +Δх2‚
[math]
\left\{\begin{matrix}f_1((x_1)^(k) +Δx_1, (x_2)^(k)+Ax_2, ..., (x_n)^(k) + Δx_n)=0,
\\ f_2((x_1)^(k) +Δx_1, (x_2)^(k)+Δx_2, ..., (x_n)^(k) + Δx_n)=0,
\\ ...
\\ f_n((x_1)^(k) +Δx_1, (x_2)^(k)+Δx_2, ..., (x_n)^(k) + Δx_n)=0,
\end{matrix}\right.
[/math]
Неизвестными в этой системе нашейных уравнений являются поправки Δх_i. Для определения Δх_i нужно решить эту систему. Но решить эту адачу так же сложно, как и исходную. Однако эту систему можно ленеаризовать, и, решив её, получить приближённые значения поправок Δx_i для нашего приближения, т.е. Ax_i. Эти поправки получают сразу получить точное решение (x_i)^*, но дают возможность приблизиться к решению, - получить новое приближение решения
[math] ((x_i)^(k+1) = ((x_i)^(k) +(Δx_i)^(k), i=1.n [/math]
Для линеаризации системы следует разложить функцию f_i в ряды Тейлора в окрестности (х_i)^(k), ограничиваясь первыми дифференциалами. Полученная система имеет вид:
Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения х. Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n - метод исключения Гаусса. Значения поправок используются для оценки достигнутой точности решения. Если максимальная по абсолютной величине поправка меньше заданной точности н, расчет завершается. Таким образом, условие окончания расчета:
1.2 Вычислительное ядро алгоритма
1.3 Макроструктура алгоритма
Данный алгоритм использует два основных метода решения в каждой итерации, это нахождением матрицы Якоби и решение СЛАУ.
