Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Нижегородский Государственный Технический Университет им. Р.Е. Алексеева

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Учебное пособие_Численные методы -26 -дек_2014 (97-2003)

.pdf

Скачиваний:

336

Добавлен:

11.03.2016

Размер:

7 Мб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 78 / 298 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

2) уточнение приближенных корней, то есть доведение их до

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

этого отрезка содержится по меньшей мере один корень уравнения f(х)=0, т. е. найдется хотя бы одно число x0, а<х0<b, такое, что f(x0)=0.

Корень x0 будет единственным, если производная	f (x) существует и

сохраняет постоянный знак внутри интервала (а, b).

Процесс отделения корней начинается с установления знаков

функции	f (x)	в граничных	точках a и b её существования. Затем
определяются знаки функции			f (x)	в ряде промежуточных точек x a1 , a2 …
Если окажется, что f (ak ) f (ak 1 ) 0				, то в силу теоремы в интервале (аk, аk+1)
имеется корень уравнения f (x) 0.

3.2. Метод половинного деления (дихотомии)

Пусть дано уравнение (3.1), где функция

f (a) f (b) 0.

f (x)

непрерывна на

a, b

Для

нахождения

корня данного

уравнения (3.1),

принадлежащего

отрезку

a, b , делим

отрезок пополам.

Если

a b

то

a b

0, то выбираем ту из половин

является корнем уравнения. Если f

a b

на которой функция f (x)

имеет противоположные

или

, b ,

знаки.

Новый суженый отрезок a1 ,b1

снова делим пополам и проводим

тоже рассмотрение и т.д. В результате получаем на каком-то этапе или точный корень уравнения (3.1), или же бесконечную последовательность вложенных друг в друга отрезков a1 , b1 , a2 , b2 ,..., an , bn ,... таких, что

f (an ) f (bn ) 0

(n 1,2,...)

(3.2)

b	a	n
n		n

		1
		2	n

(3.3)

Так как левые концы a1 , a2 ,...an ,.... образуют монотонную

неубывающую		ограниченную последовательность, а правые концы
b1 , b2 ,...bn ,...		монотонную	невозрастающую	ограниченную

последовательность, то в силу неравенства (3.3) существует общий

предел ξ lim an limbn .

n n

Переходя к пределу при

непрерывности функции

f (x)

получим

является корнем уравнения (3.1), причем

0 ξ a		1		b
	n	2	n

в неравенство

f (ξ)	0.	Отсюда
2
очевидно, что
a .

(3.2), в

f (ξ) 0,

силу т.е. ξ

(3.4)

Если корни уравнения (3.1) не отделены на отрезке [a, b], то таким способом не найти один из корней уравнения (3.1).

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

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

Пусть корень уравнения
отделен на отрезке a, b ,		причем	f (x) 0		f (x)	(3.5)
			f (x)	и		непрерывны и сохраняют

определенные знаки при		a x b.	Найдя какое-нибудь n-е приближенное
значение корня	xn ξ (a xn b),		мы	можем		уточнить его по методу
Ньютона следующим образом. Положим

где

h	n

ξ x	n	h	n	,
	n		n

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

(3.6)

формулу Тейлора,

получим 0 f (xn hn ) f (xn ) hn f (xn ). Следовательно,

h		f (x	n		)	.
h						.

	n	f (x			)
		f (x		n	)
				n

Внеся эту поправку в формулу (3.2), приближение корня

x		x		f (x	n		)	(n
x		x						(n

	n 1		n	f (x			)
				f (x		n	)
						n

найдем следующее

0,1, 2,....)	.

(по порядку)

(3.7)

Геометрически метод Ньютона эквивалентен замене небольшой дуги

кривой y f (x) касательной,		проведенной в		некоторой точке кривой
(рис. 3.1). В самом деле,	положим для определенности, что f				(x) 0 при

a x b и f (b) 0.
Выберем, например,	x0 b, для		которого		Проведем
				f (x0 ) f (x0 ) 0.
касательную к кривой y f (x)		в точке	B0 x0 , f (x0 ) .

Рис. 3.1. Графическая интерпретация метода Ньютона

В качестве первого приближения x1	корня возьмем абсциссу точки
пересечения этой касательной с осью	Ox. Через точку B1 x1 , f (x1 ) снова

проведем касательную, абсцисса точки				пересечения которой дает нам
второе приближение	x2	корня и		т.д. Очевидно, что уравнение
касательной в точке Bn xn ,		f (xn ) (n 0,1,2,...)		есть
		y f (x	) f (x		)(x x	).
		n		n	n

Полагая

y 0, x x	n 1	,
	n 1

получим формулу (3.7)

x		x		f (x	n		)	.
x		x						.

	n 1		n	f (x			)
				f (x		n	)
						n

Заметим,	что если в нашем случае положить x0 a и, следовательно,
	то, проведя касательную к кривой y	f (x)	в точке A a, f (a) ,
f (x0 ) f (x0 ) 0,
мы получили бы точку x1 , лежащую вне отрезка		a,b ,	т.е. при выборе

начального значения метод Ньютона оказывается непрактичным. Таким

образом, в данном случае «хорошим» начальным				приближением x0
является то, для которого выполнено неравенство
				(3.8)
		f (x0 ) f (x0 ) 0.
Докажем, что это правило является общим.				отличны от нуля и
Теорема.	Если f (a) f (b) 0, причем f (x)		и f (x)

сохраняют определенные знаки на a x b,			то, исходя из начального
приближения	x0 a, b ,	удовлетворяющего	неравенству (3.8), можно

вычислить методом Ньютона (формула (3.7)) единственный корень уравнения (3.5) с любой точностью.

		Доказательство. Пусть,			например,	f (x) 0,		f (b) 0, f (x) 0, f (x) 0

при a x b			(остальные случаи рассматриваются аналогично). Согласно
неравенству (3.8), имеем f (x0 ) 0 (например, можно принять x0									b ).
		Методом математической индукции докажем, что все приближения
xn		ξ (n 0,1, 2...) и,		следовательно, f (xn ) 0.			В самом деле, прежде всего,
x	0	ξ.
	0
		Пусть	теперь	xn ξ.	Положим ξ xn		ξ xn .	Применяя	формулу

Тейлора, получим

где

0 f (ξ) f (x

) f (x

)(ξ x

)

)(ξ x

)

ξ c

Так как

f (x) 0,

то имеем f (xn )

xn ) 0

и, следовательно,

(xn )(ξ

f (x

)

n 1

)

(3.9)

Что и требовалось доказать.

	Из	формулы	(3.7),	учитывая знаки	f (xn )	и		(xn ),	имеем
							f
xn 1	xn	(n 0, 1, ...),	т.е.	последовательные	приближения			x0	, x1 ,..., xn ,...

образуют ограниченную монотонную убывающую последовательность.

Следовательно, существует	ξ lim x		n .
	ξ lim x
	x
Переходя к пределу в равенстве (3.7), будем иметь
		ξ ξ		f (ξ)	,
		ξ ξ		f (ξ)	,
				f (ξ)

т.е.

f (ξ) 0

. Отсюда ξ ξ , что и требовалось доказать.

Поэтому, применяя метод Ньютона, следует следующим правилом: в качестве исходной точки

конец интервала a,b , которому отвечает ордината

и знак	f
		(x).

	руководствоваться
x0	выбирается тот

того же знака, что

3.4. Метод итерации

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

f (x) 0,	(3.10)
где f (x) – непрерывная функция,	и требуется определить его

вещественные корни. Заменим уравнение (3.10) равносильным уравнением

x (x).	(3.11)
74

Выберем каким-либо грубо приближенное значение корня

подставим его в правую часть уравнения (3.11). Тогда получим некоторое число

x1 (x0 ).	(3.12)
Подставляя теперь в правую часть равенства (3.12) вместо x0	число x1

получим новое число x2 = (x1). Повторяя это процесс, будем иметь последовательность чисел

xn = (xn-1) (n = 1, 2,…).	(3.13)
Если эта последовательность – сходящаяся, т.е. существует	ξ lim xn	,
	n

то, переходя к пределу в равенстве (3.13) и предполагая функцию (x) непрерывной, найдем

lim xn	(lim xn 1 )
n	n
или
ξ (ξ) .		(3.14)

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

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

образом (рис. 3.2). Построим на плоскости	xOy графики функций y = x и
y = (x). Каждый действительный корень	уравнения (3.11) является
абсциссой точки пересечения M кривой y = (x) с прямой y = x.
Отправляясь от некоторой точки A0 x0 ;(x0 ) , строим ломаную линию

A0 B1 A1 B2 A2 ... «лестница», звенья которой попеременно параллельны оси Ox

и оси Oy, вершины A0	, A1 , A2 ... лежат на кривой y = (x) а вершины B0 , B1 , B2 ...
– на прямой y = x.	Общие абсциссы точек A1 и B1 , A2 , B2	,..., очевидно,
представляют собой	соответственно последовательные	приближения
x1 , x2 ,... корня .

Рис. 3.2. Графическая интерпретация метода итераций вида «лестница»

Возможен также другой вид ломаной

A B A B			2	A ...
0	1	1	2	2

«спираль». Легко

сообразить, что решение в виде «лестницы» получается, если производная ’(x) положительна, а решение в виде «спирали», если ’(x) отрицательна (рис. 3.3).

Рис. 3.3. Графическая интерпретация метода итераций вида «спираль»

На рисунке с «лестницей» кривая y = (x) в окрестности – пологая, т.е. | ’(x)|<1 и процесс сходится. Однако, если рассмотреть случай, где | ’(x)|>1, то процесс итерации может быть расходящимся. Поэтому для практического применения метода итерации нужно выяснить достаточные условия сходимости итерационного метода.

Теорема 1. Пусть функция (x) определена и дифференцируема на отрезке [a,b], причем все ее значения (x) [a,b]. Тогда, если существует правильная дробь q такая, что

	\| ’(x)\|≤ q<1	(3.15)
при a x b, процесс итерации
	xn = (xn-1) (n = 1,2,…)	(3.16)
сходится, независимо от начального значения x0 a, b ;
предельное значение ξ lim xn	является единственным корнем уравнения
n
на отрезке a,b .	x = (x)	(3.17)
на отрезке a,b .

Доказательство. Рассмотрим два последовательных приближения xn = (xn-1) и xn+1 = (xn), которые в силу условий теоремы заведомо имеют смысл. Отсюда

xn+1 xn= (xn) (xn-1).

Применяя теорему Лагранжа, будем иметь

где, xn

Отсюда,


	xn 1 xn	(xn xn 1 ) ’			(xn ) ,
(xn 1 , xn ). Следовательно, на основании условия (3.15) получим:
	xn 1	xn q xn xn 1 .					(3.18)
давая значения	n 1, 2, 3 ...,		последовательно выводим:
	x2		x1	q x1 x0		,
	x3 x2	q x2		x1 q	2	x1 x0	,

. . . .

x	n 1	x	n

Рассмотрим ряд

. .

q	n	x
	n
		1

x	0

. . .

(3.19)

x0 (x1	x0 ) (x2	x1 ) ... (xn	xn 1 ) ...,			(3.20)
для которого наши последовательные приближения				xn	являются	(n 1) -ми
частными суммами, т.е. xn	Sn 1 .

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

знаменателем					q 1, поэтому ряд			(3.20) сходится, притом		абсолютно.
Следовательно существует
					lim Sn 1 lim xn ξ,
					n			n
причем, очевидно, ξ a,b . .
Переходя к пределу в равенстве (3.16), в силу непрерывности
функции (x) получаем
								= ( ).		(3.21)
Таким образом, есть корень уравнения (3.17). Другого корня на
отрезке	a, b			уравнение (3.17) не имеет. Действительно, если
отрезке				уравнение (3.17) не имеет. Действительно, если
								ξ (ξ) ,		(3.22)
то из равенств (3.21) и (3.22) получим ξ ξ (ξ) - (ξ) и, следовательно,
										(3.23)
					(	ξ	ξ) [1- ’(c)] = 0,			(3.23)
где c ξ,			. Так как выражение в квадратных скобках в равенстве (3.23) не
где c ξ,		ξ
равно нулю, то ξ ξ, т.е. корень – единственный. Теорема доказана.
Выведем оценку приближения. Пусть									f (x) x (x).	Очевидно,
что f (x) 1 ’ (x) 1 q . Отсюда, учитывая f (ξ) 0,									получим

\|xn (xn)\|		f (x	n	) f

где xn (xn , ξ), и, следовательно,

x	n

(ξ) x		n	ξ f	(x			n	) (1 q) x	n	ξ ,
		n					n		n
ξ	x	n	(x	n	)	,
ξ						,

			1 q

(3.24)

т.е.


ξ x		x	n 1		x	n	.
ξ x							.

	n		1	q
			1	q

(3.25)

Используя формулу (3.18), имеем также

ξ x			q	. x		x		,
	n		q		n		n 1
		1

т.е. в

этом случае из неравенства

x	n	x	n 1	ε
	n		n 1

вытекает неравенство

ξ x	n	ε.
	n

3.5. Метод золотого сечения

Этот метод похож на метод дихотомии. В методе половинного деления очередная точка бралась как середина отрезка, а в методе золотого сечения – в отношении золотого сечения [13].

Золотое сечение – это такое пропорциональное деление отрезка на неравные части, при котором весь отрезок так относится к большей части, как сама большая часть относится к меньшей; или, другими словами, меньший отрезок так относится к большему, как больший ко всему

(рис. 3.4).

a : b = b : c или с : b = b : а.

Рис. 3.4. Геометрическое изображение золотой пропорции

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

(рис. 3.5).

Рис. 3.5. Деление отрезка прямой в золотой пропорции с помощью циркуля и линейки

Деление отрезка прямой по золотому сечению: BC = 1/2 AB; CD = BC. Из точки В восставляется перпендикуляр, равный половине АВ.

Полученная точка С соединяется линией с точкой А. На полученной линии откладывается отрезок ВС, заканчивающийся точкой D. Отрезок

AD переносится на прямую АВ. Полученная при этом точка Е делит отрезок АВ в соотношении золотой пропорции.

Свойства золотого сечения описываются уравнением x2 – x – 1 = 0.

Решение этого уравнения

x1,2

	1	5
	2
	2

3.6. Графическое решение уравнений
Действительные корни уравнения
f (x) 0	(3.26)

приближенно можно определить как абсциссы точек пересечения графика функция y f (x) с осью Ох. Если уравнение (3.26) не имеет близких между

собой корней, то этим способом его корни легко отделяются.
На практике	часто	бывает выгодно уравнение (3.26)	заменить
равносильным ему уравнением
		u(x) v(x) ,	(3.27)
где функции u(x)	и v(x)	более простые, чем функция	f (x) .Тогда,

построив графики функций y=u(x) и y=v(x), искомые корни получим как абсциссы точек пересечения этих графиков.

Нахождение корней уравнения u(x) = v(x) упрощается, если одна из функций u(x) или v(x) линейная, то есть, например, u(x) = ax + b. Этот метод особенно эффективен при решении ряда однотипных уравнений, отличающихся только коэффициентами a и b линейной функции. В этом случае графическое построение сводится к нахождению точек пересечения фиксированного графика y = v(x) с различными прямыми.

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

3.7. Примеры

Пример 3.1
Отделить корни уравнения	f

Решение. Построим таблицу

(x)	x	3
(x)	x
3.1.

6x 2

Таблица 3.1

Нахождение интервалов, содержащих действительные корни

x		-3	-1	0	1	3
f (x)	–	–	+	+	–	+	+

Из нее видно, что уравнение f (x) x3 6x 2 0 имеет три действительных корня, лежащих в интервалах (–3, –1), (0, 1) и (1, 3).

Если существует непрерывная производная f (x)		и корни уравнения
f (x) 0		корней уравнения
	легко вычисляются, то процесс отделения

f (x) 0	можно упорядочить. Для этого, очевидно, достаточно подсчитать

лишь знаки функции f (x) в точках нулей ее производной и в граничных точках x a и x b .

Пример 3.2	x		2x		x 1 0	на отрезке
Численно решить нелинейное уравнение		4		3

[0,1] методами: шаговым методом определить интервал изоляции корня с шагом 0,2; уточнить корень уравнения методом половинного деления; методом Ньютона; методом простой итерации.

Решение. Обозначим левую часть исходного уравнения за функцию

f (x) x		4	2x		3	x 1 .
		4			3
	Шаговый метод. Ручной счет

	x			f(x)			Расчет:
							x=0; f(0)=04+2∙03-0-1=-1,
	0			-1			x=0; f(0)=04+2∙03-0-1=-1,
							x=0+0,2=0,2; f(0,2)=0,24+2∙0,23-0,2-1=-1,1824,
	0,2			-1,1824			x=0+0,2=0,2; f(0,2)=0,24+2∙0,23-0,2-1=-1,1824,
							x=0,2+0,2=0,4; f(0,4)=0,44+2∙0,43-0,4-1=-1,2464,
	0,4			-1,2464			x=0,2+0,2=0,4; f(0,4)=0,44+2∙0,43-0,4-1=-1,2464,
							x=0,4+0,2=0,6; f(0,6)=0,64+2∙0,63-0,6-1=-1,0384,
	0,6			-1,0384			x=0,4+0,2=0,6; f(0,6)=0,64+2∙0,63-0,6-1=-1,0384,
							x=0,6+0,2=0,8; f(0,8)=0,84+2∙0,83-0,8-1=-0,3664,
	0,8			-0,3664			x=0,6+0,2=0,8; f(0,8)=0,84+2∙0,83-0,8-1=-0,3664,
							x=0,8+0,2=1; f(1)=14+2∙13-1-1=1.
	1			1			x=0,8+0,2=1; f(1)=14+2∙13-1-1=1.

Смена знака функции происходит на промежутке (0,8; 1). Ответ: корень принадлежит промежутку (0,8; 1).

Реализация шагового метода в Microsoft Excel представлена на рис. 3.6.

<<< < Предыдущая 1 2 3 4 5 6 78 / 298 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
27.11.20192 Мб50Учебник по РЯ и КР. Электронная версия.doc
#
27.03.2015190 Кб16учебник ССО.doc
#
01.05.2025187 Кб4Учебно-методическое пособ.docx
#
01.04.20251 Мб0Учебное пособие (1).doc
#
01.05.20252 Мб1Учебное пособие ФАЭ 15.03.12.doc
#
11.03.20167 Мб336Учебное пособие_Численные методы -26 -дек_2014 (97-2003).pdf
#
01.07.202537 Кб0Учебный материал 2. Междун. маркетинг.docx
#
01.07.2025117 Кб0учет затрат вопросы.docx
#
03.05.2015311 Кб22Фадеев 2.pdf
#
01.03.2025669 Кб7Федеральное агентство по образованию.doc
#
28.03.20155 Мб73Физ химия и физ т.д..pdf