Численные Методы, 02 лекция (от 13 февраля)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1423 участника 155.207.113.95 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Численные Методы, 01 лекция (от 12 февраля)|Предыдущая лекция]] | [[Численные Методы, 03 лекция (от 19 февраля)|Следующая лекция]] |
- | + | ||
- | + | = Глава 1. Численные методы линейной алгебры = | |
- | + | == Параграф 2. Связь метода Гаусса с разложением матрицы на множители (продолжение) == | |
+ | |||
+ | Решение нелинейной системы (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 в таком виде осуществима. | ||
+ | |||
+ | {{Численные Методы}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Содержание |
[править] Глава 1. Численные методы линейной алгебры
[править] Параграф 2. Связь метода Гаусса с разложением матрицы на множители (продолжение)
Решение нелинейной системы (3), (4), полученной на предыдущей лекции.
- cij = (aij − Σl=1i−1 bil×clj)/bii, i < j ... (3)
- bij = aij − Σl=1j−1 bil×clj, i ≥ j ... (4)
Первый шаг: первая строка C
- b11 = a11
- c1j = a1j/b11, j = 1…m
Второй шаг: первый столбец B
- bi1 = ai1, i = 1…m
Третий шаг: вторая строка C
- b22 = a22 − b21 × c12
- c2j = (a2j − b21×c1j)/b22, j = 2…m
Четвёртый шаг: второй столбец B
- bi2 = ai2 − bi1×c12, i = 2…m
Таким образом, мы решили нелинейную систему, грамотно организовав алгоритм.
Факторизация A = B × C (2) осуществляется при bii ≠ 0
Утверждение. Пусть все главные угловые миноры A отличны от 0:
A1 = a11 ≠ 0 | ; |
| ; | …; |
|
Тогда разложение матрицы (2) существует и единственно.
Доказательство.
∃! Ai = Bi Ci = b11 × b22 × … × bi − 1,i − 1 × bii
b11 × b22 × … × bi − 1,i − 1 = Ai − 1
bii = Ai/Ai − 1, i = , i = 2…m
ч. т. д.
[править] Связь метода Гаусса с разложением A = B × C
В методе Гаусса для того, чтобы свести матрицу к верхнетреугольной матрице с единицами на главной диагонали, требуется (m3 − m)/3 операций.
Задача. Показать, что для реализации (вычисления) по формулам (3), (4) требуется точно такое же число действий: (m3 − m)/3 (решение).
В результате факторизации получаем систему BСx = f. Система Ax = f (1) сводится к решению двух уравнений By = f (5), Cx = y (6)
Число действий для решения (5):
bi1y1 + bi2y2 + … + biiyi = fi, i = 1..m
yi = (fi - Σl = 1i − 1bilyl)/bii
i − 1 умножение + 1 деление — i действий
Итого Σi = 1mi = m(m+1)/2 действий.
В точности то же самое число действий, что требуется для вычисления правой части в методе Гаусса.
Число действий для решения (6):
xi + Ci, i + 1xi+1 + … + Cimxm = yi, i = 1..m
xi = yi − Σl = i + 1mcilxl
m − i умножений, i = 2…m
Итого m(m − 1)/2
В точности то число действий, которое требуется для обратного хода Гаусса.
Весь метод Гаусса требует (m3 − m)/3 + m2 = m/3 × (m2 + 3m − 1). В чём же выигрыш? Он будет показан при нахождении обратной матрицы.
[править] Параграф 3. Обращение матрицы методом Гаусса-Жордана
Пусть есть матрица A размера m × m, det A ≠ 0. Тогда для неё существует A−1: A−1 × A = A × A−1 = E.
Один из способов нахождения матрицы — нахождение алгебраических дополнений. Один из недостатков в том, что при малом определителе гигантские погрешности. Второй способ в приписывании единичной матрицы и проведения над ней действий трёх видов до получения единичной матрицы слева. Тоже не лучше.
Метод Гаусса-Жордана:
- Обозначим A−1 = X. Тогда AX = E
- Запишем в явном виде:
- ∑l = 1mailxlj = δij, i, j = 1..m (2)
- m2 неизвестных, поэтому действий m6
Сейчас мы покажем, что разумно организовав алгоритм, получим порядка m3 действий.
Решение этой системы распадётся на решение m систем, у которых будет меняться только правая часть.
Введём вектор x(j) = (x1j, x2j, …, xmj)T
Вектор δ(j) = (0, 0, …, 0, 1 (j-я позиция), 0, …, 0)
Тогда Ax(j) = δ(j), j = 1..m (3)
Факторизуем A = B×C. Для этого потребуется (m3 − m)/3 действий
Далее решаем 2 системы:
BCx(j) = δ(j)
Cx(j) = y(j)
- By(j) = δ(j) (4), j = 2…m
- Cx(j) = y(j) (5)
Решение пары таких систем требует m2 действий, а всего таких систем m. То есть, итого (m3 − m)/3 + m3 = 4/3 m3 − m/3
Теперь покажем, что число действий можно свести к m3. За счёт чего мы можем снизить число действий:
В уравнении (4) правые части имеют очень специальный вид. Мы в первый раз ненулевую компоненту встретим только на j-м шаге.
Первое уравнение:
- b11y1(j) = 0 => y1(j) = 0
- b21y1(j) + b22y2(j) = 0 ⇒ y2(j) = 0
- …
- yj − 1(j) = 0 (6*)
- bjjyj(j) = 1 ⇒ yj(j) = 1/bjj
- bijyj(j) + bi, j + 1yj + 1(j) + … +biiyi(j) = 0, i = j + 1..m
- yi(j) = (Σl = ji − 1bilyl(j))/bii, i = j+1..m (6)
Пусть i, j фиксированы. Тогда 1 деление и i − j умножений. Отпустим один из индексов, i. Получим:
- m − j + (m − j − 1) + … + 2 + 1 = (m − j + 1)(m − j)/2 умножений
- m − j делений (6) + 1 (6*)
- m − j + 1 делений
Всего при фиксированном j: (m − j + 1)(m − j)/2 + 2(m − j + 1)/2 = (m − j + 1)(m − j + 2)/2 умножений и делений.
Отпускаем j, j = 2…m. Получим: ∑j = 1m((m − j + 1)(m − j + 2)/2) ... (δ)
Задача. Показать, что (δ) = m(m+1)(m+2)/6
Для (5) мы выигрыша получить не можем. Поэтому для (5) при фиксированном j получаем m(m − 1)/2 действий. Для решения всех систем (5) требуется m2(m− 1)/2 действий. Итого получаем:
(m3 − m)/3 + m(m + 1)(m + 2)/6 + m2(m − 1)/2 = m/6 × (2m2 − 2 + m2 + 3m + 2 + 3m2 − 3m) = m3
Таким образом, разумно организовав вычисления, мы получим обратную матрицу за m3 операций.
[править] Параграф 4. Метод квадратного корня
Другое название: метод Холецкого
Решаем уравнение Ax = f (1)
- |A| ≠ 0 (m × m)
- A = A* ⇔ aij = aji
- A = AT — для вещественных матриц
Суть метода:
Факторизуем матрицу A в виде A = S*DS (2)
s11 | s12 | s13 | ... | s1m | |
0 | s22 | s23 | ... | s2m | |
S = | 0 | 0 | s33 | .. | s3m |
... | |||||
0 | 0 | 0 | ... | smm |
sii > 0, i = 2…m
D = diag (d11, …, dmm) dii = ±1, i = 1..m
Тогда система (1) решается следующим образом:
- S*DSx = f
- S*Dy = f (3)
- Sx = y
Эти две системы решаются явным образом, ибо матрицы треугольные
рассмотрим вещественную матрицу A = ((a11, a12), (a12, a22)) aij — вещественное. Тогда S = ((s11, s12), (0, s22)), S* = ((s11, 0), (s12, s22)), D=((d11, 0), (0, d22))
Умножим DS = ((d11, 0), (0, d22)) ((s11, s12), (0, s22)) = ((d11s11, d11s12), (0, d22s22)). Она сохранила верхнетреугольную форму (позже покажем, что умножение верхнетреугольной на почти верхнетреугольную сохраняет форму). Домножим на S*. S*DS = ((s11, 0), (s12, s22))((d11s11, d11s12), (0, d22s22)) = ((d11s112, d11s12s11), (d11s12s11, d11s122 + d22s222)) = A. Поэлементно приравниваем компоненты.
- d11s112 = a11
- d11s12s11 = a12
- d11s122 + d22s222 = a22
Посмотрим на первое уравнение. Из него понятно, что d11 = sign a11. Тогда отсюда получаем s11 = sqrt(|a11|). Дальше смотрим на второе уравнение: s12 = a12/d11s11. Теперь последнее уравнение рассматриваем. Перепишем его в виде: d22s222 = a22 − d11s122. Отсюда получим d22 = sign(a22 − d11s122), s22 = sqrt(|a22 − d11s122|). Таким образом, мы показали, что для матрицы 2×2 в таком виде осуществима.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |