Энциклопедичный YouTube

1 / 1

✪ Норма вектора. Часть 4.

Субтитры

Определение

Пусть K - основное поле (обычно K = R или K = C ) и - линейное пространство всех матриц с m строками и n столбцами, состоящих из элементов K . На пространстве матриц задана норма, если каждой матрице ставится в соответствие неотрицательное действительное число ‖ A ‖ {\displaystyle \|A\|} , называемое ее нормой, так, что

В случае квадратных матриц (то есть m = n ), матрицы можно перемножать не выходя из пространства, и потому нормы в этих пространствах обычно также удовлетворяют свойству субмультипликативности :

Субмультипликативность может выполняться также и для норм неквадратных матриц, но определённых сразу для нескольких нужных размеров. Именно, если A - матрица ℓ  × m , и B - матрица m  × n , то A B - матрица ℓ  × n .

Операторные нормы

Важным классом матричных норм являются операторные нормы , также именуемые подчинёнными или индуцированными . Операторная норма однозначно строится по двум нормам, определённым в и , исходя из того, что всякая матрица m  × n представляется линейным оператором из K n {\displaystyle K^{n}} в K m {\displaystyle K^{m}} . Конкретно,

‖ A ‖ = sup { ‖ A x ‖ : x ∈ K n , ‖ x ‖ = 1 } = sup { ‖ A x ‖ ‖ x ‖ : x ∈ K n , x ≠ 0 } . {\displaystyle {\begin{aligned}\|A\|&=\sup\{\|Ax\|:x\in K^{n},\ \|x\|=1\}\\&=\sup \left\{{\frac {\|Ax\|}{\|x\|}}:x\in K^{n},\ x\neq 0\right\}.\end{aligned}}}

При условии согласованного задания норм на пространствах векторов, такая норма является субмультипликативной (см. ).

Примеры операторных норм

Свойства спектральной нормы:

1. Спектральная норма оператора равна максимальному сингулярному числу этого оператора.
2. Спектральная норма нормального оператора равна абсолютному значению максимального по модулю собственного значения этого оператора.
3. Спектральная норма не изменяется при умножении матрицы на ортогональную (унитарную) матрицу.

Неоператорные нормы матриц

Существуют нормы матриц, не являющиеся операторными. Понятие неоператорных норм матриц ввел Ю. И. Любич и исследовал Г. Р. Белицкий.

Пример неоператорной нормы

Например, рассмотрим две различные операторные нормы ‖ A ‖ 1 {\displaystyle \|A\|_{1}} и ‖ A ‖ 2 {\displaystyle \|A\|_{2}} , например строчную и столбцовую нормы. Образуем новую норму ‖ A ‖ = m a x (‖ A ‖ 1 , ‖ A ‖ 2) {\displaystyle \|A\|=max(\|A\|_{1},\|A\|_{2})} . Новая норма обладает кольцевым свойством ‖ A B ‖ ≤ ‖ A ‖ ‖ B ‖ {\displaystyle \|AB\|\leq \|A\|\|B\|} , сохраняет единицу ‖ I ‖ = 1 {\displaystyle \|I\|=1} и не является операторной .

Примеры норм

Векторная p {\displaystyle p} -норма

Можно рассматривать m × n {\displaystyle m\times n} матрицу как вектор размера m n {\displaystyle mn} и использовать стандартные векторные нормы:

‖ A ‖ p = ‖ v e c (A) ‖ p = (∑ i = 1 m ∑ j = 1 n | a i j | p) 1 / p {\displaystyle \|A\|_{p}=\|\mathrm {vec} (A)\|_{p}=\left(\sum _{i=1}^{m}\sum _{j=1}^{n}|a_{ij}|^{p}\right)^{1/p}}

Норма Фробениуса

Норма Фробениуса , или евклидова норма представляет собой частный случай p -нормы для p = 2 : ‖ A ‖ F = ∑ i = 1 m ∑ j = 1 n a i j 2 {\displaystyle \|A\|_{F}={\sqrt {\sum _{i=1}^{m}\sum _{j=1}^{n}a_{ij}^{2}}}} .

Норма Фробениуса легко вычисляется (по сравнению, например, со спектральной нормой). Обладает следующими свойствами:

‖ A x ‖ 2 2 = ∑ i = 1 m | ∑ j = 1 n a i j x j | 2 ≤ ∑ i = 1 m (∑ j = 1 n | a i j | 2 ∑ j = 1 n | x j | 2) = ∑ j = 1 n | x j | 2 ‖ A ‖ F 2 = ‖ A ‖ F 2 ‖ x ‖ 2 2 . {\displaystyle \|Ax\|_{2}^{2}=\sum _{i=1}^{m}\left|\sum _{j=1}^{n}a_{ij}x_{j}\right|^{2}\leq \sum _{i=1}^{m}\left(\sum _{j=1}^{n}|a_{ij}|^{2}\sum _{j=1}^{n}|x_{j}|^{2}\right)=\sum _{j=1}^{n}|x_{j}|^{2}\|A\|_{F}^{2}=\|A\|_{F}^{2}\|x\|_{2}^{2}.}

• Субмультипликативность : ‖ A B ‖ F ≤ ‖ A ‖ F ‖ B ‖ F {\displaystyle \|AB\|_{F}\leq \|A\|_{F}\|B\|_{F}} , так как ‖ A B ‖ F 2 = ∑ i , j | ∑ k a i k b k j | 2 ≤ ∑ i , j (∑ k | a i k | | b k j |) 2 ≤ ∑ i , j (∑ k | a i k | 2 ∑ k | b k j | 2) = ∑ i , k | a i k | 2 ∑ k , j | b k j | 2 = ‖ A ‖ F 2 ‖ B ‖ F 2 {\displaystyle \|AB\|_{F}^{2}=\sum _{i,j}\left|\sum _{k}a_{ik}b_{kj}\right|^{2}\leq \sum _{i,j}\left(\sum _{k}|a_{ik}||b_{kj}|\right)^{2}\leq \sum _{i,j}\left(\sum _{k}|a_{ik}|^{2}\sum _{k}|b_{kj}|^{2}\right)=\sum _{i,k}|a_{ik}|^{2}\sum _{k,j}|b_{kj}|^{2}=\|A\|_{F}^{2}\|B\|_{F}^{2}} .
• ‖ A ‖ F 2 = t r ⁡ A ∗ A = t r ⁡ A A ∗ {\displaystyle \|A\|_{F}^{2}=\mathop {\rm {tr}} A^{*}A=\mathop {\rm {tr}} AA^{*}} , где t r ⁡ A {\displaystyle \mathop {\rm {tr}} A} - след матрицы A {\displaystyle A} , A ∗ {\displaystyle A^{*}} - эрмитово-сопряжённая матрица .
• ‖ A ‖ F 2 = ρ 1 2 + ρ 2 2 + ⋯ + ρ n 2 {\displaystyle \|A\|_{F}^{2}=\rho _{1}^{2}+\rho _{2}^{2}+\dots +\rho _{n}^{2}} , где ρ 1 , ρ 2 , … , ρ n {\displaystyle \rho _{1},\rho _{2},\dots ,\rho _{n}} - сингулярные числа матрицы A {\displaystyle A} .
• ‖ A ‖ F {\displaystyle \|A\|_{F}} не изменяется при умножении матрицы A {\displaystyle A} слева или справа на ортогональные (унитарные) матрицы .

Максимум модуля

Норма максимума модуля - другой частный случай p -нормы для p = ∞ .

‖ A ‖ max = max { | a i j | } . {\displaystyle \|A\|_{\text{max}}=\max\{|a_{ij}|\}.}

Норма Шаттена

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

Матричная норма ‖ ⋅ ‖ a b {\displaystyle \|\cdot \|_{ab}} на K m × n {\displaystyle K^{m\times n}} называется согласованной с нормами ‖ ⋅ ‖ a {\displaystyle \|\cdot \|_{a}} на K n {\displaystyle K^{n}} и ‖ ⋅ ‖ b {\displaystyle \|\cdot \|_{b}} на K m {\displaystyle K^{m}} , если:

‖ A x ‖ b ≤ ‖ A ‖ a b ‖ x ‖ a {\displaystyle \|Ax\|_{b}\leq \|A\|_{ab}\|x\|_{a}}

для любых A ∈ K m × n , x ∈ K n {\displaystyle A\in K^{m\times n},x\in K^{n}} . Операторная норма по построению является согласованной с исходной векторной нормой.

Примеры согласованных, но не подчиненных матричных норм:

Эквивалентность норм

Все нормы в пространстве K m × n {\displaystyle K^{m\times n}} эквивалентны, то есть для любых двух норм ‖ . ‖ α {\displaystyle \|.\|_{\alpha }} и ‖ . ‖ β {\displaystyle \|.\|_{\beta }} и для любой матрицы A ∈ K m × n {\displaystyle A\in K^{m\times n}} верно двойное неравенство.

» Урок 12. Ранг матрицы. Вычисление ранга матрицы. Норма матриц

Урок №12. Ранг матрицы. Вычисление ранга матрицы. Норма матриц.

Если все миноры матрицы A порядка k равны нулю, то все миноры порядка k+1, если такие существуют, тоже равны нулю.
Рангом матрицы A называется наибольший из порядков миноров матрицы A , отличных от нуля.
Максимум ранг может быть равен минимальному числу из количества строк или столбцов матрицы, т.е. если матрица имеет размер 4х5, то максимум ранг будет 4.
Минимум ранг матрицы равен 1, если только вы не имеете дело с нулевой матрицей, там всегда ранг равен нулю.

Ранг невырожденной квадратной матрицы порядка n равен n, так как ее определитель является минором порядка n и у невырожденной матрицы отличен от нуля.
При транспонировании матрицы ее ранг не меняется.

Пусть ранг матрицы равен . Тогда любой минор порядка , отличный от нуля, называется базисным минором .
Пример. Дана матрица А.

Определитель матрицы равен нулю.
Минор второго порядка . Следовательно, r(A)=2 и минор базисный.
Базисным минором является также минор .
Минор , т.к. =0, поэтому не будет базисным.
Задание : самостоятельно проверить, какие еще миноры второго порядка будут базисными, а какие нет.

Нахождение ранга матрицы с помощью вычисления всех ее миноров требует слишком большой вычислительной работы. (Читатель может проверить, что в квадратной матрице четвертого порядка 36 миноров второго порядка.) Поэтому для нахождения ранга применяется другой алгоритм. Для его описания потребуется ряд дополнительных сведений.

Назовем элементарными преобразованиями матриц следующие действия над ними:
1) перестановка строк или столбцов;
2) умножение строки или столбца на число отличное от нуля;
3) добавление к одной из строк другой строки, умноженной на число или добавление к одному из столбцов другого столбца, умноженного на число.

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

Пусть требуется вычислить ранг матрицы размеров m x n .

В результате расчетов матрица А1 имеет вид

Если все строки, начиная с третьей, нулевые, то , так как минор . Иначе перестановкой строк и столбцов с номерами, большими двух, добиваемся, чтобы третий элемент третьей строки был отличен от нуля. Далее, добавлением третьей строки, умноженной на соответствующие числа, к строкам с большими номерами получаем нули в третьем столбце, начиная с четвертого элемента, и т.д.
На каком-то этапе мы придем к матрице, у которой все строки, начиная с (r+1)-ой, равны нулю (или отсутствуют при ), а минор в первых строках и первых столбцах является определителем треугольной матрицы с ненулевыми элементами на диагонали. Ранг такой матрицы равен . Следовательно, Rang(A)=r.

В предложенном алгоритме нахождения ранга матрицы все вычисления должны производиться без округлений. Сколь угодно малое изменение хотя бы в одном из элементов промежуточных матриц может привести к тому, что полученный ответ будет отличаться от ранга исходной матрицы на несколько единиц.
Если в исходной матрице элементы были целыми числами, то и вычисления удобно производить без использования дробей. Поэтому на каждом этапе целесообразно умножать строки на такие числа, чтобы при вычислениях дроби не возникали.

В лабораторно-практической работе рассмотрим пример нахождения ранга матрицы.

АЛГОРИТМ НАХОЖДЕНИЯ НОРМЫ МАТРИЦЫ .
Выделяют всего три нормы матрицы.
Первая норма матрицы = максимальному из чисел, полученных при сложении всех элементов каждого столбца, взятых по модулю.
Пример: пусть дана матрица А размера 3х2 (рис.10). В первом столбце стоят элементы: 8, 3, 8. Все элементы положительные. Найдем их сумму: 8+3+8=19. Во втором столбце стоят элементы: 8, -2, -8. Два элемента - отрицательные, поэтому при сложении этих чисел, необходимо подставлять модуль этих чисел (т.е. без знаков "минус"). Найдем их сумму: 8+2+8=18. Максимальное из этих двух чисел - это 19. Значит первая норма матрицы равна 19.

Рисунок 10.

Вторая норма матрицы представляет из себя квадратный корень из суммы квадратов всех элементов матрицы. А это значит мы возводим в квадрат все элементы матрицы, затем складываем полученные значения и из результата извлекаем квадратный корень.
В нашем случае, 2 норма матрицы получилась равна квадратному корню из 269. На схеме, я приближенно извлекла квадратный корень из 269 и в результате получила приблизительно около 16,401. Хотя более правильно не извлекать корень.

Третья норма матрицы представляет из себя максимальное из чисел, полученных при сложении всех элементов каждой строки, взятых по модулю.
В нашем примере: в первой строке стоят элементы: 8, 8. Все элементы положительные. Найдем их сумму: 8+8=16. В второй строке стоят элементы: 3, -2. Один из элементов отрицательный, поэтому при сложении этих чисел, необходимо подставлять модуль этого числа. Найдем их сумму: 3+2=5. В третьей строке стоят элементы 8, и -8. Один из элементов отрицательный, поэтому при сложении этих чисел, необходимо подставлять модуль этого числа. Найдем их сумму: 8+8=16. Максимальное из этих трех чисел - это 16. Значит третья норма матрицы равна 16.

Составитель: Салий Н.А.

Нормой матрицы назовем поставленное в соответствие этой матрице вещественное число ||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 2 - мерный вектор.

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

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

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

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

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

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

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

2. ||A|| 1 = |a ij | (норма-сумма)

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

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

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

Поскольку справедливо ||A|| 2 £||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 1 =0, c n =0. (8)

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

x i =x i * x i +1 +h i (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) представляют рекуррентные соотношения для вычисления коэффициентов прогонки. Они требуют задания начальных значений. В соответствии с первым условием (8) для i =1 имеем a 1 =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 1 . Этот этап расчета называется обратным ходом, в то время как вычисление прогоночных коэффициентов называется прямым ходом прогонки.

Для успешного применения метода прогонки нужно, чтобы в процессе вычислений не возникало ситуаций с делением на нуль, а при большой размерности систем не должно быть быстрого роста погрешностей округления. Будем называть прогонку корректной , если знаменатель прогоночных коэффициентов (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) корректна и устойчива.