А. А. Самарский, А. В. Гулин

II Vn IP 
=
2 fl W
 
С'и») +
2 i
^
( v °> 
C' vo)
 
+
II 
г . 
(37)
i,/=i 
/=1
т. е. Ц
у
„||2
является многочленом второй степени по переменным 
. . . , а р .
Приравнивая к нулю частные производные <3||ц„||г/ 
/дар, 
j=
1
, 
2
, . . . ,
п,
приходим к системе уравнений
2
а‘п)
(СЧ , СЧ ) +
(C’v0, Va)
= О, 
(38)
L
= 1
решение которой 
а{р ,
/ =
1
, 
2
, . . . ,
я,
и обращает в минимум ||цп||2.
6
. 
Выбор итерационных параметров в методе сопряженных гра­
диентов. Целью дальнейших рассуждений является нахождение па­
раметров 
ак,
т„, 
k = l, 2,
. . . ,
п,
для которых выполнены условия 
(38). Заметим прежде всего, что (38) можно записать в виде
( С Ч ,
vn)
=
0
, 
/ =
1
, 
2
, . . . ,
п.
(39)
Л е м м а 1. 
Условия
(39) 
эквивалентны условиям
(Cvjt Vn)=
0, 
/ = 0, 1, . . . , л—1. 
(40)
Д о к а з а т е л ь с т в о . Согласно (36) имеем
Си/ = Cv0
-f 2
a\nCinv0,
122

---

поэтому
(Cvh vn)
=
(Cv0, vn)
-f 2
a\n (C‘+1v0, vn) =
i=l
= (Cv0, 
V n)
-f 2
a
(c 4 .
Vn
)• (41)
1=2
Пусть выполнены условия (39). Тогда, если / + 1 ^ п (т. е.
^
п
—■
1
), то
(Cv0, vn)
 
= 0, 
(C2va, vn)
=0, . . . ,
(Ci+lv0, vn)
=
0
.
Поэтому из (41) при 
j ^ n
—1 получим
(Cv
j, 
vn)
 
=
0
.
Итак, условия (40) следуют из (39). Покажем, что верно и об­
ратное, т. е. из (40) следует (39). Доказательство проведем индук­
цией по числу /. Условие (40) при /' = 0 совпадает с условием (39) 
при /= 1 . Предположим, что условия (39) выполнены для / =
=
1
, 
2
, . . . ,
k
, и покажем, что они выполнены и для / = fe+ 
1
, где 
k ^ n
—
1
.
Из (40) при 
j = k
получим, учитывая (36),
О = (С
у
*, 
vn)
= ( 
Cv0
+ J
a V C ^ X , vn
i= l
=
{Cv
o, 
Vn)
+
(c 4> 
Vn)-
(42)
1=2
По предположению индукции условия (39) выполнены при / =
= 1, 2, . . . . А. Поэтому из (42) получим
(с*+х, vn)
=
о.
Поскольку 
ар ф
0 (так как 
Рк(С)
— многочлен степени 
k )
, отсюда 
получаем 
(Ch+lv
„, 
у
„)= 0 , 
т
. 
е. условия (39) выполнены и при /' =
= А +
1
.
Лемма 1 доказана. Она потребуется для построения оптималь­
ных итерационных параметров в методе (26).
Заметим, что число 
п
в лемме 1 предполагалось фиксирован­
ным, в то время как при постановке задачи оптимизации мы тре­
бовали, чтобы ||ип|| была минимальной при любом 
п=
1, 
2, ...
По­
этому оптимальные параметры надо отыскивать не из условий (40) 
при фиксированном 
п,
а из условий
(Cvu vn)=
0, 
п=
1 , 2 , . . . , / = 0, 1, . . . ,
п
—1. 
(43)
Если такие параметры будут найдены, то это будет означать, что 
построена ортогональная (в смысле скалярного произведения 
{и, v )c=(Cti
, 
v )
) система векторов 
v0, vu
. . . .
vh, . . .
Поскольку 
пространство решений системы (
1
) имеет размерность 
т,
постро­
123

---

енная ортогональная система будет содержать не более 
т
векто­
ров. Это означает, что начиная с некоторого 
п (п ^ .т )
погрешности 
vn
обратятся в нуль, т. е. метод сойдется за конечное число ите­
раций.
Перейдем к построению итерационных параметров, для которых 
выполнены условия (43). Параметры а, и т, найдены согласно (34):
Ctj — 
1
, Tj —
(С
у
о
, tip)
II Ci>„||2
(44)
Пусть параметры щ, т2, ■
• •, т*, а,, 
а2, ■
 ■
 
■, 
ак
уже выбраны опти­
мальным образом. Тогда согласно (43) выполняются условия
(Cvj,Vi)=
0
, 
i=
1
,
2
, . . . , А, / =
0
, 
1
, . . . ,
i
—
1
.
(45)
Построим оптимальные параметры т*+1, а Л+). Согласно лемме 1 
при 
n = k +
1
должны выполняться условия
{Cvh
t'fi+
1
) =0 ,
j =
0, 1, . . . ,
k.
(46)
Часть из этих условий, а именно условия (46) при / = О, I , . . . ,
k
—2, 
следует из (45) . Действительно, согласно (29) имеем
(vk+1, Cvj)
= а
*+1
(vk, Cv,) —
сснЛп (
Cv
k, 
Cv,)
-f (1 — ct*+1) 
{vk-u Cv,).
Из (45) при 
i = k
и 
i = k
—1 получим, соответственно,
(Cv;, vk) = Q,
/ = 0, 1, . . . .
k —
1,
(Cv,,vk_l) =
0, 
/ = 0, 1, . . ., 
k
— 2.
Поэтому
(v/l+l, CVj)=—al!+iTl4-1(Cvk, Cv,)
(47)
при / =
0
, 
1
, .. ., 
k
—
2
.
Покажем, что для этих же значений / выполняются равенства 
(
Cv
h, 
Cv
j)= 0 . Запишем уравнение (29) при 
k = j:
i>i
+1
= «и
-1
{Е—
т,+, С) иj + (
1
—ocj+,) Uj.,
и найдем отсюда
CVj = — — V j
--------- --------
[Vjrl —
(1 — К/+1)
т/+i 
ai+iTi+i
Умножая предыдущее соотношение скалярно па 
Cvh
и учитывая 
симметричность матрицы С, получим
(Cvh Cvk) =
—- 
—— (vit Cvk)
--------!----- [(иу-+
1
, 
Cvk)
— (1 — ot/+i) (f/-i, 
Cvk)\
=
T/+i 
a/+iT/+i
= — — (Си/, yA) -----------!------[ (C u /n , 
Vk)
(1 
a,
rl) (Cw/.J, Уд.)].
T/+1
K/
t
1T/+1
Из (45) при 
i = k
имеем
(Сиу, uft) =
0
, 
/ =
0
, 
1
, . . ., 
k
— 
1
,
{Cvj+1, vk) = 0, 
j =
0
, 
1
, . . ., 
k
— 
2
,
{Cvh u vk)
=
0
, 
/ =
1
,
2
, . . ., 
k.
124

---

Следовательно (Сщ, 
Cvh)
= 0 при / = 0, 1, . . . ,
k—
2, и согласно (47) 
имеем (
v
h+i, 
Cvj
) =
0
, / —
0
, 
1
, . . . ,
k— 2.
Итак, из всех условий (46) остаются лишь два:
(Со*-,, 
t’kki)
= 0, 
(48)
(Си*, и*+1) = 0. 
(49)
Подставляя в (48) значение 
vh+l
из (29), получим
0 = а
*+1
(v
k, 
Cvk-x)
— 
rJ-k
цТ*н (Со*, Си*-,) + (1 — a*+1) (о*_ь Co*-,).
Согласно (45) при 
i = k, j = k
—1 имеем (Сщ_ь 
vh)= 0 ,
так что пре­
дыдущее уравнение принимает вид
1 
Tfe-f.i (Со*, Cyfi- i ) - r ( l a*+1) (Сщ_ь I'^-j) =0. 
(50)
Далее, подставляя в (49) значение щ
+1
из (29), получим 
0 = a
*+1
(vk, Cvk)
— а*+
1
т*+, (Со*, Со*) -f- (1 —■
а*+1) (о*-,, Со*).
Последнее слагаемое в этом тождестве равно нулю, так как соглас­
но (45) при 
i = k, j = k
—1 имеем
{vh- u Cvk)
= (Сщ_,, 
vk)
=0.
Таким образом, приходим к тождеству
aA+ i[(Cu/,, 
vk)
Tft+i (Co*, Co*) 
]
=0,
из которого находим значение параметра хЛ+1:
Ti+l
(Cvk
■ 
vk)
II Со* ||*
(51)
Обратимся теперь к уравнению (50) и исключим из него выра­
жение (Со*, Со*-,). Из уравнения (29) получим
Со*_, = — о*_, 
— -
-----
[vk
— 
(1
— a*) и*_2],
(52)
klk
следовательно,
(Со*, Со*_,) = — (Со*, 
vk-!)
----- [(Си*, 
vk)
— (1 — a*) (
Cvk, vk-2)].
4
ak4
Согласно (45) имеем
(Co*, 
vk-i)
= (o*, 
Cvk-J =
0
, 
(Co*, o*_2) 
= (vk, Ськ-2) =
0.
Поэтому
(Си*, Co*_,) 
=
-------- (Co*, 
vk).
anxk
Подставляя это выражение в (50), получим
afe+iTfe*i 
(с^> 
vt)
akxk 
(Cvk-i- vk-i)
1
— a
*+1
=
0
.
125

---

Отсюда приходим к рекуррентной формуле для параметров оц+1:
k =
1, 2, . . ., otj = 1. (53)
Формулами (51), (53) задаются выражения для итерационных 
параметров в методе сопряженных градиентов. Скалярные произ­
ведения, входящие в эти выражения, вычисляются в процессе ите­
раций. Учитывая, что
vk = Av,zk, С = AV'B~1AV‘, zk = xk — x, Azk — Axk — f = r k,B -1rk= w k,
получим 
Cvk= A l/2wk, (CVb, vh) = (wk, rk), (Cvh, Cvh) = (Awh, w„).
Поэтому окончательно приходим к следующим формулам для 
определения итерационных параметров в методе сопряженных гра­
диентов:
—
TA+l 
1
(Cvk, vk)
Ч
'«A 
(Cvk-V Vk~i)
:
к .
rk)
6
=
0
, 
1
, . . . .
®*+i —
(Awk, wk)
4+1
1
(®A- 
4
)
1
4 ak (Awk~v wk~i)
k = l ,
2
,
(54)
ax
=
1
. (55)
7. Оценка погрешности в методе сопряженных градиентов.
Выше отмечалось, что в методе сопряженных градиентов точное ре­
шение системы уравнений (
1
) получается за конечное число итера­
ций, равное порядку системы. Если порядок системы велик, то мо­
жет оказаться полезной и оценка погрешности. Эта оценка не хуже, 
чем в одношаговом итерационном методе с чебышевским набором 
параметров. Действительно, из выражения для погрешности (33) 
получаем
llvJ = llxn- x llA^HPn(C) Hllxa- x llA.
Поскольку Р п(С) — многочлен степени 
п
от оператора 
С,
удо­
влетворяющий условию Р„(0)= .Е , выполняется оценка
\Рп(С)Ш Тп{С)1
2
р"
1
+
р
Г
P
i
—
1
- К б
1 + / I
где 
Т
п— многочлен Чебышева, наименее уклоняющийся от нуля на 
["Ь Та]. 7\.(0) =
1
-
Таким образом, для погрешности метода сопряженных градиен­
тов справедлива оценка
\\хп—
*
II
A
sS 
< 7 * 1 1 - 4 —
я
|1
а
.
где g„ = 2p"/(l + p jn).
126

---

Г Л А В А 3
ИНТЕРПОЛИРОВАНИЕ И ПРИБЛИЖЕНИЕ ФУНКЦИЙ
В настоящей главе излагаются вычислительные аспекты некото­
рых задач теории приближения функций. Задача интерполирования 
состоит в том, чтобы по значениям функции 
f ( x )
в нескольких точ­
ках отрезка восстановить ее значения в остальных точках этого 
отрезка. Разумеется, такая задача допускает сколь угодно много 
решений. Задача интерполирования возникает, например, в том 
случае, когда известны результаты измерения 
yh= f { x k)
некоторой 
физической величины 
f(x)
в точках 
хк,
& =
0
, 
1
, . . . ,
п,
и требуется 
определить ее значения в других точках. Интерполирование 
используется также при сгущении таблиц, когда вычисление зна­
чений 
f\x)
трудоемко. Иногда возникает необходимость прибли­
женной замены или аппроксимации данной функции другими 
функциями, которые легче вычислить. В частности, рассматривает­
ся задача о наилучшем приближении в нормированном простран­
стве Я, когда заданную функцию f e / / требуется заменить линей­
ной комбинацией ср заданных элементов из Я так, чтобы отклоне­
ние ||/—ср|| было минимальным. Результаты и методы теории ин­
терполирования и приближения функций нашли широкое примене­
ние в численном анализе, например при выводе формул численного 
дифференцирования и интегрирования, при построении сеточных 
аналогов задач математической физики.