Численные методы_1 / Пособия / Самарский_Задачи и упражнения по численным методам

100 Глава 7. Задачи минимизации функций

Задача 7.5. Рассмотрите условия сходимости градиентного итерационно­ го метода (7.12) при минимизации функции /(ж), для которой

™(У, У) ^ (f"(x)y, У) < ЩУ, У), т > 0.

Задача 7.6. Покажите, что если матрица f"(xk) положительно опре­ делена, /'(ж*) Ф 0, то направление hk = -(/"(ж*))~ /'(**) является направлением убывания функции /(ж) в точке ж*.

Задача 7.7. Получите оценку сходимости метода Ньютона (7.13) при ми­ нимизации дважды дифференцируемой функции /(х) при предположе­ ниях

(/"(«)», у) > т(у, у), т > 0,

\\Г\х)~Г\у)\\^М\\х-у\\.

Задача 7.8. Проекцией точки а € R" X С R" называется точка Рг(л) € X такая, что

||Pjr(o)-o||<||x-a||, Vx€X,

т.е. точка, ближайшая к а среди всех точек X. Рассмотрите метод проекции градиента при решении задачи условной минимизации (7.1), когда

xM=Px(xk-akf'(xk)),

k = 0,1,....

Задача 7.9. Покажите, что штрафная функция

1 m р

i>(x,e) = -УЧтах{0,А (х)}] , Р> 1

является выпуклой непрерывно дифференцируемой функцией, если фун­ кции g,(x), i — 1,2,... — выпуклые непрерывно дифференцируемые функции.

Задача 7.10. Постройте примеры функций штрафа для задачи миними­ зации с ограничениями типа равенств:

/(ж)-+min, #(ж) = 0, i = 1,2,... ,rn.

Глава 8

Интегральные уравнения

Среди типичных интегральных уравнений можно выделить инте­ гральные уравнения Фредгольма второго рода. Для их прибли­ женного решения применяется метод квадратур. Второй широко используемый класс методов решения интегральных уравнений — различные варианты проекционных методов. Отдельно необходи­ мо выделить интегральные уравнения с переменным пределами интегрирования — интегральные уравнения Вольтерра. Инте­ гральные уравнения Фредгольма первого рода являются харак­ терным примером некорректных задач, для численного решения которых используются методы регуляризации.

8.1. Задачи для интегральных уравнений

Будем рассматривать одномерные интегральные уравнения, решение ко­ торых есть и(х), х е [а,Ь]. Линейное интегральное уравнение с постоян­ ными пределами интегрирования (уравнение Фредгольма) записывается в виде

	ь
д(х)и(х)-Х	[K(x,s)u(s)ds	= f(x),	х€[а,Ь],	(8-1)

а

где K(x,s) — ядро интегрального уравнения, а д(х),}(х) — заданные функции, а А заданный или неизвестный числовой параметр.

Наибольшее внимание уделяется нахождению приближенного реше­ ния интегрального уравнения Фредгольма второго рода:

б
и(х)-А fK(x,s)u(s)ds	= f(x),	х£[а,Ъ]	(8.2)

а

при заданном Л,

102		Глава 8. Интегральные уравнения
	Основные обозначения
	К{х ,*)	— ядро интегрального уравнения
	А — числовой параметр
Xi,	* = 1,2,... ,п	— узлы квадратурной формулы
	а	— параметр регуляризации
	Ук — приближенное решение на fc-ой
	1=1,2 ... ,п	итерации
¥>'(*),		— линейно независимые
		координатные функции

При /(я) = 0 уравнение (8.2) есть однородное уравнение Фредгольма

ь
и (х) - А I К (х, s) и (в) ds = 0, х G [а, Ъ],	(8.3)

которое всегда имеет тривиальное решение и(х) ~ 0. Те значения параме­ тра А, при которых уравнение (8.3) имеет ненулевое решение, называются характеристическими числами, а соответствующие ненулевые решения уравнения — собственными функциями (1/А— собственные значения).

Линейное интегральное уравнение Фредгольма первого рода имеет

вид

ь
JK(x,e)u(e)d8	= f(x),	хе[а,Ь],	(8.4)
а
т. е. в общей записи (8.1) д(х)		= 0 и А = - 1 . Принципиальные трудности

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

Отдельного рассмотрения заслуживают интегральные уравнения с пе­ ременными пределами интегрирования. Интегральное уравнение Воль-

8.2. Методы решения интегральных уравнений			103
терра второго рода записывается в виде
	X
и(х)-Х	K(x,s)u(s)ds = f(x),	x€[a,6].	(8.5)

а

По аналогии с (8.4), (8.5) для уравнения Вольтерра первого рода имеем

X
/ K(x,s)u(s) ds = f(x),	x£[a,b].	(8.6)

a

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

8.2. Методы решения интегральных уравнений

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

8.2.1. Интегральные уравнения Фредгольма второго рода

Будем рассматривать алгоритмы численного решения интегральных урав­ нений (8.2), считая заданным параметр А. В основе метода квадратур лежит та или иная квадратурная формула. Пусть х\ < х2 < • • • < хп — узлы, ас*, t = l , 2 , ... ,п — коэффициенты квадратурной формулы на от­ резке интегрирования [а, 6]. При использовании квадратурной формулы

?

/ в(х) dx И 53 °i^xi)

104 Глава 8. Интегральные уравнения

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

п
Vi~ xYlciK	(Xi>si)y3=f(xih	i=l,2,...,n,	(8.7)
i=«

где j/j — приближенное решение в узле Xi, i=	1,2,..., п.
В проекционных методах приближенное решение интефального
уравнения (8.2) ищется в виде
п
у(х) = ^2а<р{(х),	(8.8)

где <pi(x), i = 1,2,...,n — заданные линейно независимые функции, которые называются координатными. Часто удобнее ориентироваться на несколько отличное от (8.8) представление приближенного решения:

п
У (х) = / ( * ) + ] £ *¥>,-(*),	(8.9)

Метод проекционного типа характеризуется выбором координатных функций <Pi{x), i = 1,2,..., п и способом определения вектора неизвест­ ных коэффициентов с = {с\, сг,..., с„}. Отметим некоторые возможности по нахождению коэффициентов в представлениях (8.8), (8.9).

При использовании представления (8.8) определим невязку

п	.	п
Г(х, С) = ^	Ci<Pi(x) - Л / К(Х,	S) 5 3	Cj<Pj(s) ds -	f(x).
• • = '	.	J = '

В методе наименьших квадратов постоянные с,, г = 1,2,... ,п находятся из минимума квадрата нормы невязки в Ьг(а,Ь), т.е.

j„. Ъ4*~*. «Г.

Для определения a, i = 1,2,...,гаполучим систему линейных алгебраи­ ческих уравнений

п
J3ayc,-=b,-, t=l,2,...,n,	(8.10)

где

8.2.	Методы решения интегральных уравнений						105
		6	6			б
	а и = /	yPi(x)-^ I K(x,s)<pi(s)ds)			I<pj(x)-X	/ K(x,s)<pj(s)ds\	dx,
	a	a			a
		6	ft
	*t=	f(x)(<fi(x)-\		K(x,s)<pi{s)ds)dx,		i=l,2,...,n.
	a		a
Тем самым матрица системы (8.10) симметрична.
	В методе Галеркина коэффициенты с,, г = 1,2,...,п определяются
из условия ортогональности				в L2(a,b)	невязки г(х,с) функциям		щ(х),
г =	1,2,...,п:
	п
	r(x,c)ifi(x)dx,		г = 1 , 2 , . . . , п.
В этом случае имеем систему линейных уравнений (8.10), в которой
		6	б
	«О =	/ (<Pj(x) ~ А / K(x,s)tpj(s)			ds)tpi(x)dx,
		а	а
		Ь
	Ь{=	f(x)<pi(x)dx,		г = l,2,...,n.

Отметим среди проекционных методов и метод коллокации. В этом случае на отрезке [а, 6] выбирается п точек коллокации ж,, г = 1,2,...,п и коэффициенты с*, г = 1,2,...,п в представлении (8.8) (или (8.9)) выбираются так, что невязка обращалась в нуль в точках коллокации, т. е.

г(х^,с) = 0, t = l , 2 , . . . , n .

Для коэффициентов матрицы и правой части системы (8.10) при исполь­ зовании представления (8.8) получим

б
о0 = <р,(х{) - А /	K(xi,s)tpj(s)ds,

а

Ь{ = /(х{), *=1,2, ... ,п .

Для решения системы линейных алгебраических уравнений (8.10) применяются прямые или итерационные методы.

106	Глава 8. Интегральные уравнения

8.2.2.Интегральные уравнения с переменными пределами интегрирования

При приближенном решении интегрального уравнения Вольтерра второго рода (8.5) используется как метод квадратур, так и проекционные методы. Для определенности, будем считать, что х\ = а, х„ = Ь. Для точек Xj, i= 1,2,..., п из (8.5) получим

u(xi)-\fK(xi,s)u(s)ds	= f(xi), t=l,2,...,n.	(8.11)
a

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

7

/*(*)&«£<£>*(*,•), «' = 2,3,..., п.

.	;=•
Применение к (8.11) дает систему линейных уравнений
	i
И - А Э Д 0 * (*<•*;)» = /<**)> »"=1,2,...,п.		(8.12)

Отличительная особенность системы уравнений (8.12) состоит в том, что матрица ее коэффициентов треугольная. Это позволяет найти прибли­ женное решение интегрального уравнения у\,Уг,-,Уп последовательно друг за другом по рекуррентным формулам в предположении, что все диагональные элементы матрицы ненулевые. Наиболее простые расчет­ ные формулы при решении интефального уравнения Вольтерра второго рода мы получим при использовании квадратурной формулы трапеций.

При численном решении интефального уравнения первого рода (8.6) можно ориентироваться на использование метода квадратур. Подоб­ но (8.11) из (8.6) будем иметь

у K(xt,«)«(«)ds = f(Xi),	« = l,2,...,n,
а

8.2. Методы решения интегральных уравнений

107

что дает систему линейных алгебраических уравнений

X ] сУк(ъ> *})У} = f(xi)> * = 1,2,..., п.

j=i

Для того чтобы решение этой системы существовало необходимо потре­ бовать выполнение условия К(х, х) Ф 0.

При численном решении интегральных уравнений часто полезно провести предварительное преобразование исходной задачи. Типичным примером является приведение интегрального уравнения Вольтерра пер­ вого рода к интегральному уравнению второго рода. Будем считать, что ядро и правая часть дифференцируемы и К(х,х) Ф 0. Тогда от уравне­ ния (8.6) можно перейти к уравнению

. .	f	1	дК(х, s)	,	ч j	_	1	df_
			dK(x,s)		4 j	= К(х,х)		dx (*),
и ж +	/	U7 \	я	u ( s ) d s
	J	К(х,х)	дх

которое представляет собой интефальное уравнения Вольтерра второго рода.

8.2.3. Интегральное уравнение Фредгольма первого рода

Интегральное уравнение (8.4) есть наиболее характерный пример не­ корректно поставленной задачи. Некорректность обусловлена тем, что при малых возмущениях правой части /(х) не гарантируется малого возмущения решения.

Помимо (8.4) рассмотрим уравнение с возмущенной правой частью

ь
j K(x,s)u(s)ds = f(x),	хе[о,Ь].	(8.13)

Ядро К(х,з) есть вещественная непрерывная функция двух аргументов, a f(x),f(x) e L2(a,b), причем

||/(х) - /(х)|| ^ 6,

108			Глава 8. Интегральные уравнения
при использовании обозначений
			ь
\\Ф)\\	- у («>«).	(«>») =	/ u{x)v(x)dx.
При 6 -> 0 норма пофешности			решения ||й(а:) -	и(а;)|| не стремиться
к нулю.
Определим линейный интефальный оператор
	ь
Ау =	I K(x,s)y(s)	ds, x£[a,b].		(8.14)

а

Задачу с неточной правой частью (8.13) запишем в виде операторного уравнения первого рода

Au = f.

(8.15)

В методе регуляризации Тихонова приближенное решение зада­ чи (8.15) находится из минимума сглаживающего функционала:

Jа (у) -+ min,		у € Ь2 (о, Ъ),			(8.16)
где
Ja(y) = \\Ay-f\\2			+	a\\y\\2,
а а > 0 — параметр регуляризации.
Обозначим решение задачи (8.16) через уа.					Оно может быть найдено
как решение уравнения Эйлера для вариационной задачи (8.16)
ауа + А*Ауа		=	A*f,
где
	о
А*у=	I K(s,x)y(s)ds,			х€[а,Ъ].
Тем самым приходим к интефальному уравнению Фредгольма
	ь
ауа +	I G(x, s)ya(s)			ds = V(x), x G [a,b]

8.3. Упражнения

109

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

ъ

G{x,s) = IK{t,x)K(t,s)dt

и правой частью

о

# r ) = J K(s,x)f(s)ds.

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

\\Aya-f\\ = 6.

При таком выборе а = а(6) норма погрешности \\уа - и|| —> 0 при 6 —• 0, т.е. приближенное решение стремится к точному решению задачи.

8.3. Упражнения

Рассмотрены иллюстративные примеры по построению и исследова­ нию вычислительных алгоритмов приближенного решения интегральных уравнений первого и второго рода.

Упражнение 8.1. Получите условия сходимости метода простой итерации

ь
ик+,(х) = Х IK(x,s)uk(s)	+ f(x),	k = 0,\,...	(8.17)

а

при, например, и0 = f(x) для приближенного решения интегрального урав­ нения (8.2).

Решение. Будем рассматривать сходимость итерационного процесса (8.17) в L2(a,b). Для погрешности из (8.2), (8.17) имеем

uk+i(x)-u(x) = \ J K(x,s)(uk(s)-u(s))ds, fc = 0,l,... .