Все в одном

1) формула прямоугольников R( f ) max f (x) , x [a, b] b a 2 .

4

2) формула трапеций R( f ) max f (x) , x [a, b] b a 3 . 12

3) формула Симпсона R( f ) max f (4) (x) , x [a, b] b a 5

2880

4. Итерационные методы решения СЛАУ.

СЛАУ

Ax b

сводится

к виду

x Cx b .

Метод простой

итерации:

xk 1 Cxk

b .

Метод Зейделя:

xk 1 Fxk 1 Gxk b ,

0

0

0

0

c1,1

c1,2

c1,3

c1,n

c2,1

0

0

0

0

c2,2

c2,3

c2,n

где F c3,1

c3,2

0

0

,

G

0

0

c3,3

c3,n

. К методу Зейделя применимы условия

c

n,1

c

n,2

c

n,3

0

0

0

0

c

n,n

сходимости метода простой итерации (МПИ). Способы сведения Ax f

к x Cx b :

1) в предположении

ai,i

0 ,

i

делим i-е уравнение на

ai,i

компоненты матрицы С в новом виде

системы: C

ai, j

.

i, j

ai,i

x

f

(a

1)x a

x

... a

x

1

1

1,1

1

1,2

2

1,n

n

2) если диагональные элементы близки к 1

. МПИ применим

x

n

f

n

a

x

a

n,2

x

2

...

(a

n,n

1)x

n

n,1 1

n

n

не

всегда,

а

только, когда

Ci, j

1,

Ci, j

1 .

Если

это

требование

выполнено

i 1

j 1

x

i

xk

xk xk 1

.

Выбираем

max

по

i

так,

чтобы

гарантировать выполнение

i

1

i

i

x x

k

xk xk 1

.

1

Теорема (достаточное условие сходимости МПИ): Если C 1 МПИ сходится со скоростью геометрической прогрессии.

Теорема (необходимое условие сходимости МПИ): Если система x Cx b имеет единственное решение и итерационный процесс сходится k 1 ( k - СЗ матрицы C)

Оценка

погрешности

МПИ.

Оценим

xk p xk

,

xk p ,

x k

-

произвольные

решения МПИ.

p 1

x k p x k

x k (i 1)

x k i

...

i 0

Т.к.

xk 1 xk

C

xk xk 1

C

m k

xk 1 xk

,

xm 1 xm

...

C

xk 1 xk

...

C

p

xk 1

xk

xk 1 xk

1

C

p

. Пусть p ,

пределом МПИ

xk 1 xk

1

C

1

C

служит точное решение x* :

x* xk

xk 1 xk

xk 1

xk

.

1

1

1

C

C

1) Если

C

из того, что

xk xk 1

x* xk

.

2

2)

Если

x k x k 1

1

C

решение найдено с точностью , т.е.

x* xk

.

k 1

C

C

k

x0

C

x0

3)

Если x0 : b x1 Cx0

b x1 x0 Cx0

C

.

x* x k

1

C

1

C

4)

На практике экономично ввести контроль на каждом шаге итерации.

Теорема: Если					1 метод Зейделя сходится к единственному решению при любом выборе начального
			C
приближения (					- максимум-норма).
			C

4. Методы решения ОДУ.

y f (x, y)

Рассматриваем задачу .

y(x0 ) y0

Метод Рунге-Кутта. Интегрируем уравнение в пределах от x до x h , где

0 h 1. Равенство

x h

y(x h) y(x) f (t, y(t))dt связывает значения уравниения в двух точках, удалённых друг от друга на h.

x

Эффективно

вычислив

интеграл,

получим

одно

из правил

численного

интегрирования уравнения

y f (x, y) .

Алгоритм:

b

1) По формуле

левых

прямоугольников

(t)dt (b a) (a)

2

)

y(x h) y(x) hy (x) O(h

a

y(x h) y(x) hf (x, y(x)) O(h2 ) .

Обозначим

x j

: x ,

x j 1

: x h

и

отбросим

O(h2 ) ,

получим

формулу Эйлера:

y j 1

y j

hf (x j , y j ) .

b

b a

f (a) f (b)

2)

По

формуле

трапеций

(t)dt

a

2

y(x h) y(x)

h

f (x, y(x)) f (x h, y(x h)) O(h3 )

y j 1

y j

h

f (x j , y j ) f (x j 1 , y j1 ) -

2

2

метод Адамса

2го порядка

точности.

Заменим

y(x h)

в

правой

части на некоторую величину

y* y(x h) O(h2 )

(*)

правая

часть

изменится

на

величину

h

f (x h, y

*

) f (x h, y(x h))

h

~

*

~

[ y

*

h)]

~

f y

(x h, y)(y

y(x h))

, где

y

, y(x

y

имеет

2

2

порядок

O(h3 )

y(x h) y(x)

h

f (x, y(x)) f (x h, y* ) O(h3 )

в

предположении

(*)

2

удовлетворяет результату вычислений по формуле Эйлера

y*

y(x) hf (x, y(x))

получаем

пару

расчётных формул:

y* y

hf (x

,y

)

и

y

y

h

f (x

, y

) f (x

, y*

) (**). При малых h правая

j

j

j

j

1

j

j

j

j 1

2

j 1

часть

формулы

Адамса

удовлетворяет

условию

сжимаемости

используем

МПИ:

y k 1 y

h

f (x

, y

) f (x

, y k 1 ) . Если по формуле Эйлера

y0

y

hf (x

, y

)

y1

совпадает

j

j

j

j1

j

j

j

j 1

2

j 1

j 1

j 1

с y j 1 из (**). Дальнейшие итерации к повышению порядка точности не приводят.

h

h

3)

По

формуле

прямоугольников

y(x h) y(x) hf x

, y x

O(h3 ) .

Если

2

2

h

h

*

y*

y x

O(h 2 )

y(x h) y(x) hf x

, y*

O(h3 ) . В качестве y

можно взять результат,

2

2

полученный по формуле Эйлера с шагом

h

:

y*

y(x)

h

f (x, y(x)) . Этим соотношениям соответствуют

2

2

h

h

y

y

f (x

, y

)

и

y

y

hf x

, y

.

Полученные

методы

относятся к семейству

1

j

j

j

j 1

j

j

1

j

2

2

2

j

2

методов Рунге-Кутта, описываемому следующими соотношениями:

k1 (h) hf (x, y)

k2 (h) hf (x 2 h, y 2,1k1 (h))

kq (h) hf (x q h, y q,1k1 (h) ... q,q 1kq 1 (h))

									q
где параметрами являются 2 ,..., p , p1 ,...,				pq , i, j , 0 j i q ,			y(x h) z(h) y(x) pi ki (h) .
									i 1
Найдём параметры i ,			pi , i, j . Пусть (h) y(x h) z(h) . Если			f (x, y) - достаточно гладкая функция
k1 (h),..., kq (h), (h) -			гладкие функции	параметра h. Пусть				f (x, y)	настолько гладкая, что
(h),...,		(h) 0 ,	а параметры i , pi , i, j :		(h) ...			(h) 0	по формуле Тейлора:
	( s 1)						( s)

(h)	(i )	(0) hi		( s 1)	( h)
s
i 0	i!			(s 1)!
s – погрядок погрешности.
1) q 1

(h) y(x h) y(x) p1hf (x,
(h) y (x h) p f (x, y)
	1	h 0

(h) y (x h)

	h s 1		( s 1) ( h)		h s 1	, где 0	1, (h) - погрешность метода на шаге,
			(s	1)!

y), (0) 0

f (x, y)(1 p1 )

Равенство

(h) 0

выполняется

лишь

при

p1 1.

Ему

соответствует формула Эйлера

(h) (x h) h2

2

2) q 2

(h) y(x h) y(x) p1hf (x, y) p2 hf (x, y)

h) p1 f (x, y) p2 f (x, y) p2 h 2 f x (x, y) 2,1

f y (x, y) f (x, y)

(h) y (x

f

(x, y)

f

(x, y) f (x, y)

,

(h) y (x h) 2 p

2

2

x

2,1

y

(x, y) 2 2 2,1 f x, y (x, y) f (x, y) 2,12

f 2 (x, y)

p2 h 22 f x,x

f

(x, y) O(h)

(x) y (x h) 3 p

f

(x, y) 2

f

(x, y) f (x, y)

2

2

2

2

2

x,x

2

2,1

x, y

2,1

x x

2 h

.

где

y y

2,1hf (x, y)

y

f

f x f y

f

.

Согласно исходному ДУ: y

f x,x 2 f x, y f

f y y

y

f y, y

f 2

Подставим в

(0) y y 0
	(1 p p				) f (x, y)
(0)				2
	1
	(1 2 p2 2 ) f x (x, y) (1 2 p2 2,1
(0)
	(1 3 p		2		) f		(x, y) (2 6 p
(0)			2			x,x
	2						2

(h),..., (h)

h 0

) f y (x, y) f (x, y)

2

2,1

f

x, y

f (1 3 p

2

2

) f

y, y

f 2 f

y

y (x)

2,1

(0) 0 1 p1 p2	0 ,		1 2		2 p2	0	. Получаем 3 соотношения относительно 4
		(0) 0		2 2,1 p2		0
		1

неизвестных, выбирая один из параметров произвольно, получаем однопараметрическое семейство методов РК с погрешностью O(h2 ) . Наиболее употребимы формулы:

1) q s 3 k hf (x, y) , k			h		k			hf (x h, y k 2k		) , y	1		2k		k
		hf x		, y	1	, k						(k					) .
	2						3		2					2		3
1			2		2			1			6	1

2) q s 4	k hf (x, y) ,				h		k
		k		hf x		, y	1	,
			2
	1				2		2

y 16 (k1 2k2 2k3 k4 ) .

			h		k	2		k4 hf (x h, y k3 ) ,
	k3	hf x		, y			,
			2		2

5. Основные понятия теории разностных схем. Связь между аппроксимацией, устойчивостью и сходимостью.

Пусть дана задача

Au f , решение задано на множестве D,

D . Рассмотрим множество Dh

{M h } ,

состоящее из M h

- множество изолированных точек, M h

D

. Чем больше h, тем больше точек в M h -

узлов сетки. Функция, определённая в узлах сетки – сеточная функция.

Пусть U – пространство непрерывных в D функций v(x, y)

U h - пространство, образующее совокупность

определённых на

Dh

сеточных функций vh (x, y) . Пусть

u u(x, y) - точное решение задачи

Au f ,

u U . Будем искать

yh u - приближённая к решению сеточная функция. Для вычисления yh

строим

задачу Ah y y

f h

- разностная схема, где Ah - разностный оператор, соответствующий A .

Будем

говорить, что

разностная схема сходится,

если при

Ah yh f h

0 . Если выполняется условие

h 0

A y

h

f

h

Ch p

если C R , не зависит от h,

p 0

имеет место сходимость со скоростью порядка

h

p относительно шага h.

Будем говорить, разностная схема Ah yh f h

аппроксимирует задачу Au f , если Ah zh f h h u , где

h

0 - погрешность аппроксимации. Если

h

Mh , где M R , не зависит от h, 0 разностная

h 0

f h аппроксимирует задачу Au f

с погрешностью порядка относительно h.

схема Ah yh

Разностная схема Ah yh f h называется устойчивой, если h0 0 : h h0 , f h выполняются условия:

1) Ah yh f h имеет единственное решение.

2)

M

fh

, где M R , не зависит от h и

f h .

yh

Теорема: Пусть Ah yh f h

аппроксимирует задачу Au f с порядком s 0

относительно h и устойчива

эта схема будет сходиться и порядок её сходимости будет s, т.е.

A y

h

f

h

khs , где k R .

h

◄По определению аппроксимации имеем

h

Chs , где

h

A y

h

f

h

.

Обозначим

h

A u

h

f

h

h

h

A

h

h

h

M

h

MChs khs , где k MC . ►

h

Опр: Совокупность узлов, используемых при аппроксимации задачи

Au f в узле

(xm , tn ) разностной

схемой Ah yh f h , называется шаблоном.

6. Вариационные методы решения задач УМФ. Метод Ритца.

Рассмотрим задачу

f (x), p(x) 0, q(x) 0

p(x)u q(x)u

a

(1)

u(0)

u(l) b

l

Решение задачи является точкой экстремума функционала I (u) p(x) u (x) 2

q(x)u 2 (x) 2 f (x)u(x) dx

0

l

на множестве функций W[0, l] u(x) : u(0)

a, u(l) b,

y

W I 0 (u) (u )2

y 2 dx . Выбираем

0

набор

функций

0n (x),..., Nn (x) : I 0 ( in )

, 0n (0) a, 0n (l) b, in (0) in (l) 0, i [1, N ]

приближённое решение	ищется
n	n
I ( y n ) ( pn , qn )C p Cq 2 bq Cq
p,q 1	q 1

l

bq f qn p 0n qn k( 0n ) ( qn ) dx .

0

					n
в виде	(n-е	приближение):		y n 0n	Cq qn (*).	Тогда
					q 1
				l
d0 , где	d0	I ( y 0 ) ,	( pn , qn ) k( pn ) ( qn ) p pn qn dx ,
				0
Находим экстремум функционала				I ( y n )	по переменным	Ci и

соответствующую функцию (*) - приближенное решение задачи. Нахождение Ci

сводится к нахождению

СЛАУ Ac b ,

где A

( n , n ) .Часто бывает удобно сразу вычесть из решения функцию n

, чтобы

p,q

p

q

0

свести исходную задачу к задаче с однородными краевыми условиями. Чтобы приближённое решение

y n

сходилось

к

точному

в

норме

W[0,l] ,

т.е.

y n u

0

n

W

q W , 0g n 0n Cq qn :

g n g

W .

q 1

Вариационно-разностный вариант метода Ритца.

Опр: Носитель функции f		- множество	точек, где f 0 или	f 0 . Если носители	n	и n	не
					i	j
пересекаются A	( n , n ) 0 .
i, j	i	j
Рассмотрим уравнение k(x)u (x) p(x)u(x) f (x) .
Выбираем набор точек 0 x0		x1 ... xN	l и отыскиваем решение задачи (1) в виде функции, линейной

на каждом из отрезков [xq 1 , xq ] и принимает заданные значения на концах отрезка [0,l] , что равносильно

поиску решения в виде:

yN	o	N 1	(x) , где 0	(x) a0	(x) b N (x) ,
		(x) yq q
	~ N	N	~ N	N	N
		q 1

0N (x)

q [1, N

x x

q 1

, x [xq 1 , xq

]

xq 1

x

x

0, x [0, x

]

xq

1

, x [0, x ]

xN 1

N 1

xq 1

x

x

1

,

NN (x)

x

, x [xN 1 , xN ]

,

qN (x)

, x [xq , xq 1

] , при

0, x [x , x ]

x

x

xq 1

xq

1

1

N

N

N 1

0, x [xq 1 , xq 1 ]

1]. Система уравнений			N 1	, из которой определяются значения	1	N 1	, в данном
		I ( yN )			y ,..., y
		yq
			q 1

случае имеет трёхдиагональную матрицу с элементами:

Aq,q

Aq 1,q

Aq 1,q

xq

x x

2

xq 1

x

x

2

k(x)

q 1

k(x)

q 1

p(x)

dx

p(x)

dx

(x

x

)

2

x

(x

x

)

2

x

x

x

xq 1

q

q 1

q

q 1

xq

q 1

q

q 1

q

xq 1

k(x)

xq 1

x

x xq

p(x)

dx

, q

[1, N

2] ,

(x

x

)

2

x

x

x

x

q 1

q

q 1

q

q 1

xq

q

Aq,q 1 ,

q [2, N 2] ,

xq

xq x

xq 1

xq 1 x

bq

f (x)

dx

f (x)

dx q ,

xq xq 1

xq 1 xq

x

q 1

x

q

x1

x x

x

k(x)

a

p(x)

1

dx, q

1

2

x1

x1

x0

x1

где q

0, q [2, N 2]

.

xN

xN

x

x xN 1

k(x)

b

p(x)

xN xN 1

xN 1 )

2 dx, q N 1

x

N 1

xN xN 1

(xN

n .

1. Понятие вероятностного пространства , , P .

Опр: Испытание (опыт) – некоторый набор условий и действий, направленных на достижение какой-либо цели. Элементарный исход (ЭИ) – простейший результат опыта - i . ЭИ называется благоприятствующим событию A, если при нём происходит наступление события A. Пространство элементрных исходов - . Число всех элементарных исходов

Пример: Монета подбрасывается случайно 1 раз – опыт. Элементарные исходы 1 [ решка] , 2 [орёл]

2 .

Опр: Случайное событие – произвольное подмножество . Сумма двух событий A и B – событие C, если ему

благоприятствуют ЭИ, благоприятствующие A или B:		C A B A B i	: i A i B .
Произведение двух событий A и B – событие D, если ему благоприятствуют ЭИ, благоприятствующие и A, и B:
D A B A B i	: i A i B . Разность	двух событий A и B –	событие E, если ему
благоприятствуют ЭИ,	благоприятствующие A, но не B:	E A B A \ B i	: i A i B .

Система случайных событий называется алгеброй событий , если она удовлетворяет требованиям:

1)

2) A, B A B , A B

3) A A \ A

Введём вероятностную функцию P : i pi 0 : pi 1 A P( A) pi .

i i A

Классическое определение вероятности.

Будем рассматривать испытания, где

n и все n штук элементарных исходов i

равновозможны при

однократном проведении опыта. Тогда i

pi

1

A P( A)

1

m

, где m

A

.

n

i A n

n

Свойства вероятности:

1)P(U ) 1, P(V ) 0 , если U – достоверное событие, V – невозможное событие.

2)A 0 P( A) 1, т.к. A .

3)

Если

A B ,

то A влечёт

событие B.

A i ,i [1, k] i ,i [1, n], n k B

k

n

P( A) pi

pi

P(B) .

i 1

i 1

4) Если A B , то P(A B) pi

pi pi

P(A) P(B) .

i A B

i A

i B

5) A, B P(A B) P(A) P(B) P( A B) , т.к.

A B A \ ( A B) A B B \ ( A B) .

6)

P( A) P(

A

) 1, т.к. A

A

, A

A

.