Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 39
Текст из файла (страница 39)
Это условие е предположении положительности диагональных элементов матрицы А оказывается также необходимым. ') Для доказательства положим А = Я*+ О+ )с, (5) где 0 — диагональная матрица, составленная из диагональных элементов матрицы. Й вЂ” треугольная матрица, образованная элементами матрицы А, лежащими выше главной диагоналм, )с" — ее сопряженная, т) Ме и к е и П. А. Некрасов [1].
ь) 'Рейх [1], Ш мейдаер [1[, Островский [3[. 1йь 228 итзглционныв методы гашения линейных систем [гл. ш (Р+/т') '/ЕЕ/=ЛЕ/ КЕ/= (Е/+ К") )и = ЛЕ)Е/+ ЛГЕ/. или Далее Я(/, Е/) =).(Е/К Е/) +ЛЯ'К Е/) =).(АК Е/) — Л(/ЕК Е/). Обозначим (АК Е/) =р (Е)К Е/)=д (/гК Е/)=а+Ей (/Е'К Е/) = (Е/, /с(/) = а — /б.
Тогда Л= а+/Ь откуда аз+ Ьз (р — а)з+ Ьз ' Но р = (АК Е/) = (ОК Е/) + ЯК Е/) + (/т'К Е/) = Н+ 2а, и потому (р — а)з = рз — 2 ар + аз = р (р — 2а) + аз = рг(+ аз. Таким образом, аз+ Ьз аз+ Ьз ра+ аз+ Ьз Лз Ио+ аз+ Ьа где Не есть наименьшее собственное значение матрицы О, ибо д) г/з, р)~ ), Очевидно, что г(е= пппам Далее, из+ба=~а-Г-ГЬ!а=~ДЕ/ Е/)(з~~~д(/~а(Е/~з <~~дйз= Ьз.
Как мы видели выше, необходимым и достаточным условием сходи- мости метода Некрасова является требование, чтобы все собственные числа матрицы Б= — (Е/-+/т*) '/Е были бы по модулю меньше единицы. ГГриведем оценку для модулей собственных значений этой матрицы, из которой непосредственно следует, что все они меньше единицы.
Обозначим через )м наименьшее собственное значение матрицы А. Так как матрица А положительно-определенная, Лз О. Далее. обозначим Ло= а/с'а = ~~И'(!. Пусть Е/ собственный вектор длины единица для матрицы (Е)+ /Е') '/т, принадлежаший некоторому собственному значению Л. Тогда 6 Зз) 229 метод некРАСОВА Следовательно, () ( ( Лч г "оео+до (6) Отметим, что г)е )» )ч, ибо с(о= пни оп — — т1п(Ае„е) )» ш1п (АХ, Х) =)ч. г ~х~-т Поэтому справедлива оценка ') Р~( -,",. у' )я+ д", несколько более грубая, чеи оценка (6).
Из полученных оценок следует, что все собственные значения матрицы (О+)с*) )с' по модулю меньше единицы. Тем самым схо- димость процесса Некрасова доказана. Докажем теперь необходимость высказанных условий. Пусть А симметричная или эрмитова матрица с положительными диагональными элементами, <А) <А) 1ь-Н <ь-1)1 Х =(х,, ..., х,~о х; а, ..., х„ два соседние последовзтельные приближения в )1-м цикле. Тогда Х' = Х+ енй (г". — АХ).
Пусть Л" решение системы, У = Х' — Х, У' = Л" — Х' соответствующие векторы ошибки. Тогда У =У вЂ” енО АУ=У вЂ” — г;ео -г 1 ли где г; — 1-я компонента векторз г = гч — АХ= АУ, е,— вектор, у которого 1-я компонента равна единице, а остальные кули. Вычислим значение функционала ) (Х') = (АУ', У') (совпадающего с функцией ошибки, если А положительно определена). Имеем ) (Х') =(АГ, У') =(АУ, У) — 2 — (АУ, е;)+ —,,' (Аеп е;).
аы аг1 Но (АУ, ег)=гп (Аеп еа)=ап, и потому гй У(Х") =(АУ', Г) =(АУ, У) — — ' ((АУ, 1'). аа Если матрица А не положительно определена и(А~ чь О, то можно найти начальный вектор Х1е) так, что (Ау~в), Ую)) (О. Тогда в силу (8) на протяжении всего процесса будет (АУЮ, У1Ю) ((Аг е>, Уйй) ч., О, а) Островский [8!. 230 итеРАЦ11онные методы РешениЯ линейных систем (гл. Иг Уга1 -+ О невозможно Таблица Пй 7 Решение системы по методу Некрасова Х1Ю ) О ! О ~ О ~ О 0.374 ! 0.41832 ( 0.4454096 Х('1 Хон) Хг е1 Х1е'1 О,З вЂ” 1.257?875 — 1.2577922 — 1,2577935 П0391641 1.0391657 1.0391662 1.4823879 1,4828916 1.4823927 0.0434903 0.0434881 0.0434874 й 34.
Методы полной релаксации Начиная с этого параграфа и до 9 33 включительно, мы будем рассматривать преимущественно системы с положительно-определенными матрицами, оговаривая каждый раз случаи, когда это требование не выполняется. Пусть Х" — точное решение системы АХ= г с положительно- определенной матрнцей А, Х вЂ” некоторый вектор, 7'(Х) — функция ошибки.
Ставится зздача, как изменить г-ю компоненту вектора Х, чтобы для измененного вектора Х' значение функции ошибки бьшо бы наименьшим. Пусть Х' = Х+аег. У'= У вЂ” аеь Тогда и 7 (х') = (А У', У') = (А ( У вЂ” «е;), У вЂ” аег):= =(АУ, У) — 2а(АУ, ег)+аз(Ае1, е ) =(АУ, У)+ааан — 2агг = 1 г' = 7 (Х) + — (агга — гг)з — —, (1) ак " ' аи' где г; — 1-я компонента вектора невязки для приближения Х, и, следовательно, предельное соотношение Поэтому процесс будет рзсходящимся. Установленный критерий показывает, что если матрица системы симметричная с положительными диагональными элементами, то область сходнмости метода Некрасова шире области сходимости метода простой итерации. Действительно, для сходимости метода Некрасова необходима ц достаточна, в этом случае, положительная определенность матрицы А, для сходимости же метода простой итерации необходимым и достаточным условием является положительная определенность матриц А и 20 — А.
В тзбл. П1.7 приводится решение системы (9) 9 23 по методу Некрасова. . 231 в 34! методы полной Релаксации Ясно, что 7(Х') будет иметь минимальное значение при гг а=— ан и это минимальное значение равно г4 71Х) Вычислим теперь 1-ю компоненту невязки для приближения Х'. Она равна (à — АХ', ес) =1à —.4Х вЂ” яАеь е~) = = — (à — АХ, еа) — я (Аеь е;) = г; — аап = О, т. е. приближение Л' удовлетворяет 1-му уравненшо системы АХ= Р. Лругими словами, 1-я компонента приближения Х' может быть вычислена из г-го уравнения системы АХ= гт, в которое вместо остальных неизвестных подстзвлены компоненты вектора Х.
Нменно так проходвт один пшг в каком-либо цикле процесса Некрасова. Тем самым процессу Некрасова может быть дано следующее истолкование: на каждом шагу минимизируется функция ошибки за счет изменения одной компоненты предыдущего приближения, номерз же этих компонент циклически чередуются от 1 до и. Если, используя отдельные шаги процесса Некрасова, отказаться от цикличности в выборе изменяемых неизвестных, то мы придем к более оощей группе методов, называемых методами полной релаксации. Нри такой постановке имеется широкий произвол в выборе последовательности номеров изменяемых компонент (ведущих индексов).
Так, например, решая систему десяти уравнений с десятью неизвестными, занумерованными числами от б до 9, можно в качестве „управления" процессом взять хотя бы деситичную запись числа е = 2.718 281 828459045 235 36..., т. е. менять на первом шагу вторую компоненту, на втором — седьмую.1на третьем — первую и т. д. Ясно, что для фактического проведения релаксационного процесса должен быть выбран какой-либо разумный принцип управления процессом, т. е. принцип выбора последовательности номеров изменяемых компонент. О некоторых принципах управления процессом релаксации будет сказано ниже. Конечно, не всякий процесс полной релаксации сходится к решению. Так, например, если выбранная последовательность номероь изменяемых компонент совсем не содержит хотя бы одного номера, то все поправки Х вЂ” Л" будут содержаться в (п — 1)-мерном <Вэю,ды подпространстве, и если Л вЂ” ХЙВ не содержится в этом подпространстве, процесс не может сходиться к Х'. Достаточное условие для сходимости процесса к решению будет дано в 9 37.
232 итввлцнонныв методы гашения линейных систем [гл. ш 5 35. Неполная релаксация Вместо полной минимизации функции ошибки на каждом отдельном шагу процессз можно заботиться лишь об уменьшении функции ошибки. Процессы, построенные исходя из этого принципа, называются проце.сами неполной ре л акса ци и. Выясним, как изменить одну компоненту приближения с тем, чтобы функция ошибки уменьшалась. Пусть Х'=Х+вео Тогда 1 2 У (Х') — г (Х) — — (пни — г,)з — — ' и ин Лля того, чтобы значение г'(Х') — г" (Х) было отрицательным, необходимо н достаточно, чтобы (анм — г;) ( г~, [пня — г;! ~ , 'г,[ откуда и, следовательно, а=ив Г~ ан при О ~ ~у ( 2.
Прн д = 1 будет иметь место полная минимизация функции ошибки или, как говорят, полная релаксация. Неполная релаксация называется нижне й, если О (д С 1 н верхней — если 1 С с) (2. При неполной релаксации функция ошибки изменяется по формуле У(Х') = г'(Х) — ч ~ гз. ан (2) Х=(Š— Я0 'А)Х+фЭ 'Р, где 12= [пни ..., аьз[, <~= [до ..., п„[(дн ..., и„— значения мно- жителей релаксации). На каждом отдельном шагу процесса метод полной релаксации является наивыгоднейшим, так как он обеспечивает максимальное уменьшение функции ошибкя за один шаг.
Однако при проведении большего числа шагов может оказаться, что неполная релаксация дает лучший результат. Число д при неполной релаксации может изменяться от шага к шагу. Если процесс неполной релаксации берется циклическим при постоянном или циклически меняющемся д, то процесс можно рассматривать как частный случай общего одношагового циклического процесса, примененного к системе, подготовленной к виду $35] неполная звллкслция Действительно. а-го цикла будут у; — (анх1Ю+ + д~ формулы для вычисления компонент результата +ам х(ь1, + анх(л Н+ ...
+а;„х(л г>) () Отметим, что последние формулы определяют итерационный процесс и для систем с не положительно-определенными матрицами. Однако в этом случае конечно нельзя уже говорить о релаксационных свойствах процесса. Легко найти необходимое и достаточное условие сходимости процесса, Действительно, в обозначениях 3 32 н 3 ЗЗ будем иметь М= — ЯВ 'Е, Х=Š— ()В (В+И) 5=(Š— М) '~И =(Е+ЯВ 'Е) (Š— Я вЂ” ЯВ )г) = =(В+ЯЕ) '( — ВЯ вЂ” Яй), (1 + дг 1) ан Ч1а12 гдзаа, (г+ да — ! ) азг д,агл (г+ д„— 1) а„„ (д„а„, гдча„з Быстрота же сходимости метода будет зависеть от величины наибольшего модуля корней этого уравнения. Полученный критерий сходимости процесса (3) представляет интерес главным образом в случае, если матрицы системы не положительно определены, так как в случае положительно-определенной матрицы циклический процесс неполной релаксации всегда сходится, как это будет показано в 3 37.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
