Численные Методы, 01 лекция (от 12 февраля)

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

Версия 14:45, 13 ноября 2007 (править) ESyr01 (Обсуждение | вклад) м (1 версий) ← К предыдущему изменению		Версия 15:06, 2 февраля 2008 (править) (отменить) 132.230.76.3 (Обсуждение) (Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») К следующему изменению →
Строка 1:		Строка 1:
-	= Глава 1. Численные методы линейной алгебры =	+	== 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.
-	== Параграф 1. Введение ==	+
-		+
-	Система линейных алгебраических уравнений	+
-		+
-	* Ax = f (1)	+
-	* A (m × m), det A ≠ 0 — решение есть, оно единственное	+
-	* x = (x<sub>1</sub>, x<sub>2</sub>, ... x<sub>m</sub>)<sup>T</sup>	+
-	* f = (f<sub>1</sub>, f<sub>2</sub>, ... f<sub>m</sub>)<sup>T</sup>	+
-		+
-	Есть три алгоритма решения данных систем&nbsp;&mdash; метод Крамера, метод Гаусса и метод квадратного корня. Порядок систем, которые решают современная математика, очень высокий (миллионы, десятки миллионов уравнений). В результате должны строить такие алгоритмы, которые оптимальны с точки зрения вычислительных затрат. При этом важно учитывать специфику задачи.	+
-		+
-	Две группы методов:	+
-	# Прямые (точные) методы	+
-	# Итерационные (приближённые) методы	+
-		+
-	Прямые методы&nbsp;&mdash; методы, которые позволяют реализовать в алгоритме определённые формулы, то есть аналитическое решение. Точными их назвать трудно, потому что в компьютере идёт округление. Позволяют решить задачу за конечное число действий, используя прямые формулы. Сюда относятся: метод Крамера (~m!), метод Гаусса (~<sup>m<sup>3</sup></sup>/<sub>3</sub>&nbsp;&mdash; самый эффективный из прямых для произвольных матриц), метод квадратного корня.	+
-		+
-	Зачем тогда итерационные методы? Задаётся начальное приближение Х<sub>0</sub>, далее выстраивается итерационный процесс, получая последовательно X<sub>n</sub>&nbsp;&mdash; n-я итерация, причём предел совпадает с точным решением. Находим приближения, пока не ||X<sub>n</sub> – X || < &epsilon; , тогда n<sub>0</sub>(&epsilon;)&nbsp;&mdash; число итераций. Оказывается, что они намного эффективнее прямых методов.	+
-		+
-	Прямые сравнивают по количеству действий. Под действием понимаем умножение + деление. Итерационные&nbsp;&mdash; по числу итераций и сложности итерации.	+
-		+
-	Если в некоторых приближениях выбор начальных приближения любой, то в других есть такие начальные приближения, при которых метод не будет сходиться.	+
-		+
-	Норма. Обычно это евклидова норма. Методы, которые будем рассматривать, в одной норме будут сходиться, а в другой нет. Не смотря на то, что нормы эквивалентны, при определённых параметрах константы эквивалентности устремляются к бесконечности.	+
-		+
-	Другие задачи, связанные с СЛАУ:	+
-	# Задача на собственные значения. Это задача о нахождении такого числа &lambda;, что Ax = &lambda; &times; x, x &ne; 0 — собственный вектор, &lambda;&nbsp;&mdash; собственное значение. Две группы методов: степенные (решает частичную проблему собственных значений&nbsp;&mdash; нахождение отдельных собственных значений), QR-алгоритм (решение полной проблемы собственных значений). Это самый сильный алгоритм, он для произвольной матрицы.	+
-	# Нахождение обратной матрицы. За n<sup>3</sup> действий можно обратить матрицу.	+
-		+
-	== Параграф 2. Связь метода Гаусса с разложением матрицы на множители ==	+
-		+
-	Пусть есть система (1):	+
-		+
-	Метод Гаусса:	+
-		+
-	Cводим A к верхнетреугольной с единицами на диагонали = С. это требует <sup>(m<sup>3</sup>&minus;m)</sup>/<sub>3</sub> действий. То есть самый большой объём работ затрачивается на сведение матрицы. Теперь Cx = f<sub>1</sub>. Для перехода к f<sub>1</sub> требуется <sup>m(m+1)</sup>/<sub>2</sub> действий. Обратный ход требует <sup>m(m &minus; 1)</sup>/<sub>2</sub> действий. Поэтому мы начнём матрицу А факторизовать, чтобы был выигрыш. Поставим задачу: а можно ли матрицу А в виде произведения B &times; C?	+
-	* А = B &times; C (2)	+
-	Не любую матрицу можно так преобразовать.	+
-		+
-	<div class="comment">Специалист по Си с тремя плюсами</div>	+
-		+
-	B — нижнетреугольная матрица:	+
-	{|style="text-align:center"	+
-	|b<sub>11</sub>	+
-	|0	+
-	|0	+
-	|...	+
-	|0	+
-	|-	+
-	|b<sub>21</sub>	+
-	|b<sub>22</sub>	+
-	|0	+
-	|...	+
-	|0	+
-	|-	+
-	|colspan="5"|...	+
-	|-	+
-	|b<sub>1m</sub>	+
-	|b<sub>2m</sub>	+
-	|b<sub>3m</sub>	+
-	|...	+
-	|b<sub>mm</sub>	+
-	|}	+
-		+
-	C:	+
-	{|style="text-align:center"	+
-	|1	+
-	|c<sub>12</sub>	+
-	|c<sub>13</sub>	+
-	|...	+
-	|c<sub>1m</sub>	+
-	|-	+
-	|0	+
-	|1	+
-	|c<sub>23</sub>	+
-	|...	+
-	|c<sub>2m</sub>	+
-	|-	+
-	|colspan="5"|...	+
-	|-	+
-	|0	+
-	|0	+
-	|0	+
-	|...	+
-	|1	+
-	|}	+
-		+
-	Пока будем предполагать, что то, на что делим, не ноль, а потом будем подбирать достаточные условия для этого.	+
-		+
-	a<sub>ij</sub> = &Sigma;<sub>l = 1</sub><sup>m</sup>b<sub>il</sub>c<sub>lj</sub>	+
-		+
-	a<sub>ij</sub> = &Sigma;<sub>l = 1</sub><sup>i&minus;1</sup>b<sub>il</sub>c<sub>lj</sub> + b<sub>ii</sub>c<sub>ij</sub> + &Sigma;<sub>l = i + 1</sub><sup>m</sup>b<sub>il</sub>c<sub>lj</sub>	+
-		+
-	b<sub>il</sub> = 0 если l > i, значит, третьего слагаемого нет.	+
-		+
-	b<sub>ii</sub>&times;c<sub>lj</sub> = a<sub>ij</sub> &minus; &Sigma;<sub>l=1</sub><sup>i&minus;1</sup> b<sub>il</sub>&times;c<sub>lj</sub>, b<sub>ii</sub>&nbsp;&ne;&nbsp;0, тогда можем поделить:	+
-		+
-	c<sub>ij</sub> = <sup>(a<sub>ij</sub> &minus; &Sigma;<sub>l=1</sub><sup>i&minus;1</sup> b<sub>il</sub>&times;c<sub>lj</sub>)</sup>/<sub>b<sub>ii</sub></sub>, i < j ... (3)	+
-		+
-	a<sub>ij</sub> = &Sigma;<sub>l=1</sub><sup>j&minus;1</sup> b<sub>il</sub>&times;c<sub>lj</sub> + b<sub>ij</sub>&times;c<sub>jj</sub> + &Sigma;<sub>l=j+1</sub><sup>m</sup> b<sub>il</sub>&times;c<sub>lj</sub>	+
-		+
-	b<sub>ij</sub>&times;c<sub>jj</sub> = b<sub>ij</sub>	+
-		+
-	c<sub>lj</sub> = 0, l > j	+
-		+
-	b<sub>ij</sub> = a<sub>ij</sub> &minus; &Sigma;<sub>l=1</sub><sup>j&minus;1</sup> b<sub>il</sub>&times;c<sub>lj</sub>, i&nbsp;&ge;&nbsp;j ... (4)	+
-		+
-	Эта система нелинейная, но если специальным образом организовать алгоритм, то мы всё вычислим.	+
-		+
-	Завтра в П-5	+
-		+
-	{{Численные Методы}}	+
-		+
-	{{Lection-stub}}	+

---

Версия 15:06, 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.