| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| - | [[Численные Методы, 01 лекция (от 12 февраля)|Предыдущая лекция]] | [[Численные Методы, 03 лекция (от 19 февраля)|Следующая лекция]]
| + | == 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. |
| - | == Параграф 2. Связь метода Гаусса с разложением матрицы на множители (продолжение) ==
| + | Dig yourself a grave - you will need it. |
| - | | + | |
| - | Решение нелинейной системы (3), (4), полученной на [[Численные Методы, 01 лекция (от 12 февраля)|предыдущей лекции]].
| + | |
| - | * c<sub>ij</sub> = <sup>(a<sub>ij</sub> − Σ<sub>l=1</sub><sup>i−1</sup> b<sub>il</sub>×c<sub>lj</sub>)</sup>/<sub>b<sub>ii</sub></sub>, i < j ... (3)
| + | |
| - | * b<sub>ij</sub> = a<sub>ij</sub> − Σ<sub>l=1</sub><sup>j−1</sup> b<sub>il</sub>×c<sub>lj</sub>, i ≥ 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…m</span>
| + | |
| - | | + | |
| - | Второй шаг: первый столбец B
| + | |
| - | * b<sub>i1</sub> = a<sub>i1</sub>, i = <span style="border-top:solid 1px">1…m</span>
| + | |
| - | | + | |
| - | Третий шаг: вторая строка C
| + | |
| - | * b<sub>22</sub> = a<sub>22</sub> − b<sub>21</sub> × c<sub>12</sub>
| + | |
| - | * c<sub>2j</sub> = <sup>(a<sub>2j</sub> − b<sub>21</sub>×c<sub>1j</sub>)</sup>/<sub>b<sub>22</sub></sub>, j = <span style="border-top:solid 1px">2…m</span>
| + | |
| - | | + | |
| - | Четвёртый шаг: второй столбец B
| + | |
| - | * b<sub>i2</sub> = a<sub>i2</sub> − b<sub>i1</sub>×c<sub>12</sub>, i = <span style="border-top:solid 1px">2…m</span>
| + | |
| - | | + | |
| - | Таким образом, мы решили нелинейную систему, грамотно организовав алгоритм.
| + | |
| - | | + | |
| - | Факторизация A = B × C (2) осуществляется при b<sub>ii</sub> ≠ 0
| + | |
| - | | + | |
| - | '''Утверждение'''. Пусть все главные угловые миноры A отличны от 0:
| + | |
| - | {|
| + | |
| - | |A<sub>1</sub> = a<sub>11</sub> ≠ 0
| + | |
| - | |;
| + | |
| - | |
| + | |
| - | {|style="text-align:center"
| + | |
| - | |rowspan="2"|A<sub>2</sub> = (
| + | |
| - | |a<sub>11</sub>
| + | |
| - | |a<sub>12</sub>
| + | |
| - | |rowspan="2"|) ≠ 0
| + | |
| - | |-
| + | |
| - | |a<sub>21</sub>
| + | |
| - | |a<sub>22</sub>
| + | |
| - | |}
| + | |
| - | |;
| + | |
| - | |…;
| + | |
| - | |
| + | |
| - | {|style="text-align:center"
| + | |
| - | |rowspan="3"|A<sub>i</sub> = (
| + | |
| - | |a<sub>11</sub>
| + | |
| - | |...
| + | |
| - | |a<sub>1i</sub>
| + | |
| - | |rowspan="3"|) ≠ 0
| + | |
| - | |-
| + | |
| - | |colspan="3"|...
| + | |
| - | |-
| + | |
| - | |a<sub>i1</sub>
| + | |
| - | |...
| + | |
| - | |a<sub>ii</sub>
| + | |
| - | |}
| + | |
| - | |}
| + | |
| - | Тогда разложение матрицы (2) существует и единственно.
| + | |
| - | | + | |
| - | <div class="comment">Класс задач, где присутствуют симметрические матрицы, достаточно широк</div>
| + | |
| - | | + | |
| - | '''Доказательство'''.
| + | |
| - | | + | |
| - | ∃! A<sub>i</sub> = B<sub>i</sub> C<sub>i</sub> = b<sub>11</sub> × b<sub>22</sub> × … × b<sub>i − 1,i − 1</sub> × b<sub>ii</sub>
| + | |
| - | | + | |
| - | b<sub>11</sub> × b<sub>22</sub> × … × b<sub>i − 1,i − 1</sub> = A<sub>i − 1</sub>
| + | |
| - | | + | |
| - | b<sub>ii</sub> = <sup>A<sub>i</sub></sup>/<sub>A<sub>i − 1</sub></sub>, i = , i = <span style="border-top:solid 1px">2…m</span>
| + | |
| - | | + | |
| - | ч. т. д.
| + | |
| - | | + | |
| - | === Связь метода Гаусса с разложением A = B × C ===
| + | |
| - | | + | |
| - | В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется <sup>(m<sup>3</sup> − m)</sup>/<sub>3</sub> операций.
| + | |
| - | | + | |
| - | '''Задача'''. Показать, что для реализации (вычисления) по формулам (3), (4) требуется точно такое же число действий: <sup>(m<sup>3</sup> − m)</sup>/<sub>3</sub> ([[Численные Методы, задачи на лекциях#Задача 1|решение]]).
| + | |
| - | | + | |
| - | В результате факторизации получаем систему BСx = f. Система Ax = f (1) сводится к решению двух уравнений By = f (5), Cx = y (6)
| + | |
| - | | + | |
| - | '''Число действий для решения (5):'''<br />
| + | |
| - | b<sub>i1</sub>y<sub>1</sub> + b<sub>i2</sub>y<sub>2</sub> + … + 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> - Σ<sub>l = 1</sub><sup>i − 1</sup>b<sub>il</sub>y<sub>l</sub>)</sup>/<sub>b<sub>ii</sub></sub><br />
| + | |
| - | i − 1 умножение + 1 деление — '''i''' действий<br />
| + | |
| - | Итого Σ<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, i + 1</sub>x<sub>i+1</sub> + … + C<sub>im</sub>x<sub>m</sub> = y<sub>i</sub>, i = 1..m<br />
| + | |
| - | x<sub>i</sub> = y<sub>i</sub> − Σ<sub>l = i + 1</sub><sup>m</sup>c<sub>il</sub>x<sub>l</sub><br />
| + | |
| - | m − i умножений, i = <span style="border-top:solid 1px">2…m</span><br />
| + | |
| - | Итого '''<sup>m(m − 1)</sup>/<sub>2</sub><br />'''
| + | |
| - | В точности то число действий, которое требуется для обратного хода Гаусса.<br />
| + | |
| - | | + | |
| - | Весь метод Гаусса требует <sup>(m<sup>3</sup> − m)</sup>/<sub>3</sub> + m<sup>2</sup> = <sup>m</sup>/<sub>3</sub> × (m<sup>2</sup> + 3m − 1). В чём же выигрыш? Он будет показан при нахождении обратной матрицы.
| + | |
| - | | + | |
| - | == Параграф 3. Обращение матрицы методом Гаусса-Жордана ==
| + | |
| - | | + | |
| - | Пусть есть матрица A размера m × m, det A ≠ 0. Тогда для неё существует A<sup>−1</sup>: A<sup>−1</sup> × A = A × A<sup>−1</sup> = E.
| + | |
| - | | + | |
| - | Один из способов нахождения матрицы — нахождение алгебраических дополнений. Один из недостатков в том, что при малом определителе гигантские погрешности. Второй способ в приписывании единичной матрицы и проведения над ней действий трёх видов до получения единичной матрицы слева. Тоже не лучше.
| + | |
| - | | + | |
| - | Метод Гаусса-Жордана:
| + | |
| - | * Обозначим A<sup>−1</sup> = X. Тогда AX = E
| + | |
| - | * Запишем в явном виде:
| + | |
| - | * ∑<sub>l = 1</sub><sup>m</sup>a<sub>il</sub>x<sub>lj</sub> = δ<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>, …, x<sub>mj</sub>)<sup>T</sup>
| + | |
| - | | + | |
| - | Вектор δ<sup>(j)</sup> = (0, 0, …, 0, 1 (j-я позиция), 0, …, 0)
| + | |
| - | | + | |
| - | Тогда Ax<sup>(j)</sup> = δ<sup>(j)</sup>, j = 1..m (3)
| + | |
| - | | + | |
| - | Факторизуем A = B×C. Для этого потребуется <sup>(m<sup>3</sup> − m)</sup>/<sub>3</sub> действий
| + | |
| - | | + | |
| - | Далее решаем 2 системы:
| + | |
| - | | + | |
| - | BCx<sup>(j)</sup> = δ<sup>(j)</sup>
| + | |
| - | | + | |
| - | Cx<sup>(j)</sup> = y<sup>(j)</sup>
| + | |
| - | | + | |
| - | * By<sup>(j)</sup> = δ<sup>(j)</sup> (4), j = <span style="border-top:solid 1px">2…m</span>
| + | |
| - | * Cx<sup>(j)</sup> = y<sup>(j)</sup> (5)
| + | |
| - | | + | |
| - | Решение пары таких систем требует m<sup>2</sup> действий, а всего таких систем m. То есть, итого <sup>(m<sup>3</sup> − m)</sup>/<sub>3</sub> + m<sup>3</sup> = <sup>4</sup>/<sub>3</sub> m<sup>3</sup> − <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 ⇒ y<sub>2</sub><sup>(j)</sup> = 0
| + | |
| - | * …
| + | |
| - | * y<sub>j − 1</sub><sup>(j)</sup> = 0 (6*)
| + | |
| - | * b<sub>jj</sub>y<sub>j</sub><sup>(j)</sup> = 1 ⇒ 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> + … +b<sub>ii</sub>y<sub>i</sub><sup>(j)</sup> = 0, i = j + 1..m
| + | |
| - | * y<sub>i</sub><sup>(j)</sup> = <sup>(Σ<sub>l = j</sub><sup>i − 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 − j умножений. Отпустим один из индексов, i. Получим:
| + | |
| - | | + | |
| - | * m − j + (m − j − 1) + … + 2 + 1 = <sup>(m − j + 1)(m − j)</sup>/<sub>2</sub> умножений
| + | |
| - | * m − j делений (6) + 1 (6*)
| + | |
| - | * m − j + 1 делений
| + | |
| - | | + | |
| - | Всего при фиксированном j: <sup>(m − j + 1)(m − j)</sup>/<sub>2</sub> + <sup>2(m − j + 1)</sup>/<sub>2</sub> = <sup>(m − j + 1)(m − j + 2)</sup>/<sub>2</sub> умножений и делений.
| + | |
| - | | + | |
| - | Отпускаем j, j = <span style="border-top:solid 1px">2…m</span>. Получим:
| + | |
| - | ∑<sub>j = 1</sub><sup>m</sup>(<sup>(m − j + 1)(m − j + 2)</sup>/<sub>2</sub>) ... (δ)
| + | |
| - | | + | |
| - | '''Задача'''. Показать, что (δ) = m(m+1)(m+2)/6
| + | |
| - | | + | |
| - | Для (5) мы выигрыша получить не можем. Поэтому для (5) при фиксированном j получаем <sup>m(m − 1)</sup>/<sub>2</sub> действий. Для решения всех систем (5) требуется <sup>m<sup>2</sup>(m− 1)</sup>/<sub>2</sub> действий. Итого получаем:
| + | |
| - | | + | |
| - | <sup>(m<sup>3</sup> − m)</sup>/<sub>3</sub> + <sup>m(m + 1)(m + 2)</sup>/<sub>6</sub> + <sup>m<sup>2</sup>(m − 1)</sup>/<sub>2</sub> = <sup>m</sup>/<sub>6</sub> × (2m<sup>2</sup> − 2 + m<sup>2</sup> + 3m + 2 + 3m<sup>2</sup> − 3m) = m<sup>3</sup>
| + | |
| - | | + | |
| - | Таким образом, разумно организовав вычисления, мы получим обратную матрицу за m<sup>3</sup> операций.
| + | |
| - | | + | |
| - | == Параграф 4. Метод квадратного корня ==
| + | |
| - | | + | |
| - | Другое название: метод Холецкого
| + | |
| - | | + | |
| - | Решаем уравнение Ax = f (1)
| + | |
| - | * |A| ≠ 0 (m × m)
| + | |
| - | * A = A* ⇔ a<sub>ij</sub> = <span style="border-top:solid 1px">a<sub>ji</sub></span>
| + | |
| - | * A = A<sup>T</sup> — для вещественных матриц
| + | |
| - | | + | |
| - | Суть метода:
| + | |
| - | | + | |
| - | Факторизуем матрицу 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…m</span>
| + | |
| - | | + | |
| - | D = diag (d<sub>11</sub>, …, d<sub>mm</sub>) d<sub>ii</sub> = ±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> — вещественное. Тогда 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> − d<sub>11</sub>s<sub>12</sub><sup>2</sup>. Отсюда получим d<sub>22</sub> = sign(a<sub>22</sub> − d<sub>11</sub>s<sub>12</sub><sup>2</sup>), s<sub>22</sub> = sqrt(|a<sub>22</sub> − d<sub>11</sub>s<sub>12</sub><sup>2</sup>|). Таким образом, мы показали, что для матрицы 2×2 в таком виде осуществима.
| + | |
| - | | + | |
| - | {{Численные Методы}}
| + | |
