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

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

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

${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=0}$

или

${\displaystyle \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.}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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})}$

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

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

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

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

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

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

${\displaystyle \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.}$

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

${\displaystyle \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)}$

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

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

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

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

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

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

${\displaystyle \varphi '(x^{*})=1+\alpha '(x^{*})f(x^{*})+\alpha (x^{*})f'(x^{*})=0}$

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

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

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

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

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

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

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

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

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

${\displaystyle 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}$ ,

где ${\displaystyle 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.

Ссылки