Дихотомия (метод деления отрезка пополам).

1. Пусть

существует хотя бы один корень на ;

2.

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

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

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

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

Метод применим к корням нечетной кратности, но хуже устойчив к ошибкам округления. Метод не применим к системам уравнений.

 

 

 

§12. Метод простой итерации для решения алгебраических и трансцендентных уравнений.

ТЕОРЕМА 1. (Принцип Банаха сжимающихся отображений).

Пусть R – полное метрическое пространство. Если сжатие, то для него существует в R единственная неподвижная точка, к которой сходится итерационный процесс.

, где - произвольный.

План доказательства.

1. – фундаментальная

(*)

q – коэффициент сжатия

.

2. Т.к. R – полное метрическое пространство, то в нем всякая фундаментальная последовательность сходится.

– сходится, , причем , т.е. – неподвижная точка.

3. – единственна.

ЧТД.

 

- последовательность приближения к решению уравнения

 

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

Если в (*) зафиксировать, а , то

– оценка погрешности, оценка скорости сходимости.

со скоростью геометрической прогрессии.

– линейная скорость сходимости.

Метод простой итерации имеет линейную скорость сходимости.

Пусть (2), – вещественная функция.

Необходимо привести к виду .

, - знакопостоянная непрерывная функция.

 

Условие сходимости для данного метода: