Метод половинного деления (бисекции)

Механизм метода бисекции, который больше известен под названием метода половинного деления, очень прост и заключается в том, что полученный при локализации отрезок на каждой итерации делится пополам. Из двух половинок выбирается та, на концах которой функция принимает значения противоположных знаков. То есть проверяется то же условие, что и при методе сканирования. Процесс заканчивается, когда длина полученного интервала становится меньше произведения 2Ɛ. Фактически этот метод исключает возможность появления ошибки. «Аварийная» ситуация может быть вызвана лишь тем, что граница полученного на итерации отрезка попадет в точку разрыва функции. Метод половинного деления наиболее универсальный среди всех итерационных методов. Но, как всегда, бочка меда не обходится без ложки дегтя – для бисекции характерна очень низкая скорость сходимости.

Итерационная формула метода бисекции:

Скорость сходимости: низкая

Надежность сходимости: высокая

Метод Ньютона

Задан отрезок [а,b], содержащий корень уравнения F(x)=0. Уточнение значения корня производится путем использования уравнения касательной. В качестве начального приближения задается тот из концов отрезка [а,b], где значение функции и ее второй производной имеют одинаковые знаки (т.е. выполняется условие F(x0)*F"(x0) > 0).

В точке F(x0) строится касательная к кривой у = F(x) и ищется ее пересечение с осью х. Точка пересечения принимается за новую итерацию. Метод Ньютона самый быстрый способ нахождения корней уравнений

Итерационная формула имеет вид:

Итерационный процесс проходит до того времени, пока не будет выполнено условие |F(X)|< e, где e - заданная точность.

Рис. 1. Иллюстрация метода Ньютона

Рис. 1. иллюстрирует работу метода Ньютона. В данном случае вторая производная функции положительна, поэтому в качестве начального приближения выбрана точка хо = b. Как видно из рисунка, метод имеет очень быструю сходимость среди всех методов решения нелинейных уравнений: обычно заданная точность достигается за 2-3 итерации.

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

Метод хорд

Для реализации данного метода, нужно построить исходную функцию y=F(x) и найти значения функции на концах отрезка F(a) и F(b). Затем провести хорду М₁M₂ c концами в точках М₁(a, F(a)) и M₂(b, F(b)). Абсцисса точки пересечения хорды М₁M₂ с осью OX это и есть приближенный корень x₁. Далее найти точку M₃(X₁,F(x₁)), построить следующую хорду и найти второй приближенный корень x₂. И так далее. В зависимости от поведения функции возможны два случая:

Рис. 1

Рис. 2

Для первого случая (Рис. 1) справедлива следующая формула (8):

и справедливо неравенство: F(a)*F''(a)>0, где x₀=b.

Для второго случая (Рис. 2) справедлива следующая формула (9):

и справедливо неравенство: F(b)*F''(b)>0, где x₀=a.

Условия сходимости метода секущих аналогичны условиям сходимости метода Ньютона, т. е.:

Метод простых итераций

Для нахождения действительных корней уравнения F(x) = 0, где F(x) - непрерывная функция на [a; b], его заменяют равносильным уравнением

х = j(х) (14)

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

х³ - 9х + 3 = 0

можно представить так:

Пусть известен отрезок изоляции корня [a; b], тогда за начальное приближение искомого корня уравнения (14) берут: Подставляя значение х₀ в правую часть уравнения (14), получают первое приближение х₁ = j(х₀). В качестве второго приближения берут х₂ = j(х₁). Продолжая этот процесс дальше, получают числовую последовательность (х_n), определенную с помощью рекуррентной формулы:

x_n+1 = j(x_n), (n = 0, 1, 2,...) (15)

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

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

или x^* = j(x^*). (16)

Следовательно, в этом случае х = х^* является корнем уравнения х = j(х), а значит, и уравнения F(x) = 0.

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

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

½j‘(x)½ £ M₁ < 1 (18)

для всех х, принадлежащих отрезку изоляции корня уравнения (14), В этом случае процесс итераций сходится, и тем быстрее, чем меньше М₁; если же ½j‘(x)½ > 1, то итерационный процесс расходится. Для конкретной оценки величины m₁, определяющей скорость сходимости, проще всего пользоваться формулой: М₁ = max½j‘(x)½, где max берется по отрезкуизоляции корня [а: b].

 

Пример решения Mathcad

Найти решение уравнения:

Примечание: TOL – системная переменная для задания точности вычислений.

Задание

1) Решить уравнение методом бисекции.

2) Решить уравнение методом Ньютона

3) Решить уравнение методом хорд.

4) Решить уравнение методом простой итераций.

Содержание отчета

1) Тема, цель работы.

2) Индивидуальное задание, текст документа Mathcad с результатами вычислений по методу бисекции.

3) Индивидуальное задание, текст документа Mathcad с результатами вычислений по методу Ньютона.

4) Индивидуальное задание, текст документа Mathcad с результатами вычислений по методу хорд.

5) Индивидуальное задание, текст документа Mathcad с результатами вычислений по методу простой итерации.

6) Выводы по проделанной работе.

индивидуальные задания

Таблица 1
Функции к заданию 1

Вариант	Уравнение
	x^3 + 3x – 1 = 0
	x^3 + 2x + 1 = 0
	x^3 + x – 1 = 0
	x^3 – 3x^2 – 17x + 22 = 0
	cos x · e^x + 1 = 0
	e^x – x^2 = 0
	x^3 – 2^x + 2 = 0
	x^3 – x + 2 = 0
	x^3 – 2x – 5 = 0
	cos x – x + 4 = 0
	2x – 3ln x – 3 = 0
	x^2 + sin2x – 2 = 0
	x = tg x
	x^3 – 3x^2 + 2 = 0
	x^3 + x – 3 = 0
	x^3 – x + 1 = 0
	x^3 + 3x + 1 = 0
	x^3 + 3x^2 – 1 = 0
	x^3 + 4x^2 – 2 = 0
	x^5 – x – 0,2 = 0
	x^3 – 0,2x^2 – 0,2x – 1,2 = 0
	x^4 + 2x^3 – x – 1 = 0
	x^3 – 3x – 3 = 0
	x^3 – 2x – 8 = 0
	x^2 + 4 sin x = 0
	3x – cos x – 1 = 0
	2x – lg x = 0
	x^3 – 5x^2 – 4x + 0,092 = 0
	x^3 – 4x^2 – 7x + 13 = 0
	x^3 – 10x^2 + 44x – 29 = 0

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

1) В чем суть метода бисекции?

2) В чем суть метода хорд?

3) В чем суть метода Ньютона?

4) В чем суть метода простой итерации?

5) Какие панели и функции Mathcad используются для создания программного расчета?