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

если

если

y y



sin tg(

x x)

0
0

			y		cos
	, то
2
		, имеем				y
2

x

и,

sec

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

2	x	и	x	y	cos	2

		x		y	sec x
x	рад.;

рад.;

если

если

y

y

ln(sin x)
ln tg(x)

	x
0
			2
0 x
		2

	, то y		ctgx				и
, тогда				y			2
						sin 2x

x

и

tan
	x

x y	рад.;
0,5sin 2x		y

рад.;

Показательная функция. Если y e x , то y e x и x			y
		e	x
1.15. Примеры

или x yy .

Пример 1.1

	Определить предельную абсолютную погрешность числа c = 2,7,
заменяющего число e.
	Решение. Так как справедливо неравенство 2,7<e<2,8 то | c e | 0,1.
	Руководствуясь формулой c e c , можно принять c 0,1.
	Если учесть, что 2,71<e<2,72, то можно получить лучшую оценку
c	0,01.

Пример 1.2

Вес 1 дм3 при температуре 10 С m 987,356г. 0,001г. предельную относительную погрешность взвешивания.

Решение. Предельная абсолютная погрешность дана

задачи: m 0,001.

Определить

в условии

Пользуясь формулой

	m

m δ	m

, получим

δ	m

	0,001	10	6
	987,356

10	4	%

.

Пример 1.3

При определении скорости света в вакууме получили, что с=199 792 м/с. Зная, что относительная погрешность этого значения равна

0,01	00 , найти пределы, в которых заключается c.
	0
	Решение. Имеем δc 0,00001, тогда c | c | δc 3 .
	Следовательно, c c C c c , т.е. 299 789	c 299 795.

Пример 1.4

Представить число

Решение. 2,7182... 2

e 2,7182... в виде десятичной дроби.

1	7 10	1	1 10	2	8 10	3	2	10	4	...
10

21

Пример 1.5

Определить незначащие цифры чисел a = 0,0024 и b = 25 600. Решение. Представим числа в виде:

a 2 10	3	4 10	4	0,0024	, b 2 10	5	5	10	4	6	10	3	25 600 .

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

Пример 1.6

Найти число верных знаков приближенного числа являющегося приближением точного числа B 686,98.

b

687,00

,

Решение. Абсолютная погрешность

	| B b | 0,02	1	0,1
		2

1 2

10	1

.

Представим число b 687,00	в виде b 6 10		8 10	7 10	0 10	1	0 10	2	,
		2	1	0

то есть старшим десятичным разрядом числа b является m = 2. Число верных знаков п определяется по формуле m n 1 1, т.е. 2 n 1 1 , следовательно п=4. То есть число b = 687,00 имеет четыре верных знака.

Пример 1.7
Округлить	число e 2,718281... до шести,		пяти, четырех	значащих
цифр.
Решение.	Округлив число	e 2,718281...	до шести, пяти,	четырех

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

числа

2,71828,

2,7183,

2,718

с абсолютными погрешностями

| 2,718281 2,71828| 0,000001		1	10			5	,
		2
| 2,718281 2,718 | 0,000281	1	10		3	.
	2

| 2,718281 2,7183| 0,000019

1 2

10	4

,

Пример 1.8

Какова предельная относительная погрешность, если вместо числа e

взять число с = 2,72?
Решение. Первая значащая цифра числа	c 2,72 α m 2 ,	число его
верных десятичных знаков n = 3 (все знаки считаются		верными).

Следовательно,												по	формуле
			1	1				3 1		1			0,25% .
δc												0,0025
			2
	2			10				400

δ			1		1
	c
			2α		10
				m

n 1

получаем

Пример 1.9

Со сколькими десятичными знаками надо взять число 40 , чтобы погрешность не превышала 1% ?

22

Решение. Так как первая цифра

причем δ 0,01. Используя формулу

Отсюда 10	n 1	16	2	и n 3.
			3

		40
δ	c

(	36
1
2αm

1 10

40	49)	равна
n 1
, получаем
		6

	6 , то			α m
	1		0,01
	10	n 1

6

.

,

Пример 1.10

Найти сумму приближенных чисел: 0,667 , 0,4874, 577,4 , 270,2 , 53,68 , 2,14, 0,0313, 0,0342, 0,000781, каждое из которых имеет все верные значащие цифры (в широком смысле).

Решение (См. Правило сложения чисел разной точности). Выделяем числа наименьшей точности 577,4 и 270,2, абсолютная погрешность которых может достигнуть 0,1 (так как речь идет о значащих цифрах в широком смысле).

Округляя остальные числа с точностью до 0,01 и, выполняя сложение, получим 577,4 270,2 53,68 2,14 0,67 0,49 0,03 0,03 0,00 904,64 Округляя полученный результат до 0,1, получим приближенное значение суммы 904,6.

Полная погрешность результата складывается из трех слагаемых:

1)суммы предельных погрешностей исходных данных

		10	3	10	4	10	1	10	1	10	2	10	2	10	4	10	4	10	6
	1

0,221301

0,2213

;

2)абсолютной величины суммы ошибок (с учетом их знаков) округления слагаемых:

2 | 0,003 0,0026 0,0013 0,0042 0,000781| 0,000681 0,0007 ;

3)заключительной погрешности округления результата: 3 0,0400.

Следовательно, 1 2 3 0,2213 0,0007 0,0400 0,262 0,3 .

Таким образом, искомая сумма есть 904,6 0,3.

23

Пример 1.11

Вычислить разность двух чисел: x1 = 32,8979 и x2 = 32,8967, каждое из которых имеет шесть верных знаков. Найти число верных знаков разности и предельные относительные погрешности.

Решение. Разность u = 32,8979 32,8967 = 0,0012 имеет две значащие

цифры, причем u	x	x	0,00005 0,00005 0,0001 (так как числа имеют 6
	1	2
верных знаков, то	x 0,00005					и		x				2	0,00005).
	1
То есть последняя значащая цифра разности сомнительна,
следовательно, разность имеет одну верную значащую цифру.
Предельные	относительные															погрешности		вычитаемого,
уменьшаемого и разности соответственно равны:
		δ					x								0,00005		0,000002,
									1
			x				x								32,8979
			1
								1
		δ							x	2					0,00005		0,000002,
			x	2			x								32,8967
									2
		δ						u						0,0001		0,08.
			y				u						0,0012

Пример 1.12

Найти разность Решение.

u

3,005

3

с четырьмя верными знаками.

3,005 1,733493...			,
3 1,732050...			,

u 0,001443 1,443 10 3.

Или

Берем корни

3,005

u		(	3,005	3)( 3,005				3)		0,005	.
			3,005							3,005
						3					3
и 3 с четырьмя верными знаками:
u			0,005		0,005						3	.
							0,001443 1,443 10
	1,733 1,732				3,465

Пример 1.13

Определить относительную погрешность и количество верных цифр

произведения y 46,345 8,3678											(каждое из множителей имеет все верные
значащие цифры).
Решение. α1 4 ,					α2		8				первые значащие цифры сомножителей,
m 5 количество верных цифр обоих сомножителей.
	1			1			1			1	)m 1	1	1			1	1				5 1	3	1				4	1	1			4
δ y			(					)	(
				1		2
	2								10			2	4			8	10					16 10						2	10

Произведение y имеет, по меньшей мере, четыре верных цифры.

24

Контрольные вопросы

1.Какое число называется приближенным?

2.Какая величина называется ошибкой приближенного числа?

3.Как вычисляются абсолютная и относительная погрешность приближенного числа?

4.Как определить количество значащих цифр в числе?

5.Как определяются верные знаки десятичного числа?

6.Сформулируйте правила округления чисел.

7.Как вычисляется абсолютная погрешность суммы приближенных чисел?

8.Сколько знаков приближенного числа следует взять, чтобы получить произведение с m-1 верными знаками?

9.Во сколько раз больше предельная относительная погрешность m-й степени предельной относительной погрешности самого числа?

10.В чем заключаются прямая и обратная задачи теории погрешностей?

25

2. Решение систем линейных алгебраических уравнений

	Задача	численного	решения	систем
	линейных алгебраических уравнений (СЛАУ)
	имеет незапамятную историю. Классический
	метод исключения, активно развиваемый и
	изучаемый даже в наши дни, был открыт К.
	Гауссом в 1849 г. Однако еще за 2000 лет до
	этого в Древнем Китае изданы «Девять книг о
	математическом искусстве», где этот алгоритм
	уже изложен в характерной для своего
	времени «натуральной» форме, но фактически				К. Гаусс
	с использованием матричных преобразований.
					(1777-1855)
	Вплоть	до начала	XX в.	алгебра

оставалась «наукой о решении уравнений», после чего произошло ее разделение на высшую алгебру (операции с абстрактными объектами различной природы) и линейную, основа которой матричное исчисление.

Становление современных вычислительных методов линейной алгебры можно считать состоявшимся после выхода в 1960 г. книги Д.К. и В.Н. Фаддеевых с одноименным названием, по которой училось не одно поколение российских и зарубежных математиков. Необходимо подчеркнуть, что актуальные проблемы вычислительной алгебры имеют фундаментальный характер не только потому, что текущая компьютеризация различных областей знаний в значительной степени сводится к векторно-матричным процедурам. Изучение матриц, являющихся операторами в простейших конечномерных пространствах, позволяет обнаружить наиболее глубокие и тонкие свойства математических объектов, имеющих свое значение для функционального анализа, теории аппроксимации, дифференциальных уравнений и т.д.

Последние десятилетия ознаменованы бурным развитием численных методов, нашедших отражение в книгах Г.И. Марчука, А.А. Самарского, С.К. Годунова, Дж. Голуба, О. Аксельсона и др. В рамках итерационных методов решения СЛАУ значительные продвижения достигнуты в таких современных направлениях, как алгоритмы сопряженных направлений, последовательной и симметричной верхней релаксации, неявные алгоритмы переменных направлений и методы неполной факторизации.

26

Несмотря на имеющиеся в этой области теоретические достижения, а также на бурный рост мировых вычислительных мощностей, проблема конструирования и исследования новых быстрых алгоритмов решения СЛАУ не теряет своей актуальности, и поток публикаций по этой тематике только увеличивается. Объясняется это тем, что возникающие практические задачи, наряду с усложнением вычислительных процедур, требуют от методов решения все большей точности и надежности. И с этим связан тот уникальный феномен, что, невзирая на появление все новых поколений ЭВМ, за последние 50 лет решение «больших» (на текущий момент) задач всегда занимало примерно одинаковое астрономическое время.

2.1.Общие сведения

Крешению систем линейных уравнений сводятся многочисленные задачи. Рассмотрим постановку задачи [10].

Дана система n алгебраических уравнений с n неизвестными:

a

x

a

x

2

...

a

x

n

b

,

11

1

12

1n

1

a

x

a

x

a

x

b

,

21

22

2

2n

n

2

1

.......... .......... .......... .......... .

a

n1

x

a

n2

x

2

...

a

nn

x

n

b .

1

n

(2.1)

Эту систему можно записать в матричном виде:

A X

=

B

, где

a11	a12	...	a1n		x1			b1
A a21	a22	...	a2n	;	X x2		;	B b2	.
.	.	.	.		...			...
an1	an 2		ann		xn			bn

A квадратная матрица коэффициентов, X вектор-столбец неизвестных, B вектор-столбец свободных членов.

Численные методы решения систем линейных уравнений делятся на прямые и итерационные. Прямые методы используют конечные соотношения для вычисления неизвестных. Эти методы сравнительно просты и пригодны для широкого класса систем. Недостатки: требуют хранения в памяти ЭВМ сразу всей матрицы A. При больших порядках системы расходуется много места в памяти и накапливается вычислительная погрешность. Кроме того, существенно возрастает время вычисления вектора X. Поэтому прямые методы обычно применяют при небольших порядках системы (n<200). Примеры прямых методов метод определителей Кремера, метод Гаусса. Первый из них применяется

27

крайне редко, так как с ростом n алгоритм нахождения определителей резко возрастает. Метод Гаусса будет подробно рассмотрен в дальнейшем.

Итерационные методы основаны на последовательных приближениях. Задается некоторое приближенное значение вектора X – начальное приближение. Затем с помощью некоторого алгоритма проводится первый цикл вычислений – итерация, в результате которого получается новое приближение вектора X. Итерации проводятся до получения решения с заданной точностью. Алгоритм решения систем линейных уравнений здесь более сложен, чем у прямых методов. Не всегда выполняется условие сходимости. Однако в ряде случаев итерационные методы предпочтительнее. Они требуют хранения в памяти ЭВМ не всей матрицы A, а лишь нескольких векторов. Вычислительная погрешность практически не накапливается. Поэтому итерационные методы применимы и для больших порядков системы. Итерационными методами являются метод простой итерации и метод Зейделя.

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

Метод основан на приведении матрицы системы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы. Сначала с помощью первого уравнения исключается x1 из всех последующих уравнений. Затем с помощью второго уравнения исключается x2 из последующих и т.д. Этот процесс называется прямым ходом метода Гаусса и продолжается до тех пор, пока в левой части последнего n-го уравнения не останется лишь один член с неизвестным xn. В результате прямого хода система принимает вид

(2.2)

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

Приведенный алгоритм является наиболее строгой реализацией метода Гаусса и применяется в стандартных программах ЭВМ. На практике можно использовать более простые действия для приведения

28

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

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

Пусть дана система из n алгебраических уравнений с n неизвестными:

a

x

a

x

2

... a

x

n

b

,

11

1

12

1n

1

a

x

a

x

... a

x

b

,

21

22

2

2n

n

2

1

.......... .......... .......... .......... .

a

n1

x

a

n2

x

2

... a

nn

x

n

b .

1

n

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

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

соответствующей строке:

a	>
ii

n aij i=1,i j

.

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

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

качестве которого обычно выбирается нулевой вектор:	(	0 )	(0)	(0)	= 0 .
	x1		= x2	= ... = xn

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

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

x k b a x k 1 ...				a		x k 1			a ,
1	1	12 2		1n			n		11
x k b a x k 1 ...				a x k 1 a ,							(2.3)
	2		21 1		2n		n		22
2
.......... .......... .......... .......... ..
x k b a			x k 1 ...	a	n,n 1			x k 1 a		nn	.
n	n		n1 1					n 1
			29

Итерационный процесс заканчивается, если для каждой i-й компоненты вектора неизвестных будет выполнено условие достижения точности ε

,

где k номер итерации; заданная точность.

О близости найденного на k-й итерации решения и точного можно также судить по так называемой невязке – разности правой и левой частей уравнений системы при подстановке в нее приближенного решения

(x1(k),x2(k),x3(k)).

Формулы для вычисления ошибок (невязок) в выполнении равенств:

O1k a11 x1k a12 x2k a13 x3k b1 ,

O2k a21 x1k a22 x2k a23 x3k b2 ,

O3k a31 x1k a32 x2k a33 x3k b3 .

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

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

Отличается здесь только третий пункт алгоритма. При вычислении x1 используется информация об остальных неизвестных, найденных на предыдущей итерации. При вычислении x2 используется значение x1, найденное на 1-м шаге текущей итерации, и значения остальных переменных, найденные на предыдущей итерации, и т.д. Наконец, при вычислении последней компоненты вектора неизвестных xn используется информация об остальных компонентах, найденных на текущей итерации. Приведенная система уравнений имеет вид

x(k)

1(k)

x2

xn(k)

= b a x(k 1 ) + ... + a

1n

x(k 1 ) / a ,

1

12 2

n

11

= b a

x(k)

+ ... + a

2n

x(k 1 )

/ a

22

,

2

21

1

n

=..........b ..........a

..........

..........

..........

/ a

(2.4)

x

(k)

+... + a

n,n 1

x

(k)

nn

.

n

n1 1

n 1

30