Таким образом

(||δx||/||x||)/(||δb||/||b||)=2/0.000053≈40000≤cond(A).

В данном примере полученное значение совпадает с коэффициентом обусловленности.

30. Свойства коэффициента обусловленности

1. Коэффициент обусловленности зависит от выбора матричной нормы ||A|| (индуцированной векторной нормой, в которой оцениваются погрешности).

2. Коэффициент обусловленности обратной матрицы равен коэффициенту обусловленности исходной матрицы: cond(A^-1)=cond(A).

3. Умножение матрицы на число не меняет ее коэффициента обусловленности: cond(αA)=cond(A). Дело в том, что умножение матрицы на число  для обратной матрицы означает деление ее на это число: ||αA||·||A^-1/α||=||A||·||A^-1||.

4. Если используются подчиненные матричные нормы (для которых норма единичной матрицы есть единица), то, нормируя соотношение E=A·A^-1, получим ||E||=||A·A^-1||≤||A||·||A^-1|| или сond (A)≥1.

5. Оценим коэффициент обусловленности через собственные значения. Пусть собственные числа матрицы A упорядочены по модулю: λ₁λ₂ …. λ_n, т.е. спектральный радиус матрицы A есть (A)= λ₁. Тогда в силу доказанного ранее неравенства (A) ||A|| и соотношения между собственными числами прямой и обратной матриц, имеем ||A||·||A^-1||(A) ·(A^-1)= λ₁/λ_n. Таким образом, оценкой снизу меры обусловленности матрицы A может служить модуль отношения максимального собственного числа к минимальному λ₁/λ_n (эту величину называют числом обусловленности Тодда).

6. Для симметричных матриц число Тодда на самом деле является числом обусловленности, соответствующим спектральной норме матрицы, индуцированной евклидовой нормой вектора. Учитывая смысл собственных чисел матрицы, можно сказать, что число обусловленности показывает величину отношения наибольшего коэффициента растяжения вектора к наименьшему посредством линейного преобразования A.

Следует отметить, что непосредственный подсчет числа обусловленности, особенно при большой размерности матриц, является весьма дорогостоящей процедурой из-за необходимости обращать матрицы или находить собственные значения. Поэтому зачастую о порядке возможного роста относительной погрешности результата решения какой-либо алгебраической задачи относительно данной матрицы судят либо по каким-то достаточным признакам (например, по доминированию элементов главной диагонали матрицы), либо на основе теоретического изучения матрицы, либо путем применения специальных алгоритмов приближенного оценивания cond (A).

31. Решение систем линейных алгебраических уравнений. Метод Гаусса.

Итак, пусть ставится задача решения системы линейных алгебраических уравнений (СЛАУ):

Ax = b. (5)

Все методы решения линейных алгебраических задач (наряду с решением систем, это и вычисление определителей, и обращение матриц, и задачи на собственные значения) можно разбить на два класса: прямые и итерационные. Прямым методом решения СЛАУ называется тот, который даёт точное решение за конечное число арифметических действий. Если операции реализуются точно, то и решение будет точным, в связи с чем к классу прямых методов применяют еще название точные методы. Итерационные методы - это такие методы, в которых точное решение может быть получено лишь в результате бесконечного повторения единообразных действий. В этих методах определяют некоторую последовательность векторов, которая в пределе сходится к точному решению.

Прямые методы различаются по числу действий Q, необходимых для нахождения решения задачи. Мерой различия может также служить число действий q, необходимое для вычисления одного неизвестного. При этом Q=nq. Так, если искать решение задачи (1) известным методом Крамера (через определители), то потребуется Q=O(nn!). Уже для n=20 ни один компьютер не сможет найти решение за обозримый промежуток времени. В методах типа Гаусса Q=O(n³). Для диагональной матрицы Q=n, q=1, т.е. не зависит от n. Метод решения задачи (1) называется экономичным, если q не зависит (или слабо зависит, например q=O(lnn)) от общего числа неизвестных, т.е. от порядка матрицы n. Такие методы предназначены для решения систем с матрицами специального вида. Для произвольной невырожденной матрицы A прямые методы с оценкой q=O(n²) являются оптимальными.

Простейший вариант метода Гаусса – схема единственного деления. Решение системы находится за два этапа:

прямой ход – приведение исходной системы к треугольному виду (к эквивалентной системе с верхней треугольной матрицей);

обратный ход – определение неизвестных системы.

Прямой ход состоит из n шагов, на каждом из которых исключается очередное неизвестное из всех последующих уравнений. Так, на первом шаге, считая a₁₁0, делят первое уравнений на этот элемент, получая

x₁+a₁₂⁽¹⁾x₂+ . . . +a_1n⁽¹⁾x_n=b₁⁽¹⁾. (6)

Верхний индекс при коэффициентах обозначает шаг преобразования. Элемент a₁₁ называется ведущим и ведущим же называется уравнение (6). Это уравнение последовательно умножается сперва на a₂₁ и вычитается из второго, чтобы из него исключить x₁, далее (6) умножается на a₃₁ и вычитается из третьего уравнения системы и т.д. до умножения на a_n1 и исключения x₁ из последного уравнения. Результатом первого шага преобразования будет система, в которой x₁ останется только в первом ведущем уравнении, а все коэффициенты системы будут пересчитаны, т.е. иметь наверху индекс равный единице. Этот процесс повторяется для исключения x₂, ..., x_n. Формулы пересчета коэффициентов ведущего уравнения:

a_kj^(k)= a_kj^(k-1)/ a_kk^(k-1), j = k+1, . . . , n; b_k^(k) = b_k^(k-1)/ a_kk^(k-1).

Коэффициенты последующих уравнений пересчитываются по формулам:

a_ij^(k)= a_ij^(k-1) - a_ik^(k-1)a_kj^(k), b_i^(k)= b_i^(k-1) - a_ik^(k-1) b_k^(k);

i, j = k+1, . . . , n; k = 1, 2, . . . , n-1.

Нулевому значению индекса k соответствуют коэффициенты заданной матрицы. После (n-1)-го шага преобразования последнее уравнение системы приобретет вид

a_nn^(n-1)x_n = b_n^(n-1).

Последний, n-ый шаг преобразования состоит в делении этого уравнения на его ведущий элемент a_nn^(n-1):

x_n = b_n⁽ⁿ⁾.

Остальные значения неизвестных вычисляются по формуле:

, i = n-1, . . . , 1.

Этот процесс вычисления неизвестных представляет второй этап решения системы и носит название обратного хода метода Гаусса.