Характеристика методов

Теоретические сведения

Постановка задачи

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

где функция

f(x)

f(x) = 0, (1.1)

определена и непрерывна на некотором

интервале

(a, b). Всякое значение

x *, обращающее функцию

f(x)

в нуль, т.е. такое, при котором

f(x*) = 0, называется

корнем уравнения, а процесс нахождения уравнения (1.1).

x* – решением

Если функция

f(x)

представляет собой многочлен

относительно

x, то уравнение (1.1) называется нелинейным

алгебраическим (например, x 4 − 3 x − 1= 0); если же в

функцию

f(x)

входят элементарные (тригонометрические,

логарифмические, показательные и др.) функции –

трансцендентным (например,

e x -x 2 − 5 = 0

). С точки зрения

вычислительной математики они эквивалентны.

Геометрически решение уравнения (1.1) состоит в

нахождении точек пересечения графика функции

осью ОХ (рис.1.1).

y = f (x) с

Характеристика методов

Методы решения нелинейных уравнений делятся на прямые и итерационные. Первые позволяют найти решение непосредственно с помощью формул и всегда обеспечивают получение точного решения (например, формула для решения квадратного уравнения). Однако они имеются лишь

для ограниченного круга уравнений, поэтому на практике более широко используются методы второго типа - итерационные. В них задается процедура решения в виде многократного применения некоторого алгоритма. Полученное решение всегда является приближенным, хотя может быть сколь угодно близким к точному. Кроме того, часто уравнения содержат коэффициенты, известные лишь приближенно, и, следовательно, сама задача о точном определении корней теряет смысл.

Можно выделить два типа итерационных методов:

Рис.1.1

1. Методы сужения интервала, содержащего корень

(например, методы половинного деления, золотого сечения).

Здесь используется только знак функции y =

f (x), а не ее

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

2. Методы аппроксимации, в которых функция

y = f (x)

заменяется некоторой более простой функцией

y = ϕ (x), для

которой и отыскивается корень (например, методы хорд,

Ньютона). Используют значения функции y =

сходимости у них выше.

f (x). Скорость

В общем случае задача решается в два этапа:

1) отделение корня, т.е. установление достаточно малого интервала (a, b), в котором содержится изолированный корень уравнения (1.1);

2) уточнение корня до заданной степени точности с помощью

одного из итерационных методов.

При решении серии систем НАТУ, к которым сводится решение какой-то более сложной задачи, необходимость в первом этапе зачастую отпадает, т.к. решение предыдущей системы является хорошим начальным приближением к решению последующей.

Для отделения корней при решении одного НАТУ

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

1. Физические явления, которые описываются уравнением (1.1).

2. Замена уравнения (1.1) более простым, имеющим корни, близкие к корням уранения (1.1).

3. Построение графика функции

y = f (x) и

приближенное определение точек, где кривая пересекает ось ОХ.

4. Запись уравнения (1.1) в виде

f 1(x) = f 2 (x) и

построение графиков двух функций

y = f 1(x) и

y = f 2 (x). Точка их пересечения есть корень

исходного уравнения.

Для отделения корней может быть использована теорема:

Если функция

y = f (x) непрерывна на интервале

(a, b) и

если

f (a) и

f (b) имеют противоположные знаки, т.е.

f (a) ⋅ f (b) < 0, то

f (x)

имеет по крайней мере один

действительный корень на интервале

(a, b). Если при этом

f (x) имеет первую производную, не меняющую знак, то корень единственный.

В соответствии с ней для отделения корней можно

вычислить значения функции в точках, расположенных через

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

На втором этапе происходит уточнение корня с помощью одного из итерационных методов, т.е. строится последовательность {xk}k=0, 1, … приближений к решению, причем можно использовать один из двух критериев окончания итерационного процесса:

1. f (xk) < ε,

2. xk − xk − 1< ε.

Возможно их одновременное использование.

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

Обозначим через

ek =

xk − x *

расстояние между очередным

приближением и точным решением. Очевидно, для

сходимости метода величина

e

ek +1

должна быть меньше, чем

ek, т.е. отношение

k +1 должно быть меньше единицы. Чем

ek

меньше это отношение, тем выше скорость сходимости. Если

предположить, что расстояния

ek < 1, то можно для каждого

метода подобрать такую константу

p, что

lim

k → ∞

ek +1

(ek) p

= C,

где

C -константа, отличная от нуля и бесконечности.

Величина p

и называется порядком метода. Рассмотрим

некоторые итерационные методы.

Метод половинного деления (бисекции)

Метод применяется, если

f(x)

непрерывна на отрезке

[a, b] и

f(a) ⋅ f(b) < 0. Суть метода заключается в следующем

(рис.1.2). Делим отрезок

[a, b], на котором имеется корень

уравнения (1.1), пополам, и если

f(a + b) > е, то выбираем

2

ту из половин

[a, a + b ]

2

или

[ a + b, b], на концах которой

2

f(x)

[a, b]

имеет противоположные знаки; новый суженый отрезок

снова делим пополам и так до тех пор, пока не получим

корень уравнения с заданной точностью.

Рис. 1.2. Метод половинного деления

Метод половинного деления надежен и его практически

удобно применять для грубого нахождения корня уравнения, так как с увеличением точности возрастает объем выполняемой работы из-за медленной сходимости итерационного процесса (порядок метода равен 1).

Вычислительная схема метода состоит в следующем. До начала вычислений задаем: ε – точность, с которой нужно

получить корень уравнения; a, b - отрезок, содержащий корень. Затем для каждого шага процесса:

1. Вычисляем координату середины отрезка и значение функции в ней:

x = a + b

с 2

, yс=f(xс);

2. Проверяем неравенство

yс < е. Если оно выполняется,

то xc

считаем корнем уравнения и выходим из цикла.

Если неравенство не выполняется, определяем, какую из двух половин взять для следующей итерации (в п.3).

3. Если

f(a) ⋅ yc > 0, полагаем

a = xc

, иначе полагаем

b = xc. Переход на п.1.

Ниже приведен соответствующий фрагмент программы.

...

yc: =1;

while abs(yc)> eps do begin

end;

xc: =(a+b)/2; yc: =f(xc); writeln(xc, yc)

if f(a)* yc > 0 then a: =xc else b: = xc;