Просмотр кода страницы Численное решение уравнений

'''Численное решение уравнений''' и их систем состоит в приближённом определении корней уравнения или системы уравнений и применяется в случаях, когда точный метод решения неизвестен или трудоёмок.

== Постановка задачи ==
Рассмотрим методы численного решения уравнений и [[Система уравнений|систем уравнений]]:

: <math>f(x_1, x_2, \ldots, x_n)=0</math>

или

<math>\left\{ \begin{array}{lcr}
f_1(x_1, x_2, \ldots, x_n) & =& 0 \\
\ldots & & \\
f_n(x_1, x_2, \ldots, x_n) & =& 0
\end{array}\right.</math>

Численное решение задачи можно проводить как непосредственно (используя одноимённые [[численные методы|методы]]), так и с применением [[Математическое программирование|оптимизационных методов]], приведя задачу к соответствующему виду. Последним посвящена статья [[Градиентные методы]].

== Численные методы решения уравнений ==
Покажем, как можно решить изначальную [[Система уравнений|систему уравнений]], не прибегая к [[Математическое программирование|оптимизационным методам]]. В случае, если наша система представляет собой [[Система линейных алгебраических уравнений|СЛАУ]], целесообразно прибегнуть к таким методам, как [[метод Гаусса]] или [[метод Ричардсона]]. Однако мы всё же будем исходить из предположения, что вид функции нам неизвестен, и воспользуемся одним из итерационных [[Численные методы|методов численного решения]]. Среди большого разнообразия таковых выберем один из наиболее известных — [[метод Ньютона]]. Этот метод в свою очередь основывается на принципе сжимающего отображения. Поэтому сначала будет изложена суть последнего.

=== [[Сжимающее отображение]] ===
Определим терминологию:

Говорят, что функция <math>\varphi</math> осуществляет '''''сжимающее отображение''''' на <math>[a,\; b]</math>, если
# <math>\forall x \in [ a, \; b ]: \varphi(x) \in [a,\; b ]</math>
# <math>\exist \alpha < 1: \forall x_1,x_2 \in [a,\; b ]\quad ||\varphi(x_1)-\varphi(x_2)||\leq \alpha ||x_1-x_2||</math>

Тогда справедлива следующая основная теорема:

{{message box |backgroundcolor = white |image =Logo_arte.jpg |size = 50px| heading=[[Теорема Банаха]] (принцип сжимающих отображений).|message= Если <math>\varphi</math> — сжимающее отображение на <math>[a, \; b]</math>, то:
# Уравнение <math>x=\varphi(x)</math> имеет единственный корень <math> x^*</math> в <math>[a, \; b]</math>;
# Итерационная последовательность <math>x_{i+1}=\varphi(x_i)</math> сходится к этому корню;
# Для очередного члена <math>x_n</math> справедливо <math>||x_n-x^*||\leq\frac{\alpha^n ||x_1-x_0||}{1-\alpha}</math>.}}

Из последнего пункта теоремы вытекает, что [[скорость сходимости]] любого метода на основе сжимающих отображений не менее линейной.

Поясним смысл параметра <math>\alpha</math> для случая одной переменной. Согласно [[Формула конечных приращений|теореме Лагранжа]] имеем:

: <math>\varphi(x) \in C^1[a, \; b].\quad \forall x_1,x_2 \in (a, \; b),\quad x_1<x_2 \quad \exist \xi \in (x_1,\; x_2): \quad \varphi'(\xi)(x_2-x_1) = \varphi(x_2)-\varphi(x_1)</math>

Отсюда следует, что <math>\alpha \approx |\varphi'(\xi)|</math>. Таким образом, для [[Предел последовательности|сходимости]] метода достаточно, чтобы <math>\forall x \in [a,\; b]\quad |\varphi'(x)|\leq 1.</math>

==== Общий алгоритм последовательных приближений ====
# Уравнение <math>f(x)=0</math> преобразуется к уравнению с тем же корнем вида <math>x=\varphi(x)</math>, где <math>\varphi(x)</math> — сжимающее отображение.
# Задаётся начальное приближение и точность <math>x_0, \quad \varepsilon, \quad i=0</math>
# Вычисляется очередная итерация <math>x_{i+1}=\varphi(x_i)</math>
#* Если <math>||x_{i+1}-x_i||>\varepsilon</math>, то <math>i=i+1</math> и возврат к шагу 3.
#* Иначе <math>x=x_{i+1}</math> и остановка.

Применительно к общему случаю операторных уравнений этот метод называется '''''методом последовательных приближений''''', или '''''методом простой итерации'''''. Однако уравнение <math>f(x)=0</math> можно преобразовывать к сжимающему отображению <math>x=\varphi(x)</math>, имеющему тот же корень, разными способами. Это порождает ряд частных методов, имеющих как линейную, так и более высокие скорости сходимости.

==== Применительно к СЛАУ ====
Рассмотрим систему:

<math>\left\{ \begin{array}{ccc}
a_{11} x_1 + \ldots + a_{1n} x_n & = & b_1 \\
\ldots & & \\
a_{n1} x_1 + \ldots + a_{nn} x_n & = & b_n
\end{array}\right.</math>

Для неё итерационное вычисление будет выглядеть так:

<math>\left( \begin{array}{c}
x_1\\
x_2\\
\vdots\\
x_n \end{array}\right)^{i+1} = \left( \begin{array}{cccc}
a_{11}+1 & a_{12} & \ldots & a_{1n} \\
a_{21} & a_{22}+1 & \ldots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \ldots & a_{nn}+1
\end{array}\right) \left(\begin{array}{c}
x_1\\
x_2\\
\vdots\\
x_n
\end{array}\right)^{i}-\left(\begin{array}{c}
b_1\\
b_2\\
\vdots\\
b_n
\end{array}\right)
</math>

Метод будет сходится с линейной скоростью, если <math>\left\|\begin{array}{ccc}a_{11}+1 & \ldots & a_{1n} \\ \vdots & \ddots & \vdots\\ a_{n1} & \ldots & a_{nn}+1 \end{array} \right\|<1</math>

Двойные вертикальные черты означают некоторую [[Норма (математика)#Норма матрицы|норму матрицы]].

[[Файл:Cosine fixed point.svg|thumb|right|Решение уравнения cos(x)=x по методу простой итерации, очередная итерация: x<sub>n+1</sub>=cos x<sub>n</sub>, начальное приближение: x<sub>1</sub> = −1]]

[[Файл:Metoda Newtona-4 kroki.png|thumb|right|300px|Решение уравнения f(x)=0 по методу Ньютона, начальное приближение: x<sub>1</sub>=a.]]

=== Метод [[Ньютон, Исаак|Ньютона]] (метод касательных) ===
{{main|Метод Ньютона}}

==== Одномерный случай ====
Оптимизация преобразования исходного уравнения <math>f(x)=0</math> в сжимающее отображение <math>x=\varphi(x)</math> позволяет получить метод с квадратичной скоростью сходимости.

Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации <math>x^*</math> выполнялось <math>\varphi'(x^*)=0</math>. Будем искать решение данного уравнения в виде <math>\varphi(x)=x+\alpha(x) f(x)</math>, тогда:

: <math>\varphi'(x^*)=1+\alpha'(x^*) f(x^*) + \alpha(x^*) f'(x^*)=0</math>

Воспользуемся тем, что <math>f(x)=0</math>, и получим окончательную формулу для <math>\alpha(x)</math>:

: <math>\alpha(x)=-\frac{1}{f'(x)}</math>

С учётом этого сжимающая функция примет вид:

: <math>\varphi(x)=x-\frac{f(x)}{f'(x)}</math>

Тогда алгоритм нахождения численного решения уравнения <math>f(x)=0</math> сводится к итерационной процедуре вычисления:

: <math>x_{i+1}=x_{i}-\frac{f(x_i)}{f'(x_i)}</math>

==== Многомерный случай ====
Обобщим полученный результат на многомерный случай.

Выбирая некоторое начальное приближение <math display="inline">\vec{x}^{[0]}</math>, находят последовательные приближения <math>\vec{x}^{[j+1]}</math> путём решения систем уравнений:

: <math>f_i + \sum_{k=1}^n\frac{\partial f_i}{\partial x_k}(x^{[j+1]}_k - x_k^{[j]})=0,\quad i = 1, 2, \ldots, n</math>,

где <math>x^{[j]}=\left( x_1^{[j]} \ldots x_k^{[j]} \ldots x_n^{[j]} \right), \quad j = 0, 1, 2, \ldots</math>.

== См. также ==
{{кол|3}}
* [[Метод Крамера]]
* [[QR-разложение|Метод QR-разложения]]
* [[Сингулярное разложение|Метод сингулярного разложения]]
* [[Метод Зейделя]]
* [[Градиентные методы]]
* [[Метод секущих]]
* [[Метод Мюллера]]
* [[Обратная параболическая интерполяция]]
* [[Метод итерации]]
{{кол|конец}}

== Литература ==
# {{книга
|автор = Амосов А. А.,  Дубинский Ю. А., Копченова Н. П.
|заглавие = Вычислительные методы для инженеров
|оригинал = 
|ссылка = 
|издание = 
|место =  М.
|издательство = Мир
|год = 1998
|страницы =
|isbn = 
}}
# {{книга
|автор = Бахвалов Н. С., [[Жидков, Николай Петрович|Жидков Н. П.]], Кобельков Г. Г.
|заглавие = Численные методы
|оригинал = 
|ссылка = 
|издание = 8-е изд
|место =  М.
|издательство = Лаборатория Базовых Знаний
|год = 2000
|страницы =
|isbn = 
}}
# {{книга
|автор = Волков Е. А.
|заглавие = Численные методы
|оригинал = 
|ссылка = 
|издание =
|место =  М.
|издательство = Физматлит
|год = 2003
|страницы =
|isbn = 
}}
# {{книга
|автор = Коршунов Ю. М., Коршунов Ю. М.
|заглавие = Математические основы кибернетики
|оригинал = 
|ссылка = 
|издание =
|место =  М.
|издательство = Энергоатомиздат
|год = 1972
|страницы =
|isbn = 
}}
# {{книга
|автор = Калиткин Н. Н.
|заглавие = Численные методы
|оригинал = 
|ссылка = 
|издание =
|место =  М.
|издательство = Наука
|год = 1978
|страницы =
|isbn = 
}}

== Ссылки ==
* [https://web.archive.org/web/20130612141722/http://millerbird.site11.com/Math/hord.php Численное решение уравнений онлайн]

[[Категория:Численные методы решения уравнений| ]]
[[Категория:Численные методы|Решение уравнений]]