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