книги / Численные методы. Ч. 1

Для установления условий сходимости определим величину погрешности метода формулой z (n) = х(п) - х, тогда из формулы (2.13) для стационарного итерационного метода можно получить

Полиномы Чебышёва1

Для дальнейшего рассмотрения определим, согласно [8], норму

JfJ = max |f(x)|.

хЦа.Ь]

называемую чебышёвской.

Рассмотрим задачу: среди всех полиномов степени N со старшим коэффициентом, равным 1, найти такой многочлен TN(x), для которого величина |TN|| = njax|TN(x)| минимальна. Такой многочлен носит название полинома Чебышёва.

Расмотрим функцию

Произведем тригонометрические преобразования:

PN+,(х) = cos((N + l)arccos(x)) = cos(N • arccos(x) + arccos(x)) =

=cos(N • arccos(x))cos(arccos(x)) - sin(N arccos(x))sin(arccos(x)) =

=xPN(x) - sin(N • arccos(x))sin(arccos(x));

PN_,(x) = cos((N - l)arccos(x)) = cos(N • arccos(x) - arccos(x)) =

=cos(N • arccos(x))cos(arccos(x)) + sin(N • arccos(x))sin(arccos(x)) =

=xPK(x) + sin(N • arccos(x))sin(arccos(x)).

Складывая почленно два последних равенства,

PN*I + P\-i = - XPN*

PN.,= 2 XPN -P n1,

получаем рекуррентное соотношение для построения функции PN+1. В соответствии с формулой (2.15)

Р0(х) = cos(0- arccos(x)) = I; Р,(х) = cos(l ■arccos(x)) = x .

Чебышев Пафнутнй Львович [4.5.1821 26.11.1894]. В 1841 году закончил Московский университет и там же в 1846 году защипы магистерскую диссертацию. В 1847 году подготовил и защитил диссертацию на право чтения лекций и был утвержден в звании доцента Петербургского университета. В 1849 году защитил докторскую диссертацию; в 1850 году стал профессором Пегербургского университета. С 1856 года являлся икадемиком Петербургской академии наук.

И далее, в соответствии с полученной зависимостью Р2(х) = 2хР,(х)- Р0(х) = 2х2 -1; Р,(х) = 2xPj(x)- Р,(х) = 4х’ - Зх: Р4(х) = 2хР,(х) - Р,(х) = 8 х \-8 х 2 +1:

Р5(х) = 2хР4(х)- Р,(х) = 1бх* -20х5 +5х

На рис. 2.4 показаны некоторые полиномы построенной системы.

Рис. 2.4. Полиномы TN(X) при N= 2, 3, 4, 5, 6

Можно заметить, что в общем случае коэффициент при старшей степени

Очевидно, что TN(x) является полиномом степени N со старшим коэффициентом, равным I.

Доказательство. Пусть существует полином SN(x) степени N со старшим коэффициентом 1(рис. 2.5), причем

I|SN | | < | Q N | .

то есть |SN(x)| < ||Qn || V xe[-I,l].

Построим функцию R(X) = QN(X) -S N(X). отличную от нуля и являющуюся полиномом степени (N-1).

Рис. 2.5. Графики полиномов QsCx), Ss(x) и их разности R(x) = Q5(x)- S5(x)

В точках экстремумов хр имеем

QN(*PM -0P-|QN1- P=^N-

Тогда R(xp) = (—l)p • ||Qn || —SN(xp) . p = 0,N и в силу предположения функция R(x) на отрезке [-1, 1] меняет знак N раз, а значит имеет N корней, чего не может быть, поскольку R(x) является полиномом степени (Nrl).

Таким образом, утверждение леммы 2.2 доказано.

Поскольку построенный ранее полином Чебышёва TN(x) удовлетворяет всем требованиям леммы, он является наименее уклоняющимся от нуля на отрезке [-1, I].

В случае необходимости отыскания полинома, наименее уклоняющегося от нуля на произвольном отрезке [а, Ь], следует перейти к новой переменной

Корни этого многочлена расположены в точках

Ь’ Ро _ Г+Х~ Ь + а

Рассмотрим соотношения: у = arccos(z);

cos(y) = z - нечетная функция;

cos(2y) = 2cos2(y ) - 1 = 2z2 -1 - четная функция:

cos(3y) = cos(y) - (4cos2(y) - з) = 4z3 - 3z - нечетная функция;

cos(4y) = 2• (2cos2(y)- l)2 -1 = 2^2z2 - l)2 -1 - четная функция:

s(N • arccos(-z)) = (- l)Ncos(N • arccos(z)) = (- l)N^ ^|z + Vz: - 1J + |z -V z : - 1j

Положим z = — , тогда

виде

N J r f _

PN = ( - I) , . 2N

1+Pl

Теперь очевидно, что построенный полином принимает экстремальные значения, равные

ITNI= lejf?JTN(Х)1 = Г+Рр^