Том 2 (1160084), страница 40
Текст из файла (страница 40)
В простейшем случае можно взять в качестве 7(Л) многочлен первой степени. Он должен иметь вид 7'(Л) = 1 — СЛ. (18) При этом С=д(Л) = — ' (14) 2. Метод М. К. Гавурина. Можно подойти к вопросу об ускорении сходимости и несколько иначе. Пусть итерационная формула (2) уже построена. Начиная с некоторого хв, построим по формуле (2) векторы хн хв, ..., х,, Поставим следуюшую задачу: подобрать коэффициенты а» так, чтобы линейная комбинация у=ха-~ яв(х,— хо)+ ..
+Ов(хв»» — -"в) (15) возможно лучше приближала точное решение системы (1). Будем предполагать. что матрица В имеет простую структуру и что все ее собственные значения действительны. Обозначим собственные векторы В через ВО ав, ..., Е„и запишем разложение х,— хв по векторам х! в виде х» — хв= с»х».+ саха+ ... +счх При этом А в В в , , А— х໠— ха=с»Л»х» -1-са)вз»+ ... + с ЛБА. (16) (17) Предположим теперь, что все собственные значения матрицы А действительны и расположены на отрезке 1»н, М1, где и» ) О.
Постараемся использовать эту информацию для наилучшего выбора многочлена 7"(Л). Прежде всего в силу (8) для » (Л) должно быть выполнено условие а 8[ гскогвнив сходимости итвглционных пгоцвссов 247 Гочное решение х может быть записано в виде ь- вх=хо+ 7>(хаог — хг) =хо-[- 7~(сгЛгзг+сгЛгзг+ .. +соЛоао)= о=о ,а=о о, — ог — о„ хо+ 1 Л хг +1 1 зг [ '+1 Л ~~. (18) — г п — — — ()ч)~ лн (19) где через Р()) обозначен многочлен Р(Л) =ао-1 — а,Л+ ... -[-а,Л'. (20) Очевидно, наша задача сводится к тому, чтобы сделать величины, стоящие в квадратных скобках (19), возможно меньшими. Пусть нам известна верхняя граница М ( 1 модулей собственных значений В, Тогда надо выбрать многочлен Р(Л) так, чтобы он на отрезке [ — М, М[ 1 наилучшим образом аппроксимировал функцию —.
Решение этой 1 — Л' задачи также сводится к многочленам Чебышева, наименее уклоняющимся от нуля. Можно показать (см. упражнения к главе 4), что Р(Л) =, — [Т...( — ) — 2аТ,'[ — )+агТо-г( )1+ ° (21) где Г1 а = — — 1гг —, — 1. м У м (22) Применяя этот метод, предложенный М. К, Гавуриным, мы можем производить несколько итераций по формуле (2) и затем улучшать полученные результаты, используя многочлен Р(Л). 3. Метод Л. А.
Люстерника. Пусть теперь нам известно (приближенно) наибольшее по модулю собственное значение Л, матрицы В. Будем сначала предполагать, что оно действительно, единственно и что матрица В имеет простую структуру. Разложим х, — хо по собственным векторам матрицы В: хг — хо = Ыгхг +-' гхг+ ° ° + ггохо (23) Тогда х,„+г — х,„=В (х,— х )=о(,Л,х,+дгЛ в — [-... +~1„) до (24) Таким образом, разность между точным решением (18) и приближенным (15) представится так: 248 вычисления совсгввнных значений и ввктогов млтгиц [гл.
8 х хч! ~~ (хщ ~ ь+! х!!!+ф) ЛФ3 л!и =,— лг(!х!+Г-'- М+ .. +, "л «„л„. (26) ! "з п При достаточно большом лз будем иметь приближенные равенства ! га х — х =1 ЛАх 1 (26) !л х,„,, — х,„л, с(!х!. (21) Таким образом, можно ожидать, что вектор х'=х +,(х,,— х ) 1 — Л (28) будет ближе к точному решению х, чем х,„н х,„,, Оценим порядок ошибки х — х', предполагая, что Л,=).,+е, гле в=О~~ — ! ), 1 а Лз — следующее за Л, по величине модуля собственное значение В. Если ввести матрицу В, = „[ — Л!ф ! (29) то, с одной стороны, В,(х — х )=х — х'.
а с другой стороны, используя (25), имеем: В,(х — х,„) = 1 — л Л1 — л, ' 1 — л, 1 — Л„ откуда получим: х — х' =. Г л, е л'," [лз — л,) л„ (л„ вЂ” л*,) 1 1 — л, Л 1 л, ' ' 1 л, 1 — Л„ Поэтому х — х' = О [Лз ). (31) Так как по (21) порядок х — х,„равен О(Л~!), то улучшение сходи- мости будет тем больше. чем меньше отношение ~ — ~. Если Л1 ' близко к 1, то целесообразно вместо формулы (28) использовать д 1 х'=х,„+ (х гр — х ) 1 — Л',Р (32) Вывод этой формулы аналогичен выволу формулы (28). Метод применим и в том случае, когда Л, — кратное собственное значение. Г!усть теперь Л, — комплексное число.
Если матрица В действительна. то существует и комплексно-сопряженное собственное значение Лд, Обозначим соответствующие этим собственным значениям комплексно-сопряженные собственные векторы через ад и ад. Тогда при больших значениях т будем иметь приближенное равенство дч ддд л, Лд х — хнд — д(гад+ — д(зам 1 — Л,'' 1Л, (33) )(злее, из х е, — х,„Лд Ндад+Лд ад а чдед — —,р.дд х „— х ., Лд,(,а, (34) находим: (Л + Л)(х х ) (х +3 х .
) Л ЛФ +Л Л (35) Таким образом, можно взять х' =- х„, +- . (Зб) (хдч+д хдч) (1 Лд Лд) + (хдчья хдчьд) 1 — (Лд + Лд) ~- Л,Л, Величины Л,+Л, и Л,Л, можно, например, найти как коэффициенты квадратного уравнения, о котором говорилось в предыдущем параграфе. Можно использовать и два наибольших по модулю собственных значения. При этом будет применима формула, аналогичная (Зб). Приведенный метод был предложен Л. А.
Люстерником, 4. За-процесс Эйткена. Можно использовать равенство (26) и иначе. Запишем его лля компонент х; — х( вектора ошибки х — х (дч) в виде х; — х, = а,Лд + а,Ла + ... +- а,„Л„ . (ЗУ) Опять предположим, что Л, преоблалает по молулю над остальными собственными значениями. Тогла при большом т можно приближенно считать: нч) дт х,— х, =а,',, х,— х; =а,Лд [т.)- д) нд -~- д хд — х, =аЛ, !дней дв+а (38> 4 8) рскорвнив сходимости итврлционных процвссов 24 У '250 вычислвнив совстввннык знлчвний и ввктовов млтвиц (гл.
8 Исключим из этих трех равенств величины а, и Л,. Обозначая (те() (ьн д (т) х,— х(=х, дх""+)' — дх('") = да '"" — х, = х, (39) получим: Ьх~,~) =а,Л, (1 — Л,), Дх; ) =а,Л, (1 — Л,), Дах(т) = — а,)т((1 — 2Л)+ Л,). (40) Следовательно. (д (т))В а,Л( =— д~х(т) (41) 1(д (т)) 3 (т) ~т+ 3) 1( ол + 1)) 3 двх("н х(т+а) — 2к(~+~) + х(т) Получили 3а-процесс Зйл)кена, о котором говорилось в предыдущей главе. Указанный способ можно обобщить на случай, когда преобладающими считаются два или больше собственных значения. Так.
пусть (т) 1л т х; — х( = а,Л, + ааЛа . (43) 'Тогда Дх(") = а,Лт (1 — Л1) + ааЛт (1 — Ла), Дах(» а,Лт(1 Л,)а „,Л,»(, Л,)а Ь'х( ) = а,Лт((1 — Л()'+ааЛт(1 — ).,)', Ь х(( ) = — а,Л( (1 — Л,) — ааЛа" (1 — )е)~. (44) Используя выражения (43) н (44). нетрудно показать, что ах('") д х(т) да (т) (45) Таким образом. да т(т) да (т) д,(т) да (т) ( да (т) (т) дх(т) да (т) д х)"') (46) да .Ол) д( (и) к; — х)вп дх)~) да (т) д х(-т) ) да ИВ) ( д4 .(т) а 91 погвяшность пги гвшвнии систвм линвйных гглвнвний 251 Аналогичные формулы мы получим.
если будем считать преобладающим 3, 4 и т, д, собственные значения. формулы (42) и (46) находят применение для улучшения сходи- мости самых различных процессов. б. Улучшение сходимости итерационных процессов для отыскания собственных значений матриц. Кратко коснемся вопроса об улучшении сходимости итерационных процессов для отыскания собственных значений матриц. И в этом случае мы находим некоторую последовательность чисел вида ха —— о»»Л».+азЛз+ ... +а„Л"„(й= О, 1, 2, ...). (47) Преобладающее по модулю собственное значение, определяемое с помошью этого равенства.
будет найдено тем точнее, чем меньше отношение ~ Ло!Л, (. Поэтому если нам известны приближенно Л, н Лз, то можно вместо последовательности (47) рассматривать последовательность р и а о ур — — ~а~саха = ~~я» ~саЛ; =,,"~ о»Рр()ч), а=о а-о »=» (48) где Р (Л)= (49) 9 9. Неустранимая погрешность при численном решении систем линейных алгебраических уравнений Пусть требуется решить систему линейных алгебраических уравнений Ах = Ь.
(1) На практике часто бывает так, что мы не знаем точно ни матрицы А, ни вектора Ь. Предположим, что вместо матрицы А нам дана матрица А и вместо вектора Ь дан вектор Ь". Тогда вместо вектора х мы сумеем найти только вектор х', удовлетворяюший системе уравнений А"х' = Ь'. (2) Если известно грубо положение всех собственных значений Ль Ло...,, Л„, то для уточнения собственного значения Л; можно использовать итерацию с матрицей Р,(А), где Р»(А) =(А — Л»1)(А — Ло1)... (А — Л»-»!)[А — Л1+»!) ° ° . (А — Лв1).
(50) 252 вычнслвнив совстввнных знлчвний и ввктогов млтгиц (гл. В При этом возникает задача об оценке отклонения вектора х" от вектора х, т. е. об оценке )(х — х')~, где норма понимается в том или ином смысле. Аналогичная задача может возникнуть и в том случае, когда матрица А и вектор Ь известны точно, но в процессе решения системы (1) были допущены те или иные погрешности, Тогда вместо точного вектора решения х мы получим некоторый приближенный вектор х". Вычисляя Ах', мы получим не Ь. а Ь*. Опять возникает необходимость оценить йх — х" )) по известной разности Ь вЂ” Ь*.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
