Нормы матриц. Согласованность и подчиненность норм.

Нормой матрицы назовем поставленное в соответствие этой матрице вещественное число ||A|| такое, что которое как вещественное число ставится в соответствие каждой матрице из n-мерного пространства и удовлетворяет 4 аксиомам:

1. ||A||³0 и ||A||=0, только если A – нулевая матрица;

2. ||αA||=|α|·||A||, где a R;

3. ||A+B||£||A||+||B||;

4. ||A·B||£||A||·||B||. (свойство мультипликативности)

Норма матриц может быть введена различными способами. Матрицу A можно рассматривать как n²-мерный вектор.

Эта норма называется евклидовой нормой матрицы.

Если для любой квадратной матрицы A и любого вектора x, размерность которого равна порядку матрицы, выполняется неравенство ||Ax||£||A||·||x||,

то говорят, что норма матрицы A согласована с нормой вектора. Заметим, что слева в последнем условии стоит норма вектора (Ax – вектор).

С заданной векторной нормой согласованы различные матричные нормы. Выберем среди них наименьшую. Таковой будет

Эта матричная норма- подчиненная заданной векторной норме. Существование максимума в этом выражении следует из непрерывности нормы, ибо всегда существует вектор x -> ||x||=1 и ||Ax||=||A||.

Покажем, xто норма N(A) не подчинена ни одной векторной норме. Нормы матрицы, подчиненные ранее введенным векторным нормам, выражаются следующим образом:

1. ||A||_¥= |a_ij| (норма-максимум)

2. ||A||₁= |a_ij| (норма-сумма)

3. ||A||₂= , (спектральная норма)

где s_1-наибольшое собств значение симметричной матрицы A¢A, являющейся произведением транспонированной и исходной матриц. Т к матрица A¢A симметричная, то все ее собственные значения вещественны и положительны. Число l -собств значение, а ненулевой вектор x – собственный вектор матрицы A(если они связаны между собой соотношением Ax=lx). Если же матрица A сама является симметричной, A¢ = A, то A¢A = A² и тогда s₁= , где - наибольшее по модулю собственное значение матрицы A. Следовательно, в этом случае мы имеем = .

Собственные числа матрицы не превышают любой из ее согласованных норм. Нормируя определяющее собственные числа соотношение, получим ||λx||=||Ax||, |λ|·||x||=||Ax||£||A||·||x||, |λ|£||A||

Поскольку справедливо ||A||₂£||A||_e, где евклидова норма вычисляется просто, в оценках вместо спектральной нормы можно использовать евклидову норму матрицы.

30.Обусловленность систем уравнений. Коэффициент обусловленности.

Степень обусловленности - влияние решения на исходные данные. Ax = b : вектору b соответствует решение x. Пусть b изменится на величину . Тогда вектору b+ будет соответствовать новое решение x+ : A(x+ ) = b+ . Так как система линейна, то Ax + A = b+ , тогда A = ; = ; = ; b = Ax; = тогда ; * , где - относительная погрешность возмущения решения, – коэффициент обусловленности cond(A) (во сколько раз может возрасти погрешность решения), – относительное возмущение вектора b. cond(A) = ; cond(A)* Свойства коэффициента: зависит от выбора нормы матрицы; cond( = cond(A); умножение матрицы на число не влияет на коэффициент обусловленности. Чем больше коэффициент, тем сильнее сказывается на решении СЛАУ ошибка в исходных данных. Число обусловленности не может быть меньше 1.

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

Часто возникает необходимость в решении систем, матрицы которых, являясь слабозаполненными, т.е. содержащими много ненулевых элементов. Матрицы таких систем обычно имеют определенную структуру, среди которых выделяют системы с матрицами ленточной структуры, т.е. в них ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях. Для решения систем с ленточными матрицами метод Гаусса можно трансформировать в более эффективные методы. Рассмотрим наиболее простой случай ленточных систем, к которым, как мы увидим впоследствии, сводится решение задач дискретизации краевых задач для дифференциальных уравнений методами конечных разностей, конечных элементов и др. Трёх диагональной матрицей называется такая матрица, у которой ненулевые элементы стоят только на главной диагонали и соседних с ней:

У трёх диагональной матрицы ненулевых элементов всего (3n-2).

Переобозначим коэффициенты матрицы:

.

Тогда в покомпонентной записи систему можно представить в виде:

a_{i *}x_i-1+ b_{i *}x_i+ c_{i *}x_i+1= d_i,i=1, 2,…, n; (7)

a₁=0, c_n=0. (8)

Структура системы предполагает взаимосвязь только между соседними неизвестными:

x_i=x_i_*x_i₊₁+h_i (9)

Уменьшим в представлении (9) индекс на единицу:

x_i_-1=x_i_-1*x_i + h_i_-1 и подставим в (7):

a_i(x_i-1*x_i+ h_i-1)+ b_{i *}x_i+ c_{i *}x_i+1= d_i

(a_{i *}x_i-1 + b_i)x_i = –c_{i *} x_i+1+d_i –a_{i *}h_i-1

Сравнивая полученное выражение с представлением (7), получаем:

(10)

Формулы (10) представляют рекуррентные соотношения для вычисления коэффициентов прогонки. Они требуют задания начальных значений. В соответствии с первым условием (8) для i =1 имеем a₁=0, а значит

, .

Далее вычисляются и сохраняются остальные прогоночные коэффициенты по формулам (10) для i=2,3,…, n, причем при i=n, с учетом второго условия (8), получаем x_n=0. Следовательно, в соответствии с формулой (9) x_n = h_n.

После чего по формуле (9) последовательно находятся неизвестные x_n_-1, x_n_-2, …, x₁. Этот этап расчета называется обратным ходом, в то время как вычисление прогоночных коэффициентов называется прямым ходом прогонки.

Для успешного применения метода прогонки нужно, чтобы в процессе вычислений не возникало ситуаций с делением на нуль, а при большой размерности систем не должно быть быстрого роста погрешностей округления. Будем называть прогонку корректной, если знаменатель прогоночных коэффициентов (10) не обращается в ноль, и устойчивой, если ½x_i½<1 при всех i=1,2,…, n. Достаточные условия корректности и устойчивости прогонки, которые во многих приложениях выполняются, определяются теоремой.

Теорема. Пусть коэффициенты a_i и c_i уравнения (7) при i=2,3,..., n-1 отличны от нуля и пусть

½b_i½>½a_i½+½c_i½ при i=1, 2,..., n. (11)

Тогда прогонка, определяемая формулами (10), (9) корректна и устойчива.