Численное решение уравнений
Численное решение уравнений и их систем состоит в приближённом определении корней уравнения или системы уравнений и применяется в случаях, когда точный метод решения неизвестен или трудоёмок.
Постановка задачи
Рассмотрим методы численного решения уравнений и систем уравнений:
- [math]\displaystyle{ f(x_1, x_2, \ldots, x_n)=0 }[/math]
или
[math]\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. }[/math]
Численное решение задачи можно проводить как непосредственно (используя одноимённые методы), так и с применением оптимизационных методов, приведя задачу к соответствующему виду. Последним посвящена статья Градиентные методы.
Численные методы решения уравнений
Покажем, как можно решить изначальную систему уравнений, не прибегая к оптимизационным методам. В случае, если наша система представляет собой СЛАУ, целесообразно прибегнуть к таким методам, как метод Гаусса или метод Ричардсона. Однако мы всё же будем исходить из предположения, что вид функции нам неизвестен, и воспользуемся одним из итерационных методов численного решения. Среди большого разнообразия таковых выберем один из наиболее известных — метод Ньютона. Этот метод в свою очередь основывается на принципе сжимающего отображения. Поэтому сначала будет изложена суть последнего.
Сжимающее отображение
Определим терминологию:
Говорят, что функция [math]\displaystyle{ \varphi }[/math] осуществляет сжимающее отображение на [math]\displaystyle{ [a,\; b] }[/math], если
- [math]\displaystyle{ \forall x \in [ a, \; b ]: \varphi(x) \in [a,\; b ] }[/math]
- [math]\displaystyle{ \exist \alpha \lt 1: \forall x_1,x_2 \in [a,\; b ]\quad ||\varphi(x_1)-\varphi(x_2)||\leq \alpha ||x_1-x_2|| }[/math]
Тогда справедлива следующая основная теорема:
Теорема Банаха (принцип сжимающих отображений). Если [math]\displaystyle{ \varphi }[/math] — сжимающее отображение на [math]\displaystyle{ [a, \; b] }[/math], то:
|
Из последнего пункта теоремы вытекает, что скорость сходимости любого метода на основе сжимающих отображений не менее линейной.
Поясним смысл параметра [math]\displaystyle{ \alpha }[/math] для случая одной переменной. Согласно теореме Лагранжа имеем:
- [math]\displaystyle{ \varphi(x) \in C^1[a, \; b].\quad \forall x_1,x_2 \in (a, \; b),\quad x_1\lt 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]\displaystyle{ \alpha \approx |\varphi'(\xi)| }[/math]. Таким образом, для сходимости метода достаточно, чтобы [math]\displaystyle{ \forall x \in [a,\; b]\quad |\varphi'(x)|\leq 1. }[/math]
Общий алгоритм последовательных приближений
- Уравнение [math]\displaystyle{ f(x)=0 }[/math] преобразуется к уравнению с тем же корнем вида [math]\displaystyle{ x=\varphi(x) }[/math], где [math]\displaystyle{ \varphi(x) }[/math] — сжимающее отображение.
- Задаётся начальное приближение и точность [math]\displaystyle{ x_0, \quad \varepsilon, \quad i=0 }[/math]
- Вычисляется очередная итерация [math]\displaystyle{ x_{i+1}=\varphi(x_i) }[/math]
- Если [math]\displaystyle{ ||x_{i+1}-x_i||\gt \varepsilon }[/math], то [math]\displaystyle{ i=i+1 }[/math] и возврат к шагу 3.
- Иначе [math]\displaystyle{ x=x_{i+1} }[/math] и остановка.
Применительно к общему случаю операторных уравнений этот метод называется методом последовательных приближений или методом простой итерации. Однако уравнение [math]\displaystyle{ f(x)=0 }[/math] можно преобразовывать к сжимающему отображению [math]\displaystyle{ x=\varphi(x) }[/math], имеющему тот же корень, разными способами. Это порождает ряд частных методов, имеющих как линейную, так и более высокие скорости сходимости.
Применительно к СЛАУ
Рассмотрим систему:
[math]\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. }[/math]
Для неё итерационное вычисление будет выглядеть так:
[math]\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) }[/math]
Метод будет сходится с линейной скоростью, если [math]\displaystyle{ \left\|\begin{array}{ccc}a_{11}+1 & \ldots & a_{1n} \\ \vdots & \ddots & \vdots\\ a_{n1} & \ldots & a_{nn}+1 \end{array} \right\|\lt 1 }[/math]
Двойные вертикальные черты означают некоторую норму матрицы.
Метод Ньютона (метод касательных)
Одномерный случай
Оптимизация преобразования исходного уравнения [math]\displaystyle{ f(x)=0 }[/math] в сжимающее отображение [math]\displaystyle{ x=\varphi(x) }[/math] позволяет получить метод с квадратичной скоростью сходимости.
Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации [math]\displaystyle{ x^* }[/math] выполнялось [math]\displaystyle{ \varphi'(x^*)=0 }[/math]. Будем искать решение данного уравнения в виде [math]\displaystyle{ \varphi(x)=x+\alpha(x) f(x) }[/math], тогда:
- [math]\displaystyle{ \varphi'(x^*)=1+\alpha'(x^*) f(x^*) + \alpha(x^*) f'(x^*)=0 }[/math]
Воспользуемся тем, что [math]\displaystyle{ f(x)=0 }[/math], и получим окончательную формулу для [math]\displaystyle{ \alpha(x) }[/math]:
- [math]\displaystyle{ \alpha(x)=-\frac{1}{f'(x)} }[/math]
С учётом этого сжимающая функция примет вид:
- [math]\displaystyle{ \varphi(x)=x-\frac{f(x)}{f'(x)} }[/math]
Тогда алгоритм нахождения численного решения уравнения [math]\displaystyle{ f(x)=0 }[/math] сводится к итерационной процедуре вычисления:
- [math]\displaystyle{ x_{i+1}=x_{i}-\frac{f(x_i)}{f'(x_i)} }[/math]
Многомерный случай
Обобщим полученный результат на многомерный случай.
Выбирая некоторое начальное приближение [math]\displaystyle{ \vec{x}^{[0]} }[/math], находят последовательные приближения [math]\displaystyle{ \vec{x}^{[j+1]} }[/math] путём решения систем уравнений:
- [math]\displaystyle{ 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]\displaystyle{ x^{[j]}=\left( x_1^{[j]} \ldots x_k^{[j]} \ldots x_n^{[j]} \right), \quad j = 0, 1, 2, \ldots }[/math].
См. также
Литература
- Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
- Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
- Волков Е. А. Численные методы. — М.: Физматлит, 2003.
- Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
- Калиткин Н. Н. Численные методы. — М.: Наука, 1978.