gos / шпоры / ЧМ

6. Нахождение собственных чисел при помощи QRразложения. Основные свойства полученной последовательности подобных матриц.

Нахождение всех у матрицы при помощи QR – разложения.

Первоначально матрицы надо привести к виду Хессенберга. После этого можно запускать итерационный процесс.

A(1) Q(1)R(1) -- раскладываем

A(2) R(1)Q(1) -- перемножаем

A(2) Q(2)R(2) -- раскладываем

A(3) R(2)Q(2) -- перемножаем

…

Делаем, пока сумма квадратов элементов на диагонали не станет значительно больше суммы квадратов элементов под диагональю; либо пока матрица не перестаёт меняться (этот второй критерий используется, если есть комплексно-сопряжённые ).

Свойства метода.

Свойства итерационной последовательности (А(i)).

1)В пределе получается верхне-блочнотреугольная матрица, в которой на диагонали стоят в порядке убывания, а блоки 2*2 соответствуют комплексно-сопряжённым .

2)Если исходная была симметричная матрица (при действительных ), то получится диагональная матрица, если не симметричная, то треугольная.

Скорость сходимости определяется тем, как стремятся к нулю недиагональные элементы:

				j			n
	aij 0	как					т.к. i	j , то i 1
			i
	i j
	при n

Все поддиагональные элементы на каждом шаге уменьшаются, что приводит к уменьшению суммы квадратов элементов под диагональю.

11

7. Нахождение собственных чисел при помощи QR-разложения со сдвигом.

Нахождение всех у матрицы при помощи QR – разложения со

сдвигом.

(100,101,105,110)

100				n	(0,99)n	Это пример, когда обычный метод QR-разложения
Скорость
	101

работает медленно.

Алгоритм разложения со сдвигом:

A(i) liE Q(i)R(i) -- раскладываем

A(i 1) R(i)Q(i) liE -- перемножаем где li -- некоторые числа.

Свойства метода, свойства полученной последовательности матриц1) тот же (В пределе получается верхне-блочнотреугольная матрица, в

которой на диагонали стоят в порядке убывания величины -l, а блоки 2*2 соответствуют комплексно-сопряжённым .)

						l			n
					j
2) скорость сходимости: a i j 0 так же, как										0
						l
					i

	5		n	0,5 n -- быстрее, чем у
Если l const, напримерl 100 , то скорость
i	10
обычного метода
Если l1 1;l2 2;...;	то после (n-1) итерации все аij = 0.

12

8. Численное решение обыкновенных дифференциальных уравнений методом Рунге-Кутта 4-го порядка. Критерии точности и сходимости. Выбор оптимальной величины шага интегрирования.

Метод Рунге-Кутта 4-ого порядка. Общая часть: Поставка задачи.

1) Задача Коши

	dy		f (x, y)
	dx
	y(x			0) y
			0	0

2) Система ДУ

d y f (x, y)dx

y(x0) y0

dy
		1						f (x , y , y								,..., y				)
dx								1		1			1	2				n
dy			2
								f		(x , y , y							,..., y				)
dx									2			1	1		2				n
...
dy			n
								fn (x1, y1, y2,..., yn )
dx
y (x							) y
1						0				10
y		2		(x				) y			20
							0
...
								) y
y		n		(x								n0
							0

3) Уравнение с высшими производными

	(n)					| 11		(n 1)
y			F (x, y, y , y ,..., y						)
y(x		) y
	0			10
	|		) y						тоже Задача Коши, как 1) и 2)
y (x					20
	0
...
	(n 1)			(x )		y
y
				0			n0

1), 2), 3) – одно и тоже (один вид постановки задачи может быть преобразован к другому)

Пример этого преобразования:

13

Для системы 5-ого порядка:

y	y		dy
1					1			y
		|							2
y2 y			dx
			dy			2
	y11							y
y
			dx						3
3
	111		...
y4 y			dy
y y IV					5			F (x, y , y			, y , y		, y )
			dx						1	2	3	4	5
5

k1 h f xi , yi

Алгоритм Рунге-Кутта:

h

k

k

h f x

, y

1

2

i

2

i

2

h

k

2

k h

f x

, y

3

i

2

i

2

k4 h f xi h, yi k3

Тогда,

y

1

k

2k

2k

k

i

1

6

1

2

3

4

Для системы: всё точно также, только стоят вектора над k, f, y.

Распишем вектора в нормальном виде.

При описании k надо не забыть, что это 2-мерная матрица 4*n:

k11 h f1 xi ,					i
		y
k12 h f2	xi ,						i
				y
...	xi ,
k1n h fn							i
				y
k21 h f1								h
	xi										, y1
								2
											i
									h
k22 h f2 xi											, y1
								2
											i

...

	k						k
	11			, y2			12			,...
	2						2
					i
		k						k
		11		, y2				12		,...
	2						2
						i

14

	Критерий устойчивости:	10 100		f (x, y)
		h		y

Критерий точности:

1

f (x, y)

h

y

f (x, y)

(Для многомерного случая вместо

берется max

у матрицы частных

производных

f (xi , y)

)

y

y j

Критерий увеличения (уменьшения) шага: (при динамическом определении шага)

k 2 k 3

Crit

k1 k 2

если crit > порог 1, то надо уменьшить шаг, если Crit < порог 2 < порог 1, то можно шаг увеличить.

								Алгоритм:
1)	Считаем max						у матрицы частных производных в x0 , y0
2)	Берём h1	1
		max
3)	Делаем 1-ый шаг и считаем							Crit	k2 k3
									k	k
								1			2
4)	Устанавливаем пороги: пороги Crit1									20%

15

9. Численное решение обыкновенных дифференциальных уравнений методом прогноза и коррекции. Области применимости метода.

Метод прогноза и коррекции 4-ого порядка.

Таких методов много, отличаются значением коэффициентов коррекции.

Алгоритм:

1) Считаем x1, y1 , x2 , y2 , x3 , y3 методом RK4 (первые 3 шага)

Дальше собственно метод:

Делаем расчёты, исходя из прогноза, для которого нужна основа, например, 4 точки (поскольку метод 4-ого порядка) в качестве начальных условий.

2)Расчёт предсказания: Pi 1 yi 3 43h 2 f i f i 1 2 f i 2

3)Изменение предсказания: mi 1 Pi 1 2928 Pi Ci

4)Изменение производной: ei 1 f xi 1, mi 1

5)Коррекция: Ci 1 yi 1 h3 ei 1 4 f i f i 1

6)Значение y в точке xi+1: yi 1 Ci 1 291 Pi 1 Ci 1

Гарантированная погрешность.

Свойства:

1)2 раза расчёт f на каждом шаге (остальные f рассчитаны ранее)

2)Погрешность < a = o(h5)=

Достоинства метода: 1) маленькая погрешность 2) всего 2 раза высчитываем функцию.

Недостатки метода: не может работать самостоятельно, сначала надо прорешать несколько шагов методом RK.

16

10. Метод прогонки для решения систем линейных алгебраических уравнений с трехдиагональной матрицей. Решение трёх-диагональных СЛАУ методом прогонки.

a x			b x			c x				f
	i i 1			i i			i i 1				i
i	1,2,..., n 1
b x		c			x	f		0
	0 0			0 1						граничные условия III рода
				b x			f
a	x
n n 1					n n				n

Решение (алгоритм):

Ищем решение в виде: xi 1 i xi i , где i

и i неизвестные пока функции.

Подставим xi 1 i xi i в исходную систему:

ai (i xi i ) bi xi ci xi 1 fi

x

ci

x

1

ai i fi

i

bi

i

bi ai i

ai i

xi 1 i xi i

i 1

ci

bi

ai i

i 1

ai i fi

bi

ai i

1, 1

берутся из 1-ого начального условия:

b0x0 c0x1 0

x

c0

x

f0

0

b0

1

b

0

1 1

17

Алгоритм.

1)Находим 1, 1 из 1-ого начального условия.

2)Прямая прогонка: i = 1, 2, …, n-1

cчитаем все i+1 и i+1

3)Из последнего начального условия находим xn

4)Обратная прогонка: i = n, n-1, …, 1

xi 1 i xi i
x	1			x		n
n				n n
	x		b x		f
a							n
n	n 1			n n

an nxn n bnxn fn

	xn		fn an n
			an n	bn

18