Конспект лекций междисциплинарного курса МДК.01.04 Математические методы разработки алгоритмов профессионального модуля ПМ.01 Разработка программных модулей программного обеспечения для компьютерных систем (стр. 4 )

Найдем интервалы изоляции для каждого из корней.

Рассмотрим для первого корня отрезок [-2, -1]:

f(-2) = -27 < 0,  f(-1) = 1 > 0,  f/(x) > 0 при , т. е. этот отрезок является интервалом изоляции корня.

Рассмотрим для второго корня отрезок [1, 3]:

f(1) = 9 > 0, f(3) = -7 < 0, f/(x) < 0 при , т. е. этот отрезок является интервалом изоляции корня.

Рассмотрим для третьего корня отрезок [4, 5]:

f(4) = -9 < 0, f(5) = 1 > 0, f/(x) > 0 при , т. е. этот отрезок является интервалом изоляции корня.

Табличный способ:

x	-3	-2	-1	0	1	2	3	4	5	6	7
f(x)	-79	-27	1	11	9	1	-7	-9	1	29	81

Графический способ:

Пусть интервалы изоляции корней известны. Познакомимся с несколькими итерационными методами, позволяющими найти корень на известном интервале изоляции [a, b].

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

Этот метод называют еще методом дихотомии или методом бисекции. Суть метода заключается в следующем. Найдем середину отрезка [a, b]: c = (a+b)/2. Корень остался на одной из частей: [a, c] или [c, b]. Если f(a) ⋅ f(с) < 0, то корень попал на отрезок [a, c], тогда деление отрезка можно повторить, приняв в качестве нового правого конца точку c, т. е. b = c. В противном случае корень попал на половину [c, b], и необходимо изменить значение левого конца отрезка: a = c. Поскольку корень всегда заключен внутри отрезка, итерационный процесс можно останавливать, если длина отрезка станет меньше заданной точности: |b – a| < е.

Пример. Найти первый корень уравнения f(x) = x3 – 6x2 + 3x + 11 = 0  с точностью .

Вычисления оформим в виде таблицы:

k	a	b	c	f(a)	f(c)	|b-a|
0	-2	-1	-1.5	-27	-10.375	1
1	-1.5	-1	-1.25	-10.375	-4.07813	0.5
2	-1.25	-1	-1.125	-4.07813	-1.39258	0.25
3	-1.125	-1	-1.0625	-1.39258	-0.1604	0.125
4	-1.0625	-1	-1.03125	-0.1604	0.42868	0.0625
5	-1.0625	-1.03125	-1.04688	-0.1604	0.136372	0.03125
6	….......
7
8
9
10	-1.05469	-1.05371	-1.0542	-0.01146	-0.00218	0.000977

где a0 , b0 – начальные границы интервала изоляции корня;

В результате расчета приближенное значение первого корня:   при точности и  х = -1.0542 при точности .

На рис. 2.1 приведена графическая иллюстрация метода.

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

2.3. Метод хорд

В этом методе кривая f(x) заменяется прямой линией – хордой, стягивающей точки (a, f(a)) и (b, f(b)). В зависимости от знака выражения f(a)⋅ f //(a) метод хорд имеет два варианта, изображенных на рис. 2.2а, б.

Рис. 2.2.  Геометрическая интерпретация метода хорд для F(a)⋅F //(a) > 0 (а)  и F(a)⋅F //(a) < 0 (б)

Пусть f(a)⋅f //(a) > 0 (рис. 2а). Тогда x0 = b, точка a будет оставаться неподвижной. Следующее приближение x1 находим как точку пересечения хорды, соединяющей точки (a, f(a)) и (x0, f(x0)) с осью x. Уравнение хорды:

.

Тогда точка пересечения хорды с осью x:

.

Пусть теперь f(a)⋅f //(a) < 0 (рис. 2б). Тогда x0 = a, точка b неподвижна. Проведем хорду, соединяющую точки (b, f(b)) и (x0, f(x0)):

.

Вычисляем точку пересечения хорды с осью x:

.

На следующей итерации в качестве x0 надо взять вычисленное значение x1.

Таким образом, имеем следующую последовательность вычислений:

если f(a)⋅f //(a) > 0, то  x0 = b  и .

Если же f(a)⋅f //(a) < 0, то x0 = a  и .

Окончание итерационного цикла в этом методе происходит по условию малости невязки уравнения:

|f(x1)| < е или .

Пример 2.3.1. Найти первый и третий корень уравнения x3 – 6x2 + 3x + 11 = 0 методом хорд.

Решение. Для первого корня  a = -2, b = -1, ,  тогда расчет ведется по первым формулам: x0 = b  и  .

Оформим вычисления в виде таблицы:

k	xk	|xk+1-xk|	f(xk)
0	-1	1
1	-1.03571	0.035714	0.345618
2	-1.0479	0.012187	0.117007
3	-1.05201	0.004108	0.039334
4	-1.05339	0.001379	0.013192
5	-1.05385	0.000462	0.004421

Для третьего корня: a = 4, b = 5, , тогда расчет ведется по вторым формулам: x0  = a  и .

Таблица вычислений:

k	xk	|xk+1-xk|	f(xk)
0	4	-9
1	4.9	0.9	-0.711
2	4.941555	0.041555	-0.02147
3	4.942783	0.001229	-0.00062
4	4.942819	3.57E-05	-1.8E-05

2.4. Метод простой итерации

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

x = ц(x).

Выберем начальное приближение x0 ∈[a, b]. Следующие итерации находим по формуле:

xk+1 = ц(xk),

т. е. x1=ц(x0), x2=ц(x1) и т. д. Итерационный процесс заканчивается, если

| xk+1 – xk | < е.

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

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

Геометрический смысл метода простой итерации:

Сходящийся метод простой итерации

Расходящийся метод простой итерации

В качестве начального приближения обычно берут середину отрезка [a, b]: .