Алгоритмы уточнения корня

2.3.1 Алгоритм уточнения корня методом половинного деления

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

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

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

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

§ либо найдется такая точка , в которой (что маловероятно!), и задача решена;

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

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

2.3.2 Алгоритм уточнения корня методом хорд

Сущность метода. Пусть отрезок изоляции корня уравнения найден, причем для определенности пусть и . График функции проходит через точки и (рис. 2.3.2(1)). Составим уравнение хорды как прямой, проходящей через точки и :

Рисунок 2.3.2(1) – Графическое представление метода хорд

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

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

Этот процесс можно продолжать неограниченно. Описанный процесс называется методом хорд.

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

(2.1)

называемой формулой метода хорд, и образуют монотонно возрастающую последовательность

, ограниченную сверху числом . По теореме Вейерштрасса эта последовательность имеет предел: .

Поскольку непрерывна на , то .

Переходя теперь к пределу в равенстве (2.1), получаем

откуда, так как , следует, что . Но в связи с тем, что уравнение на отрезке имеет единственный корень , то .

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

2.3.3 Алгоритм уточнения корня методом касательных

Сущность метода.Пусть — отрезок изоляции корня уравнения . И пусть для определенности , , и , , то есть производные сохраняют постоянный знак (рис.2.3.3(1)). Идея метода касательных, предложенного Ньютоном, сводится к замене небольшой дуги

Рисунок 2.3.3.(1) – Графическое представление метода касательных кривой касательной к кривой, проведенной в некоторой точке интервала .

Выберем, например, , так как , и в точке проведем касательную к кривой . Ее уравнение: .

Найдем теперь точку пересечения касательной с осью :

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

Имеем: .

Продолжая этот процесс далее, получим рекуррентную формулу,

(2.2)

называемую формулой метода касательных.

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

Как и в методе хорд, можно доказать (предлагаем читателю сделать это самостоятельно), что полученная числовая последовательность сходится к корню уравнения .

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

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

(2.3)

Пример 2. Методом касательных найти корень уравнения

на отрезке с точностью до .

Находим: .

Применив формулу (2.2), имеем:

.

Выберем начальное приближение , используя условие (2.3). Имеем:

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

Последовательные приближения вычисляем на ЭВМ, заполняя табл. 2.1.

Таблица 2.1 – Последовательные приближения

	2,0	2,135335	3,864665	0,552528
	1,5	0,473130	2,776870	0,170382	0,5
	1,38	0,033377	2,395523	0,013933	0,17
	1,316	0,000062	2,363794	0,000026	0,014
	1,8159738	0,0000005	2,3637346	0,0000002	0,0000262
	1,3159736	- 0,0000005	2,3637342	-0,0000002	0,0000002

Если в качестве приближенного значения корня взять число 1,3159736, то невязка .

2.3.4 Комбинированный метод хорд и касательных

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

Рисунок 2.3.4(1) – Иллюстрация метода хорд и касательных

Пусть (рис.2.3.4(1)) условие выполняется в правом конце отрезка изоляции корня ( ). Тогда последовательные значения с недостатком вычисляют методом хорд:

(2.4)

а последовательные значения корня с избытком

вычисляют методом касательных (2.2):

(2.5)

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

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

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

(2.6)

,(2.7)

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

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

Пример 3.Комбинированным методом хорд и касательных найти корень уравнения на отрезке с точностью .

Так как непрерывная функция, a и , то на отрезке имеется единственный корень уравнения. Вторая производная

.

Условие выполняется в точке , то есть . Следовательно, уточнение корня выполняем по формулам:

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

Таблица 2.2 - Расчетная таблица метода хорд и касательных

(9):(8)	(3)-(6):(7)	(3)-(2)	3*(2)-соs(2)–1	3*(3)–cos(3)-1	3 sin(3)	(6)-(5)	(6)*(2)-(5)*(3)
			-2	1,459697	3,841471	3,459697

Продолжение таблицы 2.2

0,5780853	0,6200162	0,0419309	-0,1032551	0,0461796	3,581048	0,1494401	0,0907188
0,607577	0,6071207	0,0000630

О точности полученных приближений можно судить по невязке:

2.3.5 Метод последовательных приближений (итераций)

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

(2.8)

Это можно сделать всегда, притом не одним способом. Например, уравнение можно представить так:

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

(2.9)

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

При пользовании методом итераций необходимо выяснить основной вопрос: сходится ли полученная последовательность () к решению уравнения (2.8) при возрастании ? Если последовательность () сходится, то есть существует предел , то, переходя к пределу в равенстве (2.9) и, предполагая, что функция непрерывна, получаем:

или . (2.10)

Следовательно, в этом случае является корнем уравнения , а значит, и уравнения .

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

Следовательно, метод последовательных приближений применим при выполнении условия:

(2.11)

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

Контрольные вопросы

1. Эквивалентность задач определения нулей функции и решения алгебраических уравнений.

2. Что называется корнем уравнения?

3. Необходимое и достаточное условие существования корней на заданном интервале.

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

5. Что такое интервал неопределенности?

6. Основные этапы решения задачи определения корней нелинейных уравнений.

7. Определение интервала изоляции корня - необходимое и достаточное условие единственности корня на заданном интервале.

8. Методы построения интервала изоляции корня: графический, аналитический, численный (табулирование функции).

9. В чем сущность этапа уточнения корня до заданной степени точности?

10. Процедура метода бисекции (он же называется методом деления отрезка пополам).

11. Для каких функций метод бисекции наиболее эффективен? Два типа изменения функции в окрестности нуля - два выхода из алгоритма бисекции.

12. Какие виды нелинейных уравнений можно решать численными методами?

13. Расскажите об отделении корней, приведя иллюстрацию для своего задания. Как выбирается величина ?

14. Сравните методы деления пополам и хорд.

15. Сравните методы касательных и секущих.

16. Как перейти от уравнения к равносильному ему уравнению ? Объясните алгоритм метода итераций.

17. Расскажите об условиях применения методов уточнения корней.

18. Как зависит в численных методах значение функции в корне от величины задаваемой ошибки?

19. Приведите примеры комбинации методов. Поясните их целесообразность.

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

21. Охарактеризуйте метод простой итерации. Как формулируется достаточное условие сходимости данного метода?

22. Опишите алгоритм метода Ньютона. В чем достоинство и недостаток этого метода?

23. Проведите сравнение методов по различным критериям.

24. Из какого конца следует проводить касательную в методе Ньютона?