Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 59
Текст из файла (страница 59)
мальноиэ собственных значений матрицы А основывыотся па идее отыскания с:гвциопарпых точек функционала Ф(х) = (Ах, х)/(х, х). Задача 2. Пусть Л~ = 5, 1 < Л, < 3 при 1 =- 2,..., т. Построить итерационный процесс вида хаы = (А+сЕ)х" для получения Л, с наилучшей при данной инфорл~ация скоростью сладил~ости. Сделать то же самое, агли Л~ = 1. 2 < Л, < 3 при л =- 2,..., т. 2 13. Решение полной проблемы собственных значений при помощи лдпя-алгоритма Существует ряд тщательно отрабошнных алгоритмов и программ решения полной проблемы сабствевпык значений. Поэтому и шлучм, когда возникает тлкая проблема, в первую очередь рекомап,пустея использовать сгандартные программы разлепив гэких задач.
Наиболее совершенные из них основаны па различных людификвциях б)К<ьтгоритмз, общая схема которого приводите» виже. Пусть А — произвольная еещеегвеина» матрица. Согласно лемме из 3 2 ее можно представить в аиде А = ПТА л, где П- ортогональная, а А„~ --прелая треугольная матрицы. Запишем это равенство в виде А = б)~11и где С~ — ортогональная, П~ — правая треупшьная матрицы Из (1) имеем Ег = б), 'А, поэтому матрица А, = В~ Ры = Я лАЯ~ подобна матрице А.
Построим последовательность матриц А„по следующему правилу. Матрицу А„разлагаем на произведение ортогональной и правой треугольной матриц в аиде А„= С„ыл лг и полшэем А ми = Е лг(й„чл. По' скольку А л, =- эд„'~А„С„ел, то все матрицы А„подобны межпу собой и подобны исходной матрице А.
Представим исходную матрипу А в виде А = 1)Л() г, где Л вЂ” правая каноническая форма Жордвиа, т.е. Л, = 0 при 1 < л и у > л+1, Ль = ˄— собственные значения матрицы А, Ль,чл равны нулю или 1. Всегда можно подобрать матрицу б) так, чтобы диагональные элементы матрицы Л были упорядочены в порядке невозрасгания модуля (Л,(=" =(Лй(>(Лп„,~=".=~Ли(>" >(Ли глл(=-".=)Л,.). теорема (без докэлательсгва). Пусть е рпллаеюеиаи маюулщм А все дпопоиальиме мпиарм машрпцм О ие емравсдеим. Тепдо последаептельпосгпь 331 313.
Решение полной проблемы еабсгэеввых значений матрглл А ири и -+ оа сходится ио форме к клеглочномр правому треугольному сиду А. Имеется в виду, что после некоторой перестановки строк н одновретшо такой же перестановки счолбцав лгатрицы А будут выполняться .осгношения: если 1л < л ( 1глг, 1 < г или 1г м < у, й = 1,..., э, то При реализации описанного алгоритма построения матриц А па практике мы увидим, что некаюрыг алемелты матриц Аэ оказываются малыыи.
Приравняв их нулю, мы получим клетачнуго праву~о трс угольную матрицу. Характерисгический мвогочлен этой матрицы равен щюизведению характеристических многочленав ее диагональных клеток. Если требуется найти не только собственные значения матрицы А, иа и ее собственные и пригседннепиые векторы, то в процессе построения последовательности матриц А следует запоминать ортагональные матрицы Р = Ог... Ят вычисляемые по рекурренпюй формуле Р„ы —— РЯ гп Задача 1.
Доказать, что каждый шаг 1)Е-алгоритма требуат 1У 10т~/3 арифметических операцлй. На практике прибегают к различным способам ускорения шадимасти. Один нз этих способов закгпачается в слелующем. Матрица А предварительна преобразуется в эквивалентную ей правую почти треугольную матрицу. Матрица А нгжывается иугюоа почит трергольноб, мчи а, = О при у(л — 1. Алгоритм преобразования матрицы А в правую почти треугольную матрицу заключается в последовательном постраеняи матриц А~ таких, что первые 1 ст~лгбцав матрицы А~ имегсг вид первых 1 столбцов правой почти треугольной матрицы, т.е.
а; = О, если у' < л-1 и у <1. По элементам 11+1)-го столбца матрицы Аг построим лялтрицу отражения Плы 1см. 3 3) так, чтобы в матрице В =. алмА~ элементы Ь~ льг,..., 6~ ыг были те же, что у магрицы Ап а элементы Ьллздлп..., б„ьыг были нулевыми. Положим Аыг = ц+~А~ц .а умаожение тграва на матрицу Вм не меняет первых 1-1- 1 столбцов матрицы В, поэтому матрица Амг является матрицсй требуемого вида. После получения правой почти треугольной мвтйицы Агэ — ~ пРименЯют лсЕ-алгоРитм в его пеРваначальной фоРме.
задача 3. Доказать, что в этом случае клеклый шаг 11е-алгоритма требрет АГ бтт арифметических операций. Для еще большего ускорения сходнмости применяется вариант 1)Е- аптаритма со <лангом. А имевно, строится последовательнгкпь артаго- Глава 6. Числеиныс меюды алпбрм 322 нальных матриц (~~ и правых треугольных матриц Н~ по рекурреятным формулам А — п,Е = гггНп А~ = НЯ~ + МЕ, Аш, — мЕ= ЩЛь А~ =- Л~Я~+ьгН. Матрицы Аг подобны матрице А; за счет введения вгщвигов» ш удангся добитьгя ускорения сходдискзи.
Вопрос о наиболее целесообразном выборе параметров гг мы рассматривать пе будем. В атой главе было, в частности, приведено бовыпое количество мь годов решения линейных систем уравнений. Какой же из этих методов все-таки стоит выбрать, решая юдачуб Если порядок системы небольшой и по затратал1 машинного времени число арифметических операций порядка гп', где ги —.порядок системы, э являигся приемлемым, то проще всего обратиться к стапдарпгыл~ про.
граммам метала отражений (число арифметических действий )У ж 2шз/3) или мпгсда вращений (число арифметических действий Ж = 4глз!3, но меньше накопление вычислительной погрешности). Конечно, прн этом надо иметь в виду, что точные методы типа методов отражений или вращеннй для матрицы общего вида требуют одновременного хранения в памяти ЭВМ порядка т~ чисел.
Если такое количество чисел не помещается в оперативной памяти ЭВМ, а обмен информацией между оперативной и внешней памятью происходит недостаточно быстро или из-за структуры программы, или из-за возможностей ЭВМ, то применение этих программ лювгет оказаться нецелессюбрвзиым. В случае, когда применение этих методс1в нецелессобразно, имеет смысл проанализировать возможашпи применения простейших по своей гтрукгуре итерационных методов: с~рослой игерации, Зейцеля, свврхрелаксации, наискорейшего спуска.
Если решается отдельная зв,лача, то вследгшвие простоты соответствующих программ применение этих методов может быть вполне целесообразным. Если применение этих методов требует больших затрат машинного времени, то следует проанализировать возможности применения более сложных по своей структуре методов: оптимального линейного итерационного процесбл, негода с использованием корней многочлена Чебышева, метода сопрнженных градиентов, итерационных методов, использующих спектрально эквивалентные сперм торы.
Если размерность зв,лачи столь велика, что само решение валю~и, т.е. вектор Х, не помещается в оперативной памяти ЭВМ, то иногда применявптя вероятностные метода решения систем линейных уравнений которые остались вне нашего рассмотрения. 5 13. Решение полной проблемы сабственаых значений З2З Литература Абрамов А.А. О численном репюнгш некоторых алгебраических задач, воч~пгкд. ющих в теории устой.нпюсти. // ЖВМиМФ вЂ” 1984.
24, Н 3. С. 339-347. Бахвалов Н.С. Численные метолы. — М. Наука, 1975. 3 Воеводин В.В. Численные методы алгебргл. Теория и алгоритмы.— Мл Наука, 1966. Воеводин В.В. Выпит»сдельные сюновы лзшсйпай алгебры. — Мл Наука, 1977. 5 Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. — Мл Наука, 1984. 6. Годунов С.К. Решение систем линейных травлений. — Новосибирск: Наука, 1980. 7 Годунов С.К.
Совр<манные аспекты линейное алгебры. — Новосибиршс: Научная книнь 1997. 8. Джордж А., Лю Д. Численное решенно бслыних рвзрежевных снггем уравнс иий. — Мл Мир, 1984. 9. Дьяконов Е.Г. О построонии итерационных методов на основе испол~'ювания операторов, еквивзлентных но спектру // ЖВМ и МФ. - 1966. 6, Х 1.
— С. 12- 34. В. 14крамов Х.Д. Чис»егпк» рошение матричных уравнений. — Мл Наука, 1984. П. Канторович Л.В. Функдионвльный знвлнз и прикладная математика. // УМН— 1948. 3 Б 6 (28). С. 89 -185. ~2. Крылов В.И., Бобков В.В., Ыовастырный П.И. Начала теории вычислительных методов. Лияейвая алшбра н нелинейные уравнения..
Минск: Наука н техника, 1982. 3. Марчук Г.И., Лебедев В.И. Численные метолы а теории переноса пейтровов.— Мл Аюмизлат, 1981. 4. Ортеса Д. Введоние в пареллгльныг и векторные методы решения линейных спашем. - Мл Мнр, 1991. 5.
Парггеш Б. Симметричная проблема собственных значений. — Мс Мир, 1983. 6. Поспелов В.В. Метод оптимального спуска по безису для ршненнк вырождевных систем линейвых алгебраических уравнений. // ЖВМиМФ - 1991. 31, Н 7. С. 961 969. 7. Фадзаев Л.К., Фаддеева В.Н. Вычислительные методы линейной ютгебры.— М: Физматгиз, 1963. 8.
Форсайт Дж. и др. Машинные меюды математических вычислений. — Мл 5!ир, 1980. Глава 7 Решение систем нелинейных уравнений и задач оптимизации ю Решение задач оптимизации, будь то оптимизация производственных или зкономических процессов, оптимиэапня конструкций или оптимизация численных алгоритмов, сводится в математической формулировке исследуемой задачи к отысканию экстремума функционалов. В наибшие типичных случаях возникает задача минимизации функции большого числа переменных в области Й, задаваемой большим числом ограничений типа неравенств илн равенств: ищштя ш1 Ф(хи..., х ) ' н —,в эл(аз,..., в ) > О, 1 = 1,..., 1; при условиях Задача минимиаации функций большого числа переменных возникзнг также в случае применения вариационных методов к решению задач математической физики и в других разделах прикладной математики. Системы уравнений 1;(ям...,в„„)=0, я=1,...,т, которые мы будем также обозначать Е(х) = О, (рм ..., р, ) у (О,..., 0), Ф(0,..., 0) = О, го решение системы Е(х) = 0 равносильно минимизации функции Ф(у1(хг,..., я ),..., у (хм...,я,)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
