Блок – схема решения уравнения 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)
0	-11	3453	-5183	0.7
1	-10.3	134.3	-4234	0.03
2	-10.27	37.8	-4196	0.009
3	-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

Интерполирование функций.