Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 26
Текст из файла (страница 26)
Но обратная матрица должна также удовлетворять соот-, ношению А 'А — П.=О, и если мы вычислим соответствующую матрицу невязок, то получим умноженной на !!А 11 !!А ' 11. Произведение !!А 11 11А ' 11 играет очень важную роль и называется числом обусловленности матрицы А ( о отношению к используемой норме); это число мы будем обозначать сопй(А). Матрицы, у которых значение сопй (А) велико, являются плохо обусловленными, а матрицы, у которых сопй(А) мало, хороню обусловленными (отметим, что сопд (А) > 1) .
Рассмотрим теперь случай, когда изменяются злементы матрицы А, так что возмущенное уравнение имеет вид (А + б А) (х'+ Ь х) = Ь. (35.23) Так как Ах'=Ь, то Абх=Ь вЂ” (А +ЬА)х' — ЬАбх= — ЬА(х'+бх), — Ьх=А 'ЬА(х'+бх). Следовательно, 11 ЬА11 11 бхай < 11 А ' 11 11 ЬА 11 11 х' + Ьх 11 = сопд (А ) — 11 х' + бх!1, 11А6 так что 11 бх11 11 ЬА 11 < сопд(А) 1х' + бх!! 11А 11 (3.5.24) 105 И снова главную роль в оценке играет число обусловленности.
Обратите внимание, что (3.5.24) выражает изменение х' по отношению к возмущенному решению, а не к самому х', как в (3.5.22), хотя можно получить оценку и относительно х'. Неравенства (3.5.22) и (3.5.24) нужно правильно интерпретировать. Если число обусловленности матрицы А мало, скажем близко к 1, то малые относительные изменения данных обязательно приводят лишь к малому изменению решения. С другой стороны, если число обусловленности велико, то малые изменения в данных могут привести к большому изменению решения, но это происходит не обязательно, а в зависимости от конкретного возмущения.
На практике влияние большого числа обусловленности зависит от точности данных и длины слова используемой ЭВМ. Если, например, сопд (А) = 10, то может быть потеряно б десятичных знаков, что на ЭВМ с длиной слова, эквивалентной восьми десятичным знакам, может оказаться катастрофой, в то время как на ЗВМ с длиной слова в 16 десятичных знаков это может и не вызвать никаких серьезных проблем. В общем случае очень трудно вычислить число обусловленности !! А !1 !!А ' 11, не зная матрицы А '. Однако в некоторых представляющих интерес случаях это удается сделать сравнительно просто, и мы сейчас приведем пример такого вычисления в норме 1, для трехдиагональной матрицы А из (3.2.15) .
Как указано в приложении 3, норма 1з симметричной матрицы равна ее спектральному радиусу. Следовательно, !!А!11А-' 11 = р(А), (А-'). Как мы сейчас покажем, все собственные значения матрицы (3.2.15) легко выражаются явно, что дает нам возможность найти число обусловленности.
Ключ к вычислению лежит в легко проверяемом (см. упражнение 3.5.5) тригонометрическом тождестве (у — 1) Ж ) . (у+1)Жя) ' й Р— Яй — яп = — 2 сои — яп —, (3.5.25) л+1 л+1 л+1 л+1 яя !ив и+1 уса зш л+1 2 — 1 — 1 2 2/ся ш 2яя а!ив л+1 — 2 — 2соа луги ш и+1 луга ип— л+1 Л» и соответствующие собствен- Отсюда видно, что собственные значения ные векторы т» суть ип— л+1 /ся 2»я Л» = 2 — 2 сот —, т» = яп— л+1 л+1 (3.5.2б) » =1,...,и. ляя 1п— л+1 Таким образом, максимальное собственное значение матрицы А есть Фл р(А)= Л„= 2 — 2сов —, и+1 а минимальное я Л, = 2 — 2соэ — >О. л+1 (Отсюда, между прочим, видно, что матрица А является положительно определенной.) Так как собственные значения А ' суть Л,', ..., Л„', то спектральный радиус матрицы А ' равен Л,'. Следовательно, ял 2 — 2 сочв л+ 1 ! А1т 1А ' 12 = Ля Л1 Я 2 — 2 соа— л+1 которое справедливо для у, /с = 1,...
„л. Если к обеим частям этих равенств прибавить член 2 аш [уяяу'(л+ 1) ] и затем выписать систему этих равенств при у = 1, ..., л и фиксированном Й в матричной форме, то мы получим При больших и мы можем заменить косинусы первыми членами разложе- ния в ряц Тейлора: гг С05 «+1 1— 2(гг + 1)э гг~ пгг соа— и+1 гг = -соз — ж -1 + гг + 1 2(п + 1)э так что 2(п + 1) 4(п + 1)э — яэ 11 А 11 )1А ' 11э — — — 0(ггэ), 2(п + 1)2 Отсюда видно, что матрица А является умеренно плохо обусловленной и что число обусловленности растет примерно как квадрат порядка матрицы. В заключение этой главьг вернемся к линейной двухточечной краевой задаче из раздела 3.2.
В качестве примера рассмотрим следующую задачу: !(1 + х') и'1' = 2 + бх' + 2х соах — (1 + х~ ) яп т, (3.5.27) (3.5.28) Π— 1 — п~Ь~ 2+ 2гг(гг+1)Ь~ (3.5.32) где (и + 1) Ь =! . Вектор правых частей задается в виде — Ь'!гггг — (1+Ь '), а'г,...,гń— (и'+Ь ~)(2+в!п1)1~. (3.5.33) 107 и(0) = 1, и(1) = 2+яп1. Уравнение (3.5.27) можно переписать в виде (1+х~) и" + 2хи'= 2+ бхэ + 2х соах — (1+ х2) япх, (3.5.29) т.е. в общей форме уравнения второго порядка (3.2.1). Чтобы оценить точность разностных методов раздела 3.2, мы выбрали задачу, решение которой известно: +1, +!.
(3.5.30) Зля аппроксимации уравнения (3.5.27) будем использовать три различные схемы. Первый метод определяется формулами (3.2.24) и (3.2.25) раздела 3.2 и использует для первой производной аппроксимацию первого порядка. Сравнивая форму уравнений '3.5.29) и (3.2.1), видим, что а(х) = = 1 + х', Ь(х) = 2х, с(х) = О, а гЕ(х) есть правая часть (3.5.29). Отсюда следует, чтоаг =а(хг) =а(ЕЕг) =1+ (И), Ь; =2И, с; =0 и гЕг = 2+б(И) + + 2ЕЕгсоа (И) — (1 + гэ6 ) аш (И). Таким образом, г-я строка матрицы коэффициентов в (3.2.25) принимает вид (так как Ь; > 0) ! Е э Е г э ~ + 2 г ( г + ! ) Е г г ! г ( г + (3.5.31) и вся матрица имеет форму 2 + 4Ег~ --1 — Зйэ — 1 -- 4Ь' 2+ 12йэ — 1 — 8Егэ Рис.
З.К Решение задачи (3.5.27) — (3.5.28), полученное ~о разностиой схеме (3.5.35) — (3.5.36) при шаге Ь = 1/32. Другие указанные методы дают графически неотличимые решения 0 — 1 — п (и — 1)Ь' 2 + 2пз/тз (3.5.35) и — "'(А~ — (1+и '+и '), г/з,...,аа — (п(п — 1)+Л ')(2+а)п1)) ' (3.5.36) Третья, и последняя, разностная схема определяется соотношениями (3.2.29) и (3.2.30), применимыми только к уравнениям типа (3.2.27), к которому принадлежит и уравнение (3.5.27). В этом случае /-я строка матрицы есть (/ О 5)зьз 2+ (2/з +О 5)/)з 1 (/+0 5)зйз (3 5 37 так что матрица коэффициентов и вектор правых частей принимают соответственно вид 5 2+ — й 2 9 — 1 — — /т~ 4 9 /2 4 17 2+ — й 2 25 — 1 — — Ь~ 4 -1- и — — й~ 2 2пз+- Ь' (3.5.38) — Ьз (еГ, — (1/4+й з) Из,...,Ȅ— ((и+1/2) +Ь '1(2+яп1)) (3.5.39) 1 0 1 Второй способ разностной аппроксимации определяется соотношения-.
ми (3.2.12), (3.2.13) и (3.2.14). В этом случае /-я строка матрицы коэффициентов есть -1 — ((/ — 1) й', 2+ 21'Ьз, — 1 — /(1+ 1)/)з (3.5З4) и сама матрица и вектор правых частей имеют соответственно вид 2+ 2/)з — 1 — 2йз 2 + 8йз — 1 — без 0 Отметим, что все три трехднагональные матрицы являются диагонально доминирующими, так что процесс гауссова исключения будет численно устойчив без использования какой-либо стратегии упорядочивания.
Кроме того, матрицы (3.5.35) и (3.5.38) являются симметричными. Были проведены расчеты по всем трем разностным схемам лри нескольких различных значениях шага и. Полученные решения оказались настолько близки, что на графике они неразличимы. На рис. 3.8 представлен график приближенного решения, полученного по второй разностной схеме (3.5.35) — (3.5.36) при величине шага й = 1/32.
Это приближенное решение очень хорошо согласуется с точным решением (3.5.30) . Лополнительные замечания и ссылки 3.5 В очень важной статье [83) (учебное изложение результатов этой работы можно найти, например, в книгах [52, 881) показано, что влияние ошибок округления выражается в том, что приближенное численное решение является точным решением некоторой возмущенной системы (А + ЬА) х = Ь. Детальный анализ показывает, что оценка возмущающей матрицы имеет вид !! 6А!! < р (л)ае ~!А 1 где р(л) — кубический полипом от порядка матрицы„е базовая ошибка окрутления компьютера (например, 2 ' ') и я — множитель роста, определяемый как 1 (ц) 8 = — шах ~ а" 1, а = шах ~ а;.
~, 2 гба б * 11' где а1 — элементы последовательно проеобразуемых матриц, формируемых в про(к) цессе исключения. Множитель роста очень сильно зависит от используемой стратегии перестановок. Если никаких перестановок не делается, то я может быть сколь угодно большим. При использовании стратегии частичного упорядочивания множитель е огл — 1 раничен величиной 2, которая прн больших л полностью доминирует над р(л). я — 1 Уилкинсон построил примеры матриц, на которых значение е = 2 действительно достигается, но на практике такие матрицы, по-видимому, встречаются крайне редко.
Уилкинсон и другие исследователи определяли фактическое значение я при решении большого числа практических задач, и лишь в редких случаях это значение было боль- ше, чем 8, независимо от размера матрицы. Для стратегии полного упорядочивания Уилкинсон получил весьма сложную, но гораздо лучшую оценку величины я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
