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

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

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

Предыдущая лекция | Следующая лекция

Содержание

1 Глава 1. Численные методы линейной алгебры

[править] Глава 1. Численные методы линейной алгебры

[править] Параграф 2. Связь метода Гаусса с разложением матрицы на множители (продолжение)

Решение нелинейной системы (3), (4), полученной на предыдущей лекции.

c_ij = ^{(a_ij − Σ_l=1ⁱ⁻¹ b_il×c_lj)}/_{b_ii}, i < j ... (3)
b_ij = a_ij − Σ_l=1^j−1 b_il×c_lj, i ≥ j ... (4)

Первый шаг: первая строка C

b₁₁ = a₁₁
c_1j = ^a_1j/_b₁₁, j = 1…m

Второй шаг: первый столбец B

b_i1 = a_i1, i = 1…m

Третий шаг: вторая строка C

b₂₂ = a₂₂ − b₂₁ × c₁₂
c_2j = ^{(a_2j − b₂₁×c_1j)}/_b₂₂, j = 2…m

Четвёртый шаг: второй столбец B

b_i2 = a_i2 − b_i1×c₁₂, i = 2…m

Таким образом, мы решили нелинейную систему, грамотно организовав алгоритм.

Факторизация A = B × C (2) осуществляется при b_ii ≠ 0

Утверждение. Пусть все главные угловые миноры A отличны от 0:

A₁ = a₁₁ ≠ 0

;

A₂ = (	a₁₁	a₁₂	) ≠ 0
	a₂₁	a₂₂

;

…;

A_i = (	a₁₁	...	a_1i	) ≠ 0
	...
	a_i1	...	a_ii

Тогда разложение матрицы (2) существует и единственно.

Класс задач, где присутствуют симметрические матрицы, достаточно широк

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

∃! A_i = B_i C_i = b₁₁ × b₂₂ × … × b_{i − 1,i − 1} × b_ii

b₁₁ × b₂₂ × … × b_{i − 1,i − 1} = A_i − 1

b_ii = ^A_i/_{A_i − 1}, i = , i = 2…m

ч. т. д.

[править] Связь метода Гаусса с разложением A = B × C

В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется ^{(m³ − m)}/₃ операций.

Задача. Показать, что для реализации (вычисления) по формулам (3), (4) требуется точно такое же число действий: ^{(m³ − m)}/₃ (решение).

В результате факторизации получаем систему BСx = f. Система Ax = f (1) сводится к решению двух уравнений By = f (5), Cx = y (6)

Число действий для решения (5):
b_i1y₁ + b_i2y₂ + … + b_iiy_i = f_i, i = 1..m
y_i = ^{(f_i - Σ_{l = 1}^i − 1b_ily_l)}/_{b_ii}
i − 1 умножение + 1 деление — i действий
Итого Σ_{i = 1}^mi = ^m(m+1)/₂ действий.
В точности то же самое число действий, что требуется для вычисления правой части в методе Гаусса.

Число действий для решения (6):
x_i + C_{i, i + 1}x_i+1 + … + C_imx_m = y_i, i = 1..m
x_i = y_i − Σ_{l = i + 1}^mc_ilx_l
m − i умножений, i = 2…m
Итого ^m(m − 1)/₂
В точности то число действий, которое требуется для обратного хода Гаусса.

Весь метод Гаусса требует ^{(m³ − m)}/₃ + m² = ^m/₃ × (m² + 3m − 1). В чём же выигрыш? Он будет показан при нахождении обратной матрицы.

[править] Параграф 3. Обращение матрицы методом Гаусса-Жордана

Пусть есть матрица A размера m × m, det A ≠ 0. Тогда для неё существует A⁻¹: A⁻¹ × A = A × A⁻¹ = E.

Один из способов нахождения матрицы — нахождение алгебраических дополнений. Один из недостатков в том, что при малом определителе гигантские погрешности. Второй способ в приписывании единичной матрицы и проведения над ней действий трёх видов до получения единичной матрицы слева. Тоже не лучше.

Метод Гаусса-Жордана:

Обозначим A⁻¹ = X. Тогда AX = E
Запишем в явном виде:
∑_{l = 1}^ma_ilx_lj = δ_ij, i, j = 1..m (2)
m² неизвестных, поэтому действий m⁶

Сейчас мы покажем, что разумно организовав алгоритм, получим порядка m³ действий.

Решение этой системы распадётся на решение m систем, у которых будет меняться только правая часть.

Введём вектор x^(j) = (x_1j, x_2j, …, x_mj)^T

Вектор δ^(j) = (0, 0, …, 0, 1 (j-я позиция), 0, …, 0)

Тогда Ax^(j) = δ^(j), j = 1..m (3)

Факторизуем A = B×C. Для этого потребуется ^{(m³ − m)}/₃ действий

Далее решаем 2 системы:

BCx^(j) = δ^(j)

Cx^(j) = y^(j)

By^(j) = δ^(j) (4), j = 2…m
Cx^(j) = y^(j) (5)

Решение пары таких систем требует m² действий, а всего таких систем m. То есть, итого ^{(m³ − m)}/₃ + m³ = ⁴/₃ m³ − ^m/₃

Теперь покажем, что число действий можно свести к m³. За счёт чего мы можем снизить число действий:

В уравнении (4) правые части имеют очень специальный вид. Мы в первый раз ненулевую компоненту встретим только на j-м шаге.

Первое уравнение:

b₁₁y₁^(j) = 0 => y₁^(j) = 0
b₂₁y₁^(j) + b₂₂y₂^(j) = 0 ⇒ y₂^(j) = 0
…
y_j − 1^(j) = 0 (6*)
b_jjy_j^(j) = 1 ⇒ y_j^(j) = ¹/_bjj
b_ijy_j^(j) + b_{i, j + 1}y_{j + 1}^(j) + … +b_iiy_i^(j) = 0, i = j + 1..m
y_i^(j) = ^{(Σ_{l = j}^i − 1b_ily_l^(j))}/_{b_ii}, i = j+1..m (6)

Пусть i, j фиксированы. Тогда 1 деление и i − j умножений. Отпустим один из индексов, i. Получим:

m − j + (m − j − 1) + … + 2 + 1 = ^{(m − j + 1)(m − j)}/₂ умножений
m − j делений (6) + 1 (6*)
m − j + 1 делений

Всего при фиксированном j: ^{(m − j + 1)(m − j)}/₂ + ^{2(m − j + 1)}/₂ = ^{(m − j + 1)(m − j + 2)}/₂ умножений и делений.

Отпускаем j, j = 2…m. Получим: ∑_j = 1^m(^{(m − j + 1)(m − j + 2)}/₂) ... (δ)

Задача. Показать, что (δ) = m(m+1)(m+2)/6

Для (5) мы выигрыша получить не можем. Поэтому для (5) при фиксированном j получаем ^m(m − 1)/₂ действий. Для решения всех систем (5) требуется ^m²(m− 1)/₂ действий. Итого получаем:

^{(m³ − m)}/₃ + ^{m(m + 1)(m + 2)}/₆ + ^{m²(m − 1)}/₂ = ^m/₆ × (2m² − 2 + m² + 3m + 2 + 3m² − 3m) = m³

Таким образом, разумно организовав вычисления, мы получим обратную матрицу за m³ операций.

[править] Параграф 4. Метод квадратного корня

Другое название: метод Холецкого

Решаем уравнение Ax = f (1)

|A| ≠ 0 (m × m)
A = A* ⇔ a_ij = a_ji
A = A^T — для вещественных матриц

Суть метода:

Факторизуем матрицу A в виде A = S*DS (2)

	s₁₁	s₁₂	s₁₃	...	s_1m
	0	s₂₂	s₂₃	...	s_2m
S =	0	0	s₃₃	..	s_3m
	...
	0	0	0	...	s_mm

s_ii > 0, i = 2…m

D = diag (d₁₁, …, d_mm) d_ii = ±1, i = 1..m

Тогда система (1) решается следующим образом:

S*DSx = f
S*Dy = f (3)
Sx = y

Эти две системы решаются явным образом, ибо матрицы треугольные

рассмотрим вещественную матрицу A = ((a₁₁, a₁₂), (a₁₂, a₂₂)) a_ij — вещественное. Тогда S = ((s₁₁, s₁₂), (0, s₂₂)), S* = ((s₁₁, 0), (s₁₂, s₂₂)), D=((d₁₁, 0), (0, d₂₂))

Умножим DS = ((d₁₁, 0), (0, d₂₂)) ((s₁₁, s₁₂), (0, s₂₂)) = ((d₁₁s₁₁, d₁₁s₁₂), (0, d₂₂s₂₂)). Она сохранила верхнетреугольную форму (позже покажем, что умножение верхнетреугольной на почти верхнетреугольную сохраняет форму). Домножим на S*. S*DS = ((s₁₁, 0), (s₁₂, s₂₂))((d₁₁s₁₁, d₁₁s₁₂), (0, d₂₂s₂₂)) = ((d₁₁s₁₁², d₁₁s₁₂s₁₁), (d₁₁s₁₂s₁₁, d₁₁s₁₂² + d₂₂s₂₂²)) = A. Поэлементно приравниваем компоненты.

d₁₁s₁₁² = a₁₁
d₁₁s₁₂s₁₁ = a₁₂
d₁₁s₁₂² + d₂₂s₂₂² = a₂₂

Посмотрим на первое уравнение. Из него понятно, что d₁₁ = sign a₁₁. Тогда отсюда получаем s₁₁ = sqrt(|a₁₁|). Дальше смотрим на второе уравнение: s₁₂ = a₁₂/d₁₁s₁₁. Теперь последнее уравнение рассматриваем. Перепишем его в виде: d₂₂s₂₂² = a₂₂ − d₁₁s₁₂². Отсюда получим d₂₂ = sign(a₂₂ − d₁₁s₁₂²), s₂₂ = sqrt(|a₂₂ − d₁₁s₁₂²|). Таким образом, мы показали, что для матрицы 2×2 в таком виде осуществима.

Численные Методы

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22

Календарь

Февраль
пн	12	19
вт	13	20	27

Март
пн	05	12	19	26
вт	06	13	20	27

Апрель
пн	02	09	16	23	29
вт	03	10	17	24

Дополнительная информация

Содержание курса | Задачи на лекциях

Материалы к экзамену

Вопросы по курсу | Определения

Эта статья является конспектом лекции.

Получено с http://esyr.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_13_%D1%84%D0%B5%D0%B2%D1%80%D0%B0%D0%BB%D1%8F%29

Категории: Численные Методы | Лекции

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

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

Текущая версия

Содержание

[править] Глава 1. Численные методы линейной алгебры

[править] Параграф 2. Связь метода Гаусса с разложением матрицы на множители (продолжение)

[править] Связь метода Гаусса с разложением A = B × C

[править] Параграф 3. Обращение матрицы методом Гаусса-Жордана

[править] Параграф 4. Метод квадратного корня

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-== From Ebaums Inc to MurkLoar. ==
+[[Численные Методы, 01 лекция (от 12 февраля)|Предыдущая лекция]] | [[Численные Методы, 03 лекция (от 19 февраля)|Следующая лекция]]
-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.
+=  Глава 1. Численные методы линейной алгебры =
-Dig yourself a grave - you will need it.
+==  Параграф 2. Связь метода Гаусса с разложением матрицы на множители (продолжение) ==
+Решение нелинейной системы (3), (4), полученной на [[Численные Методы, 01 лекция (от 12 февраля)|предыдущей лекции]].
+* 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)
+* 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)
+Первый шаг: первая строка C
+* b<sub>11</sub> = a<sub>11</sub>
+* c<sub>1j</sub> = <sup>a<sub>1j</sub></sup>/<sub>b<sub>11</sub></sub>, j = <span style="border-top:solid 1px">1&hellip;m</span>
+Второй шаг: первый столбец B
+* b<sub>i1</sub>&nbsp;=&nbsp;a<sub>i1</sub>, i = <span style="border-top:solid 1px">1&hellip;m</span>
+Третий шаг: вторая строка C
+* b<sub>22</sub>&nbsp;=&nbsp;a<sub>22</sub>&nbsp;&minus;&nbsp;b<sub>21</sub>&nbsp;&times;&nbsp;c<sub>12</sub>
+* c<sub>2j</sub>&nbsp;=&nbsp;<sup>(a<sub>2j</sub> &minus;  b<sub>21</sub>&times;c<sub>1j</sub>)</sup>/<sub>b<sub>22</sub></sub>, j = <span style="border-top:solid 1px">2&hellip;m</span>
+Четвёртый шаг: второй столбец B
+* b<sub>i2</sub>&nbsp;=&nbsp;a<sub>i2</sub> &minus; b<sub>i1</sub>&times;c<sub>12</sub>, i = <span style="border-top:solid 1px">2&hellip;m</span>
+Таким образом, мы решили нелинейную систему, грамотно организовав алгоритм.
+Факторизация A&nbsp;=&nbsp;B&nbsp;&times;&nbsp;C (2) осуществляется при b<sub>ii</sub>&nbsp;&ne;&nbsp;0
+'''Утверждение'''. Пусть все главные угловые миноры A  отличны от 0:
+{|
+ |A<sub>1</sub> = a<sub>11</sub> &ne; 0
+ |;
+ |
+ {|style="text-align:center"
+  |rowspan="2"|A<sub>2</sub>&nbsp;=&nbsp;(
+  |a<sub>11</sub>
+  |a<sub>12</sub>
+  |rowspan="2"|)&nbsp;&ne;&nbsp;0
+  |-
+  |a<sub>21</sub>
+  |a<sub>22</sub>
+  |}
+ |;
+ |&hellip;;
+ |
+ {|style="text-align:center"
+  |rowspan="3"|A<sub>i</sub>&nbsp;=&nbsp;(
+  |a<sub>11</sub>
+  |...
+  |a<sub>1i</sub>
+  |rowspan="3"|)&nbsp;&ne;&nbsp;0
+  |-
+  |colspan="3"|...
+  |-
+  |a<sub>i1</sub>
+  |...
+  |a<sub>ii</sub>
+  |}
+ |}
+Тогда разложение матрицы (2) существует и единственно.
+<div class="comment">Класс задач, где присутствуют симметрические матрицы, достаточно широк</div>
+'''Доказательство'''.
+&exist;!&nbsp;A<sub>i</sub>&nbsp;=&nbsp;B<sub>i</sub>&nbsp;C<sub>i</sub>&nbsp;=&nbsp;b<sub>11</sub>&nbsp;&times;&nbsp;b<sub>22</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;b<sub>i&nbsp;&minus;&nbsp;1,i&nbsp;&minus;&nbsp;1</sub>&nbsp;&times;&nbsp;b<sub>ii</sub>
+b<sub>11</sub>&nbsp;&times;&nbsp;b<sub>22</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;b<sub>i&nbsp;&minus;&nbsp;1,i&nbsp;&minus;&nbsp;1</sub>&nbsp;=&nbsp;A<sub>i&nbsp;&minus;&nbsp;1</sub>
+b<sub>ii</sub> = <sup>A<sub>i</sub></sup>/<sub>A<sub>i&nbsp;&minus;&nbsp;1</sub></sub>, i&nbsp;=&nbsp;, i = <span style="border-top:solid 1px">2&hellip;m</span>
+ч. т. д.
+=== Связь метода Гаусса с разложением A = B &times; C ===
+В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется <sup>(m<sup>3</sup>&nbsp;&minus;&nbsp;m)</sup>/<sub>3</sub> операций.
+'''Задача'''. Показать, что для реализации (вычисления) по формулам (3), (4) требуется точно такое же число действий: <sup>(m<sup>3</sup>&nbsp;&minus;&nbsp;m)</sup>/<sub>3</sub> ([[Численные Методы, задачи на лекциях#Задача 1|решение]]).
+В результате факторизации получаем систему BСx&nbsp;=&nbsp;f. Система Ax&nbsp;=&nbsp;f&nbsp;(1) сводится к решению двух уравнений By&nbsp;=&nbsp;f&nbsp;(5), Cx&nbsp;= &nbsp;y&nbsp;(6)
+'''Число действий для решения (5):'''<br />
+b<sub>i1</sub>y<sub>1</sub> + b<sub>i2</sub>y<sub>2</sub> + &hellip; + b<sub>ii</sub>y<sub>i</sub> = f<sub>i</sub>, i = 1..m<br />
+y<sub>i</sub> = <sup>(f<sub>i</sub> - &Sigma;<sub>l = 1</sub><sup>i&nbsp;&minus;&nbsp;1</sup>b<sub>il</sub>y<sub>l</sub>)</sup>/<sub>b<sub>ii</sub></sub><br />
+i&nbsp;&minus;&nbsp;1 умножение + 1 деление&nbsp;&mdash; '''i''' действий<br />
+Итого &Sigma;<sub>i = 1</sub><sup>m</sup>i = '''<sup>m(m+1)</sup>/<sub>2</sub>''' действий.<br />
+В точности то же самое число действий, что требуется для вычисления правой части в методе Гаусса.<br />
+'''Число действий для решения (6)''':<br />
+x<sub>i</sub> + C<sub>i,&nbsp;i + 1</sub>x<sub>i+1</sub> + &hellip; + C<sub>im</sub>x<sub>m</sub> = y<sub>i</sub>, i = 1..m<br />
+x<sub>i</sub> = y<sub>i</sub>&nbsp;&minus; &Sigma;<sub>l = i + 1</sub><sup>m</sup>c<sub>il</sub>x<sub>l</sub><br />
+m&nbsp;&minus;&nbsp;i умножений, i = <span style="border-top:solid 1px">2&hellip;m</span><br />
+Итого '''<sup>m(m&nbsp;&minus;&nbsp;1)</sup>/<sub>2</sub><br />'''
+В точности то число действий, которое требуется для обратного хода Гаусса.<br />
+Весь метод Гаусса требует <sup>(m<sup>3</sup>&nbsp;&minus;&nbsp;m)</sup>/<sub>3</sub> + m<sup>2</sup> = <sup>m</sup>/<sub>3</sub>&nbsp;&times;&nbsp;(m<sup>2</sup>&nbsp;+&nbsp;3m&nbsp;&minus;&nbsp;1). В чём же выигрыш? Он будет показан при нахождении обратной матрицы.
+== Параграф 3. Обращение матрицы методом Гаусса-Жордана ==
+Пусть есть матрица A размера m&nbsp;&times;&nbsp;m, det A &ne; 0. Тогда для неё существует A<sup>&minus;1</sup>: A<sup>&minus;1</sup>&nbsp;&times;&nbsp;A = A&nbsp;&times;&nbsp;A<sup>&minus;1</sup> = E.
+Один из способов нахождения матрицы&nbsp;&mdash; нахождение алгебраических дополнений. Один из недостатков в том, что при малом определителе гигантские погрешности. Второй способ в приписывании единичной матрицы и проведения над ней действий трёх видов до получения единичной матрицы слева. Тоже не лучше.
+Метод Гаусса-Жордана:
+* Обозначим A<sup>&minus;1</sup> = X. Тогда AX = E
+* Запишем в явном виде:
+* &sum;<sub>l = 1</sub><sup>m</sup>a<sub>il</sub>x<sub>lj</sub> = &delta;<sub>ij</sub>, i, j = 1..m (2)
+* m<sup>2</sup> неизвестных, поэтому действий m<sup>6</sup>
+Сейчас мы покажем, что разумно организовав алгоритм, получим порядка m<sup>3</sup> действий.
+Решение этой системы  распадётся на решение m систем, у которых будет меняться только правая часть.
+Введём вектор x<sup>(j)</sup> = (x<sub>1j</sub>, x<sub>2j</sub>, &hellip;, x<sub>mj</sub>)<sup>T</sup>
+Вектор &delta;<sup>(j)</sup> = (0, 0, &hellip;, 0, 1 (j-я позиция), 0, &hellip;, 0)
+Тогда Ax<sup>(j)</sup> = &delta;<sup>(j)</sup>, j = 1..m (3)
+Факторизуем A = B&times;C. Для этого потребуется <sup>(m<sup>3</sup>&nbsp;&minus;&nbsp;m)</sup>/<sub>3</sub> действий
+Далее решаем 2 системы:
+BCx<sup>(j)</sup> = &delta;<sup>(j)</sup>
+Cx<sup>(j)</sup> = y<sup>(j)</sup>
+* By<sup>(j)</sup> = &delta;<sup>(j)</sup> (4), j = <span style="border-top:solid 1px">2&hellip;m</span>
+* Cx<sup>(j)</sup> = y<sup>(j)</sup> (5)
+Решение пары таких систем требует m<sup>2</sup> действий, а всего таких систем m. То есть, итого <sup>(m<sup>3</sup>&nbsp;&minus;&nbsp;m)</sup>/<sub>3</sub> + m<sup>3</sup> = <sup>4</sup>/<sub>3</sub> m<sup>3</sup> &minus; <sup>m</sup>/<sub>3</sub>
+Теперь покажем, что число действий можно свести к m<sup>3</sup>. За счёт чего мы можем снизить число действий:
+В уравнении (4) правые части имеют очень специальный вид. Мы в первый раз ненулевую компоненту встретим только на j-м шаге.
+Первое уравнение:
+* b<sub>11</sub>y<sub>1</sub><sup>(j)</sup> = 0 => y<sub>1</sub><sup>(j)</sup> = 0
+* b<sub>21</sub>y<sub>1</sub><sup>(j)</sup> + b<sub>22</sub>y<sub>2</sub><sup>(j)</sup> = 0 &rArr; y<sub>2</sub><sup>(j)</sup> = 0
+* &hellip;
+* y<sub>j&nbsp;&minus;&nbsp;1</sub><sup>(j)</sup> = 0 (6*)
+* b<sub>jj</sub>y<sub>j</sub><sup>(j)</sup> = 1 &rArr; y<sub>j</sub><sup>(j)</sup> = <sup>1</sup>/<sub>bjj</sub>
+* b<sub>ij</sub>y<sub>j</sub><sup>(j)</sup> + b<sub>i, j + 1</sub>y<sub>j + 1</sub><sup>(j)</sup> + &hellip; +b<sub>ii</sub>y<sub>i</sub><sup>(j)</sup> = 0, i = j + 1..m
+* y<sub>i</sub><sup>(j)</sup> = <sup>(&Sigma;<sub>l = j</sub><sup>i&nbsp;&minus;&nbsp;1</sup>b<sub>il</sub>y<sub>l</sub><sup>(j)</sup>)</sup>/<sub>b<sub>ii</sub></sub>, i = j+1..m (6)
+Пусть i, j фиксированы. Тогда 1 деление и i&nbsp;&minus;&nbsp;j умножений. Отпустим один из индексов, i. Получим:
+* m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;(m&nbsp;&minus;&nbsp;j&nbsp;&minus;&nbsp;1)&nbsp;+&nbsp;&hellip;&nbsp;+&nbsp;2&nbsp;+&nbsp;1 = <sup>(m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;1)(m&nbsp;&minus;&nbsp;j)</sup>/<sub>2</sub> умножений
+* m&nbsp;&minus;&nbsp;j делений (6) + 1 (6*)
+* m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;1 делений
+Всего при фиксированном j: <sup>(m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;1)(m&nbsp;&minus;&nbsp;j)</sup>/<sub>2</sub> + <sup>2(m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;1)</sup>/<sub>2</sub>&nbsp;= <sup>(m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;1)(m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;2)</sup>/<sub>2</sub> умножений и делений.
+Отпускаем j, j&nbsp;=&nbsp;<span style="border-top:solid 1px">2&hellip;m</span>. Получим:
+&sum;<sub>j&nbsp;=&nbsp;1</sub><sup>m</sup>(<sup>(m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;1)(m&nbsp;&minus;&nbsp;j&nbsp;+&nbsp;2)</sup>/<sub>2</sub>) ... (&delta;)
+'''Задача'''. Показать, что (&delta;) = m(m+1)(m+2)/6
+Для (5) мы выигрыша получить не можем. Поэтому для (5) при фиксированном j получаем <sup>m(m&nbsp;&minus;&nbsp;1)</sup>/<sub>2</sub> действий. Для решения всех систем (5) требуется <sup>m<sup>2</sup>(m&minus;&nbsp;1)</sup>/<sub>2</sub> действий. Итого получаем:
+<sup>(m<sup>3</sup>&nbsp;&minus;&nbsp;m)</sup>/<sub>3</sub> + <sup>m(m&nbsp;+&nbsp;1)(m&nbsp;+&nbsp;2)</sup>/<sub>6</sub> + <sup>m<sup>2</sup>(m&nbsp;&minus;&nbsp;1)</sup>/<sub>2</sub> = <sup>m</sup>/<sub>6</sub>&nbsp;&times;&nbsp;(2m<sup>2</sup>&nbsp;&minus;&nbsp;2&nbsp;+&nbsp;m<sup>2</sup>&nbsp;+&nbsp;3m&nbsp;+&nbsp;2&nbsp;+&nbsp;3m<sup>2</sup>&nbsp;&minus;&nbsp;3m) = m<sup>3</sup>
+Таким образом, разумно организовав вычисления, мы получим обратную матрицу за m<sup>3</sup> операций.
+== Параграф 4. Метод квадратного корня ==
+Другое название: метод Холецкого
+Решаем уравнение Ax = f (1)
+* |A| &ne; 0 (m &times; m)
+* A = A* &hArr; a<sub>ij</sub> = <span style="border-top:solid 1px">a<sub>ji</sub></span>
+* A = A<sup>T</sup> &mdash; для вещественных матриц
+Суть метода:
+Факторизуем матрицу A в виде A = S*DS (2)
+{|style="text-align:center"
+ |
+ |s<sub>11</sub>
+ |s<sub>12</sub>
+ |s<sub>13</sub>
+ |...
+ |s<sub>1m</sub>
+ |-
+ |
+ |0
+ |s<sub>22</sub>
+ |s<sub>23</sub>
+ |...
+ |s<sub>2m</sub>
+ |-
+ |S =
+ |0
+ |0
+ |s<sub>33</sub>
+ |..
+ |s<sub>3m</sub>
+ |-
+ |
+ |colspan="5"|...
+ |-
+ |
+ |0
+ |0
+ |0
+ |...
+ |s<sub>mm</sub>
+ |}
+s<sub>ii</sub> > 0, i = <span style="border-top:solid 1px">2&hellip;m</span>
+D = diag (d<sub>11</sub>, &hellip;, d<sub>mm</sub>) d<sub>ii</sub> = &plusmn;1, i = 1..m
+Тогда система (1) решается следующим образом:
+* S*DSx = f
+* S*Dy = f (3)
+* Sx = y
+Эти две системы решаются явным образом, ибо матрицы треугольные
+рассмотрим вещественную матрицу A = ((a<sub>11</sub>, a<sub>12</sub>), (a<sub>12</sub>, a<sub>22</sub>)) a<sub>ij</sub> &mdash; вещественное. Тогда S = ((s<sub>11</sub>, s<sub>12</sub>), (0, s<sub>22</sub>)), S* = ((s<sub>11</sub>, 0), (s<sub>12</sub>, s<sub>22</sub>)), D=((d<sub>11</sub>, 0), (0, d<sub>22</sub>))
+Умножим DS = ((d<sub>11</sub>, 0), (0, d<sub>22</sub>)) ((s<sub>11</sub>, s<sub>12</sub>), (0, s<sub>22</sub>)) = ((d<sub>11</sub>s<sub>11</sub>, d<sub>11</sub>s<sub>12</sub>), (0, d<sub>22</sub>s<sub>22</sub>)). Она сохранила верхнетреугольную форму (позже покажем, что умножение верхнетреугольной на почти верхнетреугольную сохраняет форму). Домножим на S*. S*DS = ((s<sub>11</sub>, 0), (s<sub>12</sub>, s<sub>22</sub>))((d<sub>11</sub>s<sub>11</sub>, d<sub>11</sub>s<sub>12</sub>), (0, d<sub>22</sub>s<sub>22</sub>)) = ((d<sub>11</sub>s<sub>11</sub><sup>2</sup>, d<sub>11</sub>s<sub>12</sub>s<sub>11</sub>), (d<sub>11</sub>s<sub>12</sub>s<sub>11</sub>, d<sub>11</sub>s<sub>12</sub><sup>2</sup> + d<sub>22</sub>s<sub>22</sub><sup>2</sup>)) = A. Поэлементно приравниваем компоненты.
+* d<sub>11</sub>s<sub>11</sub><sup>2</sup> = a<sub>11</sub>
+* d<sub>11</sub>s<sub>12</sub>s<sub>11</sub> = a<sub>12</sub>
+* d<sub>11</sub>s<sub>12</sub><sup>2</sup> + d<sub>22</sub>s<sub>22</sub><sup>2</sup> = a<sub>22</sub>
+Посмотрим на первое уравнение. Из него понятно, что d<sub>11</sub> = sign a<sub>11</sub>. Тогда отсюда получаем s<sub>11</sub> = sqrt(|a<sub>11</sub>|). Дальше смотрим на второе уравнение: s<sub>12</sub> = a<sub>12</sub>/d<sub>11</sub>s<sub>11</sub>. Теперь последнее уравнение рассматриваем. Перепишем его в виде: d<sub>22</sub>s<sub>22</sub><sup>2</sup> = a<sub>22</sub> &minus; d<sub>11</sub>s<sub>12</sub><sup>2</sup>. Отсюда получим d<sub>22</sub> = sign(a<sub>22</sub> &minus; d<sub>11</sub>s<sub>12</sub><sup>2</sup>), s<sub>22</sub> = sqrt(|a<sub>22</sub> &minus; d<sub>11</sub>s<sub>12</sub><sup>2</sup>|). Таким образом, мы показали, что для матрицы 2&times;2 в таком виде осуществима.
+{{Численные Методы}}