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

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

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

+ cij cjj = aij , i = j + 1, . . . , n,(4)j = 1, 2, . . . , n.где считается, что cji = 0 при j < i.Получается, что в уравнениях из (4) для j-го столбца множителяХолесского присутствуют все элементы j-го и предшествующихстолбцов.Если последовательно рассматривать группы уравнений в порядкевозрастания номера j, то реально неизвестными к моментуобработки j-го столбца (т.

е. решения j-ой группы уравнений)являются только (n − j + 1) элементов cij именно этого j-гостолбца, которые к тому же выражаются несложным образом черезизвестные элементы и друг через друга.В целом система уравнений (4) действительно имеет специальныйвид, пользуясь которым можно находить элементы cij матрицы Cпоследовательно друг за другом по столбцам:при j = 1(при j = 2(c22 =при j = 3(c33 =c11 =√a11 ,ci1 = ai1 /c11 ,i = 2, 3, .

. . , n,pa22 − c221 ,ci2 = ai2 − ci1 c21 /c22 ,pa33 − c231 − c232 ,i = 3, 4, . . . , n,ci3 = ai3 − ci1 c31 − ci2 c32 /c33 ,i = 4, 5, . . . , n,и так далее для остальных j.Алгоритм разложения ХолесскогоDO FOR j = 1 TO nvuj−1uXtc2c ← a −jjjjjkk=1DO FOR i = j + 1 TO ncij ←END DOaij −j−1Xk=1cik cjk!cjjEND DOЕсли верхний предел суммирования меньше нижнего,то сумма «пуста» и суммирование не выполняется.Алгоритм разложения ХолесскогоЕсли A — симметричная положительно определённая матрица, то всилу теоремы о разложении Холесского система (4) обязана иметьрешение.Тогда выписанный алгоритм успешно прорабатывает до конца,находя его.Алгоритм разложения ХолесскогоЕсли A — симметричная положительно определённая матрица, то всилу теоремы о разложении Холесского система (4) обязана иметьрешение.Тогда выписанный алгоритм успешно прорабатывает до конца,находя его.Если же матрица A не является положительно определённой, тоалгоритм аварийно прекращает работу при попытке извлечь кореньиз отрицательного числа либо разделить на нуль.Алгоритм разложения ХолесскогоЕсли A — симметричная положительно определённая матрица, то всилу теоремы о разложении Холесского система (4) обязана иметьрешение.Тогда выписанный алгоритм успешно прорабатывает до конца,находя его.Если же матрица A не является положительно определённой, тоалгоритм аварийно прекращает работу при попытке извлечь кореньиз отрицательного числа либо разделить на нуль.Вообще, запуск алгоритма разложения Холесского — это самыйэкономичный способ проверки положительной определённостисимметричной матрицы.Метод ХолесскогоМетод решения СЛАУ, основанный на разложении Холесского ииспользующий соотношения(C y = b,C ⊤x = y.и выписанный выше алгоритм, называют методом Холесского.Метод ХолесскогоМетод решения СЛАУ, основанный на разложении Холесского ииспользующий соотношения(C y = b,C ⊤x = y.и выписанный выше алгоритм, называют методом Холесского.Он был предложен в 1910 году французским инженером игеодезистом А.-Л.

Холесским в неопубликованной рукописи.Позднее метод неоднократно переоткрывался, и потому иногда всвязи с ним используются также термины «метод квадратногокорня», «метод квадратных корней» или даже другие имена.Метод ХолесскогоЗамечательным свойством метода Холесского является также то,что обусловленность множителей Холесского является лучшей, чему матрицы исходной СЛАУ.Обусловленность множителей равна корню квадратному изобусловленности матрицы системы (это следует из самогоразложения Холесского).То есть, в отличие от обычного метода Гаусса, треугольные системылинейных уравнений метода Холесского менее чувствительны кошибкам, чем исходная линейная система.Метод ХолесскогоЗамечательным свойством метода Холесского является также то,что обусловленность множителей Холесского является лучшей, чему матрицы исходной СЛАУ.Обусловленность множителей равна корню квадратному изобусловленности матрицы системы (это следует из самогоразложения Холесского).То есть, в отличие от обычного метода Гаусса, треугольные системылинейных уравнений метода Холесского менее чувствительны кошибкам, чем исходная линейная система.Если при реализации метода Холесского использовать комплекснуюарифметику, то извлечение квадратного корня можно выполнятьвсегда, и потому такая модификация применима к симметричнымнеособенным матрицам, которые не являются положительноопределёнными.Другой способ распространения идеи метода Холесского напроизвольные симметричные матрицы состоит в том, чтобыограничиться разложением A = LDL⊤ .Если матрица A не является положительно определённой, тодиагональные элементы в матричном множителе D могут бытьотрицательными.Но LDL⊤-разложение столь же удобно для решения системлинейных алгебраических уравнений, как и рассмотренные ранеетреугольные разложения.Другой способ распространения идеи метода Холесского напроизвольные симметричные матрицы состоит в том, чтобыограничиться разложением A = LDL⊤ .Если матрица A не является положительно определённой, тодиагональные элементы в матричном множителе D могут бытьотрицательными.Но LDL⊤-разложение столь же удобно для решения системлинейных алгебраических уравнений, как и рассмотренные ранеетреугольные разложения.Детали этих построений читатель может найти, к примеру, вкнигах1Голуб Дж., ван Лоун Ч.

Матричные вычисления. –Москва: Мир, 1999.2Уоткинс Д. Основы матричных вычислений. – Москва:«БИНОМ. Лаборатория знаний», 2009.Число обусловленности и матричные преобразованияПусть A и B — неособенные квадратные матрицы, т. е. det A 6= 0,det B 6= 0.Пусть матрица A умножается на матрицу B.Как связано число обусловленности произведения ABс числами обусловленности матриц A и B?Число обусловленности и матричные преобразованияСправедливы соотношенияkABk ≤ kAk kBk, (AB)−1 = B −1 A−1 ≤ kA−1 k kB −1 k.Число обусловленности и матричные преобразованияСправедливы соотношенияkABk ≤ kAk kBk, (AB)−1 = B −1 A−1 ≤ kA−1 k kB −1 k.Поэтомуcond(AB) = (AB)−1 · kABk≤ kAk · kBk · kA−1 k · kB −1 k = cond A · cond B.С другой стороны, если C = AB,то A = CB −1 , и в силу доказанного неравенстваcond(A) ≤ cond(C) · cond(B −1 ) = cond(AB) · cond(B),коль скоро cond(B −1 ) = cond(B).С другой стороны, если C = AB,то A = CB −1 , и в силу доказанного неравенстваcond(A) ≤ cond(C) · cond(B −1 ) = cond(AB) · cond(B),коль скоро cond(B −1 ) = cond(B).Поэтомуcond(AB) ≥cond(A).cond(B)С другой стороны, если C = AB,то A = CB −1 , и в силу доказанного неравенстваcond(A) ≤ cond(C) · cond(B −1 ) = cond(AB) · cond(B),коль скоро cond(B −1 ) = cond(B).Поэтомуcond(AB) ≥cond(A).cond(B)Аналогичным образом из B = CA−1 следуетcond(AB) ≥cond(B).cond(A)Объединяя полученные неравенства,в целом получаем оценкуmaxcond(A) cond(B),cond(B) cond(A)≤ cond(AB) ≤ cond A · cond B.Ясно, что её левая часть не меньше 1.Полученные неравенства кажутся грубыми, но они достижимы.Полученные неравенства кажутся грубыми, но они достижимы.В самом деле, пусть A — неособенная симметричная матрица ссобственнными значениями λ1 , λ2 , .

. . и спектральным числомобусловленности, равнымcond2 (A) =maxi |λi (A)|.mini |λi (A)|Полученные неравенства кажутся грубыми, но они достижимы.В самом деле, пусть A — неособенная симметричная матрица ссобственнными значениями λ1 , λ2 , . . . и спектральным числомобусловленности, равнымcond2 (A) =maxi |λi (A)|.mini |λi (A)|У матрицы A2 собственные векторы, очевидно, совпадают ссобственными векторами матрицы A, а собственные значенияравны λ21 , λ22 , . . . .Как следствие,2cond2 Amaxi |λi (A)|2maxi (λi (A))2===mini (λi (A))2mini |λi (A)|2maxi |λi (A)|mini |λi (A)|2,и в верхней оценке получаем равенство.Сходным образом можно показать, что для спектральногочисла обусловленности верхняя оценка достигается такжена произведениях вида A⊤A.Сходным образом можно показать, что для спектральногочисла обусловленности верхняя оценка достигается такжена произведениях вида A⊤A.Нижняя оценка достигается, к примеру, при B = A−1 для чиселобусловлености, порождённых подчинёнными матричныминормами.Сходным образом можно показать, что для спектральногочисла обусловленности верхняя оценка достигается такжена произведениях вида A⊤A.Нижняя оценка достигается, к примеру, при B = A−1 для чиселобусловлености, порождённых подчинёнными матричныминормами.Практически наиболее важной является верхняя оценкаcond(AB) ≤ cond A · cond B.Она показывает, что при преобразованиях и разложениях матрицчисло обусловленности может существенно расти.Число обусловленности и матричные преобразованияРассмотрим решение системы линейных алгебраических уравненийAx = b методом Гаусса в его матричной интерпретации.Обнуление поддиагональных элементов первого столбца матрицы A— это умножение исходной СЛАУ слева на специальную матрицуE1 , так что получаем систему(E1 A) x = E1 bс матрицей E1 A.Число обусловленности и матричные преобразованияРассмотрим решение системы линейных алгебраических уравненийAx = b методом Гаусса в его матричной интерпретации.Обнуление поддиагональных элементов первого столбца матрицы A— это умножение исходной СЛАУ слева на специальную матрицуE1 , так что получаем систему(E1 A) x = E1 bс матрицей E1 A.Её число обусловленности оценивается какcond(E1 A) ≤ cond(E1 ) cond(A).Перестановка строк или столбцов матрицы, выполняемая дляпоиска ведущего элемента, может незначительно изменить этуоценку в сторону увеличения, так как матрицы перестановокортогональны и имеют небольшие числа обусловленности.Далее обнуляем поддиагональные элементы второго, третьего и т.

д.столбцов матрицы системы, умножая её слева на специальныематрицы преобразований E2 , E3 , . . . , En−1 .Перестановка строк или столбцов матрицы, выполняемая дляпоиска ведущего элемента, может незначительно изменить этуоценку в сторону увеличения, так как матрицы перестановокортогональны и имеют небольшие числа обусловленности.Далее обнуляем поддиагональные элементы второго, третьего и т. д.столбцов матрицы системы, умножая её слева на специальныематрицы преобразований E2 , E3 , . . .

, En−1 .В результате получаем верхнюю треугольную систему уравненийU x = y,в которойU = En−1 . . . E2 E1 A,y = En−1 . . . E2 E1 b,и число обусловленности матрицы U оценивается сверху какcond(U ) ≤ cond(A) · cond(E1 ) · cond(E2 ) · . . . · cond(En−1 ).Число обусловленности и матричные преобразованияЕсли Ej отлична от единичной матрицы, тоcond(Ej ) > 1,причём несмотря на специальный вид матриц Ej правая и леваячасти неравенстваcond(U ) ≤ cond(A) · cond(E1 ) · cond(E2 ) · . .

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

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