Меню Главная Случайная статья Настройки Численное решение уравнений Материал из https://ru.wikipedia.org Численное решение уравнений и их систем состоит в приближённом определении корней уравнения или системы уравнений и применяется в случаях, когда точный метод решения неизвестен или трудоёмок. Содержание 1 Постановка задачи 2 Численные методы решения уравнений 2.1 Сжимающее отображение 2.1.1 Общий алгоритм последовательных приближений 2.1.2 Применительно к СЛАУ 2.2 Метод Ньютона (метод касательных) 2.2.1 Одномерный случай 2.2.2 Многомерный случай 3 См. также 4 Литература 5 Ссылки Постановка задачи Рассмотрим методы численного решения уравнений и систем уравнений: ${\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]}$, если Тогда справедлива следующая основная теорема: Теорема Банаха (принцип сжимающих отображений). Если ${\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.}$ Уравнение ${\displaystyle f(x)=0}$ преобразуется к уравнению с тем же корнем вида ${\displaystyle x=\varphi (x)}$, где ${\displaystyle \varphi (x)}$ — сжимающее отображение. Задаётся начальное приближение и точность ${\displaystyle x_{0},\quad \varepsilon ,\quad i=0}$ Вычисляется очередная итерация ${\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 }$. См. также Метод Крамера Метод QR-разложения Метод сингулярного разложения Метод Зейделя Градиентные методы Метод секущих Метод Мюллера Обратная параболическая интерполяция Метод итерации Литература Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998. Ссылки Численное решение уравнений онлайн