Уровень алгоритма

Участник:Арутюнов А.В.: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 50: Строка 50:
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
  
Идея метода заключается в линеаризации уравнений системы
+
<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_n(x_1, ..., x_n) = 0,
 +
\end{matrix}\right.
 +
</math>
 
<br /> <br />
 
<br /> <br />
 +
 +
Идея метода заключается в линеаризации уравнений системы <br /> <br />
 
<math>
 
<math>
 
\left\{\begin{matrix}f_1(x_1, ..., x_n) = 0
 
\left\{\begin{matrix}f_1(x_1, ..., x_n) = 0
\\ }f_2(x_1,...x_n)=0 , ‚ что позволяет свести исходную задачу решения СНУ к
+
\\ f_2(x_1,...x_n)=0,
 
\\ ...
 
\\ ...
 
\\ f_n(x_1, ..., x_n) = 0,
 
\\ f_n(x_1, ..., x_n) = 0,
 
\end{matrix}\right.
 
\end{matrix}\right.
 
</math>
 
</math>
 +
<br /> <br />
 +
 +
 
многократному решению системы линейных уравнений.
 
многократному решению системы линейных уравнений.
 
Пусть известно приближение (x_i)^(k)  решения системы нелинейных уравнений xi .Введем в рассмотрение поправку ΔхΔ как разницу между решением и его приближением:
 
Пусть известно приближение (x_i)^(k)  решения системы нелинейных уравнений xi .Введем в рассмотрение поправку ΔхΔ как разницу между решением и его приближением:
Δх_i=(х_i)^* — (х_i)^(k) => (х_i)^*=(х_i)^(k) + Δx_I, i=1,n
+
Δх_i=(х_i)^* — (х_i)^k => (х_i)^*=(х_i)^k  + Δx_I, i=1,n
 
Подставим полученное выражение для (х_i)^* в исходную систему.
 
Подставим полученное выражение для (х_i)^* в исходную систему.
Е1(х‘ +Δх х +Δх2‚
+
+Δх х +Δх2‚
 
<br /> <br />
 
<br /> <br />
 
<math>
 
<math>
\left\{\begin{matrix}f_1((x_1)^(k) +Δx_1, (x_2)^(k)+Ax_2,  ..., (x_n)^(k) + Δx_n)=0,
+
\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_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,
+
\\ f_n((x_1)^(k) +Δx_1, (x_2)^(k)+Δx_2,  ..., (x_n)^k + Δx_n)=0,
 
\end{matrix}\right.
 
\end{matrix}\right.
 
</math>
 
</math>
Неизвестными в этой системе нашейных уравнений являются поправки Δх_i. Для определения Δх_i нужно решить эту систему. Но решить эту адачу так же сложно, как и исходную. Однако эту систему можно ленеаризовать, и, решив её,  получить приближённые значения поправок Δx_i для нашего приближения, т.е. Ax_i. Эти поправки получают сразу получить точное решение  (x_i)^*, но дают возможность приблизиться к решению, - получить новое приближение решения  
+
Неизвестными в этой системе нашейных уравнений являются поправки <math>Δх_i</math>. Для определения Δх_i нужно решить эту систему. Но решить эту адачу так же сложно, как и исходную. Однако эту систему можно ленеаризовать, и, решив её,  получить приближённые значения поправок Δx_i для нашего приближения, т.е. Δx_i. Эти поправки получают сразу получить точное решение  (x_i)^*, но дают возможность приблизиться к решению, - получить новое приближение решения  
<math> ((x_i)^(k+1) = ((x_i)^(k) +(Δx_i)^(k), i=1.n  </math>  
+
<math> ((x_i)^{k+1} = ((x_i)^k +(Δx_i)^k, i=1.n  </math>  
Для линеаризации системы следует разложить функцию f_i в ряды Тейлора в окрестности (х_i)^(k), ограничиваясь первыми дифференциалами. Полученная система имеет вид:  
+
Для линеаризации системы следует разложить функцию f_i в ряды Тейлора в окрестности (х_i)^k, ограничиваясь первыми дифференциалами. Полученная система имеет вид:  
 
   
 
   
Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения х. Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n - метод исключения Гаусса. Значения поправок используются для оценки достигнутой точности решения. Если максимальная по абсолютной величине поправка меньше заданной точности н, расчет завершается. Таким образом, условие окончания расчета:  
+
Все коэффициенты этого уравнения можно вычислить, используя последнее приближение решения х. Для решения системы линейных уравнений при n=2,3 можно использовать формулы Крамера, при большей размерности системы n - метод исключения Гаусса. Значения поправок используются для оценки достигнутой точности решения. Если максимальная по абсолютной величине поправка меньше заданной точности н, расчет завершается. Таким образом, условие окончания расчета:
 
 
 
 
  
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==

Версия 23:34, 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] x_{k+1} = x_k - [f'(x_k)]^{-1}f(x_k) [/math]

Пусть необходимо найти решение системы:

[math] \left\{\begin{matrix}f_1(x_1, ..., x_n) = 0 \\ ... \\ f_n(x_1, ..., x_n) = 0, \end{matrix}\right. [/math]

Идея метода заключается в линеаризации уравнений системы

[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)^* в исходную систему.

+Δх х +Δх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] Неизвестными в этой системе нашейных уравнений являются поправки [math]Δх_i[/math]. Для определения Δх_i нужно решить эту систему. Но решить эту адачу так же сложно, как и исходную. Однако эту систему можно ленеаризовать, и, решив её, получить приближённые значения поправок Δx_i для нашего приближения, т.е. Δx_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 Макроструктура алгоритма

Данный алгоритм использует два основных метода решения в каждой итерации, это нахождением матрицы Якоби и решение СЛАУ.