|
а- \-Ь . Ь — а
( 2 £ + 1 ) я
,
п
,
Xk — ~
—
1
— — cosv
^ — ,
k —
0
,
п-
2
п
(
12
)
( 1 3 )
max |
Т„ (х)
| =
(6
— Q)_ ^
хе[а,й]
22л_1
а е г о м а к с и м а л ь н о е о т к л о н е н и е о т н у л я р а в н о
(14)
3. Другая нормировка многочленов Чебышева. В теории ите
рационных методов возникает следующая задача: найти много
член
Рп(х)
степени
п,
наименее уклоняющийся от нуля на
[а, b
],
среди всех многочленов степени
п,
принимающих при х
= 0
значе
ние 1. Ясно, что искомый многочлен отличается от многочлена
(
12
) только нормировкой, т. е.
Рл ( х ) = ^ ^ - .
(15)
Тп (
0
)
Будем считать в дальнейшем, что Гп(0)+=0.
Е с л и
Т п ( 0 ) = 0 ,
т о з а д а ч а н е и м е е т р е ш е н и я в к л а с с е м н о г о ч л е н о в з а д а н
н о й с т е п е н и л . Н а п р и м е р , д л я м н о г о ч л е н а п е р в о й с т е п е н и
Pi(x) = а х + 1
и м е е м
m a x
Ц Ру
(х) | = 1 + 1 а |
X < = [ - L , l l
и м и н и м у м д о с т и г а е т с я п р и я = 0 . Н о п р и э т о м Р > (х ) п е р е с т а е т б ы т ь м н о г о ч л е
н о м п е р в о й с т е п е н и .
Из (12), (15) получим при
Ь > а >
0, что
2х
—
(Ь
+
а)
Рп (х)
=
рп
cos
п
arccos
где
Обозначая
получим
р п
=
c o s
п
a r c c o s
b
—
а
b
+
a +
- 1
) •
(16)
s = -
Ро =
а
—
b
i - i
1 + 5
рп =
cos
In
arccos
( - г )
(17)
(18)
Для дальнейших преобразований воспользуемся тождествами
cos
(п
arccos (— г)) = (—
1
)" cos
(п
arccos
z) —
= ( - l ) n
0,5
((г
+
V * = T ) n + ( г - Y
? = ! ) " ) . (19)
При
2
= p~‘ имеем
Y z * - i = — - i / r
— -
Po
V
1 -
Y
1 - Pg2
Po
и, подставляя сюда выражение для р
0
из (17), получим
z
— У г
2
—
1
1
- У
1
■
+ / I
— ,
г + У г
2 — 1
1 +
V I
1
- У
1
106
Отсюда и из (18), (19) получаем
где Рх = (1 — /£ )/(! + VD- Таким образом, приходим к следующе
му выводу: среди всех многочленов степени я, принимающих при
х =
0
значение
1
, наименее уклоняется от нуля на отрезке [а,
Ь]
многочлен
Рп
(я) = (—
1
)"
qn
cos
( п
arccos ——
) ,
V
Ь— а
где
Qn '■
2
РГ
1
+ р“
P i ;
1
-
VI
1 + V I
6 > а > 0 .
Корни многочлена (20) расположены в точках
Х к :
я +
b . b — a
12k ■
: —
-
----------- ------------------- C O S
1
)
2
п
k =
1
,
2
, . . . . я.
(
20
)
(
21
)
(
22
)
4. Примеры применения многочленов Чебышева.
П р и м е р 1. В теории интерполирования возникает следую
щая задача. Рассмотрим многочлен
со (х) = (х—х0) (х X,) ■
■
■
(х—х„)
степени л+1. Требуется так подобрать числа
хк
(среди которых нет
совпадающих чисел), принадлежащие заданному отрезку [а,
Ь],
чтобы минимизировать величину
шах | со (х) |.
хе[а,Ь]
Поскольку старший коэффициент многочлена со(х) равен 1,
для решения данной задачи достаточно потребовать, чтобы со(х)
совпал с многочленом Чебышева
.(*) =
(Ь-а)"
22
П
+1
cos ((я +
1
) arccos
2
х — (Ь + а)
(см. (12)). Условие | со (х) | = | Т
„+1
(х) | будет выполнено тогда и
только тогда, когда совпадут все корни многочленов со(х)
и
Тп-н(х). Корнями многочлена ю(х) являются числа х0, х,, . . . ,
х„,
а корни Г„+
1
(х) определяются согласно (13) формулами
а + Ь
2
(2k + 1) я
2
(л+
1
) ’
= 0 , 1 , . . . , я.
(23)
Таким образом, если задать точки
xh
по правилу
+
6
2
.
Ь — а
-1-------- COS
(2k + 1 )я
2
( л +
1
)
’
* = 0, 1, . . . . Я,
(24)
107
то величина отклонения многочлена ш(х) от нуля окажется мини
мальной и равной
max
jce[a,b]
®
(х)
I =
(Ь — а
)'1+1
22/1
Заметим, что для минимизации отклонения многочлена а,(х)
от нуля не обязательно точки
хк, k = 0,
1
, . . . .
п,
располагать в том
порядке, который указан формулами (24). Важно лишь, чтобы
множество точек
о совпало с множеством
{xk)l=o
корней мно
гочлена Чебышева. Такое множество точек М
}*=0
естественно
назвать оптимальным. Если множество {
дга
}*=
о
оптимальное, то
любая перестановка его элементов приводит также к оптималь
ному множеству. Потребуем, например, чтобы выполнялось усло
вие
а
< x ns^.b.
Тогда для оптимальности множества
{хк}1=о
Xn—
ji, h 0, 1«. • ■
t
т. е.
xh
—
a + b
b
—
a
-COS
(2k
+
1
) я
2
(я+
1
)
достаточно положить
k = 0,
1
,
. . . , n .
П р и м е р 2. При построении оптимальных итерационных па
раметров рассматривается следующая задача. Для многочлена
М М = (1—тД,) (1—т
2
Я,) ... (1—■
тД)
(25)
подобрать параметры тЛ>
0
,
k = \ ,
2
, . . . ,
п,
так, чтобы минимизи
ровать величину
max
\fn
(Х)|.
Многочлен (25) удовлетворяет условию /п(0) = 1. Поэтому дан
ная задача решается с помощью многочлена Чебышева (20). Кор
ни многочлена (25)
М =
t k \
k
=
1
,
2
,
. . . ,п,
должны совпадать с корнями многочлена
где
Рп
(Л) = (— l)rt<
7
« cos
(п
arccos
2
р”
2
к
— (Yi + Та) '
qn-
Рх =
V
2
Vl
i - V T
ъ
1
+ У
1
’
5
Та
(26)
(27)
* +
р
Г
Согласно (22) корни многочлена (26) расположены в точках
Yi + Та- -Г- ---- — LUD ---
2п
l k
- -
.IL cos
{2k
1) я,
k = l , 2
.........
n.
(28)
2
2
Следовательно, если выбрать
Tk1
- - A + J » + .У» - J L cos(2fe ~ И Д - ,
* = ] , 2 ,
(29)
2
2
2rc
108
max
|
f n (X)
|
= qn,
XetYi.V*]
где
qn
определено согласно (27). Здесь остается в силе замечание,
сделанное в конце предыдущего примера. А именно, для оптималь
ности набора параметров {т
*.}£=1
не обязательно выбирать т„ со
гласно (29), достаточно, чтобы множество {т*1} ^ совпадало с
множеством
{^}£=1
корней многочлена Чебышева (26).
§ 6. Итерационные методы с чебышевским набором параметров
1. Явный итерационный метод.
Рассмотрим систему линейных
уравнений
A x = f
(1)
с симметричной положительно определенной матрицей
А.
Будем
решать эту систему с помощью явного нестационарного итераци
онного метода
—
+ A x k = f,
fe =
0
,
1
.........
(
2
)
xk+i
то отклонение /„(X) от нуля окажется минимальным и равным
где
ха
задан.
Поставим задачу об оптимальном выборе итерационных пара
метров, т. е. о нахождении положительных чисел ть т2, . . . , т„, для
которых норма погрешности
х
„—х на я-й итерации минимальна.
В дальнейшем в этом параграфе будем использовать среднеквад
ратичную норму
т
N 1 = 1 /(£ " * ) = 2 I
12»
/=i
где
х>
— /-я координата вектора
х.
Точная формулировка и решение задачи оптимизации итераци
онного метода (
2
) содержатся в следующей теореме.
Т е о р е м а 1.
Пусть А
—
симметричная положительно опреде
ленная матрица,
Ят щ(А
) > 0
и
Ят»х
( ^ ) > 0
—
ее наименьшее и наи
большее собственные значения. Пусть задано число итераций п.
Среди методов вида
(
2
)
наименьшую погрешность \\хп
—
х\\ имеет
метод, для которого
—
,
* = 1 , 2 ......... я,
(3)
1 + Р о +
где
Ят т
(А)
+ W
Ро:
1 - 1
g = ^min
(А)
,
(2* — 1) it
.
tk
= cos —
------- ----*
k
2
n
i + 5
=
1
,
2
,
. . . ,n .
И)
max
(4)
2
n
109
И*п—xlIsS <
7
Л*о—*11',
(5)
где
Е с л и в ы б р а т ь тк с о г л а с н о ( 3 ) , ( 4 ) , то д л я п о г р е ш н о с т и б у д е т с п р а
в е д л и в а о ц е н к а
<7я =
2РГ
1 +
р
Г
P
i
:
■
- V i
i + V i
1 =
Кы (*)
(
6
)
Д о к а з а т е л ь с т в о . Для погрешности
zk= x k—х
уравнение
9
.
_
9
.
+
Azk —
0,
k
= 0, 1
,
, п —
1,
zQ = x0
TJt+i
Из уравнения (7) получим,что
zh =
(
Е— ХнА
)
(E—Tk-iA
) ...
(Е— TtA )z0
получаем
- х .
(7)
для
k =
1
,
2
, . . . ,
п
и, в частности,
Zn
Т'п^о,
где
Тп — (Е— хпА) (Е— тп- 1А ) . . . ( Е — т1А).
(
8
)
Поскольку
Тп
— симметричная матрица, ее норма совпадает с ее
спектральным радиусом (см. §
6
гл.
1
) и выполняется оценка
llzJ^ M H zo ll,
(9)
где v — максимальное по модулю собственное значение матрицы
Тп.
Оценка (9) неулучшаема, т. е. найдется вектор
г0,
для которого
она выполняется со знаком равенства. Для доказательства теоремы
остается подобрать параметры
ти
та, .. •, т„ так, чтобы минимизи
ровать | v | .
Пусть Яь,
k = \ ,
2, . . . ,
пг
,— собственные числа матрицы
А.
Не
ограничивая общности, можно считать, что
0
< Я т
1
п(Л) =Я,5СЯ2==С ... г$Лт =Яш«04).
(
10
)
Согласно (
8
) имеем
| v | = шах |
(1
— хЛ )
(1
— т
2
?ч) . . .
(1
—
tnh)
|.
(
1 1
)
Очевидно, что
тах
1
М Щ
где
f n(K) =
(1—х,Я) (1—т
2
Я) ... (1—тД ).
Таким образом, приходим к задаче о нахождении
min
max
|
f n
(Я)
|,
tj ,Тг. - . .
Хт ;п(Л)^Х^Хтах(Л)
уже рассмотренной в примере 2 из п. 4 § 5. Полученные в этом
примере формулы (29) для параметров т* совпадают с формулами
(3), (4), а величина отклонения при данных параметрах равна
| v | —<
7
„, где
qn
определяется согласно (
6
). Теорема 1 доказана.
по
Итерационный метод (2) с параметрами т*, определенными со
гласно (3), (4), называется
явным итерационным методом с чебы-
шевским набором параметров.
Do'stlaringiz bilan baham: |
