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