Кратко и по делу.
1) Числовая устойчивость
- Разложение по строке (Лаплас): комбинирует много слагаемых с чередующимися знаками, поэтому чувствительно к вычитаниям и накоплению округлённых ошибок; при плохо обусловленных матрицах погрешности могут экспоненциально возрастать.
- Приведение к верхнетреугольному виду (гауссова элиминация с частичным выбором главного элемента): в форме LU с частичным пазами обычно «обратно устойчиво» и в практике даёт существенно меньшие ошибки. Однако если матрица очень плохо обусловлена, то любая схема даёт большую относительную ошибку — это свойство самой матрицы.
Вывод: по устойчивости обычно предпочтительна гауссова элиминация с частичным выбором главного элемента.
2) Вычислительная сложность
- Разложение по строке: сложность растёт факториально; в общем случае $O(n\cdot (n-1)!)$ (часто говорят «экспоненциально/факториально»). Для небольшого $n$ (например $n=4$) это константа, но при росте $n$ быстро невыгодно.
- Элиминация (LU): сложность полиномиальная, приблизительно $O(n^3)$; более точно для операций порядка $\frac{2}{3}{n}^3$ арифметических операций. Для $n=4$ обе методы дают небольшое число операций, но при увеличении $n$ элиминация выигрывает.
3) Когда какой метод предпочтителен — конкретные примеры
- Когда разложение по строке предпочтительнее:
- Матрица с очень разреженной строкой (много нулей в выбранной строке). Тогда разложение по этой строке экономно и точнее. Пример:
A=(0005123443211000) A=\begin{pmatrix}
0&0&0&5\\[4pt]
1&2&3&4\\[4pt]
4&3&2&1\\[4pt]
1&0&0&0
\end{pmatrix}
A= 0141 0230 0320 5410 расширение по первой строке требует вычислить только один минор.
- Если нужна точная детерминанта в целой арифметике для очень малого $n$ (и нет проблем с ростом промежуточных чисел), разложение по строке просто реализуется.
- Когда элиминация предпочтительнее:
- Общие «плотные» матрицы и большинство вычислительных задач: предпочтительна гауссова элиминация с частичным выбором главного элемента (pivoting) как более устойчивая.
- Матрицы с нулевым (или близким к нулю) элементом на первом шаге: без pivoting элиминация «сломается». Пример, где обычная элиминация без выбора главного элемента выдаст деление на ноль, а разложение по строке корректно:
B=(0123100000100001) B=\begin{pmatrix}
0&1&2&3\\[4pt]
1&0&0&0\\[4pt]
0&0&1&0\\[4pt]
0&0&0&1
\end{pmatrix}
B= 0100 1000 2010 3001 (элиминация требует перестановки строк; с частичным pivoting всё нормально).
- Плохо обусловленные матрицы (где небольшие численные ошибки сильно меняют результат): пример классический — матрица Гильберта размера $4\times 4$,
Hij=1i+j−1,H=(1121314121314151314151614151617), H_{ij}=\frac{1}{i+j-1},\qquad H=\begin{pmatrix}
1&\tfrac12&\tfrac13&\tfrac14\\[4pt]
\tfrac12&\tfrac13&\tfrac14&\tfrac15\\[4pt]
\tfrac13&\tfrac14&\tfrac15&\tfrac16\\[4pt]
\tfrac14&\tfrac15&\tfrac16&\tfrac17
\end{pmatrix},
Hij =i+j−11 ,H= 121 31 41 21 31 41 51 31 41 51 61 41 51 61 71 , у которой большое число обусловленности (порядка $10^4$ — $10^5$). Для таких матриц любая прямая формула даёт большие относительные погрешности, но LU с частичным выбором обычно лучше, чем прямое разложение по строке.
- Матрицы с элементами сильно разного масштаба, приводящие к вычитанию больших близких чисел в формулах детерминанта. Пример «почти одинаковые строки»:
C=(108108108108108108+1108108108108108+2108108108108108+3), C=\begin{pmatrix}
10^8&10^8&10^8&10^8\\[4pt]
10^8&10^8+1&10^8&10^8\\[4pt]
10^8&10^8&10^8+2&10^8\\[4pt]
10^8&10^8&10^8&10^8+3
\end{pmatrix},
C= 108108108108 108108+1108108 108108108+2108 108108108108+3 , детерминанта мала по сравнению с элементами; при разложении по строке будут большие потери точности при вычитаниях — LU с частичным pivoting обычно даёт лучшее численное поведение.
4) Практическое правило
- Для плавающей арифметики и общего использования: используйте гауссову элиминацию (LU) с частичным выбором главного элемента; для экстремально плохо обусловленных задач дополнительно масштабируйте/используйте более устойчивые методы (полное pivoting, сингулярное разложение) или повышенную точность.
- Для очень маленьких и разреженных случаев или при необходимости точных целых вычислений выгодно разложение по строке по удобной строке/столбцу или специализированные алгоритмы (Bareiss для целых).
Конец.