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

курсовая работа

3. Метод половинного деления (Дихотомии)

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

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

Рис. 1

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

Алгоритм данного метода можно записать так:

1.Ввести данные (a, b, е).

2.Если нужная точность достигнута (| b - a | < 2е) то иди к п.6

3.Возьми середину очередного отрезка (x= ( a + b )/ 2).

4.Если значения функции в точках a и c одного знака (f(a)*f(c)>0), то в качестве следующего отрезка взять правую половину (а=c), иначе левую (b=c).

5.Иди к п.2.

6.Напечатать ответ c=...

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

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

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

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

Реализация удаления корней: « Если x1 есть простой корень уравнения f(x) непрерывна, то вспомогательная функция g(x)=f(x)/(x-x1) непрерывна, причем все нули функций f(x) и g(x) совпадают, за исключением x1, то он будет нулем g(x) кратности на единицу меньше; остальные нули обеих функций по-прежнему будут одинаковы». Калиткин Н.Н. «Численные методы» стр.140

Пример. Необходимо методом дихотомии уточнить корень уравнения х 3 - 3 х +1 = 0 с точностью 10 -3 (табл. 2) .

Таблица 2

N

a n

b n

f(x n)

0

0

1

0,5

-0,375

1

0

0,5

0,25

0,2656

2

0,25

0,5

0,375

-0,0723

3

0,25

0,375

0,3125

0,0930

4

0,3125

0,375

0,3438

0,0092

5

0,3438

0,375

0,3594

-0,0318

6

0,3438

0,3594

0,3516

-0,0113

7

0,3438

0,3516

0,3477

-0,0011

8

0,3438

0,3477

0,3458

0,0040

9

0,3458

0,3477

0,3468

0,0013

10

0,3468

0,3477

0,3473

a10 - b10 = 0,3468 - 0,3477 = 0,0009 < , где = 0,001.

0,347 .

Делись добром ;)