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

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

Метод хорд

Блок – схема решения уравнения f(x) методом половинного деления - student2.ru Дано уравнение f(x)=0. Пусть найден отрезок Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , такой, что на его концах функция f(x) имеет разные знаки, то есть Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . Пусть, кроме этого, производные Блок – схема решения уравнения f(x) методом половинного деления - student2.ru и Блок – схема решения уравнения f(x) методом половинного деления - student2.ru на отрезке Блок – схема решения уравнения f(x) методом половинного деления - student2.ru сохраняют знак. (Пусть Блок – схема решения уравнения f(x) методом половинного деления - student2.ru при a0<x<b0).

За приближенное значение корня принимаем точку пересечения с осью ОХ хорды, проходящей через точки A0[a0,f(a0)], B0[b0,f(b0)]

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

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

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

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

Принимая а1 за конец первого отрезка Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , можно снова провести хорду и получится приближенное значение а2

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

И так далее

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

Можно показать, что процесс сходится и в пределе Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

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

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

Положим

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

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

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

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

Так как Блок – схема решения уравнения f(x) методом половинного деления - student2.ru - «корень», то Блок – схема решения уравнения f(x) методом половинного деления - student2.ru

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

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

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

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

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

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

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

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

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

Если в качестве начального приближения выбрать точку а, то получили бы новое приближение, выходящее за интервал Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . Следовательно «хорошим» начальным приближением x0 является то, для которого выполнено неравенство:

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

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

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

Блок – схема решения уравнения f(x) методом половинного деления - student2.ru То есть «установившееся» начальные десятичные знаки приближения xn и xn+1,являются верными (следует взять более двух последующих приближений!)

Пример:

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

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

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

Решение:

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

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

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

На этом интервале Блок – схема решения уравнения f(x) методом половинного деления - student2.ru и Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . Так как Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , то есть Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , за начальное приближение выбираем х0=-11.

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

n xn f(xn) Блок – схема решения уравнения f(x) методом половинного деления - student2.ru Блок – схема решения уравнения f(x) методом половинного деления - student2.ru
-11 -5183 0.7
-10.3 134.3 -4234 0.03
-10.27 37.8 -4196 0.009
-10.261 0.2 - -

Останавливаемся на n=3. проверяем точность решения, давая приращение Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . (два знака до запятой, три знака – после)

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

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

-10261<ξ<-10260

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

ЛЕКЦИЯ 7

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

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

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

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

f(x)=0 (1)

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

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

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

где Блок – схема решения уравнения f(x) методом половинного деления - student2.ru - непрерывна на Блок – схема решения уравнения f(x) методом половинного деления - student2.ru функция.

Выбираем произвольное Блок – схема решения уравнения f(x) методом половинного деления - student2.ru и подставляем его в правую часть равенства (2). Получаем

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

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

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

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

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

Рассмотрим последовательность x0,x1,x2,…,xn,…

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

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

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

Теорема

Пусть функция Блок – схема решения уравнения f(x) методом половинного деления - student2.ru определена и дифференцируема на отрезке Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , причем все ее значения Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . Пусть кроме этого,

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

Тогда итерационный процесс сходится и дает в пределе единственный корень уравнения Блок – схема решения уравнения f(x) методом половинного деления - student2.ru

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

Уравнение Блок – схема решения уравнения f(x) методом половинного деления - student2.ru имеет на отрезке Блок – схема решения уравнения f(x) методом половинного деления - student2.ru действительный корень. Обозначим его ξ

Выбираем произвольные Блок – схема решения уравнения f(x) методом половинного деления - student2.ru и строим итерационную последовательность Блок – схема решения уравнения f(x) методом половинного деления - student2.ru ; Блок – схема решения уравнения f(x) методом половинного деления - student2.ru ;…; Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

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

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

Т.к. ( Блок – схема решения уравнения f(x) методом половинного деления - student2.ru - корень уравнения Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , т.е. Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , а Блок – схема решения уравнения f(x) методом половинного деления - student2.ru ).

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

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

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

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

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

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

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

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

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

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

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

По условию теоремы Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , поэтому из (4) следует

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

Т.е. итерационная последовательность сходится и дает в пределе корень уравнения Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . Корень этот единственный.

Действительно, предположим, что на этом отрезке есть еще корень уравнения Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . Тогда Блок – схема решения уравнения f(x) методом половинного деления - student2.ru т.к. Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

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

Замечание 1. По условию теоремы итерационный процесс сходится при любом выборе Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . Благодаря этому он является самоисправляющимся, т.к. неверно вычисленное Блок – схема решения уравнения f(x) методом половинного деления - student2.ru можно рассматривать как новое нулевое приближение.

Замечание 2. Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , Блок – схема решения уравнения f(x) методом половинного деления - student2.ru

Т.к. Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , то каждое последующее приближение ближе к корню чем предыдущее.

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

Блок – схема решения уравнения f(x) методом половинного деления - student2.ru Корень уравнения Блок – схема решения уравнения f(x) методом половинного деления - student2.ru - это абсцисса точки пересечения кривой Блок – схема решения уравнения f(x) методом половинного деления - student2.ru и прямой Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

а) При Блок – схема решения уравнения f(x) методом половинного деления - student2.ru приближения Блок – схема решения уравнения f(x) методом половинного деления - student2.ru и т.д. монотонно убывают, приближаясь к Блок – схема решения уравнения f(x) методом половинного деления - student2.ru (или возрастают, если Блок – схема решения уравнения f(x) методом половинного деления - student2.ru ).

Условие теоремы Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , автоматически выполняются если Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

б) При Блок – схема решения уравнения f(x) методом половинного деления - student2.ru последовательные приближения колеблются около Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

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

в) При Блок – схема решения уравнения f(x) методом половинного деления - student2.ru итерационный процесс расходится!

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

Для применения метода итераций уравнение Блок – схема решения уравнения f(x) методом половинного деления - student2.ru нужно привести к виду Блок – схема решения уравнения f(x) методом половинного деления - student2.ru так, чтобы Блок – схема решения уравнения f(x) методом половинного деления - student2.ru при Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

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

1. Уравнение Блок – схема решения уравнения f(x) методом половинного деления - student2.ru заменяется равносильным Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

В этом случае Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

Параметр подбирают так, чтобы Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , при Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

2. Уравнение Блок – схема решения уравнения f(x) методом половинного деления - student2.ru заменяется равносильным Блок – схема решения уравнения f(x) методом половинного деления - student2.ru ,

где Блок – схема решения уравнения f(x) методом половинного деления - student2.ru - произвольная, дифференцируемая на отрезке Блок – схема решения уравнения f(x) методом половинного деления - student2.ru функция, не имеющая корней на отрезке Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

Блок – схема решения уравнения f(x) методом половинного деления - student2.ru подбирают так, чтобы Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , при Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

Можно показать, что при соответствующем выборе функции Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , получаются расчетные формулы метода хорд и метода касательных.

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

Из условия (4) Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , учитывая, что Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , получаем

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

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

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

Из (1) и (2) следует, что итерационный процесс сходится тем быстрее, чем меньше Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

Если Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , погрешность удобно оценить так: последовательные приближения Блок – схема решения уравнения f(x) методом половинного деления - student2.ru и Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , в этом случае лежат по разные стороны от корня Блок – схема решения уравнения f(x) методом половинного деления - student2.ru . Поэтому

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

Если за приближенное значение корня взять полусумму последних полученных приближений Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , то Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

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

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

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

Блок – схема решения уравнения f(x) методом половинного деления - student2.ru Сузим этот интервал методом половинного деления.

Вычислим Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , поэтому Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

Блок – схема решения уравнения f(x) методом половинного деления - student2.ru ! поэтому заменяем исходное уравнение равносильным

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

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

Находим Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , такое чтобы Блок – схема решения уравнения f(x) методом половинного деления - student2.ru при Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

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

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

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

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

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

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

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

При таком Блок – схема решения уравнения f(x) методом половинного деления - student2.ru выполняется достаточное условие сходимости итерационного процесса, т.к. Блок – схема решения уравнения f(x) методом половинного деления - student2.ru ; Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

Выбираем Блок – схема решения уравнения f(x) методом половинного деления - student2.ru

Подставляем Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , в правую часть уравнения

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

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

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

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

Оценим погрешность по формуле Блок – схема решения уравнения f(x) методом половинного деления - student2.ru

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

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

1) Условие сходимости Блок – схема решения уравнения f(x) методом половинного деления - student2.ru всегда выполняется для функций Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , где Блок – схема решения уравнения f(x) методом половинного деления - student2.ru Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

2) Если производная Блок – схема решения уравнения f(x) методом половинного деления - student2.ru отрицательна на отрезке Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , то уравнение Блок – схема решения уравнения f(x) методом половинного деления - student2.ru , заменяется на Блок – схема решения уравнения f(x) методом половинного деления - student2.ru .

ЛЕКЦИЯ 8

Наши рекомендации