Методическое пособие для практических и лабораторных работ по курсу «Численные методы»

136
тогда, подставляя данные значения точек и приравнивая левую часть соответствующему значению
i
z , получаем систему
)
1
(
+
n
линейных алгебраических уравнений относительно
2
)
2
)(
1
(
)
1
(
2 1
+
+
=
+
+
+
+
m
m
m
неизвестных
ij
a
. Эти уравнения, вообще говоря, независимы. Следовательно, если на
)
,
(
y
x
P
не накладывать дополнительных условий, то
)
1
(
+
n
должно равняться
2
)
2
)(
1
(
+
+
m
m
. Это первое принципиальное затруднение, т.е. уже не можем решить задачу при произвольном количестве узлов интерполирования.
Пусть
2
=
n
. Рассмотрим определитель полученной системы
2 2
1 1
0 0
1 1
1
y
x
y
x
y
x

Этот определитель обращается в нуль, если три точки
)
,
(
0 0
y
x
,
)
,
(
1 1
y
x
,
)
,
(
2 2
y
x
лежат на одной прямой, и поэтому возникает вопрос о существовании и единственности решения. Аналогично соответствующие определители будут обращаться в нуль, если точки – узлы интерполяции будут лежать на кривых второго, третьего и т.д. порядков. Это порождает второе
принципиальное затруднение: узлы интерполирования не могут быть расположены произвольно. Проверка того, что определители не обращаются в нуль, чрезвычайно затруднительна. Третье принципиальное затруднение возникает при оценке остаточного члена. Теорема Ролля для рассматриваемого случая не действует.
В связи с указанными трудностями, рассмотрим специальный случай двумерной интерполяции.
Возьмем
2
)
2
)(
1
(
+
+
n
n
узлов и расположим их следующим образом
),
,
(
),
,
(
),
,
(
.
.
),
,
(
,
),
,
(
),
,
(
),
,
(
),
,
(
,
),
,
(
),
,
(
0 1
1 1
0 1
1 1
1 1
0 0
0 1
0 1
0 0
n
n
n
n
n
n
y
x
y
x
y
x
y
x
y
x
y
x
y
x
y
x
y
x
y
x
−
−
−
−
(
j
i
x
x
≠
,
j
i
≠
;
j
i
y
y
≠
,
j
i
≠
).
(14.27)

137
Значения
i
x и
j
y могут быть произвольными, так что взаимное расположение узлов может быть довольно общим. Проверим, что нет кривой
n -го порядка, проходящей через все эти узлы. В самом деле, если бы такая кривая имелась, она содержала бы точки, расположенные в первом ряду.
Этих точек
)
1
(
+
n
, и все они лежат на одной прямой. Следовательно, вся прямая также принадлежала бы кривой порядка n . В этом случае кривая порядка n распалась бы на прямую и кривую порядка
)
1
(
−
n
, проходящую через все остальные
2
)
1
(
+
n
n
точек.
Для нее провели бы аналогичные рассуждения. Продолжая этот процесс, мы в конце концов пришли бы к заключению, что три точки
)
,
(
1 0
−
n
y
x
,
)
,
(
1 1
−
n
y
x
и
)
,
(
0
n
y
x
лежат на одной прямой. Этого нет.
Следовательно, выбранные нами узлы не могут лежать на одной кривой порядка n .
Построим теперь интерполяционный полином по нашим узлам.
Обозначим его через
)
,
(
y
x
P
n
, а
)
,
(
j
i
n
y
x
P
через
ij
z , где
ij
z – соответствующие значения функции в узлах.
Если рассмотреть только те из выбранных нами узлов, для которых
n
j
i
<
+
, то на тех же основаниях мы можем построить интерполяционный многочлен
)
,
(
1
y
x
P
n
−
степени
)
1
(
−
n
, принимающий в точках
)
,
(
j
i
y
x
,
n
j
i
<
+
, значения
ij
z .
Образуем разность
)
,
(
)
,
(
1
y
x
P
y
x
P
n
n
−
−
. Она будет многочленом степени не выше n , обращающимся в нуль в точках
)
,
(
j
i
y
x
,
n
j
i
<
+
. Представим эту разность в виде
).
)...(
)(
(
)
)(
)(
)...(
(
)
)(
)...(
(
)
)...(
(
)
,
(
)
,
(
1 1
0
,
0 1
0 3
0 2
,
2 0
2 0
1
,
1 1
0 0
,
1
−
−
−
−
−
−
−
−
−
−
+
+
−
−
−
−
+
+
−
−
−
+
−
−
=
−
n
n
n
n
n
n
n
n
n
n
y
y
y
y
y
y
A
y
y
y
y
x
x
x
x
A
y
y
x
x
x
x
A
x
x
x
x
A
y
x
P
y
x
P

Покажем, что можно так подобрать
i
i
n
A
,
−
, что этот многочлен обращающийся в нуль в точках
)
,
(
j
i
y
x
,
n
j
i
<
+
, будет равен
)
,
(
)
,
(
1
j
i
n
j
i
n
y
x
P
y
x
P
−
−
при
n
j
i
=
+
В точке
)
,
(
i
n
i
y
x
−
все его члены обратятся в нуль за исключением
)
)...(
)(
)...(
(
1 0
1 0
,
−
−
−
−
−
−
−
−
−
−
i
n
i
n
i
n
i
i
i
i
n
i
y
y
y
y
x
x
x
x
A
. Таким образом, коэффициенты
i
n
i
A
−
,
определяются однозначно. В силу единственности интерполяционного многочлена по выбранным нами узлам это и будет единственным значением разности. Итак

138
∑
=
−
−
−
−
−
−
−
−
−
+
=
n
i
i
i
n
i
i
n
n
n
y
y
y
y
x
x
x
x
A
y
x
P
y
x
P
0 1
0 1
0
,
1
)
)...(
)(
)...(
(
)
,
(
)
,
(
(14.28)

Поступая также с
)
,
(
1
y
x
P
n
−
,
)
,
(
2
y
x
P
n
−
и т.д. получим
).
)...(
(
)
)(
)...(
(
)
)...(
(
...
)
)(
(
)
)(
(
)
)(
(
)
(
)
(
)
,
(
1 0
0 0
2 0
1
,
1 1
0 0
1 0
02 0
0 11 1
0 20 0
01 0
10 00
−
−
−
−
−
−
+
+
−
−
−
+
−
−
+
+
−
−
+
−
−
+
+
−
−
+
−
+
−
+
=
n
n
n
n
n
n
n
y
y
y
y
A
y
y
x
x
x
x
A
x
x
x
x
A
y
y
y
y
A
y
y
x
x
A
x
x
x
x
A
y
y
A
x
x
A
A
y
x
P
(14.29)

Выразим теперь
ij
A через значения функции
)
,
(
l
k
kl
y
x
f
z
=
в узлах сетки. Подставляя в правую часть
)
,
(
0 0
y
x
получим
)
,
(
0 0
00 00
y
x
f
z
A
≡
=
. В точке
)
,
(
0 1
y
x
)
,
(
0 1
y
x
f
P
n
=
, а правая часть (14.29) равна
)
(
0 1
10 00
x
x
A
A
−
+
, следовательно
0 1
0 0
0 1
10
)
,
(
)
,
(
x
x
y
x
f
y
x
f
A
−
−
=

Это отношение является разделенной разностью функции
)
,
(
0
y
x
f
при фиксированном
0
y
y
=
. Обозначим его через
)
;
;
(
0 1
0
y
x
x
f
. Аналогично получаем
)
;
;
(
1 0
0 01
y
y
x
f
A
=
. Зафиксируем теперь
0
y
y
=
, получаем
)
)...(
(
)
)(
(
)
(
)
,
(
1 0
0 1
0 20 0
10 00 0
−
−
−
+
+
−
−
+
−
+
=
n
n
x
x
x
x
A
x
x
x
x
A
x
x
A
A
y
x
P

Что мы получили? Это интерполяционный полином относительно x , принимающий в точках
)
,
(
0
y
x
i
значения
)
,
(
0
y
x
f
i
. Следовательно, вспоминая, что такое интерполяционный полином Ньютона, видим, что
)
;
;...
;
(
0 1
0 0
y
x
x
x
f
A
i
i
=

При
1
y
y
=
наш интерполяционный полином
)
,
(
y
x
P
n
принимает вид
).
)...(
(
)
)...(
)](
(
[
...
)
)(
)](
(
[
)
)](
(
[
)]
(
[
)
,
(
1 0
0 2
0 0
1 1
,
1 0
,
1 1
0 0
1 21 20 0
0 1
11 10 0
1 01 00 1
−
−
−
−
−
−
+
−
−
−
+
+
+
−
−
−
+
+
+
−
−
+
+
−
+
=
n
n
n
n
n
x
x
x
x
A
x
x
x
x
y
y
A
A
x
x
x
x
y
y
A
A
x
x
y
y
A
A
y
y
A
A
y
x
P

139
Этот интерполяционный полином относительно x должен в точках
)
,
(
1
y
x
i
,
1
,...,
1
,
0
−
=
n
i
, принимать значения
)
,
(
1
y
x
f
i
. Последний член при этих значениях
i
x обращается в нуль. Следовательно, все члены правой части кроме последнего дают интерполяционный полином Ньютона степени
)
1
(
−
n
, принимающий в точках
)
,
(
1
y
x
i
,
1
,...,
1
,
0
−
=
n
i
значения
)
,
(
1
y
x
f
i
Таким образом
)
;
;...;
;
(
)
(
1 1
0 0
1 1
0
y
x
x
x
f
y
y
A
A
k
k
k
=
−
+

Отсюда
0 1
0 1
0 1
1 0
1
)
;
;...;
;
(
)
;
;...;
;
(
y
y
y
x
x
x
f
y
x
x
x
f
A
k
k
k
−
−
=

Это разделенная разность по переменной y , обозначим ее так
)
;
;
;...;
;
(
1 0
1 0
1
y
y
x
x
x
f
A
k
k
=

Аналогично, если уже знаем
)
;...;
;
;
;...;
;
(
1 0
1 0
i
k
ki
y
y
y
x
x
x
f
A
=
для всех
m
i
<
, то рассматривая
)
,
(
m
y
x
P
, получаем
.
)
)](
)...(
)(
(
)
(
[
)]
)...(
(
)
(
[
)
,
(
0 1
1 0
1 0
11 10 1
0 0
0 01 00
+
−
−
−
−
+
+
−
+
+
−
−
+
+
−
+
=
−
−
x
x
y
y
y
y
y
y
A
y
y
A
A
y
y
y
y
A
y
y
A
A
y
x
P
m
m
m
m
m
m
m
m
m
m
m
m

Рассуждая как и прежде, найдем
)
;
;...;
;
(
)
)...(
(
)
(
1 0
1 0
0 1
0
m
k
m
m
m
km
m
k
k
y
x
x
x
f
y
y
y
y
A
y
y
A
A
=
−
−
+
+
−
+
−

Рассматривая это выражение, как функцию
m
y , получаем
)
;...;
;
;
;...;
;
(
1 0
1 0
i
k
ki
y
y
y
x
x
x
f
A
=

Таким образом, окончательно нашу интерполяционную формулу можем записать в виде
∑∑
∏
∏
=
−
=
−
=
−
=
−
−
⋅
=
n
i
i
n
j
i
p
j
q
q
p
j
i
n
y
y
x
x
y
y
x
x
f
y
x
P
0 0
1 0
1 0
0 0
)
(
)
(
)
;...;
;
;...;
(
)
,
(
(14.30)

140
Это – обобщенный интерполяционный полином Ньютона для неравных
промежутков в случае интерполирования функции двух переменных.

141
Лекция
15.
Наилучшее приближение в линейном нормированном пространстве. Существование и единственность элемента наилучшего приближения. Многочлен наилучшего приближения. Наилучшее приближение в гильбертовом пространстве. Метод наименьших квадратов. Аппроксимация функций многих переменных.

15.1.
Наилучшее приближение в линейном нормированном пространстве

Пусть
ℜ
– линейное нормированное пространство, элементами которого служат всевозможные действительнозначные функции
( )
x
f
, определенные на
[ ]
b
a,
0
ℜ
– это подпространство из
ℜ
,
ℜ
⊂
ℜ
0
. Пусть
0
ℜ
порождено базисом
( ) ( )
( )
{
}
x
x
x
n
ϕ
ϕ
ϕ
,...,
,
1 0
. Тогда любой элемент
0
)
(
ℜ
∈
Φ
x
представим в виде линейной комбинации с некоторыми действительными коэффициентами элементов базиса:
( )
( )
∑
=
=
Φ
n
i
i
i
x
a
x
0
ϕ
Функции из пространства
ℜ
будем аппроксимировать функциями из подпространства
0
ℜ
так, чтобы погрешность аппроксимации была наименьшей. Пусть
ℜ
∈
)
(x
f
Определение 1.
( )
0 0
ℜ
∈
Φ
x
называется элементом наилучшего приближения для
( )
ℜ
∈
x
f
, если
( )
( )
( ) ( )
x
x
f
x
x
f
Φ
−
=
Φ
−
ℜ
∈
Φ
0
inf
0
(
15.1)

Справедлива следующая теорема.
Теорема 1. Для любой функции
( )
ℜ
∈
x
f
существует элемент
наилучшего приближения
( )
0 0
ℜ
∈
Φ
x
.
Доказательство.
Введем обозначения:
)
,...,
,
(
)
(
1 0
0
n
n
i
i
i
a
a
a
x
a
Ф
ϕ
ϕ
=
=
∑
=
,
)
,...,
,
(
)
(
1 0
0
n
n
i
i
i
a
a
a
g
x
a
f
Ф
f
=
−
=
−
∑
=
ϕ
Если f зафиксировать и потребовать, что Ф пробегало
0
ℜ
, то
)
(ar
ϕ
и
)
(a
g r будут функциями переменных
n
a
a
a
,...,
,
1 0
. Докажем, что эти функции непрерывны. Рассмотрим, например
)
,...,
,
(
1 0
n
a
a
a
ϕ
. Имеем

142
(
) (
)
)
(
)
(
)
(
)
(
)
(
...,
,
,
...,
,
,
0
)
2
(
)
1
(
0
)
2
(
0
)
1
(
0
)
2
(
0
)
1
(
)
2
(
)
2
(
1
)
2
(
0
)
1
(
)
1
(
1
)
1
(
0
∑
∑
∑
∑
∑
=
=
=
=
=
−
≤
−
≤
≤
−
=
−
n
i
i
i
i
n
i
i
i
n
i
i
i
n
i
i
i
n
i
i
i
n
n
x
a
a
x
a
x
a
x
a
x
a
a
a
a
a
a
a
ϕ
ϕ
ϕ
ϕ
ϕ
ϕ
ϕ

Пусть
N
x
i
i
=
)
(
max
ϕ
и
)
1
(
+
=
n
N
ε
δ
. Тогда из того, что
δ
≤
−
)
2
(
)
1
(
i
i
a
a
следует, что
ε
ϕ
ϕ
≤
−
)
(
)
(
)
2
(
)
1
(
a
a
r r
. Непрерывность функции
)
(ar
ϕ
доказана, аналогично доказывается непрерывность функции
)
(a
g r . Итак функция
)
(a
g r непрерывная и неотрицательная. Пусть
0
≥
m
ее точная нижняя грань.
Докажем, что найдется такая точка
)
0
(
ar
, в которой эта нижняя грань достигается. Для этого в
)
1
(
+
n
-мерном Евклидовом пространстве рассмотрим сферу единичного радиуса:
{ }
1
/
:
0 2
0
=
∑
=
n
i
i
a
a
E
r
. Так как это замкнутое ограниченное множество, то непрерывная на нем функция
)
(ar
ϕ
достигает точной нижней грани
µ
. Очевидно, что
0
>
µ
, т.к. в противном случае в этой точке a
, где
0
)
(
=
a
ϕ
, было бы
0
)
(
0
=
=
∑
=
n
i
i
i
a
a
ϕ
ϕ
откуда
0 0
=
∑
=
n
i
i
i
a
ϕ
, что противоречит линейной независимости функций
)
(x
i
ϕ
. Итак,
0
>
µ
. Введем величину
µ
f
m
r
+
+
=
1
и разобьем все пространство точек
{ }
ar на две части
1
E и
2
E , где
{ }
r
a
a
E
n
i
i
≤
∑
=
0 2
1
/
:
r
,
(
15.2) а
2
E – все остальные точки
ar
. Рассмотрим теперь
)
(a
g r на
2
E . Пусть
2
E
a
∈
r
, тогда
∑
=
>
=
n
i
i
r
a
0 2
2 2
λ
, поэтому
1
)
(
0 0
0 0
+
=
−
>
−
≥
≥
−
≥
−
=
−
≥
−
=
∑
∑
∑
∑
=
=
=
=
m
f
r
f
f
a
f
a
f
a
a
f
a
g
i
n
i
i
n
i
i
n
i
i
i
n
i
i
i
µ
µ
λ
ϕ
λ
λ
λ
λ
ϕ
ϕ
r

143
Итак на
2
E
1
)
(
+
>
m
a
g r
. Следовательно,
m – это
)
(
inf
a
g r на множестве
1
E . Но согласно (15.2)
1
E – это замкнутое ограниченное множество. Значит непрерывная на нем функция
)
(a
g r обязательно достигает своей точной нижней грани в некоторой точке
1
)
0
(
E
a
∈
r
. Итак, существует точка
1
)
0
(
E
a
∈
r
, такая, что
0
)
0
(
0
inf
)
(
Ф
f
Ф
f
m
a
g
Ф
−
=
−
=
=
ℜ
∈
r
. Теорема доказана.
Эта теорема гарантирует только существование элемента наилучшего приближения в линейном нормированном пространстве и ничего не говорит об единственности. Следовательно, в общем случае в линейном нормированном пространстве элемент наилучшего приближения может быть не единственен.
Рассмотрим специальный случай.
Определение 2. Пространство называется строго нормированным, если равенство
2 1
2 1
f
f
f
f
+
=
+
справедливо тогда и только тогда, когда
2 1
f
f
α
=
, где
0
>
α
В таких пространствах справедлива теорема единственности.

Скачать 1.29 Mb.

Поделитесь с Вашими друзьями: