Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 43
Текст из файла (страница 43)
254 итеглционные методы гашения линейных систем 1гл. ш Неполная релаксация в атом случае может проводиться по формулам Х' = Х+ д (г, А;) е; (О ( д ( 2), (4) причем (г', г') =(г, г) — д(2 — д)(г, А,)'. (5) Нетрудно видеть, что метод релаксации по длине вектора не- вязки равносилен релаксационному методу по функции ошибки для системы А'АХ= А'Р, полученной из данной системы АХ=В первой трансформзцией Гаусса. Действительно, (г, г) = — (АУ, Ау) = (А'А1', )г), где 1' вектор ошибки, так что квадрат длины вектора невязки для системы АХ= Р есть функция ошибки для системы А'АХ= А'В. Если последовательность номеров изменяемых компонент задана а рпог! (например, если применять циклический процесс), то проведение процесса по формулам (2) или (4) не требует фактического выполнения трзнсформации Гаусса, т.
е, вычисления матрицы А'А. Если же осуществлять управление процессом, требуя на каждом шагу максимального убывания длины вектора незязки за счет выбора номерз изменяемой компоненты, то, как справедливо отмечает Покорна [1], целесообразно предварительно вычислить матрицу А'А и вести процесс (пря (Аь А;)=1) по формулам г1Ю=г(а О+г1л-ПВ;, ~а' где- 1в номер наибольшей по модулю компоненты вектора г1ь и, В, есть 1-й столбец матрицы А'А. Это равносильно проведению релаксационного процесса с управлением для системы А'АХ= А'Е'.
5 40. Групповая релаксация Пусть АХ= Е данная система. Отдельный шаг метода групповой релаксации заключается в следующем. Выделяется группа О индексов и при переходе от предшествующего приближения к следующему изменяются только компоненты с индексами из выбранной группы О. Изменение осуществляется так, что уравнения, индексы которых входят в группу О, удовлетворяются точно. Иначе говоря, изменяемые компоненты суть решения системы уравнений чч г, лых, = ), — га а;,„хьи тРу где индекс 1 пробегает всю группу О.
Легко видеть, что если матрица А положительно-определенная, то один шаг групповой релаксации минимизирует функцию ошибок э 401 ГРУППОВАЯ РЕЛАКСАЦИЯ в подпространстве„ натянутом на единичные векторы с индексами, образующими группу О. Метод группоной релзксации допускае~ много модификаций, в зависимости от принципа выбора групп О на каждом шагу. Про.
стейшей модификацией является циклический гр>пповой процесс, в котором все индексы раз навсегда разбиваются на несколько не перекрывающихся групп и по ходу процесса эти группы циклическн чередуются. Этот процесс может рассматриваться как процесс последовательных приближений при надлежащей подготовке системы. Для того чтобы показать это, положим, для простоты, что группы состоят из последовательных индексов и чередование осуществляется в порядке их возрастания. Обозначим через О квазпдиагональную матрицу, „вырезанную" из матрицы Л в соответствии с разбиением индексов на группы, через ь матрицу, состоящую из элементов матрицы А, лежащих налево от элементов матрицы О, через Й матрицу, состоящую нз элементов А, лежащих направо от элементов матрицы О.
Тогда (2) Л = б+ О+ )с Пусть Х( ) приближение, полученное после завершения з циклов ~А П РО процесса. Тогда Х ' и Х' ~, очевкдно, связаны соотношением (.Хазен+ ОХ<Ало 4 — КХРП = Р, и потому Х"А'=((.+О)-'à — а+ О)-'КХ'"'. (3) Таким образом, изучаемый процесс равносилен процессу последовательных приближений, примененному к системе, подготовленной к виду Х= — (~.-+ О)-' КХ+ а+ О)-' Г. Отсюда вытекает необходимое и достаточное условие сходимостн процесса, которое заключается в том, чтобы собственные значения матрицы (ь+ О) 'гс были по модулю меньше единицы. Если матрица А положительно-определенная эрмитова матрица, то процесс сходится всегда. Действительно, в этом случае собственные значения матрицы (Ь+ О) "Й = (гс'+ О) ' гс по модулю не презосходят — -'- У А,Л,+Д'; Здесь через Ле обозначено йгтс((.=((й*~~, через )з — наименьшее собственное значение матрицы А, через Не — наяменьшее собственное аначение матрицы О.
Доказательство этого неравенства проводится совершенно аналогично доказательству, проведенному для процесса Некрасова. Прп этом используется то обстоятельство, что вырезанная матрица О всегда положительно определена. Справедливо неравенство г(е)~)„. При свободной групповой релаксации допускается не только' не циклическое чередование заранее выбранных групп, но и изменение 256 итаглционныв методы вешания линейных систем [гл. ш Эти формулы равносильны формулам Обозначив (ь.(1) (ь) ос) х — х.
=3г, ) в получим (в+1) (ь) (( ~ Оно) где 8, ) есть решения системы (ь) ~~о(ю При неполной релаксации вычисление проводится по формулам х, =х,. [/~б ), (б) где 0 ()ь С 2. Йля положительно-определенной матрицы имеет место следующая теорема сходимости. Если существует число (' такое, что любая последовательность групп длины ( содержит каждый индекс хотя бы рав, и если е ч. оь с,.
2 — е, то процесс групповой свободной неполной релаксации сходится к решению системы. (Островский [8[). Локазательство этой теоремы аналогично доказательству соответствующей теоремы для одношагового процесса. )(ак правило. сходимость группового процесса оказывается более быстрой по сравнению со сходимостью соответствующего одношагового процесса. Дополнительная же работа, ааключающаяся в решении вспомогательных систем, легко осуществляется при наличии подпрограммы для решения системы фиксированного порядка.
Конечно, применять метод групповой релаксации имеет смысл лишь для систем с большим числом уравнений, состава групп на каждом шагу. Как мы видели, отдельный шаг с выбранпои группой б( ) осуществляется по формулам )ео(ь) тео(м х. =х' ' при у~О ' !" ЛАВА 117 ПОЛНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ Под полной проблемой собственных значений понимается проблема нахождения всех собственных значений матрицы А, так же как н принадлежащих этим собственным значениям собственных векторов (илн векторов, образующих канонический базис). Напомним, что собственными значенияии матрицы А называются корни ее характеристического полинома, т, е, корни уравнения ПЦ вЂ” Г Л12 ... П1„ 21 п22 ~ ' ' ' '22в аа, аи,, а„„вЂ” 1~ = ( — П" ~г" — р,г" ' — ... — р„)=о.
)А — 1Е, '= Определение компонент собственного вектора требует решения системы л однородных урзвнений с л неизвестными; для вычисления всех собственных векторов матрицы, вообще говоря, требуется решить и систем вида (А — 1чЕ) Хз = О, 17 зак. 274. Д. к. Фаддеев и в. н. Фаддеева где Х;=(х„, ..., хи1) — собственный вектор матрицы А, принадлежащий собственному значению )и. Как уже отмечалось в Э 1, п. 8 коэффициенты р1 характеристического полинома являются, с точностью до знака, суммами всех миноров определителя матрицы А порядка Е опирающихся на главную дпагональ. Непосредственное вычисление коэффициентов р; является чрезвычайно громоздким и требует огромного числа операций.
Совершенно естественно, поэтому, появление специальных вычислительных приемов, упрощающих численное решение поставленных задач. Большинство методов, дающих решение полной проблемы собственных значений, включает предварительное вычисление коэффициентов характеристического полинома, которое осуществляется теми или иными средствами, минуя вычисление многочисленных миноров. Собственные значения вычисляются затем по какому-либо методу для приближенного вычисления корней полинома. Одним из лучших йбй ПОЛНАЯ ПРОВЛЕМА СОВСТВЕННЫХ ЗНАЧЕНИЙ (гл.
1ч способов приближенного вычисления корней полинома 1у(г) = а Г" + + а11" +... + а„гг+ а„является способ Ньютона. Именно, если гз есть некоторое исходное приближение к корню, то последовательные приближения (1, гг, ... вычисляются по формуле т'(гг 1) Если гз взято лостаточно близко к искомому корню Л, то последовательные приближения Гг сходятся к Л с квадратичной сходимостью, 1.
е. погрешность последующего приближения будет иметь порядок квадрата предыдущей: ) Л вЂ” гг ( .< с ( Л вЂ” 11, (г, где с некоторая константа. Вычисление значений полинома 1Й(г) и его производной в данной точке га следУет пРоводить по схеме ХОРнеРа: Ло П1 Ог ° ° Оч-1 Ль ~~ Го д1 дг ° . дн -1 дь Ое С, С, ... С„,, которая заполняется по рекуррентным формулам дг = дг 1(р+ аг (1 = 1, 2, ..., п) с =с, А+дг (1=1, 2, ..., л — 1). Тогда дь = 'т (ге) Сн-1 = 'Г (ГО).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
