Нахождение корней методом половинного деления

Пусть дано уравнение f(x)=0, (1)

Причем f(x) непрерывна на отрезке [a, b] и . Делим отрезок пополам и находим середину

Если f(x₁) ≠0 то для продолжения вычисления выберем ту из частей данного отрезка [a, х₁] или [х₁, b]. Концы нового отрезка обозначим через a₁ и b₁ .

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

(2)

Из (2) получаем:

(3)

с погрешностью ε не превышающей

Пример:

Методом половинного деления с точностью ε = 10^-2 найти корень уравнения

1. Определяем корни уравнения при

x		+1
f(x)	+	-

1. Уточняем значение корня:

и т.д.

Заданная точность достигается на седьмом шаге.

х7 =0.8828125 с погрешностью d7=0,0078125<ε=0.01

Блок – схема решения уравнения f(x) методом половинного деления

Метод хорд

Дано уравнение f(x)=0. Пусть найден отрезок , такой, что на его концах функция f(x) имеет разные знаки, то есть . Пусть, кроме этого, производные и на отрезке сохраняют знак. (Пусть при a₀<x<b₀).

За приближенное значение корня принимаем точку пересечения с осью ОХ хорды, проходящей через точки A₀[a₀,f(a₀)], B₀[b₀,f(b₀)]

Уравнение хорды:

(1)

Точка пересечения a₁ с осью ОХ находится из (1) при у=0 (при этом х=а₁):

(2)

Принимая а₁ за конец первого отрезка , можно снова провести хорду и получится приближенное значение а₂

(3)

И так далее

(4)

Можно показать, что процесс сходится и в пределе .

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

Пусть ξ – корень уравнения f(x)=0 определен на отрезке причем и непрерывны и сохраняют знаки при a<x<b. Найдя какое-нибудь n-ое приближенное значение корня x_n= ξ (a≤x_n≤b), мы можем уточнить его по методу Ньютона.

Положим

(1)

Где h_n-малая величина.

По формуле Тейлора, беря только линейные члены находим:

(2)

Так как - «корень», то

Из (2) следует:

Подставляя h_n в (1), получаем новое приближение корня:

(3)

Так как уравнение касательной в точке B_n[b_n,f(b_n)]:

Полагая у=0 (корень!); x_n=x_n+1 получим

Поэтому метод Ньютона называют еще методом касательных.

Если в качестве начального приближения выбрать точку а, то получили бы новое приближение, выходящее за интервал . Следовательно «хорошим» начальным приближением x₀ является то, для которого выполнено неравенство:

(4)

Для оценки точности (погрешности) n-го приближения x_n можно воспользоваться следующим соотношением:

,

То есть «установившееся» начальные десятичные знаки приближения x_n и x_n+1,являются верными (следует взять более двух последующих приближений!)

Пример:

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

с пятью верными знаками.

Решение:

Полагая х=0,-10,-100,…, получим f(0)=-10000, f(-10)=-1050, f(-100)≈10⁸

Искомый корень находится в интервале [-100,-10]. Сузим интервал, рассматривая точку х=-11 f(-11)=3453.

Таким образом -11<ξ<-10

На этом интервале и . Так как , то есть , за начальное приближение выбираем х₀=-11.

Результаты вычислений сводим в таблицу:

n	xn	f(xn)
	-11		-5183	0.7
	-10.3	134.3	-4234	0.03
	-10.27	37.8	-4196	0.009
	-10.261	0.2	-	-

Останавливаемся на n=3. проверяем точность решения, давая приращение . (два знака до запятой, три знака – после)

-5 значащих цифр.

-10261<ξ<-10260

Любое из этих чисел дает искомое приближение. (А хорошо бы еще 1-2 итерации выполнить)

ЛЕКЦИЯ 7

Приближенное решение алгебраических и трансцендентных уравнений (продолжение)

Метод итераций

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

Пусть дано уравнение:

f(x)=0 (1)

где f(x) – непрерывная функция. требуется вычислить действительный корень уравнения (1) находящийся на отрезке .

Заменим уравнение (1) на равносильным ему уравнением

(2)

где - непрерывна на функция.

Выбираем произвольное и подставляем его в правую часть равенства (2). Получаем

Аналогично получаем

Рассмотрим последовательность x₀,x₁,x₂,…,x_n,…

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

Так как уравнения (1) и (2) равносильны, то c-корень и уравнения (1), то есть исходного уравнения.

Выясним при каких значениях процесс сходится.

Теорема

Пусть функция определена и дифференцируема на отрезке , причем все ее значения . Пусть кроме этого,

при (3)

Тогда итерационный процесс сходится и дает в пределе единственный корень уравнения

Доказательство:

Уравнение имеет на отрезке действительный корень. Обозначим его ξ

Выбираем произвольные и строим итерационную последовательность ; ;…; .

Рассмотрим уравнение

. (*)

Т.к. ( - корень уравнения , т.е. , а ).

Применяем теорему Лагранжа к уравнению (*).

,

где лежит между и , т.е. .

Согласно неравенству (3), имеем

, т.к. .

Аналогично находим

Используя следующее неравенство, получаем

Повторяя процесс, получаем

(4)

По условию теоремы , поэтому из (4) следует

, т.е. .

Т.е. итерационная последовательность сходится и дает в пределе корень уравнения . Корень этот единственный.

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

Пришли к противоречию. Теорема доказана.

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

Замечание 2. ,

Т.к. , , то каждое последующее приближение ближе к корню чем предыдущее.

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

Корень уравнения - это абсцисса точки пересечения кривой и прямой .

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

Условие теоремы , автоматически выполняются если .

б) При последовательные приближения колеблются около .

в) При итерационный процесс расходится!

Для применения метода итераций уравнение нужно привести к виду так, чтобы при .

Это можно сделать различными способами:

1. Уравнение заменяется равносильным .

В этом случае .

Параметр подбирают так, чтобы , при .

2. Уравнение заменяется равносильным ,

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

подбирают так, чтобы , при .

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

Оценка приближения.

Из условия (4) , учитывая, что , получаем

. (1)

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

. (2)

Из (1) и (2) следует, что итерационный процесс сходится тем быстрее, чем меньше .

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

. (3)

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

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

.

при всех .

Сузим этот интервал методом половинного деления.

Вычислим , поэтому .

! поэтому заменяем исходное уравнение равносильным

,

получаем ; .

Находим , такое чтобы при .

Пусть

Тогда

При ,

Получаем .

Пусть

При таком выполняется достаточное условие сходимости итерационного процесса, т.к. ; .

Выбираем

Подставляем , в правую часть уравнения

получаем

Аналогично находим:

; ; ; ; ; ; ; ;

Оценим погрешность по формуле

Итак ;

1) Условие сходимости всегда выполняется для функций , где .

2) Если производная отрицательна на отрезке , то уравнение , заменяется на .

ЛЕКЦИЯ 8