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