Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 94
Текст из файла (страница 94)
Процесс будет сходиться довольно медленно. однако его достоинство состоит в том, что даже при небольших и происходит ощутимое погашение компонент в широком интервале. Рис. 23. Рис. 24. Действительно, ближайший к 1 мзксимум модуля вь полинома л( ) Р гтт асимптотически равен ~совр,(=0.217, где р, есть наименьший положительный корень трансцендентного уравнения 181=1. Достигается а этот максимум в точке С, = соз — 1 †, ' ,, близкой к единице. 9 91! овщив тгвхчленныя итяглционные пгоцессы 581 На рис. 23 и 24 баны графики полиномов Ра(Е) и Ре(Е), в табл. 91.1 приведены значения внутреннего максимума модуля ел полинома Ра(Е) для й = 2, 3, ..., 6 и границы промежутка ( — та, ть), в котором )Ра(Е) ~ ( аь. Таблица 9Е.Е Описанный универсальный злгорифм цеЗначения е и й ча ~ ть лесообразно применять циклически при не очень больших й.
Применение лг циклов подавляет компоненты вектора ошибки из интеРвала ( — 7ь, 7ь) с интенсивностью а"'. Приводим результаты решения системы (9) 9 23, подготовленной при й = 2 . ((3) 9 31) по трехчленному алго- 2 2.02 рифму с постоянным а. 0.333 0,272 0.250 0.239 0.707 0.816 0.878 0,913 0.233 ~ 0.935 1 а= —, 2 1 а = —. 3 Приведем еще результаты применения к той же системе алго-' рифма с полиномамн Чебышева 2-го рода. ХО х, Х Хез Хзь Хзз Х40 Хм Хг Хе Хез х„ х, 0.22900763 — 0.4055708 — 0.5442885 — 1.2593757 — 1.2574775 — 1 2578296 — 1.2577930 — 1.2577939 0.22900763 — 0.4055708 — 0.4583667 — 1.2577739 — 1.2577920 — 1.2577939 0.38167939 0.0372933 0.1987509 0.0436874 0,0435276 6.0434832 0.0434875 0.0434874 0.38167939 0.0372939 0.2190763 0.0434788 0.0434873 0.0434873 0.53435115 0.3577880 0.7684031 1.0408131 1.0389918 1.0391862 1.0391659 1.0391664 0.53435115 0.3577880 0.7423973 1.0391330 1.0391649 1.0391662 0.68702290 0.5162869 1.0678660 1.4846543 1.4821385 1.4824220 1.4823924 1.4823932 0.68702290 0.5162869 1.0255501 1.4823466 1.4823909 1.4823929 [ГЛ.
1Х 582 УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ Циклическое проведение процесса через четыре шага укладывается в общую схему при аз=0, аз= 172, аз='/2, аз=",-,, аз=О. пз=Чз "2= 12 оз= 70 ав — — О,... Получим ХО 0 0 0 0 Применение полиномов более высоких степеней в данном случае дает худший результат. Именно, процесс через шесть шагон при аз=0, а2=.~1'з "з= ~12 "4=~1'з "0=~12 "4=~1'2, аг=-пз, ...
дает О 0 0 0 й 92, Универсальный алгорнфм Ланцонза Удобный универсальный алгорифм был предложен Ланцошем [бь Мы изложим его с некоторыми незначительными изменениями, касающимися предварительной подготовки системы. Именно, будем считать, что система подготовлена к виду Х= ВХ[ — 0 (1) ( 1 вместо Г= —, ВУ+ 2сз в обозначениях автора) и все собственные значения мазрицы В находятся в промежутке ( — 1. 1). Х4 х х,, Х1 з Х20 х. Х20 Хз Х12 Х, 'Х24 х — 1.2048821 — !.2594577 — 1.2576202 — 1.25?8018 — 1.2577945 — 1.2577936 — !.2577938 — !.5437461 — 1.1941027 — 1.2734516 1.2543485 ! 2586028 0.0715392 0.0409823 0.0437954 0.0434441 0.0434944 0.0434859 0.0434876 0.0461754 0.0504107 0.0443237 0.0436402 О.
0434955 1.0432993 1.037!510 1.0393241 1.0391507 ! .0391677 1.039!659 1.0391663 1.2796197 0.9848809 1.0509812 1.0363966 1.0397846 1.4836599 1А800347 1.4825350 !.4823855 1.4823922 1А823933 1.4823927 1.8191787 1.4059616 1.4992437 1.4784862 1.4832740 583 и 92! унизезслльный Алгоенем ллнцошл В качестве полинома г,(1) берется т„, (г) з( ) (з+ 1)т(1 т) (2) где Т... полипом Чебышева. Очевидно, что е,(1) действительно есть полипом, ибо Т„,(1)= 1, и, следовательно, 1 — Т,~,(У) делится на 1 — 1. Легко проверить. что е,(!) = 1.
Лействительно, положив 1 = — соз0, получим. что Таблица 92.7 Значения з, и т„ , з-1-1 а|из — — 0 1 — соз (з л- 1! З 2 (а+1)з(1 — соь ь! +... з 2 (3) 0.834 0.0741 ОЯ825 0.0572 0.0543 0.0525 0.54| 0.583 0.750 0.808 и, следовательно, , з+1 з|пз 3 е (!) =- !!|п 2 о.ьо ( ! !)за|аз З 2 Рнс, 25.
Рнс. 25. Последовательные максимумы полинома е,(г) убывают при движении по оси абсцисс справа налево. Наибольший внутренний максимум а, стремится. к пределу 0,0472 при з-+со. В табл. 92.! приведены значения внутреннего максимума д, Поаиномов ез(1) для а=3... 6 и граница 1, промежутка ( — 1, 7,), в котором ! е„(т) )(з,. Сравнение с табл. 91.1 показывает, что при том же номере з значения максимума модуля в алгорифме Ланцоша значительно меньше. чем в алгорифме с полиномами Чебышева 2-го рода: Числа же 7, приближаются к 1 в последнем алгорифме болйе быстро..
Из формулы (3) видно, что полинам зн(1) превращается при замене 1.=соз8 в ядро Фейсра К„(5), нормированное условием К,(0)=1. Приведем графики ез(т) и зз(Е) (рис. 25 и рнс. 26). (гл. зх 584 хнивввслльныз ллговиемы Универсальный алгорифм Ланцоша проводится по схеме, использующей рекуррентные соотношения для полинома Л,(1)=', "',".
Выведем вти соотношения. Имеем ! — т., (г) 1 — е, (Г) (э+ 1)з (1 — Г) (з+ !)з(! — Г) — 1+ Т,+, (Г) — (,+!) (1-г) ' * Поэтому (8+ 1)з(1 — 1) У 1(1) — (8+ 1)2(1 — г)+ 1 = Та+1(г). На основании соотношения Та+э Я = 21Тэ+г (1) — Т. (1) получим (з+ 2)з (1 — 1)э У, (1) — (г+ 2)э (1 — 1)+ 1 = = 21 (г+ 1)' (1 — 1)з~,, (С) — 21(з+ 1)з (1 — 1) + -+ 2г — Ф (1 — г)2 (в э (г)+ 82 (1 — г) — 1. После приведения подобных членов и сокращения на (1 — 1)э мы придем к соотношению (г+ 2)ау (1) = 2Ф (г + 1)з у„, (1) — азу, э (1) + 2 (з+ 1)з (4) 1 с начальными полиномами у,=О, дэ= —.
2' Введем далее в рассмотрение полиномы Р. (1) ='+"*У;(1). (5) Эти полнномы удовлетворяют еще более простому рекуррентному соотношению Рэ(1) = 2СРв-г(1) Ра-з(1)+ 2 (з+ 1) (6) при начальных условиях Рз(1)= —,, Р,(С)=г'+2, Последние со- 1 2' отношения позволяют провести универсальный алгорифм следующим образом. Вычислив невязку начального приближения г= ВХ+ Π— Х, образуем последовательность векторов 1 ~о = 2 Л, = 2ВЛе+ 4Ер 2; = 2ВЛг, — Л! з+ (1+ 1)з Ео (! = 2, 3....., а — 1). 686 9 92) унивегсальный алговнвм ллнцошл Тогда 1 В обозначениях Ланцоша (У= — ВУ+2с,) формулы приобретают еще более простой вид Е = —,г, г= — ВУ+2с~ — У 1 ! о 2, = ВЛо+ 4Ло Л,=ВЛ,,— 2,,+(1-+ 1) Л, рассматриваемый универсальный процесс сходится при безграничном увеличении а очень медленно, так как множители затухания е,~д(рг) на каждом фиксированном промежутке, содержащемся вну- 1 три ( — 1, +1), убывают лишь со скоростью —.
аз Однако при небольших значениях г он дает значительное подавление компонент вектора ошибки на довольно широком интервала ( — 1, т,) для собственных значений. Циклическое повторение процесса обеспечивает хорошую сходимость для систем с Р-числом обусловленности, не превосходящим 1+ тв тв Ланцош рекомендует брзть а=7. В атом случае (в применении 1 к системе г'= —, ВУ+2са) 2 Лз = — (Ва+ 4Ва+ 4Ва+ 4В'+! 6В+ 32) У'= У+ — ".2,. 16 Вычисление вектора Ла рекомендуется производить не по рекуррентным соотношениям, а по формулам схемы Хорнера (п. 86, п.
4, Ь), Ланцош советует употреблять описанный универсальный алгорифм для систем высокого порядка с целью предварительной подготовки начального приближения при применении метода минимальных итераций. так как этот последний при таком выборе начального приближения достаточно быстро становится вырожденным. Приводим в качестве примера результат циклического применения процесса Ланцоша при а= 9 для системы (9) 9 23„ подготовленной при й = = 272. 62. (гл. гх 586 УНИВЕРСАЛЬНЫЕ АЛГОРИФМЫ Первый цикл дает Х=( — 1.2574119, 0.0428473, 1.0387672, 1.4829441)', второй цикл Х= ( — 1.2577870, 0.043!7!7, 1.0391658, 1.4823988)', третий цикл: Х= ( †!.2577935, 0.0434868, 1.0391663, 1 А823931)'. В результате третьего цикла (27 итераций) мы получаем компоненты решения с точностью до 3 10 В данном примере четыре цикла при з = 7 (28 итераций) дают худший результат Х= ( †!.2577659, 0.0434909, 1.0391514, 1.4823708)'.
ф 93. Универсальные алгорифмы, наилучшие в среднем Как мы видели, при выборе полиномов, подавляющих компоненты вектора ошибки решения системы Х = ВХ.+ О, при условни,.что собственные значения матрицы В заключены в промежутке ( — 1, !), нужно руководствоваться двумя плохо совместимыми условиями, именно, малостью уклонения полинома от нуля внутри промежутка ( — 1, 1) и обращением в единицу на его правом конце. Так как буквально удовлетворить этим двум требованиям невозможно, естественно пытаться удовлетворить первому из них в смысле малости среднего квадрзтического уклонения. Именно, будем строить полипом е,(Г), минимизирующий ~ р (г) еа (г) 1й 1 в классе полиномов степени з, удовлетворяющих условию е,(1)= 1.
Весовая функция р(!) 0 может выбираться различным образом на основе информации о плотности распределения собственных значений данной матрицы В на промежутке ( — 1, !) и информации о характере распрелеления компонент начального вектора ошибок. Если такого рода информация отсутствует. естественно брать . р(т)= 1 прн — 1(г (1. 9 93) внивквслльныв алгоеиемы, нанлкчшие в сгеднам 587 Легко установить, что полиномы е,(!) образуют ортогональную систему по весу (1 — !)р(!).
Действительно. пусть е„(!)=1+а (1 — !)+а (1 !)а+ +па(! !)в ,! = ~ р (!) е„(!) еЕ!. (2) — ! Тогда очевидно, что — =2 / р(Е)(1 — !)Ее,(!)ЕЕ!. Для экстред.! да, -'! мального полинома все частные производные равны нулю, так что е, (!) будет ортогонален по весу р (!) к полиномам (1 — !)! при Е=!, .... г, а по весу (1 — !)р(Е) к полнномам (1 — !)! ' при ! = 1, ..., з и, следовательно, к любому полиному, степень которого меньше е. В частности, ! / (1 — !)р(!)е,(!)ег(!)се!=О при Е=О, 1, ..., г — 1.
(3) — ! Из теории ортогональных полнномов следует, что при любой весовой функции полиномы е;(!) связаны трехчленнымв рекуррентньши соотношениями еЕ(!) =(а!!+ р!) е! Е(!) — тгеЕ-г(!). (4) Это позволяет строить последовательные приближения к решению. системы в универсальном алгорифме, наилучшем в среднем при данном выборе весовой функции, по формулам п. 8 9 86, как только вычислены коэффициенты ин Р! и Тм Для р(Е) = 1 соотношения (4) имеют вид е (!)=1, е,(!)= — !+в !"Е (2!+1) Е 1 (2Е+ 1)(!†1)' е! ( ) = ~~(! + 1 + ( , , (! + 1 ), ~~ е! , ( ) — ( , , ) (, + , , ( ) Поэтому последовательные приближения вычисляются по формулам Л! — -(ВЛ.+О)+-Лз ! (2Е + 1) Е (2!+1) (! — 1)' (Е+!)! ' +(2! — 1)(Е+1)э ' ! '(21 — '1)(!+1)4 На рис. 27 и 28 даны графики е(!) — Еь+ Г 4з Е+ '! 77 35 35 35 35 5 32 32 32 43 96 , (!) = — ! + — ! — —,! — — Ез-(- — Еа+ — ! — —,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
