Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 24
Текст из файла (страница 24)
Разложение Холецкого Для /' = 1,..., и: /-! (а., ~ /~ )!/з а=! (3.4.14) Для !=/+1,...,и: / — ! /ц (аз/ — Х /и,//ь)/1//. А"=! 96 деленные симметричные матрицы (см. приложение 3). В обоих этих случаях можно спокойно использовать алгоритм гауссова исключения без каких- либо перестановок строк; мы еще обсудим этот вопрос в следующем разделе. Это обстоятельство особенно благоприятно для ленточнь!х матриц, и оказывается чрезвычайно удачным, что большинство возникающих при решении дифференциальных уравнений ленточных матриц являются либо диагонально доминирующими„либо симметричными и положительно определенными. В случае симметричной положительно определенной матрицы иногда оказывается полезным вариант гауссова исключения, известный как метод Холецкого. Этот метод основывается на разложении А =/.!.
!'3.4. 10) Здесь Š— нижняя треугольная матрица, у которой на главной диагонали не обязательно стоят единицы, как это было в случае Л!/-разложения; через т".~ обозначена матрица, транспонированная к А. При условии положительности диагональных элементов матрицы Ь разложение (3.4.10) является единственным (см.
упражнение 3.4.8) . Приравнивая соответствующие элементы в левой и правой частях (3.4.10), можно получить правило, позволяющее выразить элементы матрицы Х. через элементы А. Действительно, если обозначить элементы матрицы Л через 1; и принять во внимание, что /! = 0 при / > !', то (3.4.10) примет вид После вычисления матрицы г". решение линейной системы может быть получено точно так же, как и в случае г. У-разложения (3.3.1б): решаем Су = Ь, а затем решаем Л~х=у. Для реализации метода Холецкого необходима положительность величин ауу — Хф„из которых извлекается квадратный корень.
Если матрица коэффициентов А является положительно определенной, то все эти величины цействительно будут положительными и, более того, сам метод будет численно устойчивым. Метод Холецкого позволяет очень эффективно испольэовать машинную память. Так как матрица А симметрична, то нужно хранить только ее нижнюю треугольную часть, причем элементы ууу сразу после вычисления можно записывать на место соответствующих элементов матрицы А. Кроме того, этот метод легко адаптируется на случай ленточных матриц.
Если р— число ненулевых диагоналей ниже главной диагонали матрицы А (тогда, в силу симметрии, имеется и р ненулевых диагоналей выше главной диагонали), то алгоритм (3.4.14) принимает вид Разложение Холец кого для ленточных матриц Для у'=1,..., и: су+-шах(1, у" — р), у — г — 1,',)"' Для у=у'+ 1,...,пиЛ(у+р, л): т ~- шах(1„1 — р), у — г уб «аиду — ~ ~и ук )К в=г В этом разделе мы обсудили различные вопросы, связанные с точностью численного решения систем линейных уравнений. В следующем разделе мы рассмотрим ряд дополнительных проблем, в том числе важный вопрос о "плохой обусловленности". Дополнительные замечания и ссылки 3.4 Перестановку строк, обусловленную стратегией частичного упорядочивания, не обязателъно выполнять явно.
Вместо этого можно осуществлять неявные перестановки, используя вектор перестановок, который содержит информацию о том, какие строки поменялись местами; подробнее смотрите 1881. Вопрос об использовании явных или неявных перестановок зависит от машинного времени, необходимого для перестановки строк, времени, связанного с индексацией, требований к наглядности программы и ряда других соображений.
В тех случаях, когда стратегия частичного упорядочивания оказывается недостаточной пля гарантии точности, можно использовать другую стратегию, называемую стратегией полного упорядочивания. Эта стратегия заключается в перестановке строк и столбцов таким образом, чтобы в качестве делителя иа главной диагонали оказался наибольший по абсолютной величине элемент из ешс не обработанной подматрицы. Такая стратегия гауссова исключения приводит к значительному росту машинного времени и редко исполъзуется в стандартных программах. Далънейшую информацию по этому вопросу можно найти в работе [831. 7. Дж. Ортега 97 УПРАЖНЕНИЯ 3,4 3.4.1. Предположим, что (-й столбец матрицы А содержит толъко нулевые элементы.
Покамсите, что матрица А вырождена, используя следуюпвэе разные аргументы. а) определитель А равен нулю; б) Ае1= О, где е1 — вектор, имеющий единицу в 1-й позиции и нули в остальных; в) матрица А имеет не более л — 1 линейно независимых стол бцов. 3.4.2. Пусть А — матрица вида а„ О а„ О а( я а!+1А О ... О ал1 . апл Покажите, что если ай = а(+1 1=... = ал1= О, эе А вырождена. 3.4.3. Следующую систему размера 3 Х 3 решите методом гауссова исключения, делая при необходимости перестановки строк, чтобы избежать деления на нуль: 2х, + 2х, + Зх, = 1, х, +х +2х =2, 2х, +х, +2х, =3. 3.4,4.
Составьте программу, реапизуюшую алгоритм гауссова исключения (3.4.6) со стратегией частичного упорядочивания. Включите обратную подстановку. 3.4.5. Примените алгоритм гауссова исключения к системе (3.4.7), используя описанный в тексте четырехразрядиый десятичный компьютер, Повторите вычисле. ния после перестановки уравнений. 3.4.б. а) Покажите, что при умножении матрицы размера 4 Х 4 слева на матрицу перестановок (3.4.8) вторая н четвертая строки меняются местами, а первая и третья остаются без изменений; б) покажите, что умножение справа на эту матрицу перестановок меняет местами второй и четвертый стобцы; в) выпишите матрицу перестановок размера 4 Х 4, которая переставляет первую н третью строки, оставляя вторую и четвертую без изменений.
3.4.7. Покажите, что произведение двух матриц перестановок размера и Х л является матрицей перестановок. Покажите, что матрица, обратная к матрице перестаиово к, есть матрица перестановок. 3.4.8. Пусть А = 2,1,Т вЂ” факторизация симметричной положительно определенной матрицы А, где Š— нижняя треугольная матрица с положнтелъными элементами на главной диагонали. Покажите, что если матрица Е получается иэ 1. переменой знаков ""т всех элементов 1-й строки, то А = ЕЕ ~. (Отсюда видно, что разложение вида АЕг не является единственным, хотя сушествует только одна такая матрица Е с положительными элементами на главной диагонали.) 3.5.
Плохая обусловленность и анализ ошибок Алгоритм гауссова исключения с частичным упорядочиванием зарекомендовал себя на практике как эффективный и надежный метод. Тем не менее и этот алгоритм может не привести к точному решению, если система уравнений "плохо обусловлена'*. Говорят, что линейная система уравнений ' является плохо обусловлениой, если малые изменения элементов матрицы коэффициентов или правых частей приводят к большим изменениям в решении.
В этом случае ни от какого численного метода нельзя ожидать, что он даст точное решение, а во многих случаях даже не следует пытаться искать решение. Начнем с простого примера размера 2 Х 2. Рассмотрим систему 0 832х~ + 0 488 хг = 1,00 0,784х~ + 0,421хт =0 (3.5.1) и предположим, что выполняем алгоритм гауссова исключения на трех- разрядном десятичном компьютере. Так как ан — наибольший элемент матрицы, то никакой перестановки не требуется, и ювые элементы аЯ и Ьт(') вычисляются следующим образом:, 1„= 0,784)0,832 = 0,942 ! 308... = 0,942, и (') = 0,421 — 0,942 0,448 = 0,421 — 0,422 1016 = — 0,001, Ь (') = 0 — 1,00 0,942 = — 0,942. (3.5.2) Здесь мы отделяем вертикальной чертой те цифры, которые теряются при вычислении. Таким образом, получаем треугольную систему 0,832х, +0,448х = 1,00, — 0,001х, = — 0,942„ и обратная подставнока дает приближенное решение х, = -506, х, = 942.
(3.5.3) Но истинное решение (3,5.1), с точностью до трех знаков, есть х, = — 439, хт =817, (3.5.4) так что вычисленное решение отличается от точного примерно на 15%. Почему же это произошло? Первый и бросающийся в глаза ответ состоит в том, что мы потеряли знаки при вычислении аЯ. Действительно„вычисленное значение аЯ содержит только одну значащую цифру, так что наше окончательное решение не будет иметь более одного верного зчака. Но это только внешнее проявление существа проблемы. Здесь снова воспользуемся принципом обратного анализа ошибок.
Выполняя вычисления более деталью, можно показать, что полученное решение (3.5.3) является точным решением 1,00 Рис. З.б. Почти параллельпые прямые, определяемые системой (3.5Л). Прямые пересекмотся в точке ( — 439,817) 0,784 7» системы (3.5.5) 0,832х1 + 0,447974...хз = 1,00, 0,783744... х, + 0,420992... хз = О. Максимальное относительное изменение элементов этой системы по отношению к исходной системе (3,5.1) составляет примерно 0„03%. Однако такое изменение приводит к изменению решения на 15%, т.е. ошибки в данных увеличиваются примерно в 500 раз. Коренная причина этой плохой обусловленности заключается в том, что матрица коэффициентов (3.5.1) "почти вырождена'*.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
