Вычислительная математика лекции

Объяснение: машинное представление 108 =0.1 109, 1 = 0.1 101.

При сложении и вычитании порядки предварительно выравниваются.

То есть в 1-ом случае число

1 = 0.000000001 109 = 0

(единица младщего разряда оказывается за пределами разрядной сетки).

Аналогичные эффекты возникают при суммировании

следующего ряда . Пусть t = 3. Если вести

сложение слева направо, получим 100. При сложении справа налево после сложения 1000 слагаемых получаем 100 и дальнейшее прибавление 0.1 не будет изменять результат. Конечное значение

200. Однако правильный результат 300 можно получить, если сложить 1000 чисел по 0.1, затем ещё 1000чисел по 0.1 и далее промежуточные суммы.

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

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

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

числа сомножителей.
Пример 2. Пусть	и вычисляем	; a=10-30, b=10-

60 , c=10-40, d=10-50.

Если выполнить действия в порядке x=ab/c/d имеем исчезновение порядка.

Если вычислить x=1/c/dab, имеем переполнение.

Если вычислить x=(a/c)(b/d) получим x=1.

Вывод: при переполнении или исчезновении порядка следует попытаться изменить последовательность действий. При исчезновении порядка не всегда следует обнулять результат.

11

1.4.Правила записи приближенных чисел.

Значащей цифрой приближенного числа называют все его цифры, начиная с первой ненулевой справа. Примеры: 0.0103; 0.01300; 2.034.

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

Пример: a=0.010300. Имеем 5 значащих цифр. Если Δ=2 10-6, то

4 из них верные. При Δ=1 10-6 все 5 значащих цифр будут верными.

Пусть a=0.99999, = 10-5. То есть точное значение числа равно

1. В этом случае все 5 значащих цифр будут верными.

Связь количества N верных значащих цифр с величиной относительной погрешности δ:

δ≤(10N-1-1)-1≈101-N.

Для того, чтобы число содержало N верных значащих цифр достаточно выполнить неравенство δ≤(10N+1)-1≈10-N.

1.5.Корректность и обусловленность задач и алгоритмов.

Задача корректна, если выполнены следующие условия: 1.Решение y Y существует при всех x X.

2.Решение единственно.

3.Решение устойчиво к малым вариациям входных данных.

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

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

12

уравнения. Если потребовать вычисления всех корней при условиях a, b, c R; x C, то задача окажется корректной

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

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

δ(y)≤νδδ(x), где νδ –относительное число обусловленности.

Грубая оценка такова, что, если νδ ≈ 10N, то N есть число верных значащих цифр, которые могут быть утеряны в решении по сравнению с входными данными.

Задача хорошо обусловлена, если заданные погрешности входных данных отвечают приемлемым погрешностям решения.

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

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

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

1. Возможность преобразования любого x X в y Y.

2. Результат y устойчив по отношению к погрещностям исходных данных x (малым приращениям "x" соответствуют приращения "y" того же порядка малости).

3. Результат обладает вычислительной устойчивостью.

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

13

2.Конечные, разделенные разности и сеточные функции.

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

2.1. Конечные разности и их свойства.

Пусть задана сеточная функция с равноотстоящими узлами: y(xi) = yi , xi = x0 +ih, x [a,b], i = 0, 1,…,n, h=(b-a)/n, x0 = a.

Тогда, конечные разности j – ого порядка в узле xi ∆j y(xi) (j=0,..,n) определяются рекуррентными соотношениями:

∆ y(xi) = ∆ yi = yi+1 – yi , i = 0,1,…,n-1;

∆2 y(xi) = ∆2 yi = ∆ yi+1 - ∆ yi , i = 0, 1,…,n-2;

………………………………………………..

∆j y(xi) = ∆j yi = ∆j-1 yi+1 - ∆j-1 yi , i = 0, 1,…,n-j;

…………………………………………………

∆n y(xi) = ∆n yi = ∆n-1 yi+1 - ∆n-1 yi , i = 0;

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

i	xi	yi	∆ yi	∆2 yi	∆3 yi	∆4 yi	…….
0	x0	y0	∆ y0	∆2 y0	∆3 y0	∆4 y0
1	x1	y1	∆ y1	∆2 y1	∆3 y1
2	x2	y2	∆y2	∆2 y2
3	x3	y3	∆ y3
4	x4	y4
…..	……	……	…….	……	…….	……..	……..
				14

Выясним взаимосвязи между конечными разностями и

значениями сеточной функции.

1. Рассчитаем yi через конечные разности в нулевом узле,

используя очевидные соотношения:

yi = yi-1	+ ∆yi-1	(*);
∆k-1 yi = ∆k yi-1 + ∆k-1 yi-1 , (**)
Из (*)	y1 = y0 + ∆y1 .
При i = 2 из (*)		y2 = y1 + ∆y1 . Подставляя ранее рассчитанное
y1 , имеем y2	= y0 + ∆y0 + ∆y1 .
Из (**) при i=1, k=2 получаем ∆ y1 = ∆2 y0 + ∆ y0 .
Таким образом,		y2=y0 +2∆ y0 + ∆2 y0 .

Аналогичным образом получим: y3=y0 +3∆ y0 +3 ∆2 y0 + ∆3 y0 .

Найденные соотношения используются в качестве базы для

доказательства по индукции следующего общего результата

		i		i!
	yi	Cik k y0 ; Cik				биномиальные коэффициенты; Cik 0, при i<k;
				k!(i k)!
		k 0
	Ck Ci k		; 0 y y .
	i	i	0 0

2.Рассчитаем ∆i y0 по известным значениям сеточной функции.

∆y0 = y1 - y0 ;

∆2 y0 = ∆ (y1 –y0 ) = y2-y1-(y1-y0)=y2-2y1+y0; ∆3 y0 =∆ ( y2-2y1+y0)=y3-3y2+3y1-y0.

Отсюда по индукции

i

i y0 ( 1)i k Cik yk .

k0 k

k yi ( 1)k l Ckl yi l .

l 0

15

Упражнение 1.

Разработать блок схему алгоритма расчета конечных

разностей.

2.2.Разделенные разности и их свойства.

Задана сеточная функция fi=f(xi); i=0,1,…,n; x					[a,b].
Шаг сетки произволен. Нумерация узлов произвольная,
необязательно в порядке возрастания аргумента.
Разделенные разности k – ого порядка в узле xi					f(xi,xi+1,…xi+k)
(k=1,..,n) определяются рекуррентными соотношениями:
f (x , x	)	f (xi 1) f (xi )	,	i=0, n 1;
i i 1		xi 1 xi

f (x , x	, x	)	f (xi 1, xi 2 ) f (xi , xi 1)	,	i=0, n 2;
i i 1	i 2		xi 2 xi

…………………………………………………………

f (x , x	,..., x	)	f (xi 1,..., xi k ) f (xi ,..., xi k 1)	,	i=0, n k;
i i 1	i k		xi k xi

………………………………………………………………….

f (x ,..., x )		f (xi 1,...., xn ) f (xi ,..., xn 1)	, i=0.
i	n	xn xi

Для расчета разделенных разностей удобно использовать

таблицу:

16

i

xi

fi

f(xi,xi+1)

f(xi,xi+1,xi+2)

f(xi,…,xi+3)

0

x0

f0

f(x0,x1)

f(x0,x1,x2)

f(x0,…,x3)

1

x1

f1

f(x1,x2)

f(x1,x2,x3)

2

x2

f2

f(x2,x3)

3

x3

f3

……….

…………

…………

…………

………..

………..

Справедливы следующие соотношения:

n

f (xi )

1. f (x0 ,..., xn )

(x

x )...(x x

)(x x

i 0

)...(x x )

i

0

i

i 1

i

i 1

i

n

i n

f (xi )

.

n

i 0

(xi xk )

k 0,k i

Доказательство

f (x , x )

f (x0 )

f (x1)

;

0

1

x0 x1

x1 x0

f (x , x , x )

f (x0 , x1)

f (x1, x2 )

, f (x , x )

f (x1)

+

f (x2 )

. Таким образом,

0

1

2

x0 x2

x2 x0

1

2

x1 x2

x2 x1

f (x0

, x1, x2 )

f (x0 )

f (x1)

(x0 x1 )(x0

x2 )

(x1 x0 )(x0 x2 )

f (x1)

f (x2 )

.

(x x )(x x )

(x x )(x x )

1

2

2

0

2

1

2

0

После приведения подобных членов получим

f (x0 , x1, x2 )

f (x0 )

f (x1)

f (x2 )

.

(x0

x1)(x0 x2 )

(x1

x0 )(x1

x1)(x2 x0 )

x2 ) (x2

17

Полученные соотношения, рассматриваемые в качестве базы

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

.

2. Справедливо следующее соотношение

f (xn ) f (x0 ) (xn x0 ) f (x0 , x1) (xn x0 )(xn x1) f (x0 , x1, x2 ) ...(xn x0 ) xn x1)...(xn xn 1) f (x0 , x1,..., xn .

Доказательство.

Очевидно f(x1)=f(x0)+(x1-x0)f(x0,x1).

Произведем расчет f(x2).

f (x , x )		f (x2 ) f (x1)	f x		, x	x		x		f x		, x	, x		;
				0			2		0		0			2
1	2	x2 x1			1							1

f (x2 ) f (x1) (x2 x1)f x0 , x1 x2 x0 (x2 x1)f x0 , x1, x2 ;

Подставляя найденное ранее значение f(x1), получаем

f (x2 ) f (x0 ) (x2 x0 )f x0 , x1 x2 x0 (x2 x1)f x0 , x1, x2 ;

Используя последнее соотношение в качестве базы индукции,

имеем

i	k 1
f (xi ) f (x0 ,..., xk ) k x , k x (xk x j ), i=1, n, что и
k 0	j 0

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

Упражнение 2. Разработать блок схему алгоритма расчета разделенных разностей.

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

f (x) 2x3 x2 3x 1.

18

hii!

i		xi	fi	f(xi,xi+1)	f(xi,xi+1,xi+2)	f(xi,…,xi+3)
0		-1	-7	5	3	2
1	1		3	14	13	2
2	2		17	53	11
3	4		123	31
4	0		-1	……..	……….	……….

Дополнительные свойства разделенных разностей.

1.Разделенная разность f(xi,…,xi+k) является симметричной функцией своих аргументов ( т. е. её значение не меняется при любой перестановке аргументов).

2.Связь разделенных и конечных разностей:

f (x0 , x0 h,..., x0 ih) i y0 , i=1, n.

Приведенное соотношение легко доказывается, если

разделенные разности строить на равномерной сетке с шагом h.

3. Связь разделенных разностей и производных образующей

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

Для установления такой связи обратимся к следующему

утверждению.

Утверждение. Пусть x0, x1,…,xn [a,b] – узлы на интервале

	[a,b], а f(xk) сеточные функции, причем f(x)			Cn		. Тогда
				[a,b]
	разделенные разности и производные функции f(x) связаны
	повторным интегралом вида
	1	t1	tn 1	(n)		n
	f (x0 , x1,..., xn ) dt1	dt2... dtn f			ti (xi
				x0			xi 1) .
	0	0	0			i 1

Доказательство проводится индукцией по параметру n.

19

	1	f (x1) f (x0 )
	dt1 f (1) (x0 t1(x1 x0 ))		f (x0 , x1 ).
	0	x1 x0

Аналогично для n=2

1	t1
dt1 dt2 f (2) (x0 t1 (x1 x0 ) t2 (x2 x1 ))
0	0
	f (x1, x2 ) f (x0 , x1)	f (x , x , x ).
	0		1	2
	x2 x0

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

Рассмотренное интегральное соотношение есть частный случай

1	t1	tk 1		k
формулы f (xi ,..., xi k ) dt1	dt2... dtk		f (k ) xi	tk (xi j
0	0	0		j 1

xi j 1) .

Упражнение 4. Проверить справедливость интегрального соотношения для порождающей функции f (x) 2x3 x2 3x 1для второй разделенной разности в точке x1=1 .

Из доказанного утверждения следует, что

		f (x , x ,..., x )		f (n) ( )	,	[a,b].
		0 1	n	n!
Справедливость последнего соотношения становится понятной,
если n раз воспользоваться теоремой о среднем и записать
1	t1	tn 1	(n)	n				1	t1	tn 1
f (x0 , x1,..., xn ) dt1	dt2... dtn f						(n)	dt1	dt2	... dtn .
			x0 ti (xi			xi 1) f
0	0	0		i 1				0	0	0

4. Вследствие свойств 2 и 3, для конечной разности получаем

∆ny0 =hnf(n)(ξ), ξ [a,b].

20