Численное решение уравнений

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

Постановка задачи

Рассмотрим методы численного решения уравнений и систем уравнений:

$f(x_1, x_2, \ldots, x_n)=0\!$

или

$\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.$

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

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

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

Метод простой итерации

В основе метода заложено понятие сжимающего отображения. Определим терминологию:

Говорят, что функция $\varphi\!$ осуществляет сжимающее отображение на $[a,\; b]\!$, если

1. $\forall x \in [ a, \; b ]: \varphi(x) \in [a,\; b ]\!$
2. $\exist \alpha < 1: \forall x_1,x_2 \in [a,\; b ]\quad ||\varphi(x_1)-\varphi(x_2)||\leq \alpha ||x_1-x_2||\!$

Тогда основная теорема будет выглядеть так:

Теорема Банаха (принцип сжимающих отображений). Если $\varphi\!$ — сжимающее отображение на $[a, \; b]\!$, то: $x=\varphi(x)\quad \exist ! x^*\in[a, \; b]\!$ — корень; итерационная последовательность $x_{i+1}=\varphi(x_i)\!$ сходится к этому корню; для очередного члена $x_n\!$ справедливо $||x_n-x^*||\leq\frac{\alpha^n ||x_1-x_0||}{1-\alpha}\!$.

Поясним смысл параметра $\alpha\!$. Согласно теореме Лагранжа имеем:

$\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)\!$

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

1. $x_3=\varphi(x_2)\!$

.........

и так далее, пока $||x_{i+1}-x_i||>\varepsilon\!$

Применительно к СЛАУ

Рассмотрим систему:

$\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.$

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

$\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)$

Сходимость метода будет осуществлять $\left\|\begin{array}{ccc}a_{11}+1 & \ldots & a_{1n} \\ \vdots & \ddots & \vdots\\ a_{n1} & \ldots & a_{nn}+1 \end{array} \right\|<1$

Следует отметить, что для оценки сходимости вычисляется не определитель матрицы, а норма матрицы. Поэтому в данном случае поставлены двойные вертикальные черты, а не одинарные.

Решение уравнения cos(x)=x по методу простой итерации, очередная итерация: x_n+1=cos x_n, начальное приближение: x₁ = -1

Алгоритм

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

Решение уравнения f(x)=0 по методу Ньютона, начальное приближение: x₁=a.

Метод Ньютона (метод касательных)

Основная статья: Метод Ньютона

Одномерный случай

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

$\varphi'(x^*)=1+\alpha'(x^*) f(x^*) + \alpha(x^*) f'(x^*)=0\!$

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

$\alpha(x)=-\frac{1}{f'(x)}\!$

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

$\varphi(x)=x-\frac{f(x)}{f'(x)}\!$

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

$x_{i+1}=x_{i}-\frac{f(x_i)}{f'(x_i)}\!$

Многомерный случай

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

Выбирая некоторое начальное приближение $\vec{x}^{[0]}\!$, находят последовательные приближения $\vec{x}^{[j+1]}\!$ путем решения систем уравнений:

$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\!$,

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

Литература

1. Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
2. Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
3. Волков Е. А. Численные методы. — М.: Физматлит, 2003.
4. Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
5. Калиткин Н. Н. Численные методы. — М.: Наука, 1978.

См. также

• Метод Крамера
• Система уравнений и экстремальные задачи
  • Метод QR-разложения
  • Метод сингулярного разложения
  • Метод Зейделя
• Градиентные методы
  • Метод секущих
  • Комбинированный метод
  • Метод итераций