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

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

Версия от 09:49, 19 июня 2007; Esyr01 (Обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Большой класс методов, до сих пор расширяется. Вычислительная математика, казалось бы, должна сократиться в количестве задач. Но решение одних задач порождает новые.

Параграф 1. Введение

Система линейных алгебраических уравнений

  • Ax = f (1)
  • A (m × m), det A ≠ 0 — решение есть, оно единственное
  • x = (x1, x2, ... xm)T
  • f = (f1, f2, ... fm)T

Есть три алгоритма решения данных систем — метод Крамера, метод Гаусса и метод квадратного корня. Порядок систем, которые решают современная математика, очень высокий (миллионы, десятки миллионов уравнений). В результате должны строить такие алгоритмы, которые оптимальны с точки зрения вычислительных затрат. При этом важно учитывать специфику задачи.

Две группы методов:

  1. Прямые (точные) методы
  2. Итерационные (приближённые) методы

Прямые методы — методы, которые позволяют реализовать в алгоритме определённые формулы, то есть аналитическое решение. Точными их назвать трудно, потому что в компьютере идёт округление. Позволяют решить задачу за конечное число действий, используя прямые формулы. Сюда относятся: метод Крамера (~m!), метод Гаусса (~m3/3 — самый эффективный из прямых для произвольных матриц), метод квадратного корня.

Зачем тогда итерационные методы? Задаётся начальное приближение Х0, далее выстраивается итерационный процесс, получая последовательно Xn — n-я итерация, причём предел совпадает с точным решением. Находим приближения, пока не ||Xn – X || < ε , тогда n0(ε) — число итераций. Оказывается, что они намного эффективнее прямых методов.

Прямые сравнивают по количеству действий. Под действием понимаем умножение + деление. Итерационные — по числу итераций и сложности итерации.

Если в некоторых приближениях выбор начальных приближения любой, то в других есть такие начальные приближения, при которых метод не будет сходиться.

Норма. Обычно это евклидова норма. Методы, которые будем рассматривать, в одной норме будут сходиться, а в другой нет. Не смотря на то, что нормы эквивалентны, при определённых параметрах константы эквивалентности устремляются к бесконечности.

Другие задачи, связанные с СЛАУ:

  1. Задача на собственные значения. Это задача о нахождении такого числа λ, что Ax = λ × x, x ≠ 0 — собственный вектор, λ — собственное значение. Две группы методов: степенные (решает частичную проблему собственных значений — нахождение отдельных собственных значений), QR-алгоритм (решение полной проблемы собственных значений). Это самый сильный алгоритм, он для произвольной матрицы.
  2. Нахождение обратной матрицы. За 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


Календарь

Февраль
пн
12 19
вт
13 20 27
Март
пн
05 12 19 26
вт
06 13 20 27
Апрель
пн
02 09 16 23 29
вт
03 10 17 24

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

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

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

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


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



Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы