Учеба и Обучение | ИнфоСайт

ЗАДАНИЕ 4. ЧИСЛЕННОЕ РЕШЕНИЕ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Техника - Алгоритмы

Основные итерационные методы уточнения корней

Пусть дано уравнение , , где − дважды непрерывно дифференцируемая функция.

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

Основные итерационные методы уточнения корней

Пусть дано уравнение , , где − дважды непрерывно дифференцируемая функция.

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

Уравнение (4.1) записывают в виде разрешенном, относительно x:

. (4.2)

Переход от записи уравнения (4.1) к эквивалентной записи (4.2) можно сделать несколькими способами, например, положив

, (4.3)

где - произвольная, непрерывная, знакопостоянная функция (и часто достаточно выбрать ψ=const).

В этом случае корни уравнения (4.2) являются также корнями (4.1), и наоборот.

Исходя из записи (4.2) члены рекуррентной последовательности в методе простой итерации вычисляются по закону

(4.4)

Метод является одношаговым, так как последовательность x0, x1, …, xm-1(m=1) и для начала вычислений достаточно знать одно начальное приближение или или . имеет первый порядок

Условием сходимости метода простой итерации, если дифференцируема, является выполнение неравенства

для любого . (4.5)

Максимальный интервал (α, β), для которого выполняется неравенство (4.5), называется областью сходимости. При выполнении условия (4.5) метод сходится, если начальное приближение x0 выбрано из области сходимости.

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

Этот метод является модификацией метода простой итерации и часто называется методом касательных. Если f(x) имеет непрерывную производную и − дважды непрерывно дифференцируемая функция, тогда, выбрав в (4.3) , получаем эквивалентное уравнение .

k=1,2,… (4.6)

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

Из (4.6) видно, что этот метод одношаговый (m=1) и для начала вычислений требуется задать одно начальное приближение из области сходимости:

при или при .

Метод Ньютона получил также второе название метод касательных. Основной его недостаток - малая область сходимости и необходимость вычисления производной f'(x).

Метод секущих

Данный метод является модификацией метода Ньютона, позволяющей избавиться от явного вычисления производной путем ее замены приближенной формулой. Тогда вместо процесса (4.6) получаем:

.k=1,2,… (4.7)

Здесь h - некоторый малый параметр метода, который подбирается из условия наиболее точного вычисления производной.

Метод одношаговый (m=1), и его условие сходимости при правильном выборе h такое же, как у метода Ньютона.

Если f"(x)*f(a)<0; то x0=a, если же f"(x)*f(b)<0; то x0=b. X принадлежит интервалу с корнем.

Рекуррентное соотношение (4.7) можно преобразовать к более простой форме.

Каждое последующее приближение вычисляется по рекуррентной формуле

, (4.7а)

которая справедлива, если данная функция f(x) на интервале (a;b) выпуклая: (). - и ,

Если же функция вогнута, используют следующую рекуррентную формулу:

(4.7б)

и

Метод Вегстейна

Этот метод является модификацией предыдущего метода секущих. В нем предлагается при расчете приближенного значения производной по разностной формуле использовать вместо точки в (1.7) точку , полученную на предыдущей итерации. Расчетная формула метода Вегстейна:

. (4.8)

Метод является двухшаговым (m=2), и для начала вычислений требуется задать 2 начальных приближения . Лучше всего . Метод Вегстейна сходится медленнее метода секущих, однако, требует в 2 раза меньшего числа вычислений f(x) и за счет этого оказывается более эффективным.

Этот метод иногда называется улучшенным методом простой итерации и в применении к записи уравнения в форме (1.2) имеет вид

(4.9)

Метод деления отрезка пополам

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

Для разрывных функций, а также. если не требуется быстрая сходимость, для нахождения простого корня на интервале (α, β) применяют надежный метод деления отрезка пополам. Его алгоритм основан на построении рекуррентной последовательности по следующему закону: в качестве начального приближения выбираются границы интервала, на котором точно имеется один простой корень далее находится его середина очередная точка x3x2 интервалов или , на котором находится корень. выбирается как середина того из смежных с

В результате получается следующий алгоритм метода деления отрезка пополам:

1. Вычисляем .

2. Вычисляем .

3. Если тогда

иначе .

4. Если тогда повторять с п.2.

5. Вычисляем

6. Конец.

За одно вычисление функции погрешность уменьшается вдвое, то есть скорость сходимости невелика, однако метод устойчив к ошибкам округления и всегда сходится.

Варианты заданий

1. По схеме, приведенной на рис.1.2 создать и отладить программу отделения всех корней функции f(x) на указанном интервале [a, b], в соответствии с полученным вариантом из табл. 1.1.

2. Далее создать программу уточнения корня указанным итерационным методом. Метод нахождения корня оформить в виде отдельной функции. Выбрать точность ε=10-3, ε=10-4, ε=10-5. Функция должна проверить правильность определения корня (f(x*) приблизительно равна нулю).

3. После выполнения расчетов нарисовать график сходимости xk к указанному корню x* , для чего предусмотреть в процедуре нахождения корня возможность вывода значений xk и

Примечание.

В табл. 4.1. все функции на указанном интервале имеют три корня.

4. Решить уравнение для выбранного интервала методом деления отрезка пополам

Таблица 4.1

N	f(x)	Интервал	методы
А	B
1		-2	2	Метод простой итерации
2		-1	3	Метод секущих
3		1	8	Метод Ньютона
4		4	7	Метод Вегстейна
5		4	8	Метод секущих
6		2	6	Метод простой итерации
7		3	9	Метод секущих
8		-4	0	Метод секущих
9		-12	5	Метод Вегстейна
10		-2	5	Метод Ньютона
11		-6	2	Метод Ньютона
12		-4	2	Метод Ньютона
13		-7	3	Метод секущих
14		-4	3	Метод Вегстейна
15		-4	4	Метод секущих