part2 / текст(all)

Абсолютная погрешность приближенного значения xn 1 определя-

ется по формуле: xn 1		q				xn 1 xn
		q
1
Алгоритм метода итераций:
1. Задать x0 a;b . 2.			N 0 . 3. Вычислить					xn 1 ,	xn 1 по форму-

лам (1.3), (1.4). 4. Если xn 1 , то xn 1 xn 1 , конец. 5. n n 1 , идти на шаг 3.

Вопросы для самопроверки

1.Что называется корнем уравнения?

2.Что значит решить уравнение?

3.Что значит отделить корень?

4.В чем состоит суть графического отделения корней уравнения?

5.Этапы решения уравнения с одной неизвестной.

6.Способы отделения корней.

7.Каким образом графическое отделение корней уточняется с по-

мощью вычислений?

8. Словесное описание алгоритма метода половинного деления.

9. Необходимые условия сходимости метода половинного деления. 10. Условие окончания счета метода простой итерации. Погреш-

ность метода.

11. Словесное описание алгоритма метода хорд.

12. Графическое представление метода хорд. Вычисление погрешности.

13. Словесное описание алгоритма метода касательных (Ньютона). 14. Графическое представление метода Ньютона. Условие выбора

начальной точки.

11

Тема 2. МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

2.1. Метод Гаусса

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

Запишем систему линейных уравнений следующим образом:

Ax b .										(2.1)
Расширенная матрица А этой системы имеет вид:
		a11			a12	...	a1n	b1
A a21					a22	...	a2n	b2	.	(2.2)
		...			... ... ...			...
					am 2	...	amn
		am1						bm

На первом шаге элемент a11 0 называется ведущим. Разделим на него первую строку матрицы А, в результате получим (2.3).

x	a12	x	...	a1n	x		b1	.	(2.3)
1	a11	2			n		a11
				a11
Найдем x1 из (2.3), подставим его значение во все остальные урав-
нения и тем самым исключим			x1 из всех уравнений,						кроме первого.

Взяв теперь полученную систему без первого уравнения, повторяем этот процесс, беря в качестве ведущего элемента коэффициент при x2 и

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

приведена к треугольному виду. Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных: решая последнее уравнение, находим единственное неизвестное xn . Далее, используя это

значение, из предыдущего уравнения вычисляем xn 1 и т.д. Последним находим xi из первого уравнения.

Одной из модификаций метода Гаусса является схема с выбором главного элемента. Она состоит в том, что требование akk 0 (на akk ,

12

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

2.2. LU-разложения

Представим матрицу A в виде произведения нижней треугольной матрицы L и верхней треугольной U.

Введем в рассмотрение матрицы

	1		0 ...			0	0
	21		1 ...			0	0
L		31		32	...	0	0
...			... ...			...	...
	m1		m2 ...			mm 1	1
и
a11			a12 ...			a1m 1	a1m
			(0)			(0)	(0)
	0		a22 ...			a2m 1	a2m
U	0		0 ...			a(1)	a(1)
						3m 1	3m
..			... ... ...				...
	0		0 ...			0	(m 1)
							amm

Можно показать, что A = LU. Это и есть разложение матрицы на множители.

Абсолютная и относительная погрешности матрицы вводятся аналогично погрешностям вектора с помощью формул:

A*

A* A

, A*

A A*

A

где А – норма матрицы А.

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

Теорема (об оценке погрешности решения по погрешностям входных данных). Пусть решение системы Ax b , а x* – решение системы A* x* b* , тогда

13

x* cond A b* A* ,

где cond A A A 1 – относительное число обусловленности системы.

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

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

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

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

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

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

x cx d

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

Взяв за нулевое приближение какой-либо вектор x (0) ,

вычислим

приближение x(1) по формуле

x (1)

cx (0)

d

,

(2.4)

аналогично

x (2)

cx (1)

d

, и т.д.

(2.5)

Последовательность векторов

x (k ) , k=l,2,..., сходится

к точному

решению x* , т.е.

lim

x( k ) x* ,

(2.6)

k

если норма матрицы c

c

1 .

(2.7)

14

Норма c определяется по одному из следующих способов:

c m max aij ; i j

c l max aij ;

						j i
	c				k			aij		2 .
						i, j

Теорема. Метод простой итерации, реализующийся в процессе последовательных приближений (2.5), сходится к единственному реше-

нию исходной системы (2.1) при любом начальном приближении x (0) со скоростью не медленнее геометрической прогрессии, если какая либо норма матрицы c меньше единицы, то есть c 1 .

2.4. Метод Зейделя

Метод Зейделя отличается от метода простой итерации тем, что найдя какое-то значение для i-й компоненты, мы на следующем шаге используем его для отыскания следующей компоненты. Вычисления ведутся по формуле

xi(k )	1	bi ai1x1(k )	ai,i 1 xi(k1) ai,i 1 xi(k1 1)	ain xn(k 1)
	ai i

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

aii				aij		, i 1, 2, n .

(при этом, хотя бы для одного уравнения неравенство должно выполняться строго) Эти условия являются достаточными для сходимости метода, но они не являются необходимыми.

Проиллюстрируем этот метод на примере решения системы

a11 x1 a12 x2 a13 x3 b1 , a21 x1 a22 x2 a23 x3 b2 , a31 x1 a32 x2 a33 x3 b3 .

Приближение с номером k можно вычислить, зная приближение с номером k 1, как

15

			x1(k )		1			b1 a12 x2(k 1) a13 x3(k 1) ,
				a 22
			x2(k )		1			b2 a 21 x1(k ) a23 x3(k 1) ,
					a11
			x3(k )			1			b3 a31 x1(k ) a32 x2(k ) .
						a33
Итерационный процесс продолжается до тех пор, пока значения
x(k ) ,	x(k ) ,	x(k ) , не станут близкими с заданной погрешностью к значе-
1	2	3
ниям	x(k 1)	, x(k 1) ,	x(k 1) .
	1	2	3

Вопросы для самопроверки

1.Какие вы знаете группы методов решения систем линейных уравнений?

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

3.Какие методы относятся к приближенным методам решения систем линейных уравнений?

4.Что значит решить систему уравнений?

5.В чем заключается суть метода Гаусса для решения систем линейных уравнений?

6.В чем заключается суть метода LU-разложения для решения систем линейных уравнений?

7.В чем заключается суть метода простой итерации для решения систем уравнений?

8.Как привести систему к виду с преобладающими диагональными коэффициентами?

9.В чем заключается суть метода Зейделя для решения систем уравнений?

10.В чем отличие итерационного процесса метода Зейделя от аналогичного процесса метода простой итерации?

16

Тема 3. АППРОКСИМАЦИЯ ФУНКЦИЙ

Пусть дискретному множеству значений аргумента xi поставлено в соответствие множество значений функции yi f (xi ) (i = 0,1,..., n). (эти

значения – либо результаты расчетов, либо экспериментальные данные). Задача о приближении (аппроксимации) функции состоит в том, что данную функцию f (x) требуется приближенно заменить (аппрок-

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

3.1. Многочлен Лагранжа

Рассмотрим функцию

y f x ,

непрерывную на интервале a, b и заданную некоторыми своими зна-

чениями yi	f xi , i 0,1,..., n для соответствующих значений аргу-
мента a x0	x1 ... xn b .	Необходимо найти значение этой функ-
ции в точке	x* a,b , x* x	и оценить погрешность полученного при-
	i

ближенного значения.

Один из возможных путей решения поставленной задачи заключается в следующем:

1) строится многочлен степени не выше п

P x a xn		a	xn 1 ... a	x a ,	(3.1)
n	0	1	n 1	n
принимающий в точках		xi	значения yi ,	т.е. значения коэффициентов
многочлена – ai	– находятся из условия:

Pn xi yi , i 0,1,..., n.

Этот многочлен называется интерполяционным. Он всегда существует и единственен.

Функция f x представляется в виде:

f x Pn x Rn x ,

(3.2)

17

где Rn x – остаточный член интерполяционной формулы. Если функция f(x) имеет непрерывную производную порядка (n 1) на отрезке a, b , то

	R x	f n 1		x x	x x ... x x			, a,b .	(3.3)
		n 1 !
	n			0		1	n
	2) Вычисляется значение Pn x* .					Если значения yi , заданы при-

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

ближенное значение Pn x* для точного значения Pn x* . 3) Приближенно принимается, что f x* Pn x* .

4) Оценивается погрешность метода по остаточному члену интерполяционной формулы:

Rn x* 1

M n 1

x* x0 x* x1 ... x* xn

,

(3.4)

n 1 !

где M

n 1

max

f n 1 (x)

.

(3.5)

x0 ,xn

5) Оценивается погрешность вычисления по погрешностям приближенных значений исходных данных:

2		Pn x*		x*		.	(3.6)
			P n

Таким образом, полная погрешность приближенного значения есть

					f ( x )		( x )	.
	1		2			P			(3.7)
						n

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

мала. При достаточной точности исходных значений yi и достаточной точности вычислений Pn x* вычислительная погрешность будет также достаточно мала; следовательно, приближенное значение Pn x* в этом случае будет достаточно мало отличаться от точного значения f x* .

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

18

Одна из таких форм – интерполяционный полином Лагранжа:

	n	(x x0 )(x x1 )...(x xi 1 )(x xi 1 )...(x xn )
	L n x										yi . (3.8)
		(x	x )(x	x )...(x		x		)(x x		)...(x x )
	i 0				i
		i	0 i	1		i 1		i i 1		i n
	Остаточная погрешность значения						Ln x* ,		вычисленного по фор-

муле (3.8), оценивается формулой (3.4), а вычислительная погрешность по формуле (3.9)

n

(x* x )(x*

x )...(x*

x

)(x* x

)...(x* x )

2

0

1

i 1

i 1

n

yi , (3.9)

(x x )(x

x )...(x

x

)(x x

)...(x x )

i 0

i

1

i 0 i

1

i

i i 1

i n

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

таблицы, а лишь по некоторым, находящимся вблизи x* .
В	случае	равноотстоящих	узлов,	то	есть	когда
xi x0	i h,i 0,1,..., n , где h – шаг интерполяции, целесообразно исполь-

зовать интерполяционные полиномы Стирлинга, Бесселя и Ньютона.

Для более компактной записи этих полиномов обычно вводят понятие конечных разностей.

Будем называть конечными разностями первого порядка функции

y f x в точке xi следующие величины:
yi yi 1 yi ,	(3.10)

а конечные разности к-го порядка определяются такими рекуррентными соотношениями:

k y	k 1 y	k 1 y .	(3.11)
i	i 1	i

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

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

19

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

Обратимся вновь к формуле (4.4) оценки остаточной погрешности интерполяционного полинома. На практике точно определить про-

изводную f n 1 x и ее максимальное по модулю значение M n 1 быва-

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

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

m y h m f m				, x , x
i					i i m
На основании этого свойства
		max	n 1 y
		a,b		i
Mn 1					.	(3.12)
		hn 1

3.2. Интерполяционный полином Стирлинга и Бесселя

Пусть точка x* расположена вблизи от некоторого узла, который назовем x0 .

Для интерполирования выберем узлы, симметричные относительно x0 :

...x k ,..., x 1, x0 , x1,..., xk ,...

Введем в рассмотрение новую переменную

t	x x0	.	(3.13)
	h

Выбор полинома осуществляется исходя из требования получения минимальной величины погрешности интерполяции и определяется

величиной t* : если выполняется условие (3.14)

	t*		x* x
			0	0, 25 ,	(3.14)
			h

то используется полином Стирлинга, если выполняется условие (3.15)

0, 25 t* 0, 75 ,

(3.15)

то используем полином Бесселя.

20