Лабораторная работа

ЧИСЛЕННОЕ НАХОЖДЕНИЕ ИЗОЛИРОВАННОГО КОРНЯ НЕЛИНЕЙНОГО УРАВНЕНИЯ

Решение уравнений – алгебраических или трансцендентных – представляет собой одну из существенных задач прикладного анализа, потребность в которой возникает во многочисленных и самых разнообразных разделах физики, механики, техники и других областях.

Пусть дано уравнение

f (x ) = 0. (1)

Всякое число х *, обращающее функцию f (x ) в нуль, т.е. такое, при котором f (х *) = 0, называется корнем уравнения (1) или нулем функции f (x ).

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

1. Функция f (x ) непрерывна на отрезке [a, b ] вместе со своими производными 1-го и 2-го порядка;
2. Значения f (x ) на концах отрезка имеют разные знаки (f (a ) * f (b ) < 0).

3. Первая и вторая производные f " (x ) и f "" (x ) сохраняют определенный знак на всем отрезке.

Условия 1) и 2) гарантируют, что на интервале [a, b ] находится хотя бы один корень, а из 3) следует, что f (x ) на данном интервале монотонна и поэтому корень будет единственным.

Задача нахождения корня уравнения f (x ) = 0 итерационным методом состоит из двух этапов:

1. отделение корней - отыскание приближенного значения корня или содержащего его отрезка;

2. уточнение приближенных корней - доведение их до заданной степени точности.

Процесс отделения корней начинается с установления знаков функции f (x ) в граничных x = a и x = b точках области ее существования.

Пример 1. Отделить корни уравнения:

x 3 – 6x + 2 = 0 (2)

Составим приблизительную схему:

х	- ∞	- 3	- 1				+ ∞
f (x )	–	–	+	+	–	+	+

Следовательно, уравнение (2) имеет три действительных корня, лежащих в интервалах [-3, -1], и .

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

В инженерной практике распространен графический способ определения приближенных корней.

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

Пусть корень уравнения (1) изолирован на отрезке [a , b ]. Итерационный процесс уточнении начального приближения х 0 к точному решению состоит в последовательном получении последующего приближение из предыдущего (предыдущих). Каждый такой шаг называется итерацией . Применение того или иного метода зависит от имеющегося начального приближения х 0 к корню, существования и гладкости производных функции f (x ). В результате итераций находится последовательность приближенных значений корня х 1 , х 2 , ..., х n . Если эти значения с увеличением числа итераций n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится .

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

| x k +1 – x k | < ε ,

где x k , x k +1 – последовательные приближения к корню, ε > 0 – заданная точность окончания итерационного процесса. Если же функция изменяется быстро, т.е.

| f ´ (x ) | ≥ 1, то итерационный процесс следует оканчивать по выполнению условия

| f (x k ) | < ε .

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

Этот метод является одним из простейших итерационных методов вычисления вещественного корня уравнения (1) на отрезке [α , β ]. Его применяют, когда f (x ) непрерывна на [α , β ] и на концах этого отрезка принимает значения разных знаков, т.е.

f (α ) · f (β ) < 0.

Вычислительная схема метода . Отрезок [α , β ] делят пополам и если f ≠ 0, то выбирают ту из половин , , на концах которой функция f (x ) принимает значения разных знаков (корень находится в ней). Полученный отрезок опять делят пополам и повторяют описанные действия до тех пор, пока не получат корень с заданной точностью итерационного процесса. Процесс оканчивается по выполнению условия

| x k +1 – x k | < ε .

Число итераций k в методе половинного деления определяется по формуле

k ≈ .

Пример 1 . Методом половинного деления вычислить корень уравнения

х 3 + 3х 2 – 1 = 0 (2)

с точностью 0,01 на отрезке .

Проверяем условия применимости метода. Функция f (x ) является полиномом третьей степени (непрерывна) и f (0) · f (1) < 0.

Вычисляем последовательно приближения к корню и проверяем их по точности:

x 0 = 0		f (0)= – 1	[ –, + ]
x 1 = 1	|0 – 1| > 0,01	f (1)=3
x 2 = 0,5	|1 – 0,5|> 0,01	f (0,5)= – 0,125
x 3 = 0,75	|0,5 – 0,75|> 0,01	f (0,75)≈1,109
x 4 = 0,625	|0,5 – 0,625|> 0,01	f (0,625)≈0,416
x 5 = 0,5625	|0,5 – 0,5625|> 0,01	f (0,5625)≈0,127
x 6 = 0,53125	|0,5 – 0,53125|> 0,01	f (0,53125)≈ – 0,0034
x 7 = 0,546875	|0,53125 – 0,546875|> 0,01	f (0, 546875)≈0,0608
x 8 = 0,5390625	|0,53125 – 0,5390625|≤ 0,01	f (0, 5390625)≈0,0284

Примем за уточненное значения корня величину

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

Пока не будет достигнута нужная точность.

Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд .

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

Метод половинного деления известен также как метод бисекции . В данном методе интервал делится ровно пополам.

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

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

1. Один из простых способов поиска корней функции одного аргумента .
2. Применяется для нахождения значений действительно-значной функции , определяемому по какому-либо критерию (это может быть сравнение на минимум , максимум или конкретное число).

Метод половинного деления как метод поиска корней функции

Изложение метода

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

Будем считать, что корень функции отделён на отрезке . Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления. Другими словами, требуется найти приближённое значение корня с заданной точностью .

Пусть функция непрерывна на отрезке ,

и - единственный корень уравнения .

(Мы не рассматриваем случай, когда корней на отрезке несколько, то есть более одного. В качестве можно взять и другое достаточно малое положительное число, например, .)

Поделим отрезок пополам. Получим точку и два отрезка .

Новый отрезок делим пополам. Получаем середину этого отрезка и так далее.

Для того, чтобы найти приближённое значение корня с точностью до 0" alt=" \eps >0">, необходимо остановить процесс половинного деления на таком шаге , на котором и вычислить . Тогда можно взять .

Реализация метода на С++ и числовой пример

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

Ниже приведен пример программы на Си++ , которая решает поставленную задачу.

Программа 1. Корень уравнения

#include #include using namespace std; const double epsilon = 1e-2 ; double f(double x) { return 4 - exp (x) - 2 * x^ 2 ; } int main() { double a, b, c; a = 0 ; b = 2 ; while (b - a > epsilon) { c = (a + b) / 2 ; if (f(b) * f(c) < 0 ) a = c; else b = c; } cout << (a + b) / 2 << endl; return 0 ; }

Искомый корень . Вычисления проводились с точностью .

Промежуточные вычисления представлены в таблице ниже.

n	a n	b n	c n	b n -c n
1	0	1	0.5	0.5
2	0.5	1	0.75	0.25
3	0.75	1	0.875	0.125
4	0.875	1	0.9375	0.0625
5	0.875	0.9375	0.90625	0.03125
6	0.875	0.90625	0.890625	0.015625
7	0.875	0.890625	0.8828125	0.0078125

Метод половинного деления как метод оптимизации

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

Рассмотрим метод половинного деления как простейший однопараметрический метод безусловной оптимизации. Данный метод является методом прямого поиска . В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

Дана функция . Необходимо найти , доставляющий минимум (или максимум) функции на интервале с заданной точностью , т.е. найти

.

Запишем словесный алгоритм метода.

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

- константа,

При выводе – координата точки, в которой функция имеет минимум (или максимум), – значение функции в этой точке.

Метод хорд

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

Изложение метода

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

При этом в процессе поиска семейство хорд может строиться:

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

• для случая а):

• для случая б):

Процесс поиска продолжается до тех пор, пока не выполнится условие или .

Метод обеспечивает быструю сходимость, если %200" alt="f(z)\cdot f""(z) > 0">, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.

Схема алгоритма уточнения корня методом хорд представлена на рис. 4.

Комбинация метода хорд и метода половинного деления

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

где функция f(x) определена и непрерывна на некотором конечном или бесконечном интервале x . В частности, в форме нелинейных уравнений представляются математические модели анализа статических свойств объектов проектирования или их элементов. Если функция f(x) представляет собой многочлен n-й степени видаa0 + a1 x + a2 x2 + ... + anxn, то уравнение (1) называется алгебраическим. Когда x находится под знаком трансцендентной функции (показательной, логарифмической, тригонометрической и т.п.), уравнение называется трансцендентным. Значение аргумента x, при котором функция f(x) обращается в нуль, т.е. f(x*) = 0, называется корнем уравнения.

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

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

• 1) отделение корней, т.е. нахождение интервалов , внутри которых содержится один и только один корень уравнения;
• 2) уточнение приближенных значений отдельных корней до заданной степени точности.

Этап отделения корней может быть выполнен различными способами. Во-первых, приближенное значение корня иногда бывает известно из физического смысла задачи. Во-вторых, для отделения корней может использоваться графический способ, основанный на построении графика функции

нелинейный уравнение половинный деление

где приближенные значения действительных корней уравнения f(x) = 0 соответствуют абсциссам точек пересечения или касания графика с осью 0x (y = 0). Наиболее часто применяется метод отделения корней, основанный на следующем положении: если на концах некоторого интервала значения непрерывной функции f(x) имеют разные знаки, т.е. f(a)f(b) , то на этом интервале уравнение (1) имеет хотя бы один корень. При этом корень является единственным, если производная функции f"(x) существует и сохраняет постоянный знак внутри интервала .Рассмотрим простейший алгоритм отделения корней нелинейных уравнений, ориентированный на использование ЭВМ. Исходный интервал [, ], на котором определена и непрерывна функция f(x), разбивается на n отрезков равной длины

(x0, x1), (x1, x2), ..., (xn -1, xn),где x0 x1 ...xn и x0 = , xn =

Затем вычисляются значения функции f(xj) в точках xj (j =) и выбирается отрезок (xi, xi+1), на концах которого функция имеет разные знаки, т.е. f(xi)f(xi+1) 0. Если длина этого отрезка достаточно мала (можно предположить единственность корня), то считается, что корень отделен на интервале , где a = xi, b = xi+1. В противном случае границы исходного интервала сдвигаются, т.е. = xi, = xi + 1, и процедура повторяется.

Необходимо отметить, что длина исходного интервала , на котором определена функция f(x), может изменяться в широких пределах. Поэтому число отрезков n, а также длина искомого интервала являются переменными величинами, которые должны задаваться в каждом конкретном случае с учетом физического смысла решаемой задачи.

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

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

Обозначим исходный интервал как . Для нахождения корня уравнения f(x) = 0 отрезок делится пополам, т.е. вычисляется начальное приближение x0 = (a0 + b0)/2. Если f(x0) = 0, то значение x0 = x* является корнем уравнения. В противном случае выбирается один из отрезков или , на концах которого функция f(x) имеет разные знаки, так как корень лежит в этой половине. Далее выбранный отрезок обозначается как , вновь делится пополам точкой x1 = (a1 + b1)/2 и т.д. В результате на некоторой итерации получается точный корень x* уравнения f(x) = 0, либо бесконечная последовательность вложенных отрезков , , ..., , ..., таких, что f(ai)f(bi) (i =1, 2, ...), сходящихся к корню x*.

Если требуется определить корень x* с погрешностью, то деление исходного интервала продолжают до тех пор, пока длина отрезка не станет меньше 2, что записывается в форме условия bi - ai 2.

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

x* (ai + bi) / 2.

Метод половинного деления легко реализуется на ЭВМ и является наиболее универсальным среди итерационных методов уточнения корней. Его применение гарантирует получение решения для любой непрерывной функции f(x), если найден интервал, на котором она изменяет знак. В том случае, когда корни не отделены, будет найден один из корней уравнения. Метод всегда сходится, но скорость сходимости является небольшой, так как за одну итерацию точность увеличивается примерно в два раза. Поэтому на практике метод половинного деления обычно применяется для грубого нахождения корней уравнения, поскольку при повышении требуемой точности значительно возрастает объем вычислений.

Пусть f (x ) – непрерывная функция на [a ; b ], .

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

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

Обозначим через тот конец отрезка, где знаки
и
совпадают. Последовательные приближения к точному корнюc находим по формуле

для
.

Тогда
является точным корнем уравнения (1).

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

Метод секущих

Пусть есть какое-то начальное приближение . Получим еще одну точку по формуле
, гдеh – небольшое число. Будем считать, что мы выполнили несколько шагов метода, и к данному моменту у нас есть два последовательных приближения и
к точному корню (на начальном этапе – этои). Тогда следующее приближение находим по формуле

,

Процесс останавливается по такому же критерию, как и в методе Ньютона.

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

В методе итераций исходное уравнение (1) преобразуется в равносильное уравнение
. Выбирается начальное приближение. Каждое следующее приближение получается по формуле
,
Процесс останавливается по тому же критерию, что и в методе Ньютона. Метод будет сходиться, т.е. пределравен точному значению корня, если в окрестности корня выполнено неравенство
и начальное приближение находится достаточно близко к корню.

Преимущества и недостатки методов

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

Метод Ньютона обладает очень быстрой сходимостью (квадратичная сходимость), т.е.

,

где c – точное значение корня; M – некоторая константа, зависящая от функции. Грубо говоря, начиная с некоторой итерации, число верных знаков после запятой станет удваиваться на каждой итерации.

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

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

Метод итераций дает скорость сходимости значительно меньшую, чем метод Ньютона. При наличии сходимости действует оценка
, где
– числа,
,
;c –точное значение корня. Величины M , q зависят от функции и не зависят от номера итерации. Если же
близок к 1, тоq тоже близко к 1 и сходимость метода будет медленной. Счет по методу итераций можно начать без проверки условий на
и. В этом случае процесс может оказаться расходящимся, и тогда ответ не будет получен.

Существует много методов нахождения корней нелинейного уравнения, отличных от перечисленных. В MATHCAD функция root в формате
использует метод секущих, а если он не приводит к желаемым результатам, то – метод Мюллера. В последнем, в отличие от метода секущих, на каждом шаге берутся две дополнительные точки, график функции заменяется параболой, проходящей через три точки, и за следующее приближение берется точка пересечения параболы с осьюOx . В функции root в формате root(f (x ), x , a , b ) используются методы Риддера и Брента. Для нахождения корней многочлена в MATHCAD используется метод Лагерра.

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

Считаем, что отделение корней уравнения f (x ) = 0 проведено и на отрезке [ a , b ] расположен один корень, который необходимо уточнить с погрешностью ε. В качестве начального приближения корня принимаем середину этого отрезка: c 0 = (a + b) / 2 (рис. 4):

Рис. 4. Метод половинного деления.

Затем исследуем значение функции f (x ) на концах отрезков [ a , c 0 ] и [ c 0 , b ] . Тот из отрезков, на концах которого f (x ) принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка [ a 1 , b 1 ] (на рис. 4 это отрезок [ a , c 0 ]). Вторую половину отрезка [ a , b ], на которой f (x ) не меняет знак, отбрасываем. В качестве следующего приближения корня принимаем середину нового отрезка
c 1 = (a 1 + b 1 ) / 2 и т.д. Таким образом, k -е приближение вычисляется как

После каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, а после k итераций в 2 k раз:

Прекратить итерационный процесс следует, когда будет достигнута заданная точность, т.е. при выполнении условия |x 0 – c k | < ε

Поскольку корень x 0 принадлежит отрезку [ a k , b k ], а c k – середина этого отрезка, то величина |x 0 – c k | всегда будет меньше половины длины от резка [ a k , b k ] (см. рис. 4):

Следовательно, условие |x 0 – c k | < ε будет выполнено, если

| b k – a k | < 2ε

Таким образом, итерационный процесс нужно продолжать до тех пор, пока не будет выполнено условие | b k – a k | < 2ε .

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

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

поэтому данный метод является методом с линейной сходимостью.

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

Метод хорд

Рассматриваемый метод так же, как и метод половинного деления, предназначен для уточнения корня на интервале [ a , b f (x ) принимает значения разных знаков. Очередное приближение в отличие от метода половинного деления берем не в середине отрезка, а в точке x , где пересекает ось абсцисс прямая линия (хорда), проведенная через точки А и В (рис. 5).

Рис. 5. Метод хорд.

Запишем уравнение прямой, проходящей через точки А и В :

Для точки пересечения прямой с осью абсцисс (x = x 0 , y = 0) получим уравнение

В качестве нового интервала для продолжения итерационного процесса выбираем тот из двух [ a , x 0 ] и [ x 0 , b ], на концах которого функция f (x ) принимает значения разных знаков. Для рассматриваемого случая (рис. 5) выбираем отрезок [ a , x 0 ], так как
f(a) × f(x 0) < 0 . Следующая итерация состоит в определении нового приближения x 1 как точки пересечения хорды AB 1 с осью абсцисс и т.д.

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

x k +1 – x k < ε

З а м е ч а н и е . Метод хорд и метод половинного деления очень похожи. При этом второй их них в ряде случаев дает более быструю сходимость итерационного процесса. Оба метода не требуют знания дополнительной информации о функции на всем интервале [ a , b ]. Например, не требуется, чтобы функция была дифференцируема. Даже для разрывных функций рассмотренные методы обладают гарантированной сходимостью.

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

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

Отделяя корни функции, следует учесть, что применение метода Ньютона требует, чтобы функция была монотонна и дважды дифференцируема, причем вторая производная f’’(x) на этом интервале не должна менять знак.

Cходимость итерационной последовательности, получаемой в методе Ньютона, зависит от выбора начального приближения x 0 . В общем случае, если задан интервал [ a , b ], содержащий корень, и известно, что функция f (x ) монотонна на этом интервале, то в качестве начального приближения x 0 можно выбрать ту границу отрезка [ a , b ], где совпадают знаки функции f (x ) и второй производной f’’(x) . Такой выбор начального приближения гарантирует сходимость метода Ньютона при условии монотонности функции на отрезке локализации корня.

Пусть нам известно начальное приближение к корню x 0 . Проведем в этой точке касательную к кривой y = f (x ) (рис. 6). Эта касательная пересечет ось абсцисс в точке, которую будем рассматривать в качестве следующего приближения.