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

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

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

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

$f(x_1,x_2,\dots <!--\; \dots \; -->,x_n)=0$$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.$ 

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

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

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

Сжимающее отображениеПравить

Определим терминологию:

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

1. $\mathrm{\forall <!--\; \forall \; -->}x\in <!--\; \in \; -->[a,b]:\mathrm{\phi <!--\; \phi \; -->}(x)\in <!--\; \in \; -->[a,b]$$\forall x\in [a,\;b]:\varphi (x)\in [a,\;b]$ 
2. $\exists \alpha <1:\forall x_{1},x_{2}\in [a,\;b]\quad ||\varphi (x_{1})-\varphi (x_{2})||\leq \alpha ||x_{1}-x_{2}||$ 

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

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

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

Поясним смысл параметра $\mathrm{\alpha <!--\; \alpha \; -->}$$\alpha$  для случая одной переменной. Согласно теореме Лагранжа имеем:

$\varphi (x)\in C^{1}[a,\;b].\quad \forall x_{1},x_{2}\in (a,\;b),\quad x_{1}<x_{2}\quad \exists \xi \in (x_{1},\;x_{2}):\quad \varphi '(\xi )(x_{2}-x_{1})=\varphi (x_{2})-\varphi (x_{1})$ 

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

Общий алгоритм последовательных приближенийПравить

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

Применительно к общему случаю операторных уравнений этот метод называется методом последовательных приближений или методом простой итерации. Однако уравнение $f(x)=0$$f(x)=0$  можно преобразовывать к сжимающему отображению $x=\mathrm{\phi <!--\; \phi \; -->}(x)$$x=\varphi(x)$ , имеющему тот же корень, разными способами. Это порождает ряд частных методов, имеющих как линейную, так и более высокие скорости сходимости.

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

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

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

 

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

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

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

Одномерный случайПравить

Оптимизация преобразования исходного уравнения $f(x)=0$$f(x)=0$  в сжимающее отображение $x=\mathrm{\phi <!--\; \phi \; -->}(x)$$x=\varphi(x)$  позволяет получить метод с квадратичной скоростью сходимости.

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

${\mathrm{\phi <!--\; \phi \; -->}}^{\prime }(x^{\ast <!--\; \ast \; -->})=1+{\mathrm{\alpha <!--\; \alpha \; -->}}^{\prime }(x^{\ast <!--\; \ast \; -->})f(x^{\ast <!--\; \ast \; -->})+\mathrm{\alpha <!--\; \alpha \; -->}(x^{\ast <!--\; \ast \; -->})f^{\prime }(x^{\ast <!--\; \ast \; -->})=0$$\varphi '(x^{*})=1+\alpha '(x^{*})f(x^{*})+\alpha (x^{*})f'(x^{*})=0$ 

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

$\mathrm{\alpha <!--\; \alpha \; -->}(x)=-<!--\; -\; -->\frac{1}{f^{\prime }(x)}$$\alpha (x)=-{\frac {1}{f'(x)}}$ 

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

$\mathrm{\phi <!--\; \phi \; -->}(x)=x-<!--\; -\; -->\frac{f(x)}{f^{\prime }(x)}$$\varphi (x)=x-{\frac {f(x)}{f'(x)}}$ 

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

$x_{i+1}=x_i-<!--\; -\; -->\frac{f(x_i)}{f^{\prime }(x_i)}$$x_{i+1}=x_{i}-{\frac {f(x_{i})}{f'(x_{i})}}$ 

Многомерный случайПравить

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

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

$f_i+\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{\mathrm{\partial <!--\; \partial \; -->}{f}_i}{\mathrm{\partial <!--\; \partial \; -->}{x}_k}(x_k^{[j+1]}-<!--\; -\; -->x_k^{[j]})=0,i=1,2,\dots <!--\; \dots \; -->,n$$f_{i}+\sum _{k=1}^{n}{\frac {\partial f_{i}}{\partial x_{k}}}(x_{k}^{[j+1]}-x_{k}^{[j]})=0,\quad i=1,2,\ldots ,n$ ,

где $x^{[j]}=\left(x_1^{[j]}\dots <!--\; \dots \; -->x_k^{[j]}\dots <!--\; \dots \; -->x_n^{[j]}\right),j=0,1,2,\dots <!--\; \dots \; -->$$x^{[j]}=\left(x_{1}^{[j]}\ldots x_{k}^{[j]}\ldots x_{n}^{[j]}\right),\quad j=0,1,2,\ldots$ .

См. такжеПравить

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

ЛитератураПравить

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

СсылкиПравить

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