num-meth
.pdf
1.3. Проблема собственных значений и собственных векторов матриц |
41 |
1.3.3Итерационные методы решения задачи собственных значений
1.3.3.1Метод итераций.
Известно, что, во-первых, собственные значения симметрических матриц – действительные числа, собственные векторы, принадлежащие разным собственным значениям, ортогональны. Собственный вектор, отвечающий собственному значению λ1, находится из уравнения:
Axˆ = λ1xˆ
Как известно из предыдущего подраздела, собственные векторы можно находить с точностью до постоянного множителя, поэтому можно предположить, что какая-то координата искомого вектора, например, координата xn, равна 1. Тогда исходное уравнения переписывается в виде:
|
|
1 |
|
|
|
|
|
. . . . . . |
. . |
. . |
. . . . . . . . . . . |
. . . . . . . . . . . . . . . . . . |
. . . . . . . . . . . . . . . |
. . . . . |
|
|
|
λ1 (a11x1 + a21x2 + · · · + a1,n−1xn−1 + a1n) |
|
||||
x1 = |
|
||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
xn 1 = |
|
(an 1,1x1 + an 1,2x2 + + an 1,n 1xn 1 + an 1,n) |
|||||
|
|||||||
|
λ1 = an1x11 + an2x2 + |
+ an,n−1·x·n·−1 + ann |
|
||||
|
− |
|
λ − |
− |
− − − |
− |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
· · · |
|
|
|
|
|
|
|
|
|
|
Полученную систему можно решать, например, каким-либо итерационным методом. В результате будет получено некоторое приближение искомого собственного числа λ1 и соответствующего собственного вектора.
Аналогичным образом поступают и с остальными собственными значениями и векторами, при этом для i-го собственного значение принимают равной 1 координату собственного вектора n−i+ 1. В результате, таким образом удастся найти (n−1) собственных значений и векторов. Последний собственный вектор можно отыскать из условия:
(ˆxλ1 , xˆλn ) = 0
. . . . . . . . . . . . . . .
(ˆxλn 1 , xˆλn ) = 0
Вприведенной выше системе всего лишь (n − 1) уравнений, тогда как неизвестных – n. Однако эту трудность легко преодолеть, если положить xn = 0 (это обосновано в силу того, что собственные векторы находятся с точностью до постоянного множителя).
Что же касается последнего собственного значения, то его можно отыскать с помощью любого из следующих равенств:
λ1 + λ2 + · · · + λn = a11 + a22 + · · · + ann
λ1λ2 . . . λn = |A|
1
λn = x(nλn) (an1x1 + an2x2 + · · · + an,n−1xn−1 + ann)
В последнем уравнении принято обозначение xˆ(λn) – собственный вектор, соответствующий собственному значению λn.
Описанный метод в некоторых случаях может либо плохо сходится, либо даже расходится для в случае неположительной симметрической матрицы. Поэтому надежнее его использовать только для положительных симметрических матриц.
42 |
Глава 1. Численные методы линейной алгебры |
1.3.3.2Метод врашений (Якоби).
Методя Якоби – наиболее употребительный в решении проблемы собственных значений для симметрических матриц. Использование данного метода связано с спектральным разложением симметрической матрицы A:
A = T −1ΛT,
где Λ диагональная матрица, на диагонали которой расположены собственные значения, а столбцы ортогональной матрицы T – это собственные векторы матрицы A. Суть приближенного вычисления матриц A и T в построение последовательностей:
A0 = A, A1, . . . , Ak, · · · → Λ
T0 = E, T1, . . . , Tk, · · · → T
Причем элементы этой последовательности рассчитываются по формулам:
Ap+1 = TijTApTij, Tp+1 = TpTij
В этих формулах, Tij – матрица простых вращений, имеющая следующий вид:
|
|
1 ... |
|
.. .. .. |
|
|
|
1 . . . |
|
|
|
|
||
T |
= |
|
|
|
|
. . . |
cos α |
||
|
|
. . . . . . |
||
|
|
|
|
. . . |
|
|
|
|
|
ij |
|
|
|
. . . |
|
|
|
||
|
|
|
|
. . . |
|
|
|
|
|
|
|
|
. . . |
sin α |
|
|
. . . . . . |
||
|
|
|
|
. . . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. . . |
|
|
|
|
|
|
|
|
|
. . . |
|
|
|
− |
.. .. .. |
|
|
|
|
|
|
. . . |
|
|
|
|
|
|
|
|
|
|
|
|
.. |
|
|
|
|
|
|
|
. . . . . . |
. . . |
|
sin α . . . |
. . . |
. . . i-я строка |
||
1 |
|
|
|
. . . |
|
|
|
|
|
|
|
|
|
||
|
. |
|
|
. . . |
|
|
j |
|
|
|
|
|
|
||
|
|
1 . . . |
|
|
|
||
|
|
|
|
|
|||
. . . . . . |
. . . |
cos α . . . |
. . . |
|
|
||
. . . -я строка |
|||||||
|
|
|
|
. . . 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. . . |
... |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
. . . |
|
1 |
|
Матрица простых вращений строится следующим образом. В матрице Ak выбирают наибольший по модулю недиагональный коэффициент a(ijk). Угол α выбирают так, чтобы этот элемент в результирующей матрице Ak+1 оказался равен 0. Легко видеть, что этот элемент в результате перемножения можно вычислить по формуле:
a(ijk+1) = (cos2 α − sin2 α)a(ijk) + cos α · sin α(a(jjk) − a(iik))
Приравнивая это выражение к 0, получаем соотношение:
|
2aij(k) |
π |
|
tg(2α) = |
|
, |α| ≤ |
|
ajj(k) − aii(k) |
4 |
||
Отсюда, по формулам, известным из курса тригонометрии, записываем:
cos 2α = |
|
|
|
|
1 |
|
|
|
|
|
|
||
√ |
|
|
||||
1 + tg22α |
||||||
cos α = √ |
|
1 + |
cos 2α |
|||
|
|
|||||
|
2 |
|
||||
1.3. Проблема собственных значений и собственных векторов матриц |
43 |
|||||
|
|
|
|
|
|
|
sin α = ±√ |
1 − |
cos 2α |
|
|||
2 |
|
|
|
|||
|
|
|
|
|||
Чтобы выполнялось условие |α| ≤ π4 , в выражении для синуса знак выбирают так,
чтобы он совпадал со знаком выражения: a(ijk)(a(jjk) − a(iik)).
Отличительная черта описанного алгоритма заключается в его быстрой сходимости. Для выполнения одного шага этого алгоритма требуется порядка 2n2 арифметических операций.
1.3.3.3QR-алгоритм
Наиболее надежный и общеупотребительным методом решения полной проблемы собственных значений для случая матриц общего вида является QR-алгоритм. Данный метод был открыт в 1960-хх годах Дж. Френсисом и Кублановской. Суть алгоритма сводится к следующему.
Строится последовательность подобных матриц:
A0 = A, A1, . . . , Ak, . . .
по следующему правилу. Матрицу Ak−1 представляют ее QR-разложением Ak−1 = QkRk
и далее полагают Ak = Q−k 1Ak−1Qk = Q−k 1(QkRk)Qk = (Q−k 1Qk)RkQk = ERkQk = RkQk. Т.е. по сути, имея QR-разложение матрицы Ak−1, матрицу Ak получают перестановкой
сомножителей в QR-разложении. При этом имеет место
Ak = Q−k 1Ak−1Qk
=Q−k 1Q−k−11 . . . Q−1 1AQ1 . . . Qk−1Qk
=(Q1 . . . Qk−1Qk)−1A(Q1 . . . Qk−1Qk)
=P −1AP,
где матрица P – ортогональная (по свойству произведения ортогональных матриц). Получаемая таким образом последовательность матриц {Ak}∞k=0 сходится к верхнетреугольной матрице, диагональные элементы которой является характеристическими числами как этой матрицы, так и всех элементов последовательности (которые подобны этой треугольной матрице). На практике, однако, критерий останова – это соблюдение условия, что все поддиагональные элементы матрицы Ak по модулю меньше некоторого заранее заданного числа ε, характеризующего точность вычислений.
Поскольку описанный процесс осуществляется примерно в n/2 раз быстрее, если исходная матрица – почти треугольная, и еще на порядок быстрее, если она – трехдиагональная, то перед началом описанного процесса обычно стремятся привести матрицу к почти треугольному или трехдиагональному виду.
Еще один метод ускорения процесса – это принудительное зануление поддиагональных элементов, достаточно малых по модулю. Пусть на некотором шаге получена матрица:
. . . .. .... . |
. . . |
. . . |
|
|
|
n |
|
|
|
|
|
. . . |
|
||
. . . |
ε |
λ′ |
|
Если величиной ε можно пренебречь, то полагают λn = λ′n и далее работают с матрицей порядка (n − 1).
44 |
Глава 1. Численные методы линейной алгебры |
Третий важный способ ускорения процесса заключается в использовании сдвигов. На каждом шаге выбирается некоторое число vk, так что QR-разложение строится для матрицы Ak−1 − vkE. Соответственно, матрица Ak записывается как:
Ak = RkQk + vkE
В качестве коэффициента vk выбирают или элемент в правом нижнем углу матрицы Ak−1, или же наиболее близкое к нему по модулю собственное значение подматрицы
()
(k−1)
an−1,n−1 (k−1)
an,n−1
(k−1)
an−1,n a(n,nk−1)
1.4Оценка погрешности решения системы линейных уравнений
В этом параграфе будут использоваться матричные нормы, согласованные с векторными нормами, и потребуется следующее вспомогательное утверждение.
Лемма. Пусть квадратная матрица C удовлетворяет условию C < 1. Тогда для матрицы (E + C) существует обратная ей (E + C)−1 и ее норма
(E + C)−1 ≤ |
|
1 |
|
|
|
|
|
|
|
1 |
− |
C |
|
|
|
|
|
Доказательство. Любое собственное значение матрицы C по модулю не превосходит ее спектрального радиуса λC . При этом λC меньше любой нормы матрицы C, и в частности рассматриваемой нормы. Поэтому все собственные значения λ1, λ2, . . . , λn матрицы C лежат в круге |λ| < 1 с центром в начале координат, т.е. в круге разложимости функции f(λ) = (1 + λ)−1 в ряд
1 − λ + λ2 − λ3 + . . . .
Это гарантирует сходимость матричного ряда
E− C + C2 − C3 + . . . ,
апотому гарантирует существование суммы этого ряда – матрицы (E + C)−1. Учитывая соотношения C < 1, E = 1 и AB ≤ A · B , для нормы матрицы
(E + C)−1 получаем |
|
|
|
|
|
(E + C)−1 = 1 + C + C2 + C3 + · · · ≤ 1 + C + C 2 + C 3 + · · · = |
|
1 |
|
|
. |
|
|
|
|
||
1 |
− |
C |
|
||
Перейдем к оценке погрешности решения системы линейных уравнений. |
|
|
|
||
|
|
|
|
|
|
Пусть |
|
|
(1.38) |
||
Ax = b |
|
|
|||
– исходнай система линейных уравнений с квадратной невырожденной матрицей A n-го порядка, и
(A + δA)(x + δx) = b + δb |
(1.39) |
– возмущенная система. Здесь x – решение данной системы, xB = x + δx – решение возмущенной системы.
Вычитая равенство (1.38) из (1.39), получим
δA · x + (A + δA) · δx = δb. |
(1.40) |
1.4. Оценка погрешности решения системы линейных уравнений |
45 |
Представим матрицу A + δA в виде |
|
A + δA = A · (E + A−1δA) |
|
и предположим, что |
(1.41) |
A−1 · δA < 1. |
Тода
A−1 · δA ≤ A−1 · δA < 1, |
|
|
|||||
И в силу леммы для матрицы (E + A−1δA) существует обратная матрица, норма которой |
|||||||
(E + A−1δA)−1 ≤ |
|
|
1 |
|
|
. |
|
|
|
|
|
|
|
||
1 |
− |
A−1 |
· |
δA |
|
||
|
|
|
|
|
|||
Поэтому матрица
[]−1
(A + δA)−1 = A · (E + A−1δA) = (E + A−1δA)−1 · A−1,
и из равенства (1.40) получаем равенство |
|
|
|
|
|
|
|
|
|
||
δx = (E + A−1δA)−1 · A−1(δb − δA · x). |
|
||||||||||
Отсюда следует соотношение |
|
|
|
|
|
|
|
|
|
|
|
δx |
A−1 |
·( |
δA |
· |
x |
|
+ |
|
δb |
. |
|
1 − A−1 · δA |
|||||||||||
≤ |
|
|
|
|
) |
||||||
Из равенства Ax = b вытекает соотношение b ≤ A · x , откуда α =
Усилим неравенство (1.42), умножив в нем слагаемое δb на число α:
δx |
|
|
A−1 |
|
|
|
δA |
· |
x |
|
+ |
δb · A · x |
. |
||||||||
|
|
|
|
|
|
|
b |
||||||||||||||
≤ 1 − A−1 · δA ·( |
|
|
|
|
|
|
|
) |
|||||||||||||
Преобразуем полученное неавенство к виду |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
δx |
|
A−1 |
A · x |
|
|
|
|
|
δA |
+ |
δb |
. |
|
|||||||
|
≤ |
|
|
δA ·( |
|
|
|
||||||||||||||
|
1 A−1 · |
A |
|
|
A b ) |
|
|||||||||||||||
|
|
|
− |
· |
|
· |
|
A |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Ведем обозначение
K(A) = A−1 · A .
Тогда неравенство (1.43) запишем как
(1.42)
A · x ≥ 1.b
(1.43)
(1.44)
|
|
δx |
|
= |
|
x |
B − |
x |
≤ |
|
|
K(A) · x |
|
|
·( |
δA |
+ |
δb |
. |
(1.45) |
||||||||||||
|
1 |
|
δA |
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
− |
K(A) |
· |
|
A |
|
|
|
b ) |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Число K(A) называют числом обусловленности матрицы A в рассматриваемой мат- |
||||||||||||||||||||||||||||||||
ричной норме. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Разделим неравенство (1.45) на x : |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
δx = xB − x |
|
|
|
K(A) |
|
|
|
|
|
|
δA + δb . |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
≤ |
|
|
|
|
|
|
|
·( |
|
|
|
|
|
) |
(1.46) |
|||||||
|
x |
|
|
|
|
x |
|
|
|
|
|
|
|
δA |
|
A |
|
|
b |
|||||||||||||
A
46 |
Глава 1. Численные методы линейной алгебры |
Таким образом, если невырожденная матрица A и столбец b системы линейных уравнений Ax = b получают возмущения δA и δb, причем в некоторой матричной формеA−1 · δA < 1, то возмущенная система имеет единственное решение xB = x + δx
и относительная погрешность δx решения Ax = b оценивается через относительные
x
возмущения δA и δb формулой (1.46) в рассматриваемой норме.
A b
Чем больше число обусловленности матрицы системы, тем большими будут абсолютная и относительная погрешности решения этой системы. Системы линейных уравнений, у которых матрицы имеют большие числа обусловленности, называют плохо обусловленными. Число обусловленности определяется не только матрицей, но и выбором нормы.
Отметим некоторые свойства числа обусловленности. Непосредственно из его опреде-
ления вытекает, что |
(1.47) |
K(A) = K(A−1). |
|
Перемножая неравенства AB ≤ A · B и (AB)−1 = B−1A−1 ≤ B−1 · A−1 , |
|
получим соотношение |
(1.48) |
K(AB) ≤ K(A) · K(B). |
|
Из соотношения E = A−1A следует, что E = A−1A ≤ A−1 · A = K, т.е. |
|
K(A) ≥ E ≥ 1. |
(1.49) |
Пусть σ1 и σn – наибольшее и наименьшее сингулярные числа матрицы A. Тогда спектральная норма A = σ1, а спектральная норма A−1 = σn−1. Поэтому для спектрального числа обусловленности матрицы A получаем
KC (A) = |
σ1 |
. |
(1.50) |
|
|||
|
σn |
|
|
Отсюда следует, что спектральное число обусловленности ортогональной (унитарной) матрицы равно единице. Поэтому спектральное число обусловленности матрицы A не меняется при ее умножении на ортогональную (унитарную) матрицу. В силу этого при решении системы Ax = b предпочтительно трансформировать эту систему с помощью ортогональных (унитарных) преобразований.
Глава 2
Полиномиальная интерполяция функций
2.1Задача аппроксимации функций. Полиномиальная аппроксимация
При исследовании некоторой функции f(x) часто оказывается более удобным исследовать не саму эту функцию, а некоторую другую функцию, ϕ(x), близкую, с одной стороны, к f(x), но, с другой стороны, более легкую и удобную для выполнения над ней аналитических и вычислительных операций. Такая подмена называется аппроксимацией, или приближением, функции f(x) функцией ϕ(x).
В зависимости от решаемых задач, бывает удобно использоваться в качестве функции ϕ(x) функции того или иного вида, например, экспоненты, полиномы, тригонометрические функции. Мы будем рассматривать только случай полиномиальной аппроксимации (т.е. случай приближения полиномиальными или кусочно-полиномиальными функциями).
Формальная процедура, позволяющая оценить, на сколько хорошо функция ϕ(x) приближает исходную функцию f(x), называется критерием согласия. В зависимости от того, в скольких точках (узлах) известна информацию о f(x) и многочленом какой степени нужно приближать эту функцию, приходят к различным методам приближения. В качестве критерия согласия можно, например, выбрать совпадение значений функций f(x) и ϕ(x), совпадение значений в узлах как самих функций f(x) и ϕ(x), так нескольких их производных, минимум максимального отклонения, минимум среднеквадратичного отклонения и т.д.
В дальнейшем, без ограничения общности, можно считать, что функция f(x) задана на данной отрезке [a, b] сеткой своих значений (т.е. для каждой из точек x0, . . . , xn известны значения функции y0 = f(x0), . . . , yn = f(xn)).
Тогда некоторую данную функцию ϕ(x) называют интерполирующей или интерполяционной для f(x) на отрезке [a, b], если эти две функции совпадают в узлах интерполяции, т.е. для всех xi, i = 0, n, имеет место: ϕ(xi) = f(xi). Очевидно, что таких функций, в общем случае, можно подобрать бесконечное количество. Однако мы ограничиваемся только полиномами.
Задача полиномиальной интерполяции заключается в нахождении для функции f(x), заданной сеткой своих значений, такого полинома Pn(x) степени n, чтобы выполнялось условие интерполяции:
Pn(xi) = f(xi) − yi = 0, i = 0, n
47
48 |
Глава 2. Полиномиальная интерполяция функций |
2.2Интерполяционный многочлен Лагранжа
∑n
Интерполяционный многочлен Ln(x) будем искать в виде линейной комбинации cili(x)
i=0
полиномов степени n. Для того чтобы этот многочлен удовлетворял условию интерполяции, потребуем, чтобы ci = yi, i = 0, n, и:
|
0, j ̸= i |
|
|
|
li(xj) = δij = |
, i, j = 0, n |
|||
|
{1, i = j |
|
|
i∑ |
|
|
|
|
n |
В этом случае, искомый интерполяционный многочлен принимает вид Ln(x) = yili(x),
=1
и для xiLn(xi) = yi. Исходя из требования li(xj) = δij, запишем:
li(x) =
(x − x0) . . . (x − xi−1)(x − xi+1) . . . (xi − xn)
(xi − x0) . . . (xi − xi−1)(xi − xi+1) . . . (xi − xn)
Искомый полином записывается в виде:
n |
|
(x − x0) . . . (x − xi−1)(x − xi+1) . . . (xi − xn) |
|||||||||
Ln(x) = |
yi |
||||||||||
∑i |
|
(xi |
− |
x0) . . . (xi |
− |
xi |
1)(xi |
− |
xi+1) . . . (xi |
− |
xn) |
|
|
|
− |
|
|
|
|||||
=0 |
|
|
|
|
|
|
|
|
|
|
|
Этот полином называется интерполяционным полиномом Лагранжа, а базисные многочлены li(x) – базисными полиномами Лагранжа. Частные случае этого полинома для n = 1 и n = 2 (линейный и квадратичный интерполяционный многочлены) записываются, соответственно, в виде:
L1(x) = y0 x − x1 x0 − x1
+ y1 x − x0 x1 − x0
L2(x) = y0 |
(x − x1)(x − x2) |
+ y1 |
(x − x0)(x − x2) |
+ y2 |
(x − x0)(x − x1) |
|
(x0 − x1)(x0 − x2) |
(x1 − x0)(x1 − x2) |
(x2 − x0)(x2 − x1) |
||||
|
|
|
Равенства f(x) ≈ L1(x) и f(x) ≈ L2(x) называются, соответственно, формулами линейной и квадратичной интерполяции. Геометрическая интерпретация этих формул заключается в подмене исходной функции ее кусочно-линейным и кусочно-квадратичным приближением соответственно, а графики заменяются в первом случае ломанной линией, а во втором – совокупностью участков квадратичной параболы.
Использование простых интерполяционных формул позволяет довольно легко вычислять приближенные значения исходной функции в точках, отличных от узлов (в том числе и в точках, лежащих за пределами отрезка [a, b], в каковом случае иногда говорят об экстраполяции функции).
Утверждение 2.2.1. Для всякой заданной сеткой своих значений функции f(x) интерполяционный многочлен Лагранжа степени n строится единственным образом.
Доказательство. Предположим обратное. Пусть наряду с многочленом Ln(x) есть другой многочлен, Qn(x), отличный от первого. Тогда рассмотрим разность этих многочленов: Pn(x) = Ln(x) − Qn(x). Поскольку, по предположению, оба многочлена Ln(x и Qn(x), являются интерполяционными, то оба они совпадают в узлах интерполяции, а значит рассматриваемый многочлен Pn(x) должен обращаться в 0 в (n + 1) точках, что равносильно тому, что у этого многочлена n + 1 корней. Однако, многочлен Pn(x) имеет степень не выше n, и следовательно, не может иметь более, чем n корней. Следовательно наше предположение оказалось неверным.J
2.2. Интерполяционный многочлен Лагранжа |
49 |
Таким образом, интерполяционный многочлен Лагранжа определяется единственным образом по n + 1 точкам приближаемой функции.
Теперь займемся определением погрешности приближения полиномом Лагранжа. Заметим, что в самом общем случае через n + 1 точку можно провести сколько угодно
функций, из которых все будут аппроксимироваться одним и тем же, единственным образом определенным, многочленом. Поэтому многочлен Лагранжа применяется лишь для достаточно гладких функций.
Будем считать, что функция f(x) Cn+1[a, b]. Построим сначала следующую функцию:
∏n
Πn+1(x) = (x − xi)
i=0
Очевидно, что это полином степени n + 1 с нулями в узлах интерполяции. Возьмем теперь функцию:
u(x) = f(x) − Ln(x) − cΠn+1(x),
где c – некоторый параметр-константа. Согласно услвию интерполяции, функция f(x) − Ln(x) в узлах интерполяции обращается в 0, а значит в 0 общается и функция u(x). Теперь, выберем параметр c так, чтобы у функции u(x) имелся добавочный (n + 2)-й корень в некоторой точке x, отличной от узлов интерполяции. Этого легко добиться, если потребовать:
u(x) = f(x) − Ln(x) − cΠn+1(x) = 0
Откуда получаем:
c = f(x) − Ln(x) Πn+1(x)
Учтем, что x ≠ xi, а значит, x не является корнем Πn+1(x), следовательно, такая константа всегда найдется.
Точки xi, i = 0, n и x – это (n + 2) корня функции u(x), и эти точки создают разбиение отрезка [a, b] на n + 1 отрезков. На концах этих отрезков функция u(x) обращается в 0, а значит, на каждом отрезке применима теорема Ролля, согласно которой на каждом таком отрезке найдется, по меньшей мере, одна такая точка, в которой обращается в 0 функция u′(x). Аналогичным образом, найдется, по крайней мере, n точек, в которых обращается в 0 вторая производная u′′(x). Продолжая рассуждения, найдем, что существует, по крайней мере, одна точка ξ, такая что u(n+1)(ξ) = 0. Заметим, что L(nn+1)(x) = 0. Кроме того, Π(nn+1+1)(x) = (n + 1)!. Поэтому можно записать:
u(n+1)(ξ) = f(n+1)(ξ) − c(n + 1)! = 0
f(n+1)(ξ)
Откуда сразу находим c = (n + 1)! . Однако ранее мы уже определили эту константу, и оба выражения должны быть равны:
f( |
|
) − Ln( |
|
) |
= |
f(n+1)(ξ) |
|
||||
x |
x |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Πn+1( |
|
) |
|
(n + 1)! |
|
|||||
|
x |
|
|||||||||
Из этого равенства находим остаточный член: |
|
||||||||||
Rn(x) = f(x) − Ln(x) = |
|
f(n+1)(ξ) |
Πn+1(x) |
||||||||
|
|
||||||||||
|
(n + 1)! |
||||||||||
50 |
Глава 2. Полиномиальная интерполяция функций |
2.3Интерполяционная схема Эйткена
+ y1 x − x0 , x1 − x0
а это в точности первый многочлен Лагранжа. Возьмем далее две точки x1 и x2. Тогда функция P1,2(x) запишется в виде:
|
|
− |
|
|
|
− |
|
|
P1,2(x) = x2 |
1 |
x1 |
|
x |
x1 |
y1 |
|
|
|
x |
− x2 |
y2 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Легко видеть, что это тоже многочлен Лагранжа первой степени:
P1,2(x) = y1 |
x − x2 |
+ y2 |
x − x1 |
|
x2 − x1 |
||
|
x1 − x2 |
||
Если теперь взять три точки x0, x1 и x2 и построить по ним следующую функцию:
|
|
− |
|
|
|
− |
|
|
P0,1,2(x) = |
x2 |
1 |
x0 |
|
x x0 |
P0,1(x) |
|
|
|
x |
− x2 |
P1,2(x) |
|||||
|
|
|
|
|
|
|
|
|
Легко проверить, что эта функция |
является |
многочленом Лагранжа третьей степени. |
||||||
В общем случае, выбирая n точек (строя приближенное вычисление функции в некоторой точке по n точкам), получим следующую рекуррентную формулу:
|
|
1 |
|
|
x |
x0 P0,1,...,n−1 |
(x) |
|
f(x) ≈ P0,1,...,n(x) = |
|
|
|
x |
− xn P1,2,...,n−1 |
(x) |
||
xn |
− |
x0 |
||||||
|
|
|
|
|
− |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Постепенно увеличивая n, можно добиться необходимой точности вычислений, причем проведенные вычисления накапливаются, т.е. на каждом последующем шаге используются результаты всех предыдущих.
Описанный процесс называется интерполяционной схемой Эйткена.
Мы уже видели, что приведенная формула при n = 1 и n = 2 совпадает с многочленом Лагранжа соответствующей степени. По индукции можно показать также, что формула Эйткена является просто иной формой записи многочлена Лагранжа (т.е. эквивалента ему).
