Следствие. Если хотя бы для одного не крайнего коэффициента условие (2а) не выполняется, т.е.

,

То имеется хотя бы одна пара комплексных корней.

Методы уточнения корней

Имеем: для уравнения (1) на интервале (a,b) отделен корень . Требуется уточнить отделенный корень с ошибкой, определяемой заданной величиной .

Рассмотрим четыре метода уточнения отделенных корней.

Метод половинного деления

Имеем: f(x)=0, (a,b), где - точное значение корня,

а) f(x) – непрерывнана отрезке [ab],

б) f(a)· f(b)< 0.

Метод половинного деления состоит в построении путем деления пополам последовательности вложенных отрезков

[a_k,b_k] [a_k-1b_k-1] [a₀,b₀ ] [a,b], на концах которых удовлетворяются условия f(a_k)·f(b_k)<0, k=1,2,…, а вложенные отрезки определяются делением предыдущего отрезка пополам.

Рис. 2. К методу половинного деления

В соответствии с Рис.2 имеем:

1) , вычисляется , если

2, иначе процесс деления продолжается:

2) , вычисляется , если

2 2², иначе процесс деления продолжается:

………………………………………………………………………….

k) , вычисляется , если 2 2^k, иначе процесс деления продолжается k=1,2,3,… .

Очевидно:

Таким образом, метод половинного деления сходится к , как геометрическая прогрессия со знаменателем равным 1/2.

Достоинства: 1) прост в алгоритмизации и программировании;

2) на функцию f(x) не накладываются ограничения, кроме ее непрерывности.

Недостаток: метод медленно сходится! - сходимость первого порядка

На практике итерационный процесс останавливается при выполнении неравенства:

а результатом является .

Метод Ньютона (метод касательных)

В данном методе функция f(x) должна удовлетворять на отрезке (a,b) следующим условиям:

1) функция должна быть дважды дифференцируема;

2) (x) ≠ 0; (*)

3) , на отрезке [a,b].

Итерационный алгоритм в методе Ньютона имеет вид

, k=0,1,2,… (3)

x₀=b или x₀=a,

где: x_k – значение корня на k-ой итерации;

h_k=? – корректирующая поправка x_k на k-ой итерации.

Требуется определить h_k.

Представим график функции f(x), удовлетворяющий условиям (*), на отрезке [a,b] на Рис.3

Пояснение метода Ньютона на Рис.3.

Рис.3. Метод Ньютона

Из (прямоугольного) имеем / откуда , тогда на основании (2а) имеем

Аналогично из прямоугольного треугольника получаем

В общем случае для (k+1)-ой итерации можно записать

(3а)

Сходимость итерационного алгоритма (2*) или (3а) очевидна.

Остановка итерационного алгоритма производится при выполнении условия , а результатом является .

Достоинство – сходимость метода на порядок больше по сравнению с методом половинного деления.

Недостатки: – более жесткие требования к f(x) (смотри (*));

– в каждой итерации необходимо вычислять и

Метод секущих (хорд)

Требования к f(x) такие же, как в методе Ньютона. Итерационный алгоритм метода секущих получается из итерационного алгоритма методом Ньютона (3а) заменой производной ее приближенным значением

а) , если ,

или б) , если ,

При замене производной по формулеа) получим алгоритм метода секущих с неподвижным правым концом

(4)

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

Рис. 4. Метод секущих

Итерации сходятся к со скоростью метода Ньютона. Остановка алгоритма при выполнении условия – заданная ошибка, а результатом является .

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

Метод простых итераций уточнения корней уравнения (1) состоит в замене этого уравнения эквивалентным ему уравнением

и (5)

и построении последовательности

(6)

Если не удается выразить х из уравнения (1), то эквивалентное уравнение и эквивалентную функцию можно построить, например, так

x=x+f(x), =x+f(x), а далее выстраивается последовательность (6).

Последовательность (6) называется методом простых итераций.

Два вопроса:

1) сходится ли последовательность (6)?

2) если сходится, то является ли предел сходимости корнем уравнения (1) на интервале (a,b)?

Ответ на вопросы дает теорема о достаточном условии сходимости метода простой итерации к точному решению нелинейного уравнения, формирующаяся следующим образом: если функция в эквивалентном уравнении (5) определена и дифференцируема на отрезке x и если существует число q такое, что на отрезке выполняется неравенство , то последовательность (6) сходится к единственному корню уравнения (1) на интервале (a,b)при любом начальном приближении .

Точность последовательности (6) определяется неравенством

, (7)

или . (7а)

Остановка итерационного процесса (6) производится при выполнении

(8)

где - заданная точность вычисления корня .

Действительно, на основании (7) максимальная величина ошибки на k-ой итерации равна

(9)

Учитывая требование < , на основании (9) можно записать

, что идентично с (8).

 

Геометрическая интерпретация сходимости метода простых итераций:

Рис.5. Метод простой итерации

 

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

Пример:

Уточнить отделённый корень на интервале (0.5, 1.0) с точностью

 

иначе

 

продолжить итерации до выполнения условия остановки.

 

 

12

---

Не нашли, что искали? Воспользуйтесь поиском по сайту:

©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.