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

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

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

Примеры приближенных решений нелинейных уравнений онлайн

Задача 1. Методом бисекции найти решение нелинейного уравнения на отрезке $[a;b]$ с точностью $\varepsilon = 10^<-2>$. Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью $\varepsilon=10^<-4>$. Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности число итераций.

Задача 2. Отделить корни нелинейного уравнения аналитически $2 arcctg x -x+3=0$.

Задача 3. Отделить корни нелинейного уравнения аналитически и уточнить один из них методом проб с точностью до 0,01. $$3x^4-8x^3-18x^2+2=0.$$

Задача 4. Отделить корни нелинейного уравнения графически (например, в среде EXCEL) уточнить один из них методом проб с точностью до 0,01. $$x^2-20 \sin x =0.$$

Задача 5. Отделите корни уравнения графически и уточните один из них методом хорд с точностью до 0,001. Уточните один из корней этого уравнения методом касательных с точностью до 0,001. $$ \sqrt — \cos 0.387 x =0.$$

Задача 6.Отделить корни уравнения графически и уточнить один из них методом итераций с точностью до 0,001. $$\sqrt=\frac<1>.$$

Задача 7. На отрезке $[0;2]$ методом Ньютона найти корень уравнения $-x^3-2x^2-4x+10=0$ с точностью 0,01.

Задача 8. Методом хорд найти отрицательный корень уравнения $x^3-2x^2-4x+7=0$ с точностью 0,0001. Требуется предварительное построение графика функции и отделение корней.

Задача 9. Решить нелинейные уравнения с точностью до 0.001. $$1)\, x^3-12x-5=0\, (x \gt 0), \, 2)\, \tan x -1/x=0. $$

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

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

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

Отделение корней

1.2.2.1. Графическое отделение корней

1.2.2.2. Аналитическое отделение корней

Уточнение корней

1.2.3.1. Метод половинного деления

1.2.3.2. Метод итерации

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

1.2.3.4. Метод хорд

1.2.3.5. Сравнение методов решения нелинейных уравнений

1.2.4. Тестовые задания по теме «Методы решения нелинейных уравнений»

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

Одной из важнейших и наиболее распространенных задач математического анализа является задача определения корней уравнения с одним неизвестным, которое в общем виде можно представить как f(x) = 0. В зависимости от вида функции f(x)различают алгебраические и трансцендентные уравнения. Алгебраическими уравненияминазываются уравнения, в которых значение функции f(x)представляет собой полином n-й степени:

f(x) = Р(х) = a_n x n + a₂ x 2 + …+ a₁ x + a₀ = 0.(1.2.1-1)

Всякое неалгебраическое уравнение называется трансцендентным уравнением. Функция f(x) в таких уравнениях представляет собой хотя бы одну из следующих функций: показательную, логарифмическую, тригонометрическую или обратную тригонометрическую.

Решением уравнения f(x)=0называется совокупность корней, то есть такие значения независимой переменной , при которых уравнение обращается в тождество . Однако, точные значения корней могут быть найдены аналитически только для некоторых типов уравнений. В частности, формулы, выражающие решение алгебраического уравнения, могут быть получены лишь для уравнений не выше четвертой степени. Еще меньше возможностей при получении точного решения трансцендентных уравнений. Следует отметить, что задача нахождения точных значений корней не всегда корректна. Так, если коэффициенты уравнения являются приближенными числами, точность вычисленных значений корней заведомо не может превышать точности исходных данных. Эти обстоятельства заставляют рассматривать возможность отыскания корней уравнения с ограниченной точностью (приближенных корней).

Задача нахождения корня уравнения с заданной точностью ( >0)считается решенной, если вычислено приближенное значение , которое отличается от точного значения корня не более чем на значение e

(1.2.1-2)

Процесс нахождения приближенного корня уравнения состоит из двух этапов:

1) отделение корней (локализация корней);

Итерационное уточнение корней.

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

Этап уточнения корня имеет своей целью вычисление приближенного значения корня с заданной точностью. При этом применяются итерационные методы вычисления последовательных приближений к корню: x₀, x₁, . x_n, …, в которых каждое последующее приближение x_n+1вычисляется на основании предыдущего x_n. Каждый шаг называется итерацией. Если последовательность x₀, x₁, . x_n, …при n ® ¥ имеет предел, равный значению корня , то говорят, что итерационный процесс сходится.

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

Отделение корней

Корень уравнения f(x)=0считается отделенным (локализованным) на отрезке , если на этом отрезке данное уравнение не имеет других корней. Чтобы отделить корни уравнения, необходимо разбить область допустимых значений функции f(x) на достаточно узкие отрезки, в каждом их которых содержится только один корень. Существуют графический и аналитический способы отделения корней.

Уточнение корней

Задача уточнения корня уравнения с точностью , отделенного на отрезке [a;b], состоит в нахождении такого приближенного значения корня , для которого справедливо неравенство .Если уравнение имеет не один, а несколько корней, то этап уточнения проводится для каждого отделенного корня.

Метод половинного деления

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

Метод половинного деления позволяет получить последовательность вложенных друг в друга отрезков [a_1;b₁], [a₂;b₂], …,[a_i;b_i],…, [a_n;b_n], таких что f(a_i).f(b_i)

может быть принято за приближенное значение корня, например его середину отрезка

В методе половинного деления от итерации к итерации происходит последовательное уменьшение длины первоначального отрезка [a₀;b₀]в два раза (рис. 1.2.3-1). Поэтому на n-м шаге справедлива следующая оценка погрешности результата:

(1.2.3-1)

где — точное значение корня, х_nÎ [a_n;b_n] – приближенное значение корня на n-м шаге.

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

(1.2.3-2)

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

Рис. 1.2.3-2. Схема алгоритма метода половинного деления

Схема алгоритма метода половинного деления приведена на рис. 1.2.3-2. В приведенном алгоритме предполагается, что левая часть уравнения f(x)оформляется в виде программного модуля.

Пример 1.2.3-1. Уточнить корень уравнения x 3 +x-1=0 с точностью =0.1, который локализован на отрезке [0;1].

Результаты удобно представить с помощью таблицы 1.2.3-3.

k	a	b	f(a)	f(b)	(a+b)/2	f((a+b)/2)	a _k	b _k
-1	0.5	-0.375	0.5
0.5	-0.375	0.75	0.172	0.5	0.75
0.5	0.75	-0.375	0.172	0.625	-0.131	0.625	0.75
0.625	0.75	-0.131	0.172	0.688	0.0136	0.625	0.688

После четвертой итерации длина отрезка |b₄-a₄| = |0.688-0.625| = 0.063 стала меньше величины e, следовательно, за приближенное значение корня можно принять значение середины данного отрезка: x = (a₄+b₄)/2 = 0.656.

Значение функции f(x) в точке x = 0.656 равно f(0.656) = -0.062.

Метод итерации

Метод итераций предполагает замену уравнения f(x)=0 равносильным уравнением x=j(x). Если корень уравнения отделен на отрезке [a;b], то исходя из начального приближения x₀Î[a;b], можно получить последовательность приближений к корню

x₁ = j(x₀), x₂ = j(x₁), …, , (1.2.3-3)

где функция j(x) называется итерирующей функцией.

Условие сходимости метода простой итерации определяется следующей теоремой.

Пусть корень х* уравнения x=j(x) отделен на отрезке [a;b]и построена последовательность приближений по правилу x_n=j(x_n_-1). Тогда, если все члены последовательности x_n=j(x_n_-1) Î [a;b] и существует такое q (0 -1. Таким образом, очевидно, что если |j’(x)| 1. На рис. 1.2.3-4а показан случай, когда j’(x)>1, а на рис. 1.2.3-4b – когда j’(x) 0.

Таким образом, если за неподвижную точку приняли точку а,то в качестве начального приближения выступает х₀ = b, и наоборот.

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

Оценка погрешности метода хорд определяется выражением

(1.2.3-15)

Условие окончания процесса итераций по методу хорд

(1.2.3-16)

В случае, если M₁ x – 3x = 0, отделенный на отрезке [0;1] с точностью 10 -4 .

Проверим условие сходимости:

Следовательно, за неподвижную точку следует выбрать а=0, а в качестве начального приближения принять х₀=1, поскольку f(0)=1>0 и f(0)*f»(0)>0.

Результаты расчета, полученные с использованием формулы
1.2.3-14, представлены в таблице 1.2.3-4.

i	x	f(x)
0.7812	-0.1569
0.6733	-0.0591
0.6356	-0.0182
…	………..	………..
0.6191	-4.147∙10 -5

Требуемая точность достигается на 8-й итерации. Следовательно, за приближенное значение корня можно принять х = 0.6191.

Схема алгоритма метода хорд приведена на рис. 1.2.3-10.

Выбор неподвижной точки, определяющей вид расчетной формулы, производится путем сравнения одного из концов отрезка [a;b] с начальным приближением (x₀=a). В качестве неподвижного конца отрезка (точка с) выбирается тот, который не совпадает с начальным приближением.

Рис. 1.2.3-10. Схема алгоритма метода хорд

Нелинейное уравнение – это

1)алгебраическое или трансцендентное уравнение

2)алгебраическое уравнение

3)тригонометрическое уравнение

4)трансцендентное уравнение

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

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

Отделение корней

1.2.2.1. Графическое отделение корней

1.2.2.2. Аналитическое отделение корней

Уточнение корней

1.2.3.1. Метод половинного деления

1.2.3.2. Метод итерации

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

1.2.3.4. Метод хорд

1.2.3.5. Сравнение методов решения нелинейных уравнений

1.2.4. Тестовые задания по теме «Методы решения нелинейных уравнений»

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

f(x) = Р(х) = a_n x n + a₂ x 2 + …+ a₁ x + a₀ = 0.(1.2.1-1)

(1.2.1-2)

Процесс нахождения приближенного корня уравнения состоит из двух этапов:

1) отделение корней (локализация корней);

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

Введение

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

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

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

(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

источники:

http://lektsia.com/3x5f9a.html

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