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