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

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

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

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

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

• Ax = f (1)
• A (m × m), det A ≠ 0 — решение есть, оно единственное
• x = (x₁, x₂, ... x_m)^T
• f = (f₁, f₂, ... f_m)^T

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

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

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

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

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

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

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

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

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

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

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

Пусть есть система (1):

Метод Гаусса:

Cводим A к верхнетреугольной с единицами на диагонали = С. это требует ^(m3−m)/₃ действий. То есть самый большой объём работ затрачивается на сведение матрицы. Теперь Cx = f₁. Для перехода к f₁ требуется ^m(m+1)/₂ действий. Обратный ход требует ^{m(m − 1)}/₂ действий. Поэтому мы начнём матрицу А факторизовать, чтобы был выигрыш. Поставим задачу: а можно ли матрицу А в виде произведения B × C?

• А = B × C (2)

Не любую матрицу можно так преобразовать.

B — нижнетреугольная матрица:

C:

Пока будем предполагать, что то, на что делим, не ноль, а потом будем подбирать достаточные условия для этого.

a_ij = Σ_{l = 1}^mb_ilc_lj

a_ij = Σ_{l = 1}ⁱ⁻¹b_ilc_lj + b_iic_ij + Σ_{l = i + 1}^mb_ilc_lj

b_il = 0 если l > i, значит, третьего слагаемого нет.

b_ii×c_lj = a_ij − Σ_l=1ⁱ⁻¹ b_il×c_lj, b_ii ≠ 0, тогда можем поделить:

c_ij = ^{(a_ij − Σ_l=1i−1 b_il×c_lj)}/_bii, i < j ... (3)

a_ij = Σ_l=1^j−1 b_il×c_lj + b_ij×c_jj + Σ_l=j+1^m b_il×c_lj

b_ij×c_jj = b_ij

c_lj = 0, l > j

b_ij = a_ij − Σ_l=1^j−1 b_il×c_lj, i ≥ j ... (4)

Эта система нелинейная, но если специальным образом организовать алгоритм, то мы всё вычислим.

Завтра в П-5