Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 57
Текст из файла (страница 57)
Сначала посмотрим, что происхедит, ког,на операция симметризации применяется формально в случае снтгметричной матрицы. Тогда А = Ат н Ат А = Аз. При вознедении матрицы н квадрат собственные значения вачводятся в кнвдрат, поэтому "Р» )(А)) = ((А((з имеем ( т) пшх (Ляг) (ншх )Лл() пбп(Ллг) (глш(Лл()з Глава б. Численные методы алгебры 310 Если и(А) = 1, то гпах)Лл) = пвп)йл) и все собственные значения матрицы А равны между собой по модулю, т.е. А = сопэг Е. За исюпочеиием этол» частного случая и(А) > 1, поэтому п(Аз) > п(А). Таким образом, н случае <ммметричной матрицы применение симметризапии увеличивает число обусловленности. Число обусловленности янляется непрерывной функцией от матрицы, поэтому для матриц, близких к симметричным, применение г;имметризации также увеличивает число обусзовленншти ма.
триц. Таким образом, имеется яепусгой класс несимметричных матриц, по отношению к которым алгоритм гпмметризации увоэичивыт число обусловленности. Задача 2. Супгжтвук>т ли несимметричные матрицы, ддя которых (Л') = (г(Л)) У Рмтмотрим еще один метод решения плоха обусловленных систем линейных алгебраических уравнений.
Пусть Лх=Ь. (8) Относительно А будем <шитать, что в спектре матрицы А*А есть кэк гибственлые числа Лз порядка 1. так и собственные числа, близкие (илн даже равные) к нулю. Это как раз и означает, что матрица Л плохо обугловлена. Заметим, что в силу наших предположений относительно ссбгтвенных значений матрицы А'А, часть из них может быть равна нулю. Таким образом, уравнение (8), вообще говори, может не иметь решения в клас:- сическом смысле. Назовем решением Х уравнения (8) вектор, который минимизирует функционал невязки, а ил~евно, (0) Х = шХ пвп ()Ау — Ь((; у здесь и далее в этом параграфе под нормой мы будем понимать свклилову норму вектора.
Выписывая уравнение Эйлера для функционала Ф(у) = )~Ау — Ь()х, мы получим (10) А*Ах = Л*Ь. Уравнение (10), в отличие от (8), всегда имеет решение. Действительно, непосредственной проверкой убемшаемся, что 1гегА'А =- (югА. Необхадилгым и достаточным уиювием сущмтвования решения линейной системы уравнений (10) является ортогональносгь прыюй части ядру матрицы системы, т.е. вектор А*Ь должен быть ортогонален ядру 1гегА*А, которое, югк мы отметили выше, совпадает с ядром (шгА.
Но из вида правой части видно, что она действительно ортогональна ядру А. Таким образом, система (10) всегда имеет решение. В общем случае теких решений может быть несколько. 321 З 11. Погрешность приближенного решения системы х =О. а Если приближение х уже найдено, то следующее приблвжснис х""' буа дем искать в виде х + = х + Сан „Сл = соана, гдг лфл а уа = агйашп (ш1пФ(хаел)). Наряду с приближениями х введем нсиязки ла 1а 1, Выпишем условия минимума функционала Ф(х ы) по Са. Имеем (12) Ф(ха+'] = ))СаАчгз -~-Ах" — Ь)(з = Са~)(Алтз()~ е 2Са(Ан, б") + Ц 'а~. (13) Заметим, что прн поиске минимума Ф(хаю) достаточна рассматривать только те нар для которых (~Аж,~) Ф О, так как в противном случае значение функционала не меняетгть Функция Ф(х ~~), кзк функция переменной Са, является многочленом второй степени, причем коэффициент при Сз положителен в силу замечания выпас.
Ожтода следует, что минимум Ф(ха~ы) по Са при фиксированном у существует и единсхвен, если ~)Атт (~ т' О. Таким образом, из [13) гледует, по Са удовлетворяет Уравнению ОФ(ха+а) = 2СЦАч !)з + 2(А, (л) О дСа откуда (Аю, ба) )(АжДз ' Нри таком выборе Са Ф( а+а) ()(аел)~з ))ба)~з ( ~з ь ) ))АжДз ((Ама, ба) ~ уа = агйглах ' ' ха+а = х" -~- Саче.. )(А„,. ~( " = лмд. Описываемый ниже метод заключается в минимизации функционала Ф(у) меглодсы опшвмального поксорг1аюошного спуска; на каждом шаге выбирается коордиагатл, спуск по которой будет оптимальным в смысле ааинимизации Ф(у). В качытве координатных (базигпых) векторов можно ыабрать любую ортонормированную систему Пусть н л,..., тчт — ортонормировышал система векторов в В„, (пе обязательно базис) и Атту ф О по крайней лавре для ляного нз векторов.
Обклчначим через И' линейную оболочку векзоров ттм..., н . Будем искать вектор, минимизирующий функционал повязки Ф(у) на подпространсгвс И'. Для етого рассмотрим следующий итерационный меид. Положим Глава б. Численные ысгады алгебры 312 Суммируя вышесказанное, получаем следуюпгий алгоритм: 1) Вычисляем векторы А», 1 = 1,..., о, и их нормы )~Аюу((; в дальнейшем рассматриваем только те векторы»г, для кспорых А»1 Ю О. Не уменьшая общности, будем считать, что число таких векэоров равно д. 2) Выбираем ха на основе априорной информации; в частнскпи, можно взять х" = О. 3) Коли хь найден, то уь и Са вычисляем по формулам НА Ъ с")) 1э = шй п1лх — — — -, 1(А-,(Г' (А и бг) (14) ))А' )Р 4) Следующее приближение хьм вычисляем но формуле х + = хь + Сьшгг.
(1б) Найдем трудоемкость метода. Для этого оценим числа арифметических операций на шаге. Прежде всего заметим, что предварительные операции (этап 1) требугот в общем случае О(гпгд) операций. Этан 3 итерациовного метода требует О(гпо), а этап 4 — О(т) арифметических операций.
Таким образом, общая трудоемкость метода составляет О(пгг -1- тй1) арифметических операций, где 1 -число гнпгов итерационного пгюцессть Отметим также, чта гь из (14) нмадипя в общем случае несдпознаю на (таких индексов может быть несхолько). В этом случае в кюгестве 1ь можно брать, ггаггример, наименьший. Исследуем сходимогть итерационною метода.
Имеет мы:то Лемма. Пусть бм..., йг гйкпгзвольний кодор линейно нюаеисииых единичных еектозюе из П„, и Ь вЂ” линейнол оболочка этих еекглороа Тогда сущесгппует "г, О < у < 1, такое, чпю длл лгобого х Е б справедливо нсроеенстео )(х — (х, йь)йь)) ь 7))х(), Л = шбгнах )(х, бг)). Д~жазаглельстео. Положим гр(х) = )(х — (х, йь)бг((, й = шб гпах((х, б1)(. Покажем, что функпионал гд(х) непрерывен.
Для этого дасчаючно показать непРеРывность фУнкЦионала (х, бь), где й опРеделено выше. Расэ смотРим Разность )(х, йг)) — ((У, бг)(, где индекс й опРеделен вьппе„а г— индекс, определяемый аналогичным образом для у. Зуй 1 11. Погрешность приближенного решения системы Пусть для определенности ~(х, йл)) > )(у, йг)). Тогда справедлива цепочка неравенств ! )(х, йл)) ! — ( )(у, йг)( ) < ( )(х, йл)) ) — ( ((у, йл)( ) < < )(х — у, йл)/ < пшх)(х — у, йл)!, покуда и следует непрерывность рассматриваелюго функционала. Предположим, что утверждение пел~мы неверно.
Тогда существует посвацовательно~."гь (х;) такая, что ()х„.)( = 1 и ф(х„) > 1 — еб где с, — л О при л -+ оо. Так как в конечнол~ернолг пространстве сфера Я = (х: ((х(( = 1) компактна, то существует шщвящаяся подпогледовательноссь. Для прослоты изложения предположим. что сходится сама последовательность х* = 11лп х,. В силу непрерывности функционала ф имеем ф(х") = 1 и 1х'~~ = 1. Слеповательно, при 1 = агутах((х*, йу)) илсеем т ф(х*) = цх* — (х*, йл)йл)(з = ))х*((х — 2(х*, йл)з + (х*, йл)г))йл))т = = (/х*)( — (х*, йь) = 1. Отгюда следую, чтг (х*, йь) = О. Так как )(х*, йь)( > )(х*, уд)/ для любого у = 1,..., д, то (х*, й ) = О при всех 1 = 1,..., д.
Так как х' лгрюласу лежи г линейной оболочке векторов йп., ., йг, то последнее равенство может выполпвться лишь при х' = О, что противоречит условию ух*1 = 1. Лемма доказана. Теорема. Последовательность приближений х", получаемая е коде игаерационноео метода (14), (15), леллсгпся фуи1аягшгтаяьиой и сходится к некоторому вектору, минимизиругогааиу фща~жионая иппшки ф(х) на подпространсгпее И', со скоростью еплыстраческой проергссии.
А именно, сущестаусгп д < 1 спокое, апо ((хл — х (( < Сдь, х = 1пп хл. ьм Постоянная д при оспом еаеиств ога выбора базшп (ъьд) и апсрагпора А. Докгшательстео. Так как Аи' и' О, то существует постсжнная б > О такая, чю )(Аиг () ~ б Чй. (16) Из (14), (15) следуел; что невязки сь = Ах" — Ь удовлетворяют соотношению дл,! 4л и ) Аи,. (А, 4л1 (17) ))Аш: ()Я Глава Е.
Чвженвьге мевжы алгебры Положим й. = Аш,/))Ачг,!!. Тогда (17) примет вид бьы ьь (бь ) й Поскольку Сь выбиралось из условия минимума ))с + (!, то /ь агйглах (( 67)! и мы находимся в условиях предыдущей леммы. Тогда нз условий леммы следует оценка )К"'!! < Т!!('((, у <1. (18) Из (14] и [15) имеел~ (бь, Анй) х =х — —,чг,, !! Агч !( г л откуда, учитывал (16), получаем оценку !(хь+' — х"(! < (!8(ь)(!/(!Ачг (! < ((бь!(/Б. Применяя к полученному неравенству оценку (18), имеем !(х~+~ — хэ!! < Уь!(Ь(!/6, откуда следует цепочка соотношений (!х эт — хэ(! < ) !(хьь — х'!! < ~ ~' — < ' Чр б Р1.
6 (1 — )6 'Йгкнм образом, последовательность (х") явлэетса фундаментальной н имеет предел х '. В силу построения, х лгнпимизирует функционал Ф(у) на подпространстве Иг. Теорема доказана. Описанный выше метод решения систем уравнеанй с плохо обусловленнымн л~атрицалги особенно эффективен в глучае, когда априорнан информация представлена в виде каких-либо снедыгий о структурных особенностях искомого решения; например, когда известны базисные функции нг, н ращение представимо в виде разложения по небольшому числу этих функций. Такая ситуация часто имеет мес"го в задачах цифровой обработки сигналов. Особенно эффективен данный мнп:д в случае, когда д досчнточно мало. Другими словами, для эффективного применения данного мгпода надо иметь разумную парамегрнзвцню исхцвлой задачи.
Довольно часто зто можно сделать на основе априорной информации о решении. Например, если жчвестно, что решение представляет собой некоторый колебательный процесс с нгбольшнм числом гармоник, номера которых, вообще говоря, неизвестны. 212 З 12. Проблема собственных значений Излолпзпгый выше мппщ может быть обоснован также и в случае, когда спуск осуществляется не по одномерным подпространствам, ссютветствующим координатным осям в базисе (тг 1, а по гиперплоскостям.
При этом, естественно, скоросп, сходимосги обычно бывает вьппе, гщнако число арифметических операций на шаге процесса возритает. З 12. Проблема собственных значений В различных случаях возникают разные требовагшя к информации о собсгвенных значениях и собственных векторах матриц, и зто порсвгцаег многообразие проблем и приемов решения этой задачи.
1. Для решения ряла задач механики, физики, химии требуется получение всех собственных значений, а иногда и всех собственных векторов некоторых матриц. Эту задачу называют полней проблемой собственная эяачснмй. 2. В ряде случаев требуется найти липы максимальное или минимальное по мопулю собственное значение матрицы. Проблемы подобного сорта возникают, в частности, при решеяии некоторых задач яперной физики. Здесь приходится регпагь задачи, эквивалонтныг задачам отыскания собственных значений матриц размерности порядка 10з — 10ь илн даже существенно большей. При мшпзх размерностях матриц для решь" ния згих задач чаще примгнякгг итералионные методы, при бхшьшихвероя пюстные. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
