Численные Методы, 01 лекция (от 12 февраля)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1296 участника 132.230.76.3 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | = Глава 1. Численные методы линейной алгебры = |
- | + | ||
- | + | Большой класс методов, до сих пор расширяется. Вычислительная математика, казалось бы, должна сократиться в количестве задач. Но решение одних задач порождает новые. | |
- | + | ||
+ | == Параграф 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> | ||
+ | |||
+ | Есть три алгоритма решения данных систем — метод Крамера, метод Гаусса и метод квадратного корня. Порядок систем, которые решают современная математика, очень высокий (миллионы, десятки миллионов уравнений). В результате должны строить такие алгоритмы, которые оптимальны с точки зрения вычислительных затрат. При этом важно учитывать специфику задачи. | ||
+ | |||
+ | Две группы методов: | ||
+ | # Прямые (точные) методы | ||
+ | # Итерационные (приближённые) методы | ||
+ | |||
+ | Прямые методы — методы, которые позволяют реализовать в алгоритме определённые формулы, то есть аналитическое решение. Точными их назвать трудно, потому что в компьютере идёт округление. Позволяют решить задачу за конечное число действий, используя прямые формулы. Сюда относятся: метод Крамера (~m!), метод Гаусса (~<sup>m<sup>3</sup></sup>/<sub>3</sub> — самый эффективный из прямых для произвольных матриц), метод квадратного корня. | ||
+ | |||
+ | Зачем тогда итерационные методы? Задаётся начальное приближение Х<sub>0</sub>, далее выстраивается итерационный процесс, получая последовательно X<sub>n</sub> — n-я итерация, причём предел совпадает с точным решением. Находим приближения, пока не ||X<sub>n</sub> – X || < ε , тогда n<sub>0</sub>(ε) — число итераций. Оказывается, что они намного эффективнее прямых методов. | ||
+ | |||
+ | Прямые сравнивают по количеству действий. Под действием понимаем умножение + деление. Итерационные — по числу итераций и сложности итерации. | ||
+ | |||
+ | Если в некоторых приближениях выбор начальных приближения любой, то в других есть такие начальные приближения, при которых метод не будет сходиться. | ||
+ | |||
+ | Норма. Обычно это евклидова норма. Методы, которые будем рассматривать, в одной норме будут сходиться, а в другой нет. Не смотря на то, что нормы эквивалентны, при определённых параметрах константы эквивалентности устремляются к бесконечности. | ||
+ | |||
+ | Другие задачи, связанные с СЛАУ: | ||
+ | # Задача на собственные значения. Это задача о нахождении такого числа λ, что Ax = λ × x, x ≠ 0 — собственный вектор, λ — собственное значение. Две группы методов: степенные (решает частичную проблему собственных значений — нахождение отдельных собственных значений), QR-алгоритм (решение полной проблемы собственных значений). Это самый сильный алгоритм, он для произвольной матрицы. | ||
+ | # Нахождение обратной матрицы. За n<sup>3</sup> действий можно обратить матрицу. | ||
+ | |||
+ | == Параграф 2. Связь метода Гаусса с разложением матрицы на множители == | ||
+ | |||
+ | Пусть есть система (1): | ||
+ | |||
+ | Метод Гаусса: | ||
+ | |||
+ | Cводим A к верхнетреугольной с единицами на диагонали = С. это требует <sup>(m<sup>3</sup>−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 − 1)</sup>/<sub>2</sub> действий. Поэтому мы начнём матрицу А факторизовать, чтобы был выигрыш. Поставим задачу: а можно ли матрицу А в виде произведения B × C? | ||
+ | * А = B × 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> = Σ<sub>l = 1</sub><sup>m</sup>b<sub>il</sub>c<sub>lj</sub> | ||
+ | |||
+ | a<sub>ij</sub> = Σ<sub>l = 1</sub><sup>i−1</sup>b<sub>il</sub>c<sub>lj</sub> + b<sub>ii</sub>c<sub>ij</sub> + Σ<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>×c<sub>lj</sub> = a<sub>ij</sub> − Σ<sub>l=1</sub><sup>i−1</sup> b<sub>il</sub>×c<sub>lj</sub>, b<sub>ii</sub> ≠ 0, тогда можем поделить: | ||
+ | |||
+ | 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) | ||
+ | |||
+ | a<sub>ij</sub> = Σ<sub>l=1</sub><sup>j−1</sup> b<sub>il</sub>×c<sub>lj</sub> + b<sub>ij</sub>×c<sub>jj</sub> + Σ<sub>l=j+1</sub><sup>m</sup> b<sub>il</sub>×c<sub>lj</sub> | ||
+ | |||
+ | b<sub>ij</sub>×c<sub>jj</sub> = b<sub>ij</sub> | ||
+ | |||
+ | c<sub>lj</sub> = 0, l > j | ||
+ | |||
+ | 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) | ||
+ | |||
+ | Эта система нелинейная, но если специальным образом организовать алгоритм, то мы всё вычислим. | ||
+ | |||
+ | Завтра в П-5 | ||
+ | |||
+ | {{Численные Методы}} | ||
+ | |||
+ | {{Lection-stub}} |
Текущая версия
[править] Глава 1. Численные методы линейной алгебры
Большой класс методов, до сих пор расширяется. Вычислительная математика, казалось бы, должна сократиться в количестве задач. Но решение одних задач порождает новые.
[править] Параграф 1. Введение
Система линейных алгебраических уравнений
- Ax = f (1)
- A (m × m), det A ≠ 0 — решение есть, оно единственное
- x = (x1, x2, ... xm)T
- f = (f1, f2, ... fm)T
Есть три алгоритма решения данных систем — метод Крамера, метод Гаусса и метод квадратного корня. Порядок систем, которые решают современная математика, очень высокий (миллионы, десятки миллионов уравнений). В результате должны строить такие алгоритмы, которые оптимальны с точки зрения вычислительных затрат. При этом важно учитывать специфику задачи.
Две группы методов:
- Прямые (точные) методы
- Итерационные (приближённые) методы
Прямые методы — методы, которые позволяют реализовать в алгоритме определённые формулы, то есть аналитическое решение. Точными их назвать трудно, потому что в компьютере идёт округление. Позволяют решить задачу за конечное число действий, используя прямые формулы. Сюда относятся: метод Крамера (~m!), метод Гаусса (~m3/3 — самый эффективный из прямых для произвольных матриц), метод квадратного корня.
Зачем тогда итерационные методы? Задаётся начальное приближение Х0, далее выстраивается итерационный процесс, получая последовательно Xn — n-я итерация, причём предел совпадает с точным решением. Находим приближения, пока не ||Xn – X || < ε , тогда n0(ε) — число итераций. Оказывается, что они намного эффективнее прямых методов.
Прямые сравнивают по количеству действий. Под действием понимаем умножение + деление. Итерационные — по числу итераций и сложности итерации.
Если в некоторых приближениях выбор начальных приближения любой, то в других есть такие начальные приближения, при которых метод не будет сходиться.
Норма. Обычно это евклидова норма. Методы, которые будем рассматривать, в одной норме будут сходиться, а в другой нет. Не смотря на то, что нормы эквивалентны, при определённых параметрах константы эквивалентности устремляются к бесконечности.
Другие задачи, связанные с СЛАУ:
- Задача на собственные значения. Это задача о нахождении такого числа λ, что Ax = λ × x, x ≠ 0 — собственный вектор, λ — собственное значение. Две группы методов: степенные (решает частичную проблему собственных значений — нахождение отдельных собственных значений), QR-алгоритм (решение полной проблемы собственных значений). Это самый сильный алгоритм, он для произвольной матрицы.
- Нахождение обратной матрицы. За n3 действий можно обратить матрицу.
[править] Параграф 2. Связь метода Гаусса с разложением матрицы на множители
Пусть есть система (1):
Метод Гаусса:
Cводим A к верхнетреугольной с единицами на диагонали = С. это требует (m3−m)/3 действий. То есть самый большой объём работ затрачивается на сведение матрицы. Теперь Cx = f1. Для перехода к f1 требуется m(m+1)/2 действий. Обратный ход требует m(m − 1)/2 действий. Поэтому мы начнём матрицу А факторизовать, чтобы был выигрыш. Поставим задачу: а можно ли матрицу А в виде произведения B × C?
- А = B × C (2)
Не любую матрицу можно так преобразовать.
B — нижнетреугольная матрица:
b11 | 0 | 0 | ... | 0 |
b21 | b22 | 0 | ... | 0 |
... | ||||
b1m | b2m | b3m | ... | bmm |
C:
1 | c12 | c13 | ... | c1m |
0 | 1 | c23 | ... | c2m |
... | ||||
0 | 0 | 0 | ... | 1 |
Пока будем предполагать, что то, на что делим, не ноль, а потом будем подбирать достаточные условия для этого.
aij = Σl = 1mbilclj
aij = Σl = 1i−1bilclj + biicij + Σl = i + 1mbilclj
bil = 0 если l > i, значит, третьего слагаемого нет.
bii×clj = aij − Σl=1i−1 bil×clj, bii ≠ 0, тогда можем поделить:
cij = (aij − Σl=1i−1 bil×clj)/bii, i < j ... (3)
aij = Σl=1j−1 bil×clj + bij×cjj + Σl=j+1m bil×clj
bij×cjj = bij
clj = 0, l > j
bij = aij − Σl=1j−1 bil×clj, i ≥ j ... (4)
Эта система нелинейная, но если специальным образом организовать алгоритм, то мы всё вычислим.
Завтра в П-5
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
Календарь
|
|
|
Дополнительная информация |
Материалы к экзамену |