1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Если λ1 , λ2 , . . . , λn —её собственные значения, то у обратной матрицы(A∗A)−1 = A−1 (A∗ )−1−1−1собственными значениями являются λ−11 , λ2 , . . . , λn .Доказательство:Напомним, что собственные числа взаимно обратных матрицобратны друг другу: если C — неособенная n × n-матрица иCv = λv, то v = λC −1 v, и, так как λ 6= 0 в силу det C 6= 0,получаем отсюда C −1 v = λ−1 v.Применим этот факт к матрице A∗A.

Если λ1 , λ2 , . . . , λn —её собственные значения, то у обратной матрицы(A∗A)−1 = A−1 (A∗ )−1−1−1собственными значениями являются λ−11 , λ2 , . . . , λn .НоA−1 (A∗ )−1 = A−1 (A−1 )∗ .−1−1Поэтому числа λ−11 , λ2 , . . . , λn образуют набор квадратовсингулярных чисел матрицы A−1 . Отсюда вытекает требуемое.Число обусловленности матрицИтак, для любой неособенной квадратной матрицы A справедливоравенство−1(A).σmax (A−1 ) = σminПоэтому относительно спектральной нормы число обусловленностиматрицы естьcond2 (A) = kAk2 kA−1 k2 =σmax (A).σmin (A)Число обусловленности матрицИтак, для любой неособенной квадратной матрицы A справедливоравенство−1(A).σmax (A−1 ) = σminПоэтому относительно спектральной нормы число обусловленностиматрицы естьcond2 (A) = kAk2 kA−1 k2 =σmax (A).σmin (A)Если A — симметричная матрица, то это выражение упрощается:cond2 (A) =σmax (A)max |λ(A)|=.σmin (A)min |λ(A)|Число обусловленности матрицКак оценивать нормы обратных матриц?Число обусловленности матрицКак оценивать нормы обратных матриц?В общем случае это трудный вопрос .

. .Число обусловленности матрицКак оценивать нормы обратных матриц?В общем случае это трудный вопрос . . .Полезный частный случай:Теорема Алберга-НильсонаПусть A = (aij ) — n × n-матрица с диагональным преобладанием и()Xα := min |aii | −|aij | .1≤i≤nj6=iТогда kA−1 k∞ ≤ α−1 .Доказательство:Прежде всего, заметим, что−1kAk∞kA−1 xk∞kyk∞= max= max=x6=0y6=0 kAyk∞kxk∞где использована замена y = A−1 x.kAyk∞miny6=0 kyk∞−1,Доказательство:Прежде всего, заметим, что−1kAk∞kA−1 xk∞kyk∞= max= max=x6=0y6=0 kAyk∞kxk∞kAyk∞miny6=0 kyk∞−1,где использована замена y = A−1 x.Поэтому для доказательства теоремы достаточно установить, чтоkAyk∞≥αkyk∞для любого ненулевого вектора y.Доказательство:Прежде всего, заметим, что−1kAk∞kA−1 xk∞kyk∞= max= max=x6=0y6=0 kAyk∞kxk∞kAyk∞miny6=0 kyk∞−1,где использована замена y = A−1 x.Поэтому для доказательства теоремы достаточно установить, чтоkAyk∞≥αkyk∞для любого ненулевого вектора y.Это неравенство, в свою очередь, равносильноα kyk∞ ≤ kAyk∞ .Пусть компонента вектора y с наибольшим абсолютным значениемимеет номер k, так что |yk | = max1≤i≤n |yi | = kyk∞ > 0 в силу y 6= 0.Пусть компонента вектора y с наибольшим абсолютным значениемимеет номер k, так что |yk | = max1≤i≤n |yi | = kyk∞ > 0 в силу y 6= 0.По условию теоремы0 < α ≤ |akk | −Xj6=k|akj |,и мы можем умножить это неравенство почленно на |yk | > 0:X|akj | |yk |.0 < α |yk | ≤ |akk | |yk | −j6=kПусть компонента вектора y с наибольшим абсолютным значениемимеет номер k, так что |yk | = max1≤i≤n |yi | = kyk∞ > 0 в силу y 6= 0.По условию теоремы0 < α ≤ |akk | −Xj6=k|akj |,и мы можем умножить это неравенство почленно на |yk | > 0:X|akj | |yk |.0 < α |yk | ≤ |akk | |yk | −j6=kОчевидно, что полученное неравенство только усилится, еслизаменить в сумме из правой части множители |yk | на меньшие илиравные им |yj |, |yj | ≤ |yk |:X0 < α |yk | ≤ |akk | |yk | −|akj | |yj |.j6=kДалее0 < α |yk | ≤ |akk yk | −Xj6=k|akj yj |nnXXakj yj = kAyk∞ .akj yj ≤ max ≤ 1≤k≤n j=1j=1Далее0 < α |yk | ≤ |akk yk | −Xj6=k|akj yj |nnXXakj yj = kAyk∞ .akj yj ≤ max ≤ 1≤k≤n j=1j=1Вспоминая, что|yk | = kyk∞ ,можем заключить, что в самом деле выполняется неравенствоα kyk∞ ≤ kAyk∞ .Это завершает доказательство.Хорошо обусловленныеи плохо обусловленные матрицыОпределениеМатрица называется хорошо обусловленной,если её число обусловленности невелико.Если число обусловленности матрицы велико, будем говорить, чтоматрица плохо обусловлена.Хорошо обусловленныеи плохо обусловленные матрицыДля любой подчинённой матричной нормыkIk = max kIyk = max kyk = 1.kyk=1kyk=1Поэтомуcond(A) = kA−1 k kAk ≥ kA−1 Ak = kIk = 1,так что соответствующее число обусловленности матрицы всегдане меньше единицы.Хорошо обусловленныеи плохо обусловленные матрицыДля любой подчинённой матричной нормыkIk = max kIyk = max kyk = 1.kyk=1kyk=1Поэтомуcond(A) = kA−1 k kAk ≥ kA−1 Ak = kIk = 1,так что соответствующее число обусловленности матрицы всегдане меньше единицы.Достижима ли эта оценка?Примеры хорошообусловленных матрицПримером матриц с наилучшей возможной обусловленностьюотносительно спектральной нормы kAk2 = σmax (A) являютсяортогональные матрицы.Примеры хорошообусловленных матрицПримером матриц с наилучшей возможной обусловленностьюотносительно спектральной нормы kAk2 = σmax (A) являютсяортогональные матрицы.Если Q ортогональна, то kQxk2 = kxk2 для любого вектора x.Следовательно, kQk2 = maxx6=0kQxk2= 1.kxk2Примеры хорошообусловленных матрицПримером матриц с наилучшей возможной обусловленностьюотносительно спектральной нормы kAk2 = σmax (A) являютсяортогональные матрицы.Если Q ортогональна, то kQxk2 = kxk2 для любого вектора x.Следовательно, kQk2 = maxx6=0kQxk2= 1.kxk2Кроме того, Q−1 = Q⊤ и тоже ортогональна, а потому kQ−1 k2 = 1.Примеры хорошообусловленных матрицПримером матриц с наилучшей возможной обусловленностьюотносительно спектральной нормы kAk2 = σmax (A) являютсяортогональные матрицы.Если Q ортогональна, то kQxk2 = kxk2 для любого вектора x.Следовательно, kQk2 = maxx6=0kQxk2= 1.kxk2Кроме того, Q−1 = Q⊤ и тоже ортогональна, а потому kQ−1 k2 = 1.Как следствие, cond2 (Q) = kQk2 kQ−1 k2 = 1.Примеры плохообусловленных матрицСамым популярным примером плохообусловленных матрицявляются, пожалуй, матрицы Гильберта Hn = (hij ).Примеры плохообусловленных матрицСамым популярным примером плохообусловленных матрицявляются, пожалуй, матрицы Гильберта Hn = (hij ).Это симметричные матрицы, образованные элементамиhij =так что, к примеру,1,i+j−1H5 = i, j = 1, 2, .

. . , n,1121314151213141516131415161714151617181516171819.Примеры плохообусловленных матрицЧисло обусловленности матриц Гильберта растёт в зависимости отих размера n как экспонента с немалым основанием.С помощью стандартной процедуры для вычисления числаобусловленности матриц из Scilab, можно найти, чтоcond2 (H2 ) = 19.3,cond2 (H3 ) = 524,cond2 (H10 ) = 1.6 · 1013 .Примеры плохообусловленных матрицЧисло обусловленности матриц Гильберта растёт в зависимости отих размера n как экспонента с немалым основанием.С помощью стандартной процедуры для вычисления числаобусловленности матриц из Scilab, можно найти, чтоcond2 (H2 ) = 19.3,cond2 (H3 ) = 524,cond2 (H10 ) = 1.6 · 1013 .Существует общая формула:√√(1 + 2)4n√cond2 (Hn ) = O≈ O(34n / n),nгде O — «о-большое», известный символ Э.

Ландау.Примеры плохообусловленных матрицДля матрицы ВандермондаV (x0 , x1 , . . . , xn ) = 1 x0x20 . . . xn01 x1.. ... .x21 . . . xn1 .. . ... . . .1 xn x2n . . . xnnоценка снизу для числа обусловленностиcond2√ (1 +V (x0 , x1 , . . . , xn ) ≥ 2 √√2)n−1n+1также растёт экспоненциально с n. Она не зависит от вещественныхзначений x0 , x1 , . . . , xn и не очень точна.Реальные матрицы Вандермонда, как правило, обусловлены хуже.Прямые методы решения системлинейных алгебраических уравненийРешение систем линейных алгебраических уравнений видаa11 x1 + a12 x2 + . . . + a1n xn = b1 , a21 x1 + a22 x2 + .

. . + a2n xn = b2 ,...............an1 x1 + an2 x2 + . . . + amn xn = bm ,с коэффициентами aij и свободными членами bi , или, в краткойформе,Ax = bс m × n-матрицей A = ( aij ) и m-вектором правой части b = ( bi )— это важная математическая задача.Прямые методы решения системлинейных алгебраических уравненийМетоды решения уравнений и систем уравнений по характерувычислительного алгоритма традиционно разделяют напрямые,итерационные.Прямые методы решения системлинейных алгебраических уравненийМетоды решения уравнений и систем уравнений по характерувычислительного алгоритма традиционно разделяют напрямые,итерационные.В прямых методах искомое решение получается в результатевыполнения конечной последовательности действий.

Эти методыназывают также конечными или точными.Прямые методы решения системлинейных алгебраических уравненийМетоды решения уравнений и систем уравнений по характерувычислительного алгоритма традиционно разделяют напрямые,итерационные.В прямых методах искомое решение получается в результатевыполнения конечной последовательности действий. Эти методыназывают также конечными или точными.В итерационных методах решение получается как пределнекоторой последовательности приближений, которая строитсяпо решаемой системе уравнений.Прямые методы решения системлинейных алгебраических уравненийИдеяЭквивалентными преобразованиями привести решаемую системук наиболее простому виду, из которого решение находится уженепосредственно.Прямые методы решения системлинейных алгебраических уравненийИдеяЭквивалентными преобразованиями привести решаемую системук наиболее простому виду, из которого решение находится уженепосредственно.В качестве простейших могут выступать системы с диагональными,двухдиагональными, треугольными и т.

п. матрицами.Наглядные образынижней треугольной и верхней треугольной матриц00Прямые методы решения системлинейных алгебраических уравненийЧем меньше ненулевых элементов остаётся в матрицепреобразованной системы, тем проще и устойчивее её решение,но тем сложнее и неустойчивее приведение к такому виду.Прямые методы решения системлинейных алгебраических уравненийЧем меньше ненулевых элементов остаётся в матрицепреобразованной системы, тем проще и устойчивее её решение,но тем сложнее и неустойчивее приведение к такому виду.На практике обычно стремятся к компромиссу между этимипротивоположными требованиями, и в зависимости от целей,преследуемых при решении СЛАУ, приводят еёк диагональному,двухдиагональномуили треугольному виду.Прямые методы решения системлинейных алгебраических уравненийЧем меньше ненулевых элементов остаётся в матрицепреобразованной системы, тем проще и устойчивее её решение,но тем сложнее и неустойчивее приведение к такому виду.На практике обычно стремятся к компромиссу между этимипротивоположными требованиями, и в зависимости от целей,преследуемых при решении СЛАУ, приводят еёк диагональному,двухдиагональномуили треугольному виду.Мы, в основном, рассмотрим методы,основанные на приведении к треугольному виду.Решение треугольных линейных системТреугольными матрицами называют матрицы, у которых всеэлементы ниже главной диагонали либо все элементы выше главнойдиагонали нулевые:×× × ··· × ×..× ×.×××.....L = × × .

Характеристики

Список файлов лекций