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

Всякое значение

ξ ,

обращающее

функцию f (x )

называется корнем

уравнения

функции f (x ) .

Число ξ

называется корнем k-й кратности,

если при x = ξ вместе с функцией

f (x)

равны нулю и ее производные до порядка (k-1) включительно:

(k − 1)

Однократный корень называется простым . Два уравнения называются равносильными (эквивалентными), если множества их решений совпадают.

Нелинейные уравнения с одной переменной подразделяются на алгебраические (функция f (x ) является алгебраической) и трансцендентные в противном случае. Уже на примере алгебраического многочлена известно, что нули f (x ) могут быть как действительными, так и комплексными. Поэтому более точная постановка задачи состоит в нахождении корней уравнения (6.1), расположенных в заданной области комплексной плоскости. Можно рассматривать также задачу нахождения действительных корней, расположенных на заданном отрезке. Иногда, пренебрегая точностью формулировок, просто говорят, что требуется решить уравнение (6.1). Большинство алгебраических и трансцендентных нелинейных уравнений аналитически (т.е. точно) не решается, поэтому на практике для нахождения корней используются численные методы. В связи с этим под решением уравнения (6.1) будем понимать задачу приближенного нахождения корней

уравнения вида (6.1). При этом под близостью приближенного значения x к корню ξ уравнения, как правило, понимают выполнение неравенства

| ξ − x | < ε при малых ε > 0 ,

т.е. абсолютную погрешность приближенного равенства x ≈ ξ .

Используют также и относительную погрешность, т.е. величину | ξ − x | .

Нелинейная функция f (x ) в своей области определения может иметь конечное или бесконечное количество нулей или может не иметь их вовсе.

Численное решение нелинейного уравнения (6.1) заключается в нахождении с заданной точностью значений всех или некоторых корней уравнения и распадается на несколько подзадач:

во-первых, надо исследовать количество и характер корней (вещественные или комплексные, простые или кратные),

во-вторых, определить их приближенное расположение, т.е. значения начала и конца отрезка, на котором лежит только один корень,

в-третьих, выбрать интересующие нас корни и вычислить их с требуемой точностью.

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

6.1. Отделение корней нелинейного уравнения

Для функций общего вида нет универсальных способов решения задачи отделения корней. Отметим два простых приема отделения действительных корней уравнения – табличный и графический .

Первый прием состоит в вычислении таблицы значений функции в заданных точках x i , расположенных на условно небольшом расстоянии h одна от другой и использовании следующих теорем математического анализа:

1. Если функция y=f(x) непрерывна на отрезке [а,b] и f(a)f(b)<0, то внутри отрезка существует по крайней мере один корень уравнения f(x)=0.

2. Если функция y=f(x) непрерывна на отрезке [а,b], f(a)f(b) < 0 и f′(x) на интервале (a,b) сохраняет знак, то внутри отрезка существует единственный корень уравнения f(x)=0.

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

выполняется ли на отрезке [ x i − 1 , x i ] условие f (x i − 1 ) f (x i ) ≤ 0 . Таким образом, если при некотором i числа f (x i − 1 ) и f (x i ) имеют разные знаки, то это означает, что на интервале (x i − 1 , x i ) уравнение имеет по крайней мере

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

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

По таблице можно построить график функции y = f (x ) . Корнями

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

Если построение графика функции y = f (x ) вызывает затруднение, следует преобразовать исходное уравнение к виду ϕ 1 (x ) = ϕ 2 (x ) таким образом, чтобы графики функций y = ϕ 1 (x ) и y = ϕ 2 (x ) были достаточно

просты. Абсциссы точек пересечения этих графиков и будут корнями уравнения.

Пример: Отделить корни уравнения x 2 − sin x − 1 = 0 .
Представим уравнение в виде:	x 2 − 1= sin x						и построим графики
				2 −		y = sin x
Совместное				рассмотрение					графиков
позволяет сделать заключение, что данное
уравнение									ξ 1 [− 1,0] и

ξ 2 .

Допустим, что искомый корень уравнения отделен, т.е. найден отрезок , на котором имеется только один корень уравнения. Для вычисления корня с требуемой точностью ε обычно применяют какую-либо итерационную процедуру уточнения корня, строящую числовую последовательность значений x n , сходящуюся к искомому корню уравнения.

Начальное приближение x 0 выбирают на отрезке , продолжают

вычисления, пока не выполнится неравенство x n − 1 − x n < ε , и считают, что x n – есть корень уравнения, найденный с заданной точностью. Имеется

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

Последовательность x

Сходящаяся

к пределу

x * ,

скорость

сходимости порядка α , если при n → ∞

− x *

− x *

n + 1

α =1 сходимость называется линейной, при 1<α <2 – сверхлинейной, при α =2 – квадратичной. С ростом α алгоритм, как правило, усложняется и условия сходимости становятся более жесткими.

Приближённые значения корней уточняют различными итерационными методами. Рассмотрим наиболее эффективные из них.

6.2. Метод половинного деления (бисекции, дихотомии)

Пусть функция f (x ) определена и непрерывна при всех x [ a , b ] и на меняет знак, т.е. f (a ) f (b ) < 0 . Тогда согласно теореме 1 уравнение имеет на (a , b ) хотя бы один корень. Возьмем произвольную точку c (a , b ) . Будем называть в этом случае отрезок промежутком

существования, корня, а точку c - пробной точкой. Поскольку речь здесь идет лишь о вещественных функциях вещественной переменной, то

вычисление значения f (c ) приведет к какой-либо одной из следующих

взаимоисключающих ситуаций:

А) f (a ) f (c ) < 0 Б) f (c ) f (b ) < 0 В) f (c ) = 0

Если f (c ) = 0 , то корень уравнения найден. В противном случае из двух частей отрезка [ a , c ] или [ c , b ] выберем ту, на концах которой функция имеет разные знаки, так как один из корней лежит на этой половине.

Затем повторяем процесс для выбранного отрезка.
								называют
					дихотомии. Наиболее употребительным
								метода дихотомии
		c(a1 )			является	метод половинного			деления,
					реализующий		самый простой способ
			b(b1 )
					выбора пробной точки – деление
					промежутка		существования
Рис. 6.1. Метод дихотомии

За один шаг метода половинного деления промежуток существования корня сокращается ровно вдвое. Поэтому, если за k -е приближение к корню ξ уравнения примем точку x k , являющуюся серединой полученного на k -м шаге отрезка [ a k , b k ] , полагая a 0 = a , b 0 = b , то придем к неравенству

ξ−	k < b − a

которое, с одной стороны, позволяет утверждать, что последовательность (x k ) имеет предел – искомый корень ξ уравнения (6.1), с другой стороны, является априорной оценкой абсолютной погрешности равенства x k ≈ ξ , что дает возможность подсчитать число шагов (итераций) метода половинного деления, достаточное для получения корня ξ с заданной точностью ε .Для

чего нужно лишь найти наименьшее натуральное k удовлетворяющее неравенству

b 2 − k a < ε .

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

Дихотомия проста и очень надёжна: к простому корню она сходится для любых непрерывных функций f (x ) , в том числе недифференцируемых;

при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т.е. уточнение трёх цифр требует 10 итераций. Зато точность ответа гарантируется.

К основным недостаткам метода дихотомии можно отнести следующие.

1. Для начала расчёта необходимо найти отрезок, на котором функция изменяет знак. Если в этом отрезке несколько корней, то заранее неизвестно, к какому из них сойдётся процесс (хотя к одному из них обязательно сойдётся).

2. Метод неприменим к корням чётной кратности.

3. Для корней нечётной высокой кратности он сходится, но менее точен и менее устойчив к ошибкам округления, возникающим при вычислении значений функции.

Дихотомия применяется тогда, когда требуется высокая надёжность счёта, а скорость сходимости малосущественна.

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

Если x 1 есть простой корень уравнения и f (x ) липшиц-непрерывна, то вспомогательная функция g (x ) = f (x ) /(x − x 1 ) непрерывна, причём все нули функций f(x) и g(x) совпадают, за исключением x 1 , так как g (x 1 ) ≠ 0. Если x 1 - кратный корень уравнения, то он будет нулём g(x) кратности на единицу

меньше; остальные нули обеих функций по-прежнему будут одинаковы. Поэтому найденный корень можно удалить, т.е. перейти к функции

g(x) . Тогда отыскание остальных нулей				f (x ) сведётся к отысканию нулей
g(x) . Когда мы найдём какой-нибудь					x 2 функции g(x) ,
корень тоже можно	удалить, вводя				вспомогательную функцию
ϕ (x ) = g (x ) /(x − x 2 ).			последовательно			найти все
уравнения.
При использовании описанной процедуры необходимо учитывать
следующую тонкость. Строго говоря,				мы находим		лишь приближённое
значение корня x ≈ x .	А функция g (x )		F (x ) /(x − x 1 ) имеет нуль в точке x 1 и
полюс в близкой к ней точке
		x 1 (рис. 6.2); только на некотором расстоянии от

этого корня она близка к g(x ) . Чтобы это не сказывалось при нахождении следующих корней, нужно вычислять каждый корень с высокой точностью, особенно если он кратный или вблизи него расположен другой корень уравнения.

					g(x)	Кроме того, в любом методе
		g(x)				окончательные			итерации
						определяемого
		g(x)				выполнять не по функциям типа g(x) , а
			g(x)
						по исходной функции f (x ) . Последние
						итерации,		вычисленные
						g(x) , используются при этом в качестве
	Рис. 6.2. Иллюстрация возникновения
						нулевого		приближения.			Особенно
	погрешности в окрестности корня					важно это при отыскании многих
						корней, так как чем больше корней
							вспомогательной
					соответствуют остальным нулям функции						f (x) .
	G (x ) = f (x ) / ∏ (x − x i
		Учитывая эти предосторожности и вычисляя корни с 8 – 10 верными
	десятичными цифрами, зачастую можно определить десятка два корней, о
	расположении которых заранее ничего не известно (в том числе корней
	высокой кратности р 5).

6.3. Метод хорд

Логично предположить, что в семействе методов дихотомии можно достичь несколько лучших результатов, если отрезок делить точкой c не пополам, а пропорционально величинам ординат f (a ) и f (b ) .

Это означает, что точку c есть смысл находить, как абсциссу точки пересечения

оси Ох с прямой, проходящей через точки A (a , f (a )) и B (b , f (b )) , иначе, с хордой

дуги графика функции f (x ) . Такой способ

выбора пробной точки, называют методом хорд или методом линейной интерполяции .

Запишем уравнение прямой проходящей через точки А и В :

			y− f (a)		x− a
			f (b) − f (a)		b− a
и, полагая y = 0, находим:
	f (a)(b− a)
c = a − f (b) − f (a)

Метод хорд подобно алгоритму метода бисекции строит последовательность вложенных отрезков [а n ,b n ], но в качестве x n берется точка пересечения хорды с осью абсцисс :

	n+ 1				f (an )		− a
					f (bn ) − f (an )

Длина промежутка локализации корня при этом может не стремится к нулю, поэтому обычно счет ведется до совпадения значений двух очередных приближений с точностью ε . Метод сходится линейно, но близость двух очередных приближений не всегда означает, что корень найден с требуемой точностью. Поэтому, если 0 < m ≤ | f ′ (x )| ≤ M , x [ a , b ] ,

M − m

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

				− x	n− 1			< ε.
		2 x n− 1 − x n − x n− 2
6.4. Метод простой итерации
Заменим уравнение f (x ) = 0 эквивалентным ему уравнением
				x = ϕ (x ) .

сходилась к корню данного уравнения

знакопостоянная функция. Выберем некоторое нулевое приближение х 0 и вычислим дальнейшие приближения по формулам

x k + 1 = ϕ (x k ) , k = 0,1,2,..

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

требованиям должна удовлетворять функция ϕ (x ) , чтобы последовательность (x k ) , определяемая (6.7) была сходящаяся, и как

построить функцию ϕ (x ) по функции f (x ) , чтобы эта последовательность

f (x) = 0 .

Пусть ϕ (x ) - непрерывная на некотором отрезке [ a , b ] функция. Если определяемая формулой (6.7) последовательность (x k ) сходится к

некоторому числу ξ , т.е. ξ = lim x k , то, переходя к пределу в равенстве

k →∞

(6.7), получаем ξ = ϕ (ξ ) . Это равенство означает, что ξ - корень

уравнения (6.6) и эквивалентного ему исходного уравнения.

Нахождение корня уравнения (6.6) называется задачей о неподвижной точке. Существование и единственность этого корня основывается на принципе сжимающих отображений.

Определение: Непрерывная функция ϕ (x ) называется сжимающей на отрезке [ a , b ] если:

1) ϕ (x ) , x

2) q (0,1) : |ϕ (x 2 )− ϕ (x 1 )|≤ q |x 2 − x 1 |, x 1 ,x 2 .

Второе условие для дифференцируемой на [ a , b ] функции равносильно выполнению неравенства ϕ " (x ) ≤ q < 1 на этом отрезке.

Метод простых итераций имеет простую геометрическую интерпретацию: нахождение корня уравнения f(x)=0 равносильно обнаружению неподвижной точки функции x= ϕ (x) , т.е. точки пересечения

графиков функций y= ϕ (x) и y=x . Метод простой итерации не всегда обеспечивает сходимость к корню уравнения. Достаточным условием сходимости этого метода является выполнение неравенства ϕ " (x ) ≤ q < 1 на

Проиллюстрируем (рис. 6.4) геометрически поведение сходящейся итерационной последовательности (x k ) , не отмечая значения ϕ (x k ) , а

отражая их на ось абсцисс с помощью биссектрисы координатного угла

y= x .

Рис.6.4 Сходимость метода простой итерации при ϕ " (x ) ≤ q < 1 .

Как видно из рис. 6.4, если производная ϕ ′ (x ) < 0 , то последовательные приближения колеблются около корня, если же производная ϕ ′ (x ) > 0 , то

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

Теорема: Пусть ϕ (x ) определена и дифференцируема на [ a , b ] . Тогда, если выполняются условия:

1) ϕ
	(x )	x [ a, b]

x (a, b)

2) q : |ϕ (x )|≤ q < 1

3) 0

x [ a, b]

то уравнение x = ϕ (x ) имеет на [ a , b ] единственный корень ξ и к этому

корню сходится определяемая методом простых итераций

последовательность (x k ) , начинающаяся с x 0 [ a , b ] .

При этом справедливы следующие оценки погрешности:

k − 1

|ξ − x |≤ 1 − q |x

−x

ξ − x k

1 − q

x 1 − x 0

если ϕ (x ) > 0

ξ − x k

− x k − 1

если ϕ (x ) < 0

Вблизи корня итерации сходятся примерно как геометрическая прогрессия со

				x k − x k − 1
	знаменателем					Метод имеет линейную скорость
				x k − 1 − x k − 2
	сходимости. Очевидно, что чем меньше						q (0,1)	Тем быстрее сходимость.
		образом, успех						от того, насколько удачно

выбрано ϕ (x ) .

Например, для извлечения квадратного корня, т.е. для решения

уравненияx 2 = a , можно положить ϕ (x ) = a / x

или ϕ

(x ) = 1/ 2

и соответственно написать такие итерационные процессы:

x k + 1 =

x k + 1

	Первый процесс вообще не сходится, а второй сходится при любом х 0 > 0 и
	сходится очень быстро, так как ϕ "(ξ ) = 0					Второй процесс используется при
	извлечении корня в "запаянных" командах микрокалькуляторов.
	Пример 1: Найти методом итерации с точностью ε =								10− 4 наименьший
	корень уравнения
					f (x )= x 3 + 3x 2 − 1= 0 .
	Решение : Отделяем корни:
		−4	−3	−2	− 1 0
	f (x)

Очевидно, уравнение имеет три корня, расположенные на отрезках [ − 3; − 2] , [− 1;0] и . Наименьший находится на отрезке [ − 3; − 2] .

Т.к. на этом отрезке x 2 ≠ 0 , разделим уравнение на x 2 . Получим:

x +3 −

= 0 => x =

−3

x2

x2

|ϕ

−2 x

−3

1 , т.е.

q=

(x )|=

−3 ≤ x ≤ −2

−3 ≤ x ≤ −2

Пусть x 0

=− 2.5 , тогда δ

= max[− 3− x 0 ;− 2 − x 0 ] = 0.5

x = ϕ (− 2.5) =

−3

=− 2.84 [− 3,− 2]

обозначим

Проверим выполнение условия теоремы:

ϕ (x )= x 2 − 3

(− 2.5)2

|ϕ (x 0)− x 0|= 0.34< (1− q )

0 −

1 −

(x )

q n ≤ ε =>

2 10

=> n ≥ 6

1− q

3 4n

xn

ϕ (x n )=

−3

x2

− 2.50000

− 2.84000

− 2.84000

− 2.87602

− 2.87602

− 2.87910

− 2.87910

− 2.87936

− 2.87936

− 2.87938

− 2.87938

− 2.87938

Замечание: Для нахождения двух других корней исходного уравнения методом простой итерации уже нельзя пользоваться формулой: x = x 1 2 − 3 ,

−2 x

−3

=−∞,

−2 x

−3

max | ϕ (x )| =

−1 ≤ x ≤ 0

−1 ≤ x ≤ 0

−1 ≤x ≤0

Условие сходимости на этих отрезках не выполнено.

Метод релаксации - один из вариантов метода простой итерации, в котором

ϕ (x) = x − τ f (x) ,

т.е. равносильное уравнение имеет вид:

x = x − τ f (x) .

Приближения к корню вычисляются по формулам
xn + 1 = xn − τ f (xn ),
Если f (x ) < 0 , то рассматривают уравнение − f (x ) = 0 .

функции f (x ) . Пусть

0 ≤α ≤ f ′(x ) ≤γ <∞

Параметр τ подбирается таким, чтобы производная ϕ ′ (x ) = 1 − τ f ′ (x ) в нужной области была малой по модулю.

1 − τ γ ≤ ϕ′ (x ) ≤ 1 − λα

и значит,

|ϕ ′ (x )|≤ q (τ ) = max{|1− τα |,|1− τγ |}

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

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

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

Затем для реализации выбранного вычислительного метода составляется алгоритм и программа для ЭВМ. Современному инженеру важно уметь преобразовать задачу к виду, удобному для реализации на ЭВМ и построить алгоритм решения такой задачи.

В настоящее время широко используются как пакеты, реализующие наиболее общие методы решения широкого круга задач (например, Mathcad ,
MatLAB), так и пакеты, реализующие методы решения специальных задач.

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

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

Пусть дана некоторая функция и требуется найти все или некоторые значения , для которых .

Значение , при котором , называется корнем (или решением ) уравнения. Относительно функции часто предполагается, что дважды непрерывно дифференцируема в окрестности корня.

Корень уравнения называется простым, если первая производная функции в точке не равна нулю, т. е. . Если же , то корень называется кратным корнем.

Геометрически корень уравнения есть точка пересечения графика функции с осью абсцисс. На рис. 1 изображен график функции , имеющей четыре корня: два простых и два кратных .

Большинство методов решения уравнения ориентировано на отыскание простых корней.

1.2. Основные этапы отыскания решения

В процессе приближенного отыскания корней уравнения обычно выделяют два этапа: локализация (или отделение) корня и уточнение корня .

Локализация корня заключается в определении отрезка , содержащего один и только один корень. Не существует универсального алгоритма локализации корня. Иногда удобно бывает локализовать корень с помощью построения графика или таблицы значений функции . На наличие корня на отрезке указывает различие знаков функции на концах отрезка. Основанием для этого служит следующая теорема.

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

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

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

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

Разделим отрезок пополам. Получим точку . Вычислим значение функции в этой точке: . Если , то - искомый корень, и задача решена. Если , то - число определённого знака: либо . Тогда либо на концах отрезка , либо на концах отрезка значения функции имеют разные знаки. Обозначим такой отрезок . Очевидно, что и длина отрезка в два раза меньше, чем длина отрезка . Поступим аналогично с отрезком . В результате получим либо корень , либо новый отрезок и т. д. (рис. 2).

Середина -го отрезка . Очевидно, что длина отрезка будет равна , а так как , то

Критерий окончания. Из соотношения (1) следует, что при заданной точности приближения вычисления заканчиваются, когда будет выполнено неравенство или неравенство . Таким образом, количество итераций можно определить заранее. За приближенное значение корня берется величина .

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

Следовательно, не позднее 6-го деления найдем с требуемой точностью, . Результаты вычислений представлены в таблице 1.

Таблица 1

	1,0000	1,0000	1,0000	1,1250	1,1250	1,1406	1,1406
	2,0000	1,5000	1,2500	1,2500	1,1875	1,1875	1,1562
	1,5000	1,2500	1,1250	1,1875	1,1406	1,1562	1,1484
Зн	-	-	-	-	-	-	-
Зн	+	+	+	+	+	+	+
	5,5938	0,7585	-0,2959	0,1812	-0,0691	0,0532	-0,0078
-	1,0000	0,5000	0,2500	0,1250	0,0625	0,0312	0,0156

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

Пусть уравнение можно заменить эквивалентным ему уравнением

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

Формула (3) является расчетной формулой метода простой итерации.

Если последовательность сходится при , т. е. существует

и функция непрерывна, то, переходя к пределу в (3) и учитывая (4), получим: .

Таким образом, , следовательно, - корень уравнения (2).

Сходимость метода. Сходимость метода простой итерации устанавливает следующая теорема.

Теорема. Пусть функция определена и диффе-ренцируема на отрезке , причем все ее зна-чения . Тогда, если выполняется условие при :

1) процесс итерации сходится независимо от начального значения ;

2) предельное значение является единственным корнем уравнения на отрезке .

Доказательство. Так как и , то можно записать

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

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

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

Отсюда следует, что должно быть меньше единицы. В свою очередь, для всех остальных значений меньших , можно записать: . Число определим из соотношения . Тогда справедливо неравенство (вывод см. ниже): . Если поставить условие, что истинное значение корня должно отличаться от приближенного значения на величину , т.е. , то приближения надо вычислять до тех пор, пока не будет выполнено неравенство

или и тогда .

Вывод неравенства.Рассмотрим два последовательных приближения: и . Отсюда .

Используя теорему о среднем, получим:

тогда на основании условия можно записать:

С другой стороны, пусть . Очевидно, что . Отсюда, учитывая, что , получим

Тогда или .

Используя предыдущую формулу, можно получить:

Перейдём к пределу в равенстве (3), в силу непрерывности функции получим , то есть - корень уравнения (2). Других корней на нет, так как если , то , тогда , где . Равенство нулю будет достигнуто, если . То есть - корень единственный.

Теорема доказана.

Приведение уравнения к виду
для обеспечения выполнения неравенства

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

Это соотношение определяет диапазон значений коэффициента , изменяющий величину в пределах .

Обычно принимают .

На рис. 3-6 показаны четыре случая взаимного расположения линий и и соответствующие итерационные процессы. Рис. 3 и 4 соответствуют случаю , и итерационный процесс сходится. При этом, если (рис. 3), сходимость носит односторонний характер, а если (рис. 4), сходимость носит двусторонний, колебательный характер. Рис. 5 и 6 соответствуют случаю - итерационный процесс расходится. При этом может быть односторонняя (рис. 5) и двусторонняя (рис. 6) расходимость.

Погрешность метода. Оценка погрешности была доказана (5).

Критерий окончания. Из оценки (5) следует, что вычисления надо продолжать до выполнения неравенство . Если же , то оценка упрощается: .

Пример 1. Используем метод простой итерации для решения уравнения с точностью . Преобразуем уравнение к виду:

, т. е. .

Нетрудно убедиться, что корень уравнения находится на отрезке . Вычислив значения на концах отрезка, получим: , а , т. е. функция на концах отрезка имеет разные знаки,

поэтому внутри отрезка есть корень. Расположение корня наглядно иллюстрирует рис. 7.

Подсчитаем первую и вторую производные функции :

Так как на отрезке , то производная монотонно возрастает на этом отрезке и принимает максимальное значение на правом конце отрезка, т. е. в точке . Поэтому справедлива оценка:

Таким образом, условие выполнено, и можно воспользоваться критерием окончания вычислений. В табл. 2 приведены приближения, полученные по расчетной формуле. В качестве начального приближения выбрано значение .

Таблица 2

		0,8415	0,8861	0,8712	0,8774	0,8765

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

Пример 2. Решить методом простой итерации уравнение на отрезке с точностью 0,025. Для решения исходное уравнение приводится к виду . Для выбора величины используем приведенную выше формулу . Тогда расчетная формула имеет вид . В качестве начального приближения можно выбрать верхнюю границу заданного отрезка .

		0,8	0,78

Так как , то .

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

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

Уравнение касательной будет иметь вид: .

Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью , т. е. положив : .

Аналогично поступим с точкой , затем с точкой и т. д., в результате получим последовательность приближений , причем

Формула (6) является расчетной формулой метода Ньютона .

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

Сходимость метода . Сходимость метода Ньютона устанавливает следующая теорема.

Теорема. Пусть - простой корень уравнения и в некоторой окрестности этого корня функция дважды непрерывно дифференцируема. Тогда найдется такая малая - окрестность корня , что при произвольном выборе начального приближения из этой окрестности итерационная последовательность, определенная по формуле (6) не выходит за пределы этой окрестности и справедлива оценка:

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

Выбор начального приближения. Пусть - отрезок, содержащий корень. Если в качестве начального приближения выбрать тот из концов отрезка, для которого , то итерации (6) сходятся, причем монотонно. Рис. 8 соответствует случаю, когда в качестве начального приближения был выбран правый конец отрезка: (Здесь ).

Погрешность метода. Оценка (7) неудобна для практического использования. На практике пользуются следующие оценки погрешности:

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

Пример . Вычислить методом Ньютона отрицательный корень уравнения с точностью до 0,0001. Проведя отделение корня, можно убедиться, что корень локализован на интервале . В этом интервале и . Так как и , то за начальное приближение можно принять .

-11		-5183	0,6662
-10,3336	307,3	4276,8	0,0718
-10,2618	3,496	4185,9	0,0008
-10,261	0,1477	-	-

. Поэтому . Итак, в результате получаем следующее, и на , поэтому .

Так как , то

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

§ 4.1. Постановка задачи. Основные этапы решения

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

Задача отыскания корней нелинейного уравнения с одним неизвестным вида

имеет многовековую историю, но не потеряла свою актуальность и в наши дни. Она часто возникает как элементарный шаг при решении различных научных и технических проблем. Напомним, что корнем (или решением) уравнения (4.1) называется значение х, при котором

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

Корень х уравнения (4.1) называется простым, если противном случае (т. е. в случае корень х называется кратным. Целое число назовем кратностью корня х, если для Геометрически корень х соответствует точке пересечения графика функции с осью Корень х является простым, если график пересекает ось под ненулевым углом, и кратным, если пересечение происходит под нулевым углом. Функция график который изображен на рис. 4.1, имеет четыре корня. Корни простые, кратные.

Задача отыскания простых корней является существенно более простой (и чаще встречающейся), чем задача отыскания кратных корней. В действительности большинство методов решения уравнения (4.1) ориентировано именно на вычисление простых корней.

2. Уточнение постановки задачи.

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

В подавляющем большинстве случаев представить решение уравнения (4.1) в виде конечной формулы оказывается невозможным. Даже для простейшего алгебраического уравнения степени

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

уравнений пятой и более высоких степеней таких формул не существует. Этот замечательный факт, известный как теорема Абеля, был установлен в 30-е годы XIX в. Н. Абелем и Э. Галуа.

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

Пример 4.1. Предположим, что исследование некоторого явления привело к необходимости решить уравнение

Воспользовавшись формулами (3.2) для корней квадратного уравнения, получим значения Найдены ли нами точные значения параметра Очевидно, нет. Скорее всего коэффициенты уравнения (4.3) известны приближенно и в лучшем случае они представляют округленные значения "истинных" коэффициентов. В действительности можно лишь утверждать, что

Предположим теперь, что "истинный" вид уравнения (4.3) таков: Тогда точные значения параметра можно вычислить по формуле Однако она лишь указывает на то, какие операции и в каком порядке следует выполнить. В данном случае точное вычисление по формуле невозможно, так как она содержит операцию извлечения квадратного корня. Вычисленные по ней значения неизбежно окажутся приближенными.

В дальнейшем мы откажемся от попыток найти точные значения корней уравнения (4.1) и сосредоточим внимание на методах решения более реалистичной задачи приближенного вычисления корней с заданной точностью

В данной главе под задачей отыскания решений уравнения (4.1) будем понимать задачу вычисления с заданной точностью конечного числа подлежащих определению корней этого уравнения.

3. Основные этапы решения.

Решение задачи отыскания корней нелинейного уравнения осуществляют в два этапа. Первый этап называется этапом локализации (или отделения) корней, второй - этапом итерационного уточнения корней.

Локализация корней. Отрезок содержащий только один корень х уравнения (4.1), называют отрезком локализации корня х. Цель этапа локализации считают достигнутой, если для каждого из подлежащих определению корней удалось указать отрезок локализации (его длину стараются по возможности сделать минимальной).

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

Способы локализации корней многообразны, и указать универсальный метод не представляется возможным. Иногда отрезок локализации известен либо он определяется из физических соображений. В простых ситуациях хороший результат может давать графический метод (см. пример 4.2). Широко применяют построение таблиц значений функций вида При этом способе локализации о наличии на отрезке корня судят по перемене знака функции на концах отрезка (см. пример 4.3). Основанием для применения указанного способа служит следующая хорошо известная теорема математического анализа.

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

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

Дело в том, что в малой окрестности такого корня (например, корня на рис. 4.1) функция имеет постоянный знак.

Важно подчеркнуть, что далеко не всегда для успешного отыскания

корня х уравнения (4.1) необходимо полное решение задачи локализации. Часто вместо отрезка локализации достаточно найти хорошее начальное приближение к корню х. Пример 4.2. Локализуем корни уравнения

Для этого преобразуем уравнение к виду и построим графики функций (рис. 4.2). Абсциссы точек пересечения этих графиков являются корнями данного уравнения. Из рис. 4.2 видно, что уравнение имеет два корня и расположенные на отрезках и . Убедимся, что функция принимает на концах указанных отрезков значения разных знаков. Действительно, Следовательно, в силу теоремы 4.1 на каждом из отрезков и находится по крайней мере один корень.

Пример 4.3. Локализуем корни уравнения

Для этого составим таблицу значений функции на отрезке с шагом 0.4.

Таблица 4.1 (см. скан)

Из табл. 4.1 видно, что функция меняет знак на концах отрезков Теорема 4.1 дает основание утверждать, что каждый из этих отрезков содержит по крайней мере один корень. Учитывая, что в силу основной теоремы алгебры многочлен третьей степени не может иметь более трех корней, заключаем, что полученные три отрезка содержат ровно по одному корню. Таким образом, корни локализованы.

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

Общее представление об итерационных методах и основные определения были даны в § 3.3. Введем дополнительно некоторые определения.

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

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

Как нетрудно видеть, из оценки (4.5) действительно вытекает сходимость метода.

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

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

Решение нелинейных уравнений

Пусть требуется решить уравнение

Где
– нелинейная непрерывная функция.

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

Полное решение поставленной задачи можно разделить на 3 этапа:

Установить количество, характер и расположение корней уравнения (1).

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

Найти значение корней с требуемой точностью (уточнить корни).

Существуют различные графические и аналитические методы решения первых двух задач.

Наиболее наглядный метод отделения корней уравнения (1) состоит в определении координат точек пересечения графика функции
с осью абсцисс. Абсциссы точек пересечения графика
с осью
являются корнями уравнения (1)

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

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

Если функция
удовлетворяет условиям теоремы Больцано-Коши и монотонна на этом отрезке, то на
существует только один корень уравнения (1).Таким образом, уравнение (1) имеет на
единственный корень, если выполняются условия:

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

Полезным средством для отделения корней является также использование теоремы Штурма.

Решение третьей задачи осуществляется различными итерационными (численными) методами: методом дихотомии, методом простой итерации, методом Ньютона, методом хорд и т.д.

Пример Решим уравнение
методом простой итерации . Зададим
. Построим график функции.

На графике видно, что корень нашего уравнения принадлежит отрезку
, т.е.
– отрезок изоляции корня нашего уравнения. Проверим это аналитически, т.е. выполнение условий (2):

Напомним, что исходное уравнение (1) в методе простой итерации преобразуется к виду
и итерации осуществляются по формуле:

(3)

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

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

На практике часто выражают
непосредственно из уравнения (1). Если не выполняется условие сходимости, преобразуют его к виду (3) и подбирают. Представим наше уравнение в виде
(выразим x из уравнения). Проверим условие сходимости метода:

для
. Обратите внимание, что условие сходимости выполняется не
, поэтому мы и берем отрезок изоляции корня
. Попутно заметим, что при представлении нашего уравнения в виде
, не выполняется условие сходимости метода:
на отрезке
. На графике видно, что
возрастает быстрее, чем функция
­­ (|tg| угла наклона касательной к
на отрезке
)

Выберем
. Организуем итерации по формуле:

Программно организуем процесс итераций с заданной точностью:

> fv:=proc(f1,x0,eps)

> k:=0:

x:=x1+1:

while abs(x1-x)> eps do

x1:=f1(x):

print(evalf(x1,8)):

print(abs(x1-x)):

:printf("Кол. итер.=%d ",k):

end :

На 19 итерации мы получили корень нашего уравнения

c абсолютной погрешностью

Решим наше уравнение методом Ньютона . Итерации в методе Ньютона осуществляются по формуле:

Метод Ньютона можно рассматривать как метод простой итерации с функцией, тогда условие сходимости метода Ньютона запишется в виде:

.

В нашем обозначении
и условие сходимости выполняется на отрезке
, что видно на графике:

Напомним, что метод Ньютона сходится с квадратичной скоростью и начальное приближение должно быть выбрано достаточно близко к корню. Произведем вычисления:
, начальное приближение, . Организуем итерации по формуле:

Программно организуем процесс итераций с заданной точностью. На 4 итерации получим корень уравнения

с
Мы рассмотрели методы решения нелинейных уравнений на примере кубических уравнений, естественно, этими методами решаются различные виды нелинейных уравнений. Например, решая уравнение

методом Ньютона с
, находим корень уравнения на [-1,5;-1]:

Задание : Решить нелинейные уравнения с точностью

0.

деления отрезка пополам (дихотомии)

простой итерации.

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

секущих – хорд.

Варианты заданий рассчитываются следующим образом: номер по списку делится на 5 (
), целая часть соответствует номеру уравнения, остаток – номеру метода.

Общий вид нелинейного уравнения

f (x )=0, (6.1)

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

По виду функции f (x ) нелинейные уравнения можно разделить на два класса:

Алгебраические;

Трансцендентные.

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

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

Решить нелинейное уравнение – значит найти его корни или корень.

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

6.2. Методы решения

Методы решения нелинейных уравнений делятся на:

Итерационные.

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

Однако, встречающиеся на практике уравнения, не удается решить такими простыми методами, потому что

Вид функции f (x ) может быть достаточно сложным;

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

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

отделение корня , а именно, определение приближенного значения корня или отрезка, который содержит один и только один корень.

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

На первом этапе приближенное значение корня (начальное приближение ) может быть найдено различными способами:

Из физических соображений;

Из решения аналогичной задачи;

Из других исходных данных;

Графическим методом.

Более подробно рассмотрим последний способ. Действительный корень уравнения

f(x) =0

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

f 1 (x)=f 2 (x)

где f 1 (x ) и f 2 (x ) – более простые, чем f (x ) . Тогда, построив графики функций f 1 (x ) и f 2 (x ), искомый корень (корни) получим как абсциссу точки пересечения этих графиков.

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

Если такие априорные оценки исходного приближения провести не удается, то находят две близко расположенные точки a , b , между которыми функция имеет один и только один корень. Для этого действия полезно помнить две теоремы.

Теорема 1. Если непрерывная функция f (x ) принимает значения разных знаков на концах отрезка [a , b ], то есть

f (a ) f (b )<0, (6.2)

то внутри этого отрезка находится, по меньшей мере, один корень уравнения.

Теорема 2. Корень уравнения на отрезке [a , b ] будет единственным, если первая производная функции f ’(x ), существует и сохраняет постоянный знак внутри отрезка, то есть

(6.3)

Выбор отрезка [a , b ] выполняется

Графически;

Аналитически (путем исследования функции f (x ) или путем подбора).

На втором этапе находят последовательность приближенных значений корня х 1 , х 2 , … , х n . Каждый шаг вычисления x i называется итерацией . Если x i с увеличением n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится.