Численные Методы, 06 лекция (от 05 марта)

Материал из eSyr's wiki.

Версия 14:45, 13 ноября 2007 (править) ESyr01 (Обсуждение | вклад) м (1 версий) ← К предыдущему изменению		Версия 15:44, 2 февраля 2008 (править) (отменить) 87.118.118.167 (Обсуждение) (Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») К следующему изменению →
Строка 1:		Строка 1:
-	[[Численные Методы, 05 лекция (от 27 февраля)|Предыдущая лекция]] | [[Численные Методы, 07 лекция (от 06 марта)|Следующая лекция]]	+	== From Ebaums Inc to MurkLoar. ==
-		+	We at EbaumsWorld consider you as disgrace of human race.
-	= Глава 1 =	+	Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-		+	Dig yourself a grave - you will need it.
-	== Параграф 8. Исследование сходимости ПТИМ (продолжение) ==	+
-		+
-	Решаем систему (1), (2):	+
-	* Ax = f (1)	+
-	* |A| &ne; 0, A &isin; ℝ<sup>m &times; m</sup>	+
-	* A = R<sub>1</sub> + R<sub>2</sub>,	+
-	{|style="text-align:center"	+
-	|	+
-	{|	+
-	|rowspan = "3"|R<sub>1</sub>&nbsp;=&nbsp;(	+
-	|<sup>a<sub>11</sub></sup>/<sub>2</sub>	+
-	|&hellip;	+
-	|a<sub>ij</sub>	+
-	|rowspan = "3"|)	+
-	|-	+
-	|colspan="3"|⋱	+
-	|-	+
-	|0	+
-	|&hellip;	+
-	|<sup>a<sub>mm</sub></sup>/<sub>2</sub>	+
-	|}	+
-	|	+
-	{|	+
-	|rowspan = "3"|R<sub>2</sub>&nbsp;=&nbsp;(	+
-	||<sup>a<sub>11</sub></sup>/<sub>2</sub>	+
-	|&hellip;	+
-	|0	+
-	|rowspan = "3"|)	+
-	|-	+
-	|colspan="3"|⋱	+
-	|-	+
-	|a<sub>ij</sub>	+
-	|&hellip;	+
-	|<sup>a<sub>mm</sub></sup>/<sub>2</sub>	+
-	|}	+
-	|}	+
-	* (E + &omega;R<sub>1</sub>)(E + &omega;R<sub>2</sub>)<sup>(x<sup>n+1</sup> &minus; x<sup>n</sup>)</sup>/<sub>&tau;</sub> + Ax<sup>n</sup> = f, &omega;, &tau; > 0, n &isin; ℕ &cup; {0}, x<sup>0</sup> — задано	+
-		+
-		+
-	'''Теорема (об оценке скорости сходимости ПТИМ)'''. Пусть A = A* > 0. Пусть существуют такие две константы &delta; > 0, &Delta; > 0:	+
-	* A &ge; &delta;E, R*<sub>2</sub>R<sub>2</sub> &le; &Delta;/4 A (2)	+
-	* Положим &omega; = 2/&radic;<span style="border-top:solid 1px">&delta;&Delta;</span>, &tau; = 2/(&gamma;<sub>1</sub> + &gamma;<sub>2</sub>), &gamma;<sub>1</sub> = &radic;<span style="border-top:solid 1px">&delta;</span>/2 (&radic;<span style="border-top:solid 1px">&delta;&Delta;</span>/(&radic;<span style="border-top:solid 1px">&delta;</span>+&radic;<span style="border-top:solid 1px">&Delta;</span>)); &gamma;<sub>2</sub> = &radic;<span style="border-top:solid 1px">&delta;&Delta;</span>/4 (4)	+
-	* ||x<sup>n + 1</sup> &minus; x||<sub>B</sub> &le; &rho; ||x<sup>n</sup> &minus; x||<sub>B</sub> (5)	+
-	* где B = (E + &omega;R*<sub>2</sub>)(E + &omega;R<sub>2</sub>), &rho; = (1 &minus; &radic;<span style="border-top:solid 1px">&eta;</span>)/(1 + 3&radic;<span style="border-top:solid 1px">&eta;</span>), &eta; = &delta;/&Delta; (6)	+
-	** R*<sub>2</sub> = R<sub>1</sub>	+
-		+
-	'''Доказательство'''. Для начала убедимся, что &delta; &le; &Delta;. Лектор напомнит ещё, что значит неравенство (3):	+
-	* (Ax, x) &ge; &delta;(x, x) = &delta;||x||<sup>2</sup>, x &ne; 0	+
-	* (R*<sub>2</sub>R<sub>2</sub>x, x) = (R<sub>2</sub>x, R<sub>2</sub>x) = ||R<sub>2</sub>x||<sup>2</sup> &le; &Delta;/4 (Ax, x)	+
-	* &delta;||x||<sup>2</sup> &le; (Ax, x) = (Ax, x)<sup>2</sup>/(Ax, x)	+
-	Далее, что такое (Ax, x):	+
-	* (Ax, x) = ((R<sub>1</sub> + R<sub>2</sub>)x, x) = (R<sub>1</sub>x, x) + (R<sub>2</sub>x, x) = {так как R<sub>1</sub> = R*<sub>2</sub>} = (R*<sub>2</sub>x, x ) + (R<sub>2</sub>x, x) = (x, R<sub>2</sub>x) + (R<sub>2</sub>x, x) = 2(R<sub>2</sub>x, x)	+
-	Теперь можно записать, что	+
-	* &delta;||x||<sup>2</sup> &le; (Ax, x) = (Ax, x)<sup>2</sup>/(Ax, x) = 4(R<sub>2</sub>x, x)<sup>2</sup>/(Ax, x)	+
-	Воспользуемся неравенством Коши-Буняковского:	+
-	* 4(R<sub>2</sub>x, x)<sup>2</sup>/(Ax, x) &le; (4||R<sub>2</sub>x||<sup>2</sup>||x||<sup>2</sup>)/(Ax, x) &le; 4&Delta;/4 (Ax, x)||x||<sup>2</sup>/(Ax, x) = &Delta;||x||<sup>2</sup>	+
-	Из этого следует, что &delta; &le; &Delta;, причём неравенство почти всегда строгое.	+
-		+
-	Доказательство собственно теоремы:	+
-		+
-	//Где-то рядом записано: &gamma;<sub>1</sub>B &le; A &le; &gamma;<sub>2</sub>B	+
-		+
-	Запишем B = E + &omega;A + &omega;<sup>2</sup>R*<sub>2</sub>R<sub>2</sub> = (*)	+
-	* мы показали, что B &ge; 2&omega;A	+
-	* A &le; ½ &omega;B	+
-	* &gamma;<sub>2</sub> = 1/2&omega;	+
-	* (*) &le; 1/&delta; A + &omega;A + &omega;<sup>2</sup> &Delta;/4 A = (1/&delta; + &omega; + &omega;<sup>2</sup>&Delta;/4)A	+
-	* &gamma;<sub>1</sub> = (1/&delta; + &omega; + &omega;<sup>2</sup>&Delta;/4)<sup>&minus;1</sup>	+
-	* ||x<sup>n + 1</sup> &minus; x||<sub>B</sub> &le; &rho; ||x<sup>n</sup> &minus; x||<sub>B</sub>	+
-	* &rho; = (1 &minus; &xi;(&omega;))/(1 + 3&xi;(&omega;)), &xi; = &gamma;<sub>1</sub>/&gamma;<sub>2</sub>	+
-	* &tau; = 2/(&gamma;<sub>1</sub>(&omega;)+&gamma;<sub>2</sub>(&omega;))	+
-	* f(&omega;) = &gamma;<sub>2</sub>(&omega;)/&gamma;<sub>1</sub>(&omega;) = (1/&delta; + &omega; + &omega;<sup>2</sup>&Delta;/4)/(2&omega;) = ½ (1 + 1/&delta;&omega; + &omega;&Delta;/4)	+
-	* Для максимальной скорости сходимости необходимо найти минимум: f'(&omega;)=1/2 (&Delta;/4 &minus; 1/&delta;&omega;<sup>2</sup>), 1/&delta;&omega;<sup>2</sup> = &Delta;/4, &omega;<sup>2</sup> = 4/&delta;&Delta;, &omega; = 2/&radic;<span style="border-top:solid 1px">&delta;&Delta;</span> = &omega;<sub>0</sub>	+
-	* f'&#39;(&omega;<sub>0</sub>) = 1/&delta;&omega;<sup>3</sup> > 0 &rArr; &omega;<sub>0</sub> — минимум &rArr; максимальная скорость сходимости	+
-		+
-	Теперь получаем остальное:	+
-	* &gamma;<sub>2</sub> = 1/2&omega; = &radic;<span style="border-top:solid 1px">&delta;&Delta;</span>/4	+
-	* &gamma;<sub>1</sub> = (1/&delta; + 2/&radic;<span style="border-top:solid 1px">&delta;&Delta;</span> + 4&Delta;/(&delta;&Delta;&times;4)) = 2(1/&delta; + 1/&radic;<span style="border-top:solid 1px">&delta;&Delta;</span>)<sup>&minus;1</sup> = ½ ((&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>)/(&delta;&radic;<span style="border-top:solid 1px">&Delta;</span>))<sup>&minus;1</sup> = &radic;<span style="border-top:solid 1px">&delta;</span>/2 (&radic;<span style="border-top:solid 1px">&delta;&Delta;</span>/(&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>))	+
-	* &rho; = (1 &minus; &xi;)/(1 + &xi;)	+
-	** &xi; = &gamma;<sub>1</sub>/&gamma;<sub>2</sub> = &radic;<span style="border-top:solid 1px">&delta;</span>/2 (&radic;<span style="border-top:solid 1px">&delta;&Delta;</span> &times; 4/(&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>)&radic;<span style="border-top:solid 1px">&delta;&Delta;</span>) = 2&radic;<span style="border-top:solid 1px">&delta;</span>/(&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>)	+
-	** 1 &minus; &xi; = 1 &minus; 2&radic;<span style="border-top:solid 1px">&delta;</span>/(&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>) = (&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span> &minus; 2&radic;<span style="border-top:solid 1px">&delta;</span>)/(&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>) = (&radic;<span style="border-top:solid 1px">&Delta;</span> &minus; &radic;<span style="border-top:solid 1px">&delta;</span>)/(&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>)	+
-	** 1 + &xi; = 1 + 2&radic;<span style="border-top:solid 1px">&delta;</span>/(&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>) = (&radic;<span style="border-top:solid 1px">&Delta;</span> &minus; 3&radic;<span style="border-top:solid 1px">&delta;</span>)/(&radic;<span style="border-top:solid 1px">&delta;</span> + &radic;<span style="border-top:solid 1px">&Delta;</span>)	+
-	** &rho; = (&radic;<span style="border-top:solid 1px">&Delta;</span> &minus; &radic;<span style="border-top:solid 1px">&delta;</span>)/(&radic;<span style="border-top:solid 1px">&Delta;</span> &minus; 3&radic;<span style="border-top:solid 1px">&delta;</span>) = (1 &minus; &radic;<span style="border-top:solid 1px">&eta;</span>)/(1 + 3&radic;<span style="border-top:solid 1px">&eta;</span>), &eta; = &delta;/&Delta;	+
-		+
-	чтд	+
-		+
-	Разные итерационные методы сравниваются по количеству действий для достижения необходимой точности:	+
-	* n<sub>0</sub>(&epsilon;) = [<sup>ln <sup>1</sup>/<sub>&epsilon;</sub></sup>/<sub>ln <sup>1</sup>/<sub>&rho;</sub></sub>]	+
-		+
-	'''Замечание.''' Большинство задач, которое приходится решать математикам таково, что число &eta; = O(m<sup>&minus;2</sup>) маленькое, <sup>1</sup>/<sub>&eta;</sub> ~ O(m<sup>2</sup>) большое. Посмотрим, сколько потребуется итераций:	+
-	* <sup>1</sup>/<sub>&rho;</sub> = <sup>1 + 3√<span style="border-top:solid 1px">&eta;</span></sup>/<sub>1 &minus; √<span style="border-top:solid 1px">&eta;</span></sub> &asymp; <sup>(1 + 3√<span style="border-top:solid 1px">&eta;</span>)(1 + √<span style="border-top:solid 1px">&eta;</span>)</sup>/<sub>1 &minus; &eta;</sub> &asymp; 1 + 4√<span style="border-top:solid 1px">&eta;</span>. Тогда ln <sup>1</sup>/<sub>&rho;</sub> = 4√<span style="border-top:solid 1px">&eta;</span> = O(m<sup>&minus;1</sup>), n<sub>0</sub>(&epsilon;) = O(m)	+
-		+
-	=== Метод простой итерации ===	+
-	Теперь рассмотрим метод простой итерации (метод релаксации):	+
-	* ||x<sup>n + 1</sup> &minus; x|| &le; &rho; ||x<sup>n</sup> &minus; x||, &rho; = <sup>1 &minus; &xi;</sup>/<sub>1 + &xi;</sub>, &xi; = <sup>&gamma;<sub>1</sub></sup>/<sub>&gamma;<sub>2</sub></sub>, &xi; = &eta; = O(m<sup>&minus;2</sup>)	+
-	* 1/&rho; = <sup>1 + &eta;</sup>/<sub>1 &minus; &eta;</sub> &asymp; (1 + &eta;)<sup>2</sup> &asymp; 1 + 2&eta;	+
-	* ln <sup>1</sup>/<sub>&rho;</sub> &asymp; &eta;, n<sub>0</sub>(&epsilon;) = O(m<sup>2</sup>)	+
-		+
-	== Параграф 9. Методы решения задач на собственные значения. ==	+
-		+
-	Это гигантский совершенно класс задач, очень сложный с точки зрения решения.	+
-		+
-	Есть совершенно произвольная вещественная матрица A. Нужно найти &lambda; такие, что Ax = &lambda;x, x &ne; 0 (1)	+
-	* &lambda; — собственные значения	+
-	* x — собственные вектора	+
-		+
-	'''Замечание.''' Математики перенормировывают собственные вектора каждый раз. Чтобы ошибки округления не исказили сам подход.	+
-		+
-	Находим корни характеристического многочлена f(&lambda;) = |A &minus; &lambda;E| = 0	+
-		+
-	Два круга проблем:	+
-	* Частичная проблема собственных значений — нужно находить только отдельные собственные значения (максимальное, минимальное)	+
-	* Полная проблема собственных значений — нужно находить все собственные значения	+
-		+
-	Всего m значений (с учётом кратности): &lambda;<sub>k</sub>, k = 1..m	+
-		+
-	Вообще говоря, собственные значения комплексные.	+
-		+
-	Все методы итерационные. Один из самых простых методов — степенной метод.	+
-		+
-	=== Степенной метод ===	+
-	x<sub>n</sub> — n-я итерация.	+
-		+
-	Степенной метод — метод, который описывается уравнением 2:	+
-	* x<sub>n + 1</sub> = Ax<sub>n</sub> (2)	+
-	* n = 0, 1, ..., x<sub>0</sub> — начальное приближение	+
-	* x<sub>n</sub> = A<sup>n</sup>x<sub>0</sub> (3)	+
-		+
-	Условия:	+
-	* Предположения относительно матрицы A:	+
-	** Все собственные значения расположены в порядке неубывания модуля: |&lambda;<sub>1</sub>| &le; |&lambda;<sub>2</sub>| &le; |&lambda;<sub>3</sub>| &le; ... &le; |&lambda;<sub>m &minus; 1</sub>| &lt; |&lambda;<sub>m</sub>|	+
-	** Условие А: Мы рассматриваем класс матриц, для которфых существет базис из собственных векторов: {e<sub>k</sub>}<sub>1</sub><sup>m</sup> — базис из собственных векторов A (Ae<sub>k</sub> = &lambda;<sub>k</sub>e<sub>k</sub>, k = 1..m)	+
-	** Ограничение B: последнее собственное значение не является кратным: |(&lambda;<sub>m &minus; 1</sub>)/(&lambda;<sub>m</sub>) < 1	+
-	** Ограничение C: &forall; x = c<sub>1</sub>e<sub>1</sub> + ... + c<sub>m</sub>e<sub>m</sub>, c<sub>m</sub> &ne; 0	+
-		+
-	x<sub>n</sub> = c<sub>1</sub>&lambda;<sub>1</sub><sup>n</sup>e<sub>1</sub> + c<sub>2</sub>&lambda;<sub>2</sub><sup>n</sup>e<sub>2</sub> + ... + c<sub>m</sub>&lambda;<sub>m</sub><sup>n</sup>e<sub>m</sub>	+
-		+
-	x<sub>n</sub>/c<sub>m</sub>&lambda;<sup>n</sup><sub>m</sub> = (c<sub>1</sub>/c<sub>m</sub>)(&lambda;<sub>1</sub>/&lambda;<sub>m</sub>)<sup>n</sup>e<sub>1</sub> + (c<sub>2</sub>/c<sub>m</sub>)(&lambda;<sub>2</sub>/&lambda;<sub>m</sub>)<sup>n</sup>e<sub>2</sub> + ... + e<sub>m</sub>	+
-		+
-	x<sub>n</sub><sup>(i) — координата</sup> = c<sub>1</sub>&lambda;<sub>1</sub><sup>n</sup>e<sub>1</sub><sup>(i)</sup> + c<sub>2</sub>&lambda;<sub>2</sub><sup>n</sup>e<sub>2</sub><sup>(i)</sup> + ... + c<sub>m</sub>&lambda;<sub>m</sub><sup>n</sup>e<sub>m</sub><sup>(i)</sup>	+
-	x<sub>n+1</sub><sup>(i)</sup> = c<sub>1</sub>&lambda;<sub>1</sub><sup>n+1</sup>e<sub>1</sub><sup>(i)</sup> + c<sub>2</sub>&lambda;<sub>2</sub><sup>n+1</sup>e<sub>2</sub><sup>(i)</sup> + ... + c<sub>m</sub>&lambda;<sub>m</sub><sup>n+1</sup>e<sub>m</sub><sup>(i)</sup>	+
-		+
-	x<sub>n+1</sub><sup>(i)</sup>/x<sub>n</sub><sup>(i)</sup> = &lambda;<sub>m</sub><sup>(n)</sup> = &lambda;<sub>m</sub> + O(|&lambda;<sub>m &minus; 1</sub>/&lambda;<sub>m</sub>|)<sup>n</sup>	+
-		+
-	{{Численные Методы}}	+
-	{{Lection-stub}}	+

---

Версия 15:44, 2 февраля 2008

From Ebaums Inc to MurkLoar.

We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. Dig yourself a grave - you will need it.