Теория нелинейных уравнений и метод половинного деления.

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

Считаем, что отделение корней уравнения 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). Эта касательная пересечет ось абсцисс в точке, которую будем рассматривать в качестве следующего приближения.

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

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

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

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

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

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

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

1) Вычислим x = (a + b )/2; вычислим f (x );

2) Если f (x ) = 0, то переходим к пункту 5;

3) Если f (x )∙ f (a ) < 0, то b = x , иначе a = x ;

4) Если |b – a | > ε, переходим к пункту 1;

5) Выводим значение x ;

Пример 2.4. Уточнить методом бисекций с точностью до 0,01 корень уравнения (x – 1) 3 = 0, принадлежащий отрезку .

Решение в программе Excel :

1) В ячейках A 1:F 4 введем обозначения, начальные значения и формулы, как показано в таблице 2.3.

2) Каждую формулу скопируем в нижние ячейки маркером заполнения до десятой строки, т.е. B 4 - до B 10, C 4 - до C 10, D 3 - до D 10, E 4 - до E 10, F 3 - до F 10.

Таблица 2.3

	A	B	C	D	E	F
		f(a)=	=(1-B3)^3
	k	a	x	f(x)	b	b-a
		0,95	=(B3+E3)/2	=(1-C3)^3	1,1	=E3-B3
		=ЕСЛИ(D3=0;C3; ЕСЛИ(C$1*D3<0;B3;C3))			=ЕСЛИ(C$1*D3>0; E3;C3)

Результаты расчетов приведены в табл. 2.4. В столбце F проверяем значения длины интервала b – a . Если значение меньше чем 0,01, то в данной строке найдено приближенное значение корня с заданной погрешностью. Потребовалось 5 итераций для достижения требуемой точности. Приближенное значение корня с точностью до 0,01 после округления до трех знаков равно 1,0015625 ≈ 1,00.

Таблица 2.4

	A	B	C	D	E	F
		f(a)=	0,000125
	k	a	x	f(x)	b	b-a
		0,95	1,025	-2E-05	1,1	0,15
		0,95	0,9875	2E-06	1,025	0,075
		0,9875	1,00625	-2E-07	1,025	0,0375
		0,9875	0,996875	3,1E-08	1,00625	0,0187
		0,996875	1,0015625	-4E-09	1,00625	0,0094
		0,996875	0,9992188	4,8E-10	1,0015625	0,0047
		0,99921875	1,0003906	-6E-11	1,0015625	0,0023
		0,99921875	0,9998047	7,5E-12	1,000390625	0,0012

Приведенный алгоритм учитывает возможный случай «попадания в корень», т.е. равенство f (x ) нулю на очередном этапе. Если в примере 2.3 взять отрезок , то на первом же шаге попадаем в корень x = 1. Действительно, запишем в ячейке B 3 значение 0,9. Тогда таблица результатов примет вид 2.5 (приведены только 2 итерации).

Таблица 2.5

	A	B	C	D	E	F
		f(a)=	0,001
	k	a	x	f(x)	b	b-a
		0,9			1,1	0,2

Создадим в программе Excel пользовательские функции f(x) и bisect(a, b, eps) для решения уравнения методом половинного деления, пользуясь встроенным языком Visual Basic . Их описания приведены ниже:

Function f(Byval x)

Function bisect(a, b, eps)

1 x = (a + b) / 2

If f(x) = 0 Then GoTo 5

If f(x) * f(a) < 0 Then

If Abs(a - b) > eps Then GoTo 1

Функция f(x) определяет левую часть уравнения, а функция
bisect(a, b, eps) вычисляет методом половинного деления корень уравнения f (x ) = 0. Обратим внимание на то, что в функции bisect(a, b, eps) используется обращение к функции f(x). Приведем алгоритм создания пользователькой функции:

1) Выполним команду меню «Сервис - Макрос - Редактор Visual Basic ». Откроется окно «Microsoft Visual Basic ». Если в данном файле программы Excel ещё не были созданы макросы или пользовательские функции или процедуры, это окно будет иметь вид, изображенный на рис.2.4.

2) Выполним команду меню «Insert - Module» и вводим тексты программ-функции, как показано на рис 2.5.

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

Bisect(0,95;1;0,00001),

то получим значение 0,999993896.

Чтобы решить другое уравнение (с другой левой частью) нужно перейти в окно редактора с помощью команды «Сервис - Макрос - Редактор Visual Basic » и просто переписать описание функции f(x). Например, найдем с точностью до 0,001 корень уравнения sin5x + x 2 – 1 = 0, принадлежащий интервалу (0,4; 0,5). Для этого изменим описание функции

на новое описание

f = Sin(5 * x) + x ^ 2 - 1

Тогда в ячейке D 18 получим значение 0,441009521 (сравните этот результат со значением корня из интервала (0,4; 0,5), найденным в примере 2.3!).

Для решения уравнения методом половинного деления в программе Mathcad создадим подпрограмму-функцию bisec (f , a , b , ε), где:

f - имя функции, соответствующее левой части уравнения f (x ) = 0;

a , b - левый и правый концы отрезка [a , b ];

ε - точность приближенного значения корня.

Решение примера в программе Mathcad :

1) Запускаем программу Mathcad. Введем определение функции bisec (f , a , b , ε). Для этого с помощью клавиатуры и панели инструментов «Греческие символы» набираем bisec (f , a , b , ε):=. После знака присваивания «:=» на панели инструментов «Программирование» указателем мыши щелкаем левой кнопкой «Add line». После знака присваивания появится вертикальная линия. Далее вводим текст программы, который приведен ниже, используя панель инструментов «Программирование» для ввода знака «←», оператора цикла while , оператора break и условного оператора if otherwise .

2) Введем определение функции f (x ):=sin(5*x)+x^2–1, а затем вычислим значение корня с помощью функции bisec при заданных значениях:
bisec (f , –0.8,–0.7,0.0001)=. После знака «=» автоматически появится вычисленное программой значение корня –0,7266601563. Аналогично вычислим остальные корни.

Ниже приведен лист Mathcad с определением функции bisec (f , a , b , ε) и расчетами:

Приведем программу на языке C ++ для решения уравнения f (x ) = 0 методом половинного деления:

#include

#include

double f(double x);

typedef double (*PF)(double);

double bisec(PF f,double a, double b,double eps);

double a, b, x, eps;PF pf;

cout << "\n a = "; cin >> a;

cout << "\n b = "; cin >> b;

cout << "\n eps = "; cin >> eps;

x = bisec(pf,a,b,eps); cout << "\n x = " << x;

cout << "\n Press any key & Enter "; cin >> a;

double f(double x){

r = sin(5*x)+x*x-1;

double bisec(PF f, double a, double b,double eps){

do{ x = (a + b)/2;

if (f(x) == 0) break;

if (f(x)*f(a)<0) b = x;

}while (fabs(b-a) > eps);

В программе функция f (x ) определена для решения уравнения

sin5x + x 2 – 1 = 0

из примера 2.3. Результат работы программы для определения корня из интервала (0,4; 0,5) с точностью 0,00001 представлен ниже (экран компьютера):

Press any key & Enter

Последняя строка нужна для организации паузы для просмотра результата.

Пусть 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 используется метод Лагерра.

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

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

.

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

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

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

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

Из данного соотношения можно оценить число итераций k для достижения заданной точности :

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

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

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

Алгоритм нахождения корня нелинейного уравнения по методу половинного деления.

1. Найти начальный интервал неопределенности одним из методов отделения корней. Задать погрешность расчета (малое положительное число ) и начальный шаг итерации () .

2. Найти середину текущего интервала неопределенности:

3. Необходимо найти значение функции в точках , и . Далее необходимо проверить два условия:

Если выполняется условие , то искомый корень находится внутри левого отрезка положить, ;

Если выполняется условие , то искомый корень находится внутри правого отрезка принять , .

В результате находится новый интервал неопределенности, на котором находится искомых корень уравнения:

4. Проверяем новый отрезок на предмет заданной точности, в случае:

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

Если длина нового отрезка не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.