Бабенко - Основы численного анализа (947491), страница 112
Текст из файла (страница 112)
~Л„~ > О. Заметим. что из соотношений (1б) следует, что А„= Е,„',... Е,, 'АсЕо... ... Ет м где Ев = Е, Ав = А; поэтому' 10" 1т-уАт =- АОЕО . Е.о. 1 с другой стороны, Ев...Е Л ...Ло —.... Ев...Е зАтЛт у...Лв, откуда в силу предыдущего соотношения Ео" 1 Ло, Ле =АоЕо Е. — зЛ вЂ” ю Ло Следовательно, полагая 0. = Ев...
Е, Л = Л,„... Ле, получим та-~-1 = '4о (18) Преобразуем А,"". Пусть АвХЛХ з, где Л = е!!а8 (Л,) . Предположим, что матрицы Х и Х" допускают представление Х .— —. ВЯ, Х"' —.. 2зЯм где В, Вз и Я, Яз принадлежат тем же группам треугольных матриц, что и Е и Л соответственно. Заметим,что Ао =ХЛ Х ~ =ьЯЛ х',Я, =л".Я(Л"'2,Л )Л Яь ЕслиВз=(1,),",1, .=.О(1(у),1и=-1 (1.=.1,2,...,п),толегко видеть, что Л В~Л .— -- (1, (Л,/Л )™), а поскольку при 1 > з по предположению (Л,/Л )'" = 0(йт) (О ( а ( 1), то Л В,Л-"'=1+г„, где 1 единичная матрица, а матрица ет имеет элементы порядка 0(йт).
Далее, легко видеть, что Я(1, Ю„,)=(1+Л )Я=,С Я Я, где йео нижняя треугольная матрица, Яое верхняя треугольная матрица, причем хт = 1 — ' 0(вт). Поэтому Ав' = лл (Я,„ЯЛтЯе), где в скобках стоит верхняя треугольная матрица. В силу единственное~и используелаого разложения на основании (18) имеем ГчУ у .— — ВВ . Следовательно, ед .=. м' — '0(4 ы), и поэтому ~ — '0(4 +'))Аи, = А (В+0(йт 1)'л () 7. Метода реи>ения алгебраической проблема собственных оиачений 54б Отсюда сле;(уст, что А =ЯЛЯ '+О(()'"), прнчел( матрица ЯЛЯ л верхняя треугольная. Таким образом, доказана сходимость Т,й-алгоритл(а в случае собственных значений, удовлетворяюпшх неравенствам (17). Но этн неравенства заведомо не выполняются для вещественных матриц, имеющих колшлексные собственные значения.
Можно доказать, что если ~Ль, :> (Лл (, за исключением комплексно-совряженной пары Л(, Л( > (Л( > —.. Л(), и если разложение на произведение треугольных матриц не встречает препятствий в процессе итераций, зо все элементы а,, матрицы Аи, стремятся к пределу, за исключением элементов (т) Заметим, что собственные значения этой матрицы стремятся к Л(, Л(л>, а( ) — О, если ( > >', (>Л )') ф (! + 1, !); о„) — Л„если 1 ~ 1, ! + 1, и а(, ) стремятся к пределу, если л < >, (л, >) у'= (1, ! + 1).
Хотя случай комплексно-сопряженных значений включается в сферу действия ЕВ-алгоритма, тем не менее против него люжно выдвинуть много существенных возражений. Прежде всего, разложение матрицы в произведение треугольных не всегда возможно, как это мы видели при изучении алгоритма Гаусса, а требуются перестановки строк. Но даже если такое разложение возможно, оно может быть численно неустойчивым, хотя сама проблема собственных значений будет хорошо обусловлена.
Далее, ТЛ-алгоритм на каждом шаге итерационного процесса требует = 2пз,(3 умножений, нз которых половина приходится на процесс разложения матрицы в произведение треугольных, и к тому же итерации могут медленно сходиться., когда собственные значения плохо отделены друг от друга. Оказывается, что все эти недостатки ЕВ-алгоритлла можно устранить, Прежде всего покажем, как можно уменьшить число операций на шаге нтерацио>шого процесса. Для этого целее(юбразно преобразовать исходную матрицу А к такой форме, которая инвариантна относительно преобразований, используемых на итерационном п(аге ЕЛ-алгорнтл(а, и имеет максимальное число нулевых элементов.
В частности, такой формой матрицы будет обобпленная трехдиагональная форма, когда матрица А =. (а, )," имеет нулевые элементы во всех позициях (л, 1), для которых л > > + 1. В частности, ес:(н А -- еще и симметрическая матрица, то она будет трехдиагональной.
Иногда такую форму матрицы называют верхней формой Хессенберга. Выше мы установили, что произвольную симметрическую матрицу с помощью (и — 2)(п — 1))(2 элементарных преобразований подобия можно привести ь трехдиагональному виду, Но если те же выкладки применить к произвольной матрице, то с помогцью тех о(се (и — 2)(п — '!)))2 элементарных преобраеооаний подобия можно приоести матрицу к верхней форме Хессенберга. Для этого потребуется 546 Глава 8, Теория итераций и методы уешгнпл неъзтормт задом всего аа и' операций. Ниже мы покаэкем, что если исходная матрица име- 3 ет форму Хессенберга, то каждый шаг итерационного процесса потребует = пв операций.
Поэтому. целесообразно предварительно привести матрипу к форме Хессенберга, а затем уже применять алгоритм отыскания собственных значений и собственных векторов. Мы не будем продолжать дальнейшее исследование Ь1е-алгоритма, а опишом родственный ЯЛ-алгорипьм. В этом алгоритме вместо разложения в произведение треугольных матриц используется рьшложение в произведение унитарной матрицы и верхней треугольной: ~ Вд) которое гарантируется теоремой Шура.
Эту факторизацикэ мы сделаем единственной для неособенной матрицы Л, если потребуем, чтобы диагональные элементы матрицы В были вещественными и положительными. Для простоты ограничимся вещественными матрицами. Если А имеет верхнюю форму Хессенберга, то, последовательно умножая слева, эту матрицу на Ош, ..., О„', а и выбирая соответствующим образом элементы этих ортогональных матриц, получим верхнюю треугольную матрицу. В самом деле, после первого умножения получим, что элемент в позиции (2, 1) будет иметь вид ! ав, = — вэпм + сэпап и, полагая ве = азНпэ, + аяг), сэ = ееэ1(а 1 + по ), обратим его и 2 — 1/2 2 в — еуз в нуль. При умножении на О'з элементы в позициях (2, 1), (3, Ц сохраняет свое значение, равное нулю, а элелюнт в позиции (3, 2) будет иметь вид о ! ! п32 = — взазз сипая и может быть обрашен в нуль аналогичным выбором величин оя.
ся. Продолжая этот процесс., получим верхнюю треугольную матрицу, которая после умножения на подходяшую диагональную матрицу будет иметь неотрицательные диагональные элементы. Тем самым разложение (19) установлено для матриц„имеющих верхнюю форму Хессенберга. В едВ-алгоритме полагают О "1Аед = ВЯ = Лп Поскольку Ч' =-.0Я'„1 „...Щзееш, гДе ХУ = Йаи (Р )" м Р .— — т1, то матРица Л1 — "- еее,) имеет верхнюю форму Хессенберга, потому что последовательное умножение на Яш... ф, 1 „может изменить элементы только в позициях (д —, 1, д). Вычисление матрицы Л1 составляет один ~первый) шаг итеупационного процесса, и на его реализацию требуется 4и- умногкений (2п умножений необходимы для получения разложения (19)).
Далее, как и в случае ТВ-алгоритма, полагаем Лг = 01Вм О~ .4Яг = ВэОэ — .4в, и в общем случае А„,=Я Л, Я 'А ед„,=ЛтЯ =А„,.~м Таким образом получаем последовательность подобных матриц 1Л ). Поскольку на каждом шаге итерационного процосса происходит умножение на диагональную матрицу, с тем чтобы диагональные элементы матрицы Йо, бьши неотрицательны, то последовательность 1Ат) не сходится э 7. Методы решения алгебраической нроблслсы собстоеннык значений б47 в буквальном смысле, а сходится последовательность (Р 'АтР,„1, где Р, -- диагональная матрица с элементами, равными единице по модулю.
Говоря о сходимости ЯВ-алгоритма, мы будем иметь в виду сходимость последователыюсти (Р ~А Рэ 1 при соответствующих Рен 3 ад ач а 1. Пусть А =- ХЛЛ ', Л .= сйай 1Л,)'.,', и собственные значения Лз удовлетворяют неравенствам 117). Предположим, что Х" ' допускает разложение Л =. РН, гце Р - единичная внжпяя треугаэьная матрица, а ГУ -- верхняя треугольная матрипа.
Докажите сходимость А к верхней треугольной матрице. Замвчаник 1. Если вещественная матрица А имеет комплексно-сопряжепныс собственные значения, то для матрицы А имеет место та же картина, что н в случае РВ;алгоритма. Злмвчлник 2. На сходнмость ~ЗВ-алгоритма не влияет наличие кратных собственных значений, если только они пслупростые. Злмвчлииг. 3. Для убыстрения сходимости Ы1- и СдВ-алгоритмов разработана изощренная гехника сдвигов, когда очередная итерация выполняется не над матрицей А, а над матрипей А — и Д где величина р определяется с помощью четкой процедуры по результатам предшествующей итерации.
За недостатком места мы не можем остановиться на вопросах убыстрения сходи- мости более подробно. Анализ погрешностей округления на итерационном шаге ЯВ-алгоритма свидетельствуют о его надежности и определенных преимуществах перед РВ-алгоритмом, для реализации которого нужно вводить перестановки строк, что не исключает роста несциагональных элементов. В многочисленных расчетах наблюдается также быстрая сходнмость сдВ-алгоритма. Эти вопросы подробно освещены в ряде работ, в частности в )110). Когда практически ЯВ-алгоритм сошелся, вычисление собственных векторов делается элементарно„поскольку нам известна матрица перехода от А к А, а для верхней треугольной матрицы известны собственные векторы.
Гллвл 9 Численное решение краевых задач для дифференциальных уравнений и задач на собственные значения 8 1. Общие вопросы теории краевых задач — М улдтг.ьу(х)у=- ((х), х с (а, Ь(, в случае граничных условий у(а) = у(Ь) =- О (см, 3 1 гч. 1, 3 2 гл. 3). Более общие граничные условия для уравнения (1) можно записать в виде Апу(а) + Аггу (а) — Вглу(Ь) + Влгу (Ь) =. Сг, Ам у(а) -~- Ашу'(а) -~- Вш у(Ь) -Ь Вггу'(Ь) = Сг, (2) ДиффеРенциальное выРажение — л1грллл1х + д(х)У и гРаничные Условиа (2) порождакгг в В (а., Ь) некоторый опоратор. Понятно, что, для того чтобы общее дифференциальное выражение В(лу) =-- ро(х)д у~дг -~-" - р (х)у (3) определяло оператор в ьг,'а, Ь), нужно присоединить к неллу граничные усго- вия.
Предполагая граничные условия линейными, возьмем их в виде т 1г(у) = ~' (Аьгулг (а)+ Вьгу~г (Ь); = Сы Ь = 1, 2, ..., г. (4) г=л Рассмотрим, когда однородная задача Л(у) = О, 1ь(у) = О, Ь = 1, 2, ..., г, иглеет только тривиальное решение. Пусть уг(х), ..., уе,(х) линейно независимые решения дифференциального уравнения 1 (у) = О. Общее решение етого уравнения имеот вид у = сгул +, . —, с у, и, чтобы были выполнены граничные условия, необходимо выполнение равенств сг1ь(уг) = О Ь = 1, 2,..., г г=г Отслода следует, что ранг матрицы (1ь(гуг)) ',, должен быть равен т. 1.
Введение. Обыкновенное уравнение. Мы уже сталкивались с простейшей краевой задачей для уравнения второго порядка 649 81. Общие вопросы теории краевых задач б(у) = У(х), 1й(у) = Сй, Ь = 1, 2...., гп, (6) всегда имеет решение. Естественно, мы предполагали, что ро(х) ф О (х б [а, Ь[) н что коэффипиенты рз(т) (У =- О, 1, ..., ьэ) гладкие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
