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

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

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

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

$f(x_1,x_2,\dots ,x_n)=0$

или

$\{\begin{array}{ccc}{f}_1(x_1,x_2,\dots ,x_n)& =& 0\\ \dots & & \\ f_n(x_1,x_2,\dots ,x_n)& =& 0\end{array}$

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

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

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

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

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

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

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

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

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

$\phi (x)\in C^1[a,b].\mathrm{\forall }{x}_1,x_2\in (a,b),x_1<x_2\mathrm{\exists }\xi \in (x_1,x_2):{\phi }^{\prime }(\xi )(x_2-x_1)=\phi (x_2)-\phi (x_1)$

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

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

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

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

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

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

$\{\begin{array}{ccc}{a}_{11}{x}_1+\dots +a_{1n}{x}_n& =& b_1\\ \dots & & \\ a_{n1}{x}_1+\dots +a_{nn}{x}_n& =& b_n\end{array}$

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

${\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right)}^{i+1}=\left(\begin{array}{cccc}{a}_{11}+1& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}+1& \dots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \dots & a_{nn}+1\end{array}\right){\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right)}^i-\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right)$

Метод будет сходится с линейной скоростью, если $\Vert \begin{array}{ccc}{a}_{11}+1& \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{n1}& \dots & a_{nn}+1\end{array}\Vert <1$

Двойные вертикальные черты означают некоторую норму матрицы.

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

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

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

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

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

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

${\phi }^{\prime }(x^{*})=1+{\alpha }^{\prime }(x^{*})f(x^{*})+\alpha (x^{*})f^{\prime }(x^{*})=0$

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

$\alpha (x)=-\frac{1}{f^{\prime }(x)}$

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

$\phi (x)=x-\frac{f(x)}{f^{\prime }(x)}$

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

$x_{i+1}=x_i-\frac{f(x_i)}{f^{\prime }(x_i)}$

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

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

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

$f_i+\sum _{k=1}^n\frac{\partial f_i}{\partial x_k}(x_k^{[j+1]}-x_k^{[j]})=0,i=1,2,\dots ,n$,

где $x^{[j]}=(x_1^{[j]}\dots x_k^{[j]}\dots x_n^{[j]}),j=0,1,2,\dots$.

См. также

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

Литература

1. Шаблон:Книга
2. Шаблон:Книга
3. Шаблон:Книга
4. Шаблон:Книга
5. Шаблон:Книга

Ссылки

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