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