Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 19
Текст из файла (страница 19)
Ускорить сходимость итерационных методов можно двумя способами: во-первых, за счет применения неявных итерационных методов (4), когда В+Е, н, во-вторых, оставаясь в классе явных методов, можно выбрать т=т„зависящим от номера итерации и таким, чтобы уменьшить общее число итераций. Применяется и комбинация этих двух способов, т. е.
используются неявные итерационные методы с переменными итерационными параметрами. Использование неявных итерационных методов (4) объясняется тем, что прн соответствующем выборе матрицы В отношение Л „п(В хл) 9= '" для обобщенной задачи на собственные значения Лтах (В '4) Л, (А) (1О) будет больше, чем отношение )"п|ах ('4) 3. Правила действий с матричными неравенствами. Прежде чем переходить к доказательству теоремы 1, приведем необходимые для дальнейшего сведения из линейной алгебры.
1) Если А — вещественная симметричная матрица, то существует ортогональная матрица Я (т. е. Я"=(с ') такая, что А=(;)~ЛЯ, где Л вЂ” диагональная матрица. На главной диагонали матрицье Л находятся собственные значения матрицы А. Доказательство см. в [12, с.!561. 2) Для симметричной матрицы А неравенство А)0 (А)0) эквивалентно неотрицательности (положительности) всех ее собственных значений. 98 Доказательство. Используя свойство 1), получим для любого хенН, что (Ах, х) =((~~ЛЯх, х) =(ЛЯх, Ях) ='Я Л;уо 1=1 где Л вЂ” собственные числа матрицы А н у,— 1-я компонента вектора у=Як.
Отсюда сразу следует, что если все Л,)0 (Л,)0), то (Ах, х) )О для любого хяН ((Ах, х) )О для любого хФО). Обратно, пусть Л; — любое собственное число матрицы А. Зададим вектор у, у которого все компоненты кроме )чй равны нулю, а у;= т =1. Так как матрица С/-'=Я существует, для заданного вектора у найдется вектор х~Н такой, что Ях=у.
Но тогда 0((Ах, х) = (Лу, у) =Ль т. е. Л;)О. 3) Если Ат=А)0, то существует А '. Д о к а з а т е л ь с т в о. Согласно 2) все собственные числа матрицы А положительны, следовательно, бе1А~О и существует А '. 4) Для симметричной матрицы Я и любого числа р)0 эквивалентны следующие матричные неравенства: — рЕ(3(рЕ, (15) (16) Доказательство. Согласно свойству 2) условие (15) эквивалентно неравенствам ~э„~(р, Й=1,2,..., т, где э,— собственные числа матрицы 5. Отсюда получаем э' (р', й=!, 2,..., т, что в свою очередь эквивалентно (16). 5) Если А"=А и А)0 (А)0), то существует матрица В, обладающая следующими свойствами: В'=А, В'=В, В)0 (В>0).
(17) Эта матрица называется квадратным корнем иэ матрицы А и обозначается А'". Д о к а з а т е л ь с т в о. Пусть Л~ — собственные числа матрицы А, 1=1, 2, ..., т. Согласно свойству 1) существует ортогональная матрица Я такая, что ЯАЯ'=Л=б!а~[Л„Л„..., Л ). Поскольку все Л, неотрицательны, можно определить матрицу Льн как Л н = д(ай Ц/ Л„)/ Лэ, ..., )ТЛ 1.
Тогда матрица В=Я'Л нЯ обладает свойствами (17). 6) Пусть А =А и Ь вЂ” невырожденная матрица. Тогда эквиват ленгны неравенства А)0, ЕтАЕ)0. Аналогично, эквивалентны строгие неравенства А>0, Е АЕ>0. Доказательство. Для любого ненН имеем (Е АЕх, х)= т = (АЕх, Ех).
Значит, Е АЕ)0, если А')О. Докажем обратное. Так как Е-' существует, любой хенН можно представить в виде х=Еу, где у = Е-'х. Тогда получим (Ах, х) = (ЕтАЕу, у) )О, т. е. А)0. 7) Если А и  — симметричные и Š— невырожденная матри- иы, то эквивалентны неравенства А)В, ЕтАЕ= Е ВЕ. Доказательство следует немедленно из (6). 8) Пусть Ст=С)0 и а, р — любече действительные числа. Тогда эквивалентны неравенства аС)рЕ, аЕ'= 8С-'. Д о к а з а т е л ь с т в о.
Согласно 5) существует матрица Сон= = (Со') )О. Используя свойство 7), перейдем от первого неравенства ко второму с помощью следующей цепочки эквивалентныя неравенств: а(С и) С (С ") ) р (С «) (С '*) а(С *С ')(СиС и)~)~С 1, аЕ)рС '. 9) Пусть Ат=А)0, В =В>0, а и р — любые действительньче числа. Тогда эквивалентны неравенства аА) ~В, аВ-',) ~А-'.
Д о к а з а т е л ь с т в о. Умножая первое неравенство слева и справа на В ", перейдем к эквивалентному неравенству аС)~))Е, С=В 'нАВ 'и. Согласно 8) последнее неравенство эквивалентно неравенству аЕ)рС-', т. е. аЕ)рВо'А 'В"', умножая которое слева и справа на В-"', получим аВ ')рА '. 4. Доказательство теоремы 1. Уравнение для погрешности о„= =х„— х имеет вид (18) п=0,1, о,=х,— х, откуда получим о„„= Яо., 5 = Š— сВ-'А. (19) 1ОО Лемма 1.
Пусть А и  — симметричные положительно опре- деленные матрицьг и р)0 — число. Матричные неравенства — ~В<А< ~~ В т т (20) необходимы и достаточны для того, чтобы при любых о,енН для решения задачи (18) выполнялась оценка !! ...!!.<р!! .!!..=0, 1, ...
(21) Доказательство. Оценку (21) можно записать в виде !!в.„!! <р!!шЛ, (22) где тв„=А мо„, !!ж„!!=)~(ш„, ш.). Из (19) получим, что функция ш„удовлетворяет уравнению и)~+~ Би (23) где Б=А"'БА-"=Š— тС, С=А"'В-'А"'. Для решения этого уравнения в силу симметричности матрицы Б имеем !!в„,Д'= (Бв., Бш„) = (Уя„, в.). Тем самым оценка (22) эквивалентна неравенству У <р'Е (24) и остается доказать эквивалентность неравенств (20) и (24). Согласно свойству 4) из п. 3, неравенство (24) эквивалентно двум матричным неравенствам — рЕ<Б<рЕ или :РЕ< С < РЕ. Так как С А"'В 'Асн — симметричная положительно определенная матрица, согласно свойству 8) из п.
3, в этих неравенствах можно перейти к обратным матрицам, т. е. записать, что Подставляя сюда выражение для С, получим '-РА-иВА-и.< Е. + РА-лВА- (25) юеэ Умножая последние неравенства слева и справа на А'" (см. свойство 6) из п. 3), приходим к неравенствам (20). Лемма 1 доказана. Л е м и а 2. При тех же условиях что и в лемме 1, неравенства (20) необходимы и достаточны для выполнения оценки !!о„Д,<р!!о.!!„п=0, 1, ... Доказательство проводится почти так же, как и в лемме 1, только в качестве и„ надо взять вектор В"*о„, а в качестве С— матрицу В-"АВ-"*.
Для доказательства теоремы 1 теперь достаточно заметить, что матричные неравенства (5) можно переписать в виде (20), где тт 1+ $ тв 71+ ть После этого замечания утверждение теоремы 1 следует из лемм 1 и 2. 5. Оценка погрешности в случае несимметричной матрицы В. Пусть задана любая симметричная положительно определенная матрица Р. Обозначим через 5 матрицу перехода итерационного метода (4), т. е. 5=Š— тВ 'А, и через о„— погрешность метода, о„=х„— х.
Для исследования сходимости итерационных методов в случае несимметричных матриц А и В может оказаться полезной следующая простая Л е м м а 3. Если В-' существует, то для выполнения оценок !!о»+ !!ь(р!!о !!, п=б, 1, ... (26) необходимо и достаточно выполнение матричного неравенства р 0~5"05. (27) Д о к а з а т е л ь с т в о. Учитывая уравнение для погрешности (19), перепишем (26) в виде (Р5о„, 5о„) )р'(Ро„о„) или р'(0о., о„) ) (5 05о„, о„), п=0, 1, .
Так как о, произвольно, отсюда следует (27). Обратно, если выполнено (27), то !!оьн!!Ро =(Ро„+„о„„) =(5 05о„, о„) (рь(0о„, о„) =р'!!о„!!о, т. е. приходим к (26). В следующей теореме сформулированы достаточные условия сходимости метода (4) в случае несимметричной матрицы В. Теорема 2. Пусть А — симметричная положительно определенная матрица и  — невырожденная матрица. Если выполнено матричное неравенство Вт+ и (28) с константой реп(0, !), не зависящей от и, то итерационный метод (4) сходится и для погрешности справедлива оценка !!х„— х!1„(р"!!х,— х!!„. (29) Д о к а з а т е л ь с т в о. Достаточно показать, что выполнены условия леммы 3 при О=А.
Запишем неравенство (27) для Р=А )ог в виде р'А ) (Š— тА В а) А ( Š— гВ 'А ) . Раскрывая скобки в правой части этого неравенства, получим тА(Вт-'+В-')А) (1 — р')А+т'АВг 'АВ- А (30) Согласно свойству 7) матричных неравенств можно умножить каждую часть неравенства (30) справа на матрицу А=А 'В и одновременно слева — на матрицу А~=В А '. Тогда получим эквивалентное (30) неравенство т(В+В )) (1 — р')В А 'В+т'А, которое совпадает с (28). Таким образом, из (28) следует (27) и согласно лемме 3 — оценка (29).
Поскольку р~(0, 1), из оценки (29) получаем, что ]]х„— х~~ — 0 при и — оо, т. е. метод (4) сходится. Теорема 2 доказана. 3 а меч ание. Лемма 3 и теорема 2 остаются справедливыми и в случае комплексных матриц А и В, если только заменить 5 г и В на матрицы 5' и В', комплексно сопряженные с матрицами Я и В. В частности, условие (28) принимает внд Во — О,бтА ):е В'А 'В, (31) 2т где В,=0,5(В+В'), $5. Многочлены Чебышева 1. Многочлен Чебышева на отрезке 1 — 1, 11.
В ряде вопросов численного анализа, связанных с проблемой минимизации погрешности вычислительного алгоритма, нашли применение многочлены, наименее уклоняющиеся от нуля. Рассмотрим следующую задачу: среди всех многочленов степени и со старшим коэффициентом 1 найти такой многочлен Т„(х), для которого величина шах ]Т„(х)! ко[-1л] является минимальной. Многочлен, обладающий этим свойством, называется мноеочленом, наименее уклоняющимся от нуля на отрезке ( — 1, 1) или многочленом Чебышева. В этом параграфе будет показано, что функция Т„(х) = 2'-" сов(и агссоз х) (1) является многочленом Чебышева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
