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

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

Нахождение корней уравнений — одна из наиболее часто встречающихся задач. Вместе с тем не всегда есть возможность найти аналитическое решение уравнения. В первую очередь это относится к большинству трансцендентных уравнений, т.е. уравнений, в которых неизвестная х находится под знаком трансцендентной функции, например, x 2 — sin 5x = 0.

Доказано также, что не имеют аналитического решения алгебраические уравнения степени выше четвертой:

Для поиска корней таких уравнений используются численные (приближенные) методы, которые по своей сути являются способами уточнения корней 3.

В общем случае запись нелинейного уравнения имеет вида

Задача решения нелинейного уравнения состоит из двух этапов:

1) локализация корней, т.е. определение интервала изоляции (интервала неопределенности), в котором расположен корень;

2) определение с заданной точностью точности ε приближенного значения корня.

Для локализации корней можно воспользоваться следующей теоремой.

Теорема: Если непрерывная функция y=f(x) на концах отрезка [a, b] принимает значения разных знаков, т.е. f(a)·f(b)

и вычисляется значение функции f(d).

Далее делается выбор, какую из двух частей отрезка взять для дальнейшего уточнения корня. Для чего проверяется условие

Блок-схема метода половинного деления представлена на рисунке 12.

Рисунок 12 — Блок-схема алгоритма поиска корней уравнения методом половинного деления

Метод хорд

Идея метода хорд заключается в том, что кривая y=f(x) на участке [a, b] заменяется хордой и в качестве приближенного значения корня х * =x_n принимается точка пересечения оси абсцисс с хордой (рисунок 13).

Рисунок 13 – Графическая интерпретация метода хорд

Запишем уравнение хорды, проходящей через точки С с координатами (a, f(a)) и D – (b, f(b)):

Абсцисса точки пересечения хорды с осью ОХ находится из этого выражения при y=0, т.е.

Выполнив преобразования, получаем выражение для нахождения приближенного корня:

. (35)

Полученное значение x_n можно снова использовать для дальнейшего уточнения корня, рассматривая интервал [a, x_n] или [x_n , b] в зависимости от знака функции в точке x_n — f(x_n).

Если значения функции при х=а и х=x_n имеют разные знаки, т.е. выполняется условие

Вычисления повторяются до тех пор, пока выполняется условие

Блок-схема, реализующая метод хорд, приведена на рисунке 14.

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

Этот метод основан на замене функции y=f(x) в точке начального приближения x=x₀ касательной, пересечение которой с осью х дает первое приближение корня х₁ и т.д. (рисунок 15).

В качестве x₀ выбирают тот конец отрезка [a, b] (т.е. точку С или точку D), для которого выполняется условие:

Рисунок 14 — Блок-схема алгоритма поиска корней уравнения методом хорд

Рисунок 15 – Графическая интерпретация метода Ньютона

Для графической иллюстрации (рисунок 15), где начальное приближение находится в точке D, т.е. x₀=b, запишем:

откуда или .

Тогда, в общем виде выражение для нахождения корня можно записать:

Итерационный процесс уточнения корня выполняется до тех пор, пока соблюдается условие

Метод Ньютона обладает высокой скоростью сходимости. Обычно абсолютная точность решения 10 -5 — 10 -6 достигается через 5-6 итераций.

Блок-схема, реализующая метод Ньютона, приведена на рисунке 16.

Рисунок 16 — Блок-схема алгоритма поиска корня уравнения методом Ньютона

Комбинированные методы

Комбинированные методы решения уравнения основаны на сочетании описанных выше методов и позволяют получить приближение к корню с противоположных сторон с сужением интервала локализации корня.

Оба метода используются последовательно, при этом интервал локализации сравнивается с заданной точностью e. Корень уравнения находится как среднее двух значений, полученных каждым из методов.

На рисунке 17 приведена блок-схема комбинированного метода хорд-Ньютона.

Рисунок 17 — Блок-схема комбинированного метода хорд-Ньютона

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

Введение

Многие прикладные задачи приводят к необходимости нахождения общего решения системы нелинейных уравнений. Общего аналитического решения системы нелинейных уравнений не найдено. Существуют лишь численные методы.

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

Для численного решения применяются итерационные методы последовательных приближений (простой итерации) и метод Ньютона в различных модификациях. Итерационные процессы естественным образом обобщаются на случай системы нелинейных уравнений вида:

(1)

Обозначим через вектор неизвестных и определим вектор-функцию Тогда система (1) записывается в виде уравнения:

(2)

Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].

Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами.

С этим трудно не согласится хотя бы потому, что в том числе и разнообразие модулей подняло Python на вершину популярности. Однако, существуют случаи, когда даже при поверхностном рассмотрении использование прямых известных методов без применения специальных функций библиотеки SciPy тоже дают неплохие результаты. Иными словами, новое- это хорошо забытое старое.

Так, в публикации [2], на основании проведенных вычислительных экспериментов, доказано, что библиотечная функция newton_krylov, предназначенная для решения больших систем нелинейных уравнений, имеет в два раза меньшее быстродействие, чем алгоритм TSLS+WD
(two-step least squares), реализованный средствами библиотеки NumPy.

Целью настоящей публикации является сравнение по числу итераций, быстродействию, а главное, по результату решения модельной задачи в виде системы из ста нелинейных алгебраических уравнений при помощи библиотечной функции scipy.optimize.root и методом Ньютона, реализованного средствами библиотеки NumPy.

Возможности решателя scipy.optimize.root для численного решения систем алгебраических нелинейных уравнений

Библиотечная функция scipy.optimize.root выбрана в качестве базы сравнения, потому что имеет обширную библиотеку методов, пригодных для сравнительного анализа.

scipy.optimize.root(fun, x0, args=(), method=’hybr’, jac=None, tol=None,callback=None, ptions=None)
fun — Векторная функция для поиска корня.
x0 –Начальные условия поиска корней

method:
hybr -используется модификация Пауэлл гибридный метод;
lm – решает системы нелинейных уравнений методом наименьших квадратов.
Как следует из документации [3] методы broyden1, broyden2, anderson, linearmixing, diagbroyden, excitingmixing, krylov являются точными методами Ньютона. Остальные параметры являются «не обязательными» и с ними можно ознакомится в документации.

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

Приведенный далее материал действительно можно прочитать в литературе, например в [4], но я уважаю своего читателя и для его удобства приведу вывод метода по возможности в сокращенном виде. Те, кто не любит формулы, этот раздел пропускают.

В методе Ньютона новое приближение для решения системы уравнений (2) определяется из решения системы линейных уравнений:

(3)

Определим матрицу Якоби:

(4)

Запишем(3) в виде:

(5)

Многие одношаговые методы для приближенного решения (2) по аналогии с двухслойными итерационными методами для решения систем линейных алгебраических уравнений можно записать в виде:

(6)

где — итерационные параметры, a — квадратная матрица n х n, имеющая обратную.

При использовании записи (6) метод Ньютона (5) соответствует выбору:

Система линейных уравнений (5) для нахождения нового приближения может решаться итерационно. В этом случае мы имеем двухступенчатый итерационный процесс с внешними и внутренними итерациями. Например, внешний итерационный процесс может осуществляться по методу Ньютона, а внутренние итерации — на основе итерационного метода Зейделя

При решении систем нелинейных уравнений можно использовать прямые аналоги стандартных итерационных методов, которые применяются для решения систем линейных уравнений. Нелинейный метод Зейделя применительно к решению (2) дает:

(7)

В этом случае каждую компоненту нового приближения из решения нелинейного уравнения, можно получить на основе метода простой итерации и метода Ньютона в различных модификациях. Тем самым снова приходим к двухступенчатому итерационному методу, в котором внешние итерации проводятся в соответствии с методом Зейделя, а внутренние — с методом Ньютона.

Основные вычислительные сложности применения метода Ньютона для приближенного решения систем нелинейных уравнений связаны с необходимостью решения линейной системы уравнений с матрицей Якоби на каждой итерации, причем от итерации к итерации эта матрица меняется. В модифицированном методе Ньютона матрица Якоби обращается только один раз:

(8)

Выбор модельной функции

Такой выбор не является простой задачей, поскольку при увеличении числа уравнений в системе в соответствии с ростом числа переменных результат решения не должен меняться, поскольку в противном случае невозможно отследить правильность решения системы уравнений при сравнении двух методов. Привожу следующее решение для модельной функции:

Функция f создаёт систему из n нелинейных уравнений, решение которой не зависит от числа уравнений и для каждой из n переменных равно единице.

Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью библиотечной функции optimize.root для разных методов отыскания корней

Только один из методов, приведенных в документации [3] прошёл тестирование по результату решения модельной функции, это метод ‘krylov’.

Решение для n=100:

Вывод: С увеличением числа уравнений вдвое заметно появление ошибок в решении. При дальнейшем увеличении n решение становится не приемлемым, что возможно из-за автоматической адаптации к шагу, эта же причина резкого падения быстродействия. Но это только моё предположение.

Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью программы написанной на Python 3 с учётом соотношений (1)-(8) для отыскания корней по модифицированному методу Ньютона

Решение для n=100:

Решение для n=200:

Solution:
[1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1.]
Newton iteration = 14
Newton method time 1.869 seconds

Чтобы убедиться в том, что программа действительно решает систему, перепишем модельную функцию для ухода от корня со значением 1 в виде:

Получим:
Solution:
[ 0.96472166 0.87777036 0.48175823 -0.26190496 -0.63693762 0.49232062
-1.31649896 0.6865098 0.89609091 0.98509235]
Newton iteration = 16
Newton method time 0.046 seconds

Вывод: Программа работает и при изменении модельной функции.

Теперь вернёмся к начальной модельной функции и проверим более широкий диапазон для n, например в 2 и 500.
n=2
Solution:
[1. 1.]
Newton iteration = 6
Newton method time 0.048 seconds
n=500

Лекция «Численные методы решения уравнений»
учебно-методический материал

Лекция по разделу «Численные методы».

Рассматриваются следующие методы решения алгебраических и трансцендентных уравнений:

1) метод дихотомии (метод деления отрезка пополам),

3) метод касательных,

4) метод итераций.

Скачать:

Вложение	Размер
численные методы решения уравнений	87 КБ

Предварительный просмотр:

Тема 12.2.Приближенное решение алгебраических и трансцендентных уравнений.

Задача о нахождении приближенных значений действительных корней уравнения f(x)=0 предусматривает предварительное отделение корня , т.е. установления промежутка, в котором других корней данного уравнения нет.

Будем предполагать, что функция f(x) в промежутке [a; b] непрерывна вместе со своими производными f’(x) и f’’(x) , значения f(а) и f(b) функции на концах промежутка имеют разные знаки, т.е. f(а) ∙ f(b) , и обе производные f’(x) и f’’(x) сохраняют знак во всем промежутке [a; b].

Т.к. действительными корнями уравнения f(x)=0 являются абсциссы точек пересечения кривой y=f(x) с осью ОХ , то отделение корня можно произвести графически.

Иногда полезно уравнение f(x)=0 записать в виде . Действительными корнями исходного уравнения служат абсциссы точек пересечения графиков функций .

Мы рассмотрим 4 численных решения уравнений.

1. Метод дихотомии (метод деления отрезка пополам).

Этот метод можно использовать когда нам предположительно или точно известны границы отрезка, содержащего корень и на этих границах f(x) принимает значения разных знаков, тогда по теореме о достаточных условиях существования корня на заданном отрезке существует хотя бы один корень.

Делим отрезок [a; b] пополам.
Определяем, на границах какой из частей первоначального интервала функция f(x) меняет знак.
Полученный интервал снова делим на две части и т.д.

Такой процесс продолжаем до тех пор, пока не перестанут изменяться сохраняемые в ответе десятичные знаки.

Пусть требуется вычислить действительный корень уравнения f(x)=0 , изолированный на отрезке [a;b]. Рассмотрим график функции у= f(x) . Пусть f(а) и f(в) >0. Точки графика А[a;f(a)] и В[b;f(b)] соединим хордой .За приближенное значение искомого корня примем абсциссу х 1 точки пересечения хорды АВ с осью Ох .

Это приближенное значение находится по формуле , где x 1 ∈ (a;b)

Пусть, например, f(x 1 ) тогда за новой (более узкий) промежуток изоляции корня принять [x 1 ,b].

Соединив точки А 1 [x 1 ;f(x 1 )] и В[b;f(b)] , получим в точке пересечения хорды с осью Ох второе приближение x 2 , которое вычислим по формуле: и т.д.

Последовательность чисел a 1 , x 1 , x 2 ,… стремится к искомому корню уравнения f(x)=0 .Вычисление приближенных значений корней уравнения следует вести до тех пор, пока не перестанут изменятся те десятичные знаки, которые мы хотим сохранить в ответе (т.е.пока не будет достигнута заданная степень точности)

Если Х-точный корень уравнения f(x)=0 , изолированный на отрезке [а,в] , а ξ- приближенное значение корня ,найденное методом хорд ,то оценка погрешности этого приближенного значения такова:

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

Пусть действительный корень уравнения f(x)=0 изолирован на отрезке [а,в] . Будем предполагать, что все ограничения, сформулированные выше относительно f(x) , сохраняют силу и в этом случае. Выделяем на отрезке [а,в] такое число x 0 , при котором f(x 0 ) имеет тот же знак, что и f’’(x 0 ) т.е. f(x 0 ) f’’(x 0 )>0 (в частности , за x 0 может быть принят тот из концов отрезка [а,в] , в котором соблюдено это условие). Проведем в точке Мо[x 0 , f(x 0 )] касательную к кривой y=f(x) .

y= f(x)

За приближенное значение корня примем абсциссу точки пересечения этой касательной с осью Ох . Это приближенное значение корня находится по формуле: .

Применив этот прием вторично в точке M 1 [x 1 ; f(x 1 )] , найдем и т.д.

Полученная т.об. последовательность x 0 , x 1 , x 2 ,… имеет своим пределом искомый корень.

Для оценки погрешности приближенного значения корня, найденного, методом Ньютона, может быть .использовано неравенство:

4. Метод итераций.

Если данное уравнение приведено к виду , где всюду на отрезке [а,в] , на котором исходное уравнение имеет единственный корень, то исходя из некоторого начального .значения x 0 , принадлежащего отрезку [а,в] , можно построить такую последовательность: …

Пределом этой последовательности является единственный корень уравнения f(x)=0 на отрезке [а,в]. Погрешность приближенного значения x n корня Х , найденного методом итерации, оценивается неравенством.

односторонняя сходимость:

y y=x

источники:

http://habr.com/ru/post/419453/

http://nsportal.ru/npo-spo/estestvennye-nauki/library/2019/05/07/lektsiya-chislennye-metody-resheniya-uravneniy